一个使用递归下降方法实现的cminus编译器,使用nasm作为后端

onlyflyer

本来是放在cpu与编译器版的，但是那里太冷清了，故借贵宝地易用，希望能对大家有点用处：

出于对编译技术的兴趣，小弟在十一期间完成了一个cminus的编译器（Qcc）。没有太大的难度，但还算完成的非常认真，代码可读性较好。希望能与各位大侠一起交流进步。
您可以通过以下方式获取Qcc的源代码
svn checkout http://cminus-compiler.googlecode.com/svn/trunk/ cminus-compiler

下面是关于cminus的一点说明：

关于Qcc:
CMINUS是C语言的一个子集，该语言的语法在《编译原理与实践》第九章附录中有详细的介绍。
C MINUS的语法非常容易使用EBNF进行重写，所以很适合使用递归下降的方法来分析。

Qcc的特点：
1,Qcc使用nasm作为后端，也就是说Qcc不直接生成机器代码，它产生能够供nasm使用的汇编代码，然后由nasm生成elf格式的obj文件，再进一步的由ld与glibc连接生成最终的可执行文件。
2,nasm最大的特点是在语法分析的过程中不生成语法树以及任何的中间数据结构，而是直接生成汇编代码。这样做的原因有三个方面：
首先，能够简化cminus的设计，使cminus的源代码非常容易读懂，在c代码和汇编代码中间只隔了薄薄一层的语意处理。如果你有时间去看看cminus的源代码的话，你会发现它非常清晰易懂。
其次，我看过不少编译器，包括lcc都是生成了语法树或者dag（有向无环图），感觉似乎所有的编译器都要去生成这样的中间结构。我不想按部就班的也作同样的事情，于是就进行了一下新的尝试。
最后，生成中间数据结构，最大的作用是为了进行代码优化以及实现跨平台(就像lcc那样)。但是Qcc作为一个简单的演示目的小编译器，并不考虑代码优化的部分,也不考虑能够生成其他平台的汇编代码。所以也就不生成语法树或者dag.

Qcc的实现：
1,Qcc使用lex来生成词法分析程序，请见scanner.l
2,Qcc的语法和语义处理部分在parser.c中。
3,Qcc的符号表管理在symbol.c中
4,Qcc的寄存器分配算法在reg.c中
5,主程序入口在main.c中
6,另外Qcc还包含了计算语法的first和follow集合的两个使用perl完成的脚本:first.pl,follow.pl。
7,关于cminus的EBNF语法请见rules.txt。我们可以使用first.pl和follow.pl来对语法进行处理，生成这个语法对应的first和follow集合。譬如 ./first.pl rules.txt first.txt
8,一些测试例子在sample目录中.

Qcc的使用方法：
make;chmod +x Qcc
./Qcc sample/sort.c

Qcc是一个perl脚本，它将完成目标程序的编译，链接以及执行。

TODO:
语义检查的部分还需要进一步的完善。

onlyflyer@gmail.com

onlyflyer

原帖由 zx_wing 于 2007-10-16 11:59 发表

赞lz
想请教一个问题，我个人对编译器不了解，想请问你在开始写之前，学习了哪些和编译器相关的知识，又是如何开始的呢？

我看了不少编译理论方面的书。真正觉得比较好的是以下几本，推荐一下：
《编译原理》 吕映芝，张素芹，此书已经绝版。但是此书的关于编译理论方面讲得非常好，特别是关于自底向上的分析方法，讲得非常容易理解。我看过一些翻译过来的编译理论方面的书，很多看不懂，不知道是翻译的有问题还是老外的表达方式有问题。
《编译原理与实践》里面的tiny语言是用递归下降的方法来分析的，书后面有源码，比较简单。
《可变目标c编译器:设计与实现》 是详细描述lcc的源代码的。强烈推荐一下。
当然还有的龙 虎 鲸 这三本最有名的编译方面的书，这三本书都比较侧重后端。由于我本人不是搞编译器的，只是看了下龙书，那两本没有看过。

如果说真正开始学习的话，还是《可变目标c编译器:设计与实现》给我最多的启发,觉得自己也可以写一个来锻炼一下。

onlyflyer

原帖由 flw2 于 2007-10-16 13:28 发表
《可变目标c编译器:设计与实现》刚买，介绍lcc的，感觉写的很烂
就看过龙书，而且据说现在的教材内容都是模仿它的，china-pub有句话说
“现在很多编译原理书都有错误，因为它的算法和龙书不是一样的”
我第6 ...

《可变目标c编译器》，这本书可是一点都不烂的。无论是该书介绍的一些编译技巧，还是编译方面的一些思想都是非常实用和具有启发性的。

onlyflyer

非常感谢DennisRitchie的热心和细心，你提出的问题我会马上改正的。
我已经研三了，目前在北京一家公司实习，目前正在找正式工作。

onlyflyer

albcamus(leviathan)，我是你的粉丝啊。
这次aka内核开发者大会我还问asmcos你怎么没来呢。

onlyflyer

最新更改：
1,增加了read功能
2,修正了一个bug.
3,修改了Qcc脚本，Qcc不在去执行生成的可执行文件，而只是完成编译链接的任务。

使用示例：
./Qcc sample/sort.c
./sort
然后输入十个整数
23
25
20
10
9
8
7
7
6
5
得到输出：
5
6
7
7
8
9
10
20
23
25