我知道一般来说，无上下文语法是否明确是不可判定的 . 但是，这并不意味着无法为无上下文语法的子集决定这一点 .
语法用于将输入文本转换为解析树 . 如果语法可以为给定输入生成多个解析树，则该语法是不明确的 .
LR解析器算法首先将语法转换为LR解析器表 . 然后，它使用LR解析器自动机使用LR解析器表将给定输入流处理为解析树 . 第一步通常由解析器生成器完成，而第二步则针对每个解析操作执行 .
考虑LR解析器表构造算法 construct(G) = T | error . 该算法接收无上下文语法 G . 如果表构造成功，则返回无冲突的LR解析器表 T . 如果表构造失败，则返回错误 . 这种算法的示例是SLR，LALR和CLR . 算法失败的典型示例是shift-reduce和reduce-reduce冲突 .
对于有限输入流和无冲突LR解析器表，LR解析器自动机可以确定性地从给定输入流导出一个解析树，或者如果输入流与语法不匹配则返回错误 . 解析步骤可以形式化为 parse(T, I) = O | error ，其中 T 是无冲突的LR解析表， I 是令牌的输入流， O 是单个解析树 . 如果输入流与语法不匹配，则返回错误 .
问题
总结我的理解上面的陈述是任何可以某种方式转换成无冲突的LR解析器表的语法是明确的 . 但是，如果算法返回错误，则这并不意味着关于语法是否模糊的任何陈述 . 因此，LR表构造算法半决定无上下文语法的子集是否是明确的 . 它是否正确？
以下是我的结论可能落空的一些步骤：
-
LR表构造算法可能不会终止
-
LR解析器自动机可能不会终止
-
LR表构造算法是不正确的，因此LR解析器自动机将不接受与构造它的语法完全相同的输入流集，或者它导出另一个解析树而不是语法 .
据我所知，对于常见的LR表构造算法，以上都不是正确的 .
我无法找到关于此的明确陈述，所以我非常感谢解释以及参考这个问题的讨论和明确答案 .
我认为这个问题在设计编程语言时非常重要，因为如果我的结论是正确的，LR解析器可以确保用该语言编写的每个程序都可以正确解析 . 还有其他方法可以确保语法是明确的吗？
1 回答
如果可以为语法生成LR（k）解析器，那么语法肯定是明确的 . LR（k）算法是确定性的;它总是会终止，无论是错误还是正确的解析自动机 . （类似地，对于SLR（k）和LALR（k）解析器 . ）
所以你是对的：如果LR（k）解析表生成算法成功终止，那么语法是明确的，但如果它以错误终止，则语法可能是明确的 .
我没有看到这可以如何推广到“任何”LR表生成算法，因为声称是这样的算法可能是不正确的或非终止的 . 但对于标准算法，它肯定是正确的 .
对于正式证明，您可以参考S. Sippu和E.Soisalon-Soininen（Springer-Verlag，1990）的经典教科书Parsing Theory的第二卷 .