形式语法能力的实际后果?

解析(我声称)有点像排序:在CS的早期,这个问题是许多思想的焦点,导致了一系列理解良好的解决方案,并产生了一些不错的理论结果。

我的观点是,我们在编辑课上得到(或给予,给我们中的老师)的图片在某种程度上是对错误问题的一个很好的回答。

为了更直接地回答您的问题,ll(1)语法不能解析您可能想要解析的所有类型的东西;例如,使用可选“else”的“if”的“natural”公式。

但是等等!难道我不能把我的语法重新表述成ll(1)语法,然后在源代码树上遍历它来修补它吗?当然可以!在某种程度上,这就是为什么您的解析器在很大程度上没有使用哪种语法的问题。

另外,当我还是大学生的时候(1990-94),对空格敏感的语法显然是魔鬼的工作;现在,python和haskell的设计将空格敏感重新带到了光明中。另外,packrat解析说“为了检验你理论上的纯洁性:我只是将解析器定义为一组规则,我不在乎我的语法属于哪个类。”(意译)

总之,我同意你的暗示:在2009年,对ll(k)类和lr(k)类之间的区别的清楚理解,与其说是能够制定和调试语法,让你的解析器生成器感到高兴,还不如说是重要的。

ll和lr之间的区别主要在于先行机制。人们通常说LR解析器携带更多的“上下文”。要实际看到这一点,请考虑以s作为起始符号的递归语法定义:

A -> Ax | x 
B -> Ay
C -> Az
S -> B | C

当k是一个小的固定值时,解析类似于xxxxy的字符串更适合于lr解析器。然而,现在流行的ll解析器(如antlr)并没有将k限制在如此小的值上,大多数人不再关心。

我希望这或多或少符合你的问题。当然,Knuth指出,任何明确的上下文无关语言都可以 辨识 通过一些lr(1)语法。然而,在实践中,我们也关注翻译。

旁注:你也可能喜欢阅读 http://www.antlr.org/article/needlook.html .

这并没有被证明,但我一直在质疑,类LR的解析是否真的与大脑在阅读某些符号时的工作方式相似。例如,当我们阅读一个英语句子时,很明显我们是从左到右阅读的。但是,考虑下面的模式:

. ……②……

我更希望像这样的短图案人们不会从左到右逐字地读“点-点-点-条-点-点-点-点-点-点”,而是以平行或至少某种模糊迭代的方式处理图案。换句话说,我不认为我们必须以从左到右的方式阅读所有模式,使用ll/lr解析器所使用的线性先行。

此外,如果我们可以使用lr(1)语法描述任何上下文无关的语言,那么很明显,仅仅识别一个字符串和“理解”它是不同的。

首先,左递归定义在ll(k)语法中是不可能的(据我所知),不了解其他语法。这并不意味着可以定义其他事物 大量的 否则会很痛苦。例如,在左递归语言(伪代码)中,将表达式组合在一起很容易:

lexer rule expression = other rules
                        | expression
                        | '(' expression ')';

就可以用左递归生成的语法有用的东西而言,简单语法是否算作语法有用?

语言的能力不受其语法和语法的限制。

用ll(k)语法定义任何语言特性都是可能的,它对人类来说可能不是很可读。