Существуют ли основанные на PEG генераторы парсеров, которые поддерживают левую рекурсию?
Левая рекурсия, кажется, является большой проблемой для многих генераторов синтаксического анализатора, которые построены на основе анализа рекурсивного спуска. Я ищу генератор синтаксических анализаторов на основе PEG- на любом языке.
2 ответа
Есть статья по этой теме: http://tratt.net/laurie/research/publications/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf
Автор описывает несколько подходов к обработке леворекурсивных правил при разборе PEG/Packrat.
Мой генератор синтаксических анализаторов AustenX (scratchy.nz/austen.php) поддерживает левую рекурсию (включая косвенную), где важен порядок опций (хотя я никогда не удосужился написать, как это работает). Это парсер Packrat в глубине души, но запоминание можно отбросить, и это не имеет значения.