编译原理第1讲引论

第一讲引论

♦课程信息

♦编译程序概述

♦高级语言的语法描述

§1.课程信息

一、课程名称：编译原理

基本内容是介绍编译程序构造的基本原理、

方法和技术，包括词法分析、语法分析、

语义分析与中间代码产生、代码优化及目

标代码产生等。简言之，就是介绍如何将

源程序翻译成目标代码程序。

CompilerPrinciples3

二、课程性质：专业基础课，必修

。编译程序（器）出现于上世纪50年代后期

（第一个高级语言1958年）

❖60年代〜70年代是研究高峰期

60年代中期开始在高校中开设课程

。80年代开始作为计算机科学与技术专业的

必修基础课程

CompilerPrinciples4

三、课程特点：

充分体现了计算学科中抽象、理论和设计三个学科

形态

。该课程涉及多门课程的内容综合运用，涉及面广，内

容庞杂，学习艰难

9程序设计语言、计算机体系结构、语言理论及算法等；

9离散数学、数据结构'

。该课程涉及的原理、方法和技术具有十分普遍的意

义

小每一个计算机科学与技术工作者的职业生涯中反复用到，

“享用一辈子”

《这儿接受的训练很难在其他地方获得：

如：抽象与形式化方法、局部与全局优化方法、构造技术、

证明方法等

CompilerPrinciples5

四、学习该课程的意义

❖编译程序是计算机系统不可缺少的重要组成

部分

力对程序设计语言的设计与实现能有更深刻的理

解

9对程序设计语言有关理论有所了解

。从宏观上把握程序设计语言—掌握了编译原

理后，就不能再说：“某语言未学过，所以不

会”

i有助于快速理解、定位和解决程序调试与运行

中出现的问题

CompilerPrinciples6

。编译方法与技术有着广泛应用

《安全技术、程序理解、软件逆向工程、应用软件与软

件工具开发、软件测试与验证等

。编译课程蕴含着计算学科中解决问题的思路、抽

象和方法，这些与高等数学一样，使你“享用一

辈子”

课程所涉及的内容至今非常活跃

9自然语言的翻译

9软件移植

9网络安全」

9形式化方法

力形式语义学等

CompilerPrinciples7

鉴于以上所述，作为计算机科

学与技术专业的学生必须学习和

掌握编译原理这门课程，当然由

于其综合性、处理问题的复杂性

等，学习起来有一定难度，这就

需要艰苦奋斗的精神和良好的学

习方法I

CompilerPrinciples8

五、学习方法

*编译程序的构造是一个庞大而复杂的系统工

程，无论是概念还是理论、方法，对初学者

来说许多都是新的，学习起来会感到困难大

一些，这一点必须有充分认识，为此建议学

习方法上注意以下几点：

CompilerPrinciples9

1.课前预习，课堂认真听讲，课后复习加深理

解，特别要经常有意识地将前后内容联系起

来融会贯通。因为编译程序是一个庞大的程

序系统，讲解过程必须“分而治之”，这也

是人们处理复杂问题的基本方法，这就要求

大家在学习过程中，始终以处理过程为主线,

把前后联系起来考虑。

CompilerPrinciples10

2.理论联系实际——亲自动手，构造一个

演示性编译程序，至少要完成扫描器和

语法分析器，以及语法制导翻译产生中

间代码

3,认真完成作业，进一步巩固并加深理解

所学知识

4.特别要下功夫认真学习如何从实际问题

进行抽象并形式化，最终建立实际问题

的模型（上升为理性认识），并借助模

型进一步设计实现，这将对你的能力提

高大有益处

CompilerPrinciples11

六、教材选择：

《程序设计语言编译原理》（第3版）

国防工业出版社陈火旺等

1.内容详实丰富，理论与技术相结合

2.新版充分考虑了新的研究成果——属

性文法、LR分析法、全局优化等

3.大多数院校一直采用，硕士入学考试

参考书

4,较为全面介绍了编译程序构造的基本

原理、方法与技术

CompilerPrinciples12

七、考试

平时成绩：30%

期终考试成绩：70%

八、参考书目

1.《编译原理》陈意云张昱高教出版社

2.《编译原理》李建中姜守旭译

A.V.Aho,RavSethi,J.D.Ullman著

机械工业出版社

3.《编译原理及实践》廿冯博琴冯岚等译

KennethC.Louden著）

机械工业出版社

CompilerPrinciples13

§2.编译程序概述

，翻译程序（Translator）

能够把一种语言程序（称为源语言

程序）转换成逻辑上等价的另一种

语言程序（称为目标语言程序）的

程序

Compilerprinciples14

❖任何非机器语言程序都需要翻译程序

。翻译程序的工作就是进行等价变换（映射）

