编泽原理实验教程 (草稿) 张昱陈意云 中国科学技术大学合肥 2008年4月9日
编译原理实验教程 （草稿） 张昱 陈意云 中国科学技术大学 合肥 2008 年 4 月 9 日
目录 目录 (草稿) 第1章述 4444+++4444444 11本书的目标 12课程设计结构 1.21要实现的源语言 1.2.2抽象语法树.… 1.2.3课程设计选题 1.2.4小结 13实验形式及评价 14实验环墙与工具 1.4.1简介 5 1.4.2环境变量设置 1.43 Eclipse的安装和使用. 1.44XML与An简介 第2章MINIJOOL语言 2.1 MINIOOLi语言简介. 23 2.1.1MmiJ00L语言的特点 23 2.1.2个iaJO0L程序示例 24 2,2MNJ0OL语言的词法 24 2.3 MINIJOOL语言的语法 .26 2.3.1类型、值和变量 .27 232类 32 2.3.3语句快和语句…。 38 2.34表达式 0 2.4 SIMPLEMINIJOOL语言简介 42 2.5 SKIPOOMINIJOOL语言简介 .43 2.5.1一些注意事项 2.5.25 inOOMini/OOL程序示例 2.6Sk1 POOMINIJOOL语言的静态语义 .46 2.61抽象语法 2.6.2抽象类型、定型环城、断言与定型规则 48 2.6.3良形的类型以及类型兼容
目录 I 目 录 （草稿）..................................................................................................................................................I 第 1 章 概述............................................................................................................................................1 1.1 本书的目标 ...................................................................................................................................1 1.2 课程设计结构 ...............................................................................................................................2 1.2.1 要实现的源语言....................................................................................................................2 1.2.2 抽象语法树............................................................................................................................2 1.2.3 课程设计选题........................................................................................................................3 1.2.4 小结........................................................................................................................................4 1.3 实验形式及评价 ...........................................................................................................................4 1.4 实验环境与工具 ...........................................................................................................................5 1.4.1 简介........................................................................................................................................5 1.4.2 环境变量设置........................................................................................................................7 1.4.3 Eclipse的安装和使用.............................................................................................................9 1.4.4 XML与Ant简介.....................................................................................................................19 第 2 章 MINIJOOL语言 .....................................................................................................................23 2.1 MINIJOOL语言简介 ....................................................................................................................23 2.1.1 MiniJOOL语言的特点..........................................................................................................23 2.1.2 一个MiniJOOL程序示例.....................................................................................................24 2.2 MINIJOOL语言的词法 ................................................................................................................24 2.3 MINIJOOL语言的语法 ................................................................................................................26 2.3.1 类型、值和变量..................................................................................................................27 2.3.2 类..........................................................................................................................................32 2.3.3 语句块和语句......................................................................................................................38 2.3.4 表达式..................................................................................................................................40 2.4 SIMPLEMINIJOOL语言简介.........................................................................................................42 2.5 SKIPOOMINIJOOL语言简介 .......................................................................................................43 2.5.1 一些注意事项......................................................................................................................44 2.5.2 一个SkipOOMiniJOOL程序示例........................................................................................46 2.6 SKIPOOMINIJOOL语言的静态语义 ...........................................................................................46 2.6.1 抽象语法..............................................................................................................................47 2.6.2 抽象类型、定型环境、断言与定型规则..........................................................................48 2.6.3 良形的类型以及类型兼容..................................................................................................50
目录 264定型环境的扩展 2.65表达式 5 26.6语句和语句快… 53 2.67函数的定义 55 2.68程序 56 第3章一个简单的程序解释器 3.1实验软件包的结构 58 32课程设计1：一个简单的程序解释器 .59 3.3实验平台介绍 61 3.3.1实验平台接口 .6 3.3.2实验运行平台… 65 3.4课程设计1开发和测试指南 71 3.41 Eclipse下开发. 72 3.42在控制台下编译和运行 74 3.43测试要求 75 3.5抽象语法树(AST) 75 3.5.1 Eclipse AST的总体结构。 75 3.5.2org.eclipse.jdi.core.dom.AST 76 3.53org.eclipse.jdt.core.dom.ASTNode及其添生类. 77 3.5.4 org.eclipse.idt core.dom.ASTVisitor... 35.5 Eclipse AST使用示例 35.6AST的图形化是示包- -4S刀View 3.6设计模式 81 361工厂方法棋式 3.6.2访问者模式 82 第4章词法分析 85 4.1本章课程设计概述」 .85 4.2课程设计2-1：用LEX为语言生成一个词法分析器 87 4.2.1示例 87 4.2.2用Fex为finiJOOL进行词法分析… .92 4.3课程设计2-2：手工编写一个简单的词法分析器 93 431示城 93 4.3.2课程设计任务 …96 4.33编泽和运行指南 .96 4.4课程设计2-3：编写一个NFA生成器 .96 41Mex词法规范文件的格式
目录 II 2.6.4 定型环境的扩展..................................................................................................................51 2.6.5 表达式..................................................................................................................................51 2.6.6 语句和语句块......................................................................................................................53 2.6.7 函数的定义..........................................................................................................................55 2.6.8 程序......................................................................................................................................56 第 3 章 一个简单的程序解释器..........................................................................................................58 3.1 实验软件包的结构 .....................................................................................................................58 3.2 课程设计 1：一个简单的程序解释器.......................................................................................59 3.3 实验平台介绍 .............................................................................................................................61 3.3.1 实验平台接口......................................................................................................................61 3.3.2 实验运行平台......................................................................................................................65 3.4 课程设计 1 开发和测试指南 .....................................................................................................71 3.4.1 在Eclipse下开发..................................................................................................................72 3.4.2 在控制台下编译和运行......................................................................................................74 3.4.3 测试要求..............................................................................................................................75 3.5 抽象语法树（AST）..................................................................................................................75 3.5.1 Eclipse AST的总体结构 .......................................................................................................75 3.5.2 org.eclipse.jdt.core.dom.AST.................................................................................................76 3.5.3 org.eclipse.jdt.core.dom.ASTNode及其派生类 ....................................................................77 3.5.4 org.eclipse.jdt.core.dom.ASTVisitor ......................................................................................77 3.5.5 Eclipse AST使用示例 ...........................................................................................................77 3.5.6 AST的图形化显示包——ASTView......................................................................................78 3.6 设计模式 .....................................................................................................................................81 3.6.1 工厂方法模式......................................................................................................................81 3.6.2 访问者模式..........................................................................................................................82 第 4 章 词法分析..................................................................................................................................85 4.1 本章课程设计概述 .....................................................................................................................85 4.2 课程设计 2-1：用JFLEX为MINIJOOL语言生成一个词法分析器............................................87 4.2.1 示例......................................................................................................................................87 4.2.2 用JFlex为MiniJOOL进行词法分析....................................................................................92 4.3 课程设计 2-2：手工编写一个简单的词法分析器 ...................................................................93 4.3.1 示例......................................................................................................................................93 4.3.2 课程设计任务......................................................................................................................96 4.3.3 编译和运行指南..................................................................................................................96 4.4 课程设计 2-3：编写一个NFA生成器........................................................................................96 4.4.1 MLex词法规范文件的格式..................................................................................................97
目录 442澳理设计指导 4.4.3课程设计任务 .102 4.5课程设计2-4：编写 一个词法分析器的生成器 103 4.6 JFLEX词法规范 104 4.6.1用户代码 .104 462选项和声明 104 46.3词法规则 .107 第5章语法分析 5.1本章课程设计概述 111 5.2课程设计31：手工编写一个语法分析器 13 5.2.1如引轨ab2项目中的类 .13 52.2要分析的语法结构 .114 5.2.3课程设计指导 15 52.4课程设计要求… .116 5.3课程设计32：用CUP生成一个语法分析器 16 5.3.1示例1：不带错误恢复的语法分析器 5.3.2示例2：带错误恢复的语法分析器 .124 5.33课程设计任务… 125 54课程设计3-3：用NACC生成一个语法分析器 126 5.41示例1：不带错误恢复的语法分析器 .126 54.2示例2：带错误复的语法分所器。 543课程设计任务 .133 5.5课程设计3-4：编写一个语法分析器的生成器 l33 5.6CUP与YACC 133 5.6.1ACC简介.. 134 5.6.2CUP与4CC的文法规范文件的结构 134 5.6.3文法符号 135 5.64一个简单的例子… 136 56.5错误恢复 138 5.7JAVACC 138 5.7.1 JavaCC.文法规范文件的结构 5.7.2 JavaCC选项，」 .139 57.3产生式 .140 第6意语义分折 144 6.1本章课程设计概述 144 6.2课程设计指导 145
目录 III 4.4.2 课程设计指导......................................................................................................................99 4.4.3 课程设计任务....................................................................................................................102 4.5 课程设计 2-4：编写一个词法分析器的生成器 .....................................................................103 4.6 JFLEX词法规范..........................................................................................................................104 4.6.1 用户代码............................................................................................................................104 4.6.2 选项和声明........................................................................................................................104 4.6.3 词法规则............................................................................................................................107 第 5 章 语法分析................................................................................................................................ 111 5.1 本章课程设计概述 ................................................................................................................... 111 5.2 课程设计 3-1：手工编写一个语法分析器 .............................................................................113 5.2.1 如何引用Lab2 项目中的类............................................................................................... 113 5.2.2 要分析的语法结构............................................................................................................ 114 5.2.3 课程设计指导.................................................................................................................... 115 5.2.4 课程设计要求.................................................................................................................... 116 5.3 课程设计 3-2：用CUP生成一个语法分析器..........................................................................116 5.3.1 示例 1：不带错误恢复的语法分析器............................................................................. 117 5.3.2 示例 2：带错误恢复的语法分析器.................................................................................124 5.3.3 课程设计任务....................................................................................................................125 5.4 课程设计 3-3：用JAVACC生成一个语法分析器 ....................................................................126 5.4.1 示例 1：不带错误恢复的语法分析器.............................................................................126 5.4.2 示例 2：带错误恢复的语法分析器.................................................................................131 5.4.3 课程设计任务....................................................................................................................133 5.5 课程设计 3-4：编写一个语法分析器的生成器 .....................................................................133 5.6 CUP与YACC..............................................................................................................................133 5.6.1 YACC简介...........................................................................................................................134 5.6.2 CUP与YACC的文法规范文件的结构 ...............................................................................134 5.6.3 文法符号............................................................................................................................135 5.6.4 一个简单的例子................................................................................................................136 5.6.5 错误恢复............................................................................................................................138 5.7 JAVACC.......................................................................................................................................138 5.7.1 JavaCC文法规范文件的结构............................................................................................138 5.7.2 JavaCC选项........................................................................................................................139 5.7.3 产生式................................................................................................................................140 第 6 章 语义分析................................................................................................................................144 6.1 本章课程设计概述 ...................................................................................................................144 6.2 课程设计指导 ...........................................................................................................................145
目录 62.1符号表的设计与组织 5 6.2.2过AST的语义分折 45 6.2.3在语法分析的同时进行语义分析 第7章MIPS汇编代码生成 .146 7.1本章课程设计概述 146 7.2汇编代码的内部表示 147 72.1设计概述 .147 7.22示.… l48 7.3MPSR2000/R30O0架构、汇编语言及SPIM ..151 7.3.1MPSR2000R3000架构概述 7.3.2汇编语言的语法 152 7.3.3寄存器. .153 73.4江端指令 l55 73.5过理调用 .159 7.4MIPS汇编语言与SKIPOOMINIJOOL语言中部分结构的对应.… l60 7.41程序 160 7.42全局变量的定义和引用 16 74.3方法的定义 161 7.4.4方法的调用 162 7.4.5f语句 163 7.46 while语句 163 7.4.7enm语句. 164 7.5 SPIM.. l6 7.5.1 XSpim APCSpim 164 7.6SPM提供的系统调用 -165 7.7全局寄存器分配器. -166 771与编代码生成器的关系 166 7.72使用方法.… .166 7.8课程设计5-1 .167 78.1课程设计指导 .167 7.82江编代码生成器的病译和运行 7.9课程设计5.2 168 7.9.1课理设计指导 .169 7.9,2汇编代码生成器的编泽和运行 169 第8章X86汇编代码生成- .170 8.1本章课程设计概述 170 IV
目录 IV 6.2.1 符号表的设计与组织........................................................................................................145 6.2.2 对AST的语义分析.............................................................................................................145 6.2.3 在语法分析的同时进行语义分析....................................................................................145 第 7 章 MIPS汇编代码生成..............................................................................................................146 7.1 本章课程设计概述 ...................................................................................................................146 7.2 汇编代码的内部表示 ...............................................................................................................147 7.2.1 设计概述............................................................................................................................147 7.2.2 示例....................................................................................................................................148 7.3 MIPS R2000/R3000 架构、汇编语言及SPIM..........................................................................151 7.3.1 MIPS R2000/R3000 架构概述............................................................................................151 7.3.2 汇编语言的语法................................................................................................................152 7.3.3 寄存器................................................................................................................................153 7.3.4 汇编指令............................................................................................................................155 7.3.5 过程调用............................................................................................................................159 7.4 MIPS汇编语言与SKIPOOMINIJOOL语言中部分结构的对应 ................................................160 7.4.1 程序....................................................................................................................................160 7.4.2 全局变量的定义和引用....................................................................................................161 7.4.3 方法的定义........................................................................................................................161 7.4.4 方法的调用........................................................................................................................162 7.4.5 if语句 ..................................................................................................................................163 7.4.6 while语句............................................................................................................................163 7.4.7 return语句...........................................................................................................................164 7.5 SPIM...........................................................................................................................................164 7.5.1 XSpim和PCSpim .................................................................................................................164 7.6 SPIM提供的系统调用...............................................................................................................165 7.7 全局寄存器分配器 ...................................................................................................................166 7.7.1 与汇编代码生成器的关系................................................................................................166 7.7.2 使用方法............................................................................................................................166 7.8 课程设计 5-1.............................................................................................................................167 7.8.1 课程设计指导....................................................................................................................167 7.8.2 汇编代码生成器的编译和运行........................................................................................168 7.9 课程设计 5-2.............................................................................................................................168 7.9.1 课程设计指导....................................................................................................................169 7.9.2 汇编代码生成器的编译和运行........................................................................................169 第 8 章 X86 汇编代码生成................................................................................................................170 8.1 本章课程设计概述 ...................................................................................................................170
目录 82x86架构、汇编语言及工具 170 8.2.1数据类型与指令.… .170 82.2寄存器 171 82.3操作数的格式 .171 8.2.4理序线.… 172 82.5一些常用的指令 172 8.2.6gcc与gdb. .176 8.3一些语句到x86汇编代码的映射 .17 8.3.1总体生成的ǐ端代码结想 177 8.4X86寄存器分配器 180 85课程设计61. .182 8.5.1课程设计指导。 182 85.2汇编代码生成器的编译和运行 8.6课程设计6-2. 183 第9章综合课程设计。 .185 9.1课程设计内容 185 9.2课程设计开发的目录结构 185 9.3课程设计提交的目录结构 l85 9,4课程设计的时间节点。 .186 9.5课程设计的考评方法 .186 参考文献 .188 附录 .189 附录1 MINIJOOL语言的词法记号D 189 附录2算符的优先级与结合性 189 附录3 MINUJOOL语言语法的EBNF表示. l91 附录4 SIMPLEMINLJOOL语言语法的EBNF表示. .193 附录5 SKIPOOMINIJOOLI语言语法的EBNF表示 .194 附录6语法结构与AST节点的对应关系 .196 附录7MIPS汇编语言的EBNF定义 .198 附录8X86的AT&T汇编汇编语言的EBNF定义 .200
目录 V 8.2 X86 架构、汇编语言及工具.....................................................................................................170 8.2.1 数据类型与指令................................................................................................................170 8.2.2 寄存器................................................................................................................................171 8.2.3 操作数的格式....................................................................................................................171 8.2.4 程序栈................................................................................................................................172 8.2.5 一些常用的指令................................................................................................................172 8.2.6 gcc与gdb .............................................................................................................................176 8.3 一些语句到X86 汇编代码的映射 ............................................................................................177 8.3.1 总体生成的汇编代码结构................................................................................................177 8.4 X86 寄存器分配器.....................................................................................................................180 8.5 课程设计 6-1.............................................................................................................................182 8.5.1 课程设计指导....................................................................................................................182 8.5.2 汇编代码生成器的编译和运行........................................................................................183 8.6 课程设计 6-2.............................................................................................................................183 第 9 章 综合课程设计........................................................................................................................185 9.1 课程设计内容 ...........................................................................................................................185 9.2 课程设计开发的目录结构 .......................................................................................................185 9.3 课程设计提交的目录结构 .......................................................................................................185 9.4 课程设计的时间节点 ...............................................................................................................186 9.5 课程设计的考评方法 ...............................................................................................................186 参考文献..............................................................................................................................................188 附 录..................................................................................................................................................189 附录 1 MINIJOOL语言的词法记号ID..........................................................................................189 附录 2 算符的优先级与结合性....................................................................................................189 附录 3 MINIJOOL语言语法的EBNF表示....................................................................................191 附录 4 SIMPLEMINIJOOL语言语法的EBNF表示 ........................................................................193 附录 5 SKIPOOMINIJOOL语言语法的EBNF表示.......................................................................194 附录 6 语法结构与AST节点的对应关系 ....................................................................................196 附录 7 MIPS汇编语言的EBNF定义 ............................................................................................198 附录 8 X86 的AT&T汇编汇编语言的EBNF定义........................................................................200
第1章概述 第1章概述 1.1本书的目标 编译原理是构造编译器的重要理论和技术基础。随者计算机技术和社会应用需求的发 展，编译原理及技术也越来越多地运用在诸如编辑器、排版系统、数据处理等更广阔的领域， 因此《编译原理》这门课程对于计算机及相关专业的本科生来说也越来越显得重要。 在实际的《编译原理》教学和学习中，大家普遍认为这门课程非常抽象而难学，剖析其 中的主要原因是实践环节比较薄弱。一方面是缺少系统的编译原理实验教材，另一方面是学 生很少实践或实践的深度不够。 十几年来，中国科学技术大学计算机专业学生的编译原理实验一直以阅读和扩展P心 语言的编译器为基础。PL0语言过于简单，甚至没有函数参数，这就限制了以这个语言为 基础的编译原理课程实践的深度和意义。另外，实验主要停留在阅读PL0编译器已有的源 代码层次上，学生实际动手很少。而要掌捏编译原理的知识，实践是非常重要的。很显然 这种实验设置已经不能适应教学的需要和对不断发展的编译技术的学习理解。 为给计算机及相关专业的学生设计合适的编译原理课程实验，笔者调研了一些国外知名 大学的编译原理实验设置。他们的编译实验已经非常成熟，并且与课程很好地搭配，覆盖了 编译原理的主要知识点，这些经验值得我们借鉴。例如，加州大学伯克利分校、加州理工 学院等学校的编译原理课程实验，尽管它们在实验语言的定义上有所差别，但是都要求在 一个学期内实现一个简单的高级语言，也就是要完成一个功能完备的编译器：此外，加州大 学伯克利分校还要求学生实现词法分析器和语法分析器的生成器，在难度上就更高一些。 这些编译实验的设计对当前的编译技术考虑得很周到，定义的语言一般具有面向对象的 特性，符合现代高级语言的特征。从学生的角度来看，实验的难度较大，但实验的设计遵循 了循序渐进的原则，在必要的时候给予学生足够的帮助。这使得学生能保持对这种技术的兴 趣，并且学生成功完成一个实验所获得的成就感会激发他们挑战更高难度的实验任务。学生 在完成一个学期的实验后，对编译原理与技术的理论知识可以理解得更加透彻：而实验中涉 及到的对一些编程语言和工具环境的使用，更是为学生积累了宝贵的实践经验，学生的动手 能力和科研能力都会有大幅度的提升。 在加州大学伯克利分校的编译实验设置基础上，笔者和曾经的一些学生（他们是吕博海、 赵雷、周清博、王伟、张吴中、李勋浩)一起尝试做这些实验，然后设计适合国内学校学生 的编译原理课程实验。目前，整个课程实验设计尚未全部完成，但是主体部分已成系统。这 本书即是反映我们当前的主要成果，其中一部分的内容还很粗糙，需要进一步的完善。 笔者热忱欢迎大家对本书提出宝贵的意见，并将吸纳其中的精髓，来继续完善这本书： Ras Bodik.UC Berkeley CS164 Pro Compilers Fall 003. http://www.cs.caltech.edu/courses/cs134/cs134b/
第 1 章 概述 1 第1章 概述 1.1 本书的目标 编译原理是构造编译器的重要理论和技术基础。随着计算机技术和社会应用需求的发 展，编译原理及技术也越来越多地运用在诸如编辑器、排版系统、数据处理等更广阔的领域， 因此《编译原理》这门课程对于计算机及相关专业的本科生来说也越来越显得重要。 在实际的《编译原理》教学和学习中，大家普遍认为这门课程非常抽象而难学，剖析其 中的主要原因是实践环节比较薄弱。一方面是缺少系统的编译原理实验教材，另一方面是学 生很少实践或实践的深度不够。 十几年来，中国科学技术大学计算机专业学生的编译原理实验一直以阅读和扩展 PL/0 语言的编译器为基础。PL/0 语言过于简单，甚至没有函数参数，这就限制了以这个语言为 基础的编译原理课程实践的深度和意义。另外，实验主要停留在阅读 PL/0 编译器已有的源 代码层次上，学生实际动手很少。而要掌握编译原理的知识，实践是非常重要的。很显然， 这种实验设置已经不能适应教学的需要和对不断发展的编译技术的学习理解。 为给计算机及相关专业的学生设计合适的编译原理课程实验，笔者调研了一些国外知名 大学的编译原理实验设置。他们的编译实验已经非常成熟，并且与课程很好地搭配，覆盖了 编译原理的主要知识点，这些经验值得我们借鉴。例如，加州大学伯克利分校 1 、加州理工 学院 2 等学校的编译原理课程实验，尽管它们在实验语言的定义上有所差别，但是都要求在 一个学期内实现一个简单的高级语言，也就是要完成一个功能完备的编译器；此外，加州大 学伯克利分校还要求学生实现词法分析器和语法分析器的生成器，在难度上就更高一些。 这些编译实验的设计对当前的编译技术考虑得很周到，定义的语言一般具有面向对象的 特性，符合现代高级语言的特征。从学生的角度来看，实验的难度较大，但实验的设计遵循 了循序渐进的原则，在必要的时候给予学生足够的帮助。这使得学生能保持对这种技术的兴 趣，并且学生成功完成一个实验所获得的成就感会激发他们挑战更高难度的实验任务。学生 在完成一个学期的实验后，对编译原理与技术的理论知识可以理解得更加透彻；而实验中涉 及到的对一些编程语言和工具环境的使用，更是为学生积累了宝贵的实践经验，学生的动手 能力和科研能力都会有大幅度的提升。 在加州大学伯克利分校的编译实验设置基础上，笔者和曾经的一些学生（他们是吕博海、 赵雷、周清博、王伟、张昊中、李勋浩）一起尝试做这些实验，然后设计适合国内学校学生 的编译原理课程实验。目前，整个课程实验设计尚未全部完成，但是主体部分已成系统。这 本书即是反映我们当前的主要成果，其中一部分的内容还很粗糙，需要进一步的完善。 笔者热忱欢迎大家对本书提出宝贵的意见，并将吸纳其中的精髓，来继续完善这本书！ 1 Ras Bodik. UC Berkeley CS164 Programming Languages and Compilers, Fall 2003. http://www.cs.berkeley.edu/~bodik/cs164-fall-2003/ 2 Jason Hickey. Caltech Compiler Design Laboratory. http://www.cs.caltech.edu/courses/cs134/cs134b/
第1章概述 1.2课程设计结构 这一节将介绍综合的编译原理课程设计任务。我们将从要实现的源语言、使用的抽象语 法树Abstract Syntax Tree,.AST)和课程设计的选题等米介绍。 1.2.1要实现的源语言 这本书中引入了三种课程设计用的源语言，在第2章将详细描述这些语言的特点 ·MiniJOOL语言：一种类似Java的小型面向对象语言。在2.1-2.3节给出了这种语 言的描述，在附录3中给出了这种语言的文法描述。 ●SimpleMiniJOOL语言：它是MiniJOOL语言的一个简单子集，不具有面向对象特 征。'一个SimpleMiniJOOL程序只有一个名为Program的类，且类中只有一个静态 的、名为main的函数。在这种语言中，只有整型类型，因此变量无须定义即可使 用。在24节给出了这种语言的简要描述，在附录4中给出了这种语言的文法描述。 ·SkipOOMiniJOOL语言：它扩展了SimpleMiniJOOL语言，但是程序中只有一个名 为Program的类，不过类中仅支持多个静态域和方法。它仍然是MiniJOOL语言的 子集，包含了MiniJOOL语言的所有非面向对象特征.在这个语言中，有int,boolean 和String类型以及一维数组类型。在2.5节中给出了这种语言的简要描述，2.6节 给出这种语言静态语义的形式描述，附录5给出了这种语言的文法描述。 为简便起见，我们将用上述三种语言编写的程序的扩展名都定义为m。在附录1中给 出了三种语言涉及的终结符（记号）名及对应的串值。 在下面的课程设计任务的各个选题中，我们要求你应该实现SimpleMiniJOOL语言，然 后再扩展来实现SkipOOMiniJOOL语言。对于面向对象部分，即完整的MiniJOOL语言， 我们则不做要求。 1.2.2抽象语法树 在本书的所有课程设计中，抽象语法树(Abstract Syntax Tree,.AST)是其中关键的数据 结构之一，它是编译器中常用的中间表示形式之一，能够清楚地反映源程序的语法结构。本 书以这个结构为接口来分解一个完整编译器的各个任务，从而使你只需做一个完整编译器的 部分工作，而这些工作同时又能和其他学生或者本书提供的工作装配到一起，形成一个完整 的编译器。 为了简少编程的工作量，本书采用Eclipse的JDT(Java Development Tools)提供的AST 类层次结构。关于EclipseAST结构和使用说明将在3.5节中详细介绍。 你需要在课程设计前期熟悉Eclipse AST,你还要学会怎么编写AST的访问者类（参见 3.6.2节)。你可以从第3章的课程设计入手来学习和了解它们。不论你选择12.3节中的哪 一个选题，你都需要首先了解这个AST,它是课程设计的基础
第 1 章 概述 2 1.2 课程设计结构 这一节将介绍综合的编译原理课程设计任务。我们将从要实现的源语言、使用的抽象语 法树(Abstract Syntax Tree, AST)和课程设计的选题等来介绍。 1.2.1 要实现的源语言 这本书中引入了三种课程设计用的源语言，在第 2 章将详细描述这些语言的特点。 z MiniJOOL 语言：一种类似 Java 的小型面向对象语言。在 2.1~2.3 节给出了这种语 言的描述，在附录 3 中给出了这种语言的文法描述。 z SimpleMiniJOOL 语言：它是 MiniJOOL 语言的一个简单子集，不具有面向对象特 征。一个 SimpleMiniJOOL 程序只有一个名为 Program 的类，且类中只有一个静态 的、名为 main 的函数。在这种语言中，只有整型类型，因此变量无须定义即可使 用。在 2.4 节给出了这种语言的简要描述，在附录 4 中给出了这种语言的文法描述。 z SkipOOMiniJOOL 语言：它扩展了 SimpleMiniJOOL 语言，但是程序中只有一个名 为 Program 的类，不过类中仅支持多个静态域和方法。它仍然是 MiniJOOL 语言的 子集，包含了 MiniJOOL 语言的所有非面向对象特征。在这个语言中，有 int、boolean 和 String 类型以及一维数组类型。在 2.5 节中给出了这种语言的简要描述，2.6 节 给出这种语言静态语义的形式描述，附录 5 给出了这种语言的文法描述。 为简便起见，我们将用上述三种语言编写的程序的扩展名都定义为 mj。在附录 1 中给 出了三种语言涉及的终结符（记号）名及对应的串值。 在下面的课程设计任务的各个选题中，我们要求你应该实现 SimpleMiniJOOL 语言，然 后再扩展来实现 SkipOOMiniJOOL 语言。对于面向对象部分，即完整的 MiniJOOL 语言， 我们则不做要求。 1.2.2 抽象语法树 在本书的所有课程设计中，抽象语法树（Abstract Syntax Tree, AST）是其中关键的数据 结构之一，它是编译器中常用的中间表示形式之一，能够清楚地反映源程序的语法结构。本 书以这个结构为接口来分解一个完整编译器的各个任务，从而使你只需做一个完整编译器的 部分工作，而这些工作同时又能和其他学生或者本书提供的工作装配到一起，形成一个完整 的编译器。 为了简少编程的工作量，本书采用 Eclipse 的 JDT（Java Development Tools）提供的 AST 类层次结构。关于 Eclipse AST 结构和使用说明将在 3.5 节中详细介绍。 你需要在课程设计前期熟悉Eclipse AST，你还要学会怎么编写AST的访问者类(参见 3.6.2 节)。你可以从第 3 章的课程设计入手来学习和了解它们。不论你选择 1.2.3 节中的哪 一个选题，你都需要首先了解这个AST，它是课程设计的基础
第1章概述 1.2.3课程设计选题 下面列出儿个课程设计的选题，我们给出每个选题的输入和输出，以及这个选题的功能 要求。其中，每个选题要实现的源语言在1.21节中已做规定，即你所做的部分必须能实现 SimpleMiniJOOL语言，这是一个基本要求。你可以在此基础上进行扩展，直至实现 SkipOOMiniJOOL语言. 1.23.1选题一：实现一个语言的解释器 输入：源语言程序对应的AST 输出：输出对该AST解释执行的结果 功能要求：在解释执行中，要对不合法的AST节点进行异常检查和处理。 你需要用文字描述你的解释器中所处理的异常情况。你也需要构造一些测试用例来测试 你的程序，你所构造的测试用例有两类：一类是自己手工编码构造的AST:另一类是编写 m程序，再利用其他的分析器来生成所需要的AST。你也需要用文字说明你的设计实现关 键以及你的测试用例的设计意图。 12.3.2选题二：语法分析器的生成 输入：源语言程序 输出：该源语言程序对应的AST 功能要求：你将使用分析器的生成工具PIex和CUP来完成对源语言程序的词法分析 和语法分析。你要对输入的不合法程序进行异常处理。 你需要用文字描述你所处理的异常情况。你也需要编写m程序，再利用我们提供的 ASTViewer(见第3章)来图形化显示你所构造的AST,你还需要和其他同学实现的解释器 或代码生成器集成来形成一个完整的编译器。你需要用文字说明你的设计实现关键以及你的 测试用例的设计意图。 123.3选题三：类型检查器 输入：源语言程序对应的AST 输出：是否满足类型要求 功能要求：你需要对不合法的AST进行错误定位以及必要的错误恢复处理。 你需要用文字描述你所处理的异常情况，你也需要参照选题一米编写测试用例。你还需 要和其他同学实现的分析器、解释器或代码生成器集成来形成一个完整的编译器。你需要用 文字说明你的设计实现关键以及你的测试用例的设计意图。 1.2.34选题四：x86汇编代码生成器 输入：源语言程序对应的中间表示（如AST) 输出：对应的x86汇编代码文件 功能要求：输出的x86汇编代码应能用gc汇编而得到可执行文件，运行可执行文件可 以得到正确的执行结果。 3
第 1 章 概述 3 1.2.3 课程设计选题 下面列出几个课程设计的选题，我们给出每个选题的输入和输出，以及这个选题的功能 要求。其中，每个选题要实现的源语言在 1.2.1 节中已做规定，即你所做的部分必须能实现 SimpleMiniJOOL语言，这是一个基本要求。你可以在此基础上进行扩展，直至实现 SkipOOMiniJOOL语言。 1.2.3.1 选题一：实现一个语言的解释器 输入：源语言程序对应的 AST 输出：输出对该 AST 解释执行的结果 功能要求：在解释执行中，要对不合法的 AST 节点进行异常检查和处理。 你需要用文字描述你的解释器中所处理的异常情况。你也需要构造一些测试用例来测试 你的程序，你所构造的测试用例有两类：一类是自己手工编码构造的 AST；另一类是编写 mj 程序，再利用其他的分析器来生成所需要的 AST。你也需要用文字说明你的设计实现关 键以及你的测试用例的设计意图。 1.2.3.2 选题二：语法分析器的生成 输入：源语言程序 输出：该源语言程序对应的 AST 功能要求：你将使用分析器的生成工具 JFlex 和 CUP 来完成对源语言程序的词法分析 和语法分析。你要对输入的不合法程序进行异常处理。 你需要用文字描述你所处理的异常情况。你也需要编写 mj 程序，再利用我们提供的 ASTViewer（见第 3 章）来图形化显示你所构造的 AST，你还需要和其他同学实现的解释器 或代码生成器集成来形成一个完整的编译器。你需要用文字说明你的设计实现关键以及你的 测试用例的设计意图。 1.2.3.3 选题三：类型检查器 输入：源语言程序对应的 AST 输出：是否满足类型要求 功能要求：你需要对不合法的 AST 进行错误定位以及必要的错误恢复处理。 你需要用文字描述你所处理的异常情况，你也需要参照选题一来编写测试用例。你还需 要和其他同学实现的分析器、解释器或代码生成器集成来形成一个完整的编译器。你需要用 文字说明你的设计实现关键以及你的测试用例的设计意图。 1.2.3.4 选题四：x86 汇编代码生成器 输入：源语言程序对应的中间表示（如 AST） 输出：对应的 x86 汇编代码文件 功能要求：输出的 x86 汇编代码应能用 gcc 汇编而得到可执行文件，运行可执行文件可 以得到正确的执行结果
第1章概述 你需要用文字描述你的设计实现关键，说明不同的语法结构与汇编代码的映射关系。你 需要考虑寄存器分配、错误检查与处理等问题。你还需要和其他同学实现的分析器集成米形 成一个完整的编译器。你需要用文字说明你的测试用例的设计意图。 1.23.5选题五：MPS32汇编代码生成器 输入：源语言程序对应的中间表示（如AST)》 输出：对应的MPS32汇编代码文件 功能要求：输出的MIPS32汇编代码应能在SPIM模拟器上运行并得到正确的执行结果， 你需要用文字描述你的设计实现关键，说明不同的语法结构与汇编代码的映射关系你需 要考虑寄存器分配、错误检查与处理等问题。你还需要和其他同学实现的分析器集成来形成 一个完整的编译器。你需要用文字说明你的测试用例的设计意图。 1.2.4小结 本节所述的课程设计内容是一个综合的编译原理课程实验。你可以参考后面各章介绍的 局部而循序渐进的课程设计及指导，从而帮助你打开你要完成的课程设计的思路，你可以超 域这些指导，提出更好的设计实理方法。 1.3实验形式及评价 注意：PB0511学生的编译实验要求参见第9章
第 1 章 概述 4 你需要用文字描述你的设计实现关键，说明不同的语法结构与汇编代码的映射关系。你 需要考虑寄存器分配、错误检查与处理等问题。你还需要和其他同学实现的分析器集成来形 成一个完整的编译器。你需要用文字说明你的测试用例的设计意图。 1.2.3.5 选题五：MIPS32 汇编代码生成器 输入：源语言程序对应的中间表示（如 AST） 输出：对应的 MIPS32 汇编代码文件 功能要求：输出的 MIPS32 汇编代码应能在 SPIM 模拟器上运行并得到正确的执行结果。 你需要用文字描述你的设计实现关键，说明不同的语法结构与汇编代码的映射关系你需 要考虑寄存器分配、错误检查与处理等问题。你还需要和其他同学实现的分析器集成来形成 一个完整的编译器。你需要用文字说明你的测试用例的设计意图。 1.2.4 小结 本节所述的课程设计内容是一个综合的编译原理课程实验。你可以参考后面各章介绍的 局部而循序渐进的课程设计及指导，从而帮助你打开你要完成的课程设计的思路，你可以超 越这些指导，提出更好的设计实现方法。 1.3 实验形式及评价 注意：PB0511 学生的编译实验要求参见第 9 章
