解析 – 如何解决三元表达式(a?b:c)和“可能”表达式(a?)之间
发布时间:2020-12-16 07:03:40 所属栏目:百科 来源:网络整理
导读:我创建了一个语法,其精简版本如下: (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可解析的. (如果
我创建了一个语法,其精简版本如下:
(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 6 Conflicts in state 9: Reduction using rule 3: exp2: exp2 "+" exp3 · | "?" Shift to state 6 Conflicts in state 13: Reduction using rule 4: exp2: exp3 · | "?" Shift to state 16 Conflicts in state 20: Reduction using rule 4: exp2: exp3 · | "?" Shift to state 23 Conflicts in state 25: Reduction using rule 3: exp2: exp2 "+" exp3 · | "?" Shift to state 23 Conflicts 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 3 State 1: exp1: ternary · | {?} → reduce 0 State 2: ternary: exp2 · "?" exp1 ":" exp1 | {?} → shift 7 exp2: exp2 · "+" exp3 | {"?","+"} → shift 8 State 3: exp2: exp3 · | {"+"} → reduce 4 exp2: exp3 · | {"?"} → reduce 4 shift 6 maybe: exp3 · "?" | {"?","+"} → reduce 4 shift 6 State 4: exp3: maybe · | {"?","+"} → reduce 5 State 5: exp3: "1" · | {"?","+"} → reduce 6 State 6: maybe: exp3 "?" · | {"?","+"} → reduce 7 State 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 13 State 8: exp2: exp2 "+" · exp3 | {"?","+"} → shift 9 exp3: · maybe | {"?","+"} → shift 9 State 9: exp2: exp2 "+" exp3 · | {"+"} → reduce 3 exp2: exp2 "+" exp3 · | {"?"} → reduce 3 shift 6 maybe: exp3 · "?" | {"?","+"} → reduce 3 shift 6 State 10: exp1: ternary · | {":"} → reduce 0 State 11: exp1: exp2 · | {":"} → reduce 1 ternary: exp2 · "?" exp1 ":" exp1 | {":"} → shift 26 exp2: exp2 · "+" exp3 | {"?","+"} → shift 27 State 12: ternary: exp2 "?" exp1 · ":" exp1 | {?} → shift 17 State 13: exp2: exp3 · | {":","+"} → reduce 4 exp2: exp3 · | {"?"} → reduce 4 shift 16 maybe: exp3 · "?" | {"?","+"} → reduce 4 shift 16 State 14: exp3: maybe · | {"?","+"} → reduce 5 State 15: exp3: "1" · | {"?","+"} → reduce 6 State 16: maybe: exp3 "?" · | {"?","+"} → reduce 7 State 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 20 State 18: exp1: exp2 · | {?} → reduce 1 ternary: exp2 · "?" exp1 ":" exp1 | {?} → shift 7 exp2: exp2 · "+" exp3 | {?,"+"} → shift 24 State 19: ternary: exp2 "?" exp1 ":" exp1 · | {?} → reduce 2 State 20: exp2: exp3 · | {?,"+"} → reduce 4 exp2: exp3 · | {"?"} → reduce 4 shift 23 maybe: exp3 · "?" | {?,"+"} → reduce 4 shift 23 State 21: exp3: maybe · | {?,"+"} → reduce 5 State 22: exp3: "1" · | {?,"+"} → reduce 6 State 23: maybe: exp3 "?" · | {?,"+"} → reduce 7 State 24: exp2: exp2 "+" · exp3 | {?,"+"} → shift 25 exp3: · maybe | {?,"+"} → shift 25 State 25: exp2: exp2 "+" exp3 · | {?,"+"} → reduce 3 exp2: exp2 "+" exp3 · | {"?"} → reduce 3 shift 23 maybe: exp3 · "?" | {?,"+"} → reduce 3 shift 23 State 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 13 State 27: exp2: exp2 "+" · exp3 | {"?","+"} → shift 28 exp3: · maybe | {"?","+"} → shift 28 State 28: exp2: exp2 "+" exp3 · | {":","+"} → reduce 3 exp2: exp2 "+" exp3 · | {"?"} → reduce 3 shift 16 maybe: exp3 · "?" | {"?","+"} → reduce 3 shift 16 State 29: ternary: exp2 "?" exp1 · ":" exp1 | {":"} → shift 30 State 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 13 State 31: ternary: exp2 "?" exp1 ":" exp1 · | {":"} → reduce 2 解决方法
我认为这可能是一个优先问题.当解析器查看类似这样的内容时,会发生冲突:
a + b ? c : d 在解析器看到b的时候?而且正在看c,它无法决定是否需要 >减少b ?,以便它将解析a(b?)形式的表达式,然后从那里继续,或者 我认为这里的挑战是,在一个案例中,?具有非常低的优先级(当用作三元运算符时),而在另一种情况下,它具有非常高的优先级(当用作一元运算符时).但是,如果您确实以这种方式分配优先级,我认为解析器可能能够消除这些情况的歧义. 希望这可以帮助! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |