编译原理抽象语法树的构建

‘壹’ 如何用python写一个解释器

大学里计算机科学最吸引我的地方就是编译器。最神奇的是，编译器是如何读出我写的那些烂代码，并且还能生成那么复杂的程序。当我终于选了一门编译方面的课程时，我发现这个过程比我想的要简单得多。
在本系列的文章中，我会试着通过为一种基本命令语言IMP写一个解释器，来展示这种简易性。因为IMP是一个简单广为人知的语言，所以打算用 Python写这个解释器。Python代码看起来很像伪代码，所以即使你不认识 Python，你也能理解它。解析可以通过一套从头开始实现的解析器组合完成（在本系列的下一篇文章中会有解释）。除了sys（用于I/O）、re（用于解析正则表达式）以及unittest（用于确保一切工作正常）库，没有使用其他额外的库。
IMP 语言
在开始写之前，我们先来讨论一下将要解释的语言。IMP是拥有下面结构的最小命令语言：
赋值语句（所有变量都是全局的，而且只能存储整数）：

Python

1

x := 1

条件语句：

Python

1
2
3
4
5

if x = 1 then
y := 2
else
y := 3
end

while循环：

Python

1
2
3

while x < 10 do
x := x + 1
end

复合语句（分号分隔）：

Python

1
2

x := 1;
y := 2

OK，所以它只是一门工具语言，但你可以很容易就把它扩展成比Lua或python更有用的语言。我希望能把这份教程能保持尽量简单。
下面这个例子是计算阶乘的程序：

Python

1
2
3
4
5
6

n := 5;
p := 1;
while n > 0 do
p := p * n;
n := n - 1
end

IMP没有读取输入的方式，所以初始状态必须是在程序最开始写一系列的赋值语句。也没有打印结果的方式，所以解释器必须在程序的结尾打印所有变量的值。
解释器的结构
解释器的核心是“中间表示”（Intermediate representation，IR）。这就是如何在内存中表示IMP程序。因为IMP是一个很简单的语言，中间表示将直接对应于语言的语法；每一种表达和语句都有对应的类。在一种更复杂的语言中，你不仅需要一个“语法表示”，还需要一个更容易分析或运行的“语义表示”。
解释器将会执行三个阶段：
将源码中的字符分割成标记符（token）
将标记符组织成一棵抽象语法树（AST）。抽象语法树就是中间表示。
评估这棵抽象语法树，并在最后打印这棵树的状态
将字符串分割成标记符的过程叫做“词法分析”，通过一个词法分析器完成。关键字是很短，易于理解的字符串，包含程序中最基本的部分，如数字、标识符、关键字和操作符。词法分析器会除去空格和注释，因为它们都会被解释器忽略。

将标记符组织成抽象语法树（AST）的过程称为“解析过程”。解析器将程序的结构提取成一张我们可以评估的表格。

实际执行这个解析过的抽象语法树的过程称为评估。这实际上是这个解析器中最简单的部分了。
本文会把重点放在词法分析器上。我们将编写一个通用的词汇库，然后用它来为IMP创建一个词法分析器。下一篇文章将会重点打造一个语法分析器和评估计算器。
词汇库
词法分析器的操作相当简单。它是基于正则表达式的，所以如果你不熟悉它们，你可能需要读一些资料。简单来说，正则表达式就是一种能描述其他字符串的特殊的格式化的字符串。你可以使用它们去匹配电话号码或是邮箱地址，或者是像我们遇到在这种情况，不同类型的标记符。
词法分析器的输入可能只是一个字符串。简单起见，我们将整个输入文件都读到内存中。输出是一个标记符列表。每个标记符包括一个值（它代表的字符串）和一个标记（表示它是一个什么类型的标记符）。语法分析器会使用这两个数据来决定如何构建一棵抽象语法树。
由于不论何种语言的词法分析器，其操作都大同小异，我们将创建一个通用的词法分析器，包括一个正则表达式列表和对应的标签（tag）。对每一个表达式，它都会检查是否和当前位置的输入文本匹配。如果匹配，匹配文本就会作为一个标记符被提取出来，并且被加上该正则表达式的标签。如果该正则表达式没有标签，那么这段文本将会被丢弃。这样免得我们被诸如注释和空格之类的垃圾字符干扰。如果没有匹配的正则表达式，程序就要报错并终止。这个过程会不断循环直到没有字符可匹配。
下面是一段来自词汇库的代码：

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import sys
import re

