编译原理课程设计任务书
1、目的
学生在学习《程序设计语言编译原理》课程过程中,结合各章节的构造编译程序的基本理论,总共用10个课时完成课程设计。在基本实验完成的基础上,逐步完成课程设计。要求用C或C++语言描述及上机调试,实现一个小编译器(词法分析,语法分析,中间代码产生,优化,目标代码生成等重要子程序,其中词法分析、语法分析及语义分析功能必须完成),使学生将理论与实际应用结合起来,受到软件设计等开发过程的全面训练,从而提高学生软件开发的能力。
2、课程设计的任务
(1)设计符号表
确定符号表的组织方式,一般应包括名字栏和信息栏,其中名字栏作为关键字。要考虑能够存储有关名字的信息,并可以高效地完成如下操作:
a.查找:根据给定的名字,在符号表中查找其信息。如果该名字在符号表中不存在,则将其加入到符号表中,否则返回指向该名字的指针;
b.删除:从符号表中删除给定名字的表项。
(2)设计词法分析器
设计各单词的状态转换图,并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括:
a.具备预处理功能。将不翻译的注释等符号先滤掉,只保留要翻译的符号串,即要求设计一个供词法分析调用的预处理子程序;
b.能够拼出语言中的各个单词;
c.将拼出的标识符填入符号表;
d.返回(种别码, 属性值)。
(3)语法分析与中间代码产生器
要求用预测分析法、递归下降分析法、算符优先分析法、SLR分析法(几种方法任选),实现对表达式、各种说明语句、控制语句进行语法分析。
若语法正确,则用语法制导翻译法进行语义翻译:对说明语句,要求将说明的各符号记录到相应符号表中;对可执行语句,应产生出四元式中间代码并填写到三地址码表中;
若语法错误,要求指出出错性质和出错位置(行号)。出错处理应设计成一个出错处理子程序。
(4)优化器
a.局部优化:设计出划分基本块的算法,在每一个基本块中实现:合并已知量、删除多余运算和删除无用赋值三种局部优化。设计构造基本块的DAG图的算法,以及将DAG图还原实现基本块的优化的算法。
b.循环优化:只做一重循环优化,完成代码外提,强度削弱和删除归纳变量等三种优化。要求实现while循环和for循环语句的优化。
(5)目标代码生成器
能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码(汇编指令应包括加、减、乘、除),要求指令条数最少的情况下,尽量使用寄存器,尽量少访问内存,这样才能做到运行效率高。
3、样本语言
样本语言为C-语言(见附录),其中基本的语句要求必须实现,其余部分可根据自己的实际情况选择实现。
4、要求
各函数和过程应有框图描述,有功能说明,有入口和出口参数说明。
5、参考资料
《程序设计语言编译原理》,陈火旺编著,国防工业出版社
《编译原理》,吕映芝、张素琴、蒋维杜编著,清华大学出版社
《编译原理》,Alfred V.Aho等,李建中译,机械工业出版社
6、考察方式
最终完成一个完整的编译程序。要求输入一小段完整的C-语言源程序,输出各编译阶段的运行结果。在课程设计结束时上机运行,展示运行效果。
7、作业提交
最晚在期末(第17周课程结束时)提交纸质作业及可运行程序,格式参考学院的规定课程设计任务书模板。