编译原理教案(终稿)Word文档格式.docx

1、三、本课程与其它课程的关系本课程是计算机科学与技术专业的重要专业课。其先行课有高级程序设计语言、数据结构、离散数学、计算机系统结构、操作系统等。课程基础性、理论性强，与相关课程的学习联系密切，是计算机科学与技术专业学生进一步提高的基本课程。四、本课程的基本要求五、课程内容与学时分配（一）编译原理概论2 学时1、教学内容：什么是编译原理编译过程概述 编译程序的结构编译阶段的组合编译技术和软件工具2、教学要求：了解：编译技术和软件工具。掌握：什么是编译原理, 编译程序的结构，编译过程和六个阶段的任务和组合。（二）PL/0 编译程序的实现4 学时PL/0 语言描述：PL/0 语言的语法描述图；PL/

2、0 语言文法的 EBNF 表示PL/0 编译程序的结构PL/0 编译程序的词法分析PL/0 编译程序的语法分析PL/0 编译程序的目标代码结构和代码生成PL/0 编译程序的语法错误处理PL/0 编译程序的目标代码解释执行时的存储分配PL/0 编译程序的词法分析、语法分析、目标代码结构和代码生成、语法错误处理及目标代码解释执行时的存储分配。PL/0 语言的语法描述图及文法的 EBNF 表示，PL/0 编译程序的结构。（三）文法和语言4 学时文法的直观概念符号和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析：自上而下的分析方法；自下而上的分析方法；句型分析的有关问题有关文法

3、实用中的一些说明：有关文法的实用限制；上下文无关文法中的 规则文法的直观概念，符号和符号串，上下文无关文法中的 规则。文法和语言的形式定义。熟练掌握：文法的类型，上下文无关文法及其语法树，句型的分析。（四）词法分析8 学时词法分析程序的设计：词法分析程序与语法分析程序的接口方式；词法分析程序的输出；将词法分析工作分离的考虑单词的描述工具：正规文法；正规式；正规文法到正规式有穷自动机：确定的有穷自动机（DFA）；不确定的有穷自动机（NFA）；DFA NFA 的转换；确定有穷自动机的化简正规式和有穷自动机的等价性正规式和有穷自动机间的转换词法分析程序的自动构造工具：LEX 语言（选讲内容）词法分析

4、程序与语法分析程序的接口方式和输出；词法分析工作分离的考虑，LEX 语言。正规文法到正规式。确定有穷自动机的化简，正规式和有穷自动机的等价性，正规式和有穷自动机间的转换。（五）自顶向下语法分析方法6 学时确定的自顶向下分析思想LL（1）文法的判别某些非 LL（1）文法到 LL（1）文法的等价变换不确定的自顶向下分析思想确定的自顶向下分析方法：递归子程序法；预测分析法不确定的自顶向下分析思想。确定的自顶向下分析思想，LL（1）文法的判别，递归子程序法，预测分析法。某些非 LL（1）文法到 LL（1）文法的等价变换。（六）自底向上优先分析法6 学时自底向上优先分析法概述简单优先分析法：优先关系；简

5、单优先文法的定义；简单优先分析法算符优先分析法：直观算符优先分析法；算符优先分析法的定义；算符优先关系表的构造；算符优先分析法；优先函数；算符优先分析法的局限性简单优先分析法。算符优先分析法。（七）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 学时属性

6、文法语法制导翻译概论中间代码的形式：逆波兰记号；三元式和树形表示；四元式简单赋值语句的翻译布尔表达式的翻译：布尔表达式的翻译方法；控制语句中布尔表达式的翻译控制结构的翻译：条件转移；开关语句；for 循环语句；出口语句；goto 语句；过程调用语句的四元式产生。说明语句的翻译：简单说明句的翻译；过程中的说明数组和结构的翻译：数组说明和数组元素的引用；结构（记录）说明和引用的翻译中间代码的形式逆波兰记号、三元式和树形表示、四元式。简单赋值语句、布尔表达式、控制结构、说明语句、数组和结构的翻译。（九）符号表4 学时符号表的作用和地位 符号的主要属性机作用符号表的组织：符号表的总体组织；符号表项的排

7、列；关键字域的组织；其它域的组织；下推链域的组织符号表的管理：符号表的初始化；符号的登录；符号的查找；符号表中分程序结构层次的管理符号的主要属性机作用。符号表的组织。（十）目标程序运行时的存储组织6 学时数据空间的三种不同使用方法和管理方法：静态存储分配；动态存储分配；栈式动态存储分配；堆式动态存储分配栈式存储分配的实现：简单的栈式存储分配的实现；嵌套过程语言的栈式实现；分程序结构的存储管理参数传递：传值；传地址；过程参数堆式动态存储分配、过程调用、过程进入和过程返回掌握：静态存储分配，参数的传值、传地址和过程参数分程序结构的存储管理（十一）代码优化8 学时优化技术简介局部优化：基本块的划分；

