编译原理 课程教学大纲

1、编译原理与实现课程教学大纲课程编码：07153008课程名称：编译原理与实现英文名称：Compiler Principle开课学期：6学时/学分：64 / 4 课程类型：学科基础必修课开课专业：软件学院专业本科生选用教材：刘磊 编译原理及实现技术 机械工业出版社 2005主要参考书：1）陈火旺等 程序设计语言编译原理 国防工业出版社 20012）吕映芝，张素琴，蒋维杜 编译原理 清华大学出版社 19983） Alfred V.Aho,Ravi，Sethi，Jeffrey D.Ullman. Compilers: Principles, Techniques, and Tool. Addison

2、 Wesley, 1985.4）Charles N.Fischer, Richard J.LeBlanc. Crafting a Compiler with C. Pearson Education, 1991.执笔人：刘磊一、课程性质、目的与任务编译原理课程是计算机科学与技术专业学生的专业骨干课之一。通过学习这门课程，使学生掌握编译程序的基本原理、方法和实现技术，使学生更好的理解程序语言的内部机制，培养学生初步掌握设计大型系统软件的方法、技术以及设计大型软件的能力。二、教学基本要求1）正确理解什么是编译程序；了解编译程序工作的基本过程及其各阶段的基本任务；熟悉编译程序总框；了解编译程序的生成

3、过程和构造工具。2）正确理解上下文无关文法基本概念，包括：文法的定义、编写、句型、句子、语言、语法树、二义性等；能进行各种文法等价变换；熟练掌握NFA、DFA、正则表达式和正则文法之间的等价关系，能够进行相互转换，掌握DFA的最小化算法。3）理解词法分析器功能及形式；熟练掌握词法分析器设计的原理，掌握运用状态转换图进行词法分析器设计。4）正确理解自上而下分析的基本思想；熟练掌握递归下降分析基本方法：消除左递归和公共前缀，消除回溯，构造递归下降子程序；掌握LL(1)分析程序的基本原理和LL(1)分析表构造；理解LL(1)方法的定义。5）正确理解自下而上语法分析的基本思想，以及归约、短语、句柄、分

4、析树等概念；掌握简单优先分析基本方法：简单优先关系矩阵；LR类语法分析的基本思想及其分析表的构造，掌握LR类语法分析的基本过程。6）理解符号表的作用及符号表组织和使用方法，了解名字的作用范围，了解符号表中一般应包含的内容。7）正确理解语法制导翻译基本原理；熟悉常见的几种中间语言：四元式、三元式、逆波兰表示；掌握各种语句到四元式的翻译方法，包括：简单算术表达式，布尔表达式，控制语句，数组引用，过程调用等。了解自上而下分析制导翻译基本思想和实现方法。8）正确理解代码优化的定义和各种可能的优化概念；掌握基于基本块的局部优化方法。9）正确理解目标程序运行进存储空间的使用和组织管理方式；理解静态分配和动

5、态存储分配基本思想；掌握栈式存储分配的处理方式；掌握栈式动态分配中活动记录和DISPLAY表作用、组织、内容及使用；了解嵌套过程语言程序运行时整个运行栈的内容的组织。10）正确理解代码生成过程的基本问题，理解临时变量、寄存器描述和地址模式等概念；掌握简单代码生成算法。三、各章节内容及学时分配第一章 编译引论（2学时）主要内容：编译程序，编译过程概述，编译程序的结构，编译程序生成，学习构造编译程序。重点：编译程序工作的基本过程及其各阶段的基本任务，编译程序框架。1.1 程序设计语言和编译程序1.2.1 编译程序构成1.2.2 遍1.2.3 编译程序的前端和后端1.3 编译程序和程序设计环境1.4

6、 编译程序的实现第二章 形式语言与有限自动机（8学时）主要内容：上下文无关文法，文法等价变换，语法树与文法二义性，正规表达式与有限自动机。重点：上下文无关文法，正则表达式与有限自动机。2.1 语言和文法2.1.1 基本概念2.1.2 文法分类2.1.3 推导和归约2.1.4 语法树与文法二义性2.1.5 文法等价变换2.2 有限自动机（FA）2.2.1 确定有限自动机（DFA）2.2.2 非确定有限自动机（NFA）2.2.3 DFA与NFA的等价2.2.4 DFA的化简2.3 正则表达式第三章 词法分析（4学时）主要内容：词法分析器任务，词法分析器设计，词法分析器自动生成。重点：词法分析器的任

7、务与设计，状态转换图。3.1 词法分析介绍3.1.1 词法分析程序的功能3.1.2 词法分析程序的接口3.2 词法分析程序的设计3.2.1 单词分类3.2.2 单词的内部表示3.2.3 单词的形式描述3.2.4 自动机的实现3.3 词法分析程序的实现3.3.1 实现词法分析程序应注意的问题3.3.2 标识符表和常量表 HYPERLINK l _Toc104927883 3.3.3 单词结构 HYPERLINK l _Toc104927884 3.3.4 实现算法 HYPERLINK l _Toc104927885 3.4 词法分析程序自动生成 HYPERLINK l _Toc104927886

