第1章 绪论new (编译原理 陈火旺)

1、编译原理编译原理 主讲：周雁主讲：周雁Email：课程的性质课程的性质v计算机专业的专业基础课计算机专业的专业基础课v是软件技术基础是软件技术基础v是计算机专业的学生必修的一门主干课是计算机专业的学生必修的一门主干课学习编译原理的目的学习编译原理的目的v通过本课程主要学习编译程序构造的基本原理和技术通过本课程主要学习编译程序构造的基本原理和技术v加深对程序研发过程的理解加深对程序研发过程的理解v加深对程序执行过程的认识加深对程序执行过程的认识v进一步编好程序进一步编好程序v为将来从事系统软件和软件工具研究与开发打下基础为将来从事系统软件和软件工具研究与开发打下基础v提高计算机专业素养（计算机专

2、业的提高计算机专业素养（计算机专业的“诗经诗经”）学习任务学习任务v掌握编译的理论基础和形式化系统掌握编译的理论基础和形式化系统v了解编译的全过程及其具体的实现方法了解编译的全过程及其具体的实现方法成绩考核方法成绩考核方法v成绩考核方法成绩考核方法 平时成绩占平时成绩占20实践成绩占实践成绩占30% 期末考试成绩占期末考试成绩占50v平时成绩为平时成绩为 课堂点名课堂点名+作业作业学习方法及要求学习方法及要求v认真听课，认真理解书中的基本概念、基本原理与基认真听课，认真理解书中的基本概念、基本原理与基本算法本算法v弄懂书中的例题与习题弄懂书中的例题与习题v在看书时或理解例题时，一定要划出相应的

3、细节变化在看书时或理解例题时，一定要划出相应的细节变化过程，通过画图来加深理解过程，通过画图来加深理解v在理解的基础上记忆在理解的基础上记忆v理论结合实践理论结合实践v上课、上机纪律！上课、上机纪律！v编译原理课程学习方法之我见：编译原理课程学习方法之我见：(1)编译原理与离散数学的关系编译原理与离散数学的关系(2)“游戏游戏”与与“游戏规则游戏规则”*例如，有一个文法例如，有一个文法 : (0)E E+E | E*E | (E) | i 请采用最右推导最右推导产生句子i+i*i : 解：E E+E E+E*E E+E*i E+i*i i+i*i“变形金刚变形金刚”游戏规则：游戏规则：1.从开

4、始符号开始变形；从开始符号开始变形；2.每次按照每次按照“变形规则变形规则” 将将一个一个式子的左部变形为右部；式子的左部变形为右部；3. 每次变形串中每次变形串中最右边最右边的大写字母，一直变形到目标串的大写字母，一直变形到目标串(不含大写字母不含大写字母)为止。为止。*试采用最右推导产生句子试采用最右推导产生句子:(1) i*(i+i) (2) i*(i+i*i ) C语言的复习：语言的复习：编写程序编写程序要求：要求：让用户输入一个字符，然后判断让用户输入一个字符，然后判断(如果用户输入如果用户输入多个字符，只判断第一个多个字符，只判断第一个)：1.若是字母，在屏幕上输出该字母若是字母，

5、在屏幕上输出该字母ASC值；值；2.若是数字，在屏幕上输出该数字的二进制值；若是数字，在屏幕上输出该数字的二进制值；3.若是若是*/，在屏幕上输出，在屏幕上输出“输入为算符输入为算符”；4.若是其它字符，在屏幕上输出若是其它字符，在屏幕上输出“非法输入！非法输入！”。第第1章章 引论引论内容简介内容简介v 程序的翻译程序的翻译v 编译程序的工作过程编译程序的工作过程v 编译程序的结构编译程序的结构v 编译程序的组织方式编译程序的组织方式v 编译程序的构造编译程序的构造第第1章章 引论引论教学要求教学要求v掌握：编译的概念，编译的过程掌握：编译的概念，编译的过程v理解：编译的各个阶段理解：编译的