def lex(characters, token_exprs):
pos = 0
tokens = []
while pos < len(characters):
match = None
for token_expr in token_exprs:
pattern, tag = token_expr
regex = re.compile(pattern)
match = regex.match(characters, pos)
if match:
text = match.group(0)
if tag:
token = (text, tag)
tokens.append(token)
break
if not match:
sys.stderr.write('Illegal character: %sn' % characters[pos])
sys.exit(1)
else:
pos = match.end(0)
return tokens

注意，我们遍历正则表达式的顺序很重要。lex会遍历所有的表达式，然后接受第一个匹配成功的表达式。这也就意味着，当使用词法分析器时，我们应当首先考虑最具体的表达式（像那些匹配算子（matching operator）和关键词），其次才是比较一般的表达式（像标识符和数字）。
词法分析器
给定上面的lex函数，为IMP定义一个词法分析器就非常简单了。首先我们要做的就是为标记符定义一系列的标签。IMP只需要三个标签。RESERVED表示一个保留字或操作符。INT表示一个文字整数。ID代表标识符。

Python

1
2
3
4
5

import lexer

RESERVED = 'RESERVED'
INT = 'INT'
ID = 'ID'

接下来定义词法分析器将会用到的标记符表达式。前两个表达式匹配空格和注释。它们没有标签，所以 lex 会丢弃它们匹配到的所有字符。

Python

1
2
3

token_exprs = [
(r'[ nt]+', None),
(r'#[^n]*', None),

然后，只剩下所有的操作符和保留字了。记住，每个正则表达式前面的“r”表示这个字符串是“raw”；Python不会处理任何转义字符。这使我们可以在字符串中包含进反斜线，正则表达式正是利用这一点来转义操作符比如“＋”和“＊”。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

(r':=', RESERVED),
(r'(', RESERVED),
(r')', RESERVED),
(r';', RESERVED),
(r'+', RESERVED),
(r'-', RESERVED),
(r'*', RESERVED),
(r'/', RESERVED),
(r'<=', RESERVED),
(r'<', RESERVED),
(r'>=', RESERVED),
(r'>', RESERVED),
(r'=', RESERVED),
(r'!=', RESERVED),
(r'and', RESERVED),
(r'or', RESERVED),
(r'not', RESERVED),
(r'if', RESERVED),
(r'then', RESERVED),
(r'else', RESERVED),
(r'while', RESERVED),
(r'do', RESERVED),
(r'end', RESERVED),

最后，轮到整数和标识符的表达式。要注意的是，标识符的正则表达式会匹配上面的所有的保留字，所以它一定要留到最后。

Python

1
2
3

(r'[0-9]+', INT),
(r'[A-Za-z][A-Za-z0-9_]*', ID),
]

既然正则表达式已经定义好了，我们还需要创建一个实际的lexer函数。

Python

1
2

def imp_lex(characters):
return lexer.lex(characters, token_exprs)

如果你对这部分感兴趣，这里有一些驱动代码可以测试输出：

Python

1
2
3
4
5
6
7
8
9
10
11

import sys
from imp_lexer import *

if __name__ == '__main__':
filename = sys.argv[1]
file = open(filename)
characters = file.read()
file.close()
tokens = imp_lex(characters)
for token in tokens:
print token

继续……

‘贰’ 编译原理简单吗

编译原理主要是讲了编译器的实现。
那什么是编译器呢？
编译器就是将 源程序→编译器 →目标机器代码的程序
本文将用一段最简单的代码进行说明

1 + 2 + 3

第一步. 词法分析
当代码从文件中被读入到编辑器时，将会进行词法分析
示例中的代码最终会转换为(下面为伪代码)

1 ADD 2 ADD 3

第二步. 语法分析
这一步编译器将会把词法分析的结果转换成AST(abstract syntax tree, 抽象语法树)
所有的操作数将会作为子节点，所有的操作符将会作为父节点。(不知道的同学可以看一下树的生成)

