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

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

0 голосов
/ 15 октября 2018

Я пишу парсер для существующего языка, используя библиотеку 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 ;

Ответы [ 2 ]

0 голосов
/ 15 октября 2018

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

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

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

0 голосов
/ 15 октября 2018

Обычно это записывается как: 

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

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

...