parsing - LALR(1) 解析器中的冲突解决

Question

关于LALR(1)解析器冲突的一些问题，主要涉及到解析的细节：

1. 根据教科书中描述的不同 LALR(1) 解析器，如果遇到移位/归约冲突，那么这表明语法一开始就不是 LALR(1)，对吧？

2. Reduce/Reduce 冲突可能出现在有效的LALR(1) 语法中，因为从 LR(1) 到 LALR(1) 的状态合并，对吧？

3. YACC 和 GNU Bison 中使用的优先级和关联性是用来帮助解决移位/减少冲突的工具，对吧？

4. 此外，只有当冲突的移位/归约规则优先级等于先行符号优先级时，解析器才应该检查关联性，在任何其他情况下关联性都无关紧要，对吧？

我之所以问，是因为我不是 100% 确定，而且这些书籍没有提供关于解决冲突的太多细节，我在这个主题上找到的仅有的几行是在 GNU Bison 手册中

与上述 Bison 手册链接相关的问题：

• 为什么他们声称在冲突规则或前瞻令牌中没有优先级，选择是 SHIFT？我认为，如果减少规则有任何优先级，它会完全没有优先级地击败前瞻。

Answer 1

1. 如果在 LALR(k) 构造期间发现任何冲突（移位/归约或归约/归约），则文法不是 LALR(k)。

2. 从 LR(1) 到 LALR(1) 的状态合并不会产生移位/归约冲突，因此如果存在冲突，则文法也不是 LR(1)。但它会产生减少/减少冲突。如果是，则文法不是 LALR(1)，即使它是 LR(1)。（这并不是真正的“有效性”问题；而是特定算法的可解析性问题。）

3. 是的，优先级（和关联性，这只是优先级的一个子案例）允许解决移位/减少冲突。

4. 优先级是产生式（左侧）和前瞻标记（右侧）之间的比较。关联性会影响所使用的比较运算符：≤ 或 <（或者，在 的情况下%nonassoc，等于错误）。

Dragon book中对算法有很好的讨论。但是，这并不是很复杂：如果产生式“获胜”，则解析器减少；否则它会改变。

%prec额外问题：仅当为产生式（通过或默认情况下，产生式中最后一个终端的优先级）和前瞻令牌定义了优先级时，才应用优先级规则。如果其中任何一个缺少优先声明，则 shift 获胜。这可能看起来不合逻辑，但事实就是如此。