1

我正在尝试解析正数和负数小数。

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

包含前两个规则会产生移位/减少冲突，但我不知道如何编写语法以使冲突永远不会发生。我正在使用柠檬解析器。

编辑：来自 .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.
4

2 回答 2

3

您显示的冲突表明number非终端的使用方式存在问题，而不是其number本身。

基本问题是，在看到 a pnumberor之后nnumber，当前瞻的下一个标记是 aDOT时，它无法确定是否应该是number（减少，因此是之后的DOT其他非终结符的一部分）的结尾，或者是否应该被视为的一部分（转移，以便以后可以减少 p/nnumber DOT pnumber 规则之一。）numberDOTnumber

因此，为了诊断问题，您需要显示在右侧任何位置使用的所有规则number（以及在右侧递归地使用任何这些规则的非终结符的任何其他规则）。

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

所以这里的问题是你需要两个标记的前瞻来区分 a DOTin a (real)number literal和 aDOT末尾的 a rule。

简单的解决方法是让词法分析器处理它——词法分析器可以很容易地做少量的前瞻，所以你可以识别REAL_NUMBER为一个不同的非终端NUMBER（可能仍然没有-，所以你最终会得到

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

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

一般来说，要重构语法以消除前瞻冲突，您需要找出表现冲突的规则（rule和number此处）并重构事物以将它们组合成具有共同前缀的规则，直到您能够消除歧义。

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

variable ::= number | name

我们希望将number语法中的规则“向上”移动，使其rule与 with相同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 CONJUNCTION number
body_n ::= bodydef_n
body_n ::= body CONJUNCTION bodydef_n

请注意，当您向上移动时，您需要拆分越来越多的规则，因此这个过程可能会严重破坏语法。但是，仅在您正在重构的 rhs 末尾使用的规则最终将只需要该_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

并且 shift-reduce 冲突消失了，因为规则具有公共前缀，直到超过所需的前瞻来确定使用哪个。我通过添加减少了最终扩展中的规则数量

integer ::= pnumber | nnumber
于 2016-08-17T00:43:09.627 回答
0

您必须使用 or 声明操作符标记的关联DOT性。%left%right

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

number : number DOT NUMBER

一个数字后跟DOT一个NUMBER令牌仍然是一个数字。

该规则不需要DOT声明关联性，因为没有歧义；该规则是纯左递归的，右手DOT是一个终结符。解析器必须将栈顶减少到number状态机在这一点时，然后移位DOT：

number : number DOT NUMBER

您在这里解析的语言是常规的；它可以被正则表达式解析而无需任何递归。这就是为什么同时具有左右递归并需要声明关联性的规则有点像“大锤子”。

于 2016-08-19T00:29:55.673 回答