编译原理第三版 第一章 引论

1、程序设计语言程序设计语言编译原理编译原理主讲：高秀芬课程简介课程简介n课程性质课程性质 是计算机科学与技术专业的一门重要专业课。是计算机科学与技术专业的一门重要专业课。n基本要求基本要求 n透彻地理解和掌握编译程序的概念、原理、常用主要透彻地理解和掌握编译程序的概念、原理、常用主要算法和技巧。算法和技巧。n并具有编制、调试简单编译程序的能力。并具有编制、调试简单编译程序的能力。n了解编译技术的最新发展和研究方向。了解编译技术的最新发展和研究方向。n参考书参考书编译原理编译原理 吕映芝、张素琴，清华大学出版社。吕映芝、张素琴，清华大学出版社。 Compilers： Principles, Tec

2、hniques, &Tools Alfred V. Aho等著等著 机械工业出版社。机械工业出版社。 n什么叫编译程序什么叫编译程序n编译过程概述编译过程概述n编译程序的结构编译程序的结构n编译程序的生成编译程序的生成本章要点本章要点n计算机上运行的所有软件都是用某种程序设计计算机上运行的所有软件都是用某种程序设计语言编写的。语言编写的。n程序设计语言编写的程序可以运行之前，首先程序设计语言编写的程序可以运行之前，首先需要被翻译成一种能被计算机执行的形式。完需要被翻译成一种能被计算机执行的形式。完成这项翻译工作的软件系统称为成这项翻译工作的软件系统称为语言处理程序。语言处理程序。n常用

3、的语言处理程序有两种：解释程序和编译常用的语言处理程序有两种：解释程序和编译程序。程序。解释程序解释程序n定义：解释程序是定义：解释程序是边解释边执行边解释边执行源语言程源语言程序，序，不产生目标语言程序不产生目标语言程序的一种语言转换的一种语言转换系统。系统。n特点：逐条语句地分析和执行，不生成目标程特点：逐条语句地分析和执行，不生成目标程序。如：序。如：BasicBasic，PrologProlog。优点：易于查错优点：易于查错不足：效率低，运行速度慢不足：效率低，运行速度慢编译程序编译程序n编译程序是把用高级语言编写的源程序转换成编译程序是把用高级语言编写的源程序转换成低级语言（如汇编语

4、言或机器语言）表示的低级语言（如汇编语言或机器语言）表示的目目标程序标程序的一种语言翻译程序的一种语言翻译程序。n特点：对特点：对整个程序整个程序进行分析，翻译成等价的目进行分析，翻译成等价的目标程序后执行。如：标程序后执行。如：PascalPascal，FortranFortran，C C优点：只需分析和翻译一次。优点：只需分析和翻译一次。不足：在运行中发现的错误必须查找整个程序不足：在运行中发现的错误必须查找整个程序 确定。确定。图示图示编译程序编译程序高级语言编高级语言编写的程序写的程序（源程序）（源程序）低级语言程序低级语言程序（目标程序）（目标程序）n有时用有时用T T形图来表示编译

5、程序涉及的三个语言形图来表示编译程序涉及的三个语言S OI S:源语言源语言(程序程序) Source language(program)O:目标语言目标语言(程序程序) target/objectlanguage(program)I:实现语言实现语言 implementation languageJava语言处理器语言处理器n Java语言处理器结合了编译和解释过程。一个语言处理器结合了编译和解释过程。一个Java源程序首先被编译成一个称为字节码的中间表源程序首先被编译成一个称为字节码的中间表示形式，然后由一个虚拟机对字节码解释执行。示形式，然后由一个虚拟机对字节码解释执行。源程序源程序翻译

6、器翻译器中间程序中间程序虚拟机虚拟机输入输入输出输出好处：一台机器上得到的字节码可以在另一台好处：一台机器上得到的字节码可以在另一台机器上解释执行。机器上解释执行。 依据编译程序的不同用途和侧重可对其分依据编译程序的不同用途和侧重可对其分类为类为: :诊断型编译程序诊断型编译程序- -帮助程序开发和调试。帮助程序开发和调试。优化型编译程序优化型编译程序- -提高目标代码效率。提高目标代码效率。交叉型编译程序交叉型编译程序- -编译程序产生不同于宿主机的机器代编译程序产生不同于宿主机的机器代码，即码，即A A机器上运行的编译程序生成机器上运行的编译程序生成B B机器的机器代码。机器的机器代码。可

