parsing - 形式语法权力的实际后果？

Question

每个本科生编译器入门类(class)都会回顾上下文无关文法的常用子集:LL(k)、SLR(k)、LALR(k)、LR(k)。我们还了解到，对于任何给定的 k，这些语法中的每一个都是下一个的子集。

我从未见过的是对哪些类型的编程语言句法特征可能需要转移到不同的语言类的解释。 GLR 解析器有一个明显的实际动机，即在解析 C++ 时避免将解析器和符号表混在一起。但是两个“标准”类 LL 和 LR 之间的区别呢？

两个问题:

什么(一般)句法结构可以用 LR(k) 而不是 LL(k') 来解析？

如果有的话，这些结构以什么方式表现为理想的语言结构？

通过使 k 尽可能小来降低语言能力有一个合理的论据，因为需要很多很多前瞻标记的语言对人类来说更难解析，对机器来说“更难”解析。问题 (2) 含蓄地询问相同的推理是否最终在类之间以及类内成立。

编辑:这是一个例子来说明我正在寻找的各种答案，但对于常规语言而不是上下文无关:

在描述一种正则语言时，通常会得到三个运算符:+ , * , 和 ? .现在，您可以删除 +不降低语言的力量；而不是写 x+ , 你写 xx* ，效果是一样的。但如果 x是一些毛茸茸的大表情，两人x由于人类健忘，s 可能会随着时间的推移而发散，从而产生与原始作者意图不匹配的语法正确的正则表达式。因此，即使添加 +并没有严格地增加权力，它确实使符号更不容易出错。

当从 LR 切换到 LL 时，是否存在具有类似实际(人类？)影响的结构必须“移除”？

Answer 1

解析(我声称)有点像排序:在 CS 的早期，这个问题是很多思想的焦点，导致了一组很好理解的解决方案和一些很好的理论结果。

我的主张是，我们在编译器类(class)中获得(或提供给我们这些教学者)的图片在某种程度上是对错误问题的漂亮答案。

为了更直接地回答您的问题，LL(1) 语法无法解析您可能想要解析的所有类型；例如，带有可选的“else”的“if”的“自然”表述。

可是等等!我不能将我的语法重新表述为 LL(1) 语法，然后通过遍历它来修补源树吗？你当然可以!在某种程度上，这就是解析器使用哪种语法的问题在很大程度上没有实际意义的原因。

此外，当我还是一名本科生时(1990-94 年)，对空格敏感的语法显然是魔鬼的杰作。现在，Python 和 Haskell 的设计将空白敏感度带回了人们的视野。此外，Packrat 解析说“看看你的理论纯度:我只是将解析器定义为一组规则，我不在乎我的语法属于哪个类。” (转述)

总而言之，我同意我认为是您隐含的建议:在 2009 年，清楚地了解类 LL(k) 和 LR(k) 之间的区别本身不如制定和调试 a 的能力重要使您的解析器生成器满意的语法。