Вложенные выражения вызывают переполнение стека

Question

Я столкнулся с проблемой, которую вы, ребята, возможно, поможете мне решить.

Я пытаюсь разобрать грамматику, которая содержит это:

Expr:  BinOp | Name | Constant ;
Name: id=ID ;
Constant: value=INT ;
BinOp: left=expr op=operator right=expr ;
Operator: Add | Sub ;
Add: 'plus' ;
Sub: 'minus' ;

Но это вызывает переполнение стека, потому что я предполагаю, что BinOp оценивает себя как левое выражение, и так будет всегда. Есть идеи, как решить проблему? Если возможно, без необходимости добавлять разделители, например круглые скобки.

Answer 1

Text X использует синтаксический анализ рекурсивного спуска с возвратом (реализованный Arpeggio), то есть это нисходящий подход, который по умолчанию не поддерживает леворекурсивные правила, потому что для соответствия некоторымA Правило сначала должно соответствовать A приводя к бесконечной рекурсии.

Чтобы реализовать языки, подобные выражениям, вам необходимо удалить все прямо или косвенно леворекурсивные правила. Для этого есть механический подход. Это описание удаления левой рекурсии работает для арпеджио и, следовательно, для textX.

Вы также можете увидеть пример расчета в арпеджио. Хотя синтаксис в арпеджио отличается, арпеджио является основным движком textX, поэтому все, что там написано, работает для textX.

Также обратите внимание, что в преобразованной грамматике приоритет оператора закодирован в правилах грамматики: операторы с более низким приоритетом соответствуют раньше, а операторы с более высоким приоритетом - позже.