计算机课件第06章 编译技术

第6章编译技术

6」编译程序的工作过程

6.2状态矩阵法的编译过程

6.3词法分

6.4中间语言表示

6.5语法的分析与加工

左

编译程序是一种将高级语言编

写的源程序编译成机器语言程序

（称为目标程序）的实用程序。

g.i编译程序的工作过程

为了将源程序翻译成目标程序，一般

都要包括以下几个步骤。

①输入源程序。

②对以机内码表示的源程序进行词法

分析，辨认出一个个单词符号。

③根据源语言的语法规则进行语法

分析。

④在实际运行之前，通常还要对目

标程序的各部分进行连接装配。

对于块结构的语言（如C语言和

FORTRAN语言等），通常是进行分块

编译，分别得到半目标程序，最后可用

装配程序组装成一个完整的程序。

图6.1三遍扫描的编译过程

半目标程序1

装

半目标程序2配错误处理

程

.一-库程序

序

半目标程序72

▼

目标程序

璐图丘2半目标程序的装配示意图

编译程序一般要包含以下几个程序模块。

(1)词法分析程序

(2)语法分析程序

(3)加工程序

(4)优化修饰部分

(5)装配程序或连接编辑程序

6.2状态矩阵法的编译过程

6.2.1状态矩阵法的基本原理

所谓“状态”，粗略地说，是表示过

去已经扫描了什么语法成分，以便当遇到

新的语法符号时，在不同的状态下对该语

法符号作出不同的处理。

状态矩阵法的核心是状态矩阵（也称

‘犬态表），如表6」所示。

\单击鼠标左键换页R|G|>P

<61状态矩阵

♦•~•A4•

SY?

】

STSUB1]SUBn

ST1SUB?1SUBJ2

ST,SUBfSUBpSUB"

单击鼠标左键换页

6.2.2状态矩阵的压缩

在具体实现状态矩阵法时，为了节省

存储空间，通常要对状态矩阵进行压缩。

V冏〉同

表6.2m=〃=3的状态矩阵

SY,SY3

SUB12EPJI.OR

STJERRORSUBnERROR

ST】ERRORSUBnSUB33

*朦麻蟋V窗〉a

•・

表6.3状态矩陈压缩后的形式

状态符号加工子程序伏态改变转向

1

SY1SUBnfST,>ST,N

SY：SUBn+STjN

•・•・

OtherERRORP

f

SYjSUBn

ST3

1OtherERROR

SYj+STj,STN

•SUB33r

鹏SHSUB”-STiN

15'■.■1,»

FOtherERRORp

各列的意义如下:

①状态指状态栈栈顶项中所包含的

可能状态。

②符号指当前扫描到的可能符号。

③加工子程序指当前遇到的相应状

态符号配对时编译程序应做的工作。

V冏〉同

INITIATION

图6.3状态矩阵法的总控程序框图

6.3词法分析

6.3.1词法分析的任务

词法分析是编译过程各阶段的基础和

必要的准备。

词法分析的主要任务是从源程序语句

中识别出具有独立意义的语法单位（即语

法符号），并且建立一个符号表，用以保

存各语法符号的属性。

表6.4符号表

序号符号属性其他信息

001RN实符号名

002赋值号

003(左括号

0042.4实常数

005*乘号

006+加号

007X实符号名

008)右括号

009除号

010N整符号名

表6.4中的符号最后都变成二进制

形式的代码串。

可以将这些通用符号建立一个通

用符号表，这些符号的代码可用较大

的编号来表示，如表6.5所示。

在这种情况下，上述赋值语句经

词法分析后可以得到一张符号表如表

6.6所示。

醒噌蝴㈱

表65通用符号表

符号编码

+900

901

*902

903

904

)905

906

表6.6符号表

序号符号属性其他信息

001RN实符号名

0022.4实常数

003实符号名

004N整符号名

6.3.2读字符程序

读字符程序的任务是从源程序字符串中顺