1 + 2 + 3 对应的树
3. 生成目标代码
对上面的树进行后序遍历，将会得到下面的伪代码

((1 2 +) 3 +)

生成的汇编伪代码为

START:

MOV VALUE, 0//初始化结果为0

ADD VALUE, 1

ADD VALUE, 2//(1 2 +)的汇编伪代码

ADD VALUE, 3

RET VALUE

END

最终汇编代码会被编译成机器代码，在计算机上执行。
下面为一般情况下的编译流程
1. 词法分析(生成代码对应的token序列，使用正则表达式)
2. 语法分析(生成AST)
3. 语义分析(对代码的语法进行检查)
4. 代码生成(生成可执行的代码)

‘叁’ Ocaml语言编程 AST文件(抽象语法树)定义了 stmt可以是stmt也可以是stmt List 为什么还会报错

您好，这样的：
抽象语法树的结构不依赖于源语言的文法，也就是语法分析阶段所采用的上下文无关文法。因为在Parser工程中，经常会对文法进行等价的转换（消除左递归、回溯、二义性等），这样会给文法引入一些多余的成分，对后续阶段造成不利影响，甚至会使各阶段变得混乱。因此，很多编译器（包括GJC）经常要独立地构造语法分析树，为前、后端建立一个清晰的接口。

‘肆’ 编译原理笔记9：语法分析树、语法树、二义性的消除

语法分析树和语法树不是一种东西 。习惯上，我们把前者叫做“具体语法树”，其能够体现推导的过程；后者叫做“抽象语法树”，其不体现过程，只关心最后的结果。

语法分析树是语言推导过程的图形化表示方法。这种表示方法反映了语言的实质以及语言的推导过程。

定义：对于 CFG G 的句型，分析树被定义为具有下述性质的一棵树：

推导，有最左推导和最右推导，这两种推导方式在推导过程中的分析树可能不同，但因最终得到的句子是相同的，所以最终的分析树是一样的。

分析树能反映句型的推导过程，也能反映句型的结构。然而实际上，我们往往不关心推导的过程，而只关心推导的结果。因此，我们要对 分析树 进行改造，得到 语法树 。语法树中全是终结符，没有非终结符。而且语法树中没有括号

定义：

说白了，语法树这玩意，就一句话： 叶子全是操作数，内部全是操作符 ，树里没有非终结符也不能有括号。

语法树要表达的东西，是操作符（运算）作用于操作数（运算对象）

举俩例子吧：

【例】： -(id+id) 的语法树：

【例】：-id+id 的语法树：

显然，我们从上面这两个语法树中，直接就能观察出来它们的运算顺序。

【例】：句型 if C then s1 else s2

二义性问题：一个句子可能对应多于一棵语法树。

【例】： 设文法 G： E → E+E | E*E | (E) | -E | id

则，句子 id+id*id、id+id+id 可能的分析树有：

在该例中，虽然 id+id+id 的 “+” 的结合性无论左右都不会影响结果。但万一，万一“+”的含义变成了“减法”，那么左结合和右结合就会引起很大的问题了。

我们在这里讲的“二义性”的“义”并非语义——我们现在在学习的内容是“语法分析器”，尚未到需要研究语言背后含义的阶段。

我们现在讲的“二义性”指的是一个句子对应多种分析树。

二义性的体现，是文法对同一句子有不止一棵分析树。这种问题由【句子产生过程中的某些推导有多于一种选择】引起。悬空 else 问题就可以很好地体现这种【超过一种选择】带来的二义性问题，示例如下。

看下面这么个例子。。

（其实，我感觉这个其实比较像是“说话大喘气”带来的理解歧义问题。。。）上面的产生式中并没体现出来该咋算分一块，所以两种完全不同的句子结构都是合法的。

二义性问题是有救的，大概有以下这三种办法：

这些办法的核心，其实都是将优先级和结合性说明白。

核心：把优先级和结合性说明白

既然要说明白，那就不能让一个非终结符可以直接在当次推导中能推出会带来优先级和结合性歧义的东西。（对分析树的一个内部节点，不会有出现在其下面的分支是相同的非终结符的情况。如果有得选，那就有得歧义了。没得选才能确定地一路走到黑）

