第一章编译程序概述

主讲：王莲芝计算机编译原理（CompilerDesign）课程简介课程内容介绍编译器构造的一般原理和基本实现方法介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法等强调形式化描述技术强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于某种源语言或目标机器课程简介学习的意义对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用。从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。在软件逆向工程、程序理解和软件安全等方面有着广泛的应用。逆向工程（reverseengineering）是根据已有的东西和结果，通过分析来推导出具体的实现方法。比如你看到别人写的某个exe程序能够做出某种漂亮的动画效果，通过反汇编、反编译和动态跟踪等方法，分析出其动画效果的实现过程；不仅仅是反编译，而且还要推倒出设计.课程简介课程要求目标：师生共同努力，达到效果课程进展较快，配合做作业加深理解课后作业占成绩30%，要求独立完成上机实验不要轻视，实验作业占成绩20%

阅读PL/0编译器，会有很大收获考试开卷但不会轻松，占成绩50%

考核方法：期末笔试50分实验、作业50分学时:48(40课，单双周/8实验)教材：主要教材：《编译原理》第二版作者：吕映芝张素琴蒋维杜清华大学出版社出版参考教材1：《编译原理和技术》作者：陈意云中国科技大学出版社参考教材2：《编译程序的设计与实现》作者：刘磊等高等教育出版社课程内容介绍第一、二章编译程序概述、PL/0介绍第三章文法和语言

第四章词法分析第五章自顶向下语法分析第六章自顶向上优先分析法第七章LR分析法第八章语法制导翻译和中间代码生成第九章符号表与错误处理第十章代码生成、存储与优化

高级语言机器语言编译处理程序语言处理过程：使用计算机处理数据—涉及到使用的语言第1章 编译程序概述1.1编译程序及其功能↓1.2编译过程概述↓1.3编译阶段的组合↓1.4编译技术和软件工具↓1.5编译程序的开发↓1.1编译程序及其功能编译程序是一种语言翻译程序，它把高级语言书写的程序翻译成低级语言的等价程序。

编译程序定义：编译程序高级语言程序低级语言程序源程序目标程序翻译功能关于语言的分类机器语言低级语言高级语言机器语言特点：由0、1组成的二进制的编码，用起来困难由于计算机硬件的器件特性，决定了计算机本身只能直接接受由0和1编码的二进制指令和数据，这种二进制形式的指令集合称为该计算机的机器语言，它是计算机惟一能够直接识别并接受的语言。低级语言特点：与机器硬件联系密切，用起来繁琐用机器语言编写程序既不方便也容易出错，编写的程序也难以调试、阅读和交流。为此，出现了用助记符代替机器语言二进制编码的语言，这就是汇编语言。汇编语言是机器语言的符号化形式，虽然比机器语言在阅读和理解上直观，但计算机并不能直接识别这种符号化语言，须用汇编语言编写的程序翻译成机器语言后执行。由于汇编语言和机器语言一样都是面向机器的，所以它们都称之为低级语言。例:从AL寄存器输出一个字节到端口5：

OUT5,AL高级(编程)语言特点：独立于机器，用户不必考虑与机器硬件有关的细节，也称编程语言。功能更强、更抽象的面向用户、面向各种应用的语言称为高级语言。它从具体机器中抽象出来，摆脱了依赖具体机器的特性，更加接近人类自然语言(形式语言)。用高级语言编制的程序几乎能够在不改动的情况下在不同种类的计算机上运行且不易出错,但却使高级语言程序翻译的难度大大增加。高级语言列举VC++VBJAVAFORTRANPASCAL．．．．．．

程序设计语言的类型：

1.命令式语言。这种语言的语义基础是模拟“数据存储/数据操作”的图灵机可计算模型，十分符合现代计算机体系结构的自然实现方式。其中产生操作的主要途径是依赖语句或命令产生的副作用。现代流行的大多数语言都是这一类型，比如Fortran、Pascal、Cobol、C、C++、Basic、Ada、Java、C#

等，各种脚本语言也被看作是此种类型。

2.函数式语言。这种语言的语义基础是基于数学函数概念的值映射的λ算子可计算模型。这种语言非常适合于进行人工智能等工作的计算。典型的函数式语言如Lisp、Haskell、ML、Scheme