两个程序逻辑上等价是指对相同输入得到

相同的输出

CompilerPrinciples15

1.汇编程序(Assembler)

把汇编语言程序转变为机器语言程序的翻译程序

2.解释程序(Interpreter)

把源程序作为输入接收，边解释边执行的翻译程序

r源程序解释＞结果

数据程序

CompilerPrinciples16

3.编译程序

将高级语言程序转变为低级语言程序的翻译程序

源程序

CompilerPrinciples17

。编译程序又可根据用途和侧重点的不同，

进一步分类为：

①诊断编译程序(DiagnosticCompiler)

专门用于帮助程序开发和调试的编译程序

②优化编译程序(OptimizingCompiler)

着重于提高目标代码效率的编译程序

③交叉编译程序(CrossCompiler)

能够产生不同于其宿主机机器代码的编译程序

④可变目标编译程序(Retargetablecompiler)

无须重写与机器无关部分就能改变目标机的

编译程序

CompilerPrinciples18

二、与编译程序相关的程序

本讲义只介绍编译程序（器）构造的基本原

理、方法与技术，但在一个完整的语言开发

（或称程序设计）环境中，除了编译器这一I

主要工具外，还需要其他一些工具，如编辑

器、连接器、装入程序等。现代计算机系统

常将这些相互独立的程序设计工具集成起来,

构成一个集成化的程序开发环境，以提高程

序设计效率和程序的质量。如TurboC、

VisualC++等语言环境都是集成化的程序设

计环境。而Ada语言的集成环境是这方面的

J

如Ada语言的集成环境是一个分层的程序开发环境

这儿要强调的是：尽

管本课程只介绍编译

的基本理论、方法和

技术，但这些基本理

论、方法与技术对其

他工具的构造同样起

作用！

CompilerPrinciples21

1编辑器（Editor）

.完成源程序输入、编辑并产生标准文件

（如ASCII文件）的程序。

近来已与编译器和其他程序捆绑进一个交

互开发环境——IDE中

尽管这样的编辑器仍生成标准文件，但会

转向正被讨论的程序设计语言的格式或结

构（称为基于结构的），且已包含了编译

器的某些操作；因此在程序编写时而不是

编译时就可得知错误，甚至也可调用编译

器

CompilerPrinciples22

2,预处理程序(Preprocessor)

在真正翻译开始之前产生编译程序的输入

的程序

。处理宏及注释：宏是被经常使用的较长结

构的缩写

处理文件包含：把头文件包含到程序正文

中(如C的文件包含includev..・.h>)

。“理解”预处理器：把现代控制流和数据

结构机制添加到比较老式的语言中

。语言扩充：通过大量的内部宏定义来增强

语言的能力，如Equel语言是一种嵌套在C

,樟司中的数据库查询语言

CompilerPrmciples二2323

K连接程序(Linker)——又称为连接编辑器。

将分别在不同的目标文件中编译(或汇编)

的代码、所用标准库函数的代码以及操作

系统提供的资源(如存储分配程序及输入/

输出设备)收集到一个可直接执行的文件

中的程序

4.装配程序(Loader)

完成程序的装入和连接编辑两项功能。

装入过程包括读入可重定位机器代码、修

改可重定位地址、并将修改后的指令和数

据放到内存的适当位置。

装入程序使得可执行代码更加灵活

CompilerPrinciples24

5,调试程序（Debugger）

可在被编译了的程序中判定执行错误的程

序

❖它经常与编译程序一起放在IDE中

。运行一个带有调试程序的程序与直接执行

不同，这是因为调试程序保存着所有的或

大多数源代码信息，它可以在预先指定的

位置（断点Breakpoint）暂停执行，并提供

有关信息（已调用的函数、变量名的当前

值等）

CompilerPrinciples25

6.其他有关的还有

。描述器(Profiler)——执行中搜集目标程序行

为统计的程序

项目管理程序(ProjectManager)-----如

Unix系统中的SCCS(源代码控制系统)和

RCS(修正控制系统)和汇编程序等

综上所述可给出一个“语言处理系统”的图示:

CompilerPrinciples26

源程序梗概

_______1_______

预处理器

丁

源程序

编全器

丁

目标汇编程序

—

汇编器

可重定位机器代码

____________+

装载器/连接编辑器;一库、可重定位目标程序

可执行机器代码

我们这个课只介绍编译程序这一部分

CompilerPrinciples27

三、编译过程与编译程序结构

1.编译过程：

输入---------编译程序--------输出

（高级语言源程序）（低级语言目标程序）

编译程序工作过程如下：

•识别出一个个的单词

•分析句子的语法结构

•分析句子的语义并进行初步翻译.

•对初步翻译进行优化

•整理出目标程序

对以上过程进一步整理可得如下编译程序结构总框:

