8

只要我一直在编程（现在只有 5 年），我就一直对编译器/解释器的设计/实现感兴趣，而且它总是看起来像没有人真正谈论的幕后“魔法”（我至少知道2 个操作系统开发论坛，但我不知道有任何编译器/解释器/语言开发社区）。无论如何，最近我决定开始自己工作，希望能扩展我对整个编程的了解（嘿，这很有趣:)。因此，基于我拥有的有限阅读材料和维基百科，我为编译器/解释器开发了这个组件概念：

源代码 -> 词法分析 -> 抽象语法树 -> 句法分析 -> 语义分析 -> 代码生成 -> 可执行代码。

（我知道代码生成和可执行代码还有更多内容，但我还没有做到这一点：）

有了这些知识，我创建了一个非常基本的词法分析器（在 Java 中）来从源文件中获取输入，并将标记输出到另一个文件中。示例输入/输出如下所示：

输入：

int a := 2
if(a = 3) then
    print "Yay!"
endif

输出（来自词法分析器）：

INTEGER
A
ASSIGN
2
IF
L_PAR
A
COMP
3
R_PAR
THEN
PRINT
YAY!
ENDIF

就个人而言，我认为从那里开始进行句法/语义分析，甚至可能是代码生成真的很容易，这让我产生疑问：为什么要使用 AST，而我的词法分析器似乎做得同样好？然而，我用来研究这个主题的 100% 的资源似乎都坚持认为这是任何编译器/解释器的必要部分。我是否错过了 AST 的真正含义（显示程序逻辑流程的树）？

TL;DR：目前正在开发编译器，完成词法分析器，在我看来，输出将有助于轻松进行句法分析/语义分析，而不是进行 AST。那么为什么要使用一个呢？我错过了一个点吗？

谢谢！

4

2 回答 2

17

首先，关于您的组件列表的一件事是没有意义的。构建 AST是（几乎）句法分析，所以它不应该在那里，或者至少在AST 之前。

你得到的是一个词法分析器。它给你的只是个人代币。在任何情况下，您都需要一个实际的解析器，因为使用常规语言进行编程没有任何乐趣。您甚至不能（正确地）嵌套表达式。哎呀，您甚至无法处理运算符优先级。令牌流不会给您：

  1. 语句和表达式开始和结束的想法。
  2. 一个想法如何将语句分组到块中。
  3. 一个想法 表达式的哪个部分具有哪个优先级、关联性等。
  4. 对程序的实际结构有清晰、整洁的视图。
  5. 一种可以通过无数次转换的结构，而无需每一次通过都知道并且有代码来适应an 中的条件if被括号括起来。
  6. ...更一般地说，任何一种高于单个令牌水平的理解。

假设您在编译器中有两次优化某些类型的运算符适用于某些参数（例如，常量折叠和代数简化，如x - x -> 0）。如果您将表达式的标记交给他们x - x * 1，这些通道就会变得杂乱无章，因为要弄清楚x * 1零件首先出现。他们必须知道这一点，以免转换不正确（考虑1 + 2 * 3）。

这些事情很棘手，无法按原样正确处理，因此您也不想被解析问题所困扰。这就是您首先在单独的解析步骤中解决解析问题的原因。然后，您可以使用其定义替换函数调用，而不必担心添加括号，因此含义保持不变。您可以节省时间、分离关注点、避免重复、在许多其他地方启用更简单的代码等。

解析器计算出所有这些，并构建一个 AST，从而保存所有这些信息。如果没有关于节点的任何进一步数据，仅 AST 的形状就不会给您任何帮助。1、2、3 等等，免费。接下来的无数次通行证都不必再担心它了。

这并不是说您总是必须拥有 AST。对于足够简单的语言，您可以使用单遍编译器。您无需在解析期间生成 AST 或其他中间表示，而是在执行过程中发出代码。但是，对于不太简单的语言，这变得更加困难，并且您无法合理地做很多事情（例如所有优化和诊断的 70% ——是的，我刚刚做了这个数字）。一般来说，我不建议你这样做。单遍编译器大多已死，这是有充分理由的。即使是允许它们的语言（例如 C）现在也可以通过多次传递和 AST 来实现。这是一种简单的入门方式，但以后会严重限制您（以及语言，如果您设计的话）。

于 2012-08-10T02:13:58.417 回答
9

您在流程图中的错误位置获得了 AST。通常，词法分析器的输出是一系列标记（就像您在输出中一样），这些标记被馈送到生成 AST 的解析器/句法分析器。因此，您的词法分析器的输出与 AST 不同，因为它们在编译过程中的不同点使用并实现不同的目的。

下一个合乎逻辑的问题是：那么，什么是 AST？好吧，解析/句法分析的目的是将词法分析器生成的一系列标记转换为 AST（或解析树）。AST 是一种中间表示，它以更易于以编程方式使用的方式捕获语法元素之间的关系。对此的一种思考方式是，文本程序是一维结构，只能将想法表示为一系列元素，而 AST 则不受此约束，可以在二维中表示这些元素之间的潜在关系（如通常绘制的那样），或任何更高维度的空间，如果您选择以这种方式考虑的话。

例如，二元运算符有两个操作数，我们称它们为 A 和 B。在代码中，这可能拼写为“A * B”（假设是中缀运算符 - AST 的另一个优点是隐藏在语法上可能很重要的区别，但不是语义上的），但要让编译器“理解”这个表达式，它必须顺序读取 5 个字符，而且这个逻辑很快就会变得很麻烦，即使是一种小语言也有很多可能性。然而，在 AST 表示中，我们有一个“二元运算符”节点，其值为“*”，该节点有两个子节点，值“A”和“B”。

随着您的编译器项目的进展，我想您将开始看到这种表示的优势。

于 2012-08-10T02:30:19.440 回答