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

Question

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

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

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

Answer 1

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

问题Language theoretic comparison of LL and LR grammars的answer使用以下语言，即LR(1)但不是LL(*):

{ a^i b^j | i≥j }

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

this answer将相同的语言引用给相似的问题Example of an LR grammar that cannot be represented by LL?。但是，当前问题有所不同，因为一个人说“LL”，意思是LL(k)，而在这里我们要问的是LL(*)(和Antlr4)。

直观演示(不是证明)

让我们直观地指出这是LR(1)，而不是LL(*)。

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

S ::= a S | P
P ::= a P b | <empty>

直观地讲，这是LR(1)，因为LR(1)解析器可以将任意数量的a符号压入其堆栈，然后当到达第一个b时，开始使用a对弹出对应的a,b符号，并使用第一个产生的P。如果b符号用完了，它将使用a的第一个生成方式弹出剩余的S符号。如果剩余a符号用尽了b符号，则表明存在错误。 (请记住，在这种情况下，我们主要关注识别，因此输出为"is"或“错误”。)

相反，该语法不是LL(*)。凭直觉，LL(*)解析器必须在看到第一个a时决定是否使用S的第一或第二个产生方式。它希望向前看是否剩余的b符号与a符号一样多，因为如果没有，那么它将知道它必须使用第一个生产来“燃烧”多余的a符号。但是LL(*)前瞻仅限于识别常规语言，并且常规语言无法识别{ a^i b^i }，因为它无法识别"count"。

当然，一个语法不是LL(*)的事实并不意味着该语言不是LL(*)，因为可能存在更聪明的语法。为了证明它不是LL(*)，我可能以formal definition开头，假设我对这些条件有一个语法，然后使用pumping lemma参数表明它不能正确识别感兴趣的语言。但是，我将使链接的资源足以满足该语言不是LL(*)的严格要求。

更高层次的解释

我的思考方式是，LL在“向下”解析树的方式上做出决定，而LR在“向上”解析树的方式上做出决定。为了制作不是LL(k)的语言，我们对其进行了排列，以便当所需的信息超出k符号的范围时，假定的解析器将不得不对符号进行解释。为了使其不成为LL(*)，我们需要将关键信息置于一个只能先识别非常规语言才能跨越的范围。

相反，LR可以将符号插入其堆栈，从而延迟其解释，直到看到相关生产的结束并已经构造了它们之间的所有内容的解释为止。

为了使这一点更加具体，请想象一下一种编程语言，它包含两种用大括号括起来的东西，例如代码块和对象文字(例如Javascript)。想象它们都可以在相同的上下文中发生(不同于Javascript):

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

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

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

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

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

相反，LR很乐意推迟对{的解释，将其插入堆栈，并实际上进行两种可能的解释，直到某些标记消除了歧义。

希望这可以为LR包含哪些东西而LL(*)不包含东西提供一些直觉。

有一些相反的例子(LL(*)但不是LR)，尽管我不知道它们的外观(“not LR”是一个很难考虑的问题)；有关详细信息，请参见第一个链接的问题。

Antlr4语义谓词

现在，问题标题实际上是在询问有关Antlr4的问题。 Antlr4具有semantic predicates，有效地允许程序员插入任意的超前计算。因此，如果您愿意超越语法形式主义，那么Anltr4解析器可以识别的内容实际上没有任何限制(可判定性不足)。