LR(k)转换为LR(1)语法

Question

我对维基百科上的引用感到困惑：

换句话说，如果一种语言足够合理，可以允许高效的一遍扫描解析器，那么它可以由LR(k)文法描述。而且，该文法总是可以机械地转化为等价的（但更大的）LR(1)文法。因此，LR(1)解析方法在理论上足够强大，可以处理任何合理的语言。实际上，许多编程语言的自然文法接近于LR(1)。

这意味着解析器生成器（例如bison）非常强大（因为它可以处理LR(k)文法），如果能够将LR(k)文法转换为LR(1)文法。是否存在一些示例或如何执行此操作的说明？我想知道这个，因为我的语法中存在移位/规约冲突，但我认为这是因为它是LR(2)文法，想将其转换为LR(1)文法。附带问题：C ++是否是不合理的语言，因为我读到，bison生成的解析器无法解析它。

- user1095108

Answer 1

查找覆盖 LR(k) 语法的通用算法以获得 LR(1) 语法的参考，请参阅Real-world LR(k > 1) grammars?

通用算法会生成相当大的语法；事实上，我非常确定生成的 PDA 与 LR(k) PDA 的大小相同。然而，在特定情况下，可能会想出更简单的解决方案。不过，总体原则仍然适用：需要通过无条件移位来推迟移位/规约决策，直到可以使用单个前瞻记号做出决策。

其中一个例子是：C#的 lambda 表达式语法是否为 LALR(1)？

如果不知道有关您的语法的更多详细信息，则无法提供更多帮助。

关于 C++，使其难以解析的是预处理器和解析（以及词法分析）模板实例化中的一些边角情况。表达式的解析取决于符号的“种类”（而不是类型）（在符号出现的上下文中），这使得使用 bison 进行精确解析变得复杂。[1] “不合理”是一个价值判断，我无法做出这样的判断；当然，如果有不同的语法，则工具支持（如准确的语法颜色着色和选项完成器）将非常简单，但证据表明编写（甚至阅读）良好的 C++ 代码并不那么困难。

---

注释：

[1] 经典的棘手解析问题也适用于 C，即 (a)*b，如果 a 表示类型，则为解除引用的转换，否则为乘法。如果您在以下上下文中编写它：c/(a)*b，那么很明显，在不知道它是转换还是乘法的情况下，无法构造 AST，因为这会影响 AST 的形状。

更具体地说，C++ 中的一个问题是：x<y>(z)（或x<y<z>>(3)），根据 x 是否命名模板，解析（和可能的记号化）方式不同。

- rici