解析 – 如何解决三元表达式(a？b：c)和“可能”表达式(a？)之间的LR(1)语法歧义？

概述我创建了一个语法,其精简版本如下： (0) exp1: ternary;(1) exp1: exp2;(2) ternary: exp2 "?" exp1 ":" exp1;(3) exp2: exp2 "+" exp3;(4) exp2: exp3;(5) exp3: maybe;(6) exp3: "1";(7) maybe: exp3 "?"; 我相信这种语言是明确的,应该是L 我创建了一个语法,其精简版本如下：

(0) exp1: ternary;(1) exp1: exp2;(2) ternary: exp2 "?" exp1 ":" exp1;(3) exp2: exp2 "+" exp3;(4) exp2: exp3;(5) exp3: maybe;(6) exp3: "1";(7) maybe: exp3 "?";

我相信这种语言是明确的,应该是LR可解析的. (如果我错了,请告诉我！)

但是,当我尝试为这个语法生成一个LR(1)解析器时,我得到了shift / reduce冲突,因为当解析器看到带有lookahead的exp3时,它不知道是要移位还是减少：

Conflicts in state 3:    Reduction using rule 4: exp2:  exp3 · | "?"    Shift to state 6Conflicts in state 9:    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"    Shift to state 6Conflicts in state 13:    Reduction using rule 4: exp2:  exp3 · | "?"    Shift to state 16Conflicts in state 20:    Reduction using rule 4: exp2:  exp3 · | "?"    Shift to state 23Conflicts in state 25:    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"    Shift to state 23Conflicts in state 28:    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"    Shift to state 16

有没有合理的方法让我使这种语言LR(1) – 可分解(没有冲突)？

或者glr(或LR(2)？)是我这样的语言的唯一现实选择？
(或者我甚至错误地认为语言首先是明确的？)

作为参考,我生成的模糊状态机如下(其中♦是EOF)：

