第1章引论--清华大学出版社(2012)

1、编译原理编译原理 武汉理工大学计算机科学与技术学院编译原理 计算机科学与技术学院 何九周 教材：编译原理(第2版)张素琴、吕映芝、蒋维杜、戴桂兰，清华大学出版社 参考书：程序设计语言编译原理(第3版)陈火旺、刘春林等，国防工业出版社编译原理学习与解题指南伍春香编著 华中科技大学出版社Compilers: Principles, Technigues, and Tools Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Addison-Wesley,1986. 影印版：人民邮电出版社教材与参考书教材与参考书学时学时 总学时总学时48理论学时理论学时40实验

2、学时实验学时8 在这一学期里，希望我们能共同努力，学好这门功课！教学目的教学目的 编译系统是现代计算机系统的基本组成之编译系统是现代计算机系统的基本组成之一，编译程序构造的基本原理和技术不仅应一，编译程序构造的基本原理和技术不仅应用于编译程序的设计，也广泛应用于一般软用于编译程序的设计，也广泛应用于一般软件的设计和实现。本课程是计算机专业、软件的设计和实现。本课程是计算机专业、软件工程专业的一门十分重要的核心专业课。件工程专业的一门十分重要的核心专业课。 通过本课程的学习，旨在使学生掌握编译通过本课程的学习，旨在使学生掌握编译的基本理论、原理和技术，并对编译程序有的基本理论、原理和技术，并对编

3、译程序有较为具体的认识。使学生能运用所学过的基较为具体的认识。使学生能运用所学过的基本知识、着手开发系统程序，为今后的工作本知识、着手开发系统程序，为今后的工作（技术和理论研究）打下基础。（技术和理论研究）打下基础。教学计划教学计划1 引论 2学时2 文法和语言 6学时3 词法分析 6学时4 自顶向下语法分析方法 4学时5 自底向上语法分析法 6学时6 语法制导翻译和中间代码生成 6学时7 符号表 2学时8 目标程序运行时的存储组织 2学时9 代码优化 4学时10 代码生成 2学时学习要求学习要求 编译程序是一个系统性很强的软件。在课编译程序是一个系统性很强的软件。在课程中我们按阶段进行讨论，

4、但在学习时心中程中我们按阶段进行讨论，但在学习时心中一定要有系统的概念，把每个阶段放到整个一定要有系统的概念，把每个阶段放到整个编译程序背景中学习，才不致将所学的内容编译程序背景中学习，才不致将所学的内容孤立化。通过课程的学习应掌握各个阶段的孤立化。通过课程的学习应掌握各个阶段的功能和设计原则，以及在编译中的逻辑关系。功能和设计原则，以及在编译中的逻辑关系。理解他们怎样作为一个整体完成编译任务的，理解他们怎样作为一个整体完成编译任务的，并且或多或少做些实践工作更能加深理解。并且或多或少做些实践工作更能加深理解。第第1章章 引论引论 本章主要介绍在后面的章节中将要学到什么内容。第第1章教学内容章

5、教学内容 了解：什么是翻译程序、编译程序、解释程序； 明确编译程序的功能及其在计算机系统中的作用； 了解源语言程序被编译为目标程序的整个过程，这个过程一般划分为哪些阶段； 知道编译技术可用于哪类软件的设计和开发。 一、什么是编译程序一、什么是编译程序【翻译程序】【翻译程序】将源语言程序转换为目标语言将源语言程序转换为目标语言程序的程序的等价等价的程序称为翻译程序。的程序称为翻译程序。某一种语言程序某一种语言程序另一种语言程序另一种语言程序转换转换源语言程序源语言程序目标语言程序目标语言程序编译程序编译程序【编译程序】【编译程序】将高级语言源程序翻译为低级语将高级语言源程序翻译为低级语言目标程序

6、的程序称为编译程序。言目标程序的程序称为编译程序。高级语言程序高级语言程序低级语言程序低级语言程序编译程序编译程序机器或汇编程序机器或汇编程序编译程序的意义：使得多数计算机用户不必编译程序的意义：使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程考虑与机器有关的繁琐细节，使程序员和程序专家独立于机器。序专家独立于机器。汇编程序汇编程序【汇编程序】【汇编程序】将汇编语言源程序翻译为机器语将汇编语言源程序翻译为机器语言目标程序的程序称为汇编程序。言目标程序的程序称为汇编程序。汇编语言程序汇编语言程序机器语言程序机器语言程序汇编程序汇编程序【反汇编程序】【反汇编程序】将机器语言源程序翻译为