等。

3.逻辑式语言。这种语言的语义基础是基于一组已知规则的形式逻辑系统。这种语言主要用在专家系统的实现中。最著名的逻辑式语言是Prolog。

4.面向对象语言。现代语言中的大多数都提供面向对象的支持，但有些语言是直接建立在面向对象基本模型上的，语言的语法形式的语义就是基本对象操作。主要的纯面向对象语言是Smalltalk。

虽然各种语言属于不同的类型，但它们各自都不同程度地对其他类型的运算模式有所支持。Ada语言：Ada是一种表现能力很强的通用程序设计语言，大大改善软件系统的清晰性，可靠性，有效性，可维护性。Ada语言的重要特征就是其嵌入式风格，模块化设计，编译检查，平行处理，异常处理及泛型编程。Lisp：全名LIStProcessor，即表处理语言，由约翰·麦卡锡在1960年左右创造的一种基于λ演算的函数式编程语言。Haskell：是一种标准化的、通用纯函数式编程语言，有非限定性语义和强静态类型。ML：是一个通用的函数式编程语言，它是由爱丁堡大学的RobinMilner及他人在二十世纪七十年代晚期开发的。作为元语言的ML是为了帮助在LCF定理证明机中寻找证明策略而构想出来的。Scheme：语言是Lisp的一个现代变种、方言，诞生于1975年，由MIT的GeraldJ.SussmanandGuyL.SteeleJr.完成。与其他lisp不同的是，scheme是可以编译成机器码的。Prolog（ProgramminginLogic的缩写）是一种逻辑编程语言。它建立在逻辑学的理论基础之上，最初被运用于自然语言等研究领域。现已广泛的应用在人工智能的研究中，可以用来建造专家系统、自然语言理解、智能知识库等。Smalltalk被公认为历史上第二个面向对象的程序设计语言和第一个真正的集成开发环境

(IDE)。Ada语言程序设计环境APSE的基本构成：

第一层是核心APSE(KAPSE)。它包括环境数据库、通信及运行时支撑功能等。最内层(第0层)是宿主计算机系统，它包括硬件宿主操作系统和其它支持软件以Ada语言为例:第二层，最小MAPSE。它包括Ada程序开发及维护的基本工具，这些工具包括编译程序、编辑程序、连接程序、调试程序、命令解释程序、配置管理程序、美化打印程序、静态分析工具、动态分析上具等等。第三层，APSE。在MAPSE外面再加上更广泛的工具就构成了完整的APSE。

对这一层没有精确规定工具的类型，它通常可以包括，面向应用的工具和支持特定程序设计方法的工具等：可以是支持需求分析、设计、实现、维护等软件开发全生命周期的工具。世界编程语言排行榜

翻译程序的工作方式:编译方式:

将源程序翻译成目标程序后再执行该目标程序解释方式:

逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。典型的解释型高级语言是BASIC语言高级语言程序的执行分为两个阶段：即编译阶段和运行阶段。编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。编译方式：如果编译生成的目标程序是汇编语言形式，那么在编译与运行阶段之间还要添加一个汇编阶段，它将编译生成的汇编语言目标程序再经过汇编程序变换成机器语言目标程序，如图：解释程序也是一种翻译程序，它将源程序作为输入，一条语句一条语句地读入并解释执行，如图：解释方式：一个高级语言程序的执行步骤：例如一个PASCAL语言源程序在PDP-Ⅱ机上执行的步骤：磁盘文件名为A.PAS源程序1）编译.RPASCAL（启动PASCAL语言的编译程序）*A=A（PASCAL编译程序要求用户回答要编译 的文件名）

—

产生A.MAC的汇编语言文件2）汇编.MACA（调用汇编程序将汇编语言形式的目标 代码转换成机器能够识别的机器代码）

