编译原理第1章

1、编译原理(第3版）2 编译原理这门课程主要介绍编译原理这门课程主要介绍设计设计和构造和构造编译程序编译程序的基本原理和常用的的基本原理和常用的技术和方法技术和方法。本章重点介绍编译程序的本章重点介绍编译程序的基本概念基本概念。3 翻译程序是指这样一个程序翻译程序是指这样一个程序, ,它把它把一种语言一种语言( (称作源语言称作源语言) )所写的程序所写的程序( (源源程序程序) )翻译成等价的另一种语言翻译成等价的另一种语言( (称作称作目标语言目标语言) )的程序的程序( (目标程序目标程序) )。 高级语言程序机器语言程序翻译程序#include int main(void) printf

2、(hello, worldn); return 0; 00 00 10 10.4 编译程序编译程序是一种是一种翻译程序翻译程序，它将，它将高级语言高级语言所写的所写的源程序源程序翻译成翻译成等价的等价的机器语言机器语言或或汇编语言汇编语言的的目标程序目标程序。 源程序源程序高级语言程序高级语言程序编译程序编译程序目标程序目标程序汇编语言或者汇编语言或者机器语言程序机器语言程序5 采用编译方式在计算机上执行用高级采用编译方式在计算机上执行用高级语言编写的程序，需分阶段进行。语言编写的程序，需分阶段进行。第一种情况：第一种情况：源程序源程序编编译译程程序序机器语言机器语言目标程序目标程序初始数据初

3、始数据运行系统运行系统结果结果编编 译译 阶阶 段段运运 行行 阶阶 段段高级语言高级语言 程序程序6第二种情况：第二种情况：源程序源程序编编译译程程序序机器机器语言语言目标目标程序程序初始数据初始数据运行系统运行系统结果结果编编 译译 阶阶 段段运行阶段运行阶段汇汇编编程程序序汇编汇编语言语言目标目标程序程序汇汇 编编 阶阶 段段高级语言高级语言 程序程序7 将英文句子将英文句子 “I wish you success ”翻译成中文句子的大致过程是：翻译成中文句子的大致过程是：q 词法分析词法分析q 语法分析语法分析q 语义分析语义分析q 修饰工作修饰工作q 翻译成文翻译成文 8 编译程序是

4、将一种语言形式翻译成编译程序是将一种语言形式翻译成另一种语言形式，因此，其工作过程一另一种语言形式，因此，其工作过程一般可划分为如下五个阶段：般可划分为如下五个阶段： q 词法分析词法分析 q 语法分析语法分析 q 语义分析和中间代码生成语义分析和中间代码生成 q 代码优化代码优化 q 目标代码生成目标代码生成9 float r，h，s； s = 2* *3.1416 * * r * *(rh);例如例如 计算圆柱体表面积的程序计算圆柱体表面积的程序 片断如下：片断如下：10 词法分析阶段的任务是对构成词法分析阶段的任务是对构成源程序的源程序的字符串字符串从左到右进行扫描从左到右进行扫描和分解

5、，根据语言的和分解，根据语言的词法规则词法规则，识，识别出一个一个具有独立意义的别出一个一个具有独立意义的单词单词( 也称也称单词符号单词符号, 简称简称符号符号 )。1. 11 词法规则词法规则是单词符号的形成规则是单词符号的形成规则, ,它规定了哪样的字符串构成一个单词它规定了哪样的字符串构成一个单词符号。符号。 float r float r，h h，s s； s = 2s = 2* *3.14163.1416* *r r* *(h(hr)r)；例如例如12 上述源程序通过词法分析识别出上述源程序通过词法分析识别出如下单词符号：如下单词符号： 基本字基本字 float 标识符标识符 r、

6、h、s 常数常数 3.1416、2 算符算符 * * 、 界符界符 （、（、 ）、）、 ；、；、 ，、，、= 13 语法分析的任务是在词法分析的基语法分析的任务是在词法分析的基 础上础上, 根据语言的根据语言的语法规则语法规则从从单词符单词符 号串号串中识别出各种中识别出各种语法单位语法单位 ( 如表如表 达式、说明、语句等达式、说明、语句等 ) , ,并进行并进行语法语法 检查检查, ,即检查各种语法单位在语法结即检查各种语法单位在语法结 构上的正确性。构上的正确性。 14 语言的语言的语法规则语法规则规定了如何从单规定了如何从单词符号形成语法单位，词符号形成语法单位，语法规则语法规则是语是

7、语法单位的形成规则。法单位的形成规则。 float r float r，h h，s s； s = 2s = 2* *3.14163.1416* *r r* *(h(hr)r)；例如例如15 单词符号串单词符号串 s=2* *3.1416 * * r * *(hr)中，中，“s” 是是，单词符号串，单词符号串 “2 * * 3.1416 * * r * *(hr)”组合成组合成这样的语法单位这样的语法单位 , 由由=构成构成这这样的语法单位。样的语法单位。16 语义分析语义分析的任务是首先对每种语的任务是首先对每种语法单位进行静态的语义审查，然后分法单位进行静态的语义审查，然后分析其含义析其含义

8、，并用另一种语言形式并用另一种语言形式 (比比源语言更接近于目标语言的一种中间源语言更接近于目标语言的一种中间代码或直接用目标语言代码或直接用目标语言 ) 来描述这种来描述这种语义。语义。17 将将s = 2* *3.1416 * * r * *(hr)翻译成如下翻译成如下形式的四元式中间代码：形式的四元式中间代码：(1) ( * *, 2, 3.1416, T1 ) (2) ( * *, T1, r, T2 )(3) ( +, h, r, T3 )(4) ( * *, T2, T3, T4 )(5) ( =, T4, _, s )18 代码优化的任务是对前阶段产生的代码优化的任务是对前阶段产

9、生的中间代码进行中间代码进行等价变换或改造等价变换或改造，以期获得，以期获得更为更为高效即省时间和空间的目标代码高效即省时间和空间的目标代码。优。优化主要包括局部优化和循环优化等，例如化主要包括局部优化和循环优化等，例如上述四元式经局部优化后得：上述四元式经局部优化后得： (1) ( * *, 6.28, r, T2 )(2) ( +, h, r, T3 )(3) ( * *, T2, T3, T4 )(4) ( =, T4, _, s )19 目标代码生成的任务是将中间目标代码生成的任务是将中间代码变换成特定机器上的绝对指令代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编代码或可

10、重定位的指令代码或汇编指令代码。指令代码。 20表格管理和错误处理表格管理和错误处理 编译程序在工作过程中需要建立一编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在些表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各编译过程中所产生的一些信息，编译各个阶段的工作都涉及到个阶段的工作都涉及到构造、查找、修构造、查找、修改或存取有关表格中的信息改或存取有关表格中的信息，因此，在，因此，在编译程序中必须有一组管理各种表格的编译程序中必须有一组管理各种表格的程序。程序。 在编译程序的各个阶段中，都要涉及在编译程序的各个阶段中，都要涉及表格管理和错误处理表格管理和错误处理

11、。21表格管理和错误处理表格管理和错误处理 一个好的编译程序在编译过程中，一个好的编译程序在编译过程中，应具有应具有广泛的程序查错能力广泛的程序查错能力，并能准确，并能准确地报告错误的种类及出错位置，以便用地报告错误的种类及出错位置，以便用户查找和纠正，因此，在编译程序中还户查找和纠正，因此，在编译程序中还必须有一个出错处理程序。必须有一个出错处理程序。 22编译程序的结构编译程序的结构 源程序源程序语义分析和中间代码生成程序语义分析和中间代码生成程序语法分析程序语法分析程序词法分析程序词法分析程序代码优化程序代码优化程序目标代码生成程序目标代码生成程序 目标程序目标程序表表格格管管理理程程序

12、序出出错错处处理理程程序序( 字符串字符串)231.3 编译程序的生成方法编译程序的生成方法q 对源语言和目标语言认真分析对源语言和目标语言认真分析q 设计编译算法设计编译算法q 选择语言编制程序选择语言编制程序q 调试编译程序调试编译程序q 提交相关文档资料提交相关文档资料 编译程序是一个复杂的系统程序，要编译程序是一个复杂的系统程序，要生成一个编译程序一般要考虑以下几方面：生成一个编译程序一般要考虑以下几方面：24编译程序的自动生成编译程序的自动生成 如目前已广为使用词法分析程序的自如目前已广为使用词法分析程序的自动生成系统动生成系统LEX和语法分析程序自动生成和语法分析程序自动生成系统系

13、统YACC等，此外等，此外, 还有可用来自动产还有可用来自动产生整个编译程序的软件工具：编译程序产生整个编译程序的软件工具：编译程序产生器生器, 它的功能是将任一语言的词法规则、它的功能是将任一语言的词法规则、语法规则和语义解释的描述作为输入，自语法规则和语义解释的描述作为输入，自动生成该语言的编译程序。动生成该语言的编译程序。 随着编译技术和自动机理论的发展随着编译技术和自动机理论的发展, 近近年来已研制出了一些编译程序的年来已研制出了一些编译程序的自动生成自动生成系统系统。25编译程序的自动生成编译程序的自动生成 生成编译程序的方法还常采用生成编译程序的方法还常采用自编译自编译方式方式和移

14、植方式和移植方式。 随着并行技术和并行语言的发展，处随着并行技术和并行语言的发展，处理并行语言的并行编译技术和将串行程序理并行语言的并行编译技术和将串行程序转换成并行程序的转换成并行程序的自动并行编译技术自动并行编译技术正在正在深入研究之中。深入研究之中。261.4 编译技术在软件开发中的应用编译技术在软件开发中的应用 虽然我们只有少数人从事构造或虽然我们只有少数人从事构造或维护程序语言编译程序的工作维护程序语言编译程序的工作, ,但是，但是，大部分系统软件和应用软件的开发，大部分系统软件和应用软件的开发，通常要用到编译的原理和技术。通常要用到编译的原理和技术。271.4 编译技术在软件开发中

15、的应用编译技术在软件开发中的应用 例如例如, ,设计词法分析器的串匹配设计词法分析器的串匹配技术已用于技术已用于正文编辑器、信息检索正文编辑器、信息检索系统和模式识别程序；系统和模式识别程序；上下文无关上下文无关文法和语法制导定义已用于创建诸文法和语法制导定义已用于创建诸如如排版、绘图系统排版、绘图系统和语言结构化编和语言结构化编辑器中，代码优化技术已用于辑器中，代码优化技术已用于程序程序验证器验证器和和从非结构化的程序产生结从非结构化的程序产生结构化程序构化程序的编程之中。的编程之中。 28q 编译过程的五个阶段编译过程的五个阶段q 编译程序的结构框图编译程序的结构框图编译程序编译程序是一种翻译程序，它将高是一种翻译程序，它将高级语言所写的源程序级语言所写的源程