1

考虑以下 LR 语法的尝试，其中引用的字符串被假定为终端符号：

S: E
E: ("y" | "z") X A
E: ("y" | "z") X B
X: "x"
X:  X "x"
A: "a"
B: "b"

看起来这应该是一个无冲突的 LR(1) 文法，因为它等价于

S: E
E: ("y" | "z") X (A | B)
X: "x"
X:  X "x"
A: "a"
B: "b"

然而，我认为（？）任何现实世界的解析器都会机械地将它翻译成

S: E
E: U X A
E: V X B
U: "y"
U: "z"
V: "y"
V: "z"
X: "x"
X:  X "x"
A: "a"
B: "b"

其中U和V是在解析树中由其子代直接替换的符号。

得到的文法现在是 LR(∞)；它对 LR(k < ∞) 有减少-减少冲突——尽管它确实不应该！

现在，我意识到可以让这个例子变得更复杂（比如说，使用重复和析取）；事实上，据我所知，检测这种情况可以简化为测试两个上下文无关语法的等价性，这（如果我没记错的话）是一个无法确定的问题。

我的问题是：

  1. 我是否正确地认为这是一个实际问题，还是我错过了一个实际的解决方案？

  2. 处理这个问题的最佳方法是什么？报告冲突是最好的方法，还是在实践中使用启发式方法来解决问题？

4

0 回答 0