关于LALR(1)解析器冲突的一些问题,主要涉及解析的细节:
根据教科书中描述的不同 LALR(1) 解析器,如果遇到 shift/reduce 冲突,那么这表明语法不是 LALR(1) 开始,对吗? 减少/减少冲突可能出现在有效 LALR(1) 文法,因为从 LR(1) 到 LALR(1) 的状态合并,对吧? YACC 和 GNU Bison 中使用的优先级和关联性是否引入了工具来帮助解决转移/减少冲突,对吗? 此外,仅当冲突的移位/归约规则优先级等于前瞻符号优先级时,解析器才应检查关联性,在任何其他情况下关联性都无关紧要,对吗? 我问是因为我不是 100% 确定,而且这些书没有提供关于冲突解决的太多细节,我在这个主题上找到的唯一几行是
in the GNU Bison Manual与上面的 Bison 手册链接相关的问题:
为什么他们声称冲突规则中没有优先级或 前瞻标记,选择是 SHIFT?我认为如果减少规则有任何优先级,它就会在没有任何优先级的情况下击败前瞻。
如果在 LALR(k) 构造过程中发现任何冲突(shift/reduce 或 reduce/reduce),则语法不是 LALR(k)。 从 LR(1) 到 LALR(1) 的状态合并不会产生 shift/reduce 冲突,所以如果有,语法也不是 LR(1)。但它会产生减少/减少冲突。如果是,则语法不是 LALR(1),即使它是 LR(1)。 (这不是真正的“有效性”问题;而是特定算法的可解析性问题。)是的,优先级(和结合性,这只是优先级的一个子案例)允许解决移位/减少冲突。 优先级是产生式(左侧)和前瞻标记(右侧)之间的比较。关联性影响使用的比较运算符:≤ 或 <(或者,在 %nonassoc
的情况下,等于错误)。 在
Dragon book 中有对该算法的精彩讨论。 .然而,它并不是很复杂:如果生产“获胜”,解析器就会减少;否则它会移动。
额外问题:仅当为产生式(通过
%prec
或,默认情况下,产生式中最后一个终端的优先级)和前瞻标记定义了优先级时,才应用优先规则。如果其中任何一个缺少优先声明,则 shift 获胜。这可能看起来不合逻辑,但事实就是如此。