—产生A.OBJ文件3）连接.LINKA，PASCAL（把A.OBJ文件与 PASCAL.OBJ连接进行装配）4）运行.RUNA（运行A.SAV）因此,一个高级语言程序执行的步骤主要如下:1.对源程序进行编译2.执行目标程序：由于目标程序的语言可是机器语言或汇编语言,则执行目标程序的步骤有所区别。汇编语言形式的目标程序汇编程序机器语言形式的目标程序①若目标程序是汇编语言，则对目标程序经过汇编程序进行汇编，再经过连接程序进行连接后才能运行。如下图：②当目标程序是机器语言时，不必经过上图步骤。连接程序可运行的目标程序机器语言形式的目标程序③对中间语言形式（栈式计算机的汇编语言）的目标程序需借助解释程序才能执行执行可运行的目标程序输入数据输出结果中间语言形式的目标程序解释程序输入数据输出结果注:虚线框表示广义存储器

编译程序完成从源程序到目标程序的翻译工作。它是一个分阶段进行的过程，每个阶段完成的使命是将源程序由一种表示形式转换成另一种表示形式。一种典型的划分方法是将编译过程划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成六个阶段和表格管理、出错处理两个重要工作。1.2编译过程概述编译过程各阶段源程序目标程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成表格管理出错处理分析部分综合部分人受教育的过程儿童人才幼儿园小学初中高中大学工作单位成绩、档案法律、守则类似于：1.词法分析词法分析是编译过程的第一阶段实际完成两个任务：从左至右读入源程序，对构成源程序的字符流进行扫描和分解；识别出一个个的单词符号：如基本字、标识符、常数、算符、界符ifi=5thenx=y词法分析器（3，‘if’）（1，指向I的符号表入口）（4，‘=’）（2，‘5’）（3，‘then’）（1，指向x的符号表入口）（4，‘=’）（1，指向y的符号表入口）1）结果用二元式表示2）二元式形式是：（单词种别，单词自身的值）3）定义单词种别为： 1：标识符 2：常数 3：保留字 4：运算符 5：界符词法分析器判断单词的依据依据单词的文法例： 定义标识符的文法为： 字母开头的字母和数字串 也即：1）任何字母是标识符 2）任何字母+字符串是标识符标识符单词表达式语句语言标识符的文法单词的文法表达式的文法语句的文法语言的文法形式文法文法规律2.语法分析作用：识别由词法分析给出的单词符号组成的短语是否是给定文法的语法单位包括：短语、表达式、语句、程序、程序段依据：短语的文法规则性质：是对形式的分析例：若定义：表达式的文法 1）任何标识符是表达式； 2）任何常数（整常数，实常数）是表达式； 3）若有表达式1和表达式2，那么： 表达式1+表达式2 表达式1*表达式2都是表达式。（递归定义）

定义：语句的文法 1）标识符=表达式是语句（赋值语句） 2）while表达式do语句

if表达式then语句else语句 都是语句

3.语义分析作用：收集类型信息，审查源程序有没 有语义错误，分析其含义，在语 法分析树中插入语义处理节点性质：是对内容的分析分类：分为静态语义分析和动态语义分 析静态语义分析一系列限定规则，确定哪些合乎语法的程序是合适的，如：变量是否定义，类型是否匹配，运算的合法性等。如果语义正确，进行中间代码的翻译动态语义分析确定程序要做什么、要计算什么（即确定程序的意思）动态语义也称运行语义或执行语义4.中间代码生成中间代码：是源程序经编译程序转变成 的一种结构简单、含义明确 独立于具体硬件的记号系统设计原则：容易生成、容易被翻译成目 标代码常用形式：四元式—（运算符，运算对 象1，运算对象2，结果）5.代码优化作用：对前阶段产生的中间代码进行加 工变换或改造目的：使生成的代码更高效（省时、省 空间）优化的主要方面：公共子表达式的提取、循环优化、算符规约等原则：等价变换