改写为非二义文法的二义文法大概有下面这几个特点：

改写的关键步骤：

【例】改写下面的二义文法为非二义文法。图右侧是要达成的优先级和结合性

改写的核心其实就两句话：

所以能够得到非终结符与运算的对应关系（因为不同的运算有不同的优先级，我们想要引入多个优先级就要引入多个新的非终结符。这样每个非终结符就可以负责一个优先级的运算符号，也就是说新的非终结符是与运算有关系的了。因此这里搞出来了“对应关系”四个字）如下：

优先级由低到高分别是 +、 、-，而距离开始符号越近，优先级越低。因此在这里的排序也可以+ -顺序。每个符号对应一层的非终结符。根据所需要的结合性，则可确定是左递归还是右递归，以确定新的产生式长什么样子

【例】：规定优先级和结合性，写出改写的非二义文法

我们已经掌握了一种叫做【改写】的工具，能让我们消除二义性。接下来我们就要用这个工具来尝试搞搞悬空 else 问题！

悬空 else 问题出现的原因是 then 数量多于 else，让 else 有多个可以结合的 then。在二义文法中，由于选哪两个 then、else 配对都可以，故会引起出现二义的情况。在这里，我们规定 else 右结合，即与左边最靠近的 then 结合。

为改写此文法，可以将 S 分为完全匹配（MS）和不完全匹配（UMS）两类。在 MS 中体现 then、else 个数相等即匹配且右结合；在UMS 中 then、else 不匹配，体现 else 右结合。

【例】：用改写后的文法写一个条件语句

经过检查，无法再根据文法写出其他分析树，故已经消除了二义性

虽然二义文法会导致二义性，但是其并非一无是处。其有两个显着的优点：

在 Yacc 中，我们可以直接指定优先级、结合性而无需自己重写文法。

left 表示左结合，right 表示右结合。越往下的算符优先级越高。

嗯就这么简单。。。

我们其实可以把语言本身定义成没有优先级和结合性的。。然后所有的优先、结合都交由括号进行控制，哪个先算就加括号。把一个过程的结束用明确的标志标记出来。

比如在 Ada 中：

在 Pascal 中，给表达式加括号：

‘伍’ 抽象语法树的简介

在计算机科学中，抽象语法树（abstract syntax tree或者缩写为AST），或者语法树（syntax tree），是源代码的抽象语法结构的树状表现形式，这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于if-condition-then这样的条件跳转语句，可以使用带有两个分支的节点来表示。
和抽象语法树相对的是具体语法树（concrete syntaxtree），通常称作分析树（parse tree）。一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树。一旦AST被创建出来，在后续的处理过程中，比如语义分析阶段，会添加一些信息。

‘陆’ Java 虚拟机一样的速度甚至出现AOT编译方式吗

不论是物理机还是虚拟机，大部分的程序代码从开始编译到最终转化成物理机的目标代码或虚拟机能执行的指令集之前，都会按照如下图所示的各个步骤进行：

‘柒’ 编译原理问题，高手进。

回答下列问题：(30分)
(6分)对于下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出程序执行的输出结果。
答： (1) 3 (2) 16 (3) 16 (每个值2分)