CompilerPrinciples

3.五个阶段简介

・第一阶段：词法分析——依据语言构词规

贝I」，识别出一个个单词（符号）

◊单词种类

•基本字：for,if,while等、

•算符：+,一，X,/等、有穷性!

•界符：，；O等J

•标识符：a123,pi等

无穷性

•常数：9,36,486E6等

CompilerPrinciples30

◊词法分析工作由词法分析器（或称扫描

器）完成。

◊扫描器输出为等长度的单词符号（二元

式）流。

◊例：

(06,'Position')。l,-X06,'initial'X12,-X06,'rate')(13,—)(07,'60的二进制')

CompilerPrinciples31

・第二阶段：语法分◊如：Position=initial+rate*60是——

析——依据语言的个“赋值表达式”（C语言中）

语法规则，把扫描

器提供的单词符号

串分解成各种语法

单位（范畴），如

“短语”、“子Position

句”、“句子”乃

至“程序”。同时

进行语法检查，以

确定输入串是否正

确，该工作是由语initial标示符常数

法分析器完成的。

rate60

CompilerPrinciples32

•第三阶段：语义分析与中间代码产生——针对

各类不同的语法范畴，按语言的语义规则进行

语义分析和初步翻译工作，产生某种中间语言

形式的中间代码（即一种结构简单，含义明确

的记号系统）

该阶段工作通常包括两个方面的工作：

◊对每种语法范畴进行静态语义检查，包括：

•变量是否定义过.

•类型是否正确1

•是否用了。作除数等

CompilerPrinciples33

J•将语法范畴翻译成某种形式的中间代码,

如四元式：

OpARG1ARG2Result

*rate60T1

+initialT1T2

■T2Position

CompilerPrinciples34

•第四阶段：优化——对前阶段产生的中间

代码进行加工变换，以期在最后阶段能产

生出高效（节省时、空）的目标代码，这

一任务是由优化器来完成的I

•根据优化的范围不同，可分为：

局部优化，循环优化和全局优化

・一个循环优化的例子：

■

循环语句为：For(k=1;k<=100;k++){M=l+10*k;N=J+10*k;}

⑴=1K(1)=IM

(2)J<10°K(9)⑵=JN

⑶*10KT1⑶=1K

(4)+IT1M(4)J<1。。K⑼

⑸*10KT2⑸+M10M

(6)+JT2N(6)+N10N

⑺+K1K⑺+K1K

(8)J(2)(8)J(4)

•优化前用了两个临时工作单元(T1,T2),优化后没有用临时单元

•优化前循环体中要做300次加、200次乘，

就施箫循环体内只做30。次加36

•第五阶段：目标代码生成——把中间代码

翻译成目标代码

•显然这阶段要依赖于硬体系统结构和指

令系统

•涉及存贮分配、寄存器调度

这一阶段工作是由代码生成器完成的

说明：

以上各阶段（或称工序）并不是截然分开

的，尤其编译程序结构十分复杂、体积相

当庞大，所以有时人们把几个阶段的工作

有机地组合在一起、穿插进行，构成遍。

Compilerprinciples37

。遍(Pass)：对源程序或源程序的中间代

码从头到尾扫描一次并做相应处理加工

•分遍的好处是结构清晰、节省内存(每

遍都从外存获取前一遍的结果作为开始,

工作结果仍记入外存，每遍几乎可使用

全部内存)

•分不分遍、如何分遍要视具体情况----

计算机内存容量、源语言的繁简、从事

编译程序设计人员的情况等

CompilerPrinciples38

如最早的基本BASIC语言采用一遍扫描的编译程序:

CompilerPrinciples39

又如PL/O编译程序的结构

PL/O源程序

格

表

错

出

理

管

理

处

序

程

程

序

目标程序

CompilerPrinciples40

再如COBOL编译程序采用了四遍扫描的编译程序:

序

程

源U

词法分析与

名等内码内

码生成器

1山I

文

配

基

外

字

对

词

名

信

矩

表

表

息

阵

表

表

CompilerPrinciples41

4.前端与后端：概念上讲，编译程序的五个阶

）段可进一步划分为前端和后端：

•前端：主要由与源语言有关而与目标机无

关的部分组成，包括词法分析、语法分析、

语义分析和中间代码产生。代码优化一般

也包含在前端。J

•后端：主要由与目标机有关的部分组成，（

包括目标代码生成和与目标机有关的优化

等。

详见下图：

CompilerPrinciples42

前端后端

中

义

词

语

语

目

目

中

目

源

析

间

据

法

分

令

标

间

标

程

分

分

中

代

和

代

代

语

语

序

析

析

代

间

码

码

码

言

言

产

码

优

优

生

主

件

化

化

成

CompilerPrinciples43