序读出基本符号，并作一些简单的处理后提供

给词法分析程序。

6.3.3状态矩阵法的词法分析过程

词法分析程序可以用状态矩阵法来实现。

醒

由图6.4可以看出，每执行一次这

个程序，就顺序从源程序中读出一个

语法符号，并且将有关的信息存放在

一些工作单元中。

读下一个语法单位的第一个字符CH

判断CH

图6.4直接分析方法的框图

左

下面以FORTRAN语言为例来说明用

状态矩阵法实现词法分析的过程。为简单

起见，作如下一些假设：

①不考虑格式语句。

②不考虑数的翻译。

③不考虑以E开头的运算符，且运算

符只有两个字母。

V冏〉同

♦表6.7FORTRAN说词程序的状态矩阵

状态符号加工子程序状态改变转向

字母fNAMEN

数字—NUMBERN

fRN

PR

*-STARN

4结束N

其他给出队列中的符号N

字母当队列中是专用定义符时，给出该符号，并且N

-PR.否则不做任何工作

NAME

数字N

其他给出队列中“名”，保留其他fPRP

左

状态符号加工子程序状态改变转向

数字

*保留读字符指示器N

NUMBERE—PNN

-PN

其他给出队列中的“整型数”，保留其他-*PRP

RN字母给出队列中的“整型数”恢复读字符指示器-*PRP

数字N

RN1E给出队列中的“实型数”，保留其他fPN

其他-PRP

数字fPlN

PN

其他错误P

数字-*P1N

+fPNN

P

—fPNN

其他错误P

左

数字N

Pl

其他给出队列中的“实型数”，保留其他fPRP

字母-R1N

R数字-*PN1N

其他给出队列中的“”，保留其他-PR，P

字母N

RI

其他错误->POINTP

■若队列中为拼写运算符，则给出运算符，并N

POINT-PR,否则错误

其他错误P

♦给出队列中的“**”—PR:"N

STAR->PR1

其他给出队列中的，保留其他P

f

w#ssi

1单击鼠标左键换页

表6.8逻辑条件语句的分析过程

当前扫描到的

状态栈队列切口工情况转向

基本符号

PRII—NAME；N

NAMEFIF给出专用定义符IF，且-PRN

*R•：G给出左括号（:N；

PRRRfNAME；N

NAMER.给出名字R，保留其他，fPRP

PRfRN"

RG,.GfRlN

RIT.GT-POINT；N；

POINT.GT.给出运篁符.GT-一PR:N

—*，

PR11-NUMBER；N

NUMBER1.保留读字符指示器，fRNN

RN01.0N

------------------------------------」

1

RN)1.0)给出实型数1.0,保留其他，-PRP

|PR：'给出符号）N

1PR

AAfNAMEN

