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

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 оценивает себя как левый expr и работает так всегда. Есть идеи, как решить проблему? По возможности без необходимости добавлять разделители, такие как скобки.

Answer 1

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

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

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

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