6、各个阶段v了解：编译的结构和组合了解：编译的结构和组合1.0 程序设计语言程序设计语言程序设计语言程序设计语言 在计算机上如何执行一个高级语言程序？在计算机上如何执行一个高级语言程序？把高级语言程序翻译成机器语言程序把高级语言程序翻译成机器语言程序1.运行所得的机器语言程序求得计算结果运行所得的机器语言程序求得计算结果v机器语言机器语言 001110010010001110010010v汇编语言汇编语言 ADDADDv高级语言高级语言 begin x:=9+2 endbegin x:=9+2 end v各种程序设计语言都有自己的语法和语义体各种程序设计语言都有自己的语法和语义体系，其编译程序根

7、据这种语言的语法和语义系，其编译程序根据这种语言的语法和语义将其翻译成机器能够接受的机器语言。将其翻译成机器能够接受的机器语言。v程序设计语言是按一定规则排列的符号集合程序设计语言是按一定规则排列的符号集合，而，而编译程序就是把这些符号集合变成机器编译程序就是把这些符号集合变成机器指令的转换器指令的转换器，编译程序又称为编译器。，编译程序又称为编译器。软件分类软件分类v软件软件 计算机系统中的程序及其文档计算机系统中的程序及其文档v系统软件系统软件 居于计算机系统中最靠近硬件的一层，其他软件居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用，如一般都通过系统软件发挥作用，如编

8、译系统编译系统和操作和操作系统。系统。 v应用软件应用软件 把软件语言编写的各种程序处理成可在计算机上把软件语言编写的各种程序处理成可在计算机上执行的程序。执行的程序。操作系统编译系统编译系统裸机编译程序的重要性编译程序的重要性v使得计算机用户不必考虑与机器有关的繁琐细节使得计算机用户不必考虑与机器有关的繁琐细节v使程序员和程序设计人员独立于机器使程序员和程序设计人员独立于机器 一、翻译程序的定义一、翻译程序的定义 程序的翻译通常有两种方式程序的翻译通常有两种方式：1.1.编译编译2.2.解释解释翻译：翻译： 是指能将用甲语言（源语言）编写的程序，在是指能将用甲语言（源语言）编写的程序，在不改

9、变语义不改变语义的条件下转换成用乙语言（目标语言）书写的程序。的条件下转换成用乙语言（目标语言）书写的程序。 高级语言程序高级语言程序翻译翻译机器语言程序机器语言程序1.1 什么是编译程序什么是编译程序(compiler)二、什么是编译程序二、什么是编译程序(compiler)(compiler)v编译程序编译程序 是一个语言翻译程序是一个语言翻译程序, ,是将用是将用高级语言高级语言书写的源程序翻译成等价的书写的源程序翻译成等价的低级语言低级语言的目标的目标程序。程序。C、PASCLE、JAVA等等机器语言、汇编语言机器语言、汇编语言v编译程序的功能编译程序的功能一个编译程序就是一个语言翻译

10、程序，它把一种语言一个编译程序就是一个语言翻译程序，它把一种语言( (称作称作源语言源语言) )编写的程序翻译成另一种语言编写的程序翻译成另一种语言 ( (称作称作目目标语言标语言) )的等价的程序的等价的程序. .v世界上第一个编译程序世界上第一个编译程序FORTRANFORTRAN编译程序是编译程序是2020世纪世纪5050年代中期研制成功。年代中期研制成功。高级语言书高级语言书写的程序写的程序编译程序编译程序 低级语言程序低级语言程序1.编译方式是一种分阶段进行的方式。编译方式是一种分阶段进行的方式。 两个阶段的转换：两个阶段的转换：v编译阶段编译阶段 v运行阶段运行阶段 三、三、 编译

11、方式编译方式源程序编译程序目标程序编译时初始数据计算结果运行时目标代码运行子程序三个阶段的转换：三个阶段的转换：v编译阶段编译阶段v汇编阶段汇编阶段 v运行阶段运行阶段 源程序汇编语言编译时编译程序汇编程序目标代码汇编时初始数据计算结果运行时目标代码运行字程序2.编译方式的特点编译方式的特点 编译方式下，生成了编译方式下，生成了目标代码目标代码，且可多次执行。，且可多次执行。 在编译方式下，源程序的执行需要在编译方式下，源程序的执行需要分阶段分阶段。v如果编译后的目标程序是机器语言程序，则源程序如果编译后的目标程序是机器语言程序，则源程序的执行分为的执行分为两大阶段两大阶段：编译阶段和运行阶段

