时间戳

首页 > 解决方案 > 有没有 Yacc 可以表达但 Antlr4 无法表达的语言语法示例？

compiler-construction - 有没有 Yacc 可以表达但 Antlr4 无法表达的语言语法示例？

问题描述

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

那么有人可以请教我这里强大的词是什么意思吗？

我只是假设它的意思是“Yacc 可以做 Antlr 做不到的事情”，如果我希望我能看到关于它的确切示例

标签： compiler-constructionantlr4yacclllalr

解决方案

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

LL 和 LR 语法的语言理论比较问题有以下语言的答案，即 LR(1) 但不是 LL(*)：

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

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

这个对类似问题的回答引用了相同的语言无法用 LL 表示的 LR 语法示例？. 然而，现在的问题是不同的，因为那个问题是“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，使用第一个产生式 for P。如果符号用完了，它会使用第一个产生式 forb弹出剩余的符号。如果它用完符号而仍然有符号，则表示错误。（请记住，在这种情况下，我们主要关注识别，因此输出要么是“是”，要么是“错误”。）aSab

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

当然，一种语法不是 LL(*) 的事实并不意味着该语言不是 LL(*)，因为可能存在更聪明的语法。为了证明它不是 LL(*)，我可能会从正式定义开始，假设我有一个符合这些条件的语法，然后使用抽引引理参数来表明它无法正确识别感兴趣的语言。但我会让链接资源足以作为语言不是 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(*) 解析器可以跳过“标识符或 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），虽然我不知道它们是什么样子（“不是 LR”是一个很难思考的类）；有关详细信息，请参阅第一个链接问题。

Antlr4 语义谓词

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

推荐阅读