7、汇编将机器语言源程序翻译为汇编语言目标程序的程序称为反汇编程序。语言目标程序的程序称为反汇编程序。高级语言有两种翻译途径：高级语言有两种翻译途径： 编译方式与解释方式。编译方式与解释方式。它们的主要区别在于它们的主要区别在于是否产生目标程序是否产生目标程序。 解释程序不产生目标程序，而是边解解释程序不产生目标程序，而是边解释边执行源程序本身，是一种释边执行源程序本身，是一种“会话型会话型”语言。语言。编译程序与解释程序的异同编译程序与解释程序的异同程序设计语言的实现：程序设计语言的实现：有些语言基本通过解释程序有些语言基本通过解释程序 Java的的Bytecode有些环境同时提供编译程序和解释

8、系统有些环境同时提供编译程序和解释系统 Lisp 编译程序低级语言程序高级语言程序高级语言程序 解释程序计算结果编译程序和解释系统编译程序和解释系统如对源程序： b := 2 ; a := b+2 ; write a ; 编译程序编译程序 解释程序解释程序 直接将4的值输出（显示）（直接对源程序中的语句进行分析，执行其隐含的操作。）Int 2St bLd badd 2St a生成代码Java编译器把Java代码翻译成独立于机器的Java“字节代码”。运行时，目标装置中的校验器便分析这些字节代码以确保代码的安全执行。在目标装置中，内置一个JVM（Java虚拟机）。该虚拟机用一个解释器或一个JIT

9、（适时）编译器把字节代码翻译成目标处理器能够识别的机器语言。二、高级语言程序的处理过程二、高级语言程序的处理过程 需预处理的源程序预处理的程序源程序目标汇编程序可再装配的机器代码编译程序汇编程序连接装配程序可再装配的目标代码绝对机器代码三、编译程序的工作过程三、编译程序的工作过程 编译程序的工作，从输入源程序开始编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非到输出目标程序为止的整个过程，是非常复杂的。但就其过程而言，它与人们常复杂的。但就其过程而言，它与人们进行自然语言之间的翻译有许多相近之进行自然语言之间的翻译有许多相近之处。处。 英汉翻译与编译的比较英汉翻译与编译的比较

10、【例如】英语句子【例如】英语句子This is a book.This is a book.的的翻译过程：翻译过程：1 1、识别单词、识别单词2 2、“组词成句组词成句”3 3、分析句子的含义、分析句子的含义4 4、进行初步翻译、进行初步翻译5 5、修饰译文、修饰译文6 6、写出最后译文、写出最后译文编译程序的翻译过程类似：1、词法分析2、语法分析3、语义分析4 4、中间代码生成5、代码优化6、目标代码生成编译程序的编译程序的6个阶段个阶段 编译程序的工作过程一般划分为六个阶段：编译程序的工作过程一般划分为六个阶段： 词法分析词法分析 语法分析语法分析 语义分析语义分析 中间代码生成中间代码生

11、成 代码优化代码优化 目标代码生成目标代码生成 1.词法分析词法分析任务：从左至右读字符流的源程序，识别(拼)单词。【单词】单词是具有独立意义的最小语法单位。识别原则：词法规则描述工具：正规式 正规文法 有穷自动机FA自动生成工具：LEX 【例如】某赋值语句如下：例如】某赋值语句如下： yx1x2 * 60；词法分析阶段识别出的单词序列为：单词类型单词类型单词值单词值标识符(变量名) y算符(赋值) =标识符(变量名) x1算符(加法) +标识符(变量名) x2算符(乘法) *整数 60界符 ；2.语法分析语法分析任务：依据依据源程序的语法规则语法规则把源程序的单词序列组成更大的语法成分“组词

12、成句” (表示成语法树) 。识别原则：语法规则描述工具：上下文无关文法 下推自动机PDA自动生成工具：YACC赋值语句的语法规则 := = := + := * :=( ) := := := 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符=表达式*语语法法树树3.语义分析与中间代码生成语义分析与中间代码生成任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 语义审查(静态语义) 上下文相关性 类型匹配 类型转换识别原则：语义规则描述工具：属性文法实现方法：语法制导翻译中间代码中间代码 所谓所谓“中间代码中间代码”是一种含义明确、便于处理的是一种含义明确

