编译原理第一章教学课件

课程简介（课程地位）

上…

分类课程名校课程定位番注

计尊机导论入门

计痒机基础尊法和款据结构基础

高级语音程序设计（b2）必备工具

计算机理论数理逻辑;

《薄散数学1X3）集合论和图论|计其机数学

组台数学1

上子电路和数字逻辑________硬件基础课程含实验

计算机硬件类课程计其机原理和汇缰百言部件原理含实脆

计尊机接口与通讯部件间通讯含实验

计算机体系结构体系结构含森

计算机刖络

编译技术含课程设计

It作系统系统软付层含课程设计

计算机软件类课程

数据库荔统膜理含谡程设计

软件工程

信息系统分析与设计应用类

计管机图形学（多幅体技术）应用樊______1

开课目的

源程序—-—>目标程序____可执行

J01程序

_________)V----------

OO

形式语言与自动机

预备知识：两门以上的高级

)匚编语言

程序设计语言数据结构等

课程简介

学习的意义

W对编程语言的设计和实现有深刻的理解，对和编程

语言有关的理论有所了解，对宏观上把握编程语言

来说，起一个奠基的作用.

力从软件工程看，编译器是一个很好的实例，所介绍

的概念和技术能应用到一般的软件设计之中.

i大多数程序员同时是简单语言的设计者，有助于提

高对这些语言的设计水平.

《它的理论基础扎实，其形式化系统不仅应用于编译

技术，还大量应用于人工智能，多媒体技术及数据库

等领域.

'o//

课程简介弯

［教材和参考书］»

W肖军模，程序设计语言编译方法,大连理工

大学出版社I

小陈火旺等，程序设计语言编译原理,国防工业

出版社，2000|

小陈意云、张昱，编译原理和技术,高等教育

出版社，2003

《吕映芝等，编译原理,清华大学出版社

课程简介

课程要求:

小课时：48学时

«分为两部分：（分别计分）i

♦:♦理论基础（48学时）:课堂教学I

♦:♦实践部分（0学时）：上机实践）

目的：）

掌握编译的理论基础和形式化系统，了解

编译的全过程及其具体实现方法。能运用所

学技术解决实际问题，能独立编写一人小剂

编译系统。（

课程简介

要求：

4提前预习，认真听课,理解基本概念,基本原

理与基本算法

《在看书时或理解例题及习题时，一定要划出

相应的细节变化过程,通过画图来加深理解

9作业要求独立、按时完成

f辅导地点：软件楼421

gE-mai1：guow9966@163,com

s答疑时间：

P9学期总评=考试成绩占80%,平时占20%

内容简介

•第一章概论

•第二章编译基础知识

•第三章词法分析器

•第四章自上而下语法分析

•第五章自下而上语法分析

•第六章LR分析法

•第七章语法制导翻译技术

•第八章运行时的存贮分配

・第九章目标代码优化

方式

方式

词法分析程序

语法分析程序

语义分析程序

组成（中间代码生成程序

中间代码优化程序

目标代码生成程序

表格管理程序

卜出错处理程序

I单遍扫描的编译程序

结构

I多扫4苗的编!译^呈序

compiler

第二章

终结符号集合

知识体系

非终结符号集合

，组成

产生式集合

识别符号（开始符号）

0型文法函语结构文法）

1型文法5下文有关文法）

分类

2型文法5下文无关文法）

3型文法（正规文法）

推导/归约

推导

语法树

句型

语言与语法分析有关的概念1递归文法

句子

二义性文法

绥语直摄7罐语

句柄

compiler

第三章

知识体系

/功能-分割符号串形式的源程序，得到单词串

榆入一字符串形式的源程序

输出一单词申

词法分析《

分析方法T?•前搜索

步（1）阐才匡图-

程序设计方法-最小化DFA的状态转换图

步（2）由框图编写程序

其中“步（1）”画才匡图涉及的内容如下:

正规式7

二^NF广集遂DFA华简.最小化DFA

转换规则

compiler

第四章

知识体系

提取左公因子

自

上整本问题’।直接左递归的消除

।消除左递归间接左递归的消除

而1

下

语

法不确定方法-回溯算法

分

析满足的条件

分析方法，递归于程序的构造

｛递归于程序分析过程

确定,

方法满足的条件

