Правильная рекурсивная грамматика или левая рекурсивная?
Я почти ничего не знаю о том, что собираюсь спросить, поэтому я хотел бы получить предложение, основанное на уровне навыков, необходимых для реализации синтаксического анализатора для данной грамматики (поскольку я новичок в этом формальном подходе к парсеры и языки).
Прошло всего несколько лет, и эта ситуация немного напоминает мне грамматику Паскаля по сравнению с грамматикой Си / Си ++, это левые и правые вещи.
Но я не собираюсь этого делать, моя цель — реализовать простой синтаксический анализатор для языка разметки для таких документов, как Markdown.
Поэтому, учитывая, что я начинаю с языка разметки, я хочу сохранить простоту, которая является самой простой для обработки между этими двумя вариантами и почему. Другой вид грамматики может быть проще для меня? Если да, какой из них вы предлагаете?
Решение
Правая рекурсивная и левая рекурсивная в основном сводятся к тому, как вы собираетесь реализовать парсер.
Если вы собираетесь выполнять синтаксический анализатор сверху вниз (например, с рекурсивным спуском), вы обычно хотите использовать правильную рекурсию в грамматике (и для чистого рекурсивного спуска это единственный вариант).
Если вы собираетесь использовать анализатор снизу вверх, вы обычно хотите использовать левую рекурсию. Анализаторы снизу вверх обычно генерируются с помощью генератора синтаксических анализаторов, таких как Yacc или Bison, большинство из которых Можно обрабатывать правую рекурсию, если необходимо, но может обрабатывать левую рекурсию несколько эффективнее.
Другие решения
Это зависит от того, какой тип парсера вы используете. Если вы используете тип LL, вы должны использовать правильную рекурсию.
Если вы используете тип LR, вы можете использовать левую или правую рекурсию. Однако левая рекурсия минимизирует глубину стека.
Ну, есть два основных типа грамматик:
LL(k) = Left to tight, leftmost derivation, k symbols look ahead
LR(k) = Left to right, rightmost derivation, k symbols look ahead
Парсеры LR гораздо сложнее писать вручную, однако они более мощные, чем парсеры LL. Если вы смотрите на некоторые популярные инструменты генератора парсеров:
ANTLR : a LL parser
BISON: a LALR(1) parser (a type of LR parser but a bit less powerful)
CUP: a LALR(1) parser (outputs Java / C# code)