中国科学技术大学：《编译原理》课程教学资源（教程）编译原理实验教程（草稿）.pdf

目录 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

目录 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

目录 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

目录 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