[NAMEBABN

[NAME1A—B•IN

|NAME

=ABU给出名字AB1,保留其他，fPRP

PR=给出符号=N

1PR

*-RN

R22—PJN1N

|RNlE,2E->PN

F+.2E+—PN,N

|PN6,2E+6-PlN

*,2E+6*给出实型数2E+6,保留*,fPRP

|PR*fSTARN

'STARB给出*，保留B,fPRP

IPRB-►NAMEN

"NAMECBCN

当前扫描到的

状态栈队列力情况转向

基本符号nX

NAME—BC-给出名字BC,保留-，-PRP

PR一给出-N

PRXX—NAMEN

NAME2X2H

NAMEHJX2H给出X2,保留T,fPRP

PR结束N

1

1建换页V合〉〉[]

1单击鼠标左4

表6.9语法符号表

序号123456

符号IFR.GT.L0：'

78910111213

ABI=2E+6*BC—X2

聿击鼠标左键换页〈局〉〉

6.3.4算术常数的识别和翻译

在词法分析的过程中，不仅要识别出

常数，还需要将常数翻译成统一的格式。

经过词法分析后，所有的实数都分解

成两部分：一部分是有效数字的所有位组

成的正整数；另一部分是以10为底的整数

指数部分。

醒

图6.5算术常数的识别与翻译流程图

表6.10常数翻译的状态矩阵表示

状态符号加工子程序状态改变转向

数字夕=0,x=Q,p=CI,g=+=1。*y+数fBN

字-*CN

AA

V=0,x=0,p=0,g=+P

耳他ERROR

数字，=io*y+数字N

->DN

B

EfE;N

其他V=2^10^*,结束P

数字*10*^+数字,w=n+lfDN

C

其他ERRORP

数字夕=10**+数字,？2=力+1：N

DE->EN

其他方=獐10个",结束P；

+fFN

—E=一->FN

E

数字P=10*2»+数字fGN

其他ERRORP；

数字尸=10*p+数字-GN

rn

其他ERRORP

数字尸=10*p+数字N

G其他1

*=獐1匕1，结束P：

单击鼠标左键换页V合〉H

表6.11状态矩阵法对常效的识别与翻译过程

状态栈当前扫描到的基本符号加工绪果转向

A0，=0,n=O>p=O>e=+N

B*.N

D0V-0»门=1N

D3\V-39n-2N

D232,n=3N

DE-M

E—e=一N

F1P=1N

GV=32x10*】=32xIT，绪束

单击艮曷标左键换页

6.4中间语言表示

中间语言”,为能用来表述源程序

并与之等效的一种编码方式。

6.4.1波兰表示

一个表达式的波兰表示就是后缀表示,

即表达式中的运算对象写在前面，运算符

写在后面。

（2）无条件转向语句

GOTOn

的波兰表示为:

n'GOTO

（3）逻辑条件语句

IFCS

的波兰表示为:

CS'LIF

（4）子程序调用语句

CALLS(yl,y2,yn)

的波兰表示为：

yl',y2',yn'SSUB

6)维数说明语句

DIMENSIONA(N,

的波兰表示为：

NMADIM

（6）函数子程序段头语句

FUNCTIONF(X1,X2,…，XN)

的波兰表示为:

XI,X2,…，XNFDEFF

V冏〉同

6.4.2三元组表示

波兰表示有一个缺点，就是不便于

作代码的优化。

三元组表示的一般形式为:

k,(0olo2)

V冏〉同

表6、12三元组表示的优化过衽

序号三元组出现次数变化过程最终出现次数

1、*AB121211

2/CD121211

3+1212322

4；然A3122

5+3411

6尸4D11

7-5611

左

去6.13翻译三元组表示的规则

运算符

可交换运算符。不可交换运苴符。

运算对象—

olc.2当AC=O时：当ACWO时：

取。1存T

9o2'取"o*"l••

0o2

当AC=。时：当ACW0时：

0取。1存T

olL

ol田Tr取⑹

eT

Lo29o2

当AC=0时：当ACWO时：

LL0Tr存T

9T

左

表6.14翻译三元组的过程

序号三元组出现次数目标程序指令

1*AB1取A

2/CD1存T1

取C

ID

3计122+T1

存T2

4*A32*A

存T3

5斗341+T2

6/4D1存T4

取T3

Q

7-561存T5

取T4

-T5；I

表6.16FORTRAN部分语句的三元组表示

语句名称涪司二兀蛆表示:说明

赋值语句V=ee的二兀蛆表示设表达式e在第n-1

n,(=n-1V)个三元组时算出

无条件转向语句GOTOL(GOTOL)

逻辑条件语句IF(C)SC的二兀蛆表示设表达式C在第n-1

n,(UFn-lL)个三元组时算出

语句s的三元组表示

(LABL)

算术条件语句IF(C)L1L2L3C的二兀组表示设表达式C在第n-1

n,(BMn-lL)个三元组时算出

n+l>(BZn-1L)

n+2,(BPn-lL)

数组说明语句DIMENSIONA(dl,d2)n,(DIMdl)DIM为维运算符

n+1,(DIMd2)ADEC为数组运菖符

n+2,(ADECA)

左：页

调用语句CALLSfywg实元五的三元蛆表示设凭值地址在第个

实元力的三元蛆表示三元组菖出，SUB为子

1程序调用运算符

*

,(ACAm。

1

(ACAmJ

>(SUBS)：

子程序返回语句RETURN(RETURN)々无运算对象

结束行终止语句END(END)无运算对象

噌曲李㈱蟋

1单击鼠林左键换页々合〉以

6.5语法的分析与加工

语法分析和加工的主要任务有

以下几项。

①识别出各种类型的语句，并

进行语法检查。

②语法的加工处理。

③编译程序工作的最后结果是

产生目标程序或半目标程序。

醒噌蝴蟋

示左键换V冏〉同

6.5.1优先矩阵法

优先矩阵法的基本思想如下。

将程序设计语言中的所有算符（广

义运算符，包括算术运算符、分隔符、

拼写定义符及界限符卜和T等）设置一

个优先关系，而这种优先关系用一张优

先矩阵表来表示。

表6.17;优先矩阵表

1

**

+一♦/()

+>><<<<>>

一>><<<<>>

♦>>>><<>>

/>>>><<>>

**>>>>><>>

(<<<<<<=X

)>>>>>X>>

卜<<<<<<XQ

・21

L・■■—Q(■、I[----』

表6.18优先矩阵法编译过程

当前扫描到的

当前运算对象栈当前算符栈处理说明目标程序指令

语法符号

H喳算符栈：

A卜A进运算对象栈

♦h卜因1c叫率进算符栈

A*卜因*<3（进算符栈

BA(*hB进运算对象栈

+BA(*F因（《+，+进翼符枝

CBA+(*hC进运算对象栈

)CBA；+（叶因+>），产生B+D代码取B

+C

A（*卜因(=），）进菖符栈

1

w#ssi

i单击1标左V。〉以

AX叶因））-，）与（退出算符栈

A叶因*）-,产生A*AC代码♦A

H因卜<-，-进篁符栈

c-F.；C进运算对象栈

rC-卜因"磁算符栈

DCD进运篁对象极

r二.取•密

HDCH因/>T，存累加器，产生CQ存T1

代码取C

/D

-卜因->T，产生T1-AC代码存T2

取T1

-T2

卜因卜与T配对，结束

左

6.5.2优先数法

基于算符的优先数进行编译的方法称

为优先数法。

表6.19优先敬我

*

)**/+一(卜

栈内优先数工©)97553310

栈外优先数虱夕)16442280

6.5.3状态矩阵法

状态矩阵法用表格形式来描述编

译过程，因此条理十分清楚，这是其

他方法所不及的。

V冏〉同

6.5.4递归子程序法

递归子程序法的基本思想是：从整个

源程序开始，根据各种语法成分的形成规

则从大到小逐层往细分析处理，而对于每

个递归定义的语法成分，都用一个相应的

递归子程序来进行处理。

V冏〉同

SuccesswithMoneyandJoy

附熠人生心语

•成功是一种观念

•致富是一种义务

•快乐是一种权利

•每个人都有能力、有义

务、有权利办到成功

致富快乐

附赠人生心语

成成功不是打败别人

功成功不是超越别人

成功不是名、利、权的获得

致拥有健康的身体

丰足的物质生活

富平衡的心理状态

又才能拥有成功

快SuccesswithMoneyandJoy

战胜自己

乐贡献自己

扮演好自己的历史角色

才能超越自己

融入成功里

附赠人生心语

知人者智，自知者明，胜人者力，自

胜者强。

——老子

附赠人生心语

•成功必须靠百分之九十八的辛勤血

汗，加上百分之二的天才灵感。

•世界上注定只有百分之二十的人会成

功。

附赠人生心语

成犹太谚语中有一句名