有没有Yacc可以表达而Antlr4不能表达的语言语法的例子？
Is there any example of language grammar that possible for Yacc to express but impossible for Antlr4?
最近想学习语言解析器，经常看到关于Yacc和Antlr的区别的评论（关于LALR和LL）。它总是一些总结性的措辞，例如 "LALR is more powerful"。但是我不明白它的真正含义
所以谁能告诉我这里强大这个词的意思是什么？
我假设它的意思是 "Yacc can do something Antlr can't do"，如果是的话，我希望我能看到关于它的确切示例
LR(1) 但不是 LL(*) 的语言
问题 Language theoretic comparison of LL and LR grammars has an answer 具有以下语言的 LR(1) 但不是 LL(*):
{ a^i b^j | i≥j }
也就是说，一些 a 后跟相等或更少的 b。
this answer to the similar question 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,b 对中相应的 a 个符号，使用 P 的第一个产生式。如果它用完了 b 个符号，它会使用 S 的第一个产生式弹出剩余的 a 个符号。如果它用完了 a 个符号，但还剩下 b 个符号，它会发出错误信号。 （请记住，在这种情况下，我们主要关注 识别 ，因此输出是 "yes" 或 "error"。）
相比之下，这个语法不是LL(*)。直觉上，LL(*) 解析器必须决定，当它看到第一个 a 时，是使用第一个还是第二个 S 的产生式。它想向前看是否还有 b 个符号与剩余的 a 个符号一样多，因为如果没有，那么它就会知道它必须使用第一个产生式来 "burn"多余的 a 个符号。但是 LL(*) lookahead 仅限于识别常规语言，而常规语言无法识别 { a^i b^i } 因为它不能 "count".
当然，一个 grammar 不是 LL(*) 并不意味着 language 不是 LL(* ), 因为可能有更聪明的语法。为了证明它不是 LL(*)，我可能会从 formal definition, assume I had a grammar with those conditions, and then use a pumping lemma 参数开始，以表明它无法正确识别感兴趣的语言。但我会让链接的资源足以作为语言不是 LL(*) 的严格理由。
更高层次的解读
我的想法是，LL 在 "down" 解析树的途中做出决定，而 LR 在 "up" 的途中做出决定。为了创建一种不是 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"很难class去想）；有关详细信息，请参阅第一个链接的问题。
Antlr4 语义谓词
现在题主问的其实是Antlr4。 Antlr4 有 semantic predicates，有效地允许程序员插入任意先行计算。因此，如果您愿意跳出语法形式主义，实际上 Anltr4 解析器可以识别的内容没有限制（缺乏可判定性）。
这是一个示例语法，对于其中的示例，ANTLR 和 YACC 都无法在没有 hackery 的情况下解析：
stmt = declaration ';' ;
stmt = expression ';' ;
declaration = type ID ;
type = ID '*' ;
expression = product ;
product = ID ;
product = product '*' ID ;
这是一个 ANTLR 或 L(AL)R 都无法解析的例子：
x * y ;
使用这个语法。
有两种可能的解析：1) 作为语句，2) 作为声明。
本例取自C语言。 （你可以做一个更小的
语法;我试图以一种易于理解其真实性的形式保留它。
L(ALR) 解析器和 ANTLR 将最多为您提供一个推导。意思是
他们每个人都会错过任何选择。
可以破解解析机制来解决这个问题（正如 GCC 过去所做的那样）
通过引入符号 table 信息。混淆了解析和符号 table
恕我直言，这种结构只会让解析器变得一团糟。特别是，你不能仅仅通过查看语法来决定它接受什么。
问题是 ANTLR 和 L(AL)R 不会解析所有上下文无关语言。
他们只解析（不同的）子集；这意味着一个人可以解析另一个人不能解析的某些实例，反之亦然。这意味着一个并不比另一个更强大。
如果您想要一个更强大的解析器，例如，处理完全上下文无关的语言，您需要查看 Earley 解析器，或 GLR 或 GLL 解析器。 Earley 解析器效率不高。 GLR 和 GLL 往往是语法部分的高效解析器，不会引入歧义（多次解析）或需要大量前瞻。但是您可能想要解析的大多数编程语言结构往往不会造成混淆，因为在这种情况下人们也很难阅读它们。
由于 L(AL)R 和 ANTLR 的限制，我的公司 (Semantic Designs) 对大约 40 种语言使用 GLR 解析器。这包括完整的 C++17，它具有更多模棱两可的解析和超前预测案例，包括上面的示例，其中大多数更加晦涩难懂。据我所知，我们拥有唯一直接使用语法的 C++17 解析器； GCC 和 Clang 使用带有大量纠结符号 table 检查的手工编码递归下降。
[另一个答案的作者 Scott McPeak 确实使用 GLR 为 C++ 的旧方言构建了 C++ 解析器，或多或少与我们开始这样做的同时。向他致敬。]
最近想学习语言解析器，经常看到关于Yacc和Antlr的区别的评论（关于LALR和LL）。它总是一些总结性的措辞，例如 "LALR is more powerful"。但是我不明白它的真正含义
所以谁能告诉我这里强大这个词的意思是什么？
我假设它的意思是 "Yacc can do something Antlr can't do"，如果是的话，我希望我能看到关于它的确切示例
LR(1) 但不是 LL(*) 的语言
问题 Language theoretic comparison of LL and LR grammars has an answer 具有以下语言的 LR(1) 但不是 LL(*):
{ a^i b^j | i≥j }
也就是说，一些 a 后跟相等或更少的 b。
this answer to the similar question 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,b 对中相应的 a 个符号，使用 P 的第一个产生式。如果它用完了 b 个符号，它会使用 S 的第一个产生式弹出剩余的 a 个符号。如果它用完了 a 个符号，但还剩下 b 个符号，它会发出错误信号。 （请记住，在这种情况下，我们主要关注 识别 ，因此输出是 "yes" 或 "error"。）
相比之下，这个语法不是LL(*)。直觉上，LL(*) 解析器必须决定，当它看到第一个 a 时，是使用第一个还是第二个 S 的产生式。它想向前看是否还有 b 个符号与剩余的 a 个符号一样多，因为如果没有，那么它就会知道它必须使用第一个产生式来 "burn"多余的 a 个符号。但是 LL(*) lookahead 仅限于识别常规语言，而常规语言无法识别 { a^i b^i } 因为它不能 "count".
当然，一个 grammar 不是 LL(*) 并不意味着 language 不是 LL(* ), 因为可能有更聪明的语法。为了证明它不是 LL(*)，我可能会从 formal definition, assume I had a grammar with those conditions, and then use a pumping lemma 参数开始，以表明它无法正确识别感兴趣的语言。但我会让链接的资源足以作为语言不是 LL(*) 的严格理由。
更高层次的解读
我的想法是，LL 在 "down" 解析树的途中做出决定，而 LR 在 "up" 的途中做出决定。为了创建一种不是 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"很难class去想）；有关详细信息，请参阅第一个链接的问题。
Antlr4 语义谓词
现在题主问的其实是Antlr4。 Antlr4 有 semantic predicates，有效地允许程序员插入任意先行计算。因此，如果您愿意跳出语法形式主义，实际上 Anltr4 解析器可以识别的内容没有限制（缺乏可判定性）。
这是一个示例语法，对于其中的示例，ANTLR 和 YACC 都无法在没有 hackery 的情况下解析：
stmt = declaration ';' ;
stmt = expression ';' ;
declaration = type ID ;
type = ID '*' ;
expression = product ;
product = ID ;
product = product '*' ID ;
这是一个 ANTLR 或 L(AL)R 都无法解析的例子：
x * y ;
使用这个语法。
有两种可能的解析：1) 作为语句，2) 作为声明。
本例取自C语言。 （你可以做一个更小的 语法;我试图以一种易于理解其真实性的形式保留它。
L(ALR) 解析器和 ANTLR 将最多为您提供一个推导。意思是 他们每个人都会错过任何选择。
可以破解解析机制来解决这个问题（正如 GCC 过去所做的那样） 通过引入符号 table 信息。混淆了解析和符号 table 恕我直言，这种结构只会让解析器变得一团糟。特别是，你不能仅仅通过查看语法来决定它接受什么。
问题是 ANTLR 和 L(AL)R 不会解析所有上下文无关语言。 他们只解析（不同的）子集；这意味着一个人可以解析另一个人不能解析的某些实例，反之亦然。这意味着一个并不比另一个更强大。
如果您想要一个更强大的解析器，例如，处理完全上下文无关的语言，您需要查看 Earley 解析器，或 GLR 或 GLL 解析器。 Earley 解析器效率不高。 GLR 和 GLL 往往是语法部分的高效解析器，不会引入歧义（多次解析）或需要大量前瞻。但是您可能想要解析的大多数编程语言结构往往不会造成混淆，因为在这种情况下人们也很难阅读它们。
由于 L(AL)R 和 ANTLR 的限制，我的公司 (Semantic Designs) 对大约 40 种语言使用 GLR 解析器。这包括完整的 C++17，它具有更多模棱两可的解析和超前预测案例，包括上面的示例，其中大多数更加晦涩难懂。据我所知，我们拥有唯一直接使用语法的 C++17 解析器； GCC 和 Clang 使用带有大量纠结符号 table 检查的手工编码递归下降。
[另一个答案的作者 Scott McPeak 确实使用 GLR 为 C++ 的旧方言构建了 C++ 解析器，或多或少与我们开始这样做的同时。向他致敬。]