独立开发Micro C编译器

Jun 20, 2017


这一段时间向老师要了一个project,用C++开发一个Micro C编译器, 并且把编译器的每一个部分都做成可视化的,这样还能够起到一个教学的作用。

于是就开始写这个编译器了嘛,不过不准备把里面每一个步骤都在博文里面说的很详细。编译原理是一门 门槛很高的科目,花太多时间放在教学和其他的方面会妨碍到我的正常的学习步伐。于是这几篇博文更多 的就是描述我写这个编译器的过程吧,而不是原理和语言教学。 原理的话,更多的需要看看书,把这门课学好。所以这些博文更适合有一定基础的人,并且想做些什么的同学看。

233,对我来说相当于重构一遍上机题吧。

嗯,我现在处于四个project并行进行…嗯…原谅我话变少了。

整体的思路

这个编译器的难度不大,除去界面外,本体大致分了五个部分:

  • 词法分析
  • 文法定义
  • 语法分析
  • 语义分析
  • 中间代码生成

也就是普通的编译器的前端部分。还没有深入到内存等等的部分,做出来的效果也大概就是输入这样的一段代码:

while(c > b){
    if(a < d){
        f = e + k;
    }else{
        c = b - c;
        f = e - k;
    }
}

能够先根据词法分析器,输出记号流。

然后根据这些记号流和定义的文法,构造语法分析,包括堆栈和一棵抽象语法树。

最后根据语法分析,进行语义加工,制导翻译,得到标识符的值。

顺带还可以根据源代码得到三地址代码,也就是一种中间表示形式。

那么,我们首先要做的,自然而然就是词法分析了。

词法分析

先描述一下我们词法分析要做些什么。

比如我们输入这样的一个源代码:

if(a > b){
    c = d + e;
}

通过词法分析器,我们要得到记号流,一个记号也就是二元组,由记号种类和属性值构成,比如上面的代码,我们要输出的就是下面的记号流。

<if,   0>
<(,   21>
<a,    0>
<rop, 20>
<b,    1>
<),   22>
<{,    3>
<c,    2>
<=,   16>
<d,    3>
<+,   14>
<e,    4>
<;,    6>
<},    4>

上面的输出是根据我自己定义的记号种类和属性值来的。

我定义的符号和属性值如下:

if     0
else   1
while  2
{      3
}      4
;      6
#      8
+      14
*      15
=      16
&&     17
||     18
!      19
>=     20
<=     20
==     20
(      21
)      22
id     23
const  24

弄好了这些之后,我们先定义二元组的数据结构:

二元组

class tokens{
public:
    string token_name;
    int token_num;
    static int idNum;
    tokens(string tn, int tnum): token_name(tn), token_num(tnum){}
    void set(string tn, int tnum){token_name = tn; token_num = tnum;}
    void show(){cout<<"tokenName: "<< token_name<< " token_num: "<< token_num<<endl;}
};

然后就可以设计词法分析类了。

词法分析类

直接上代码:

class token_parser{
public:
    // judge if(ch == letter)    letter: a_z, A_Z, -, _
    bool isLetter(char c);
    // judge if(ch == digit)     digit: 0-9
    bool isDigit(char c);
    // judge if(str== num)       num: 0 - 2147483648
    bool isNum(string s);
    // judge if(str== key)       key: keywords, see private
    bool isKeywords(string s);
    // get the num of keywords
    int getKeywordsNum(string s);
    // judge if(str == ID)       id: letter(letter|digit)*
    bool isID(string s);
    // parser, output the ans.   basicElement: <tokenName, tokenNum>
    void parser(string &s);
    // trim, cut off all ' ' and '\n' in the source codes
    void trim(string &s);
    // output the input, get the source codes from a txt
    string getInput(string filename = "./input.txt");
    // source code after trim
    string input;
    // tokens flow
    vector<tokens> ans;
    // ids table
    map<string, int> ids;

private:
    // all keywords
    string keywords[20] = {"if", "else", "while"};
};

主要思路便是:

step1: 逐个字符的读入源程序,如果遇到字母,转入step2,如果遇到数字,转入step4,如果遇到其他的字符,转入step6。

step2: 从当前位置开始,继续往后扫描,直到中间所有的字符连在一起不满足一个标识符id的条件为止。 标识符判定方法为正则式: letter(letter|digit)* 这个时候中间所有的字符除掉最后一个之后就是一个标识符,转入step3。

step3: 遍历关键字表,如果标识符不在里面,则加入符号表后成为二元组输出,否则便是一个关键字,从关键字表中匹配属性值成为二元组输出。

step4: 从当前位置,继续往后扫描,知道中间所有的数字字符连在一起不满足一个Num的条件为止。 Num判定方法为正则式:digit digit* 这个时候中间所有的字符除去最后一个之后就是一个Num,转入step5。

step5: 通过这个Num求出Num的值,讲其作为属性值,组成二元组后输出。

step6: 用一个switch-case语句判断,如果是已定义的符号,直接组成二元组输出。如果是非定义的符号,就跳过。

具体的代码可以参考我的Github