如何克服 LALR 文法中的 shift-reduce 冲突

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).

包含前两条规则会产生 shift/reduce 冲突，但我不知道如何编写语法才能使冲突永远不会发生。我正在使用 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 的一部分（移动以便以后可以减少 p/nnumber DOT pnumber 规则之一。）

因此，为了诊断问题，您需要在右侧的任何位置显示所有使用 number 的规则（并递归地显示使用任何这些规则的非-右边的终端）。

请注意，post 只是一个语法片段很少有用，因为 LR 解析器构建过程在很大程度上取决于语法中其他地方使用规则的上下文...

所以这里的问题是你需要两个标记前瞻来区分（真实的）number literal 中的 DOT 和rule.

结束

简单的解决方法是让词法分析器处理它——词法分析器可以很容易地进行少量的前瞻，因此您可以将 REAL_NUMBER 识别为不同于 NUMBER 的非终结符（可能仍然没有 -，所以你最终会得到

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

通过分解语法来消除冲突要困难得多，但可以做到。

一般来说，要重构语法以消除先行冲突，您需要弄清楚表明冲突的规则（此处为 rule 和 number）并重构事物以将它们组合在一起进入具有共同前缀的规则，直到你走得足够远以消除歧义。

首先，我假设除了 number 之外还有其他规则可以出现在这里，否则我们可以消除所有中间规则。

variable ::= number | name

我们想在语法中移动 number 规则 "up"，使其与 rule 和 DOT 放在同一个位置。所以我们需要将包含规则拆分为特殊情况，当它们以 number 结尾时。我们添加一个后缀来表示与原始规则相对应的规则，所有版本都以 number split off

结尾

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

...并传播 "up"

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

...又一次

bodydef ::= number | bodydef_n
bodydef_n := literal_n

...又一次

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

请注意，当你向上移动时，你需要拆分越来越多的规则，所以这个过程可能会大大破坏语法。但是，在重构的 rhs 末尾使用 only 的规则将最终只需要 _n 版本，因此您不必加倍规则数。

...最后一步

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

现在你在所有相同的地方都有 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

并且 shift-reduce 冲突消失了，因为规则有共同的前缀，直到通过所需的前瞻来确定使用哪个。我通过添加

减少了最终扩展中的规则数量

integer ::= pnumber | nnumber

Answer 2

您必须声明 DOT 运算符标记与 %left 或 %right 的关联性。

或者，另一个想法是放弃这个中间减少。您的语法中的明显特征是数字按 DOT 后跟数字增长。可以用一条规则捕获：

number : number DOT NUMBER

数字后跟 DOT 后跟 NUMBER 标记仍然是数字。

此规则不要求 DOT 声明关联性，因为没有歧义；该规则纯粹是左递归的， DOT 的右手是一个终端标记。解析器必须在状态机此时将栈顶缩减到number，然后shift DOT:

number : number DOT NUMBER

您在这里解析的语言是正规的；它可以通过正则表达式解析而无需任何递归。这就是为什么同时具有左递归和右递归并且需要声明关联性的规则有点像 "big hammer".

如何克服 LALR 文法中的 shift-reduce 冲突

How to overcome shift-reduce conflict in LALR grammar

parsing

yacc

shift-reduce-conflict

shift-reduce

lemon