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

Question

我对以下内容感到困惑quote来自维基百科:

In other words, if a language was reasonable enough to allow an efficient one-pass parser, it could be described by an LR(k) grammar. And that grammar could always be mechanically transformed into an equivalent (but larger) LR(1) grammar. So an LR(1) parsing method was, in theory, powerful enough to handle any reasonable language. In practice, the natural grammars for many programming languages are close to being LR(1).[citation needed]

这意味着解析器生成器，如 bison，非常强大(因为它可以处理 LR(k) 语法)，如果能够转换 LR(k) 语法到 LR(1) 语法。是否存在一些这样的例子，或者如何做到这一点的秘诀？我想知道这一点，因为我的语法中有移位/归约冲突，但我认为这是因为它是 LR(2) 语法，并且想将其转换为 LR(1) 语法。附带问题:C++ 是一种不合理的语言吗，因为我读过，bison 生成的解析器无法解析它。

Answer 1

有关寻找覆盖的通用算法的引用LR(1) LR(k) 的语法语法，参见Real-world LR(k > 1) grammars?

通用算法产生相当大的语法；事实上，我非常确定生成的 PDA 与 LR(k) 的大小相同。 PDA 就可以了。然而，在特定情况下，可以提出更简单的解决方案。不过，一般原则是适用的:您需要通过无条件移位来推迟移位/归约决策，直到可以使用单个前瞻标记做出决策为止。

一个例子:Is C#'s lambda expression grammar LALR(1)?

在不了解有关语法的更多详细信息的情况下，我无法提供更多帮助。

对于 C++，使解析变得棘手的是预处理器和解析(和词法分析)模板实例化中的一些极端情况。事实上，表达式的解析取决于符号的“种类”(而不是类型)(在符号出现的上下文中)，这使得使用 bison 进行精确解析变得复杂。 [1] “不合理”是一种我不愿意做出的值(value)判断；当然，使用不同的语法，工具支持(如准确的语法着色器和制表符完成器)会很简单，但证据表明编写(甚至阅读)好的 C++ 代码并不难。

<小时/>

注释:

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

一个更特定于 C++ 的问题是:x<y>(z) (或 x<y<z>>(3) )根据是否 x 进行不同的解析(并且可以说标记化)是否命名模板。