前言
這個系列算作我自己的學習筆記，到現在已經有十三篇了，加上這篇一共十四篇。一步一步的從詞法分析到文法分析、語義分析，再到代碼生成，準備在這一篇做一個總結收尾和一個這個系列以前文章的索引。
（另外，由于我現在的這個主題不能對markdown的一級标題作目錄，是以這個系列文章的目錄都是有問題的）
索引
從零寫一個編譯器（一）：輸入系統和詞法分析
從零寫一個編譯器（二）：文法分析之前置知識
從零寫一個編譯器（三）：文法分析之幾個基礎資料結構
從零寫一個編譯器（四）：文法分析之構造有限狀态自動機
從零寫一個編譯器（五）：文法分析之自動機的缺陷和改進
從零寫一個編譯器（六）：文法分析之表驅動文法分析
從零寫一個編譯器（七）：語義分析之符号表的資料結構
從零寫一個編譯器（八）：語義分析之構造符号表
從零寫一個編譯器（九）：語義分析之構造抽象文法樹(AST)
從零寫一個編譯器（十）：編譯前傳之直接解釋執行
從零寫一個編譯器（十一）：代碼生成之Java位元組碼基礎
從零寫一個編譯器（十二）：代碼生成之生成邏輯
從零寫一個編譯器（十三）：代碼生成之周遊AST
示例
對于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這個節點的操作可能就是找到這個存儲這個變量的寄存器，然後生成對這個寄存器指派的指令
- 在這個過程有一個非常重要的資料結構，即符号表，無論是直接解釋執行還是代碼生成都會用到。它的主要用來辨別和存儲源代碼的變量、函數等。在符号表中，源程式中的每個辨別符都和它的聲明或使用資訊綁定在一起，比如其資料類型、作用域以及記憶體位址。
- 一個玩具型編譯器的主體思路是很明确的，但是在實際實作當中需要考慮的細節也很多，是以才讓實作過于繁瑣