8、 3.4.1 LEX简介 HYPERLINK l _Toc104927887 3.4.2 LEX工作原理 HYPERLINK l _Toc104927888 3.4.3 LEX源文件结构 HYPERLINK l _Toc104927889 3.4.4 LEX系统中的正则式 HYPERLINK l _Toc104927890 3.4.5 LEX的使用方式 HYPERLINK l _Toc104927891 3.4.6应用实例第四章 语法分析自顶向下分析方法（8学时）主要内容：上下文无关文法，自上而下语法分析（递归下降分析法，LL(1)方法）。重点：上下文无关文法，递归下降子程序，LL(1)分析表

9、构造，LL(1)文法。 HYPERLINK l _Toc104927893 4.1 语法分析程序介绍 HYPERLINK l _Toc104927894 4.1.1 语法分析程序的功能 HYPERLINK l _Toc104927895 4.1.2 语法错误类别及错误处理 HYPERLINK l _Toc104927896 4.1.3 自顶向下语法分析基本思想 HYPERLINK l _Toc104927897 4.1.4 三个重要的集合 HYPERLINK l _Toc104927898 4.1.5 自顶向下语法分析条件 HYPERLINK l _Toc104927899 4.2 递归下降法

10、 HYPERLINK l _Toc104927900 4.2.1 递归下降法语法分析原理 HYPERLINK l _Toc104927901 4.2.2 递归下降法语法分析程序的构造 HYPERLINK l _Toc104927902 4.3 LL(1)分析方法 HYPERLINK l _Toc104927903 4.3.1 LL(1)分析法原理 HYPERLINK l _Toc104927904 4.3.2 LL(1)分析表的构造 HYPERLINK l _Toc104927905 4.3.3 LL(1)驱动程序构造 HYPERLINK l _Toc104927906 4.4 自顶向下分析程

11、序的自动生成第五章 语法分析自底向上分析方法（14学时）主要内容：自下而上语法分析（LR(0),LR(1),SLR(1),LALR(1)等语法分析方法、简单优先分析方法）。重点：简单优先关系矩阵的构造；LR类分析表的构造及其分析过程。 HYPERLINK l _Toc104927908 5.1 自底向上语法分析方法介绍 HYPERLINK l _Toc104927909 5.2 简单优先分析 HYPERLINK l _Toc104927910 5.2.1 简单优先文法及其优先关系矩阵的构造 HYPERLINK l _Toc104927911 5.2.2 简单优先分析算法 HYPERLINK l

12、 _Toc104927912 5.3 LR分析法 HYPERLINK l _Toc104927913 5.3.1 LR类分析法的工作过程 HYPERLINK l _Toc104927914 5.3.2 LR(0)分析方法 HYPERLINK l _Toc104927915 5.3.3 SLR(1)分析方法 HYPERLINK l _Toc104927916 5.3.4 LR(1)分析方法 HYPERLINK l _Toc104927917 5.3.5 LALR(1)分析方法 HYPERLINK l _Toc104927918 5.3.6 LR方法小结 HYPERLINK l _Toc10492

13、7919 5.4 自底向上分析程序的自动生成第六章 语义分析和符号表（8学时）主要内容：语义分析内容、标识符的内部表示、类型的内部表示、值的内部表示。符号表的组织和使用，整理与查找，名字的作用范围，表的内容。程序的语义分析方法。重点：符号表的作用与内容、语义分析原理及过程。 HYPERLINK l _Toc104927921 6.1 语义分析概述 HYPERLINK l _Toc104927922 6.2 标识符的内部表示 HYPERLINK l _Toc104927923 6.3 类型的内部表示 HYPERLINK l _Toc104927924 6.4 值的内部表示 HYPERLINK l

14、 _Toc104927925 6.5 符号表的组织和管理 HYPERLINK l _Toc104927926 6.5.1符号表的总体组织 HYPERLINK l _Toc104927927 6.5.2符号表项的排列 HYPERLINK l _Toc104927928 6.5.3符号表的建立与查找 HYPERLINK l _Toc104927929 6.6嵌套式符号表和分程序结构的管理 HYPERLINK l _Toc104927930 6.6.1简单C语言的符号表 HYPERLINK l _Toc104927931 6.6.2 Pascal语言的符号表 HYPERLINK l _Toc1049

15、27932 6.6.3带有分程序结构的符号表 HYPERLINK l _Toc104927933 6.7 标号的语义分析第七章 中间代码生成（6学时）主要内容：语法制导翻译概述，各种常见中间语言形式，各种语句到四元式的翻译，自下而上分析制导翻译概述。重点：语法制导翻译基本思想；三种中间语言：四元式、三元式、逆波兰表示；算术表达式的翻译，布尔表达式的翻译，控制语句的翻译。 HYPERLINK l _Toc104927935 7.1 常用的中间代码结构 HYPERLINK l _Toc104927936 7.1.1 后缀式 HYPERLINK l _Toc104927937 7.1.2 抽象语法树

