课 程 设 计 报 告
设计题目:一个简单的C语言编译器的设计与实现
班 级:计算机1503
组长学号:20154349
组长姓名:邵威
指导教师:张俐
设计时间:2017 年 11 月
设计分工
组长学号及姓名:20154349 邵威
分工: 文法设计,翻译文法设计,基本块划分,中间
代码优化处理,函数部分目标代码生成,生成 TXT 文件
组员 1 学号及姓名:20154538 郭苗苗
分工: 文法讨论,声明语句部分语法分析,条件赋值
循环语句部分中间代码生成,基本块划分,目标代码生
成,活跃信息填写
组员 2 学号及姓名:20154474 石家昊
分工: 文法讨论,扫描器设计,符号表设计,程序和
语句部分语法分析,函数部分中间代码生成,递归函数
目标代码生成
组员 3 学号及姓名:20154391 陈欣
分工: 文法讨论,算术表达式,逻辑语句部分语法分
析以及其中间代码生成
摘 要
在经过一个学期的编译原理课程学习之后,我们迎来了课程设计,使
我们可以将课堂所学应用到设计中,完成一个简易的编译器。经过两周
的努力,组内成员在完成了这次课程设计,收获良多。
编译程序是一种翻译程序,它特指把某种高级语言翻译成具体计算
机上的低级程序设计语言。编译程序是计算机系统软件最主要的组成部
分,也是用户最直接关系的工具之一。一个编译程序的可以划分为前端
和后端。前端包括词法分析、语法分析、语义分析与中间代码生成三个
阶段,后端包括优化、目标代码生成两个阶段,另外还有符号表的管理
和错误处理贯穿整个过程。
这次编译器设计,我们小组完成了前端,后端的设计与实现,并完
成了几乎所有的附加内容。首先是词法分析识别 Token 序列,由于语法
较为庞大,所以在语法分析中我们使用相对容易实现的递归下降子程序
方法,通过插入翻译动作来填符号表,并形成中间代码,即四元式序列,
四元式中使用自行设计的符号表得到的较为完善的数据和参数可以为后
续的目标代码生成提供便利,并且我们前端对源程序扫描一遍就实现了
词法分析、语法分析、语义分析与中间代码生成三个阶段。
在目标代码生成中,我们选择了虚拟机指令作为目标代码。算法先
进行了基本块的划分,为了生成高效的目标指令代码,我们还对四元式
序列做了基于 DAG 的局部优化,最后又填写了活跃信息,才生成了目标
代码。同时这次课设我们还做了一些扩展,增加了对数组,函数,函数
嵌套的处理。
关键词:编译程序,前端,后端,DAG 优化,函数处理。
I
目 录
摘要.......................................................I
1 概述 ....................................................1
2 课程设计任务及要求 ......................................2
2.1 设计任务 ..........................................2
2.2 设计要求...........................................2
3 算法与数据结构...........................................3
3.1 算法的总体思想(流程).............................3
3.2 词法分析识别器模块.................................4
3.2.1 功能.........................................4
3.2.2 数据结构.....................................5
3.2.3 算法.........................................7
3.3 语法分析模块.......................................9
3.3.1 功能.........................................9
3.3.2 数据结构....................................10
3.3.3 算法........................................17
3.4 语义分析和中间代码生成模块........................36
3.4.1 功能........................................36
3.4.2 数据结构....................................37
3.4.3 算法........................................38
3.5 符号表模块........................................39
3.5.1 功能........................................39
3.5.2 数据结构....................................39
II
3.5.3 算法........................................41
3.6 优化处理模块......................................42
3.6.1 功能........................................42
3.6.2 数据结构....................................42
3.6.3 算法........................................43
3.7 目标代码生成模块..................................46
3.7.1 功能........................................46
3.7.2 数据结构....................................46
3.7.3 算法........................................47
4 程序设计与实现..........................................51
4.1 程序流程图........................................51
4.2 程序说明..........................................52
4.3 实验结果..........................................55
5 结论....................................................66
6 参考文献................................................67
7 收获、体会和建议........................................68
7.1 邵威个人总结......................................68
7.2 郭苗苗个人总结....................................69
7.3 石家昊个人总结....................................70
7.4 陈欣个人总结......................................71
III
1 概述
编译原理课程兼有很强的理论性和实践性,是计算机专业的一门非
常重要的专业基础课程,在系统软件中占有十分重要的地位。编译原理
课程设计是本课程重要的综合实践教学环节,是对平时实验的一个补充。
通过编译器相关子系统的设计,使学生能够更好地掌握编译原理的基本
理论和编译程序构造的基本方法和技巧,融会贯通本课程所学专业理论
知识;培养学生独立分析问题、解决问题的能力,以及系统软件设计的
能力;培养学生的创新能力及团队协作精神。
在计算机上执行一个高级语言程序一般要分为两步;第一步,把高
级语言翻译成机器语言程序;第二步,运行所得的机器语言程序求得计
算结果。编译程序就是将高级语言程序翻译成机器语言程序或汇编语言
程序的工具。工作过程一般可以划分为五个阶段:词法分析、语法分析、
语义分析和中间代码生成、优化、目标代码生成。前端包含词法分析、
语法分析、语义分析和中间代码生成三个阶段,后端包含优化、目标代
码生成两个阶段。
本次课设将前端的三个阶段整合到一起,通过对输入的源程序扫描
一遍的方式实现,入口为语法分析,使用递归下降子程序分析法。将词
法分析器作为语法分析的子程序,当语法分析需要用到 Token 时,调用
词法分析器识别出一个 Token 串,同时在语法分析的过程中插入语义动
作,每识别完一定的 Token 串就能生成四元式。在后端则直接根据四元
式生成目标代码。符号表用于存储变量以及检查是否有重定义、未定义
的变量。在错误处理中,一旦发现错误,就进行输出并立即停止编译过
程。
1
2 课程设计任务及要求
2.1 设计任务
定义一个简单 C 语言文法(包括变量声明语句、数组声明语句、赋
值语句、算术运算表达式、逻辑运算表达式、if 语句、while 语句、return
语句、函数、参数声明、函数调用等);
扫描器设计实现;
语法分析器设计实现;
中间代码设计;
中间代码生成器设计实现;
优化处理
目标代码生成。
2.2 设计要求
1、在深入理解编译原理基本原理的基础上,对于选定的题目,以小
组为单位,先确定设计方案;
2、设计系统的数据结构和程序结构,设计每个模块的处理流程。要
求设计合理;
3、编程序实现系统,要求实现可视化的运行界面,界面应清楚地反
映出系统的运行结果;
4、确定测试方案,选择测试用例,对系统进行测试;
5、运行系统并要通过验收,讲解运行结果,说明系统的特色和创新
之处,并回答指导教师的提问;
6、提交课程设计报告。
2
3 算法与数据结构
3.1 算法的总体思想(流程)
对给定的一段源程序,先进行前端分析。前端包括词法分析、语法
分析、语义分析和中间代码生成三个阶段,这三个阶段通过对输入的源
程序扫描一遍的方式即可实现,词法分析器作为语法分析的子程序,当
语法分析需要用到 Token 时,调用词法分析器识别出一个 Token 串,同
时在语法分析的过程中插入语义动作,在进行语法分析的同时也能生成
四元式。然后将生成的四元式交给后端进行优化处理以及目标代码生成。
此外,符号表用来记录源程序中出现的变量,如果在分析的过程中出现
错误,则进行错误处理。具体流程图如下:
符
号
表
管
理
源程序
前端(词法分析、语法分
析、语义分析和中间代码
生成)
中间代码
后端(优化、目标代码生成)
目标代码
错
误
处
理
3