Бесконечная рекурсия, вызванная многократным появлением элемента синтаксического анализа YACC-PLY

Question

Я имею дело с Yacc (сгибом), и я не знаю, как сделать больше вхождений элемента разбора, не вызывая сбой программы из-за бесконечной рекурсии. Допустим, у меня есть:

def p_Attribute(p):
    ''' Attribute : STRING
                  | NUMBER 
                  | Attribute
                  | empty '''
[do stuff] 

ПРИМЕЧАНИЕ: Вопрос похож на: Python PLY ноль или более вхождений элемента разбора, но предложенное решение там не работает, у меня всегда бесконечная рекурсия.

Answer 1

Проблема здесь на самом деле в вашей грамматике. Парсеры, подобные Yacc, не работают с этим типом правила, так как оно требует уменьшения атрибута, чтобы уменьшить атрибут, а следовательно, бесконечную рекурсию. (Изменить, чтобы добавить примечание: было бы хорошо, если правая рука Attribute имел какой-то непустой не двусмысленный токен, например, Attribute : STRING | NUMBER | '$' Attribute | empty разбирается и позволяет любое количество $ знаки перед другим приемлемым Attributes. Но как есть, обе альтернативы, Attribute а также empty, может быть полностью пустым. Это конфликт уменьшения / уменьшения, и он плохо разрешается здесь. Я думаю, что конфликт уменьшения / уменьшения может разрешиться "по желанию", если вы сначала поставите пустое правило, но в целом это все же "неправильный способ" сделать это.)

Предположительно, вы хотите одну из трех вещей (но я не уверен, что именно, так что представьте себе путаницу генератора синтаксического анализатора:-)):

• ноль или более атрибутов в последовательности (эквивалентных регулярному выражению "x*")
• один или несколько атрибутов в последовательности (эквивалентных регулярному выражению "x+")
• ноль или один Атрибут, но не более (эквивалентный регулярному выражению "x?")

Для всех трех из них вы должны, как правило, начинать с определения одного нетерминала, который распознает только один действительный атрибут типа вещи, например:

Exactly_One_Attribute : STRING | NUMBER

(который я собираюсь просто по буквам Attribute ниже).

Затем вы определяете правило, которое принимает то, что вы намерены разрешить для вашей последовательности (или необязательный атрибут). Например:

Zero_Or_More_Attributes : Zero_Or_More_Attributes Attribute | empty

(При этом используется "левая рекурсия", которая должна быть наиболее эффективной. Используйте правую рекурсию, см. Ниже, только если вы действительно хотите распознавать элементы в другом порядке.)

Требовать хотя бы один атрибут:

One_Or_More_Attributes: One_Or_More_Attributes Attribute | Attribute

(в этом примере также леворекурсивный) или:

Attribute_opt : empty | Attribute

который допускает либо "ничего" (пусто), либо ровно один атрибут.

---

Право-рекурсивная версия просто:

Zero_Or_More_Attributes : Attribute Zero_Or_More_Attributes | empty

Как правило, при использовании правильной рекурсии синтаксический анализатор вынужден "сдвигать" (выдвигать на свой стек анализа) больше токенов. В конечном итоге парсер встречает токен, который не соответствует правилу (в данном случае что-то не STRING или же NUMBER) и затем он может начать сокращать каждый сдвинутый токен, используя правильно-рекурсивное правило, работая над STRING-а также-NUMBERсправа налево. Используя левую рекурсию, он делает сокращения раньше, работая слева направо. См. http://www.gnu.org/software/bison/manual/html_node/Algorithm.html для получения дополнительной информации.