0

我知道，一般来说，上下文无关语法是否明确是不确定的。然而，这并不意味着这不能为上下文无关文法的子集决定。

语法用于将输入文本转换为解析树。如果一个文法可以为给定的输入生成不止一个解析树，那么它就是模棱两可的。

LR 解析器算法首先将文法转换为 LR 解析器表。之后，它使用 LR 解析器自动机将给定的输入流处理成使用 LR 解析器表的解析树。第一步通常由解析器生成器完成，而第二步是针对每个解析操作执行的。

考虑 LR 解析器表构造算法construct(G) = T | error。该算法接收上下文无关文法G。如果表构造成功，T则返回无冲突的 LR 解析器表。如果建表失败，则返回错误。这种算法的示例是 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 解析器会确保每个用该语言编写的程序都可以被正确解析。还有其他方法可以确保语法明确吗？

4

1 回答 1

4

如果可以为文法生成 LR(k) 解析器，那么文法肯定是明确的。LR(k) 算法是确定性的；它总是会因错误或正确的解析自动机而终止。（同样适用于 SLR(k) 和 LALR(k) 解析器。）

所以你是对的：如果 LR(k) 解析表生成算法成功终止，那么语法是明确的，但如果它以错误终止，则语法可能是明确的。

我看不出这可以如何推广到“任何” LR 表生成算法，因为声称是这样的算法可能是不正确的或非终止的。但对于标准算法，它肯定是正确的。

对于正式的证明，您可以参考S. Sippu 和 E. Soisalon-Soininen的经典教科书Parsing Theory的第二卷（Springer-Verlag，1990）。

于 2016-03-24T20:37:13.933 回答