编译原理与技术讲义-第1章

1、青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术第第1章章 概论概论青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术2主要内容主要内容u为什么学习编译为什么学习编译u什么叫编译程序什么叫编译程序 u编译过程概述编译过程概述u编译程序的构成编译程序的构成u与编译有关的概念和技术与编译有关的概念和技术 u如何开发编译程序如何开发编译程序 u编译系统以及其它相关程序编译系统以及其它相关程序青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术31.1 为什么学习编译为什么学习编译u编译程序构造的原理和技术一直属于计算编译程序构造的原理和技术一直属

2、于计算机科学必备的专业基础知识。机科学必备的专业基础知识。u是计算机科学中一个非常成功的分支，也是计算机科学中一个非常成功的分支，也是最早获得成功的分支之一。是最早获得成功的分支之一。u它所建立的理论、技术和方法值得深入研它所建立的理论、技术和方法值得深入研究和学习。究和学习。编译构造正确地建立了研究的问题领域和研编译构造正确地建立了研究的问题领域和研究方式。究方式。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术41.1 为什么学习编译为什么学习编译针对编译程序构造的某些部分已经开发了标针对编译程序构造的某些部分已经开发了标准的形式化技术，包括有限自动机理论、上准的形式化

3、技术，包括有限自动机理论、上下文无关文法、正规表达式、属性文法、机下文无关文法、正规表达式、属性文法、机器代码描述、数据流分析方程式等。器代码描述、数据流分析方程式等。 编译程序包含许多普遍使用的数据结构和算编译程序包含许多普遍使用的数据结构和算法，例如散列法（哈希算法）、栈机制、堆法，例如散列法（哈希算法）、栈机制、堆机制、垃圾收集、集合算法、表驱动算法。机制、垃圾收集、集合算法、表驱动算法。编译程序的许多构造技术已经得到了广泛的编译程序的许多构造技术已经得到了广泛的应用。应用。学习编译原理和技术还有助于我们理解程序学习编译原理和技术还有助于我们理解程序设计语言，编写优秀的软件。设计语言，编

4、写优秀的软件。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术51.2 什么叫编译程序什么叫编译程序u概念概念翻译程序或翻译器是把一种语言（翻译程序或翻译器是把一种语言（源语言源语言）转换成等价的另外一种语言（转换成等价的另外一种语言（目标语言目标语言）的）的程序。程序。如果源语言是高级编程语言，目标语言是机如果源语言是高级编程语言，目标语言是机器代码和汇编语言这样的低级语言，这类翻器代码和汇编语言这样的低级语言，这类翻译程序就叫做译程序就叫做编译程序编译程序或或编译器编译器。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术61.2 什么叫编译程序什

5、么叫编译程序编译执行方式：把源程序用编译程序翻译成编译执行方式：把源程序用编译程序翻译成机器可以执行的目标程序或目标代码，然后机器可以执行的目标程序或目标代码，然后才能接受输入数据运行。才能接受输入数据运行。 编译程序源程序输入数据目标程序计算机系统计算机系统目标程序运行结果青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术71.2 什么叫编译程序什么叫编译程序解释程序：解释程序不产生源程序的目标代解释程序：解释程序不产生源程序的目标代码，而是对源程序逐条语句的分析，根据每码，而是对源程序逐条语句的分析，根据每个语句的含义执行产生结果。个语句的含义执行产生结果。 解释程序解释

6、程序输入数据源程序计算机系统计算机系统运行结果青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术81.3 编译过程概述编译过程概述u词法分析词法分析词法分析的任务是逐步地扫描和分解构成源词法分析的任务是逐步地扫描和分解构成源程序的字符串，识别出一个一个的单词符号程序的字符串，识别出一个一个的单词符号或符号。或符号。编译程序的词法分析也叫编译程序的词法分析也叫词法扫描词法扫描或线或线性扫性扫描描。 计算机高级语言的单词符号通常包括：标识计算机高级语言的单词符号通常包括：标识符、关键字或基本字、标点符号、常数、运符、关键字或基本字、标点符号、常数、运算符、分隔符等类型。算符、分隔

