编译原理课程设计报告--c-minus小型编译器设计与构造.doc

课程设计报告 课题名称： c-minus小型编译器设计与构造 提交文档学生姓名： 童华兵 提交文档学生学号： 0643041343 同组 成 员 名 单： 无 指导 教 师 姓 名： 张兵 指导教师评阅成绩： 指导教师评阅意见： . 提交报告时间： 2009年 6 月 日 1.课程设计目标 题目实用性 ：C－，本质上它是C的一个子集，但省去了一些重要的部分，因此得名。该课程设计给出了该语言惯用的词法，包括语言标记的描述。其次，给出了每个语言构造的BNF描述，同时还有相关语义的描述。 要求 ：通过对编译原理的学习和理解，参照tiny语言的实现，运用所学知识实现C_的词法分析和语法分析阶段。 目标 ： 1）词法分析阶段：熟悉通过正则表达式构造NFA，进而构造DFA的方法 2）语法分析阶段，熟练掌握语法分析方法，如递归下降分析或者LL（1）分析或者自底向上分析法，熟悉并掌握词法分析中如何构造DNF和各种语法分析方法。 3）能有效的运用DNF来分析源代码得到各Token值，根据采用的语法分析方法构造出语法分析树。 2.分析与设计 程序流程图 程序的流程参照了书本TINY编译器的实例程序：语法分析器(Parser)调用词法分析器得到符合词法的字，建立语法树；符号表通过对语法树的分析，建立符号表，同时检查变量未定义等错误；类型检查包括检查表达式两边是否匹配，函数参数是否匹配等等；经由上述步骤而未出错的源程序被认为是合法程序，然后代码生成通过语法树和符号表生成P Code中间代码，并将变量地址存入符号表。 其中类型检查和代码生成不要求实现。 以下为具体实验分步报告以及过程： 词法分析阶段 ： 词法分析描述：依次地读入源程序，即对字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)一般过程是: 1.?????? 语言的词法描述. 2.?????? 根据描述产生正则表达式. 3.?????? 根据正则表达式产生NFA-DFA 4.?????? 根据DFA来构造程序else if int return void while 标识符：用来表示各种名子 常量：数字或字符串常量 运算符：+ 、-、*等 分隔符：逗号、分号、冒号等 C-惯用词法规则： (1) 下面是语言的关键字： else if int return void while 所有的关键字都是保留字，并且必须是小写。 (2) 下面是专用符号： + - * / = = == != = ; , ( ) [ ] { } /* */ (3) 其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 小写和大写字母是有区别的。 (4) 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字。 (5) 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。 c)C-的DFA图 第一部分：设计cminus符号表 符号表是编译器中的主要继承属性，并且在语法树之后，形成了主要的数据结构。符号表主要的操作有插入、查找和删除。杂凑表（hash表）通常为符号表的实现提供了最好的选择，因为所有3种操作都能在几乎恒定的时间内完成，在实践中也是最常使用。该课程设计所用的C-符号表采用建立杂凑表的方法。杂凑表是一个入口数组，称作“桶( b u c k e t )”，使用一个整数范围的索引，通常从0到表的尺寸减1。杂凑函数(hash fuction)把索引键(在这种情况下是标识符名，组成一个字符串)转换成索引范围内的一个整数的杂凑值，对应于索引键的项存储在这个索引的“桶”中。每个“桶”实际上又是一个线性表，通过把新的项插入到“桶”表中来解决冲突在任何情况下，“桶”数组的实际大小要选择一个素数，因为这将使一般的杂凑函数运行得更好。 杂凑函数。在符号表实现中使用的杂凑函数将字符串(