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

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

Результат можно использовать для создания парсера, при помощи библиотеки 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 );
    }
});

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

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

expr=term, expr1; expr1="+",term,expr1|"-",term,expr1|; term=factor, term1; term1="*", factor, term1 | "/", factor, term1|; factor="(", expr , ")" | number; number=digit , {digit}; digit = "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|"0"; syntax=expr;

Грамматика в формате EBNF

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

(1+2)/3*(4+5)

Выражение

Удалять правила

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

Показать FIRST/FOLLOW наборы

Показать дерево разбора

Рассчитать

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

Код парсера 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 шага ), на первом шаге выделяются все лексемы и удаляются ненужные, затем на очищенном потоке токенов производится окончательный разбор. Для примера добавим возможность присутствия пробелов в любом месте математического выражения:

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

• Стандарт ISO/IEC 14977
• Engineering A Compiler by Keith D. Cooper & Linda Torczon
• Crafting a Compiler by Charles N. Fischer, Ron K. Cytron, Richard J. LeBlanc Jr.
• Compilers, Principles, Techniques, Tools (Dragon book) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ulman