8、基本块的变换；基本块的 DAG 表示；DAG 的应用；DAG 构造算法讨论控制流分析和循环优化：出现域循环；循环；循环的查找；可规约流图；循环优化数据流的分析与全局优化：一些主要的概念；数据流方程的一般形式；到达一定值数据流方程；可用表达式及其数据流方程；活跃变量数据流方法；复写传播数据流的分析与全局优化。局部优化、控制流分析和循环优化。十二、代码生成6 学时代码生成概述 一个计算机模型一个简单的代码生成器：寄存器分配的原则；待用信息链表法；代码生成算法代码生成研究现状：中间语言的选择；代码生成的自动化研究代码生成研究现状。代码生成算法。五、主要参考书目考试教材：编译原理,吕映芝、张素琴等编著

9、清华大学出版社。主要参考书目有；Compilers: Principles, Techniques, and Tools/编译原理技术与工具（英文版）ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN.程序设计语言编译原理陈火旺，国防工业出版社， 2000编译原理及编译程序构造高仲仪、金茂忠，北京航空学院出版社，1990.12编译原理胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002 年编译程序原理与技术李赣生、王华民编著，清华大学出版社编译原理技术陈意云，中国科技大学出版社编译原理习题精选陈意云、张昱著，中国科技大学出版社授课时间 第一周第 1次课授课章节

10、课程的性质与任务第 1 章 引 论1.1 什么是编译程序1.2 编译过程、 编译程序的结构1.3 编译程序和软件工具1.4 程序设计语言范型任课教师及职称冯玲讲师教学方法与手段多媒体课堂教学课时安排2 节课编译原理（第 2 版）张素琴，吕映芝等著，清华大学出版社Principles,Techniques,andTools/编译原理技术与工具（英文版）ALFRED V.AHO, RAVISETHI, JEFFREY D. ULLMAN.使用教材和主要参考书教学目的与要求：本章重点对编译程序的功能和结构做了综合概述,要求学生了解编译程序各个成分在编译阶段的逻辑关系以及它们怎样作为一个整体完成编译任

11、务的。1 了解课程的性质与任务2 理解什么是编译程序3 了解编译过程和编译程序的结构4 为什么要学习编译程序教学重点，难点：1. 理解理解什么是编译程序2. 了解编译过程和编译程序的结构教学内容：课程的性质与任务 本课程地位属于计算机科学与技术专业的一门重要的专业必修课。 本课程的学习有助于对语言的执行系统、程序语言的理解。 通过本课程的学习，要掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造方法。各种语法分析技术和中间代码生成符号表的构造、代码优化、并行编译技术常识及运行时存储空间的组织等基本方法和主要实现技术。语言的发展 机器语言 汇编语言 高级语言 查询语言、标注

12、语言第 1 章编译程序概论1.1.1 语言处理程序语言处理程序：把较高级语言编写的程序语义等价地变换成较低级语言程序的程序。汇编程序语言处理程序解释程序编译程序源程序目标程序语言处理程序 （0）语言的执行方式解释方式（Basic）口译编译方式（C,pascal）笔译（1） 汇编程序汇编程序：把用汇编语言编写的程序翻译成机器语言的程序。汇编语言可重定位的汇编语言是为特定的计算机或计算机系统设计的面向机器的语言。如 8086/8088 PC、Z-80、VAX 汇编语言。汇编的过程就是对汇编指令逐行进行处理，最终得到机器代码的过程。（2） 解释程序解释程序：对用高级语言编写的程序进行逐句分析并立即得

13、到结果。解释程序按源程序中语句的动态顺序逐句进行分析翻译，并立即予以执行，它不产生目标代码。BASICAPLLISP Java 等语言就是采用解释方法实现的。解释程序计算结果初始数据高级语言解释系统（interpreter）功能：让计算机执行高级语言（basic,lisp,prolog）与编译程序的不同：1）不生成目标代码 2）能支持交互环境（同增量式编译系统） 源程序解释系统直接对源程序中的语句进行分析，执行其隐含的操作。 编译原理教案如： Int 2 St b Ld badd 2 St ab := 2;编译程序a :=b+2;writea;解释程序直接将 4 的值输出（显示）（3） 编译程

14、序编译程序：把用高级语言编写的源程序翻译成等价的低级语言（称作目标语言）程序。编译系统是编译程序和运行系统的合称。高级语言低级语言一个编译程序把一个高级语言源程序翻译成目标程序的工作可分为前后衔接的六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化及目标代码生成。大多数高级语言是采用编译的方法实现的。PASCAL、FORTRAN、ADA、C、C+、PL/1、 ALGOL 60、 ALGOL 68,等等。1.1.2 什么是编译程序（compiler）编译程序是现代计算机系统的基本组成部分.从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言（称作源语言）书写的程序翻译成另一种语

