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

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

Este contenido se encuentra disponible en Русский

Aquí puede editar una traducción de Русский a Español

Este contenido se encuentra disponible en English

Aquí puede editar una traducción de English a Español

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

Результат можно использовать для создания парсера, при помощи библиотеки 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
 
Наборы символов для LL(1) разбора
Результат разбора выражения
 
Guarde el cálculo para reutilizarlo la próxima vez, para extension incrustarlo en su sitio web o share compartirlo con amigos.

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

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

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

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

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

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

Comentarios