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

Question

我对维基百科的以下报价感到困惑：

换句话说，如果一种语言足够合理，允许高效的一次通过解析器，那么它可以用LR(k)语法来描述。而这种语法总是可以机械地转换成一个等价的(但更大的) LR(1)语法。因此，从理论上讲，LR(1)解析方法足够强大，可以处理任何合理的语言。实际上，许多编程语言的自然语法接近于LR(1)所需的.citation。

这意味着解析器生成器(如bison )非常强大(因为它可以处理LR(k)语法)，如果能够将LR(k)语法转换为LR(1)语法的话。这方面是否存在一些例子，或如何做到这一点的食谱？我想知道这一点，因为我的语法中有一个移位/减少冲突，但我认为这是因为它是一个LR(2)语法，并且希望将它转换成一个LR(1)语法。附带问题：C++是一种不合理的语言，因为我已经读过了，bison-generated解析器不能解析它。

Answer 1

有关为LR(1)语法查找覆盖LR(k)语法的通用算法的参考信息，请参阅Real-world LR(k > 1) grammars?

通用算法产生相当大的语法；事实上，我非常肯定得到的PDA与LR(k) PDA的大小相同。但是，在特定情况下，可以提出更简单的解决方案。但是，一般的原则是适用的:您需要通过无条件的移位来推迟shift/reduce决策，直到可以使用一个前瞻性令牌做出决定为止。

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

不知道更多关于你语法的细节，我真的帮不了什么忙。

关于C++，需要分析的是预处理程序和解析(和词法)模板实例化中的一些角落案例。表达式的解析取决于符号的“种类”(而不是类型)(在符号发生的上下文中)，这使得bison的精确解析变得复杂。1“不合理”是我不习惯的一种价值判断；当然，工具支持(比如精确的语法着色器和制表符)使用不同的语法很简单，但是证据是，编写(甚至阅读)好的C++代码并不难。

备注：

1经典的棘手的解析(也适用于C )是(a)*b，如果a表示类型，它是取消引用的强制转换，否则是乘法。如果您要在上下文中编写它：c/(a)*b，很明显，如果不知道它是一个强制转换还是一个产品，就不能构造它，因为这会影响AST的形状，

一个更特定于C++的问题是：x<y>(z) (或x<y<z>>(3))，它的解析(可以说是tokenise)是不同的，这取决于x是否为模板命名。