第四章 语法分析1最后版本

编译原理

CompilerPrinciples

第四章语法分析

黄海平_compiling

Irunning

yprogramming

hhp@I

南京邮电大学,计算机学院一

教材：《编译技术原理及其实现方法》王汝传编著

第四章语法分析%]

矗

本章内谷、

§4.1引言.

一、语法分析任务

二、语法分析方法

§4.2自顶向下语法分析

一、自顶向下分析方法的问题及其解决办法

二、递归子程序分析法(递归下降分析法)

三、LL(1)分析法

§4.3自底向上语法分析

一、简单优先文法分析法

二、算符优先分析法

三、优先函数及其构造

四、LR分析法

五、二义性文法的应用

§4.4语法分析程序的自动生成

一、分析器的生成器YACC

二、用YACC处理二义性文法2」

第四章语法分析

本章内容、

§4.1弓|言

一、语法分析任务

二、语法分析方法

§4.2自顶向下语法分析

一、自顶向下分析方法的问题及其解决办法

二、递归子程序分析法(递归下降分析法)

三、LL(1)分析法

§4.3自底向上语法分析

一、简单优先文法分析法

二、算符优先分析法

三、优先函数及其构造

四、LR分析法

五、二义性文法的应用

§4.4语法分析程序的自动生成

一、分析器的生成器YACC

二、用YACC处理二义性文法3

§4」引言_

本节内容

一、语法分析任务

1.语法检查

2.根据语法符号进行一定处理加

:、语法分析方法

1.自顶向下语法分析方法

2.自底向上语法分析方法

§4.1引言

-一、语法分析任务—

词法分析阶段，主要介绍了单词符号的结构、识别（用

状态转换图），描述（通过正规式）以及有限自动机DFA和

NFAo

在一个编译程序对某个源程序完成了词法工作以后，就

进入了语法分析阶段。由词法分析程序所产生的单词符号流,

作为语法分析程序的输入串，按文法规则分析检查是否构成

了合法的句子。

首先来了解一下语法分析的任务。

§4」引言Q

_Bu

一、语法分析任务一

、语法分析任务

1.语法检查

2.根据语法符号进行一定处理加工

、语法分析方法

1.自顶向下语法分析方法

2.自底向上语法分析方法

§4.1引言物

一—、语法分析任务—>

1.语法检查

根据语法规则对各种语法成分进行分析，确定它们的

语法关系以检查语法上的正确和错误，并指出错误的性质

和出错位置。

如：ifBthenSIelseS2

若写成ifBthenelseS2就错了（then后少一个SI）

7

§4.1引言1

BQ

一、语法分析任务一

、语法分析任务

1.语法检查

2.根据语法符号进行一定处理加工

、语法分析方法

1.自顶向下语法分析方法

2.自底向上语法分析方法

§4.1引言物

一—、语法分析任务—>

2.根据语法符号进行一定语义处理加工

如语法分析过程得到一个合法的句子时，往往同时进

行必要的语义分析等

如：当遇到处理表达式a+b*c时，若该表达式语法关j

系正确，就可以进行语义处理加工，可将该表达式]

变成中间语言，以便以后生成目标程序

9

§4.1引言1

lu

二、语法分析方法—

-、语法分析任务

1.语法检查

2.根据语法符号进行一定处理加工

八语法分析方法

1.自顶向下语法分析方法

2.自底向上语法分析方法

§4.1引言物

、语法分析方法—>

语法分析方法很多，但能够产生计算机程序并

能得到广泛应用的主要有两大类，按照生成语

法树的顺序，分别称为自顶向下和自底向上分

析方法。

11

§4.1引言第

二、语法分析方法—>

-、语法分析任务

L语法检查’

2.根据语法符号进行一定处理加工

二、语法分析方法

1.自顶向下语法分析方法

2.自底向上语法分析方法

12

§4」引言Q

9u

二、语法分析方法—

1.自顶向下语法分析方法

(1)带回溯分析方法

(2)不带回溯分析方法

(3)递归子程序法

(4)LL(1)分析法

§4.1引言

、语法分析方法

一、语法分析任务

1.语法检查

2.根据语法符号进行一定处理加