16、和DAG HYPERLINK l _Toc104927938 7.1.3三地址中间代码 HYPERLINK l _Toc104927939 7.2 语法制导方法概论 HYPERLINK l _Toc104927940 7.3 类型检查和类型转换 HYPERLINK l _Toc104927941 7.4 中间代码生成中的几个问题 HYPERLINK l _Toc104927942 7.4.1语义信息的获取和保存 HYPERLINK l _Toc104927943 7.4.2语义栈Sem及其操作 HYPERLINK l _Toc104927944 7.4.3常用的语义子程序 HYPERLINK

17、l _Toc104927945 7.5 表达式的中间代码生成 HYPERLINK l _Toc104927946 7.6 下标变量的中间代码生成 HYPERLINK l _Toc104927947 7.6.1 下标变量的地址 HYPERLINK l _Toc104927948 7.6.2 下标变量的四元式结构 HYPERLINK l _Toc104927949 7.6.3 下标变量的中间代码生成 HYPERLINK l _Toc104927950 7.6.4 下标变量中间代码生成例 HYPERLINK l _Toc104927951 7.7 赋值语句的中间代码 HYPERLINK l _Toc

18、104927952 7.8 过程调用和函数调用的中间代码 HYPERLINK l _Toc104927953 7.9 控制语句的中间代码生成 HYPERLINK l _Toc104927954 7.9.1 GOTO语句和标号定位的中间代码 HYPERLINK l _Toc104927955 7.9.2 条件语句的中间代码 HYPERLINK l _Toc104927956 7.9.3 While语句的中间代码 HYPERLINK l _Toc104927957 7.10 过程 函数声明的中间代码生成第八章 中间代码优化（6学时）主要内容：优化概述，局部优化，基本块、程序流程图，常量表达式优化，

19、基于常量定值分析的常表达式全局优化，公共表达式的优化，基于值编码的公共表达式局部优化，循环不变式外提等 。重点：常量表达式优化，公共表达式的优化，基于值编码的公共表达式局部优化，循环不变式外提。 HYPERLINK l _Toc104927959 8.1 优化方法概述 HYPERLINK l _Toc104927960 8.2 基本块划分 HYPERLINK l _Toc104927961 8.3 常量表达式局部优化 HYPERLINK l _Toc104927962 8.4 公共表达式局部优化 HYPERLINK l _Toc104927963 8.5 循环不变式外提 HYPERLINK l

20、 _Toc104927964 8.5.1 循环不变式外提概述 HYPERLINK l _Toc104927965 8.5.2 循环不变式外提原理 HYPERLINK l _Toc104927966 8.6 其它各类优化介绍第九章 运行时存储空间的组织与管理（6学时）主要内容：运行时存储空间结构，运行时存储空间的分配策略，简单的栈式存储分配的实现，过程活动记录，运行时变量的访问以及变量访问环境的三种实现方法。重点：静态分配策略和动态分配策略基本思想，嵌套过程语言栈式分配，活动记录、DISPLAY表、运行时栈的组织。变量访问环境的实现（掌握一种） HYPERLINK l _Toc104927968

21、 9.1 目标程序运行时的活动 HYPERLINK l _Toc104927969 9.1.1 过程的活动 HYPERLINK l _Toc104927970 9.1.2 名字的作用域和绑定 HYPERLINK l _Toc104927971 9.1.3 过程活动记录 HYPERLINK l _Toc104927972 9.1.4 抽象地址分配 HYPERLINK l _Toc104927973 9.1.5 参数传递 HYPERLINK l _Toc104927974 9.2 运行时存储器的划分 HYPERLINK l _Toc104927975 9.3 静态存储分配 HYPERLINK l

22、_Toc104927976 9.4 简单的栈式存储分配 HYPERLINK l _Toc104927977 9.5 嵌套式语言的栈式存储分配 HYPERLINK l _Toc104927978 9.5.1局部Display表方法 HYPERLINK l _Toc104927979 9.5.2静态链方法 HYPERLINK l _Toc104927980 9.5.3全局Display表方法 HYPERLINK l _Toc104927981 9.6 堆式动态存储分配 HYPERLINK l _Toc104927982 9.6.1 堆区的分配策略 HYPERLINK l _Toc104927983

23、 9.6.2 堆区的回收策略 HYPERLINK l _Toc104927984 9.7 过程调用中几种特殊情况的处理 HYPERLINK l _Toc104927985 9.9.1 非正常出口语句 HYPERLINK l _Toc104927986 9.9.2 形式过程语句 HYPERLINK l _Toc104927987 9.9.3 过程的奇特型调用第十章 目标代码生成（2学时）主要内容：目标代码的种类，临时变量的空间分配方法，基于多元式的单寄存器的目标代码生成重点：基于多元式的单寄存器的目标代码生成。 HYPERLINK l _Toc104927989 10.1 目标代码生成介绍 HYPERLINK l _Toc104927990 10