6.目标代码生成作用：把优化处理后的中间代码转变成特定机器上的绝对指令代码或汇编指令代码该阶段的工作涉及硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配及寄存器的调度等（依赖于硬件系统结构和机器指令含义）需要预处理的源程序预处理程序源程序编译程序目标汇编程序汇编程序可再装配的机器代码装配/连接-编辑程序绝对机器代码高级语言程序的处理过程存放在不同文件里的几个高级语言程序模块完成文件合并、宏展开等任务高级语言程序完成将高级语言翻译成低级语言的任务生成的低级语言程序将低级语言程序翻译成机器代码编译预处理编译预处理是C/C++的重要功能。在编译程序开始编译之前，先由预处理程序对源程序中的预处理命令进行处理，然后才进行通常的编译。预处理命令是源程序文件中以#开始的命令，常用的有文件包含和宏定义命令。在C/C++中，扩展名为.h的文件称为头文件，它们包含了大量的符号常量定义和函数说明等。编程时若需要使用这些文件，就用文件包含命令把它们插入到源程序文件中。文件包含命令是以“#include”开始的预处理命令。其主要功能是将指定文件的内容嵌入到文件包含命令所在的地方，取代该命令，从而把指定的文件和当前的源程序文件连成一个源文件。文件包含宏定义在C/C++中，允许用户用标识符来表示一个字符串，这个标识符称为宏。若一个宏简单地表示一个常量，则该宏称为符号常数。在编译预处理时，程序中所有出现的宏都用它所表示的字符串来替换。定义符号常量的形式为：#include标识符常量1.3编译阶段的组合出错处理程序源程序目标程序词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序表格管理程序编译阶段的组合分为：前端后端前端的划分通常，前端由主要依赖源语言而与目标机无关的一些阶段组成，包括：词法分析、语法分析、语义分析、中间代码生成、某些优化工作及与上述各阶段相关的出错处理和符号表管理工作后端的划分后端由依赖于目标机而不依赖于源语言、只与中间代码有关的阶段，即目标代码生成及其相关的出错处理和符号表操作组成。后端不依赖于源语言而仅仅依赖中间语言。前端与后端的组合某一语言编译程序的前端+与之相应的不同的后端→同一个源语言在不同的机器上的编译程序不同语言编译程序的前端+共同的后端→不同语言在同一机器上的编译程序

编译程序的遍遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程，即每一遍扫视可完成一个或多个阶段的任务。每遍的工作由外存上获得的前一遍的中间结果开始双框表示子程序或过程一遍扫描示意图：以语法分析程序为核心多遍扫描示意图：多遍编译与一遍编译的比较多遍编译：占用内存少、消耗时间多、 速度慢、编译程序的逻辑结 构清晰一遍编译：占用内存多、省时、速度快语言的结构化编辑器语言程序的调试工具↓语言程序的测试工具↓高级语言之间的转换工具↓↓1.4编译技术和软件工具语言的结构化编辑器作用：引导用户在语言的语法制导下编制程序，能自动地提供关键字和与其匹配的关键字，以减少语法上的错误语言程序的调试工具作用：发现并帮助编程人员解决算法或程序没能反应算法的功能等错误语言程序的测试工具静态分析器：对源程序进行语法分析，检查变量定值与引用的关系及语法分析发现不了的错误动态分析器：在源程序的适当位置插入某些信息，将运行结果与期望的结果进行比较分析高级语言之间的转换工具解决将一种高级语言转换成另一种高级语言或将汇编语言转换成高级语言的问题，使原语言可在新机器上使用，减少开发成本分析部分：有赋值语句：position：=initial+rate*60词法分析得到下列词汇：1）标识符position2）赋值号：=3）标识符initial4）加号+5）标识符rate6）乘号*7）数60编译程序各阶段例：依次读源程序的每个字符，识别出词汇。词法分析：符号表

positioninitialrate.........123语法分析：按照语法规则识别源程序中的词汇序列所构成的句子，是一种层次结构的分析。

initial标识符数

rate60

赋值语句标识符：=

表达式position表达式

+

表达式标识符表达式*表达式赋值语句的语法树任何一个标识符都是表达式；任何一个数都是表达式；如果e1和e2都是表达式，那么

e1+e2e1*e2

(e1)也都是表达式(递归定义)position：=initial+rate*60：=

：=

position+position+

initial*initial*

rate60rate

inttoreal

60

在语法树中插入表示类型转换的结点语义分析：分析部分的各阶段综合部分：中间代码生成：用三地址代码表示赋值语句可翻译成如下指令序列：（四元式序列）temp1：=intooreal（60）temp2：=id3*temp1temp3：=id2+temp2id1：=temp3

