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

《编译原理与技术讲义-第1章》由会员分享，可在线阅读，更多相关《编译原理与技术讲义-第1章（30页珍藏版）》请在金锄头文库上搜索。

1、编译原理与技术第1章 概论青岛大学信息工程学院主要内容u为什么学习编译u什么叫编译程序 u编译过程概述u编译程序的构成u与编译有关的概念和技术 u如何开发编译程序 u编译系统以及其它相关程序2青岛大学信息工程学院1.1 为什么学习编译u编译程序构造的原理和技术一直属于计 算机科学必备的专业基础知识。u是计算机科学中一个非常成功的分支， 也是最早获得成功的分支之一。u它所建立的理论、技术和方法值得深入 研究和学习。编译构造正确地建立了研究的问题领域和研 究方式。3青岛大学信息工程学院1.1 为什么学习编译针对编译程序构造的某些部分已经开发了标 准的形式化技术，包括有限自动机理论、上 下文无关文法

2、、正规表达式、属性文法、机 器代码描述、数据流分析方程式等。 编译程序包含许多普遍使用的数据结构和算 法，例如散列法（哈希算法）、栈机制、堆 机制、垃圾收集、集合算法、表驱动算法。编译程序的许多构造技术已经得到了广泛的 应用。学习编译原理和技术还有助于我们理解程序 设计语言，编写优秀的软件。 4青岛大学信息工程学院1.2 什么叫编译程序u概念翻译程序或翻译器是把一种语言（源语言） 转换成等价的另外一种语言（目标语言）的 程序。如果源语言是高级编程语言，目标语言是机 器代码和汇编语言这样的低级语言，这类翻 译程序就叫做编译程序或编译器。 5青岛大学信息工程学院1.2 什么叫编译程序编译执行方式：

3、把源程序用编译程序翻译成 机器可以执行的目标程序或目标代码，然后 才能接受输入数据运行。 编译程序源程序输入数据目标程序计算机系统目标程序运行结果6青岛大学信息工程学院1.2 什么叫编译程序解释程序：解释程序不产生源程序的目标代 码，而是对源程序逐条语句的分析，根据每 个语句的含义执行产生结果。 解释程序输入数据源程序计算机系统运行结果7青岛大学信息工程学院1.3 编译过程概述u词法分析词法分析的任务是逐步地扫描和分解构成源 程序的字符串，识别出一个一个的单词符号 或符号。编译程序的词法分析也叫词法扫描或线性扫 描。 计算机高级语言的单词符号通常包括：标识 符、关键字或基本字、标点符号、常数、

4、运 算符、分隔符等类型。 8青岛大学信息工程学院1.3 编译过程概述符号类型while关键字(分隔符i标识符运算符100整常数)分隔符sum标识符=运算符sum标识符i标识符+运算符;分隔符例子1.1：while (i 100) sum = sum + i 词法分析的结果识别出的单词 9青岛大学信息工程学院1.3 编译过程概述u语法分析语法分析的任务是在词法分析基础上，根据 语言的语法规则把单词符号串分解成各类语 法单元（语法范畴、语法短语）l例如“短语”、“子句”、“语句”、“程序段”、“函 数”和“程序”等。语法分析是把线形序列的单词符号，根据语 言的语法规则，按照层次分解，结果通常表 示

5、成语法分析树。 10青岛大学信息工程学院1.3 编译过程概述例子1.1while (i 100) sum = sum + i 语法分析树while语句分隔符分隔符(分隔符)表达式表达式；表达式循环体语句运算符赋值表达式变量常量100i变量表达式复合赋值运算符+sum+=运算符表达式变量i11青岛大学信息工程学院1.3 编译过程概述u语义分析和中间代码生成语义分析的任务是检查程序语义的正确性， 解释程序结构的含义。检查变量是否有定义，变量在使用前是否具 有值，数值是否溢出等，其中的一个重要部 分是进行类型的检查和转换。 语义分析完成之后，编译程序通常就依据语 言的语义规则、利用语法制导技术把源程

6、序 翻译成某种中间代码。 12青岛大学信息工程学院1.3 编译过程概述中间代码是一种定义明确、便于处理、独立 于计算机硬件的记号系统，可以认为是一种 抽象机的程序。其中一类是三地址代码，很 象机器的汇编语言 Lbegin：if i 100 goto Lbody goto Lend Lbody：t1 := sum + i sum := t1 t2 := i + 1 i := t2 goto Lbegin Lend：13青岛大学信息工程学院1.3 编译过程概述u中间代码优化主要任务是对前一阶段产生的中间代码进行 等价变换，以便产生速度快、空间小的目标 代码。 Lbegin：if i 100 got

7、o Lbody goto Lend Lbody：sum := sum + i i := i + 1 goto Lbegin Lend：14青岛大学信息工程学院1.3 编译过程概述u目标代码生成目标代码生成的主要任务是把（经过优化处 理的）中间代码翻译成特定的机器指令或汇 编程序。这个阶段的工作依赖于计算机的硬件结构和 指令系统，主要涉及到机器指令的选择、各 种类型变量存储空间的分配，以及寄存器的 分配和调度，等等。 15青岛大学信息工程学院1.3 编译过程概述u目标代码生成MOV #100, R0/ 把常数100存入寄存器R0 MOV i, R1/ 把变量i的值存入寄存器R1 MOVsum，R

