一、作案动机
由于这学期有一门《编译原理》的课程，感觉如果不写一个编译器对不起这门课，所以我便动手了。但是考虑到我的时间有限和做一个编译器的难度，于是我给自己的时间是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