temp1：=id3*60.0id1：=id2+temp1代码优化：“三地址”指的就是两个运算分量（操作数1、操作数2）及目标操作数三个对象的地址。例如，（ADD5,A,B）对上述指令的中间代码翻译成汇编代码，使用两个寄存器R1和R2，代码如下：MOVFID3，R2 MULF#60.0，R2 MOVFID2，R1 ADDFR2，R1 MOVFR1，ID1F表示执行浮点数操作综合部分的各阶段编译的预处理和后续处理1.5编译程序的开发由于计算机语言功能的完善、硬件结构的发展、环境界面的友好要求等都对编译程序提出更多、更高的要求，因而构造一个编译系统并非易事。虽然编译理论和编译技术的发展使编译程序的生产周期不断缩短，但是要研制完成一个编译程序仍需相当长的时间，工作也相当艰巨。因此，如何高效、高质量地生成一个编译程序一直是计算机系统设计人员追求的目标。

开发要求：编译程序的任务是把源程序翻译成某台计算机上的目标程序，因此，开发人员首先要熟悉这种源程序语言，对源程序语言的语法和语义要有准确无误的理解。

其次必须对目标机器的硬件和指令系统有深刻的了解。例如，产生两个数相加的指令在8086/8088汇编中假定用下面两种指令实现：

ADDAX，06或ADDBX，06粗略看来，这两条加法指令除了寄存器不同外没有本质上的差别，其实不然。由于AX是累加器，因此，从机器指令的代码长度来说，第一条指令比第二条指令节省一个字节。从PC机硬件结构来看，AX本身就是累加器且相加的结果也在累加器中，这就节省了传送的时间；而第二条指令则先要将BX中的值送到累加器中，相加后又要由累加器取出结果再送回寄存器BX中。显然，第二条指令要比第一条指令费时，因此，在可能的情况下，应尽量生成像第一条指令这样的目标代码。此外，开发人员还需确定编译程序的开发方案及方法，这是编译开发过程中最关键的一步，其作用是使编译程序具有易读性和易改性，以便将来对编译程序的功能进行更新和扩充。选择合适的语言编写编译程序也是非常重要的，语言选择不当会使开发出来的编译程序可靠性较差，难以维护且质量也无法保证。目前大部分编译程序都是用PASCAL、C和ADA这类高级语言编写的，不仅减少了开发的工作量，也缩短了开发周期。最后，开发人员对目标机要有深入的研究，这样才能充分利用目标机的硬件资源和特点，产生质量较高的目标程序。编译器的编写及工具：把高级语言翻译成低级语言的程序被称为编译器(或解释器)，把汇编语言翻译成机器代码的程序被称为汇编器。编译器本身也是一个程序，那么用什么编写编译器呢?早期人们用汇编语言编写编译器。虽然人工可以编写出效率很高的程序，但由于编译器本身是一个十分复杂的系统(如早期的FORTRAN用了18人年才完成)，而用汇编语言编写编译器的效率很低，往往实现起来困难很大。因此，除了特别需要，人们早已不用汇编语言编写完整的编译器。用单纯程序设计的方法来进行编译这样的庞大工程也显得很不够。为此，需要一些专门的编译器编写工具来支持编译器某些部分的自动生成。比较成熟和通用的工具有：词法分析器生成器和语法分析器生成器，如LEX和YACC。另外，还有一些工具，如语法制导翻译工具(用于语义分析)、自动的代码生成器(用于中间代码生成和目标代码生成)和数据流工具(用于优化)等。这些工具的共同特点是，仅需要对语言相应部分的特征进行描述，而把生成算法的过程隐蔽起来，同时所生成的部分可以很容易地并入到编译器的其它部分中。因此，这些工具往往与某程序设计语言联系在一起，如与LEX和YACC联系的程序设计语言是C。

1．自编译

用某种高级语言书写自己的编译程序称为自编译。例如，假定A机器上已有一个PASCAL语言可以运行，则可以用PASCAL语言编写出一个功能更强的PASCAL语言编译程序，然后借助于原有的PASCAL编译程序对新编写的PASCAL编译程序进行编译，从而在编译后即得到一个能在A机器上运行的功能更