從零寫一個(gè)編譯器（完結(jié)）：總結(jié)和系列索引

前言


這個(gè)系列算作我自己的學(xué)習(xí)筆記，到現(xiàn)在已經(jīng)有十三篇了，加上這篇一共十四篇。一步一步的從詞法分析到語法分析、語義分析，再到代碼生成，準(zhǔn)備在這一篇做一個(gè)總結(jié)收尾和一個(gè)這個(gè)系列以前文章的索引。

（另外，由于我現(xiàn)在的這個(gè)主題不能對markdown的一級標(biāo)題作目錄，所以這個(gè)系列文章的目錄都是有問題的）

索引

從零寫一個(gè)編譯器（一）：輸入系統(tǒng)和詞法分析 <https://www.cnblogs.com/secoding/p/11367511.html>

從零寫一個(gè)編譯器（二）：語法分析之前置知識(shí) <https://www.cnblogs.com/secoding/p/11367521.html>

從零寫一個(gè)編譯器（三）：語法分析之幾個(gè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu) <https://www.cnblogs.com/secoding/p/11367530.html>

從零寫一個(gè)編譯器（四）：語法分析之構(gòu)造有限狀態(tài)自動(dòng)機(jī) <https://www.cnblogs.com/secoding/p/11367533.html>

從零寫一個(gè)編譯器（五）：語法分析之自動(dòng)機(jī)的缺陷和改進(jìn) <https://www.cnblogs.com/secoding/p/11369177.html>

從零寫一個(gè)編譯器（六）：語法分析之表驅(qū)動(dòng)語法分析 <https://www.cnblogs.com/secoding/p/11371502.html>

從零寫一個(gè)編譯器（七）：語義分析之符號表的數(shù)據(jù)結(jié)構(gòu) <https://www.cnblogs.com/secoding/p/11373929.html>

從零寫一個(gè)編譯器（八）：語義分析之構(gòu)造符號表 <https://www.cnblogs.com/secoding/p/11375710.html>

從零寫一個(gè)編譯器（九）：語義分析之構(gòu)造抽象語法樹(AST)
<https://www.cnblogs.com/secoding/p/11379216.html>

從零寫一個(gè)編譯器（十）：編譯前傳之直接解釋執(zhí)行 <https://www.cnblogs.com/secoding/p/11382017.html>

從零寫一個(gè)編譯器（十一）：代碼生成之Java字節(jié)碼基礎(chǔ) <https://www.cnblogs.com/secoding/p/11384619.html>

從零寫一個(gè)編譯器（十二）：代碼生成之生成邏輯 <https://www.cnblogs.com/secoding/p/11388347.html>

從零寫一個(gè)編譯器（十三）：代碼生成之遍歷AST <https://www.cnblogs.com/secoding/p/11391239.html>

示例

對于C語言的一個(gè)快速排序
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]); } }
解釋執(zhí)行

就直接在控制臺(tái)輸出



代碼生成

會(huì)在當(dāng)前目錄生成一個(gè)C2Bytecode.j字節(jié)碼文件，再經(jīng)過字節(jié)碼的匯編器就可以在JVM上運(yùn)行
.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
總結(jié)

* 詞法分析
一般用有限狀態(tài)自動(dòng)機(jī)或者手工編寫來實(shí)現(xiàn)，這一步輸出的是token序列

* 語法分析
主要分為自頂向下和自底向上的語法分析，一般有遞歸下降，LL(1),LR(1),LALR(1)幾種方法實(shí)現(xiàn)。這一步輸出的是語法樹

* 語義分析
語義分析主要任務(wù)是生成符號表，并且發(fā)現(xiàn)不符合語義的語句，這一步輸出的還是AST

* 代碼生成
這里一般會(huì)生成一個(gè)與平臺(tái)無關(guān)的較為貼近底層的中間語言（IR），這一步輸入AST，輸出的是IR

這個(gè)編譯過程在第一篇的時(shí)候就有提起，現(xiàn)在主要想總結(jié)的是解釋執(zhí)行和代碼生成部分，也就是遍歷AST的過程

*
首先抽象語法樹AST的構(gòu)造就像是把所有代碼分割成一塊一塊，但是其中塊和塊之間又有邏輯關(guān)系，然后把它們組成一棵樹

*
正是有這顆樹我們才得以對代碼進(jìn)行邏輯的解釋，從葉子節(jié)點(diǎn)開始，再存儲(chǔ)處理后的信息，傳遞至父節(jié)點(diǎn)



*
比如對于a = 0節(jié)點(diǎn)，我們先遞歸至子節(jié)點(diǎn)，求出a和0的值并且保存在自己的節(jié)點(diǎn)，而父節(jié)點(diǎn)a =
0就可以利用子節(jié)點(diǎn)的信息來對a賦值，比如如果是生成代碼的話，a = 0這個(gè)節(jié)點(diǎn)的操作可能就是找到這個(gè)存儲(chǔ)這個(gè)變量的寄存器，然后生成對這個(gè)寄存器賦值的指令

*

在這個(gè)過程有一個(gè)非常重要的數(shù)據(jù)結(jié)構(gòu)，即符號表，無論是直接解釋執(zhí)行還是代碼生成都會(huì)用到。它的主要用來標(biāo)識(shí)和存儲(chǔ)源代碼的變量、函數(shù)等。在符號表中，源程序中的每個(gè)標(biāo)識(shí)符都和它的聲明或使用信息綁定在一起，比如其數(shù)據(jù)類型、作用域以及內(nèi)存地址。

*
一個(gè)玩具型編譯器的主體思路是很明確的，但是在實(shí)際實(shí)現(xiàn)當(dāng)中需要考慮的細(xì)節(jié)也很多，所以才讓實(shí)現(xiàn)過于繁瑣

• ? 上一篇：.net測試篇之測試神器Autofixture在幾個(gè)復(fù)雜場景下的使用示例以及與Moq結(jié)合
• ? 下一篇：記一道字節(jié)跳動(dòng)的算法面試題