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

目录 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 汇编而得到可执行文件，运行可执行文件可以得到正确的执行结果