7、变目标型编译程序可变目标型编译程序- -不重写编译程序中与机器无关不重写编译程序中与机器无关的部分就能改变目标机。的部分就能改变目标机。第一个编译程序出现在第一个编译程序出现在2020世纪世纪5050年代早期，年代早期，多是将算术公式翻译成机器代码。多是将算术公式翻译成机器代码。2020世纪世纪5050年代中期，出现了年代中期，出现了FORTRANFORTRAN等一批等一批高级语言，相应的一批编译系统开发成功。高级语言，相应的一批编译系统开发成功。2020世纪世纪5050年代末，提出并研制编译程序的编年代末，提出并研制编译程序的编译程序，即编译程序的自动生成工具（译程序，即编译程序的自动生成工

8、具（LEXLEX，YACCYACC等）。等）。2020世纪世纪6060年代起，出现年代起，出现自展技术自展技术（用被编译（用被编译的语言来书写该语言自身的编译程序）。的语言来书写该语言自身的编译程序）。19711971年，年，PASCALPASCAL的编译程序用自展技术生成的编译程序用自展技术生成后，其影响越来越大。后，其影响越来越大。至今已形成一套比较成熟、系统的理论与方至今已形成一套比较成熟、系统的理论与方法及开发环境，但并行编译、嵌入式应用的法及开发环境，但并行编译、嵌入式应用的交叉编译等仍在研究和发展中。交叉编译等仍在研究和发展中。5. 编译技术的应用编译技术的应用 n高级程序设计语言

9、的实现。高级程序设计语言的实现。 每一轮编程语言新特征的出现都刺激编译每一轮编程语言新特征的出现都刺激编译器优化的新研究。器优化的新研究。 有效的编译器寄存器分配技术，使有效的编译器寄存器分配技术，使C语言语言的的register关键字控制变得没有必要了。关键字控制变得没有必要了。 二进制翻译。二进制翻译。 编译器技术可用于把一种机编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码以运行原先为别的指令集编译的代码 数据库查询解释器。数据库查询解释器。 数据库查询由一些谓数据库查询由一些谓词组成，这些谓词由包含关系

10、运算的布尔词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行表达式组成，可以被解释执行,也可以被编也可以被编译成搜索数据库的命令译成搜索数据库的命令n 程序翻译程序翻译 计算机体系结构的迅速演化引起对新的编译器计算机体系结构的迅速演化引起对新的编译器技术的需要技术的需要 并行编译并行编译n编译器重新整理指令，使得指令级并行更有效。编译器重新整理指令，使得指令级并行更有效。n编译器从传统的串行程序自动生成并行代码，使之编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上运行于多处理器上 内存分层内存分层n 编译器优化历来集中在优化处理器的执行上，但是编译器优化历来集中在优化处

11、理器的执行上，但是现在更强调要使内存分层更有效现在更强调要使内存分层更有效n 针对计算机体系结构的优化针对计算机体系结构的优化 现在计算机系统的性能不仅仅取决于它的原现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利始速度，还取决于编译器是否能生成充分利用其特征的代码。用其特征的代码。 在现代计算机体系结构的研究中，在处理器在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结代码在模拟器上运行，以评价拟采用体系结构的特征。构的特征。n 新计算机体系结构的设计新计算机体系

12、结构的设计 源于编译器中代码优化技术的源于编译器中代码优化技术的程序分析程序分析一直在改进软件开发效率。一直在改进软件开发效率。 类型检查类型检查 类型检查是一种捕捉程序中前后不一致的类型检查是一种捕捉程序中前后不一致的成熟而有效的技术成熟而有效的技术 边界检查边界检查 数据流分析技术可用来定位缓冲区溢出数据流分析技术可用来定位缓冲区溢出n 提高软件开发效率的工具提高软件开发效率的工具1 1、词法分析、词法分析(Lexical analysis)(Lexical analysis)n词法分析程序又称词法分析程序又称扫描程序扫描程序。n是编译过程的第一个阶段，其是编译过程的第一个阶段，其任务任务

13、是：读是：读源程序的字符流、识别单词（如标识符、源程序的字符流、识别单词（如标识符、整数、界限符等），并转换成内部形式。整数、界限符等），并转换成内部形式。n输入输入：源程序中的字符流：源程序中的字符流n输出输出：等长的内部形式，即属性字。：等长的内部形式，即属性字。 例：一个C源程序片段：int a;a=a+2;词法分析后返回(如右图)： 单词类型单词类型 单词值单词值保留字保留字 int标识符 a界符 ;标识符 a算符(赋值) =标识符 a算符(加) +整数 2界符 ；2 2、语法分析（、语法分析（Syntax analysisSyntax analysis）语法分析程序又称识别程序。功能