八语法分析方法

L自顶向下语法分析方法

2.自底向上语法分析方法

14

§4.1引言B

9u

二、语法分析方法—

2.自底向上语法分析方法

(1)简单优先分析法

(2)算符优先分析法

(3)LR分析法

(4)SLR分析法

(5)LALR分析法

第四章语法分析

本章内容、

§4.1引言

一、语法分析任务

二、语法分析方法

§4.2自顶向下语法分析

一、自顶向下分析方法的问题及其解决办法

二、递归子程序分析法(递归下降分析法)

三、LL(1)分析法

§4.3自底向上语法分析

一、简单优先文法分析法

二、算符优先分析法

三、优先函数及其构造

四、LR分析法

五、二义性文法的应用

§4.4语法分析程序的自动生成

一、分析器的生成器YACC

二、用YACC处理二义性文法16

第四章语法分析

本章内容、

§4.1引言

一、语法分析任务

二、语法分析方法

§4.2自顶向下语法分析

一、自顶向下分析方法的问题及其解决办法

二、递归子程序分析法(递归下降分析法)

三、LL(1)分析法

§4.3自底向上语法分析

一、简单优先文法分析法

二、算符优先分析法

三、优先函数及其构造

四、LR分析法

五、二义性文法的应用

§4.4语法分析程序的自动生成

一、分析器的生成器YACC

二、用YACC处理二义性文法17

§4.2自顶向下语法分析&

本节内容

一、自顶向下分析方法的问题及其解决办法

1.消除回溯

2.消除左递归

二、递归子程序分析法(递归下降分析法)

1.递归子程序定义

2.递归调用子程序的处理

3.分析实例

4,递归子程序特点

三、LL(1)分析法

1.定义

2.LL(1)分析方法

3.构造分析表

4.LL(1)文法18

§4.2自顶向下语法分析1

＜一—、自顶向下分析方法的问题及其解决办法—\

一、自顶向下分析方法的问题及其解决办法

1.消除回溯

2.消除左递归

二、递归子程序分析法(递归下降分析法)

1,递归子程序定义

2.递归调用子程序的处理

3.分析实例

4.递归子程序特点

三、LL(1)分析法

1.定义

2.LL(1)分析方法

3.构造分析表

4.LL(1)文法19

§4.2自顶向下语法分析1

、自顶向下分析方法的问题及其解决办法一\

一、自顶向下分析方法的问题及其解决办法

L消除回溯

2.消除左递归

二、递归子程序分析法(递归下降分析法)

1.递归子程序定义

2.递归调用子程序的处理

3.分析实例

4.递归子程序特点

三、LL(1)分析法

1.定义

2.LL(1)分析方法

3.构造分析表

4.LL(1)文法

20

§4.2自顶向下语法分析&

"一、自顶向下分析方法的问题及其解决办法—\

L消除回溯

对于自顶向下语法分析来说，对于某些文法，可能会遇到“回溯”和

“左递归”的问题，为了能有效地运用这种语法分析方法，应使文法不含左

递归及避免回溯。

(1)回溯分析方法定义

在进行自顶向下语法分析时，对于文法规则中具有同一左部而右部有

不同规则时，在分析时按顺序一个个试探，若能分析下去则成，否则再退回

到出错点换另一规则重新试探。这种方法称回溯分析方法。其实质就是使用

不同规则反复试探。

如：S：：=cAd

A：：=ab|a

要判断“cad”是否为该文法的句子，可以分别用A：：=ab和A：：=a代入

第一个产生式中试探。21

§4.2自顶向下语法分析&

＜一—、自顶向下分析方法的问题及其解决办法—＞

(2)回溯问题的解决.

1)路标法

定义：设有规则U：：=a1V1|a2V2|...|anVn若为为互不相同的

终结符时，将为作为路标，当被分析符号串为匹时，便可

按规则U：：=aVi往下分析，这样可以消除回溯。

如：

v语句〉：：=＜变量＞:=＜表达式＞|ifv布尔表达式,thenv语句》

当分析语句：ifAvBthenA:=B时，我们可以根据第二个

产生式以if开始直接选用它作判断。ifS这里就是路标

