一、作案動機
由于這學期有一門《編譯原理》的課程，感覺如果不寫一個編譯器對不起這門課，是以我便動手了。但是考慮到我的時間有限和做一個編譯器的難度，于是我給自己的時間是2周，太多有點浪費，太少挑戰又有點大，2周剛好。
二、被捕感言
2周已經過去了，我也實作了一個編譯器。我感覺寫一個編譯器最大的挑戰在于如何起步，也就是說一個小白如何快速的搭建出一個編譯器的整個流程。我所說的這個流程是大概的架構而不是完全知道細節，細節隻有在慢慢實作時才可以慢慢完善。架構包括什麼内容呢？包括：你設計的語言的文法是什麼(我的語言叫Cf語言，和C語言類似)？有哪些關鍵字？有哪些資料結構？有多少功能(比如函數調用、類、結構體等等)？文法分析用什麼(比如LL1、LR1等等)？大概需要哪些資料結構(比如變量表、函數表)？編譯的目标代碼是什麼（彙編還是機器指令）？中間代碼用什麼？（四元式、樹等等）大概就這些吧。
就是這些家夥花了我4天，開始的4天我主要檢視不同的書籍去弄出整體架構。最好不要隻看課本，因為不好找到總體方向。不要以為看個目錄就算知道整體流程，我們的目标是：幹出一個編譯器而不是考個試。我主要看了2本書：課本《編譯原理教程(第四版)》胡元義寫、《編譯器設計之路》裘巍。我的資料結構的設計主要參考第二本書，但是我隻看他的資料結構設計而不看他的代碼，因為我看了頭有點暈(((φ(◎ロ◎;)φ)))。弄出架構以後的日子，我依次實作了詞法分析器、文法分析器、在文法分析的過程中加上語義程式得到中間代碼、把中間代碼轉成彙編。可能有人發現了我沒加優化，确實我沒有加上優化，原因很簡單：降低難度。其實我是想過加上優化的，但是我扳了扳手指發現時間不夠于是放棄了，可能我會在課程設計時加上優化的。補充說明:純手工，不用lex等工具。
三、作案過程
首先最重要的，我要介紹一下我的Cf語言的結構：
- 資料結構：int整型、int[]整型數組、string字元串和string[]字元串數組。
補充說明：我的int必須>=0，占16位。
- 控制結構：if語句和while語句。
補充說明：我的if隻有if沒有else，但是不影響功能因為if else 可以用2個if實作隻是傻了點。
- 關鍵字：int string def printf if while
補充說明：def 用于函數定義 printf是我的内置函數便于列印結果
總體的代碼結構：
資料定義(就像這樣)
int a;
int b[5];
string c;
string d[6];
函數申明(就像這樣)
def gogo(){
a=3;
b[2]=3;
b[a]=a;
b[3]=a;
b[a]=4;
c="Test";
d[a]=c;
d[5]="TEST2";
d[a]="TEST1";
d[0]="HELLO";
d[a]=d[0];
}
def cfmain(){
gogo();
printf("TEST",1);
}
補充說明：我的語言的入口函數叫cfmain不能少。整個代碼必須按照上面的結構，即先定義變量，這些變量就是全局變量，我這裡沒有局部變量。在函數裡面申明不了變量的，要用的變量都放開頭，申明中不能指派。然後是函數申明，我的函數不能有參數，所有操作對象都是資料區的資料。
下面我放上文法大家就知道了。首先說明：我是用LL1進行文法分析的，是以文法需要進行消除左遞歸和提取公因子，導緻下面的文法可讀性不好，下面T開頭的非終結符都是中間産生的。
終結符:
{ "i","n","s",",",";","(",")","[","]","{","}","<",">","=","!=","==","+","-","*","/","int",
"string","def","if","while","printf","#" }
//必要說明
i:變量名
n:數字
s:字元串
int:整型定義
string:字元串定義
if:if語句
while:while語句
printf:列印函數名
def:函數定義
#:僅僅用于分析，沒任何意義
文法：
//下面的格式是： 非終結符 産生式1|産生式2|産生式3| .....
//産生式裡面每個非終結用空格隔開 這個格式便于處理生成分析表
P V F| //程式由變量申明鍊 V 和函數申明鍊 F 組成
V T1| //變量申明鍊V：int或string或數組 變量名i ;
T1 V1 T1|e|
V1 T i T2|
T int|string|
T2 ;|[ n ] ;|
F T3| //函數申明F: def 函數名i （）{語句 S};
T3 F1 T3|e|
F1 def i ( ) { S }|
S T4| //語句S:if語句 IS 指派和函數調用 ACS while語句 WS 列印語句CP
T4 S1 T4|e|
S1 IS|ACS|WS|CP|
IS if ( CE ) { S }| //if語句 IS： if(比較表達式 CE){S}
WS while ( CE ) { S }| //while語句 WS： while(比較表達式 CE){S}
ACS i T5| //指派和函數調用語句 ACS: 變量名i=值表達式 VE 函數調call i()
T5 = T6|[ T13 ] = T6|( ) ;|
T6 VE ;|s ;|
AO +|-|
MO *|/|
RO <|>|!=|==|
CE VE RO VE| //比較表達式 CE: > < != == 比較用于跳轉
VE T7 T8| //值表達式 VE: 加減乘除算術運算
T8 AO VE T8|e|
T7 T9 T10|
T10 MO T7 T10|e|
T9 ( VE )|n|i T11|
T11 [ T13 ]|e|
CP printf ( T12| //列印語句 CP: printf(i或s或n,n)
T12 i , n ) ;|s , n ) ;|n , n ) ;|
T13 i|n|
下面放上我的語義程式設計，因為LL1是自頂向下的分析，是以我的語義程式也是自頂向下的。這裡我要說明下，有的課本隻講了自底向上的語義程式，他是和LR1配套的，和我的不太一樣。
//0到7的數字就是語義程式插入的位置，也就是說在這個位置執行語義程式
P V F 0| //0号判斷有沒有cfmain
V T1|
T1 V1 T1|e|
V1 T i T2 1| //1号申明處理
T int|string|
T2 ;|[ n ] ;|
F T3|
T3 F1 T3|e|
F1 def i 1 ( ) { S }|
S T4|
T4 S1 T4|e|
S1 IS|ACS|WS|CP|
IS if ( 2 CE ) { S } 3| //2号if while 入口處理 3号if while結尾處理
WS while ( 2 CE ) { S } 3|
ACS i T5|
T5 4 = 5 T6 6|[ T13 ] 4 = 5 T6 6|( ) ; 7| //4号操作數入棧 5号算術符号入棧 6号計算 7号函數調用
T6 VE ;|s 4 ;|
AO +|-|
MO *|/|
RO <|>|!=|==|
CE VE RO 5 VE 6|
VE T7 T8|
T8 AO 5 VE 6 T8|e|
T7 T9 T10|
T10 MO 5 T7 6 T10|e|
T9 ( VE )|n 4|i T11 4|
T11 [ T13 ]|e|
CP printf ( T12|
T12 i , n ) ; 7|s , n ) ; 7|n , n ) ; 7|
T13 i|n|
下面是加上語義程式的分析表。左邊一列是省略的非終結符，順序和文法相同。上邊一行是省略的終結符，順序和上面的終結符相同。這個表是根據文法自動生成的，在我的代碼tool.cpp裡面有生成FIRST、FOLLOW集合和分析表的代碼。一開始産生的原始分析表有4出沖突，直接删掉另一個e(就是空)即可。短杠-表示出錯。每個項目用空格分開，一個豎杠|表示一個産生式完了或者一個語義程式。
- - - - - - - - - - - - - - - - - - - - V|F|0| V|F|0| - - - - e
- - - - - - - - - - - - - - - - - - - - T1| T1| e - - - e
- - - - - - - - - - - - - - - - - - - - V1|T1| V1|T1| e - - - e
- - - - - - - - - - - - - - - - - - - - T|i|T2|1| T|i|T2|1| - - - - -
- - - - - - - - - - - - - - - - - - - - int| string| - - - - -
- - - - ;| - - [|n|]|;| - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - T3| - - - e
- - - - - - - - - - - - - - - - - - - - - - F1|T3| - - - e
- - - - - - - - - - - - - - - - - - - - - - def|i|1|(|)|{|S|}| - - - -
T4| - - - - - - - - - e - - - - - - - - - - - - T4| T4| T4| -
S1|T4| - - - - - - - - - e - - - - - - - - - - - - S1|T4| S1|T4| S1|T4| -
ACS| - - - - - - - - - - - - - - - - - - - - - - IS| WS| CP| -
- - - - - - - - - - - - - - - - - - - - - - - if|(|2|CE|)|{|S|}|3| - - -
- - - - - - - - - - - - - - - - - - - - - - - - while|(|2|CE|)|{|S|}|3| - -
i|T5| - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - (|)|;|7| - [|T13|]|4|=|5|T6|6| - - - - - 4|=|5|T6|6| - - - - - - - - - - - - -
VE|;| VE|;| s|4|;| - - VE|;| - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - +| -| - - - - - - - - -
- - - - - - - - - - - - - - - - - - *| /| - - - - - - -
- - - - - - - - - - - <| >| - !=| ==| - - - - - - - - - - -
VE|RO|5|VE|6| VE|RO|5|VE|6| - - - VE|RO|5|VE|6| - - - - - - - - - - - - - - - - - - - - -
T7|T8| T7|T8| - - - T7|T8| - - - - - - - - - - - - - - - - - - - - -
- - - - e - e - - - - e e - e e AO|5|VE|6|T8| AO|5|VE|6|T8| - - - - - - - - -
T9|T10| T9|T10| - - - T9|T10| - - - - - - - - - - - - - - - - - - - - -
- - - - e - e - - - - e e - e e e e MO|5|T7|6|T10| MO|5|T7|6|T10| - - - - - - -
i|T11|4| n|4| - - - (|VE|)| - - - - - - - - - - - - - - - - - - - - -
- - - - e - e [|T13|]| - - - e e - e e e e e e - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - printf|(|T12| -
i|,|n|)|;|7| n|,|n|)|;|7| s|,|n|)|;|7| - - - - - - - - - - - - - - - - - - - - - - - -
i| n| - - - - - - - - - - - - - - - - - - - - - - - - -
我的代碼檔案夾結構是:
下面主要簡單介紹每個檔案裡面代碼實作的功能和資料結構的設計：
lex.cpp 詞法分析
裡面實作了詞法分析的功能，裡面最重要的資料結構就是字元流。當完成了詞法分析以後，就産生字元流，用于後面的文法分析。
//token結構
struct token {
string type;//類型
string content;//内容
int line;//單詞行号
token(string t, string c,int l=0) {
type = t;
content = c;
line = l;
}
};
vector<token> token_stream;//token流 用于下一步的文法分析
syntax.cpp 文法分析
裡面主要完成帶語義程式的文法分析。如果沒有錯誤，那麼就會翻譯成彙編執行代碼。
void main() {
init_parse_table();//初始化分析表
if (lex()) {//詞法分析正确
string result = syntax() ? "OK" : "FAILE";//文法分析結果
if (result == "OK")
to_asm();//翻譯成彙編并執行
cout << result << endl;
}
}
semantic.cpp 語義程式
這是一個主要代碼，裡面實作了上面提到的8個語義程式和把中間代碼轉成彙編的函數。這裡面有很多關鍵結構:
//操作數資訊
struct op_info {
int type;//操作數類型 （變量 數字 字元串 數組一項)
string value;
string position;//數字操作數的位置 有可能是變量而不是常量
op_info(int t,string v="",string po="") {//字元串 變量 數組一項
type = t;
value = v;
position = po;
}
op_info() {};
};
//IR中間代碼 四元式
struct ir_code {
int type;//操作類型 (JMP 等類彙編)
op_info op1, op2, result;
ir_code(int t, op_info p1, op_info p2, op_info re) {
type = t;
op1 = p1;
op2 = p2;
result = re;
}
};
//變量資訊
struct var_info {
int type;//變量類型 (int string 數組)
int length;//如果是數組記錄數組長度
var_info(int t, int l = -1) {
type = t;
length = l;
}
};
//if while 語句跳轉位址回填輔助結構
struct if_while_back{
bool is_if;
int back_index;//需要回填的IR位址
string label_out;//if while 的出口
string label_in;//while 的入口
if_while_back(bool i, int b, string out,string in) {
is_if = i;
back_index = b;
label_out = out;
label_in = in;
}
};
//函數過程資訊
struct func_info {
//vector<var_info> paras;//函數調用參數 為printf内部函數使用 使用者定義函數不能有參數
vector<ir_code> codes;//函數翻譯成的四元式序列
};
//變量資訊表
map<string, var_info> var_map;
//函數過程資訊表
map<string, func_info> fun_map;
//字元串常量資訊表 左邊是字元串内容 右邊是名字
map<string, string> str_map;
//表達式操作符号類型棧
stack<string> ex_t_stack;
//表達式操作數棧
stack<op_info> ex_o_stack;
//if_while出口回填輔助棧
stack<if_while_back> i_w_stack;
操作數結構主要用于算術計算和指派語句裡面。IR四元式就是中間代碼。變量和函數資訊用于建立變量表和函數表，便于查找變量和函數的資訊。函數裡面有IR鍊，也就是說一個函數對于一串IR。下面的具體代碼我就不貼了，有點多。
tool.cpp 工具
這裡面主要實作根據文法建構分析表。就是把FIRST和FOLLOW集合的生成寫了下，然後就生成分析表輸出到檔案供以後每次編譯時使用。
上面的介紹很簡單，大家可以具體去看代碼了解，我不可能每一個都介紹，代碼裡面我寫了注釋的。
下面看一下我的檔案結構，也就是放測試代碼、分析表等等的檔案夾:
asm: 生成的彙編代碼，裡面有用于彙編的LINK.EXE和MASM.EXE
code:Cf測試代碼
asm.bat: 彙編批處理。因為我是64位WIN10,要使用MASM要用DOSBOX，而用DOSBOX必須每次配置比較煩，是以我寫了個批處理，當我在VS2015裡面直接運作編譯器時，隻要測試代碼通過，那麼我就直接翻譯成彙編執行。
@start E:\DOSBox\DOSBox.exe
dosbox-0.74.conf:配置DOSBOX的檔案位址，用于配置DOSBOX自動執行我配置的參數，如下:
[autoexec]
# Lines in this section will be run at startup.
# You can put your MOUNT lines here.
mount c: e:\Cf_compiler\asm
c:
masm test.asm ;;
link test.obj ;;
test.exe
grammar.txt:文法定義
grammar_semantic.txt：帶語義的文法定義
parse_table.txt:分析表
四、案發錄像
下面我就放幾張運作的照片:
測試代碼:
int a;
def cfmain(){
printf("Hello World!",1);
printf(" ---HackerLi",0);
}
測試代碼:
int a;
int b;
int c;
def test(){
a=0;
b=1;
printf("0+1=",0);
c=a+b;
printf(c,1);
b=167;
a=20;
printf("167-20=",0);
c=b-a;
printf(c,1);
b=2;
a=20;
printf("2*20=",0);
c=b*a;
printf(c,1);
b=50;
a=2;
printf("50/2=",0);
c=b/2;
printf(c,1);
}
def cfmain(){
test();
}
測試代碼:
int a;
int b;
int cc;
int d[5];
string e;
string f;
string g;
string h[5];
def tt(){
a=0;
b=1;
cc=2;
d[0]=3;
d[1]=4;
d[a]=9;
d[4]=d[a];
f="Test IF statement!";
g="Test WHILE statement!";
h[0]="Test string array !";
if(b>0){
f="1111 IF";
printf(f,1);
}
if(d[4]!=0){
f="22222 IF";
printf(f,1);
while(d[3]>0){
g="IF -- WHILE !!!";
printf(g,1);
d[3]=d[3]-1;
}
}
while(cc>0){
if(d[3]==0){
f="3333 IF";
printf(f,1);
}
printf(g,1);
cc=cc-1;
}
printf("Test printf string !",1);
cc=2;
printf(cc,1);
cc=d[4]/cc+cc+b*d[a]-d[1]+a;
cc=a+(b+d[2])*a;
printf(cc,0);
}
def cfmain(){
e="Hello World!";
printf(e,1);
tt();
}
五、自我忏悔
由于時間比較緊，代碼的設計存在很多缺陷和不合理處。同時，我的測試代碼也很片面，沒有進行全面的測試，也就是說代碼很有可能有BUG。請大家看到它不要害怕，直接用拖鞋拍死即可。另外大家看到生成的彙編代碼時不要吐槽，因為沒有優化，是以看起來有點傻-。-！
代碼位址: https://github.com/Liiiiiiiiiq/CfCompiler