•划分前端和后端，就可以仅改写后端

而生成不同目标机上的目标程序，当然

也可考虑对不同语言仅稍加改变前端而

产生相同的中间代码，经同一后端生成

相同目标机的目标代码。就目前来说，

针对相同中间代码适应不同目标机的工

作较多，如Ada语言的APSE（Ada程序设

计环境）中使用的Diana中间代码，Java

语言定义的虚拟机代码---Bytecode中

间语言，都是定义良好的中间语言。

详见下图：

Compilerprinciples44

Java的传统环境

编译环境

Java源程序

(Java)

Java编译器

Java字节码

（本地或

网络传输）,

Java字节码

(,class)

CompilerPrinciples45

5,表格与表格管理

•表格记录源程序中的各类有用信息——名

字、函数、标号、过程、数值等

•每个阶段的工作都要与表格打交道：查、

填、改等

•表格的结构与处理方法：统一的大表与分

类的小表

•统一大表NAMEINFORMATION

名字栏为主栏（关键字栏），信息栏又分

成若干子栏——种属、类型等

CompilerPrinciples46

•分类小表：每类一张表，如:

•符号名表(SNT)X哑元实型

A数组整型...

•常数表(CT)3.1415926

48

Compilerprinciples47

•入口表(ENT)Swap二目子程序入口地址

•标号表

(LBT)L1入口地址

•基本字表DO编号(03)

(KWT)

CompilerPrinciples48

6.出错处理：

这是编译程序的又一重要组成部分，

因为编译的各个阶段都有可能发现源

程序中的错误。一旦发现这样或那样

的错误，就应把错误的性质及位置报

告给用户，并且使编译能继续下去。

Compilerprinciples49

四、编译程序的构造过程

1.需求分析，确定语言文本

（1）确定语言的种类：

◊按语言范型分类，当今大多数程序语言可分为四类:

过程式（强制式语言）：命令驱动，面向语句，如

FORTRAN>PASCAL>Ada及C等

函数式（应用式）语言：功能驱动，面向函数，如

LISP、SNOBOL及ML等

逻辑式（基于规则的）语言：依据条件进行逻辑推演,

如Prolog等

00语言：支持封装性、继承性、多态性及动态聚

束等，以对象为运行单位，如Smalltalk、Java、

C++等

CompilerPrinciples50

◊通过用户提供的应用范围，决定采用何种语

、A

H。

例如：

偏重于科学计算的则选用Fortran；

偏重于符号处理的则选用Lisp或Snobol；

偏重于事务处理的则选用Cobol或数据库管理

语言；

CompilerPrinciples51

(2)深刻理解语言的结构、语法及语义

这就是说不仅仅是用程序设计语言编几个程序的

问题，而是要在语法和语义方面下一些功夫。具

体说来有以下几个方面：

①程序语言的定义：

任何程序语言都是某个确定的字符集上的符号按

照一定规则组成的有穷序列。

这里所谓的规则是从两个方面来谈的：

­语法规则：用于形成和产生一个正确的程序的

一组规则。

•语义规则：用于定义程序意义的一组规则。

CompilerPrinciples52

例如：

从语法的角度看，标识符和名字是一个东

西，都是以字母开头的字母数字串；但从语

义的角度看，标识符是一个没有任何意义的

字符序列，而名字却有确定的意义和属性，

而且具有一定的作用域和定义域，即有局部

和全部之分。

又如：....

程序从语法角度看，是一些语法范畴构成

的如下层次结构：

CompilerPrinciples53

程序

I

分程序或子程序（过程、函数等）

PBT

语句

I

表达式

数据引用算符函数调用

而从语义的角度来说，程序是描述一定

的数据结构及其处理过程。

CompilerPrinciples54

②程序结构：

现代高级语言程序通常由若干子程序段

（过程、函数等）构成，许多语言还引入了

类、程序包等更高级的结构。

例如,Fortran、C程序是块结构的;

Pascal程序是过程嵌套的；Algol既有分程序

嵌套，又有过程嵌套；Java与C++是面向对象

的，它们很重要的方面是类和继承的概念，

同时支持多态性和动态聚束等特性；而在Ada

中引入了程序包，它可以把数据和操作代码

封装在一起，支持数据抽象。

（详见教材P15.18）

CompilerPrinciples55

③语言的基本成分：

包括数据类型、表达式、语句、过程或函数等，

这些在学习语言课时都已经学过了，但从编译的角

度出发，应如何了解这些基本成分呢？

•初等数据类型：牵扯到存储空间的问题；

■结构数据类型：牵扯到下标、维数、存放方式、

分配时间动态与静态等；

・表达式：牵扯到运算分量、运算符、形成规则、

运算顺序等；

•语句：顺序、控制、循环等；