因此，我们在设计程序设计语言时，要考虑语法规则各选

择项开始符号互不相同一

§4.2自顶向下语法分析&

一—、自顶向下分析方法的问题及其解决办法—>

一般地，设U为文法G的任意非终结符号，若.

+

U：：=diIa2I…Ian|^HiV

若定乂任一个选择ai的所有可能推出终结符号串的首符号集FIRST(aQ

^^HHRST(aj)={aIa户*心・.，V1

显然FIRST(ap

为了避免回溯，

FIRST(a।)AFIRST(dj)=0(响)

即对文法中的任意一个非终结符号，其规则右部有多个选择时，若由

各个选择所推出的终结符号串首符号集合要两两不相交。这样，就可能

根据当时读进的符号是属于哪个选择的FIRST(aj),来唯一地确定

该选用哪个选择来匹配输入串。

如：当前输入符号为b(b£丫丁)^■如果b£FIRST(di),则可以

选择第i个产生式去匹配输入串。

23

§4.2自顶向下语法分析&

<一—、自顶向下分析方法的问题及其解决办法—>

2）提取左因子法

当文法不满足上述路标法条件，即右部各规则首符号相同时，我们可以

采用提取左因子法对文法进行改写。

一般地说，

U：：=aPiIap2I...IapnIyMI

U：：=aUrI

u-:=p1Ip2I...Ipn-

其中a称为左公因子，经过反复提取公因子即可将每个非终结符的所有

选择首符号集变成两两不相交。.

24

§4.2自顶向下语法分析1

、自顶向下分析方法的问题及其解决办法一\

注意：U：：=xy|x,可写成U：：=x(y|8),当分析符号串遇到s时，认为总

能匹配，可以一直分析下去。U：：=xy|x,也可写成U：：=x[y],表示y不出

现或出现一次。

25

<一—、自顶向下分析方法的问题及其解决办法—>

如：有文法S：：=xAy,A：：=**|*要分析x*y,显然存在回

溯。为避免分析时回溯，可以将文法改写成：

S::=xAy,A：：=*（*|8）

进一步改写成

S：：=xAy,A：：=*APAi：：=*|gS

为分析符号串x*y,可以从开始符号出SnxAy,I

下一待匹配符号为*,所以用A：：=*A-得:[二，

SnxAynx*%%下一个待匹配的符号为y,所XAY

以/、

I用AJ：=£（若用AJ：=*则意味着下一个为*,*中

不能匹配）得S=xAy=x*A]y=>x*£y（即x*y,I

匹配成功）。£

可见没出现回溯现象。

26

§4.2自顶向下语法分析&

<一—、自顶向下分析方法的问题及其解决办法—>

一、自顶向下分析方法的问题及其解决办法

1.消除回溯

2.消除左递归

二、递归子程序分析法(递归下降分析法)

L递归子程序定义

2.递归调用子程序的处理

3.分析实例

4.递归子程序特点

三、LL(1)分析法

1.定义

2.LL(1)分析方法

3.构造分析表

4.LL(1)文法

27

§4.2自顶向下语法分析&

BIB

，-、自顶向下分析方法的问题及其解决办法;一＞

2、消除左递归

(1)问题的提出‘

在自顶向下分析过程中，假定现在轮到要用非终结符u去匹配输入串，

它是一条直接左递归规则，这种左递归文法将使上述自顶向下的分析过

程陷入无限循环，即：

当试图用U去匹配输入串时会发现，在没有吃进任何输入符号的情况下，

又得重新要求U去匹配，如此循环下去而无终止。

若文法具有间接左递归，

Un+U■

那么，也会发生上述问题。28

§4.2自顶向下语法分析物

__——一二_n

一、自顶向下分析方法的问题及其解决办法一\

如：已知文法G[S]

S：：=AB

A：：=bB|Aa（存在直接左递归）

B::=Sb|a

现分析符号串baabaab是否是文法G的句子。

其分析过程如下：

SnABnbBBnbSbBnbABbBnbbBBbB（得第二个

字符与输入串不匹配）

S=>ABnbBB=>bSbBnbABbBnbAaBbB

（只能用A：：=Aa推导，又遇A,出现了死循环）

由于文法规则中有左递归A：：=Aa,所以无法分析下去

29

§4.2

、自顶向下分析方法的问题及其解决办法一\

（2）消除左递归方法

1）用重复表示法（扩充的BNF表示法）改写语法规则

A：：=Aa|p

其中a非空，P不以A开头,

A：：=0{a}・

例如，

30

§4.2自顶向下语法分析显

f一i一、自顶向下分析方法的问题及其解决办法"一\

§4.2自顶向下语法分析富

、自顶向下分析方法的问题及其解决办法一\

同样，■■■

等价于T：：=T(*F|/F)IF

T：：=F{*F|/F)

这样，改写后的文法消除了直接左递归。可以证明，改写前后的文法

是等价的。

32

§4.2自顶向下语法分析&

自顶向下分析方法的问题及其解决办法，一\

2)消除直接左递归

还可用另一种方法来改写形如文法规则A：：=AaI0的直接左递归

对A引入一个新的非终结符A，，将A：：=A(x|

A：：=0A，^!

A，：：=aA，|

由于P不以A开头，a不以A，开头，因此改写后两条规则不是直接

左递归。同样可以证明这种形式和原来形式是等价的。

33

§4.2自顶向下语法分析®

、自顶向下分析方法的问题及其解决办法一\

AA

/\pA

Aa/、

/aA'

Aa/:

/、等价a/、

,

AaaA

II

Pe

PaaaPaaa

34

§4.2自顶向下语法分析1

/一—、自顶向下分析方法的问题及其解决办法—\

就一般而言，

A：：=A(X]|Aa2|...|Aan||p2|...|pj

这时可改写成如下形式：

A：：=A(di[02I…I%)IPlIP2।•••I0n・

由消除直接左递归方法，得

A：：=(%邙2I…邙n)A'・

A，：：=(a1Ia2I…I册)A'I

35

§4.2自顶向下语法分

（一一、自顶向下分析方法的问题及其解决办法—\

例如：A：：=Ac|Aad|bd|e等价于A：：=A(c|ad)|bd|e,所以可以改

写成：

A：：=(bd|e)N(即A：：=bdA，|eA，)

A，：：=(c|ad)A91£(即A，：：=cA[adA1g)

：|iM|

TE，：：=+TE，|

T：：=FT，|：：=(E)|

36

§4.2自顶向下语法分析脸

<一—、自顶向下分析方法的问题及其解决办法—>

上述两种方法可消除任意直接左递归，但不能消除两步或多步推导形成

的左递归。

例如，有文法G[S]■

S：：=QcI

Q：：=RbIb^H

R：：=SaI

该文法无直接左递归，但有间接左递归，

SnQcnRbcnSabc^H

即Sn+Sabc^H

37

§4.2自顶向下语法分析B

/一一、自顶向下分析方法的问题及其解决办法—>

3)消除间接左递归电

对于间接左递归先将间接左递归变成直接左递归，然后消除直接左递归

例如；A：：=aB|Bb(1)

B：：=Ac|d(2)

先将(1)代入(2)中，得

B：：=Bbc|aBc|d(3)

由止匕将(3)改写为；

B：：=(aBc|d)B'

B，：：=bcB，|g

加入文法开始符号的产生式得消除左递归后的等价文法为：1

A：：=aB|Bb

B：：=(aBc|d)B，

B'：：=bcB'|£38

§4.2自顶向下语法分析事

<一—、自顶向下分析方法的问题及其解决办法—>

4）消除文法递归的一般算法

要求：文法不含形如An+A的推导，也不存在人：：=£这样规则

算法思想如下：

①将文法G的所有非终结符整理成某种顺序U1,U2,...Un

②从U1开始消除U1规则的直接左递归

③用左部为U1的所有规则右部替换左部为U2,右部以U1开始的规则中

的UL并消除U2规则的直接左递归。

④用类似的方法把ULU2的右部替换左部为U3,右部以ULU2开始

的规则中，消除U3规则中的直接左递归。

⑤重复上一步，直到最后把左部为ULU2,…Umi的右部带入Un规则

中，并消除Un中的直接左递归。

⑥消除多余规则

39

§4.2自顶向下语夕

（一一、自顶向下分析方法的问题及其解决办法—\

①将文法的所有非终结符整理成某种顺序然后

GU-U2,...Un,

F0Ri:=1T0n

F0Ri：=1T0i-1

把形如Uj：：=Uj)

Ui：：=x~Ix2yI

其中Uj：：=X1

X2

③去掉多余规则（如果有的话）消除左递归算法40

§4.2自顶向下语法分析嚼

、自顶向下分析方法的问题及其解决办法一\

例4.2设有文法G[S]

S：：AaI

A：：AcISdI

应用上述算法，将非终结符排列S,A。

F0Ri：=1T02

41

§4.2自顶向下语法分析科

/一—、自顶向下分析方法的问题及其解决办法—\

当1=1时，上述语句对文法G不产生影响。当i=2时，应改写规则A：：=Sd,

因为S::=AaIb,所以A：：=AadIbd,

S：：=AaIb|^|

A：：=AcIAadIbdI

消除关于A的直接左递归即可。该文法没有多余的规则。■

42

§4.2自顶向下语法分析性

二、递归子程序分析法—>

一、自顶向下分析方法的问题及其解决办法

1.消除回溯

2.消除左递归

二、递归子程序分析法(递归下降分析法)

1.递归子程序定义

2.递归调用子程序的处理

3.分析实例

4.递归子程序特点

三、LL(1)分析法

1.定义

2.LL(1)分析方法

3.构造分析表

4.LL(1)文法

43

§4.2自顶向下语法分析事

ats

■二、递归子程序分析法一

1.递归子程序定义

一个子程序以直接或间接方式调用本身，称为递归子程序。

如：PASCAL语言中的递归函数就是递归子程序。

44

§4.2自顶向下语法分析4

二、递归子程序分析法

一、自顶向下分析方法的问题及其解决办法

1.消除回溯

2.消除左递归

二、递归子程序分析法(递归下降分析法)

1.递归子程序定义

2.递归调用子程序的处理

3.分析实例

4.递归子程序特点

三、LL(1)分析法

1.定义

2.LL(1)分析方法

3,构造分析表

4.LL(1)文法45

§4.2自顶向下语法分析事

-二、递归子程序分析法一

2.递归调用子程序的处理

⑴处理基本思想

对于递归子滞而用，用栈存放返回地址，当调用该子程序

时，由递归入口子程序将返回地址压入栈中，当返回时，用

递归出口子程序从校中取出返回地址。

(2)构造递归子程序的方法

程序语言的许多语法成分是递归定义的，在对程序语言进行

不带回溯自顶向下语法分析时，就可以采用递归子程序法。

其方法步骤如下：

46

§4.2自顶向下语法分析%

—二、递归子程序分析法一

1)对文法中每个非终结符号U(它们都分别代表一种语法成分)都编出一个

子程序P(U)

2)对于递归出现的非终结符，其相应的子程序中应有递归入口部分(递归入

口子程序，取名SCIN),以便将返回地址压入栈中。此外，还应有

递归出口部分，设此子程序取名SCOUT。以便从地址压入栈中取返

回地址

3)对于规则U：：=x1Ix2|...|xn,可用下列方法构造P(U)