7、符等类型。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术91.3 编译过程概述编译过程概述符号符号类型类型while关键字(分隔符i标识符运算符100整常数)分隔符sum标识符=运算符sum标识符i标识符+运算符;分隔符例子例子1.1：while (i 100) sum = sum + i 词法分析的结果识别出的单词词法分析的结果识别出的单词 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术101.3 编译过程概述编译过程概述u语法分析语法分析语法分析的任务是在词法分析基础上，根据语法分析的任务是在词法分析基础上，根据语言的语法规则把单词符号串分解成

8、各类语语言的语法规则把单词符号串分解成各类语法单元（语法范畴、语法短语）法单元（语法范畴、语法短语）l例如例如“短语短语”、“子句子句”、“语句语句”、“程序程序段段”、“函数函数”和和“程序程序”等。等。语法分析是把线形序列的单词符号，根据语语法分析是把线形序列的单词符号，根据语言的语法规则，按照层次分解，结果通常表言的语法规则，按照层次分解，结果通常表示成语法示成语法分析树分析树。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术111.3 编译过程概述编译过程概述例子例子1.1while (i 100) sum = sum + i 语法分析树语法分析树while语句分

9、隔符分隔符(分隔符)表达式表达式；表达式循环体语句运算符赋值表达式变量常量100i变量表达式复合赋值运算符+sum+=运算符表达式变量i青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术121.3 编译过程概述编译过程概述u语义分析和中间代码生成语义分析和中间代码生成语义分析的任务是检查程序语义的正确性，语义分析的任务是检查程序语义的正确性，解释程序结构的含义。解释程序结构的含义。检查变量是否有定义，变量在使用前是否具检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等，其中的一个重要部有值，数值是否溢出等，其中的一个重要部分是进行类型的检查和转换。分是进行类型的检查和

10、转换。 语义分析完成之后，编译程序通常就依据语语义分析完成之后，编译程序通常就依据语言的语义规则、利用语法制导技术把源程序言的语义规则、利用语法制导技术把源程序翻译成某种中间代码。翻译成某种中间代码。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术131.3 编译过程概述编译过程概述中间代码是一种定义明确、便于处理、独立中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种于计算机硬件的记号系统，可以认为是一种抽象机的程序。其中一类是三地址代码，很抽象机的程序。其中一类是三地址代码，很象机器的汇编语言象机器的汇编语言 Lbegin：if i 100

11、goto Lbodygoto LendLbody：t1 := sum + isum := t1t2 := i + 1i := t2goto LbeginLend：青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术141.3 编译过程概述编译过程概述u中间代码优化中间代码优化主要任务是对前一阶段产生的中间代码进行主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标等价变换，以便产生速度快、空间小的目标代码。代码。 Lbegin：if i 100 goto Lbodygoto LendLbody：sum := sum + ii := i + 1goto L

12、beginLend：青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术151.3 编译过程概述编译过程概述u目标代码生成目标代码生成目标代码生成的主要任务是把（经过优化处目标代码生成的主要任务是把（经过优化处理的）中间代码翻译成特定的机器指令或汇理的）中间代码翻译成特定的机器指令或汇编程序。编程序。这个阶段的工作依赖于计算机的硬件结构和这个阶段的工作依赖于计算机的硬件结构和指令系统，主要涉及到机器指令的选择、各指令系统，主要涉及到机器指令的选择、各种类型变量存储空间的分配，以及寄存器的种类型变量存储空间的分配，以及寄存器的分配和调度，等等。分配和调度，等等。 青岛大学信息工程

13、学院青岛大学信息工程学院编译原理与技术编译原理与技术161.3 编译过程概述编译过程概述u目标代码生成目标代码生成MOV #100, R0/ 把常数100存入寄存器R0MOV i, R1/ 把变量i的值存入寄存器R1MOVsum，R2 / 把变量m的值存入寄存器R2Lbegin:CMP R1, R0 / 比较R1和R0的值，结果存入状态寄 存器CTJ Lend/ 状态寄存器CT1或2，即R1R0，程序转入单元Lend ADDR1, R2/ 把寄存器R1加R2，结果送入R2INCR1/ 寄存器R1的值加1JLbegin/ 无条件转移到地址LbeginLend:青岛大学信息工程学院青岛大学信息工程

