《编译原理》教学大纲
(2013版)
课程编码:0611101802
课程名称:编译原理
学时/学分:32/2
先修课程:《高等数学》、《程序设计基础》、《算法与数据结构》
适用专业:计算机科学与技术
开课教研室:软件工程教研室
执笔:
审定:
一、课程性质与任务
1.课程性质:本课程是计算机科学与技术专业的专业课,是所有计算机科学与技术专业学生的必修课。
2.课程任务:本课程除了教授学生基础理论知识外,含有基本问题求解的典型思路和方法,继程序设计、数据结构等课程后,从系统级再认识程序、算法,根据课程容量和学生特点,选择适当的知识为载体,向学生介绍本学科问题求解的基本思路、方法,使学生主要获得如下收获:
(1)掌握程序变换基本概念、问题描述和处理方法;
(2)掌握“问题、形式化描述、计算机化”的问题求解典型过程,推进从“实例计算”到
“类计算”和“模型计算”的跨越的实现;
(3)从宏观到微观,从微观到宏观,培养系统能力。
二、课程教学基本要求
通过本课程学习要达到如下要求:
1.正确理解什么是编译程序;了解编译程序工作的基本过程及其各阶段的基本任务;熟悉编译程序结构。
2.理解程序语言词法、语法和语义等概念。正确理解上下文无关文法基本概念,包括:文法的定义、推导、句型、句子、语言、语法树、二义性等。
3.理解词法分析器功能及形式;熟练掌握正规文法、正规式、有穷自动机以及三者之间的等价转换,掌握NFA的确定化及化简方法,理解词法分析器设计的原理。
4.正确理解自上而下分析的基本思想;熟练掌握LL(1)分析方法;掌握提取左公因子及消除左递归的方法;掌握预测分析程序的基本原理。
5.正确理解自下而上语法分析的基本思想,理解算符优先分析基本方法,掌握LR(0)分析、SLR(1)分析及LR(1)分析方法。
6.正确理解语法制导翻译基本原理;了解基于属性文法的处理方法。
7.熟悉常见的几种中间代码:四元式、三元式、逆波兰表示;了解简单语句的翻译。
8.理解符号表的作用及符号表的组织和管理方法。
9.正确理解目标程序运行时的存储空间的使用和组织管理方式;了解静态存储分配和动态存储分配基本思想。
10.正确理解代码优化的定义和各种可能的优化概念;掌握用DAG表示进行局部优化的方法。
本课程共计学时:32。
成绩考核形式:末考成绩(闭卷考试)(70%)+平时成绩(平时测验、作业、课堂提问、课堂讨论等)(30%)。成绩评定采用百分制,60分为及格。
三、课程教学内容
第一章 引论
1.教学基本要求
掌握基本的编译原理概念和系统的总体结构。
2.要求学生掌握的基本概念、理论、技能
通过本章教学,使学生掌握基本的概念和系统的总体结构,以激发学生对这门课的兴趣。
3.教学重点和难点
教学重点是编译程序的总体结构。教学难点是编译程序的组织。
4.教学内容
(1)程序设计语言
主要知识点:程序设计语言的分类。
(2)程序设计语言的翻译
主要知识点:翻译程序的种类及特点。
(3)编译程序的总体结构
主要知识点:编译程序总体结构及各模块功能。
(4)编译程序的组织
主要知识点:编译程序的划分方式。
第二章 高级语言及其文法
1.教学基本要求
掌握语言的相关概念及其描述方式。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生掌握包括文法、正则语言、上下文无关文法、语法分析树等相关概念及其描述方式。
3.教学重点和难点
教学重点是文法的定义,文法的分类,CFG的语法树。教学难点CFG的语法树,CFG的二义性。
4.教学内容
(1)语言概述
主要知识点:语言的分类;语言的构成。
(2)基本定义
主要知识点:语言相关基本概念。
(3)文法的定义
主要知识点:文法相关基本定义。
(4)文法的分类
主要知识点:Chomsky体系文法分类。
(5)CFG的语法树
主要知识点:语法树;短语;句柄;推导;规约。
(6)CFG的二义性
主要知识点:CFG的二义性。
第三章 词法分析
1.教学基本要求
理解词法分析器的功能,掌握单词描述的方法。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生理解词法分析的功能,掌握文法描述的方法,如正则文法、正则表达式、有穷状态自动机、状态转换图等。
3.教学重点和难点
教学重点是单词的描述。教学难点是单词的描述,单词的识别。
4.教学内容
(1)词法分析器的功能
主要知识点:单词的分类与表示;词法分析器的输出;源程序的输入缓冲与预处理;词法分析器的位置。
(2)单词的描述
主要知识点:正则文法;正则表达式;有穷状态自动机;状态转换图;正则表达式转换为状态转换图。
(3)单词的识别
主要知识点:有穷状态自动机与单词识别的关系;单词识别的状态转换图表示;集中典型的单词识别问题;状态转换图的实现。
第四章 自顶向下的语法分析
1.教学基本要求
理解自顶向下分析思想,掌握LL(1)文法的自顶向下分析。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生理解确定的自顶向下分析思想,掌握LL(1)文法的自顶向下分析,了解不确定的自顶向下分析思想,掌握预测分析方法进行确定的自顶向下分析。
3.教学重点和难点
教学重点是LL(1)文法,预测分析法。教学难点是LL(1)文法。
4.教学内容
(1)语法分析概述
主要知识点:语法分析的概要说明。
(2)自顶向下的语法分析面临的问题与文法改造
主要知识点:自顶向下分析面临的问题;对上下文无关文法的改造;LL(1)文法。
(3)预测分析法
主要知识点:预测分析法的构成;预测分析法的构造;预测分析中错误的处理。
第五章 自底向上的语法分析
1.教学基本要求
理解自底向上分析方法,了解算符优先分析法,掌握LR分析法。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生理解自顶向下分析的基本思想,熟悉预测分析器的总体结构,掌握LR(0)、LR(1)、SLR(1)等文法的预测分析表的构造方法,了解算符优先分析法的基本思想。
3.教学重点和难点
教学重点是LR分析法。教学难点是算符优先分析法,LR分析法。
4.教学内容
(1)自底向上的语法分析概述
主要知识点:移进-归约分析;优先法;状态法。
(2)算符优先分析法
主要知识点:算符优先文法;算符优先矩阵的构造;算符优先分析算法;优先函数;算符优先分析的出错处理。
(3)LR分析法
主要知识点:LR分析算法;LR(0)分析表的构造;SLR(1)分析表的构造;LR(1)分析表的构造;二义性文法的应用;LR分析表中的出错处理。
第六章 语法制导的翻译与属性文法
1.教学基本要求
理解属性文法及语法制导翻译方法的基本思想。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生理解属性文法及语法制导翻译方法的基本思想,会设计简单文法的语法制导定义和翻译模式。
3.教学重点和难点
教学重点是语法制导定义,翻译模式。教学难点属性计算,翻译模式。
4.教学内容
(1)语法制导翻译概述
主要知识点:语义分析器的主要任务;语法制导翻译的定义及功能。
(2)语法制导定义
主要知识点:综合属性;继承属性;属性文法。
(3)属性计算
主要知识点:依赖图;属性的计算顺序;S-属性定义;L-属性定义。
(4)翻译模式
主要知识点:翻译模式与语义动作的执行时机;S-属性定义的自底向上翻译;L-属性定义的自顶向下翻译;L-属性定义的自底向上翻译。
第七章 语义分析与中间代码生成
1.教学基本要求
理解基于语义分析的中间代码生成,掌握常见的中间代码表达形式,了解简单语句的翻译。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生理解基于语义分析的中间代码生成,掌握中间代码的逆波兰表示、三地址码表示和图表示方法,了解声明语句和赋值语句的翻译。
3.教学重点和难点
教学重点是中间代码的形式。教学难点是声明语句的翻译,赋值语句的翻译。
4.教学内容
(1)中间代码的形式
主要知识点:逆波兰表示;三地址码;图表示。
(2)声明语句的翻译
主要知识点:类型表达式;类型等价;声明语句的文法;过程内声明语句的翻译。
(3)赋值语句的翻译
主要知识点:简单赋值语句的翻译;数组元素的寻址。
第八章 符号表管理
1.教学基本要求
了解符号表的作用,掌握符号表的组织和管理。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生了解符号表的作用和存放的内容,掌握符号表的线性表和散列表实现,了解符号表对作用域的影响。
3.教学重点和难点
教学重点是符号表中存放的信息,符号表的组织结构。教学难点是符号表的组织结构,符号表与作用域。
4.教学内容
(1)符号表的作用
主要知识点:符号表的功能。
(2)符号表中存放的信息
主要知识点:符号表中的名字;符号表中的属性;符号的地址属性。
(3)符号表的组织结构
主要知识点:符号表的线性表实现;符号表的散列表实现。
(4)符号表与作用域
主要知识点:程序块结构的符号表;程序块结构符号表的其他实现;C语言的符号表。
第九章 运行时的存储组织
1.教学基本要求
理解存储组织的分配策略,理解静态存储分配和动态存储分配的实现。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生理解运行时内存划分、局部数据组织及全局存储分配策略,理解静态存储分配和动态存储分配的实现。
3.教学重点和难点
教学重点是存储组织存储分配。教学难点是存储分配。
4.教学内容
(1)与存储组织有关的源语言概念
主要知识点:名字及其绑定;声明的作用域;过程及其活动;参数传递方式;对变长数据及用户自由申请空间的支持。
(2)存储组织
主要知识点:运行时内存的划分;活动记录;局部数据的组织;全局存储分配策略。
(3)存储分配
主要知识点:静态存储分配;动态存储分配。
第十章 代码优化
1.教学基本要求
了解代码优化技术,掌握控制流分析和局部优化,了解数据流分析。
2.要求学生掌握的基本概念、理论、技能
通过本章学习,使学生了解代码优化的常用技术,掌握控制流分析和局部优化方法,了解数据流分析。
3.教学重点和难点
教学重点是优化的种类,局部优化。教学难点是优化分析,局部优化。
4.教学内容
(1)优化的种类
主要知识点:公共子表达式删除;复制传播;无用代码删除;代码外提;强度削弱和归纳变量删除。
(2)优化分析
主要知识点:控制流分析;数据流分析。
(3)局部优化
主要知识点:基本块的DAG表示;局部公共子表达式删除;无用代码删除,代数恒等式的使用;数组引用的DAG表示;指针赋值和过程调用的DAG表示;从DAG到基本块的重组。
四、学时分配
1.讲授内容及学时分配
章序 |
内容 |
课时 |
备注 |
一 |
引论 |
2 |
|
二 |
高级语言及其文法 |
4 |
|
三 |
词法分析 |
2 |
|
四 |
自顶向下的语法分析 |
4 |
|
五 |
自底向上的语法分析 |
6 |
|
六 |
语法制导翻译与属性文法 |
4 |
|
七 |
语义分析与中间代码生成 |
2 |
|
八 |
符号表管理 |
4 |
|
九 |
运行时的存储组织 |
2 |
|
十 |
代码优化 |
2 |
|
合计 |
32 |
|
五、主用教材及参考书
(一)主用教材:
《编译原理》主编:蒋宗礼 出版社:清华大学出版社 出版时间:2010年。
(二)参考书:
1.《编译原理》(第二版)主编:陈意云 出版社:高等教育出版社 出版时间:2008年。
2.《程序设计语言编译原理》主编:陈火旺 出版社:国防科技大学出版社 出版时间:2006年。
3.《编译原理》(第二版)主编:何炎祥 出版社:清华大学出版社 出版时间:2010年。