Анализ грамматики, записанной при помощи РБНФ. И еще один компилятор компиляторов.

Калькулятор позволяет оценить корректность LL1 грамматики в РБНФ формате, разобрать текст при помощи этой грамматики, просмотреть FIRST и FOLLOW наборы, создать парсер для использования внутри PLANETCALC.

Калькулятор ниже генерирует код для парсера на основе грамматики в формате РБНФ. В качестве примера взята классическая грамматика для распознавания математических выражений.

Результат можно использовать для создания парсера, при помощи библиотеки PCP, доступной на этом сайте.
Пример кода:

var parser = new PCP.parser
( [/* сгенерированный код вставлять сюда */] );
//формирует дерево разбора
var tree = parser.parse( text ); 
//обход результата
tree.visit( {
/* функции для обхода  нетерминалов nt1 и nt2 
    ( названия нетерминалов nt1 и nt2 выбраны 
для примера, предполагается, 
что они описаны в исходной грамматике);*/
   "nt1": function ( v ) {
        // для получения значения: v.getValue()
    }
   ,"nt2": function ( v ) {
        // для обхода дочерних значений: 
       // v.visit( childvisitor );
    }
});

Немного информации про РБНФ и другие детали по теории компиляторов, а также детальная информация по применению данного инструмента находится сразу же за калькулятором.

PLANETCALC, Компилятор LL(1) парсера

Компилятор LL(1) парсера

Расширенная БНФ грамматика в соответствии с форматом ISO/IEC 14977 : 1996(E)
Наименования правил, которые требуется удалить, разделенные запятыми.
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Код парсера PLANETCALC
 
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Результат разбора выражения
 

Расширенная форма Бекуса Наура (РБНФ)

По сравнению с обычной БНФ записью, РБНФ обладает рядом достоинств:

  • Правило РБНФ не ограничено одной строкой, правило может занимать несколько строк. Конец правила отмечается специальным символом - ; ( точка с запятой)

    terminal character
    = letter
    | decimal digit
    | concatenate symbol
    | defining symbol
    | definition separator symbol
    | end comment symbol
    | end group symbol
    | end option symbol
    | end repeat symbol
    | except symbol
    | first quote symbol
    | repetition symbol
    | second quote symbol
    | special sequence symbol
    | start comment symbol
    | start group symbol
    | start option symbol
    | start repeat symbol
    | terminator symbol
    | other character;

  • Нет необходимости отделять треугольными скобками < > названия нетерминальных символов (но все терминалы при этом должны быть заключены в одинарные или двойные кавычки).

    decimal digit = ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’| ’8’ | ’9’;

  • В РБНФ есть специальный синтаксис для замыканий - выражение заключенное в фигурные скобки, задает ноль или более повторений этого выражения:

    syntax= syntax rule, {syntax rule};

  • При помощи знака минус задаются исключения из предыдущего выражения, например следующее правило задает любой символ, кроме кавычек:

first terminal character= terminal character - first quote symbol;

Полное описание формата РБНФ, а также грамматику описывающую РБНФ в можно найти в стандарте ISO/IEC 14977 (заметим, что грамматика в приложении к этому стандарту не является LL1, что было выяснено опытным путем при написании данного калькулятора).

Улучшения РБНФ

Калькулятор реализует ряд улучшений стандартного синтаксиса РБНФ: В качестве специальной последовательности можно использовать регулярное выражение или 16-ричный код ASCII символа. Например, для переноса строки можно использовать следующее правило, основанное на кодах символов в шестнадцатиричном виде:

lineend= ?0xd?,?0xa?;

или можно использовать регулярные выражения, например, для непечатных символов - разделителей:

sp=?/\s+/?;

Анализ грамматики

Калькулятор определяет ряд ошибок и несоответствий грамматики:

  • Синтаксические ошибки грамматики
  • Отсутствие корневого правила
  • Наличие единственного корневого правила
  • Левую рекурсию
  • Возможность разбора без возвратов

Многошаговый лексический и синтаксический анализ

В классической теории компиляторов процесс разбора складывается из лексического и синтаксического анализа. На шаге лексического анализа из входного потока выделяются токены, и удаляется все лишнее, например пробелы и комментарии. Лексический анализ обычно выполняется набором правил на основе регулярных выражений. Данный калькулятор несколько отходит от классического подхода - лексический и синтаксический анализ делаются с применением той же самой грамматики. Если применять такой подход в лоб, то грамматика для разбора конечного выражения окажется переусложненной и будет довольно сложно с ней управляться. Чтобы этого не произошло грамматика разбивается на несколько шагов ( в простейшем случае 2 шага ), на первом шаге выделяются все лексемы и удаляются ненужные, затем на очищенном потоке токенов производится окончательный разбор. Для примера добавим возможность присутствия пробелов в любом месте математического выражения:

Пример двухшаговой грамматики с удалением пробелов

Список литературы:

Ссылка скопирована в буфер обмена
PLANETCALC, Анализ грамматики, записанной при помощи РБНФ. И еще один компилятор компиляторов.

Комментарии