(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。
G(M)：
M → TB
T → Ba |
B → Db | eT |
D → d |

解答：
计算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， }
FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#}
FOLLOW (B) = {a，# } FOLLOW (D) = { b}

检查文法的所有产生式，我们可以得到：
1. 该文法不含左递归，
2. 该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。
3. 该文法的非终结符T、B和D，它们都有候选式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以该文法不是LL(1)文法。(2分)

(4分)考虑下面的属性文法
产 生 式 语 义 规 则
S→ABC

A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
画出字符串abc的语法树;
对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少。
答：(1) (2分)

(2) S.v的值为18 (2分)

(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？
答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。

(5分)对下列四元式序列生成目标代码：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本块出口之后是活跃变量， R0和R1是可用寄存器。
答: 目标代码序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H

(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。
答：
逆波兰式：(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象语法树：(2分)

(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符串。
答：
(2分)构造相应的正规式：(a|b)*ab(a|b)*

(3分)
a a

a b
b b

(3分)确定化：
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a

a b b
b

最小化：
{0，1，2} {3，4，5}
{0， 2}，1， {3，4，5}

(6分)写一个文法使其语言为L(G)={anbncm| m,n≥1，n为奇数，m为偶数}。
答：
文法G(S):

(8分)对于文法G(S):

1. 写出句型b(Ma)b的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语和句柄。
答：
1. (4分)

2. (4分)
短语: Ma)， (Ma)， b(Ma)b
直接短语: Ma)
句柄: Ma)

(12分)对文法G(S)：
S → a | ^ | (T)
T → T，S | S
(1) 构造各非终结符的FIRSTVT和LASTVT集合;
(2) 构造算符优先表;
(3) 是算符优先文法吗?
(4) 构造优先函数。
答：
(1) (4分)

(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >

(3) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。 (1分)

(4) 优先函数(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3

(8分)设某语言的do-while语句的语法形式为
S do S(1) While E
其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：
(1) 写出适合语法制导翻译的产生式；
(2) 写出每个产生式对应的语义动作。
答：(1). 适合语法制导翻译的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }

UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }

SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }

答案二：
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}

(10分)将语句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻译成四元式。
答：
100 (j>， C， 0， 102)
101 (j， -， -， 112)
102 (jnz， A， -， 106)
103 (j， -， -， 104)
104 (j=， B， 0， 106)
105 (j， -， -， 109)
106 (+， C， D， T1)
107 (:=， T1， -， C)
108 (j， -， -， 100)
109 (*， C， D， T2)
110 (:=， T2， -， C)
111 (j， -， -， 100)
112

(10分)设有基本块如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
画出DAG图；
设L，M，N 是出基本块后的活跃变量，请给出优化后的四元式序列。
答：

1. (6分)
L

*
T2,M T4 T2,N

* - +

T1 T3
3 A B 12 C D

2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D

(8分)文法G(S)及其LR分析表如下，请给出串baba#的分析过程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答：
步骤 状态 符号 输入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈，估计认识！！

‘捌’ 简述利用推导构造语法树的过程

语法树，是针对上下文无关文法，用来表示一个句型的生成过程的一种描述手段。
对于给定的句型，依据文法构造它的语法树，是语法分析的任务。
编译原理课程中重点学习的各种语法分析方法，都是解决语法树的构造的具体分析方法。
在学习并掌握各种语法分析方法之前，一般只能依据直觉印象，通过猜测、拼凑等手段，去试着推演，凑出符合要求的句型的语法树。所以这个阶段练习用的题目一般也不很复杂，通过多多练习也能找到一些技巧（其实主要是后面将要学习的自顶向下语法分析中的一些原则）。
对于给定的文法，有一些句型可能能构建出两棵甚至多棵结构不同的语法树，结果不一定是唯一的。这样的文法就是所谓的二义性文法。
对于非二义性文法而言，任意一个句型的语法树都是唯一的。

‘玖’ 符号表和抽象语法树是什么关系两者在编译器设计中是否必需

一般的编译器可能包含下面这些模块:

1, 词法分析器:
输入: 源代码
输出: token
2, 语法分析器:
输入: token
输出: AST
在这个过程中, 可以识别出不符合语法规则的语句, 就可以报syntax错误, 如果有syntax错误, 编译结束
3, 语义分析器:
输入: AST
输出: 无
在这个过程中, 根据语言的语义规则来识别语义错误, 要识别语义错误 就必须编译AST, 因为是树的遍历, 假如你先遍历到了int a 这个节点, 接着又遍历到了一个表达式a = 4这个节点, 你需要检查变量a有没有声明啊, 变量a和4的类型批不匹配呢? 这时你如果没有保存变量a的信息, 那么你怎么检查? 所以就需要符号表来保存这些信息了.
4, 代码优化:
最简单的就是常量折叠优化了, 比如: a = 1 + 2 这个语句可以直接换成: a = 3了, 也就是说在编译阶段就把一些必要的运算先计算完成, 在程序运行的时候就不需要计算这些了, 就提高了程序的运行效率. 这部分是最复杂的了, 还有各种各样各样的优化
5, 代码生成:
输入: AST
输出: 可以是虚拟机代码, 可以是本地汇编代码