13、、便于处理的记号系统，它通常独立于具体的硬件。这种记号记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算接近，或者能够比较容易地把它变换成现代计算机的机器指令。机的机器指令。 许多编译程序采用了一种与许多编译程序采用了一种与“三地址指令三地址指令”非常非常近似的近似的“四元式四元式”作为中间代码，其形式是：作为中间代码，其形式是： (算符算符 , 运算对象运算对象1 , 运算对象运算对象2 , 结果结果)常用的中间代码有：四元式，三元式，间接三元式，常用的中间代码有：四元式，三

14、元式，间接三元式，逆波兰记号和树形表示等等。逆波兰记号和树形表示等等。 中间代码生成示例中间代码生成示例赋值语句赋值语句 y= x1 + x2* 60对应的四元式是：对应的四元式是： (1) (*,x2,60,t1) (2) (+,x1,t1,t2) (3) (=,t2,-,y)4.代码优化代码优化 任务：任务：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。 主要包括：主要包括：公共子表达式的提取 循环优化 删除无用代码等等 优化所依循的原则：优化所依循的原则：程序的等价变换规则。 优化示例优化示例 【例如】程序片断：【例如】程序片断： for K

15、：1 to 100 do begin M：I10 * K； N：J 10*K end中间代码为：( ：, 1, , K ) ( j , 100, K, （9）)( * , 10, K, T1 )( , I, T1 , M )( * , 10, K, T2 )( , J, T2 , N )( , K, 1 , K )( j , , ,（2）)1) 循环中需做循环中需做300次加法次加法和和200次乘次乘法法 优化后的中间代码为：( ：, I, , M ) ( ：, J, , N ) ( ：, 1, , K )( j , 100, K, （9）)( , M, 10 , M )( , N, 10 ,

16、 N )( , K, 1 , K )( j , , ,（4）)1) 循环中只循环中只需做需做300次次加法加法5.目标代码生成目标代码生成 任务：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。生成原则：硬件系统结构和机器指令含义。目标代码的形式： 绝对指令代码 可重定位的指令代码 汇编指令代码 目标代码生成示例目标代码生成示例(*,x1 ,60.0,t1)(+,x2 ,t1 ,x1)movfx1,R2mulf#60.0,R2movfx2,R1addfR2,R1movfR1,x1注意注意 上述编译过程的阶段划分只是一种典型的分法，上述编译过程的阶段划分只是一种典型的分法，事实上并

17、不是所有的编译程序都分成这样几个事实上并不是所有的编译程序都分成这样几个阶段的。阶段的。 有些编译程序对优化没有什么要求，优化阶段有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，就可省去。在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉。有些最简单的中间代码产生阶段也可以去掉。有些最简单的编译程序是在语法分析的同时产生目标代码。编译程序是在语法分析的同时产生目标代码。但是，多数实用编译程序的工作过程大致都像但是，多数实用编译程序的工作过程大致都像上面所说的那六个阶段。上面所说的那六个阶段。 其它其它 编译程序的另外两个重要的工作是表格管理和出错处理。

18、 编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。表格与表格管理表格与表格管理 编译程序在工作过程中需要保持一系列的编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编译各表格，以登记源程序的各类信息和编译各阶段的进展状况。合理地设计和使用表格阶段的进展状况。合理地设计和使用表格是编译程序

19、构造的一个重要问题。是编译程序构造的一个重要问题。 在编译程序中最重要的一种表格是在编译程序中最重要的一种表格是符号表符号表。 记录源程序中使用的名字 收集每个名字的各种属性信息 类型、作用域、分配存储信息出错处理出错处理 一个编译程序不仅应能对书写正确的程序进一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现在源程序中的错误行翻译，而且应能对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。设法发现错误，把有关错误信息报告给用户。这部分工作是由专门的一组程序（叫做出错这部分工作是由专门的一组程序（

20、叫做出错处理程序）完成的。处理程序）完成的。 出错处理程序的任务包括出错处理程序的任务包括检查错误、报告出检查错误、报告出错信息、排错、恢复编译工作错信息、排错、恢复编译工作。四、编译程序的组成四、编译程序的组成 编译过程的五个阶段的任务，再加上表编译过程的五个阶段的任务，再加上表格管理和出错处理的工作可分别由几个格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错标代码生

