前言


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

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

索引

从零写一个编译器(一):输入系统和词法分析 <https://www.cnblogs.com/secoding/p/11367511.html>

从零写一个编译器(二):语法分析之前置知识 <https://www.cnblogs.com/secoding/p/11367521.html>

从零写一个编译器(三):语法分析之几个基础数据结构 <https://www.cnblogs.com/secoding/p/11367530.html>

从零写一个编译器(四):语法分析之构造有限状态自动机 <https://www.cnblogs.com/secoding/p/11367533.html>

从零写一个编译器(五):语法分析之自动机的缺陷和改进 <https://www.cnblogs.com/secoding/p/11369177.html>

从零写一个编译器(六):语法分析之表驱动语法分析 <https://www.cnblogs.com/secoding/p/11371502.html>

从零写一个编译器(七):语义分析之符号表的数据结构 <https://www.cnblogs.com/secoding/p/11373929.html>

从零写一个编译器(八):语义分析之构造符号表 <https://www.cnblogs.com/secoding/p/11375710.html>

从零写一个编译器(九):语义分析之构造抽象语法树(AST)
<https://www.cnblogs.com/secoding/p/11379216.html>

从零写一个编译器(十):编译前传之直接解释执行 <https://www.cnblogs.com/secoding/p/11382017.html>

从零写一个编译器(十一):代码生成之Java字节码基础 <https://www.cnblogs.com/secoding/p/11384619.html>

从零写一个编译器(十二):代码生成之生成逻辑 <https://www.cnblogs.com/secoding/p/11388347.html>

从零写一个编译器(十三):代码生成之遍历AST <https://www.cnblogs.com/secoding/p/11391239.html>

示例

对于C语言的一个快速排序
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上运行
.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这个节点的操作可能就是找到这个存储这个变量的寄存器,然后生成对这个寄存器赋值的指令

*

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

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