IFchINFRIST(XI)THENP(XI)

ELSEIFchINFIRST(X2)THENP(X2)

ELSE

IFchINFIRST(Xn)THENP(Xn)

ELSE

47

§4.2自顶向下语法分析*

・二、递归子程序分析法—

其中全程变量ch中存放了当前输入字符；ERROR为出错信息，表

示源程序中语法有错。当输入符号遇选择项为翎寸，应该求解左部非

终结符号的Follow集合，并对Follow集合中的每个符号进行判定。

4)对于符号串x=y1y2…ym,如果yi£V「则P(yi)

IFch=yiTHENREAD(ch)ELSE

这就是说，如果当前文法中的符号与输入符号匹配，则继续读入下

一个字符至ch中；否则表明源程序有错。如果yieVN，则P(yi)就

代表调用与yi相应的子程序。

48

§4.2自顶向下语法分析■

二、递归子程序分析法

一、自顶向下分析方法的问题及其解决办法

1.消除回溯

2.消除左递归

二、递归子程序分析法(递归下降分析法)

1.递归子程序定义

2.递归调用子程序的处理

3.分析实例

4.递归子程序特点

三、LL(1)分析法

1.定义

2.LL(1)分析方法

3.构造分析表

4.LL(1)文法49

§4.2自顶向下语法分