14、学院编译原理与技术编译原理与技术171.4 编译程序的构成编译程序的构成 符号表管理错误处理词法分析器语法分析器语义分析与中间代码生器代码优化器目标代码生成器目标代码单词符号源程序语法单元中间代码中间代码青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术181.4 编译程序的构成基本功能编译程序的构成基本功能词法分析器，又叫扫描器，对输入的源程序执行词法词法分析器，又叫扫描器，对输入的源程序执行词法分析工作，输出单词符号序列。分析工作，输出单词符号序列。语法分析器，又叫分析器，对单词符号序列进行语法语法分析器，又叫分析器，对单词符号序列进行语法分析，识别出各类语法单元，判断输

15、入的符号串是否分析，识别出各类语法单元，判断输入的符号串是否构成语法正确的构成语法正确的“程序程序”。语义分析与中间代码生成器，对语法正确的各类程序语义分析与中间代码生成器，对语法正确的各类程序单元进行语义分析，并把它们翻译成一定形式的中间单元进行语义分析，并把它们翻译成一定形式的中间代码。代码。代码优化器，执行对中间代码的优化处理，以提高代代码优化器，执行对中间代码的优化处理，以提高代码的执行效率。码的执行效率。目标代码生成器，根据特定的机器把中间代码翻译成目标代码，目标代码生成器，根据特定的机器把中间代码翻译成目标代码，并进行优化处理。并进行优化处理。青岛大学信息工程学院青岛大学信息工程学

16、院编译原理与技术编译原理与技术191.4 编译程序的构成辅助功能编译程序的构成辅助功能符号表管理：把编译程序中的各种符号合理符号表管理：把编译程序中的各种符号合理地组织和管理，方便符号信息的添加、查询、地组织和管理，方便符号信息的添加、查询、更新和删除。更新和删除。错误诊断和报告错误诊断和报告 ：有效地识别、诊断、分析：有效地识别、诊断、分析和报告程序中的各种错误。和报告程序中的各种错误。分类：语法错误（词法错误和句法错误）和分类：语法错误（词法错误和句法错误）和语义错误这两类。语义错误这两类。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术201.5 其它与编译有关的概念

17、和技术其它与编译有关的概念和技术 u遍（趟）遍（趟）在编译的具体实现时，往往根据不同的源语在编译的具体实现时，往往根据不同的源语言、设计要求、使用对象以及编译程序所在言、设计要求、使用对象以及编译程序所在宿主机的内存等硬件条件，将编译过程组织宿主机的内存等硬件条件，将编译过程组织为若干遍（趟）。一个编译程序最终经过几为若干遍（趟）。一个编译程序最终经过几遍完成，就称为几遍编译。遍完成，就称为几遍编译。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术211.5 其它与编译有关的概念和技术其它与编译有关的概念和技术 u编译的前端和后端编译的前端和后端 编译前端只依赖于源程序，

18、独立于目标计算机。编译编译前端只依赖于源程序，独立于目标计算机。编译前端的工作包括词法分析、语法分析、语义分析、中前端的工作包括词法分析、语法分析、语义分析、中间代码生成及其优化，文法错误的处理和符号表的组间代码生成及其优化，文法错误的处理和符号表的组织也在编译前端完成。织也在编译前端完成。编译后端的工作主要是目标代码的生成和优化，独立编译后端的工作主要是目标代码的生成和优化，独立于源程序，完全依赖于目标机器和中间代码。于源程序，完全依赖于目标机器和中间代码。把编译程序分成前端和后端已经成为目前编译程序的把编译程序分成前端和后端已经成为目前编译程序的设计实践，其显著优点是，可以优化配置不同的编