21、成程序、表格管理程序和出错处理程序。从而可给出一个典型的编译处理程序。从而可给出一个典型的编译程序结构框图，如图所示。程序结构框图，如图所示。出错处理程序语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理程序编译程序的组成编译程序的组成源程序词法分析器单词符号语法分析器语法单位语义分析与中间代码生成器中间代码 优化器中间代码目标代码生成器目标代码 表 格 管 理 程 序 出 错 处 理 程 序五、编译的前端与后端五、编译的前端与后端o 常把编译的过程分为前端和后端。o 前端前端：主要依赖于源语言而与目标机无关。通常包括词法分析、语法分析、语义分析和中间代码

22、生成这些阶段，某些优化（中间代码优化），也包括相应的出错处理和符号表管理等工作。o 后端后端：依赖于目标机而一般不依赖源语言。后端包括目标代码生成和目标代码优化，以及相关出错处理和符号表操作。六、遍（六、遍（pass） 所谓“遍”就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 Turbo C是一遍完成编译，以及预处理和后续处理。 两遍编译： 1.进行词法分析、语法分析、语义分析，生成中间代码作为文件保留，以及符号表文件。 2.优化后生成目标代码作为文件保留。 三遍编译： 3.对目标代码的优化。七、编译程序涉及的三种语言七、编译程序涉及的三种语言

23、 源语言源语言：要深刻理解源语言(如 FORTRAN、Pascal或 C)结构(语法)和含义(语义)； 目标语言目标语言：最终的目标语言还是机器语言，则必须搞清楚硬件的系统结构和操作系统的功能； 宿主语言宿主语言：编写编译程序的语言。 自编译程序：宿主语言是源语言。例如PASCAL。八、编译程序的生成八、编译程序的生成 q手工手工q机器语言机器语言q汇编汇编q系统程序设计语言，自编译，移植，交叉编系统程序设计语言，自编译，移植，交叉编译等方式译等方式q自动构造工具自动构造工具lex yacc九、九、编译程序与程序设计环境编译程序与程序设计环境 编译程序无疑是实现高级语言的一个最重要编译程序无疑

24、是实现高级语言的一个最重要的工具。但支持程序设计人员进行程序设计开的工具。但支持程序设计人员进行程序设计开发通常还需要其它一些工具：如编辑程序、连发通常还需要其它一些工具：如编辑程序、连接程序、调试程序等。编译程序与这些程序设接程序、调试程序等。编译程序与这些程序设计工具一起构成所谓的计工具一起构成所谓的程序设计环境程序设计环境。 在一个程序设计环境中，编译程序起着中心在一个程序设计环境中，编译程序起着中心的作用。连接程序、调试程序、程序分析等工的作用。连接程序、调试程序、程序分析等工具直接依赖于编译程序所产生的结果，而其它具直接依赖于编译程序所产生的结果，而其它工具的构造也常常要用到编译的原

25、理、方法和工具的构造也常常要用到编译的原理、方法和技术。技术。十、编译技术在软件工具中的应用十、编译技术在软件工具中的应用 大部分系统软件与应用软件的开发通常大部分系统软件与应用软件的开发通常要用到编译原理和技术。要用到编译原理和技术。 设计词法分析器的串匹配技术已用于正文编设计词法分析器的串匹配技术已用于正文编辑器、信息检索系统和模式识别程序。辑器、信息检索系统和模式识别程序。 上下文无关文法和语法制导定义已用于排版、上下文无关文法和语法制导定义已用于排版、绘图系统和语言结构化编辑器。绘图系统和语言结构化编辑器。 代码优化技术已用于程序验证器和从非结构代码优化技术已用于程序验证器和从非结构化

26、的程序产生结构化程序的编程中。化的程序产生结构化程序的编程中。十一、处理源程序的软件工具十一、处理源程序的软件工具1.语言的结构化编辑器语言的结构化编辑器2.语言程序的调试工具语言程序的调试工具3.程序格式化工具程序格式化工具4.语言程序测试工具语言程序测试工具5.程序理解工具程序理解工具6.高级语言之间的转换工具高级语言之间的转换工具1.语言的结构化编辑器 用户可使用该编辑器在语言的语法制导下编制出所需的源程序。结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，而且还能像编译程序那样对源程序正文进行分析。因此，结构化编辑器能够执行一些对编制程序有用的附加的任务。例如，它能够检查用户的

