编译原理教案(终稿)Word文档格式.docx
《编译原理教案(终稿)Word文档格式.docx》由会员分享，可在线阅读，更多相关《编译原理教案(终稿)Word文档格式.docx（239页珍藏版）》请在冰点文库上搜索。
三、本课程与其它课程的关系
本课程是计算机科学与技术专业的重要专业课。
其先行课有高级程序设计语言、数据结构、离散数学、计算机系统结构、操作系统等。
课程基础性、理论性强，与相关课程的学习联系密切，是计算机科学与技术专业学生进一步提高的基本课程。
四、本课程的基本要求
五、课程内容与学时分配
（一）编译原理概论 2学时
1、教学内容：
什么是编译原理编译过程概述编译程序的结构编译阶段的组合
编译技术和软件工具
2、教学要求：
了解：
编译技术和软件工具。
掌握：
什么是编译原理,编译程序的结构，编译过程和六个阶段的任务和组合。
（二）PL/0编译程序的实现 4学时
PL/0语言描述：
PL/0语言的语法描述图；
PL/0语言文法的EBNF表示
PL/0编译程序的结构
PL/0编译程序的词法分析
PL/0编译程序的语法分析
PL/0编译程序的目标代码结构和代码生成
PL/0编译程序的语法错误处理
PL/0编译程序的目标代码解释执行时的存储分配
PL/0编译程序的词法分析、语法分析、目标代码结构和代码生成、语法错误处理及目标代码解释执行时的存储分配。
PL/0语言的语法描述图及文法的EBNF表示，PL/0编译程序的结构。
（三）文法和语言 4学时
文法的直观概念符号和符号串
文法和语言的形式定义文法的类型
上下文无关文法及其语法树
句型的分析：
自上而下的分析方法；
自下而上的分析方法；
句型分析的有关问题有关文法实用中的一些说明：
有关文法的实用限制；
上下文无关文法中的є规则
文法的直观概念，符号和符号串，上下文无关文法中的є规则。
文法和语言的形式定义。
熟练掌握：
文法的类型，上下文无关文法及其语法树，句型的分析。
（四）词法分析 8学时
词法分析程序的设计：
词法分析程序与语法分析程序的接口方式；
词法分析程序的输出；
将词法分析工作分离的考虑
单词的描述工具：
正规文法；
正规式；
正规文法到正规式
有穷自动机：
确定的有穷自动机（DFA）；
不确定的有穷自动机（NFA）；
DFA→NFA的转换；
确定有穷自动机的化简
正规式和有穷自动机的等价性正规式和有穷自动机间的转换
词法分析程序的自动构造工具：
LEX语言（选讲内容）
词法分析程序与语法分析程序的接口方式和输出；
词法分析工作分离的考虑，LEX语言。
正规文法到正规式。
确定有穷自动机的化简，正规式和有穷自动机的等价性，正规式和有穷自动机间的转换。
（五）自顶向下语法分析方法 6学时
确定的自顶向下分析思想
LL
（1）文法的判别
某些非LL
（1）文法到LL
（1）文法的等价变换不确定的自顶向下分析思想
确定的自顶向下分析方法：
递归子程序法；
预测分析法
不确定的自顶向下分析思想。
确定的自顶向下分析思想，LL
（1）文法的判别，递归子程序法，预测分析法。
某些非LL
（1）文法到LL
（1）文法的等价变换。
（六）自底向上优先分析法 6学时
自底向上优先分析法概述
简单优先分析法：
优先关系；
简单优先文法的定义；
简单优先分析法
算符优先分析法：
直观算符优先分析法；
算符优先分析法的定义；
算符优先关系表的构造；
算符优先分析法；
优先函数；
算符优先分析法的局限性
简单优先分析法。
算符优先分析法。
（七）LR分析法 10学时
LR分析概述
LR（0）分析：
可归前缀和子前缀；
识别活前缀的有限自动机；
活前缀及其可归前缀的一般计算方法；
LR（0）项目集规范族的构造
SLR
（1）分析
LR
（1）分析：
LR
（1）项目集族的构造；
LR
（1）分析表的构造
LALR
（1）分析
二义性文法在LR分析中的应用
SLR
（1）分析，LALR
（1）分析。
LR（0）分析，LR
（1）分析。
（八）语法制导翻译和中间代码生成 10学时
属性文法
语法制导翻译概论
中间代码的形式：
逆波兰记号；
三元式和树形表示；
四元式简单赋值语句的翻译
布尔表达式的翻译：
布尔表达式的翻译方法；
控制语句中布尔表达式的翻译
控制结构的翻译：
条件转移；
开关语句；
for循环语句；
出口语句；
goto语句；
过程调用语句的四元式产生。
说明语句的翻译：
简单说明句的翻译；
过程中的说明
数组和结构的翻译：
数组说明和数组元素的引用；
结构（记录）说明和引用的翻译
中间代码的形式逆波兰记号、三元式和树形表示、四元式。
简单赋值语句、布尔表达式、控制结构、说明语句、数组和结构的翻译。
（九）符号表 4学时
符号表的作用和地位符号的主要属性机作用
符号表的组织：
符号表的总体组织；
符号表项的排列；
关键字域的组织；
其它域的组织；
下推链域的
组织
符号表的管理：
符号表的初始化；
符号的登录；
符号的查找；
符号表中分程序结构层次的管理
符号的主要属性机作用。
符号表的组织。
（十）目标程序运行时的存储组织 6学时
数据空间的三种不同使用方法和管理方法：
静态存储分配；
动态存储分配；
栈式动态存储分配；
堆式动态存储分配
栈式存储分配的实现：
简单的栈式存储分配的实现；
嵌套过程语言的栈式实现；
分程序结构的存储管
理
参数传递：
传值；
传地址；
过程参数
堆式动态存储分配、过程调用、过程进入和过程返回掌握：
静态存储分配，参数的传值、传地址和过程参数
分程序结构的存储管理
（十一）代码优化 8学时
优化技术简介
局部优化：
基本块的划分；
基本块的变换；
基本块的DAG表示；
DAG的应用；
DAG构造算法讨论控制流分析和循环优化：
出现域循环；
循环；
循环的查找；
可规约流图；
循环优化
数据流的分析与全局优化：
一些主要的概念；
数据流方程的一般形式；
到达一定值数据流方程；
可用表达式及其数据流方程；
活跃变量数据流方法；
复写传播
数据流的分析与全局优化。
局部优化、控制流分析和循环优化。
十二、代码生成 6学时
代码生成概述一个计算机模型
一个简单的代码生成器：
寄存器分配的原则；
待用信息链表法；
代码生成算法代码生成研究现状：
中间语言的选择；
代码生成的自动化研究
代码生成研究现状。
代码生成算法。
五、主要参考书目
考试教材：
《编译原理》,吕映芝、张素琴等编著 清华大学出版社。
主要参考书目有；
《Compilers:
Principles,Techniques,andTools/编译原理技术与工具（英文版）》 ALFREDV.AHO,RAVISETHI,JEFFREYD.ULLMAN.
《程序设计语言编译原理》 陈火旺，国防工业出版社，2000
《编译原理及编译程序构造》高仲仪、金茂忠，北京航空学院出版社，1990.12
《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002年
《编译程序原理与技术》李赣生、王华民编著，清华大学出版社
《编译原理技术》陈意云，中国科技大学出版社
《编译原理习题精选》陈意云、张昱著，中国科技大学出版社
授课时间 第一周 第1 次课
授课章节
课程的性质与任务第1章引论
1.1什么是编译程序
1.2编译过程、编译程序的结构
1.3编译程序和软件工具
1.4程序设计语言范型
任课教师及职称
冯玲 讲师
教学方法与手段
多媒体课堂教学
课时安排
2节课
《编译原理》（第2版）张素琴，吕映芝等著，清华大学出版社
Principles, Techniques, and Tools/编译原理技术与工具（英文版）》ALFREDV. AHO,RAVISETHI,JEFFREYD.ULLMAN.
使用教材和主要参考书
教学目的与要求：
本章重点对编译程序的功能和结构做了综合概述,要求学生了解编译程序各个成分在编译阶段的逻辑关系以及它们怎样作为一个整体完成编译任务的。
1了解课程的性质与任务
2理解什么是编译程序
3了解编译过程和编译程序的结构
4为什么要学习编译程序
教学重点，难点：
1.理解理解什么是编译程序
2.了解编译过程和编译程序的结构
教学内容：
课程的性质与任务
•本课程地位属于计算机科学与技术专业的一门重要的专业必修课。
•本课程的学习有助于对语言的执行系统、程序语言的理解。
•通过本课程的学习，要掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造方法。
各种语法分析技术和中间代码生成符号表的构造、代码优化、并行编译技术常识及运行时存储空间的组织等基本方法和主要实现技术。
语言的发展
•机器语言
•汇编语言
•高级语言
•查询语言、标注语言
第1章 编译程序概论
1.1.1语言处理程序
语言处理程序：
把较高级语言编写的程序语义等价地变换成较低级语言程序的程序。
汇编程序
语言处理程序 解释程序编译程序
源程序
目标程序
语言处理程序
（0）语言的执行方式
解释方式（Basic） 口译编译方式（C,pascal） 笔译
（1）汇编程序
汇编程序：
把用汇编语言编写的程序翻译成机器语言的程序。
汇编语言
可重定位的
汇编语言是为特定的计算机或计算机系统设计的面向机器的语言。
如8086/8088PC、Z-80、VAX汇编语言。
汇编的过程就是对汇编指令逐行进行处理，最终得到机器代码的过程。
（2）解释程序
解释程序：
对用高级语言编写的程序进行逐句分析并立即得到结果。
解释程序按源程序中语句的动态顺序逐句进行分析翻译，并立即予以执行，它不产生目标代码。
BASIC APL LISPJava等语言就是采用解释方法实现的。
解释程序
计算结果
初始数据
高级语言解释系统（interpreter）
功能：
让计算机执行高级语言（basic,lisp,prolog）
与编译程序的不同：
1）不生成目标代码2）能支持交互环境（同增量式编译系统）源 程 序
解释系统
直接对源程序中的语句进行分析，执行其隐含的操作。
《编译原理》教案
如：
……
Int2StbLdb
add2Sta
b:
=2 ;
编译程序
a:
= b+2 ;
write a ;
解释程序直接将4的值输出（显示）
（3）编译程序
编译程序：
把用高级语言编写的源程序翻译成等价的低级语言（称作目标语言）程序。
编译系统是编译程序和运行系统的合称。
高级语言 低级语言
一个编译程序把一个高级语言源程序翻译成目标程序的工作可分为前后衔接的六个阶段：
词法分析、语法分析、语义分析、中间代码生成、代码优化及目标代码生成。
大多数高级语言是采用编译的方法实现的。
PASCAL、FORTRAN、ADA、C、C++、PL/1、ALGOL60、ALGOL68,等等。
1.1.2什么是编译程序（compiler）
编译程序是现代计算机系统的基本组成部分.
从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言（称作源语言）书写的程序翻译成另一种语言
（称作目标语言）的等价的程序.
编译程序的功能
术语：
编译程序的源语言（源程序）;
编译程序的目标语言（目标程序）;
编译程序的实现语言;
软件：
计算机系统中的程序及其文档;
系统软件：
居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。
他和具体的应用领域无关，如编译系统和操作系统等。
处理系统：
把软件语言书写的各种程序处理成可在计算机上执行的程序。
软件语言：
用于书写软件的语言。
它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言
编译程序（compiler）;
编译程序的源语言（源程序） （sourcelanguage）（sourceprogram）;
编译程序的目标语言（目标程序）（objectortargetlanguage）（objectortargetprogram）;
编译程序的实现语言（implementationlanguage）;
语言处理程序（languageprocessor）;
语言转（变）换（languagetransformation）
绝对机器码
可重定位机器代码
高级语言程序的处理过程
汇编器
目标汇编程序
可重定位目标文件库
预处理器源程序
装配连接编辑
编译器
13
1.2.1编译逻辑过程
1.2编译过程和结构
（1）词法分析这个阶段的任务是从左至右、从上到下一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。
词法分析后可能返回:
单词类型 单词值
保留字 int
标识符（变量名） a
界符 ;
算符（赋值） =
算符（加） +
整数 2
界符 ；
有关术语
词法分析 从左到右读字符流的源程序、识别（拼）单词。
单词 具有独立意义的基本语法单位。
保留字 具有特殊规定的意义，不允许用户将它们作为别用，是用户定义标识符的禁区。
标识符 用来表示程序、过程、函数、类型、常量和变量等名称的符号。
（2）语法分析
在词法分析的基础上，根据语言的语法规则（文法规则），把单词符号串分解成各类语法单位，如“短语”、“句子”、“程序段”和“程序”。
通过语法分解，确定整个输入串是否构成一个语法上正确的程序。
例:
符号串X+0.168*Y, 经语法分析就可识别出这个字符串属于算术表达式。
Y:
=X+0.168*Y;
语法分析所依循的是语言的语法规则，用产生式描述。
语法分析器读入单词，将它们组合成按产生式规定的各类语法单位。
sum:
=first+count*10
规则
<
赋值语句>
:
=<
标识符>
“:
=”<
表达式>
“+”<
“*”<
=“（”<
“）”
整数>
实数>
赋值语句
表达式
标识符 =
+
标识符 *
标识符 整数
术语
语法：
定义语言各语法成分的形式或结构。
语法分析：
依据源程序的语法规则把源程序的单词序列组成语法短语（表示成语法树）。
语法树（推导树）：
表示句型推导（或归约）的树型结构。
语法树有助于理解一个句子语法结构的层次。
（3）语义分析
语义审查（静态语义）类型匹配
类型转换
例:
Programp（）;
Varrate:
real;
procedureinitial;
…
position:
=initial + rate*60
/*error*/ /*error*/ /*warning*/;
语义分析的一个重要内容是类型检查,对表达式及语句中的各语法成分作类型检查和分析.如:
Var count:
Var first:
Var sum:
real;
=first + count*10
用来定义语言中各语法成份的形式或结构。
语义：
用来规格各语法成份的含义和功能，即规定它们的属性或在执行时应进行的运算或操作。
语义分析：
检查源程序是否包含语义错误，并搜集类型，供后面的代码生成阶段使用，只有语法和语义正确的源程序才可被翻译成目标代码。
语义分析程序需要进行频繁的造表和查表工作。
（4）中间代码生成
语义分析之后生成一种介于源语言和目标语言之间的中间语言代码。
中间代码有多种形式：
三元式、四元式、逆波兰表示、树型结构
19
例：
a:
=b*c
三元式：
逆波兰表示式：
abc*:
=
（1）（*,b,c） 树：
:
=
（2）（:
=,a,
（1）） a *
四元式：
b c
（*,b,c,a）
id1:
=id2+id3*10
因运算需要，需设置临时变量t1,t2,t3来存放中间运算结果。
四元式 （ 算符 第一运算量 第二运算量 运算结果 ）
（1） （inttoreal, 10, -, t1 ）
（2） （*, id3, t1, t2 ）
（3） （+, id2, t2, t3 ）
（4） （:
= , t3, -, id1 ）
中间代码的几种形式
逆波兰表示：
运算符在其运算量之后的表达式。
（OP，ARG1，ARG2）
（OP，ARG1，ARG2，RESULT）
树：
根结点OP，左子树ARG1，右子树ARG2
（5）代码优化
对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和省空间）的目标代码
t1=b*c t1=b*c
t2=t1+0 t2=t1+t1
t3=b*c a=t2
t4=t2+t3a=t4
在本例中，b、c的值没有改变，故t1=t3，由第二个表达式知道t2=t1。
（6）目标代码生成
将前阶段产生的中间代码翻译为机器语言或汇编语言形式的目标程序。
目标程序总是按某一具体计算机的机器语言或汇编语言来产生的。
目标代码生成
（*
id310.0t1 ）
（+
id2t1 id1）
movfid3,R2mulf#10.0,R2movfid2,R1addfR2,R1movfR1,id1
（7）符号表管理
符号表管理：
记录源程序中使用的名字,收集每个名字的各种属性信息:
类型、作用域、分配存储信息在编译过程中，源程序中的标识符及其各种属性都要记录在符号表中，这些属性可以提供标识符的存储分配信息、类型信息、作用域信息等等。
对于过程标识符，还要有参数信息，包括参数的个数和类型、实参和形参的结合方式等等。
符号表结构
符号表是一种含记录
升级会员 