每个本科生编程入门课程都会回顾常用的无上下文语法子集:LL(k),SLR(k),LALR(k),LR(k).我们还被教导,对于任何给定的k,这些语法中的每一个都是下一个语法的子集.
我从未见过的是解释什么样的编程语言语法特征可能需要转移到不同的语言类.GLR解析器有一个明显的实际动机,即在解析C++时避免解析器和符号表的不合理混合.但是,LL和LR这两个"标准"类之间的差异呢？
两个问题:
通过使k尽可能小来减少语言能力有一个似是而非的理由,因为需要许多许多前瞻标记的语言对于人类来说难以解析,以及机器要解析的"更难".问题(2)隐含地询问相同的推理是否最终在类之间以及在类中保持.
编辑:这是一个例子来说明我正在寻找的各种答案,但对于常规语言而不是无上下文:
当描述一个普通的语言,人们通常得到三大运营商:+,*和?.现在,你可以删除+而不降低语言的力量; 而不是写作x+,你写xx*,效果是一样的.但是,如果x是一些大而多毛的表达,那么x由于人类的遗忘,这两个人可能会随着时间的推移而发散,产生一个与原作者意图不符的语法正确的正则表达式.因此,即使添加+不严格增加功率,它确实使符号更不容易出错.
是否存在具有类似实际(人类？)效果的结构,从LR切换到LL时必须"删除"？
解析(我声称)有点像排序:一个问题是CS早期的很多思想的焦点,导致一组理解得很好的解决方案,并带来了一些很好的理论结果.
我的主张是,我们在编译器课上得到(或者给予我们这些教授)的图片在某种程度上是对错误问题的美妙回答.
为了更直接地回答您的问题,LL(1)语法无法解析您可能要解析的各种事物; 例如,带有可选'else'的'if'的"自然"表述.
可是等等!我不能将我的语法重新表达为LL(1)语法,然后通过在其上行走来修补源树吗？你当然可以!在某种程度上,这就是你的解析器使用什么样的语法的问题.
另外,当我还是一名本科生(1990-94)时,空格敏感的语法显然是魔鬼的作品; 现在,Python和Haskell的设计正在将空白灵敏度带回到光明之中.此外,Packrat解析说"要理解你的理论纯度:我只是将解析器定义为一组规则,我不关心我的语法属于哪个类." (转述)
总之,我同意我认为你暗示的建议:在2009年,明确理解LL(k)和LR(k)类之间的差异本身并不比制定和调试使您的解析器生成器开心的语法.