什么是抽象语法树/它需要吗？

Question

我一直对编程/解释器设计/实现感兴趣,只要我编程(现在只有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.那为什么要用一个？我错过了一点吗？

谢谢!

Answer 1

首先,关于组件列表的一件事没有意义.构建AST 是(几乎)句法分析,所以要么不应该在那里,或至少来到之前的AST.

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

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

假设您的编译器中有两个通道,它们优化某些类型的运算符适用于某些参数(例如,常量折叠和代数简化等x - x -> 0).如果你把它们的标记交给表达式x - x * 1,那么这些过程就会变得杂乱无章,并发现该x * 1部分是第一位的.他们必须知道,以免转变是不正确的(考虑1 + 2 * 3).

这些东西很难实现,因此你也不希望通过解析问题来解决问题.这就是您在单独的解析步骤中首先解决解析问题的原因.然后,您可以使用其定义替换函数调用,而不必担心添加括号,因此含义保持不变.您可以节省时间,分散顾虑,避免重复,在许多其他地方启用更简单的代码等.

解析器将所有这些都计算出来,然后构建一个AST,从而保存所有信息.在节点上没有任何进一步的数据,AST的形状单独给你没有.1,2,3等等,免费.无下面的bazillion通行证必须再担心它.

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

Answer 2

您的流程图中的AST处于错误的位置.通常,词法分析器的输出是一系列标记(如输出中所示),并将这些标记输入解析器/语法分析器,生成AST.因此,词法分析器的输出与AST不同,因为它们在编译过程中的不同点使用并满足不同的目的.

接下来的逻辑问题是:什么是AST？好吧,解析/句法分析的目的是将词法分析器生成的一系列标记转换为AST(或解析树).AST是一种中间表示,以一种易于以编程方式工作的方式捕获语法元素之间的关系.考虑这一点的一种方式是文本程序是一维构造,并且只能将构思表示为元素序列,而AST从这个约束中解放出来,并且可以表示这些元素之间的二维关系(通常绘制的),或任何更高维度的空间,如果您选择以这种方式思考它.

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

随着编译器项目的进展,我认为您将开始看到这种表示的优势.