4

我对维基百科的以下引用感到困惑:

换句话说,如果一种语言足够合理以允许高效的一次性解析器,那么它可以用 LR(k) 文法来描述。并且该语法总是可以机械地转换为等效(但更大)的 LR(1) 语法。因此,理论上,LR(1) 解析方法足够强大,可以处理任何合理的语言。在实践中,许多编程语言的自然语法接近于 LR(1)。[需要引用]

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

4

1 回答 1

3

LR(1)有关查找文法覆盖文法的通用算法的参考资料LR(k),请参阅Real-world LR(k > 1) 文法?

通用算法产生相当大的文法;事实上,我很确定生成的 PDA 与 PDA 的大小相同LR(k)。但是,在特定情况下,可以提出更简单的解决方案。但是,一般原则适用:您需要通过无条件移位来推迟移位/减少决策,直到可以使用单个前瞻令牌做出决策。

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

在不了解您的语法的更多细节的情况下,我真的无能为力。

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


笔记:

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

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

于 2013-12-19T20:45:29.173 回答