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

编译原理

主讲：周雁Email：yanzi0910@课程的性质计算机专业的专业基础课是软件技术基础是计算机专业的学生必修的一门主干课学习编译原理的目的通过本课程主要学习编译程序构造的基本原理和技术加深对程序研发过程的理解加深对程序执行过程的认识进一步编好程序为将来从事系统软件和软件工具研究与开发打下基础提高计算机专业素养（计算机专业的“诗经”）学习任务掌握编译的理论基础和形式化系统了解编译的全过程及其具体的实现方法成绩考核方法成绩考核方法平时成绩占20％ 实践成绩占30%期末考试成绩占50％平时成绩为课堂点名+作业学习方法及要求认真听课，认真理解书中的基本概念、基本原理与基本算法弄懂书中的例题与习题在看书时或理解例题时，一定要划出相应的细节变化过程，通过画图来加深理解在理解的基础上记忆理论结合实践上课、上机纪律！编译原理课程学习方法之我见：

(1)编译原理与离散数学的关系

(2)“游戏”与“游戏规则”*例如，有一个文法:

(0)EE+E|E*E|(E)|i

请采用最右推导产生句子i+i*i:解：EE+EE+E*EE+E*iE+i*ii+i*i“变形金刚”游戏规则：1.从开始符号开始变形；2.每次按照“变形规则”将一个式子的左部变形为右部；3.每次变形串中最右边的大写字母，一直变形到目标串(不含大写字母)为止。*试采用最右推导产生句子:(1)i*(i+i)(2)i*(i+i*i)C语言的复习：

编写程序要求：让用户输入一个字符，然后判断(如果用户输入多个字符，只判断第一个)：1.若是字母，在屏幕上输出该字母ASCⅡ值；2.若是数字，在屏幕上输出该数字的二进制值；3.若是＋－*/，在屏幕上输出“输入为算符”；4.若是其它字符，在屏幕上输出“非法输入！”。第1章引论内容简介程序的翻译编译程序的工作过程编译程序的结构编译程序的组织方式编译程序的构造第1章引论教学要求掌握：编译的概念，编译的过程理解：编译的各个阶段了解：编译的结构和组合1.0程序设计语言程序设计语言

在计算机上如何执行一个高级语言程序？把高级语言程序翻译成机器语言程序运行所得的机器语言程序求得计算结果机器语言001110010010汇编语言ADD高级语言

beginx:=9+2end

各种程序设计语言都有自己的语法和语义体系，其编译程序根据这种语言的语法和语义将其翻译成机器能够接受的机器语言。程序设计语言是按一定规则排列的符号集合，而编译程序就是把这些符号集合变成机器指令的转换器，编译程序又称为编译器。软件分类软件计算机系统中的程序及其文档系统软件

居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用，如编译系统和操作系统。

应用软件把软件语言编写的各种程序处理成可在计算机上执行的程序。操作系统编译系统裸机编译程序的重要性使得计算机用户不必考虑与机器有关的繁琐细节使程序员和程序设计人员独立于机器一、翻译程序的定义

程序的翻译通常有两种方式：1.编译2.解释翻译：是指能将用甲语言（源语言）编写的程序，在不改变语义的条件下转换成用乙语言（目标语言）书写的程序。高级语言程序翻译机器语言程序1.1什么是编译程序(compiler)二、什么是编译程序(compiler)编译程序

是一个语言翻译程序,是将用高级语言书写的源程序翻译成等价的低级语言的目标程序。C、PASCLE、JAVA等机器语言、汇编语言编译程序的功能一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)编写的程序翻译成另一种语言(称作目标语言)的等价的程序.世界上第一个编译程序——FORTRAN编译程序是20世纪50年代中期研制成功。高级语言书写的程序编译程序低级语言程序1.编译方式是一种分阶段进行的方式。两个阶段的转换：编译阶段

运行阶段

三、编译方式源程序编译程序目标程序编译时初始数据计算结果运行时目标代码运行子程序三个阶段的转换：编译阶段汇编阶段运行阶段

源程序汇编语言编译时编译程序汇编程序目标代码汇编时初始数据计算结果运行时目标代码运行字程序2.编译方式的特点

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

源程序解释执行的历程

在解释方式下，并不生成目标代码，而是直接执行源程序本身。这是编译方式与解释方式的根本区别。

•先看自然语言的翻译1.识别出句子中的一个个单字2.分析句子的语法结构3.初步翻译句子的含意4.译文修饰5.写出最后译文1.2编译过程概述

•编译的五个阶段1.词法分析2.语法分析3.语义分析中间代码生成4.优化5.目标代码生成1.2编译过程概述

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