LL(D分析表的构造

｛LL(D分析过程

compiler

第五、六章

知识体系

宜*rgJ如何找到当前句型的可归约串

自基本问题1将被归约串归约成哪一个非终结符号

下实现技术••移进-归约技术

而I定义

简单优先关系

上1构造方法

简单优先分析।简单优先文法

语分析算法

法优先分析法I定义

分算符优先关系1构造方法

析算符优先分算符优先文法

分析算法

分析方法

优先函数构建!需信看着法

LR分析法

一

compiler

规范句型活前缀

LR(0)项目

基础知识

LR(0)项目集规范族的构造

LR⑴项目

LR⑴项目集规范族的构造

［分析栈

LR分析法LR分析程周分析表

(自动构造)I分析方法

LR(0)分析表的构造

SLR(1)分析表的构造

分析表的构造，

LR⑴分析表的构造

LALR⑴分析表的构造

二义性文法的分析-无二义性规则的使用表的构造

compiler

第七孽

先1三只/年系1定义

得'比1小击I继承得,注

种类套合属性

禺牲文法1

语构造方法

法

制

导

■年逆茂兰式

中间语言

4*毅语法树

compiler

第八章

知识体系

运

基本思想

行

时地址

传值

刻j

参数传递

的1传结果

存।传名

储

组静态存储分配隹本思想

织存储纽卜4局部变

与栈式存

织方案静态链］活动记

分储分配［量访问的DISPLAY表T录结构

配（实现

堆式存储分配

compiler

第九章

知识体系局部优化常量合并1利用

优化的，消除公共子表达式|DAG图

目的删除无用赋值J优化

与机器

代无关的循环优化循环不变式外提

码，强度削弱

优优化

化删除归纳变量

全局优化

优化的

种类［寄存器优化

与机器有|并行分支优化

关的优化

I窥孔优化

第一章概论

（介绍名词术语、了解编译系统的结构和编译过程）

编译的起源：程序设计语言的发展

基本概念

编译过程和编译程序构造

编译程序的生成

1.1存序设计语言的发展

机器语言＞面向用户A面向问题

A汇编语言

（机器指令）的语言的语言

C70600000002MOVx,2x=2

77

高级语言

132

•低级语言(LowlevelLanguage)

字位码、机器语言、汇编语言

特点：与特定的机器有关，功效高，但使用复

争、繁琐、费时、易出错

•高级语言

--Fortran、Pascal、C语言等

特点：不依赖具体机器，移植性好、对用户要求低、

易使用、易维护等。

用高级语言编制的程序，计算机不能立即执行，

必须通过一个“翻译程序”加工，转化为与其等价的

机器语言程序，机器才能执行。

这种翻译程序，称之为“编译程序”。

1.2基本概念

•源程序

用汇编语言或高级语言编写的程序称为源程序。

•目标程序

用目标语言所表示的程序。

目标语言：可以是介于源语言和机器语言之间的

“中间语言”，可以是某种机器的机器语言，也可以是

某机器的汇编语言。

•翻译程序

修源程序转换为目标程序的程序称为翻译程序。

它是指各种语言的翻译器，包括汇编程序和编译程序，

是汇编程序、编译程序以及各种变换程序的总称

源程序、翻译程序、目标程序三者关系:

源程序翻译程序目标程序

即源程序是翻译程序的输入，目标程序是翻译程序

的输出

源程序翻译程序目标程序

5z2^?iler汇编语言汇编程序机器语言

高级语言编译程序目标程序

•汇编程序

若源程序用汇编语言书写，经过翻译程序得到用机器语言

表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过

程称为“汇编”(Assemble)I

•编译程序

若源程序是用高级语言书写，经加工后得到目标程序,

这种翻译过程称“编译”(Compile)

汇编程序与编译程序都是翻译程序，主要区别是加工对象的

不同。由于汇编语言格式简单，常与机器语言之间有——对

应的关系，汇编程序所要做的翻译工作比编译程序简单得多。

^^ompi1er

源程序的编译和运行

•编译或汇编阶段

编译程序

源程序或目标程序

汇编程序

•运行阶段

目标程序

+

输入数据运行子程序输出数据

友mpi\er

程序设计语言的转换

♦:♦翻译

—是指能把某种语言的源程序，在不改变语义的条件I

下，转换成另一种语言程序一目标语言程序

♦:.编译

—专指由高级语言转换为低级语言

解释U一

—接受某高级语言的一个语句输入，进行解释并控制

计算机执行，马上得到这句的执行结果，然后再接

受下一句

源程序的编译和运行

•编译或汇编阶段

编译程序

源程序或

汇编程序

•运行阶段

目标程序

+

输入数据运行子程序输出数

友mpi\er

程序设计语言的转换

♦:♦翻译

—是指能把某种语言的源程序，在不改变语义的条件I

下，转换成另一种语言程序一目标语言程序

孝编译

—专指由高级语言转换为低级语言

♦:.解释

—接受某高级语言的一个语句输入，进行解释并控制

计算机执行，马上得到这句的执行结果，然后再接

受下一句

•解释程序(Interpreter)

对源程序进行解释执行的程序。

•工作过程

源程序

输入数据输出数据

解释程序

•特点、与编译程序比较

源程序的中间形式

输出数据

输入数据解释程序

编译程序

编译过程概述

1.3的各个程序

一段英文翻译成中文阶段

需经下列步骤：

识别出句子中的单词词法分析

分析句子的语法结构

语法分析

根据句子的含义进行语义分析及中间代码

初步分析生成

对译文进行修饰代码优化

写出最后的译文目标代码生成

YZompi1er

1.3.1编译过程

编译过程是指修高级语言程序翻译为等价的目标程

序的过程。

习惯上是将编译过程划分为5个基本阶段:

语法分析

语义分析、一生成中间代码

萨勺码优化

生成目标程序

一词法分析

任务：分析和识别单词。

源程序是由字符序列构成的，词法分析扫描源程序（字符

串），根据语言的词法规则分析并识别单词，并以某种编码形

式输出。（

•单词：是语言的熊太语法单位，一般语言有左大

对于如下的字符串，词法分析程序将分析和识别出9个单词:

Xli^XZ.O^OXACl

123456789

/一、词法分析zz^iler

识别右边程序中的单词、

举例说明

•基本字：Void,int,float|

Voidjisuan()

{inty,c,d;•标识符：a,b,c,d,x,y,jisuan

floatx,a,b;•常数：5°

x=a+b*50;•运算符：*,+,=「

y=c+)d*(x+b;•界限符：㈠；，()

zz^iler

1.词法分析

•词法分析依照词法规则，识别出正确的单词，转换

成统一规格备用

•转换

—对基本字，运算符，界符的转换

—标识符的转换

—常数的转换

—转换完成后的格式（类号，内码）

•描述词法规则的有效工具是正规式和有限自动机

i^ompi1er

以position=initial+rate*60为例

1m、

形成一个记号的字

符序列称为该记

号的单词

position>=、initial

(a

、+、rate>*、60

并用记号表示识别出的单词

d3表示position、initial、rate

上语句:idl-id2+id3*60

;第一章概论

position=initial+rate*60符号表

1position・・•

2initial・・・

词法分析器3rate•--

id1=id2+id3*60

二、语法分析^wpiler

任务：根据语法规则（即语言的文法），分析并识别出

各种语法成分，如表达式、各种说明、各种语句、

过程、函数等，并进行语法正确性检查。

语法规则一语言的规则，又称为文法

语法规则的表示：

----BNF：A::=B|C

XI:=（2.0+0.8）*Cl

赋值语句的文法：

＜赋值语句）一＜变量＞＜赋值操作符＞＜表达式）

＜变量＞一＜简单标识符》

〈赋值操作符＞一：=

〈表达式＞一....

赋值语句的语法规则:

。A::=V=E

E::=T|E+T

T::=F|T*F

❖F::=V|(E)|C

❖V::=标识符

c：:=常数

举例说明赋值语句的语法规则:

Voidjisuan()❖A::=V=E

{inty,c,d;❖E::=T|E+T

❖T::=F|T*F

floatx,a,b;

❖F::=V|(E)|C

x=a+b*50;

V::=标识符

y=c+)d*(x+b;

❖c：:=常数

语法分析的方法：

----推导（derive）和归约（reduce）

推导---最左推导，最右推导

最右目隹导最左归约（x=a+b*50）

举例说明赋值语句的语法规则:

Voidjisuan()A:=V=E

{inty,c,d;E:=T|E+T

T:=F|T*F

floatx,a,b;

F:=V|(E)|C

x=a+b*50;

V:=标识符

y=c+)d*(x+b;

最右推导C:=常数

A^^V=Ev=E+l^^V=E+T*FV=E+T*C

—V=E+T*50—V=E+F*50

—V=E+V*50—V=E+b*50—V=T+b*50

-►V=F+b*50-►V=V+b*50-►V=a+b*50

^^x=a+b*50

归约一最右归约，最左归约

❖AV=Ei^*x=E-^x=E+T™>x=T+T

x=V+T™^x=a+Tx=a+T*F

^^x=a+F*F^^x=a+V*F^^x=a+b*F

x=a+b*C^^x=a+b*50赋值语句的语法规则:

♦:♦A:=V=E

最左推导最右归约E:=T|E+T

❖T:=F|T*F

❖F:=V|(E)|C

❖V:=标识符

❖C:=常数

举例说明赋值语句的语法规则:

Voidjisuan()*A::=V=E

{inty,c,d;❖E::=T|E+T

T::=F|T*F

floatx,a,b;

F::=V|(E)|C

x=a+b*50;

❖V::=标识符

y=c+)d*(x+b;

❖c：:=常数

)

♦:.c语言语句y=c+)

分析过程：

AV=EV=E+TV=E+F

V=E+VV=E+bV=T+b

V=T*F+bV=T*V+bV=T*x+b

❖无法得到该句

♦:♦故，该C语言语句是错误的

;二、语法分析^ompiler

•具体地说，语法分析是在记号流的基础上建立一

个层次结构-建立语法树

•语法分析过程也可以用一棵倒着的树来表示

•这棵树叫语法树，比如上述程序段中的单词序列:

idl=id2+id3*60经语法分析得知其是PASCAL语言

的“赋值语句:表示成如下所示形式。

语法分析^ompiler

_i_d___3___|___3_____|_N____u___m____|_6___0___

b.数据结构

第一章概论

idj=id2+id3*60

三、语义分析、生成中间代码

任务：对识别出的各种语法成分进行语义分析，

并产生相应的中间代码。)

•中间代码：一种介于源语言和目标语言之间的中间语

言形式I

•生成中间代码的目的：)

<1>便于做优化处理；\

<2>便于编译程序的移植。

•中间代码的形式：编译程序设计者可以自己设计，常用的有

四元式、三元式、逆波兰表示等。

~Zeller

例：Xl:=(2.0+0.8)*Cl

•由语法分析识别出为赋值语句，语义分析首先要

分析语义上的正确性,例如要检查表达式中和赋值

号两边的类型是否一致。

•根据赋值语句的语义，生成中间代码。

即用一种语言形式来代替另一种语言形式，

这是翻译的关键步骤。

(翻译的实质：语义的等价性)

position=initial+rate*60

三、语义分析、生成中间代码

一

三、语义分析、生成中间代码

总结一下语义分析主要的任务:

完成静态语义审查和处理

上下文相关性审查

类型匹配审查

类型转换

］龙如Hlei

★四元式(三地址指令)

XI:=(2.0+0.8)*C1

运左运算对象右运算对象

⑴结果

⑵+2.00.8T1

⑶T1C1T2

XIT2

其中T1和T2为编译程序引入的工作单元

四元式的语义为：2.0+0.8->T1

T1*C1一T2

T2一XI

这样所生成的四元式与原来的赋值语句在语言的

形式上不同，但语义上等价。

四、代码优化

任务：目的是为了得到高质量的目标程序。

例如：前面的四元式中第一个四元式是计算常量表达式值,

该值在编译时就可以算出并存放在工作单元中，不必生成目

标指令来计算，这样四元式可优化为：

编译时：2.0+0.8TT1

(1)*T1ClT2

⑵=XIT2

优化前的四元式：

(1)+2.00.8T1

(2)*T1ClT2

(3):=XIT2

position=initial+rate*60

第一章概论

tempi:=inttoreal(60)

tempi:=id3*tempi

temp3:=id2+tempi

idl:=temp3

代码优化器

tempi:=id3*60.0

idl:=id2+tempi&

四、代码优化

试图改进中间代码，以产生执行速度较快占用内

存空间少的机器代码

原则：等价变换

主要方面：公共子表达式的提取、合并已知量、

删除无用语句、强度削弱、循环优化等优化工作

代码优化工作会降低编译程序的编译速度，因此

编译优化阶段常常作为可选择阶段，编译程序具

有控制机制以允许用户在编译速度和目标代码的

质量间进行权衡。

代码优化

例：将下面的语句转换

成中间代码

k=1

for(k=1;k<=100;k++)10ifk<=100then

{m=i+10*k;

{m=i+10*k;

n=j+10*k;

n=j+10*k;k++;

goto10;

})

四、代码优化

序号OPARG1ARG2RESULT

(1)1k

■k=1

(2)100k(9)

*10ifk<=100

(3)10kTithen

■

(4)+ITim{m=i+10*k;

*n=j+10*k;

(5)10kT

■2k++;

+ngoto10;

(6)JT2

⑺+k1k)

■

(8)J(2)

(9)

四、代码优化

序号OPARG1ARG2RESULT

■

(1)Im

■k=1f

(2)Jnm=i

(3)1kn=J|

■

(4)100k(9)10ifk<=100then

+m10m{m=m+10;

(5)n=n+10;

(6)+n10nk++；

⑺+k1kgoto10;

■

(8)J(4)

(9)

五、目标程序生成

任务:把中间代码变换成特定机器上的低级语言代码。

目标代码形式：

—绝对指令代码

—汇编指令代码

一可重定位的指令代码。

编译的最后阶段，它的工作与硬件系统结构和指令定义有

关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运

用、机器指令的选择、各种数据类型变量的存储空间分配以

及寄存器和后缓寄存器的调度等。

五、目标代码生成

由中间代码很容易生成目标程序（地址指令序列）。这

部分工作与机器关系密切，所以要根据机器进行。在做这

部分工作时（要注意充分利用累加器），也可以进行优化

处理。

XI:=(2.0+0.8)*C1

LOAD2.0

ADD0.8

STOT1作利用累LOAD2.0

LOADT1加器的优化ADD0.8

MULClMULCl

STOT2STOXI

LOADT2注意：在翻译成目标程序的过程中,

STOXI要切记保持语义的等价性。

position=initial+rate*60

五、目标程序生成

使用两个寄存器（RI和R2）,上面生成的中间代码可

生成下面的汇编代码

(1)(MOVFid3R2)

(2)(MOLF#60.0R2)

(3)(MOVFid2R1)

⑷(ADDFR1R2)

(5)(MOVR1id1)

position=initial+rate*60

五、目标程序生成

tempi：=id3*60.0

idl：=id2+tempi

符号表

1position•••

代码生成器2initial•••

3rate•••

MOVFid3,R2

MULF#60.0,R2

MOVFid2,RI

AbbFR2,RI

MOVFRI,idl

1.3-2编译程序构造

一、编译程序的逻辑结构

按逻辑功能不同，可将编译过程划分为五个基本阶段，

与此相对应，我们将实现整个编译过程的编译程序划分为

五个逻辑阶段（即五个逻辑子过程）。

编译程序构造

在某机器上为某种语言构造编译程序要掌

握以下三方面：

-----源语言

-----目标语言

-----编译方法.I

i—Zeller

上上列五个阶段中都要做两件事：

（1）建表和查表；（2）出错处理；

所以编译程序中都要包括符号表管理和出错处理两部分

★符号表管理I

在整个编译过程中始终都要贯穿着建表（填表）和查表的

工作。即要及时地把源程序中的信息和编译过程中所产生的信

息登记在表格中，而在随后的编译过程中同时又要不断地查找

这些表格中的信息。I

4昔无甲

规履建官盔痈程序难免有多种错误，编译程序必须要有出错I

处理的功能。即能诊察出错误，并能报告用户错误的性质和位

置，以便用户修改源程序。出错处理能力的大小是衡量编译程

序质量好坏的一个重要指标。

z^piler

典型的编译程序具有7个逻辑部分

S.P

词法分析

符语法分析

出

号

错

表

处

管语义分析、生成中间代码

理

理

代码优化

生成目标程序

6、表格管理

。作用：用来记录源程序的各种信息以及编译

过程的各种状况。

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

—符号表,常数表?标号表?分程序入口表5

中间代码表等

1）符号表：用来登记源程序中的常量名，变

量名，数组名，过程名等。

—记录它们的性质,定义和弓I用情况

符号表管理

符号表是一个数据结构

。。

每个标识符在符号表

中都有一条记录

NameTypekindvaladdr

id1

id2

常数表与标号表

常数表标号表

NAMEINFORMATION

值

1

4

10四元式序号4

入口名表

。作用：登记过程的层号，分程序

符号表入口等

NAMEINFORMATION

INCWAP二目子程序，四元

式序号1

中间代码表（四元式，三元组构成表）

序号0PARG1ARG2RESULT

(1)1k

■

(2)100k(9)

*

(3)10kTi

(4)+ITim

*

(5)10kT

■2

+n

(6)JT2

⑺+k1k

■

(8)J(2)

(9)return

7、错误处理

任务：在编译的各个阶段都会发现源程序中的错

误，为了使编译器能继续运行，以检测出源程序

中更多的错误，在检测到错误后，必须以合适的

方式进行错误处理。

完成：由专门的出错处理程序来完成

错误类型：一语法错误

—语义错误

>error

二、遍（PASS）

遍：对源程序（包括源程序中间形式）从头到尾扫描

一次，并做有关的加工处理，生成新的源程序中间形

式或目标程序，通常称之为一遍。

第一遍第二遍

S,0C2S,P.......op

S.PC1中间形式11甲间形式25产

k__________）

★要注意遍与基本阶段的区别

上一■遍的结果是下