12、。：编译阶段和运行阶段。v如果编译后的目标程序是汇编语言程序，如果编译后的目标程序是汇编语言程序， 则源程序则源程序的执行分为的执行分为三大阶段三大阶段：编译阶段、汇编阶段和运行：编译阶段、汇编阶段和运行阶段。阶段。 完成解释工作的解释程序将按源程序中完成解释工作的解释程序将按源程序中语语句的动态顺序句的动态顺序，逐句地进行分析解释，并立，逐句地进行分析解释，并立即予以执行。即予以执行。v优点优点：直观易懂，结构简单，易于实现人机对话直观易懂，结构简单，易于实现人机对话v缺点缺点：效率低效率低四、四、 解释方式解释方式 源程序解释执行的历程源程序解释执行的历程 在解释方式下，并在解释方式下，并

13、不生成目标代码不生成目标代码，而是直接执，而是直接执行源程序本身。这是编译方式与解释方式的根本区行源程序本身。这是编译方式与解释方式的根本区别。别。 先看自然语言的翻译先看自然语言的翻译v1. 识别出句子中的一个个单字识别出句子中的一个个单字v2. 分析句子的语法结构分析句子的语法结构v3. 初步翻译句子的含意初步翻译句子的含意v4. 译文修饰译文修饰v5. 写出最后译文写出最后译文1.2 1.2 编译过程概述编译过程概述 编译的五个阶段编译的五个阶段v1. 词法分析词法分析v2. 语法分析语法分析v3. 语义分析中间代码生成语义分析中间代码生成v4. 优化优化v5. 目标代码生成目标代码生成

14、1.2 1.2 编译过程概述编译过程概述 目标代码源程序出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理1.2 1.2 编译过程概述编译过程概述举例说明：举例说明：有一个有一个C C语言程序，对它进行编译语言程序，对它进行编译void jisuan() int y,c,b; float x,a,b; x=a+b-50; y=c+(d+x)+b; 1.2 1.2 编译过程概述编译过程概述 一、词法分析一、词法分析 void jisuan() int y,c,b; float x,a,b; x=a+b-50; y=c+(d+x)+b; 识别右边程序中

15、的单词识别右边程序中的单词基本字：基本字：标识符：标识符：整常数：整常数：运算符：运算符：界限符界限符：v任务：任务： 输入源程序，对构成源程序的字符串进行输入源程序，对构成源程序的字符串进行 扫描和分析，识别出一个个的单词。扫描和分析，识别出一个个的单词。v单词：单词： 是高级语言中有实在意义的最小语法单位，是高级语言中有实在意义的最小语法单位，它由字符构成。它由字符构成。void 、int 、 floata、b、c、d、x、y、 jisuan50、=（ ），）， ；一、一、 词法分析词法分析 转换：转换： 对基本字、运算符、界限符的转换；对基本字、运算符、界限符的转换； 标识符的转换；标识

16、符的转换； 常数的转换；常数的转换； 转换完成后的格式转换完成后的格式：（单词种别：（单词种别 单词值）单词值） 词法分析依照词法规则，识别出正确地单词，词法分析依照词法规则，识别出正确地单词，转换转换成统一规格，备用。成统一规格，备用。描述词法规则：描述词法规则：有效工具是正规式和有限自动机有效工具是正规式和有限自动机二、语法分析二、语法分析 语法规则：语法规则：语言的规则，又称为语言的规则，又称为文法文法；规定单词如何构；规定单词如何构 成短语、语句、过程和程序。成短语、语句、过程和程序。 任务：任务： 在词法分析的基础上，根据语言的在词法分析的基础上，根据语言的语法规则语法规则， 把单词