-二、递归子程序分析法

3.分析实例

设有文法G[E]■

E::=eBaA^H

A：：=aIbAcB^H

B::=dEdIaC^|

C：：=e|dC|M

此文法共有四个非终结符，并且在规则中都是递归出现，故应该

编写四个相应的递归子程序：P(E)、P(A)、P(B)、

P(C)。在第一次执行前，ch中已存有输入串中首字符。

50

(l)构造递归子程序:

P(E)

E::=eBaASCIN

2I~

(用方法ch=e?」

4))/X

READERROR

P(B)

5I

ch=a?

6X7

READERROR

直

P(A)

SCOUT

51

(D构造递归子程序

P(A)

A::=aIbAc

（用方法3）和4）)

⑴构造递归子程序

P(B)1

B：：=dEdIaC

(用方法3)和4))

SCOUT

53

（2）分析实例

判别字符串eadeaa是否是文法G[E]的句子。

分析步骤从识别符号E开始，扫视字符串

eadeaaeadeaa,设一个全程变量ch用于存放输入串

中的字符。并设一个返回地址栈用于存放返回

地址

ch

TOP->栈底

adeaa子程序P(E)

chSCIN

2

1)开始时，在全程变量ch中存放了输入串中的

首字符e,故分析与识别从符号匕'开始。此时

