是否有任何语言语法示例可以让Yacc表达但不能为Antlr4表达？

Question

我最近尝试学习语言解析器，并且总是看到有关Yacc和Antlr（关于LALR和LL）差异的评论。总是有一些总结性的措词，例如“ LALR更强大”。但我不明白它的真正含义

那么，有谁能启发我，这里的强大一词是什么意思？

我只是认为这意味着“ Yacc可以做Antlr不能做的事情”，如果我希望我能看到有关它的确切示例

Answer 1

LR(1) 但不是 LL(*) 的语言

\n\n

LL 和 LR 语法的语言理论比较问题有答案以下语言的

\n\n

{ a^i b^j | i\xe2\x89\xa5j }\n

\n\n

也就是说，一定数量的a后跟相同或更少数量的b。

\n\n

类似问题的答案引用了相同的语言无法用 LL 表示的 LR 语法的示例？。然而，现在的问题是不同的，因为有人说“LL”，意思是 LL(k)，而这里我们问的是 LL(*)（和 Antlr4）。

\n\n

直观演示（不是证明）

\n\n

让我们直观地认为这是 LR(1) 而不是 LL(*)。

\n\n

首先，LR(1) 语法（从第二个链接的答案复制）：

\n\n

S ::= a S | P\nP ::= a P b | <empty>\n

\n\n

直观上，这是 LR(1)，因为 LR(1) 解析器可以将任意数量的a符号压入其堆栈，然后当它到达第一个 时b，开始使用第一个产生式成对弹出相应的a符号。如果用完符号，它会使用 的第一个产生式弹出剩余符号。如果符号用完而仍有符号剩余，则表示发生错误。（请记住，在这种情况下，我们主要关注识别，因此输出要么是“是”，要么是“错误”。）a,bPbaSab

\n\n

相反，这个文法不是 LL(*)。直观上，LL(*) 解析器在看到第一个 时必须决定a是使用第一个还是第二个产生式S。它希望向前查看是否有与剩余符号一样多的b符号a，因为如果没有，那么它就会知道它必须使用第一个产生式来“烧毁”多余的a符号。但是 LL(*) 前瞻仅限于识别常规语言，而常规语言无法识别，{ a^i b^i }因为它无法“计数”。

\n\n

当然，一种语法不是 LL(*)的事实并不意味着该语言不是 LL(*)，因为可能存在更聪明的语法。为了证明它不是 LL(*)，我可能会从正式定义开始，假设我有一个具有这些条件的语法，然后使用泵引理参数来表明它无法正确识别感兴趣的语言。但我会让链接的资源足以作为该语言不是 LL(*) 的严格理由。

\n\n

更高层次的诠释

\n\n

我的想法是，LL 在解析树“向下”的方向上做出决定，而 LR 在“向上”的方向上做出决定。为了创建一种不是 LL(k) 的语言，我们对其进行了安排，以便当所需的信息超出了符号的范围时，假定的解析器必须致力于对符号的解释。k符号的解释。为了使其不是 LL(*)，我们需要将关键信息置于只有首先识别非常规语言才能跨越的视野之外。

\n\n

相反，LR 可以将符号推入其堆栈，延迟它们的解释，直到它看到相关产生式的结束以及已经构建的对之间所有内容的解释为止。

\n\n

为了让这个更具体一些，想象一种编程语言，它有两种用大括号括起来的东西，比如代码块和对象文字（如 Javascript）。想象一下它们都可以出现在相同的上下文中（与 Javascript 不同）：

\n\n

  var x = { console.log("I am a code block"); /*result is*/ 6; };\n  var x = { a:1, b:2 };\n

\n\n

在这种情况下，解析器会遇到{. LL 必须立即决定这是代码块的开始还是对象文字的开始。在 Javascript 中，对象文字键必须是标识符或字符串文字，并且两者的联合是常规语言，因此 LL(*) 解析器可以跳过“identifier or stringlit”的正则表达式来检查 ，:这将信号对象文字（否则代码块）。

\n\n

  {                    // hmmm, code or object?\n  { a                  // possible object literal key\n  { a :                // a-ha! definitely object literal\n

\n\n

相反，如果键可以是任意字符串类型的表达式，则 LL(*) 就会遇到麻烦，因为它必须平衡括号才能通过假定的键，以便它可以检查:：

\n\n

  {                    // start of object literal?\n  { (                  // uh-oh ...\n  { (a                 // I\'m\n  { (a ?               //     getting\n  { (a ? b             //             lost\n  { (a ? b :           // is this the \':\' after a key? help!\n

\n\n

相反，LR 愉快地推迟了 的解释{，将其推入堆栈，并实际上继续进行两种潜在的解释，直到某个标记消除它们的歧义。

\n\n

希望这可以让我们直观地了解 LR 包含哪些内容而 LL(*) 不包含哪些内容。

\n\n

有相反的例子（LL(*)但不是LR），尽管我不知道它们是什么样的（“不是LR”是一个很难思考的类）；有关详细信息，请参阅第一个链接的问题。

\n\n

Antlr4 语义谓词

\n\n

现在，问题标题实际上询问的是 Antlr4。Antlr4 具有语义谓词，有效地允许程序员插入任意先行计算。因此，如果您愿意跳出语法形式主义，实际上 Anltr4 解析器可以识别的内容没有限制（除了可判定性之外）。

\n