language-agnostic - 什么是抽象语法树/是否需要？

Question

一直以来，我一直对编译器/解释器设计/实现感兴趣(仅5年)，而且似乎总是幕后的“魔力”，没有人真正谈论(我至少知道) 2个用于操作系统开发的论坛，但我不知道有任何社区进行编译器/解释器/语言开发。无论如何，最近我决定开始自己工作，以期扩大我对编程的整体了解(嘿，这很有趣:)。因此，基于我和Wikipedia有限的阅读 Material ，我为编译器/解释器开发了组件的这一概念:

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

(我知道代码生成和可执行代码还有更多，但是我还没走那么远:)

有了这些知识，我就创建了一个非常基本的词法分析器(使用Java)，以从源文件中获取输入，并将 token 输出到另一个文件中。输入/输出示例如下所示:

输入:

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之前。

您得到的是一个词法分析器。它给您的都是单独的 token 。无论如何，您都将需要一个实际的解析器，因为使用常规语言进行编程不会带来任何乐趣。您甚至不能(适本地)嵌套表达式。哎呀，您甚至无法处理运算符优先级。 token 流不会给您:

一个想法，其中语句和表达式开始和结束。

一个想法，如何将语句分组为块。

一个想法，表达式的哪个部分具有哪个优先级，关联性等。

对程序的实际结构的清晰，整洁的 View 。

一种结构，可以通过无数次转换来传递，而无需每一次传递都知道并且没有代码来表示if中的条件用括号括起来。

...更一般而言，是对单个 token 级别以上的任何理解。

假设您在编译器中有两次遍历，它们优化了将某些类型的运算符应用于某些自变量(例如，常量折叠和 x - x -> 0之类的代数简化)。如果您将它们传递给表达式 x - x * 1的 token ，则弄清楚 x * 1部分排在第一位，这些过程会很困惑。他们必须知道，以免转换不正确(请考虑 1 + 2 * 3)。

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

解析器将所有内容解析出来，并构建一个AST，从而保存所有这些信息。在节点上没有任何其他数据的情况下，仅AST的形状就无法为您提供任何帮助。免费提供1、2、3等更多功能。随之而来的无数通行证都不必再为此担心了。

这并不是说您必须始终拥有AST。对于足够简单的语言，可以执行单遍编译器。无需在解析过程中生成AST或其他中间表示形式，而是在运行时发出代码。但是，对于不太简单的语言，这将变得更加困难，并且您无法合理地做很多事情(例如所有优化和诊断的70％，是的，我只是增加了这个数目)。通常，我不建议您这样做。有充分的理由说明单遍编译器大多已失效。如今，即使是允许使用它们的语言(例如C语言)也可以通过多次传递和AST来实现。这是上手的简单方法，但以后会严重限制您(以及您的语言，如果您设计的话)。