Преодоление бесконечной левой рекурсии в синтаксическом анализаторе TextX

Question

Я пишу парсер для существующего языка, используя библиотеку Python TextX (на основе парсера Arpeggio PEG)

Но когда я пытаюсь использовать его для анализа файла, я получаю исключение:

RecursionError: maximum recursion depth exceeded while calling a Python object

Вот минимальный пример, который вызывает это исключение:

#!/usr/bin/env python
from textx import metamodel_from_str

meta_model_string = "Expr: ( Expr '+' Expr ) | INT ;"
model_string      = "1 + 1"

mm = metamodel_from_str(meta_model_string, debug=True)
m = mm.model_from_str(model_string, debug=True)

Я проследил это до левой проблемы рекурсии Арпеджио, где говорится, что правило A := A B не поддерживается и должен быть преобразован в правило, где такой рекурсии нет.

Итак, мой вопрос: можно ли переписать Expr := Expr '+' Expr Правило выше таким образом, чтобы не использовать левую рекурсию? Обратите внимание, что реальный Expr Правило намного сложнее. Немного менее упрощенная версия этого будет:

Expr: '(' Expr ')' | Expr '+' Expr | Expr '*' Expr' | '!' Expr | INT | STRING ;

Answer 1

Автор textX здесь. В дополнение к превосходному ответу Павла, есть пример выражения, который должен дать вам хорошее начало.

Нисходящие парсеры вообще не обрабатывают леворекурсивные правила без таких хаков. Если ваш язык будет сложным и в значительной степени ориентированным на выражения, возможно, лучше попробовать какой-нибудь анализатор снизу вверх, который допускает левую рекурсию и обеспечивает декларативный приоритет и спецификацию ассоциативности. Если вам понравился textX, то я предлагаю взглянуть на parglare, который имеет схожие цели дизайна, но использует технику синтаксического анализа снизу вверх (в частности, LR и GLR). Пример быстрого введения - это точный язык, который вы строите.

В этом посте я написал в блоге об обосновании начала проекта parglare и различиях с textX/Arpeggio.

Answer 2

Это обычно пишется как:

multop: '*' | '/'
addop: '+' | '-'
Factor: INT | STRING | '(' Expr ')' ;
Term: Factor [multop Factor]... ;
Expr: Term [addop Term]... ;

Сейчас Expr не будет непосредственно возвращаться к себе до тех пор, пока не найдет первое совпадение с ведущим '('. Вы также получите группы, соответствующие приоритету операций. (Обратите внимание, что повторение для Expr а также Term в конечном итоге будет производить такие группы, как ['1', '+', '1', '+', '1']когда вы могли ожидать [['1', '+', '1'], '+', '1'] что даст вам леворекурсивный парсер.)