Как преодолеть сдвиг-уменьшить конфликт в грамматике LALR

Question

Я пытаюсь разобрать положительные и отрицательные десятичные дроби.

number(N) ::= pnumber(N1).

number(N) ::= nnumber(N1).

number(N) ::= pnumber(N1) DOT pnumber(N2).

number(N) ::= nnumber(N1) DOT pnumber(N2).

pnumber(N) ::= NUMBER(N1).

nnumber(N) ::= MINUS NUMBER(N1).

Включение первых двух правил дает конфликт сдвиг / уменьшение, но я не знаю, как я могу написать грамматику так, чтобы конфликт никогда не возникал. Я использую анализатор Lemon.

Редактировать: конфликты из.out файла

State 79:
     (56) number ::= nnumber *
          number ::= nnumber * DOT pnumber

                           DOT shift        39
                           DOT reduce       56      ** Parsing conflict **
                     {default} reduce       56     number ::= nnumber

State 80:
     (55) number ::= pnumber *
          number ::= pnumber * DOT pnumber

                           DOT shift        40
                           DOT reduce       55      ** Parsing conflict **
                     {default} reduce       55     number ::= pnumber
State 39:
          number ::= nnumber DOT * pnumber
          pnumber ::= * NUMBER

                        NUMBER shift-reduce 59     pnumber ::= NUMBER
                       pnumber shift-reduce 58     number ::= nnumber DOT pnumber

State 40:
          number ::= pnumber DOT * pnumber
          pnumber ::= * NUMBER

                        NUMBER shift-reduce 59     pnumber ::= NUMBER
                       pnumber shift-reduce 57     number ::= pnumber DOT pnumber

Редактировать 2: Минимальная грамматика, которая вызывает проблемы

start ::= prog.
prog ::= rule.
rule ::= REVERSE_IMPLICATION body DOT.
body ::= bodydef.
body ::= body CONJUNCTION bodydef.
bodydef ::= literal.
literal ::= variable.
variable ::= number.
number ::= pnumber.
number ::= nnumber.
number ::= pnumber DOT pnumber.
number ::= nnumber DOT pnumber.
pnumber ::= NUMBER.
nnumber ::= MINUS NUMBER.

Answer 1

Конфликты, которые вы показываете, указывают на проблему с тем, как number нетерминал используется, а не с number сам.

Основная проблема заключается в том, что после просмотра pnumber или же nnumber, когда следующий жетон Lookahead является DOTне может решить, должен ли это быть конец number (уменьшить, так DOT является частью некоторого другого нетерминала после number) или, если DOT следует рассматривать как часть number (сдвинуто, чтобы впоследствии можно было уменьшить одно из правил pnnumber DOT pnumber.)

Таким образом, чтобы диагностировать проблему, вам нужно показать все правила, которые используют number в любом месте справа (и рекурсивно любые другие правила, использующие нетерминалы любого из этих правил справа).

Обратите внимание, что редко полезно публиковать только фрагмент грамматики, так как процесс построения LR-синтаксического анализатора сильно зависит от контекста, где правила используются в других местах грамматики...

---

Таким образом, проблема здесь в том, что вам нужно заглянуть в два токена, чтобы различать DOT в (реальном) numberliteral и DOT в конце rule,

Простое решение состоит в том, чтобы позволить лексеру справиться с этим - лексеры могут довольно легко выполнять небольшое количество задач, чтобы вы могли распознать REAL_NUMBER как отдельный нетерминал от NUMBER (вероятно, до сих пор без -так что вы бы в конечном итоге

number ::= NUMBER | MINUS NUMBER | REAL_NUMBER | MINUS REAL_NUMBER

удалить конфликт намного сложнее, используя грамматику, но это можно сделать.

---

В общем, чтобы реорганизовать грамматику для устранения конфликта, необходимо выяснить правила, которые проявляют конфликт (rule а также number здесь) и рефакторинг вещей, чтобы объединить их в правила, которые имеют общие префиксы, пока вы не получите достаточно далеко, чтобы устранить неоднозначность.

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

variable ::= number | name

Мы хотим переместить number правило "вверх" в грамматике, чтобы получить его в том же месте, что и rule с DOT, Таким образом, мы должны разделить содержащиеся правила на особый случай, когда они заканчиваются number, Мы добавляем суффикс для обозначения правил, которые соответствуют исходному правилу со всеми версиями, которые заканчиваются на number откалываться

variable ::= number | variable_n
variable_n ::= name

... и прогрессировать это "вверх"

literal ::= number | literal_n
literal_n ::= variable_n

... и Агин

bodydef ::= number | bodydef_n
bodydef_n := literal_n

...и опять

body ::= number | body_n
body := body CONUNCTION number
body_n ::= bodydef_n
body_n ::= body CONJUNCTION bodydef_n

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

...последний шаг

rule ::= REVERSE_IMPLICATION body_n DOT
rule ::= REVERSE_IMPLICATION number DOT
rule ::= REVERSE_IMPLICATION body CONJUNCTION number DOT

Теперь у вас есть точки во всех одинаковых местах, так что number правила:

rule ::= REVERSE_IMPLICATION body_n DOT
rule ::= REVERSE_IMPLICATION integer DOT
rule ::= REVERSE_IMPLICATION integer DOT pnumber DOT
rule ::= REVERSE_IMPLICATION body CONJUNCTION integer DOT
rule ::= REVERSE_IMPLICATION body CONJUNCTION integer DOT pnumber DOT

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

integer ::= pnumber | nnumber

Answer 2

Вы должны объявить ассоциативность DOT токен оператора с %left или же %right,

Или другая идея - отказаться от этого промежуточного сокращения. Очевидная особенность вашей грамматики в том, что числа растут на DOT с последующим номером. Это может быть зафиксировано с помощью одного правила:

number : number DOT NUMBER

Номер, за которым следует DOT с последующим NUMBER токен все еще число.

Это правило не требует DOT объявить ассоциативность, потому что нет двусмысленности; правило чисто леворекурсивное, а правая рука DOT это терминальный токен Парсер должен уменьшить вершину стека до number когда конечный автомат находится в этой точке, а затем смена DOT:

number : number DOT NUMBER

Язык, который вы здесь анализируете, является регулярным; это может быть проанализировано регулярными выражениями без какой-либо рекурсии. Вот почему правила, в которых есть как левая, так и правая рекурсия и которые требуют декларирования ассоциативности, являются чем-то вроде "большого молотка".