14、是：读入由词法分析程序识别出的符号，根据给定语法规则，识别出各个语法单位（如：短语、子句、语句、程序段、程序）,并生成另一种内部表示。输入：由词法分析程序识别出并转换的符号输出：另一种内部表示，如语法分析树或其它中间表示。例：例： idid1 1:=id:=id2 2+id+id3 3* *10 10 的语法树的语法树3、语义分析(Semantic analysis)和中间代码生成n对语法分析树或其他内部中间表示进行静态语义检查，并生成目标代码或中间代码。n确定类型n类型检查n识别含义与相应的语义处理n其它静态语义检查n为了优化，往往先生成内部中间表示代码，即中间代码。语义分析举例n错在哪里？

15、n例1： int arr2, c; c = arr1 * 10; n例2： Program p(input,output); Var rate: real; procedure initial; position := initial + rate*60n中间代码 中间代码是一种独立于具体硬件的记号系统，或者与现代计算机的指令形式有某种程度的接近，或者能比较容易地变换成机器指令。如：逆波兰表示、三元式序列、四元式序列，或者抽象语法树。例例1：Pascal语句语句 id1:= id2 + id3 * 60的四元式序列的四元式序列(1)(inttoreal60-t1)(2)(*id3t1t2)(3

16、)(+id2t2t3)(4)(:=t3-id1)例例2：C语言的源程序语言的源程序a = b*c + b*d 的三地址序列（赋值的三地址序列（赋值语句形式的四元式）：语句形式的四元式）： (1) t1 := b*c (2) t2 := b*d (3) t3 := t1 + t2 (4) a := t3例例3:源程序：源程序： if (an四元式：四元式： 100（j=,a,b,102) 101 (j, _, _, 104) 102 (-, a, c, t1) 103 (=, t1, _, a) 104 (*, b, c, t2) 105 (=, t2, _, c)4 4、代码优化、代码优化任务

17、： 对中间表示代码进行分析，把它变换成功能相同，但功效更高的优化了的中间表示代码.它是为改进代码质量而进行的工作。常用技术：基本块优化、循环优化等。举例：id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1)变换成变换成 （1） ( *id360.0t1) ( 2）（）（ + id2 t1id1)5、目标代码生成功能：把中间代码（或经优化处理之后的代码）变换成特定机器上的低级语言代码。总是与机器相关。可在语义分析时生成。如果语义分析的结果是中间表示代码，则目标代码生成部分必须将中间代码

18、变换成等价的目标语言代码。举例：(*,id360.0t1)(+,id2t1id1)movfid3 R2mulf#60.0 R2movfid2 R1addfR2 R1movfR1 id1本节小结本节小结n编译过程的五个阶段：编译过程的五个阶段：n词法分析词法分析n语法分析语法分析n语义分析和中间代码生成语义分析和中间代码生成n中间代码优化中间代码优化n目标代码生成目标代码生成词法分析器语法分析器语义分析与中间代码产生器优化器目标代码生成器源程序单词符号语法单位中间代码优化后的中间代码目标代码表格管理出错处理编编译译程程序序总总框框符号表管理记录源程序中使用的名字记录源程序中使用的名字( (标识符

19、标识符) )收集每个名字的各种属性信息收集每个名字的各种属性信息n类型、作用域、分配存储信息类型、作用域、分配存储信息名字信息出错处理出错处理n检查错误、报告出错信息、排错、恢复编译工检查错误、报告出错信息、排错、恢复编译工作。作。n出错处理程序应能出错处理程序应能最大限度最大限度地发现源程序的各地发现源程序的各种错误，种错误，尽可能尽可能指出错误的性质和地点，并将指出错误的性质和地点，并将错误造成的影响限制在错误造成的影响限制在尽可能小尽可能小的范围内。的范围内。n词法错误和语法错误可由编译程序在编译时刻词法错误和语法错误可由编译程序在编译时刻查出。查出。n语义错误常采用下列方式查出：语义错误常采用下列方式查出：n静态模拟检查：静态模拟检查：n动态调试检查：动态调试检查：概念：趟（遍）概念：趟（遍）n对源程序或源程序的中间结果从头到尾扫描一对源程序或源程序的中间结果从头到