27、输入是否正确，能够自动地提供关键字,当用户敲入if后，编辑器立即显示then并将这两个关键字之间必须出现的条件留给用户输入，并能检查begin或左括号与end或右括号是否相匹配等等。由于结构化编辑器具有上述功能，既可保证编出的源程序无语法错误，并有统一的可读性好的程序格式，这无疑将会提高程序的开发效率和质量。 商用产品很多如Turbo-Edit,Editplus和Ultraedit等等。很多集成开发环境中里也都包含这种类似的工具,如Jbuild中就有JAVA程序的结构化编辑器。2.语言程序的调试工具 调试是软件开发过程中一个重要环节，结构化编辑器只能解决语法错误的问题，而对一个已通过编译的程序

28、来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致，程序的执行是否实现预计的算法和功能。这种对算法的错误或程序没能反映算法的功能等错误就需用调试器来协助解决。有一种调试器允许用户使用源程序正文和它的符号来调试,即一行一行的跟踪程序,查看变量和数据结构的变化以进行调试工作.当然,这些符号的信息必须由编译程序提供.调试器的实现可以有很多途径.其中一种是写一个解释器,以交互的方式翻译和执行每一行,它必须维护其所有的运行时的资源以保证在程序执行期间很容易的查询不同变量的当前值.如果不想通过解释程序允许编译了的代码调试,编译程序必须在目标代码(汇编)生成时同时生成特定的调试信息,比如,关联标识

29、符和它表示的地址的信息,用于无歧义的引用一个声明了多次的标识符的信息等等.调试功能愈强，实现愈复杂，它涉及源程序的语法分析和语义处理技术。3.程序格式化工具程序格式化工具程序格式化工具分析源程序并以使程序结构变得清晰可读的形式打印出来。例如，注释可以以一种专门的字形出现，且语句的嵌套层次结构可以用缩排方式（齿形结构）表示出来。4.语言程序测试工具语言程序测试工具 语言程序的测试工具有两种：静态分析器和动态测试器。 静态分析器静态分析器是在不运行程序的情况下对源程序进行静态地分析，以发现程序中潜在的错误或异常.它对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系。如某变量未被赋值就被引

30、用，或定值后未被引用，或多余的源代码等一些编译程序的语法分析发现不了的错误。 动态测试工具动态测试工具也是首先对源程序进行分析，在分析基础上将用于记录和显示程序执行轨迹的语句或函数插入到源程序的适当位置，并用测试用例记录和显示程序运行时的实际路径,将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。5.程序理解工具程序理解工具对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用户理解程序。6. 高级语言之间的转换工具高级语言之间的转换工具 由于计算机硬件的不断更新换代，更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好条件，然而一些已

31、有的非常成熟的软件如何在新机器新语言情况下使用呢?为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题。这种转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已。这与实现一个完整的编译程序相比工作量要少些。 比如：C，PASCAL，FORTRAN到Ada的翻译器 IBM 4700汇编到C的转换器 COBOL 到Java 的编译器 Human-orientedlanguageComputer-orientedlanguage计算模式，语言范式语言应用领域编译程序冯 诺依曼机体系结构并行体系结构嵌入

32、系统十二、程序设计语言范型十二、程序设计语言范型S OI高级程序语言高级程序语言v不同的应用侧重:数值计算 Fortran 系统程序设计-C事务处理-obol VLSI设计-VHDL人工智能-rolog大型嵌入式实时处理-da 符号处理-nobol语言范型语言范型（支持的计算模式）（支持的计算模式）强制式语言-C,Fortran,Pascal应用式(函数式）语言-ML，Lisp基于规则(逻辑）的语言-Prolog,Yacc面向对象语言-Ada,C+,Java强制式语言（强制式语言（Imperative Language）也称过程式语言。）也称过程式语言。 其特点是命令驱动，面向语句，一个强制式

33、语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变，这种语言的语法形式通常具有如下形式； 语句1；语句2；语句3；语言执行的解释与万诺曼机的体系结构对应：改变机器状态（内存，各种寄存器和外存的内容） 应用式（函数式）：应用式语言（Applicative Language）更注重程序所表示的功能，而不是一个语句接一个语句地执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果。程序执行： 执行一个个函数施用在数据上的变换最终得到的结果Example: 解决八皇后问题的一段Haskell98程序：queen 0 = queen (n+1) = x :y | y - queen n, x - 1.8, safe 1 x ysafe n x = Truesafe n x (z :y) = and x/=z, x/=z +n, x/=z -n, safe (n+1) x y-test = que