8、2 / 把变量m的值存入寄存器R2 Lbegin:CMP R1, R0 / 比较R1和R0的值，结果存入状态寄 存器CT J Lend/ 状态寄存器CT1或2，即R1R0，程序转入单元 Lend ADDR1, R2/ 把寄存器R1加R2，结果送入R2 INCR1/ 寄存器R1的值加1 JLbegin/ 无条件转移到地址Lbegin Lend:16青岛大学信息工程学院1.4 编译程序的构成 符号表管理错误处理词法分析器语法分析器语义分析与 中间代码生器代码优化器目标代码生成器目标代码单词符号源程序语法单元中间代码中间代码17青岛大学信息工程学院1.4 编译程序的构成基本功 能词法分析器，又叫扫描

9、器，对输入的源程序执行词 法分析工作，输出单词符号序列。语法分析器，又叫分析器，对单词符号序列进行语 法分析，识别出各类语法单元，判断输入的符号串 是否构成语法正确的“程序”。语义分析与中间代码生成器，对语法正确的各类程 序单元进行语义分析，并把它们翻译成一定形式的 中间代码。代码优化器，执行对中间代码的优化处理，以提高 代码的执行效率。目标代码生成器，根据特定的机器把中间代码翻译成目标代 码，并进行优化处理。18青岛大学信息工程学院1.4 编译程序的构成辅助功 能符号表管理：把编译程序中的各种符号合理 地组织和管理，方便符号信息的添加、查询 、更新和删除。错误诊断和报告 ：有效地识别、诊断、

10、分 析和报告程序中的各种错误。分类：语法错误（词法错误和句法错误）和 语义错误这两类。19青岛大学信息工程学院1.5 其它与编译有关的概念和 技术 u遍（趟）在编译的具体实现时，往往根据不同的源语 言、设计要求、使用对象以及编译程序所在 宿主机的内存等硬件条件，将编译过程组织 为若干遍（趟）。一个编译程序最终经过几 遍完成，就称为几遍编译。 20青岛大学信息工程学院1.5 其它与编译有关的概念和 技术 u编译的前端和后端 编译前端只依赖于源程序，独立于目标计算机。编 译前端的工作包括词法分析、语法分析、语义分析 、中间代码生成及其优化，文法错误的处理和符号 表的组织也在编译前端完成。编译后端的

11、工作主要是目标代码的生成和优化，独 立于源程序，完全依赖于目标机器和中间代码。把编译程序分成前端和后端已经成为目前编译程序 的设计实践，其显著优点是，可以优化配置不同的 编译程序组合，实现编译的重用，保持语言与机器 的独立性。 21青岛大学信息工程学院1.5 其它与编译有关的概念和 技术u编译程序的分类 诊断型编译程序：专门用于帮助程序的开发 和调试，它们系统地分析程序，发现程序中 的错误，智能地校正一些错误。优化型编译程序：这类编译程序着重于提高 目标代码的时空效率，使得产生的目标代码 既占用较少的存储空间，又运行的快。22青岛大学信息工程学院1.5 其它与编译有关的概念和 技术交叉型编译程

12、序：运行目标程序的计算机和 运行编译程序的计算机的型号不相同 。利用编译前端和后端的技术，可以设计与目 标机无关的编译程序，利用编译后端就可以 改变目标计算机，这样编译方便移植，称为 可变目标型编译程序。 23青岛大学信息工程学院1.6 编译技术和软件工具u语法制导编辑器 这类工具运用程序语言的语法知识，在用户 编写程序的时候按照词法和语法分析的信息 提供智能的帮助，包括自动地提供关键字及 其匹配的关键字、左右括号的配对、对象的 属性和操作，等等。 u程序调试工具 调试的目的是根据程序的异常，追踪和确定 错误在程序中的具体位置，并且修改程序， 消除错误。 24青岛大学信息工程学院1.6 编译技

13、术和软件工具u程序测试工具 程序测试是为了发现错误而执行程序的过程 ，基于编译技术的测试辅助工具可以分为静 态分析器和动态测试工具。u程序理解工具 在软件测试、软件维护以及软件的再向工程 和逆向工程等工作中，需要人们理解和分析 程序，得到需要的软件信息，这类工具称为 程序理解工具。 25青岛大学信息工程学院1.7 如何开发编译程序 u手工编写编译程序 u编译程序的自动生成技术 u编译程序的自展技术 Ln=LL0L1.26青岛大学信息工程学院1.7 如何开发编译程序 u编译程序的移植技术用宿主计算机上的高级语言编写一个能在另 外类型目标机上运行的编译程序 A BHH KMA BK图1.7 把机器

14、H上的编译移植到机器K上 27青岛大学信息工程学院1.7 编译系统以及其它相关程 序 编译系统 预处理器源程序 编辑器修改后的源程序 汇编程序 可重定位的目标程序 可执行的目标程序 函数库 可重定位的目标文件 连接器与 加载器特性器调试器解释器配置与 版本控制器源程序 汇编器编译器源程序 28青岛大学信息工程学院1.7 编译系统以及其它相关程 序编辑器：程序员借助编辑器编写源程序，由 编辑器产生出标准的正文文件（如ASCII文 件）作为编译程序的输入。 预处理器：它是在编译程序真正开始翻译源 程序之前调用的一个独立的程序，以便加快 和简化翻译工作。 汇编器 ：汇编器把汇编语言代码翻译成一 个特定的机器指令序列。连接器：搜集和组织程序所需要的不同代码 和数据，把它们连接成可以执行的目标代码 的工具。29青岛大学信息工程学院1.7 编译系统以及其它相关程 序装载器：给程序在内存器中分配一个起始地 址，载入目标机器，以便程序中的各个符号 通过相对地址可以真实地访问存储器。 调试器 ：用来确定编译过的程序在运行时 的错误。 特性器： 这是搜集运行程序行为特征的统 计数据的软件工具。 配置与版本控制器：管理和维护每个独立的 源程序模块、编译模块、数据文件及其每个 文件的修改历史信息包括模块连接、加载的 信息等的工具。 30