homechevron_rightУчебаchevron_rightИнформатика

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

Калькулятор позволяет оценить корректность 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) парсера

Расширенная БНФ грамматика в соответствии с форматом ISO/IEC 14977 : 1996(E)

Наименования правил, которые требуется удалить, разделенные запятыми.

Анализ грамматики
Код парсера PLANETCALC
 
Наборы символов для LL(1) разбора
Результат разбора выражения
 

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

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

  • Правило РБНФ не ограничено одной строкой, правило может занимать несколько строк. Конец правила отмечается специальным символом - ; ( точка с запятой)
    >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 шага ), на первом шаге выделяются все лексемы и удаляются ненужные, затем на очищенном потоке токенов производится окончательный разбор. Для примера добавим возможность присутствия пробелов в любом месте математического выражения:
expr=term, expr1;
expr1=plus,term,expr1|minus,term,expr1|;
term=factor, term1;
term1=mul, factor, term1 | div, factor, term1|;
factor=lb, expr , rb | number;
lb="(";
rb=")";
mul="*";
div="/";
plus="+";
minus="-";
space=?/\s/?;
number=digit , {digit};
digit = "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|"0";
lexer={ space|digit|rb|lb|div|mul|plus|minus };
syntax=expr;
1 + 2 / (12 - 3)space


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

Комментарии