17、符号组成各类的语法单位：短语、子把单词符号组成各类的语法单位：短语、子 句、语句、过程、程序。句、语句、过程、程序。语法规则的表示：语法规则的表示： （Backus Backus 范式）范式） BNF: A:=B|CBNF: A:=B|C 读做读做“A A定义为定义为B B或或C”C”语法分析方法：语法分析方法： 推导和归纳。推导和归纳。三、三、 语义分析与中间代码产生语义分析与中间代码产生 中间代码的形式：中间代码的形式： 四元式、三元式、逆波兰式四元式、三元式、逆波兰式 任务：任务： 对语法分析识别出的各类对语法分析识别出的各类语法范畴语法范畴，分析其含，分析其含 义，进行和初步翻译，产生

18、介于源代码和目义，进行和初步翻译，产生介于源代码和目 标代码之间的一种代码。标代码之间的一种代码。分为两个阶段：分为两个阶段： & 对每种语法范畴进行静态语义检查对每种语法范畴进行静态语义检查 & 若语义正确，就进行中间代码的翻译若语义正确，就进行中间代码的翻译 四、四、 代码优化代码优化 任务：任务：对前面产生的中间代码进行加工变换，使变换后对前面产生的中间代码进行加工变换，使变换后 的代码更为高效的代码更为高效 （时间，空间上）。（时间，空间上）。原则：原则： 等价变换等价变换 主要方面：主要方面： 公共子表达式的提取，合并已知量，删除无用公共子表达式的提取，合并已知量，删

19、除无用 语句，循环优化等语句，循环优化等 五、五、 目标代码生成目标代码生成 任务：任务： 把经过优化的中间代码转换成特定机器上的低把经过优化的中间代码转换成特定机器上的低 级语言代码。级语言代码。目标代码的形式：目标代码的形式： & 绝对指令代码绝对指令代码：（可直接运行）：（可直接运行） & 汇编指令代码汇编指令代码：（要经过汇编才能运行）：（要经过汇编才能运行） & 可重新定位的指令代码可重新定位的指令代码：（要经过：（要经过linklink才能运行）才能运行） v说明：说明： 上述编译过程的阶段划分是一种典型的处理模式上述编译过程的阶段划分是一种典型的处理模式，

20、事实上并非所有的编译程序都包括这样几个阶段，事实上并非所有的编译程序都包括这样几个阶段。有些编译程序并不要中间代码，即不存在中间代。有些编译程序并不要中间代码，即不存在中间代码生成阶段；有些编译程序不进行优化，优化阶段码生成阶段；有些编译程序不进行优化，优化阶段即可省去即可省去; ;有些最简单的编译程序只有词法分析，有些最简单的编译程序只有词法分析，语法分析；语义分析和目标代码生成。语法分析；语义分析和目标代码生成。1.3 编译程序的结构编译程序的结构 编编译译程程 序序总总框框词法分析器词法分析器语法分析器语法分析器中间代码生成中间代码生成中间代码优化中间代码优化目标代码生成目标代码生成源程

21、序源程序单词符号单词符号语法单位语法单位四元式四元式四元式四元式目标程序目标程序 出出错错处处理理 表表格格管管理理一、表格与表格管理一、表格与表格管理 v与编译前三个阶段有关的表格有：与编译前三个阶段有关的表格有： &* 符号表符号表: :登记源程序中出现的每个名字登记源程序中出现的每个名字（常量名（常量名、变量名、数组名等）、变量名、数组名等）以及名字的各种属性；以及名字的各种属性； & 常数表常数表: :登记源程序中出现的各种类型的常数值；登记源程序中出现的各种类型的常数值； & 标号表标号表: :登记源程序中出现的标号的定义和引用情况登记源程序中出现的标号的定义

