我被维基百科上的以下引文弄糊涂了:
换句话说,如果一种语言足够合理,可以允许它可以用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
是否命名模板,其解析(可以说是标记化)方式不同。