我正在为 ANTLR 中的一小部分 C 语言编写一个词法分析器/解析器，它将在 Java 环境中运行。我是语言语法领域的新手，在许多 ANTLR 教程中，他们创建了一个 AST - 抽象语法树，我是否被迫创建一个，为什么？
Yoely
问问题
6915 次
3 回答
3
我在创建 ANTLR 的 Terence Parr 在 jGuru 上找到了这个问题的答案。我从这里链接的网站复制了这个解释：
只有简单的、所谓的语法导向翻译可以通过解析器中的操作来完成。这些类型的翻译只能吐出结构，这些结构是在解析中已经看到的信息的函数。树解析器允许您遍历中间形式并操作该树，在几个翻译阶段逐渐将其变形为最终形式，可以轻松地打印回新的翻译。
想象一个简单的翻译问题，您想打印一个标题为“有 n 个项目”的 html 页面，其中 n 是您在输入流中找到的标识符的数量。ids 必须打印在标题之后，如下所示：
<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>
从输入
Dog
Cat
Velociraptor
那么，通过语法中的简单操作，如何计算标题？你不能不阅读整个输入。好的，现在我们知道我们需要一个中间形式。最好的通常是我发现的 AST，因为它记录了输入结构。在这种情况下，它只是一个列表，但它证明了我的观点。
好的，现在您知道除了简单的翻译之外，树对于任何事情都是一件好事。给定一个 AST，你如何从中获得输出？想象一下简单的表达式树。一种方法是使树中的节点成为特定类，如 PlusNode、IntegerNode 等。然后你只需要求每个节点打印出来。对于输入，3+4 你会有树：
+ | 3 -- 4
和班级
class PlusNode extends CommonAST {
public String toString() {
AST left = getFirstChild();
AST right = left.getNextSibling();
return left + " + " + right;
}
}
class IntNode extends CommonAST {
public String toString() {
return getText();
}
}
给定一个表达式树，您可以使用 t.toString() 将其转换回文本。那么，这有什么问题？似乎工作得很好，对吧？它似乎在这种情况下运行良好，因为它很简单，但我认为，即使对于这个简单的示例，树语法也更具可读性，并且是对您在 PlusNode.toString() 中编码的内容的形式化描述。
expr returns [String r]
{
String left=null, right=null;
}
: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT {r=i.getText();}
;
请注意，特定类（“异构 AST”）方法实际上在 toString() 中手动为 #(+ INT INT) 编码了一个完整的递归下降解析器。作为解析器生成器的人，这应该让你畏缩。;)
异构 AST 方法的主要缺点是它不能方便地访问上下文信息。在递归下降解析器中，您的上下文很容易访问，因为它可以作为参数传入。通过查看语法，您还可以准确地知道哪个规则可以调用哪个其他规则（例如，这个表达式是 WHILE 条件还是 IF 条件？）。上面的 PlusNode 类存在于一个分离的、孤立的世界中，它不知道谁会调用它的 toString() 方法。更糟糕的是，程序员无法通过读取它来判断它将在哪个上下文中被调用。
总之，向输入解析器添加操作适用于非常简单的翻译，其中：
- 输出结构的顺序与输入顺序相同
- 所有构造都可以从解析到需要吐出它们的信息中生成
除此之外，您还需要一个中间形式——AST 通常是最好的形式。使用语法来描述 AST 的结构类似于使用语法来解析输入文本。像 ANTLR 这样的领域特定高级语言的形式化描述比手动编码的解析器更好。树语法中的动作具有非常清晰的上下文，并且可以方便地访问从调用规则传递的信息。使用树语法来操作树进行多遍翻译的翻译也更容易。
于 2009-03-30T18:02:15.300 回答