一、词法分析

voidjisuan(){inty,c,b;floatx,a,b;x=a+b-50;y=c+(d+x)+b;}识别右边程序中的单词基本字：标识符：整常数：运算符：界限符：任务：输入源程序，对构成源程序的字符串进行扫描和分析，识别出一个个的单词。单词：

是高级语言中有实在意义的最小语法单位，它由字符构成。void、int、floata、b、c、d、x、y、

jisuan50＋、—、=（），{}；一、词法分析

转换：对基本字、运算符、界限符的转换；标识符的转换；常数的转换；转换完成后的格式：（单词种别单词值）

词法分析依照词法规则，识别出正确地单词，转换成统一规格，备用。描述词法规则：有效工具是正规式和有限自动机二、语法分析

语法规则：语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。

任务：在词法分析的基础上，根据语言的语法规则，把单词符号组成各类的语法单位：短语、子句、语句、过程、程序。语法规则的表示：（Backus范式）

BNF:A::=B|C

读做“A定义为B或C”语法分析方法：推导和归纳。三、语义分析与中间代码产生

中间代码的形式：

四元式、三元式、逆波兰式任务：对语法分析识别出的各类语法范畴，分析其含义，进行和初步翻译，产生介于源代码和目标代码之间的一种代码。分为两个阶段：

&对每种语法范畴进行静态语义检查

&若语义正确，就进行中间代码的翻译四、代码优化任务：对前面产生的中间代码进行加工变换，使变换后的代码更为高效（时间，空间上）。原则：等价变换

主要方面：

公共子表达式的提取，合并已知量，删除无用语句，循环优化等五、目标代码生成

任务：把经过优化的中间代码转换成特定机器上的低级语言代码。目标代码的形式：

&绝对指令代码：（可直接运行）

&

汇编指令代码：（要经过汇编才能运行）

&可重新定位的指令代码：（要经过link才能运行）

说明：上述编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都包括这样几个阶段。有些编译程序并不要中间代码，即不存在中间代码生成阶段；有些编译程序不进行优化，优化阶段即可省去;有些最简单的编译程序只有词法分析，语法分析；语义分析和目标代码生成。1.3编译程序的结构编译程序总框词法分析器语法分析器中间代码生成中间代码优化目标代码生成源程序单词符号语法单位四元式四元式目标程序

出错处理

表格管理一、表格与表格管理

与编译前三个阶段有关的表格有：

&***符号表:登记源程序中出现的每个名字（常量名、变量名、数组名等）以及名字的各种属性；

&常数表:登记源程序中出现的各种类型的常数值；

&标号表:登记源程序中出现的标号的定义和引用情况；

&分程序入口表:登记过程的层次、分程序符号表的入口等；

&中间代码表:记录四元式序列的表。表格的作用：登记源程序的各类信息和编译各阶段的进展状况。编译各阶段均须维持表格并进行表格管理。二、出错处理

任务：如果源程序有错误，编译程序应该设法发现错误，并报告给用户。完成：由专门的出错处理程序来完成。源程序中的错误通常分为：

&语法错误不符合语法（或词法）规则的错误单词拼写错误、括号不匹配...

&

语义错误不符合语义规则的错误说明错误、作用域错误、类型不匹配...三、遍(趟，趟程)

遍:对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

&注：遍与阶段的含义毫无关系。根据对编译程序在完成翻译任务的过程中需要对源程序或其中间等价物扫描的遍数，可以把编译程序分为单遍扫描的编译程序(只需扫描一遍)和多遍扫描的编译程序(需扫描多遍)。

前端主要由与源语言有关但与目标机器无关的那些部分组成，如词法分析、语法分析、语义分析与中间代码生成及部分代码优化工作。

后端主要包括编译中与目标机器有关的那些部分，如与目标机有关的代码优化和目标代码生成等。后端不依赖于源语言而仅依赖于中间语言。

可以通过改变编译程序的后端来实现编译程序的移植。四、编译的前端和后端1.4编译程序的生成构造编译程序的语言： 1.直接用机器语言编写的编译程序 2.用汇编语言编写的编译程序 3.用高级语言编写的编译程序（普遍采用的方法）构造编译程序的方法：1.自编译：“滚雪球”2.移植：同种语言的编译程序在不同类型的机器之间移植编译工具

LEX（词法分析）YACC（用于自动产生LALR分析表）1.5编译程序与程序设计环境编译程序

&

无疑是实现高级语言的一个最重要的工具

&

支持程序设计人员进行程序设计开发通常还需要其它一些工具：如编辑程序、连接程序、调试程序等

&

编译程序与这些程序设计工具