19、译设计实践，其显著优点是，可以优化配置不同的编译程序组合，实现编译的重用，保持语言与机器的独立程序组合，实现编译的重用，保持语言与机器的独立性。性。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术221.5 其它与编译有关的概念和技术其它与编译有关的概念和技术u编译程序的分类编译程序的分类 诊断型编译程序：专门用于帮助程序的开发诊断型编译程序：专门用于帮助程序的开发和调试，它们系统地分析程序，发现程序中和调试，它们系统地分析程序，发现程序中的错误，智能地校正一些错误。的错误，智能地校正一些错误。优化型编译程序：这类编译程序着重于提高优化型编译程序：这类编译程序着重于提高目

20、标代码的时空效率，使得产生的目标代码目标代码的时空效率，使得产生的目标代码既占用较少的存储空间，又运行的快。既占用较少的存储空间，又运行的快。青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术231.5 其它与编译有关的概念和技术其它与编译有关的概念和技术交叉型编译程序：运行目标程序的计算机和交叉型编译程序：运行目标程序的计算机和运行编译程序的计算机的型号不相同运行编译程序的计算机的型号不相同 。利用编译前端和后端的技术，可以设计与目利用编译前端和后端的技术，可以设计与目标机无关的编译程序，利用编译后端就可以标机无关的编译程序，利用编译后端就可以改变目标计算机，这样编译方便移

21、植，称为改变目标计算机，这样编译方便移植，称为可变目标型编译程序。可变目标型编译程序。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术241.6 编译技术和软件工具编译技术和软件工具u语法制导编辑器语法制导编辑器 这类工具运用程序语言的语法知识，在用户这类工具运用程序语言的语法知识，在用户编写程序的时候按照词法和语法分析的信息编写程序的时候按照词法和语法分析的信息提供智能的帮助，包括自动地提供关键字及提供智能的帮助，包括自动地提供关键字及其匹配的关键字、左右括号的配对、对象的其匹配的关键字、左右括号的配对、对象的属性和操作，等等。属性和操作，等等。 u程序调试工具程序调试

22、工具 调试的目的是根据程序的异常，追踪和确定调试的目的是根据程序的异常，追踪和确定错误在程序中的具体位置，并且修改程序，错误在程序中的具体位置，并且修改程序，消除错误。消除错误。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术251.6 编译技术和软件工具编译技术和软件工具u程序测试工具程序测试工具 程序测试是为了发现错误而执行程序的过程，程序测试是为了发现错误而执行程序的过程，基于编译技术的测试辅助工具可以分为静态基于编译技术的测试辅助工具可以分为静态分析器和动态测试工具。分析器和动态测试工具。u程序理解工具程序理解工具 在软件测试、软件维护以及软件的再向工程在软件测试

23、、软件维护以及软件的再向工程和逆向工程等工作中，需要人们理解和分析和逆向工程等工作中，需要人们理解和分析程序，得到需要的软件信息，这类工具称为程序，得到需要的软件信息，这类工具称为程序理解工具。程序理解工具。 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术261.7 如何开发编译程序如何开发编译程序 u手工编写编译程序手工编写编译程序 u编译程序的自动生成技术编译程序的自动生成技术 u编译程序的自展技术 Ln=LL0L1.青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术271.7 如何开发编译程序如何开发编译程序 u编译程序的移植技术编译程序的移植技术用宿主计算机上的高级语言编写一个能在另用宿主计算机上的高级语言编写一个能在另外类型目标机上运行的编译程序外类型目标机上运行的编译程序 A BHH KMA BK图1.7 把机器H上的编译移植到机器K上 青岛大学信息工程学院青岛大学信息工程学院编译原理与技术编译原理与技术281.7 编译系统以及其它相关程序编译系统以及其它相关程序 编译系统 预处理器源程序 编辑器 修改后的源程序 汇编程序 可重定位的目标程序 可执行的目标程序 函数库 可重定位的目标文件 连接器与加载器特性器调试器解释器配置与版本控制器源程序 汇编器编译器 源程序 青岛大学信息