Получить код ссылки
Внешний вид
Пример
УчебаИнформатика

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

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

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

Результат можно использовать для создания парсера, при помощи библиотеки 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) парсераCreative Commons Attribution/Share-Alike License 3.0 (Unported)
Анализ грамматики:
Код парсера 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 шага ), на первом шаге выделяются все лексемы и удаляются ненужные, затем на очищенном потоке токенов производится окончательный разбор. Для примера добавим возможность присутствия пробелов в любом месте математического выражения:

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

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

  • Стандарт 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

Комментарии

Пока нет комментариев

 Все обсуждения Отправь комментарий - будь первым!
Защита от спама