22、和引用情况； & 分程序入口表分程序入口表: :登记过程的层次、分程序符号表的入登记过程的层次、分程序符号表的入 口等；口等； & 中间代码表中间代码表: :记录四元式序列的表。记录四元式序列的表。v表格的作用表格的作用：登记源程序的各类信息和编译各阶段的登记源程序的各类信息和编译各阶段的进展状况。进展状况。v编译各阶段均须编译各阶段均须维持表格维持表格并进行并进行表格管理。表格管理。二、出错处理二、出错处理 v任务：任务：如果源程序有错误，编译程序应该设法发现如果源程序有错误，编译程序应该设法发现错误，并报告给用户。错误，并报告给用户。v完成：完成：由专门的出错处理程序来完成

23、。由专门的出错处理程序来完成。 v源程序中的错误通常分为：源程序中的错误通常分为： & 语法错误语法错误不符合语法（或词法）规则的错误单词不符合语法（或词法）规则的错误单词拼写错误、括号不匹配拼写错误、括号不匹配. & 语义错误语义错误不符合语义规则的错误说明错误、作用不符合语义规则的错误说明错误、作用域错误、类型不匹配域错误、类型不匹配.三、三、 遍遍( (趟，趟程趟，趟程) ) v遍遍: : 对源程序或源程序的中间结果对源程序或源程序的中间结果从头到尾扫描一从头到尾扫描一 次，次，并作有关的并作有关的加工处理，生成新的中间结果或加工处理，生成新的中间结果或 目标程序。目标程

24、序。 & 注：遍与阶段的含义毫无关系。注：遍与阶段的含义毫无关系。v根据对编译程序在完成翻译任务的过程中需要对源根据对编译程序在完成翻译任务的过程中需要对源程序或其中间等价物扫描的遍数，可以把编译程序程序或其中间等价物扫描的遍数，可以把编译程序分为分为单遍扫描单遍扫描的的编译程序编译程序(只需扫描一遍只需扫描一遍) )和和多遍扫多遍扫描描的编译程序的编译程序( (需扫描多遍需扫描多遍) )。v 前端前端主要由与源语言有关但主要由与源语言有关但与目标机器无关与目标机器无关的那些的那些部分组成，如词法分析、语法分析、语义分析与中部分组成，如词法分析、语法分析、语义分析与中间代码生成及部分代

25、码优化工作。间代码生成及部分代码优化工作。 v 后端后端主要包括编译中主要包括编译中与目标机器有关与目标机器有关的那些部分，的那些部分，如与目标机有关的代码优化和目标代码生成等。后如与目标机有关的代码优化和目标代码生成等。后端不依赖于源语言而仅依赖于中间语言。端不依赖于源语言而仅依赖于中间语言。 v 可以通过改变编译程序的后端来实现编译程序的可以通过改变编译程序的后端来实现编译程序的移移植。植。四、四、 编译的前端和后端编译的前端和后端1.4 编译程序的生成编译程序的生成v构造编译程序的语言：构造编译程序的语言：1.直接用机器语言编写的编译程序直接用机器语言编写的编译程序2.用汇编语言编写的编

26、译程序用汇编语言编写的编译程序3.用高级语言编写的编译程序用高级语言编写的编译程序 （普遍采用的方法）（普遍采用的方法）v构造编译程序的方法：构造编译程序的方法： 1.自编译：自编译：“滚雪球滚雪球” 2.移植：同种语言的编译程序在不同类型的机器之移植：同种语言的编译程序在不同类型的机器之间移植间移植v编译工具编译工具 LEX（词法分析）（词法分析） YACC（用于自动产生（用于自动产生LALR分析表）分析表）1.5 编译程序与程序设计环境编译程序与程序设计环境v编译程序编译程序 & 无疑是实现高级语言的一个最重要的工具无疑是实现高级语言的一个最重要的工具 & 支持程序设计人员进行程序设计开发通常还需要其它一支持程序设计人员进行程序设计开发通常还需要其它一 些工具：如编辑程序、连接程序、调试程序等些工具：如编辑程序、连接程序、调试程序等 & 编译程序与这些程序设计工具一起构成所谓的程序设计编译程序与这些程序设计工具一起构成所谓的程序设计 环境，如环境，如visual c，Delphi，C+Builderv程序设计环境程序设计环境 & 在一个程序设计环境中，编译程序起着中心的作用在一个程序设计环境中，编