《编译原理及其习题解答武汉大学出版社课件chap1》由会员分享，可在线阅读，更多相关《编译原理及其习题解答武汉大学出版社课件chap1（48页珍藏版）》请在金锄头文库上搜索。
1、编译原理compilers principlesn学时安排上课：48学时（112周）实验：12学时（510周 周一下午）1课程内容n第一章 引论n第二章 形式语言概论n第三章 有穷自动机n第四章 词法分析n第五章 自上而下语法分析n第六章 自下而上分析和优先分析方法n第七章 自下而上的LR(k)分析方法n第八章 语法制导翻译 n代码优化 2成绩：n平时n实验n期中考查n期末考试3与课程有关的问题：n本课程的性质、目的和任务 ： 本课程是计算机类专业的专业课，目的是使学生了解并掌握编译程序的基本理论和方法，具有分析和实现编译程序的初步能力。 n本课程的基本要求 ： 通过对本课程的学习，对形式语言
2、有初步了解，对编译程序的整个结构有较清楚的了解，熟悉和掌握几种主要编译方法。 n课程内容的重点、深度与广度 ： 文法和形式语言、词法分析和有穷自动机、语法分析语义分析、目标代码的生成，了解符号表的构造、存储分配与管理、代码优化和错误校正(学时所限。)41.课前预习，课后复习2.实践出真知3.力求两境界，克服一状态n境界一：原理理解马马乎乎、做题顺手n境界二：基本掌握编译原理的设计、做题讲究技巧n一状态：听课稀里糊涂、课后与己无关5参考书：n编译原理教程编译原理教程 胡元义胡元义等西安电子科大等西安电子科大n程序设计语言编译原理陈火旺、刘春林等程序设计语言编译原理陈火旺、刘春林等 国防工业出版社
3、国防工业出版社n编译原理编译原理 吕映芝等吕映芝等 清华出版社清华出版社nKenneth C Louden Compiler Construction Principles and Practice 编译原理与实践编译原理与实践, PWS Publishing Company, 1997。中译本。中译本 机械工业出版社机械工业出版社 nAlfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. UllmanCompilers: Principles, Techniques, and Tools (2nd Edition), Addison Wesl
4、ey, 2006 (Dragon book，龙书，龙书)nAndrew W. Appel Modern Compiler Implementation in Java, CambridgeUniversity Press, 2002. 2nd Ed. (Tiger Book，虎书，虎书)nMichael L. Scott Programming Language Pragmatics, Second Edition,Morgan Kaufmann, 2005. (中译本中译本: 程序设计程序设计语言：实践之路语言：实践之路裘宗燕，电子工业出版社裘宗燕，电子工业出版社)6第一章 引 论本节内容：
5、n程序的翻译n编译程序的工作过程n编译程序的结构n编译程序的组织方式n编译程序的构造7编译程序在计算机系统中的位置n分类软件系统软件语言处理系统操作系统编译系统裸机81.1 程序的翻译程序的翻译n1.1.1 程序设计语言程序设计语言机器语言机器语言 001110010010汇编语言汇编语言 add R1 2高级语言高级语言 begin x:=9+2 endn问题问题: 计算机只能识别二进制数计算机只能识别二进制数0、1表示的表示的指令和数构成的本计算机系统的机器指令和数构成的本计算机系统的机器语言。如何让计算机执行高级语言程语言。如何让计算机执行高级语言程序呢？序呢？91.1 程序的翻译程序的
6、翻译n1.1.2 翻译程序翻译程序 所谓翻译程序，是指这样一种程所谓翻译程序，是指这样一种程序，它能将用甲语言（源语言）编写序，它能将用甲语言（源语言）编写的程序翻译成与之等价的用乙语言的程序翻译成与之等价的用乙语言（目标语言）书写的程序。（目标语言）书写的程序。n 程序的翻译通常有两种方式：一是程序的翻译通常有两种方式：一是“编译编译”方式，二是方式，二是“解释解释”方式。方式。101.1 程序的翻译程序的翻译n1.1.3 编译方式编译方式 一种分阶段进行的方式一种分阶段进行的方式1.翻译阶段：翻译阶段： 高级语言或汇编语言源程序高级语言或汇编语言源程序 机器语言目标机器语言目标程序程序2.
7、运行阶段运行阶段目标程序、运行子程序、数据目标程序、运行子程序、数据 运行结果运行结果111.1 程序的翻译程序的翻译3.编译方式的特点编译方式的特点n在编译方式下，源程序的执行需要分阶段。在编译方式下，源程序的执行需要分阶段。 如果目标程序是机器语言程序，如果目标程序是机器语言程序， 则源程序的执则源程序的执行分为两大阶段：编译阶段和运行阶段。行分为两大阶段：编译阶段和运行阶段。 如果目标程序是汇编语言程序，如果目标程序是汇编语言程序， 则源程序的执则源程序的执行分为三大阶段：编译阶段、汇编阶段和运行行分为三大阶段：编译阶段、汇编阶段和运行阶段。阶段。 n编译方式下，生成了目标代码，且可多次
8、执行。编译方式下，生成了目标代码，且可多次执行。 121.1 程序的翻译程序的翻译4.关于编译程序的几点说明关于编译程序的几点说明编译程序生成的目标程序不一定是机器语言的编译程序生成的目标程序不一定是机器语言的程序，也有可能是汇编语言程序；程序，也有可能是汇编语言程序；编译程序编译程序与具体的机器和语言有关与具体的机器和语言有关，即任何一，即任何一个具体的编译程序都是某一特定类型的计算机个具体的编译程序都是某一特定类型的计算机系统中关于某一特定语言的编译程序；系统中关于某一特定语言的编译程序；对编译程序而言，源程序是输入数据，目标程对编译程序而言，源程序是输入数据，目标程序是输出结果。序是输出
9、结果。131.1 程序的翻译程序的翻译n1.1.4 解释方式解释方式 完成解释工作的解释程序将按源程序中语完成解释工作的解释程序将按源程序中语句的动态顺序，逐句地进行分析解释，并立即句的动态顺序，逐句地进行分析解释，并立即予以执行。予以执行。 执行历程为：执行历程为：141.1 程序的翻译程序的翻译n源程序解释执行的历程源程序解释执行的历程 源程序源程序 （高级语言）、初始数据（高级语言）、初始数据 解解释程序程序计计 算算 结结 果果n在解释方式下，并不生成目标代码，而在解释方式下，并不生成目标代码，而是直接执行源程序本身。这是编译方式是直接执行源程序本身。这是编译方式与解释方式的根本区别。
10、与解释方式的根本区别。 151.2 编译程序的工作过程编译程序的工作过程 n词法分析词法分析n语法分析语法分析n语义分析和中间代码生成语义分析和中间代码生成n中间代码优化中间代码优化n目标代码生成目标代码生成161.2 编译程序的工作过程编译程序的工作过程 n1.2.1 词法分析词法分析 依据语言词法规则，分析由字符组成的源依据语言词法规则，分析由字符组成的源程序，把它识别为一个一个具有独立意义的最程序，把它识别为一个一个具有独立意义的最小语法单位，即小语法单位，即“单词单词”，并识别出与其相关，并识别出与其相关的属性的属性(如是标识符，是界限符，还是数，等如是标识符，是界限符，还是数，等等等
11、)，再转换成长度上统一的标准形式，再转换成长度上统一的标准形式(这种统这种统一的标准形式既刻画了单词本身，又刻画了它一的标准形式既刻画了单词本身，又刻画了它所具有的属性，称为属性字所具有的属性，称为属性字)，以供其它部分，以供其它部分使用。使用。 17词法分析n读字符流的源程序、识别单词例： position = initial + rate * 6018词法分析单词类型单词类型单词值单词值 标识符1(id1)position算符(赋值) = 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 分号 ；191.2 编译程序的工作过程编译
12、程序的工作过程 n1.2.2 语法分析语法分析 依据语法规则，逐一分析词法分析时得到依据语法规则，逐一分析词法分析时得到的单词，把单词串分解成各类语法单位，即确的单词，把单词串分解成各类语法单位，即确定它们是怎样组成说明和语句，以及说明和语定它们是怎样组成说明和语句，以及说明和语句又是怎样组成程序的。分析时如发现有不合句又是怎样组成程序的。分析时如发现有不合语法规则的地方，便将出错的位置及出错性质语法规则的地方，便将出错的位置及出错性质打印报告给程序员；如无语法错误，则用另一打印报告给程序员；如无语法错误，则用另一种中间形式给出正确的语法结构，供下一阶段种中间形式给出正确的语法结构，供下一阶段
13、分析使用。分析使用。 20语法分析n功能:层次分析,把源程序的单词序列组成语法短语(表示成语法树).例: :=“=” :=“+” :=“*” :=“(”“)” := := :=21n 赋值语句标识符表达式表达式+表达式表达式标识符常数标识符=表达式*22语法分析id1=id2+id3*N=+N 60*Id1 PositionId2 initialId3 rate231.2 编译程序的工作过程编译程序的工作过程 n1.2.3 语义分析语义分析 依据语言的语义规则对语法分析得到的语依据语言的语义规则对语法分析得到的语法结构进行静态语义检查法结构进行静态语义检查(确定类型、类型和确定类型、类型和运算
14、合法性检查、识别含义与相应的语义处理运算合法性检查、识别含义与相应的语义处理及其它一些静态语义检查及其它一些静态语义检查)，并用另一种内部，并用另一种内部形式表示出来，或者直接用目标语言表示出来。形式表示出来，或者直接用目标语言表示出来。 凡在编译时可以确定的内容称为凡在编译时可以确定的内容称为“静态静态”的；凡必须推迟到程序运行时才能确定的内容的；凡必须推迟到程序运行时才能确定的内容称为称为“动态动态”的。的。24语义分析n语义审查(静态语义)上下文相关性类型匹配类型转换例:Program p();Var rate:real;procedure initial;position := ini
15、tial + rate * 60 /* error */ /* error */ /* warning */;25Program p();Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 26语义分析60:=+*Id1 positionId2 initialId3 rateinttoreal27中间代码生成n源程序的内部(中间)表示三元式、四元式、P-Code、C-Code、U-Code、bytecode28中间代码生成id1= id2 + id3 * 60(1)(int
16、toreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(=,t3-id1)291.2 编译程序的工作过程编译程序的工作过程 n1.2.4 代码优化代码优化 依据程序的等价变换规则，尽量压缩目标依据程序的等价变换规则，尽量压缩目标程序运行所需的时间和所占的存储空间，以提程序运行所需的时间和所占的存储空间，以提高目标程序的质量。高目标程序的质量。 30代码优化id1= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换变换 （1） ( *id360.0t1)
17、 ( 2）（ + id2 t1id1)311.2 编译程序的工作过程编译程序的工作过程 n1.2.5 代码生成代码生成 如果语义分析时把源程序表示成中间形式如果语义分析时把源程序表示成中间形式而不是表示成目标指令，则由本部分完成从中而不是表示成目标指令，则由本部分完成从中间形式到目标指令的转换。如果语义分析时，间形式到目标指令的转换。如果语义分析时，已直接生成目标指令，则无需另外再做代码生已直接生成目标指令，则无需另外再做代码生成工作。成工作。 目标指令可能是绝对指令代码，或可重新目标指令可能是绝对指令代码，或可重新定位的指令代码或汇编指令代码。该阶段的工定位的指令代码或汇编指令代码。该阶段的
18、工作有赖于硬件系统结构和机器指令含义。作有赖于硬件系统结构和机器指令含义。 32目标代码生成(*,id360.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1331.2 编译程序的工作过程编译程序的工作过程 n1.2.6 表格管理表格管理 登记源程序中出现的每个名字以及名字的登记源程序中出现的每个名字以及名字的各种属性。有些名字的属性需要在各个阶段才各种属性。有些名字的属性需要在各个阶段才能填入。能填入。 34符号表管理n记录源程序中使用的名字n收集每个名字的各种属性信息类型、作用域、分配存储信息Const1
19、常量值：35Var1变量类型：实层次：2351.2 编译程序的工作过程编译程序的工作过程 n1.2.7 出错处理出错处理 源程序中的错误有语法错误和语义错误两种。源程序中的错误有语法错误和语义错误两种。 1.语法错误：源程序中不符合语法语法错误：源程序中不符合语法(或词法或词法)规则规则的错误，它们可在词法分析或语法分析时检测的错误，它们可在词法分析或语法分析时检测出来。出来。 2.语义错误：源程序中不符合语义规则的错误，语义错误：源程序中不符合语义规则的错误，一般在语义分析时检测出来，有的语义错误要一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。通常包括：说明错误、在运行时才能
20、检测出来。通常包括：说明错误、作用域错误、类型不一致等等作用域错误、类型不一致等等36出错处理n检查错误、报告出错信息、排错、恢复编译工作371.3 编译程序的结构编译程序的结构 出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理381.3 编译程序的结构编译程序的结构 391.4 编译程序的组织形式编译程序的组织形式 n1.4.1 遍遍(趟，趟程趟，趟程) 所谓一趟或一遍是指一个编译程序在编译所谓一趟或一遍是指一个编译程序在编译时刻把源程序或源程序的等价物时刻把源程序或源程序的等价物(中间程序中间程序)从从头到尾扫描一遍并转换成另一紧邻的等价物的
21、头到尾扫描一遍并转换成另一紧邻的等价物的全过程。全过程。 根据编译程序在完成翻译任务的过程中需根据编译程序在完成翻译任务的过程中需要对源程序或其中间等价物扫描的遍数，可以要对源程序或其中间等价物扫描的遍数，可以把编译程序分为单遍扫描的编译程序把编译程序分为单遍扫描的编译程序(只需扫只需扫描一遍描一遍)和多遍扫描的编译程序和多遍扫描的编译程序(需扫描多遍需扫描多遍)。 40单遍扫描的编译程序单遍扫描的编译程序411.4 编译程序的组织形式编译程序的组织形式 n1.4.2 编译的前端和后端编译的前端和后端 前端主要由与源语言有关但与目标机器无关的那些前端主要由与源语言有关但与目标机器无关的那些部分
22、组成，如词法分析、语法分析、语义分析与中间代部分组成，如词法分析、语法分析、语义分析与中间代码生成及部分代码优化工作。码生成及部分代码优化工作。 后端主要包括编译中与目标机器有关的那些部分，后端主要包括编译中与目标机器有关的那些部分，如与目标机有关的代码优化和目标代码生成等。后端不如与目标机有关的代码优化和目标代码生成等。后端不依赖于源语言而仅依赖于中间语言。依赖于源语言而仅依赖于中间语言。 n可以通过改变编译程序的后端来实现编译程序的移植。可以通过改变编译程序的后端来实现编译程序的移植。 421.5 编译程序的构造编译程序的构造n 1.5.1 高级语言的自编译性高级语言的自编译性构造编译程序
23、可以用机器言语、汇编语言构造编译程序可以用机器言语、汇编语言和高级语言。和高级语言。 高级语言的自编译性：一个语言可以用来高级语言的自编译性：一个语言可以用来编写自己的编译程序。编写自己的编译程序。431.5 编译程序的构造编译程序的构造n 1.5.2 编译的自展技术编译的自展技术通过一系列自展途径而形成编译程序通过一系列自展途径而形成编译程序的过程。的过程。 先对语言的核心部分构造一个小小编译程先对语言的核心部分构造一个小小编译程序序(可用低级语言实现可用低级语言实现)，再以它为工具构造一，再以它为工具构造一个能够编译更多语言成分的较大编译程序。如个能够编译更多语言成分的较大编译程序。如此扩
24、展下去，越滚越大，最后形成所期望的整此扩展下去，越滚越大，最后形成所期望的整个编译程序。个编译程序。441.5 编译程序的构造编译程序的构造n 1.5.3 编译的自展技术编译的自展技术将一个机器（宿主机）上的一个具有将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序移植到另一个机自编译性的高级语言编译程序移植到另一个机器（目标机）上。器（目标机）上。 利用利用A机器上的高级语言机器上的高级语言L编写能在编写能在B机器机器上运行的高级语言上运行的高级语言L的编译程序。的编译程序。如图：如图：451.5 编译程序的构造编译程序的构造n 1.5.3 编译的自展技术编译的自展技术将一个机器（宿
25、主机）上的一个具有自编译性的高将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序移植到另一个机器（目标机）上。级语言编译程序移植到另一个机器（目标机）上。 利用利用A机器上的高级语言机器上的高级语言L编写能在编写能在B机器上运行的高级机器上运行的高级语言语言L的编译程序。的编译程序。46第第1章内容小结章内容小结n 什么是编译程序什么是编译程序n 编译方式的特点编译方式的特点n 解释方式的特点解释方式的特点n 编译方式与解释方式的根本区别编译方式与解释方式的根本区别n 编译程序的工作过程编译程序的工作过程n 编译程序的结构编译程序的结构n 遍与编译程序的组织形式遍与编译程序的组织形式n 编译程序的构造方法编译程序的构造方法47结束，再见结束，再见n复习复习n预习预习48
