Модуль python lrparsing; не может разобрать простую рекурсивную грамматику

Question

expr = Ref('expr') 
block = '{' + Repeat(expr) + '}' 
expr = block | Token(re='[0-9]') 
START = expr 

Вот грамматика с использованием модуля lrparsing для Python. Модуль не сообщает о конфликтах в грамматике.

Он не может разобрать строку {{0}} с ошибкой lrparsing.ParseError: line 1 column 5: Got '}' when expecting __end_of_input__ while trying to match block in state 11

Стадию стек состояние шагом является:

shift '{'; ItemSet:5='{' 
shift '{'; ItemSet:5='{' ItemSet:5='{' 
shift /[0-9]/; ItemSet:4=/[0-9]/ ItemSet:5='{' ItemSet:5='{' 
reduce '}'; ItemSet:4=/[0-9]/ -- ItemSet:7=expr ItemSet:5='{' ItemSet:5='{' 
reduce '}'; ItemSet:7=expr -- ItemSet:9=expr ItemSet:5='{' ItemSet:5='{' 
shift '}'; ItemSet:11='}' ItemSet:9=expr ItemSet:5='{' ItemSet:5='{' 

Что AFAIK означает, что он смещается {{0, то при виде } снижения 0 к expr , затем уменьшив на }снова, не переложив его первым, что сбивает меня с меня.

Является ли это ошибкой, или я делаю что-то бесконечно просто и глупо?

Если это моя грамматика, как бы я реорганизовал ее, чтобы удовлетворить мои вечно пышные и страстные желания? Если это ошибка, может ли кто-нибудь направить меня к модулю python, у которого есть синтаксис , наиболее похожий на lrparsing, что делает работы?

EDIT: Рефакторинг как:

blocks = Ref('blocks') 
block = Ref('block') 
expr = Ref('expr') 
blocks = blocks + block | THIS*0 # THIS*0 is the idiomatic way of getting the empty string 
block = '{' + expr + '}' 
expr = blocks | Token(re='[0-9]') 
START = expr 

Позволяет для правильного разбора. Теперь вопрос для меня ... почему? Я чувствую, что lrparsing раньше жаловался на какие-либо проблемы синтаксического анализа ... Repeat просто не работает так, как я ожидаю?

Answer 1

lrparsing имеет ошибку; он не учитывает рекурсивные повторы правильно.

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

block = Ref('block') 
block = '{' + block + '}' | Token(re='[0-9]') 
START = block 

Заметим также, что исходная грамматика позволила бы ввод, например {{0{1}}}. (Причина в том, что повторяемая часть может быть расширена до простых чисел или expr.) Учитывая вашу вторую грамматику, вы, вероятно, этого не хотели.

Я сделал некоторые работы с pyparsing, но синтаксис значительно отличается. Аналогичный пример:

from pyparsing import Forward, Literal, nums, oneOf, Word 

l = lambda c: Literal(c).suppress() 
block = Forward() 
block << (Word(nums, exact=1)^l('{') + block + l('}')) 
print(block.parseString("{{0}}")) 

Выход:

['0'] 

Надежда, что помогает.

Answer 2

Я сообщил о вашей проблеме автору lrparsing, когда я наткнулся на эту страницу - это действительно была ошибка, и она была исправлена ​​в версии 1.0.8. В случае, если это полезно в будущем, lrparsing bug tracker можно найти here.

Answer 3

Lrparsing автор здесь. Как сказал Серж, это была ошибка, и она исправлена ​​в 1.0.8. Это произошло только потому, что Серж сообщил об этом на Source Forge, но трекер, иначе я бы не знал. Спасибо, Серж.

Замечания об этом, возможно, являются ошибкой в ​​Repeat() намекают на то, что вы не понимаете, что делает lrparsing. Лрпарсинг - довольно сложный зверь. Он позволяет вводить грамматику таким образом, я надеюсь, что это естественно для программиста на Python. Затем он компилирует во что-то, что может понять генератор парсеров LR (1), который представляет собой серию постановок. Затем он генерирует таблицу разбора LR (1) из этих производств. И, наконец, он подает ваш язык ввода и таблицу синтаксического анализа в парсер LR (1) для генерации дерева синтаксического анализа. Для чего это стоит, ошибка была в той части, которая генерирует таблицу синтаксического анализа.

Отладка такой серии преобразований была бы почти невозможной для меня, если бы я не мог видеть, что производит каждый шаг. Соответственно, lrparsing имеет функцию repr_xxxx(), которая отображает выходные данные каждого шага. Первое преобразование - разбор вашей грамматики. Результат отображается repr_grammar():

<G> = START + __end_of_input__ 
START = expr 
block = '{' + expr *() + '}' 
expr = block | /[0-9]/ 

который выглядит очень похож на оригинальные грамматики, представленных в этом вопросе. Следующим шагом является компиляция этих правил в продуктах, что может понять генератор парсеров LR (1). Они печатаются repr_productions():

<G> = START __end_of_input__ 
START = expr 
block = '{' '}' 
block = '{' block.Sequence.Repeat '}' 
block.Sequence.Repeat = expr 
block.Sequence.Repeat = block.Sequence.Repeat expr 
expr = block 
expr = /[0-9]/ 

block.Sequence.Repeat новый нетерминал lrparsing введена для того, чтобы справиться с Repeat(). Эти постановки выглядят как верное представление оригинальной грамматики для меня.

Lrparsing выходит из своего способа скрыть нетерминалы, которые он вводит как block.Sequence.Repeat. Например, они не будут отображаться в дереве синтаксиса вывода. Это означает, что пользователю не требуется заботиться о них, за исключением двух случаев. Эти 2 случая - это восстановление ошибок и попытка понять выход из журнала синтаксического анализатора. Первая сложная техника больше всего не будет пытаться. Но некоторые здесь смотрели на последнего, чтобы попытаться понять, что делает lrparsing. Журнал не будет иметь большого смысла, если вы не увидите файлы, которые пытается распознать парсер LR (1). Но если бы вы их видели, вы бы знали, что в Repeat() не было ошибок.

Вы также можете сбросить сгенерированную таблицу анализа LR (1). Если вы действительно хотите понять, как работает парсер LR (1), вот что вы должны пытаться опрокинуть. Если вам не удастся разобрать очень интересную тему, я не рекомендую ее.