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 回答