State 0:    exp1:  · ternary | {♦} → shift 1    ternary:  · exp2 "?" exp1 ":" exp1 | {♦} → shift 2    exp2:  · exp2 "+" exp3 | {"?","+"} → shift 2    exp2:  · exp3 | {"?","+"} → shift 3    exp3:  · maybe | {"?","+"} → shift 4    exp3:  · "1" | {"?","+"} → shift 5    maybe:  · exp3 "?" | {"?","+"} → shift 3State 1:    exp1:  ternary · | {♦} → reduce 0State 2:    ternary:  exp2 · "?" exp1 ":" exp1 | {♦} → shift 7    exp2:  exp2 · "+" exp3 | {"?","+"} → shift 8State 3:    exp2:  exp3 · | {"+"} → reduce 4    exp2:  exp3 · | {"?"} → reduce 4 shift 6    maybe:  exp3 · "?" | {"?","+"} → reduce 4 shift 6State 4:    exp3:  maybe · | {"?","+"} → reduce 5State 5:    exp3:  "1" · | {"?","+"} → reduce 6State 6:    maybe:  exp3 "?" · | {"?","+"} → reduce 7State 7:    exp1:  · ternary | {":"} → shift 10    exp1:  · exp2 | {":"} → shift 11    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11    ternary:  exp2 "?" · exp1 ":" exp1 | {♦} → shift 12    exp2:  · exp2 "+" exp3 | {"?",":","+"} → shift 11    exp2:  · exp3 | {"?","+"} → shift 13    exp3:  · maybe | {"?","+"} → shift 14    exp3:  · "1" | {"?","+"} → shift 15    maybe:  · exp3 "?" | {"?","+"} → shift 13State 8:    exp2:  exp2 "+" · exp3 | {"?","+"} → shift 9    exp3:  · maybe | {"?","+"} → shift 9State 9:    exp2:  exp2 "+" exp3 · | {"+"} → reduce 3    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 6    maybe:  exp3 · "?" | {"?","+"} → reduce 3 shift 6State 10:    exp1:  ternary · | {":"} → reduce 0State 11:    exp1:  exp2 · | {":"} → reduce 1    ternary:  exp2 · "?" exp1 ":" exp1 | {":"} → shift 26    exp2:  exp2 · "+" exp3 | {"?","+"} → shift 27State 12:    ternary:  exp2 "?" exp1 · ":" exp1 | {♦} → shift 17State 13:    exp2:  exp3 · | {":","+"} → reduce 4    exp2:  exp3 · | {"?"} → reduce 4 shift 16    maybe:  exp3 · "?" | {"?","+"} → reduce 4 shift 16State 14:    exp3:  maybe · | {"?","+"} → reduce 5State 15:    exp3:  "1" · | {"?","+"} → reduce 6State 16:    maybe:  exp3 "?" · | {"?","+"} → reduce 7State 17:    exp1:  · ternary | {♦} → shift 1    exp1:  · exp2 | {♦} → shift 18    ternary:  · exp2 "?" exp1 ":" exp1 | {♦} → shift 18    ternary:  exp2 "?" exp1 ":" · exp1 | {♦} → shift 19    exp2:  · exp2 "+" exp3 | {♦,"?","+"} → shift 18    exp2:  · exp3 | {♦,"+"} → shift 20    exp3:  · maybe | {♦,"+"} → shift 21    exp3:  · "1" | {♦,"+"} → shift 22    maybe:  · exp3 "?" | {♦,"+"} → shift 20State 18:    exp1:  exp2 · | {♦} → reduce 1    ternary:  exp2 · "?" exp1 ":" exp1 | {♦} → shift 7    exp2:  exp2 · "+" exp3 | {♦,"+"} → shift 24State 19:    ternary:  exp2 "?" exp1 ":" exp1 · | {♦} → reduce 2State 20:    exp2:  exp3 · | {♦,"+"} → reduce 4    exp2:  exp3 · | {"?"} → reduce 4 shift 23    maybe:  exp3 · "?" | {♦,"+"} → reduce 4 shift 23State 21:    exp3:  maybe · | {♦,"+"} → reduce 5State 22:    exp3:  "1" · | {♦,"+"} → reduce 6State 23:    maybe:  exp3 "?" · | {♦,"+"} → reduce 7State 24:    exp2:  exp2 "+" · exp3 | {♦,"+"} → shift 25    exp3:  · maybe | {♦,"+"} → shift 25State 25:    exp2:  exp2 "+" exp3 · | {♦,"+"} → reduce 3    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 23    maybe:  exp3 · "?" | {♦,"+"} → reduce 3 shift 23State 26:    exp1:  · ternary | {":"} → shift 10    exp1:  · exp2 | {":"} → shift 11    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11    ternary:  exp2 "?" · exp1 ":" exp1 | {":"} → shift 29    exp2:  · exp2 "+" exp3 | {"?","+"} → shift 13State 27:    exp2:  exp2 "+" · exp3 | {"?","+"} → shift 28    exp3:  · maybe | {"?","+"} → shift 28State 28:    exp2:  exp2 "+" exp3 · | {":","+"} → reduce 3    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 16    maybe:  exp3 · "?" | {"?","+"} → reduce 3 shift 16State 29:    ternary:  exp2 "?" exp1 · ":" exp1 | {":"} → shift 30State 30:    exp1:  · ternary | {":"} → shift 10    exp1:  · exp2 | {":"} → shift 11    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11    ternary:  exp2 "?" exp1 ":" · exp1 | {":"} → shift 31    exp2:  · exp2 "+" exp3 | {"?","+"} → shift 13State 31:    ternary:  exp2 "?" exp1 ":" exp1 · | {":"} → reduce 2

解决方法 我认为这可能是一个优先问题.当解析器查看类似这样的内容时,会发生冲突：

a + b ? c : d

在解析器看到b的时候？而且正在看c,它无法决定是否需要

>减少b ?,以便它将解析a(b？)形式的表达式,然后从那里继续,或者
>减少一个b,以便它将解析形式的表达式(a b)？ c：d

我认为这里的挑战是,在一个案例中,？具有非常低的优先级(当用作三元运算符时),而在另一种情况下,它具有非常高的优先级(当用作一元运算符时).但是,如果您确实以这种方式分配优先级,我认为解析器可能能够消除这些情况的歧义.

希望这可以帮助！

总结

以上是内存溢出为你收集整理的解析 – 如何解决三元表达式(a？b：c)和“可能”表达式(a？)之间的LR(1)语法歧义？全部内容，希望文章能够帮你解决解析 – 如何解决三元表达式(a？b：c)和“可能”表达式(a？)之间的LR(1)语法歧义？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。