15、言（称作目标语言）的等价的程序.编译程序的功能术语：编译程序的源语言（源程序）;编译程序的目标语言（目标程序）; 编译程序的实现语言;软件：计算机系统中的程序及其文档;系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言编译程序（compiler）;编译程序的源语言（源程序）（source language）（source program）;编译程序的目标

16、语言（目标程序） （object or target language）（object or target program） ;编译程序的实现语言（implementation language）;语言处理程序（language processor）;语言转（变）换（language transformation）绝对机器码可重定位机器代码高级语言程序的处理过程汇编器目标汇编程序可重定位目标文件库预处理器源程序装配连接编辑编译器131.2.1 编译逻辑过程1.2 编译过程和结构（1） 词法分析这个阶段的任务是从左至右、从上到下一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从

17、而识别出一个个单词。词法分析后可能返回:单词类型单词值保留字int标识符（变量名）a界符;算符（赋值）=算符（加）+整数2界符；有关术语词法分析从左到右读字符流的源程序、识别（拼）单词。单词具有独立意义的基本语法单位。保留字具有特殊规定的意义，不允许用户将它们作为别用，是用户定义标识符的禁区。标识符用来表示程序、过程、函数、类型、常量和变量等名称的符号。（2） 语法分析在词法分析的基础上，根据语言的语法规则（文法规则），把单词符号串分解成各类语法单位，如“短语”、“句子”、“程序段”和“程序”。通过语法分解，确定整个输入串是否构成一个语法上正确的程序。 例: 符号串 X+0.168*Y,经语法

18、分析就可识别出这个字符串属于算术表达式。Y:= X+0.168*Y;语法分析所依循的是语言的语法规则，用产生式描述。语法分析器读入单词，将它们组合成按产生式规定的各类语法单位。sum :=first + count * 10规则:=“:=”“+”“*”=“（”实数赋值语句表达式标识符=+标识符*标识符整数术语语法：定义语言各语法成分的形式或结构。语法分析：依据源程序的语法规则把源程序的单词序列组成语法短语（表示成语法树） 。语法树（推导树）：表示句型推导（或归约）的树型结构。语法树有助于理解一个句子语法结构的层次。（3 ）语义分析语义审查（静态语义） 类型匹配类型转换例: Program p（

19、）;Var rate:real; procedure initial;position := initial+rate * 60/* error */* error */* warning */;语义分析的一个重要内容是类型检查,对表达式及语句中的各语法成分作类型检查和分析. 如:Varcount: Varfirst : Varsum :real ;= first+count* 10用来定义语言中各语法成份的形式或结构。语义：用来规格各语法成份的含义和功能，即规定它们的属性或在执行时应进行的运算或操作。语义分析：检查源程序是否包含语义错误，并搜集类型，供后面的代码生成阶段使用，只有语法和语义正

20、确的源程序才可被翻译成目标代码。 语义分析程序需要进行频繁的造表和查表工作。（4 ）中间代码生成语义分析之后生成一种介于源语言和目标语言之间的中间语言代码。中间代码有多种形式：三元式、四元式、逆波兰表示、树型结构19例： a:=b*c三元式：逆波兰表示式：abc* := （1） （*, b, c）树：:=（2） （:=,a,（1）a*四元式：bc（*, b, c, a）id1:= id2 + id3 * 10因运算需要，需设置临时变量 t1,t2,t3 来存放中间运算结果。四元式（算符第一运算量第二运算量运算结果）（1）（inttoreal,10,-,t1） （2）（* ,id3,t1,t2）

21、（3）（+ ,id2,t2,t3）（4）（:=,t3,-,id1）中间代码的几种形式逆波兰表示：运算符在其运算量之后的表达式。（OP，ARG1，ARG2）（OP，ARG1，ARG2，RESULT）树：根结点 OP，左子树 ARG1，右子树 ARG2（5 ）代码优化对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和省空间）的目标代码t1 = b* ct1 = b* ct2 = t1+ 0t2 = t1 + t1t3 = b* ca = t2t4 = t2 + t3 a = t4在本例中，b、c 的值没有改变，故 t1=t3，由第二个表达式知道 t2=t1。（6 ）目标代

22、码生成将前阶段产生的中间代码翻译为机器语言或汇编语言形式的目标程序。目标程序总是按某一具体计算机的机器语言或汇编语言来产生的。目标代码生成（*,id3 10.0 t1）（+id2 t1id1 ）movf id3,R2 mulf #10.0,R2 movf id2,R1 addf R2,R1 movf R1,id1（7） 符号表管理符号表管理：记录源程序中使用的名字,收集每个名字的各种属性信息:类型、作用域、分配存储信息 在编译过程中，源程序中的标识符及其各种属性都要记录在符号表中，这些属性可以提供标识符的存储分配信息、类型信息、作用域信息等等。对于过程标识符，还要有参数信息，包括参数的个数和类型、实参和形参的结合方式等等。符号表结构符号表是一种含记录