主程序调用子程序P(E)READERROR

P(B)

TOP5

56

adeaa程序P(E)

chSCIN

2

2)进入P(E)后，执行P(E)子程序，首先通过递归

入口子程序SCIN,将P(E)在主程序中的返回地址

送入返回栈中READERROR

P(B)

5

TOP

57

adeaa子程序P(E)n

chSCIN

2

3)执行P(E)子程序，首先判断ch?=e,现在ch

='曰，接着读入下一个字符。

READERROR

P(B)

5

TOP

58

e|apeaa子程序P(E)n

chSCIN

2

4）读入下一个字符a,即ch=a

READERROR

P(B)

51

TOP

59

edeaa

子程序P(E)1Q

ch

5)P(E)子程序调用子程序P(B),P(B)调用递归入口

子程序SCIN,将P(B)在P(E)中的返回地址(E):5

送入返回栈中

6

READERROR

P(A)

FIT

SCOUT

60

edeaa子程序P(B)1

1SCIN

ch21

ch=d?

6)然后执行子程序P(B),分析ch?=d,现在

不是d,再判定ch?=a,现在ch=a,接着读入7、

READch=a?

下一个字符。

ECX*

T(E)ERRORREAD

主返5r□JL2

ch=d?

P(E)：5P(C)

7、

TOP->ERRORREAD

io|

SCOUT

61

eaeaa子程序P(B)1

SCIN

ch2I

ch=d?

7)读入下一个字符d,即ch=d

READch=a?

41

P(E)ERRORREAD

主返工

ch=d?

P(E)：5P(C)

7、

TOPERRORREAD

io|

SCOUT

eaeaa

ch子程序p（c）「AL

|SCIN

9）接着执行P（C）,分析ch?=e。现在不是字符

e,再接着道1定611?=€1,现在ch=d,接着2

读入下一个字符。

6

ch=d?READ

N

ERROR

71

SCOUT

64

eadaa

ch

10）读入下一个字符e,即ch=e

主返

P(E)：5

P(B):10

TOP->

SCOUT

65

eadaa

eadaa

子程序P(C)1口

ch

e,

67

eade

子程序P(C)

ch1

13)读入下一个字符a,即ch=a

主返

P(E)：5

P(B):10

P(C):7

TOP一SCOUT

68

eade

子程序P(C)

eade

子程序P(C)1口

ch

70

eade

子程序P(C)

ch1

71

eade

子程序P(C)

ch1

71

SCOUT

72

1

eade子程厂Pf：

SCIN

ch