从零写一个编译器(完结):总结和系列索引

前言

这个系列算作我自己的学习笔记,到现在已经有十三篇了,加上这篇一共十四篇。一步一步的从词法分析到语法分析、语义分析,再到代码生成,准备在这一篇做一个总结收尾和一个这个系列以前文章的索引。

(另外,由于我现在的这个主题不能对markdown的一级标题作目录,所以这个系列文章的目录都是有问题的)

索引

从零写一个编译器(一):输入系统和词法分析

从零写一个编译器(二):语法分析之前置知识

从零写一个编译器(三):语法分析之几个基础数据结构

从零写一个编译器(四):语法分析之构造有限状态自动机

从零写一个编译器(五):语法分析之自动机的缺陷和改进

从零写一个编译器(六):语法分析之表驱动语法分析

从零写一个编译器(七):语义分析之符号表的数据结构

从零写一个编译器(八):语义分析之构造符号表

从零写一个编译器(九):语义分析之构造抽象语法树(AST)

从零写一个编译器(十):编译前传之直接解释执行

从零写一个编译器(十一):代码生成之Java字节码基础

从零写一个编译器(十二):代码生成之生成逻辑

从零写一个编译器(十三):代码生成之遍历AST

示例

对于C语言的一个快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void quicksort(int A[10], int p, int r) {
int x;
int i;
i = p - 1;
int j;
int t;
int v;
v = r - 1;
if (p < r) {
x = A[r];
for (j = p; j <= v; j++) {
if (A[j] <= x) {
i++;
t = A[i];
A[i] = A[j];
A[j] = t;
}
}
v = i + 1;
t = A[v];
A[v] = A[r];
A[r] = t;
t = v - 1;
quicksort(A, p, t);
t = v + 1;
quicksort(A, t, r);
}
}

void main () {
int a[10];
int i;
int t;
printf("before quick sort:");
for(i = 0; i < 10; i++) {
t = (10 - i);
a[i] = t;
printf("value of a[%d] is %d", i, a[i]);
}
quicksort(a, 0, 9);
printf("after quick sort:");
for (i = 0; i < 10; i++) {
printf("value of a[%d] is %d", i, a[i]);
}
}

解释执行

就直接在控制台输出

代码生成

会在当前目录生成一个C2Bytecode.j字节码文件,再经过字节码的汇编器就可以在JVM上运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
.class public C2Bytecode
.super java/lang/Object

.method public static main([Ljava/lang/String;)V
sipush 10
newarray int
astore 0
sipush 0
istore 2
sipush 0
istore 1
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "before quick sort:"
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "
"
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
sipush 0
istore 2

loop0:
iload 2
sipush 10
if_icmpge branch0
sipush 10
iload 2
isub
istore 1
aload 0
iload 2
iload 1
iastore
aload 0
iload 2
iaload
istore 3
iload 2
istore 4
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "value of a["
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
getstatic java/lang/System/out Ljava/io/PrintStream;
iload 4
invokevirtual java/io/PrintStream/print(I)V
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "] is "
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
getstatic java/lang/System/out Ljava/io/PrintStream;
iload 3
invokevirtual java/io/PrintStream/print(I)V
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "
"
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
iload 2
sipush 1
iadd
istore 2
goto loop0
branch0:
aload 0
sipush 0
sipush 9
invokestatic C2Bytecode/quicksort([III)V
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "after quick sort:"
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "
"
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
sipush 0
istore 2

loop2:
iload 2
sipush 10
if_icmpge branch4
aload 0
iload 2
iaload
istore 3
iload 2
istore 4
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "value of a["
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
getstatic java/lang/System/out Ljava/io/PrintStream;
iload 4
invokevirtual java/io/PrintStream/print(I)V
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "] is "
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
getstatic java/lang/System/out Ljava/io/PrintStream;
iload 3
invokevirtual java/io/PrintStream/print(I)V
getstatic java/lang/System/out Ljava/io/PrintStream;
ldc "
"
invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
iload 2
sipush 1
iadd
istore 2
goto loop2
branch4:
return
.end method
.method public static quicksort([III)V
sipush 0
istore 5
sipush 0
istore 6
iload 1
sipush 1
isub
istore 6
sipush 0
istore 7
sipush 0
istore 3
sipush 0
istore 4
iload 2
sipush 1
isub
istore 4
iload 1
iload 2
if_icmpge branch1

aload 0
iload 2
iaload
istore 5
iload 1
istore 7

loop1:

iload 7
iload 4
if_icmpgt ibranch1

aload 0
iload 7
iaload
iload 5
if_icmpgt ibranch2

iload 6
sipush 1
iadd
istore 6
aload 0
iload 6
iaload
istore 3
aload 0
iload 6
aload 0
iload 7
iaload
iastore
aload 0
iload 7
iload 3
iastore
ibranch2:

iload 7
sipush 1
iadd
istore 7
goto loop1

ibranch1:

iload 6
sipush 1
iadd
istore 4
aload 0
iload 4
iaload
istore 3
aload 0
iload 4
aload 0
iload 2
iaload
iastore
aload 0
iload 2
iload 3
iastore
iload 4
sipush 1
isub
istore 3
aload 0
iload 1
iload 3
invokestatic C2Bytecode/quicksort([III)V
iload 4
sipush 1
iadd
istore 3
aload 0
iload 3
iload 2
invokestatic C2Bytecode/quicksort([III)V
branch1:

return
.end method

.end class

总结

  • 词法分析

一般用有限状态自动机或者手工编写来实现,这一步输出的是token序列

  • 语法分析

主要分为自顶向下和自底向上的语法分析,一般有递归下降,LL(1),LR(1),LALR(1)几种方法实现。这一步输出的是语法树

  • 语义分析

语义分析主要任务是生成符号表,并且发现不符合语义的语句,这一步输出的还是AST

  • 代码生成

这里一般会生成一个与平台无关的较为贴近底层的中间语言(IR),这一步输入AST,输出的是IR

这个编译过程在第一篇的时候就有提起,现在主要想总结的是解释执行和代码生成部分,也就是遍历AST的过程

  • 首先抽象语法树AST的构造就像是把所有代码分割成一块一块,但是其中块和块之间又有逻辑关系,然后把它们组成一棵树

  • 正是有这颗树我们才得以对代码进行逻辑的解释,从叶子节点开始,再存储处理后的信息,传递至父节点

  • 比如对于a = 0节点,我们先递归至子节点,求出a和0的值并且保存在自己的节点,而父节点a = 0就可以利用子节点的信息来对a赋值,比如如果是生成代码的话,a = 0这个节点的操作可能就是找到这个存储这个变量的寄存器,然后生成对这个寄存器赋值的指令

  • 在这个过程有一个非常重要的数据结构,即符号表,无论是直接解释执行还是代码生成都会用到。它的主要用来标识和存储源代码的变量、函数等。在符号表中,源程序中的每个标识符都和它的声明或使用信息绑定在一起,比如其数据类型、作用域以及内存地址。

  • 一个玩具型编译器的主体思路是很明确的,但是在实际实现当中需要考虑的细节也很多,所以才让实现过于繁琐