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



我被维基百科上的以下引文弄糊涂了:

换句话说,如果一种语言足够合理,可以允许它可以用LR(k)语法来描述。这种语法总是可以机械地转化为等价(但更大)的LR(1)语法。因此,LR(1)解析方法是,理论上,强大到足以处理任何合理的语言。在里面实践中,许多编程语言的自然语法是接近LR(1)。【需要引文】

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

有关为LR(k)语法查找覆盖LR(1)语法的通用算法的参考,请参阅真实世界LR(k>1)语法?

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

一个例子:是C#';s 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是否命名模板,其解析(可以说是标记化)方式不同。

最新更新