《编译原理》教学大纲

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体系文法分类。

5CFG的语法树

主要知识点:语法树;短语;句柄;推导;规约。

6CFG的二义性

主要知识点:CFG的二义性。

第三章    词法分析

1.教学基本要求

理解词法分析器的功能,掌握单词描述的方法。

2.要求学生掌握的基本概念、理论、技能

通过本章学习,使学生理解词法分析的功能,掌握文法描述的方法,如正则文法、正则表达式、有穷状态自动机、状态转换图等。

3.教学重点和难点

教学重点是单词的描述。教学难点是单词的描述,单词的识别。

4.教学内容

1)词法分析器的功能

主要知识点:单词的分类与表示;词法分析器的输出;源程序的输入缓冲与预处理;词法分析器的位置。

2)单词的描述

主要知识点:正则文法;正则表达式;有穷状态自动机;状态转换图;正则表达式转换为状态转换图。

3)单词的识别

主要知识点:有穷状态自动机与单词识别的关系;单词识别的状态转换图表示;集中典型的单词识别问题;状态转换图的实现。

第四章    自顶向下的语法分析

1.教学基本要求

理解自顶向下分析思想,掌握LL(1)文法的自顶向下分析

2.要求学生掌握的基本概念、理论、技能

通过本章学习,使学生理解确定的自顶向下分析思想,掌握LL(1)文法的自顶向下分析,了解不确定的自顶向下分析思想,掌握预测分析方法进行确定的自顶向下分析

3.教学重点和难点

教学重点是LL1)文法,预测分析法。教学难点是LL1)文法。

4.教学内容

1)语法分析概述

主要知识点:语法分析的概要说明。

2)自顶向下的语法分析面临的问题与文法改造

主要知识点:自顶向下分析面临的问题;对上下文无关文法的改造;LL1)文法。

3)预测分析法

主要知识点:预测分析法的构成;预测分析法的构造;预测分析中错误的处理。

第五章    自底向上的语法分析

1.教学基本要求

理解自底向上分析方法,了解算符优先分析法,掌握LR分析法

2.要求学生掌握的基本概念、理论、技能

通过本章学习,使学生理解自顶向下分析的基本思想,熟悉预测分析器的总体结构,掌握LR0)、LR1)、SLR1)等文法的预测分析表的构造方法,了解算符优先分析法的基本思想。

3.教学重点和难点

教学重点是LR分析法。教学难点是算符优先分析法,LR分析法。

4.教学内容

1)自底向上的语法分析概述

主要知识点:移进-归约分析;优先法;状态法。

2)算符优先分析法

主要知识点:算符优先文法;算符优先矩阵的构造;算符优先分析算法;优先函数;算符优先分析的出错处理。

3LR分析法

主要知识点:LR分析算法;LR0)分析表的构造;SLR1)分析表的构造;LR1)分析表的构造;二义性文法的应用;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年。