gop计算机编译原理课程设计之第五章 自下而上的语法分析

程内

一章概

法分析

上下文无文法及分析

/自上而下的法分析

,自下而上的法分析

•第六章分析

•运行境

•代生成

第5章自

/5.1自下而上的法分析

■5.2LR分析概

■5.3LR(O)目的有自机与LR(O)分析

■5.4SLR(l)分析

・5.5一般的LR(1)

■5.6LALR⑴分析

■5.7法分析器自生成工具YACC

作

2

5.1自

自下而上法分析方

>/\A入符号串始，自左至右逐步行，直至

到文法的始符号。如果能入符号串构造一个

最左，其是一个合法的句子，否它是一个非

法的符号串°

>M入符号串始，以它做法的叶点，自底向

上地构造法。

例：文法G:

S一cAd

A一ab

A—a

采用自下而上的法分析算法入串cabd是

否是文法所定的句子？

5

最右推I

二最右推：在推的任何一步&=6,

其中&、8是句型，都是a中的最右

非符行替。

最右推被称由范推所得的

句型称

6

于文法G[S]

S-^aAcBeA—bA7AbB-^d

,建立入用abbcde的范推：

SraAcBeraAcde「aAbcde「abbcde

自下而上法分师

在分析程序工作的每一步，都是从当前串

中一个子串，将它到某个非符号

,子串称“可串”;

了便于求解法分析算法，我可串

行定：一

8

刻画“可力竟

文法G[S]

句型郊6的短：一

若有S=>*aA6=>+ap6,

«'P'决(VN3T)：

称6是句型以66相于非符人的一

是句型。6台相于非符S的短？

S=>*£5£=>+£«p6e

:任何句型都是其自身相于文法的始符号的短

9

文法G[S]

■句型aBB的

若有S=>*(xA6=a

aP6e(VNuVT)*

称是句型a£台

句型a6台的

句型的最左直接短

10

例5.1:已知文法G[E]:E—E+T|T

T—T*F|F

+

F—(E)|i

求句型i*i+i的短、直接短和句^

T

:iH+i3,i2，

1，

2，

11

第5章自

/5.1自下而上的法分析

/5.2LR分析概

■5.3LR(O)目的有自机与LR(O)分析

■5.4SLR(l)分析

・5.5一般的LR(1)

■5.6LALR⑴分析

■5.7法分析器自生成工具YACC

作

13

5.2LR1

L—法是一有效的自下而上的法分析

技，它能适用于大部分上下文无文法的分

析，一般叫LR（k）分析方法，其中L是指自

左（Left）向右法分析人串，R是指分析

程都是构造最右（Right）推的逆程（

）,括号中的k是指在决定当前分析作向

前右看的个数°

14

有以下原因使得与其它法分析方法相

比，用更广泛，具有更强的吸引力。

⑴用面广：能通LR分析程序所有采用上下

文无文法描述的程序言的法构；

(2)能有效：是最一般的无回溯的移—方法；

(3)容易：LR分析器能及法和准确指出

位置°

15

例5.2考以下文法国造范的法分析程序

要解决的？

S一aSbSIc

回LL(1)?

acbc的范

abe=>aSb

下表出了使用文法串acbc的LR分析

步分析入作

1a移

2$cbcc$移

cbc$

$a$用s

3bc

4$ac$移

b$c

$aS移

5$c$

$aSb用

6$sc

7$aSbc用sasbS

$aSbS接

8受

LR分析算法的

如何（符号）的符号成的符号串是否形成

柄？即何移

分析

1.活前和可前的定

2.求文法中的所有可前

3.可前和活前

4.分析表的构造

18

1-w：

若x,y,z是字母表上的符号串，且z=xy,

是符号串z的（），是符号串z的

（尾），符号用的是指M符号串的尾部

去若干（包括0个）个符号之后所余下的部

分。

19

当前范句型（a03）的句柄是什？

■有文法6网，若S=>*aA3=>a03是文法G

的一个范推peV\coeVT*5AeVN）9

的一个称文法G的一个

称文法G的°

包含句柄的

20

例，于G[S]

S—aAcBeA—bAfAbB-»d

入串:abbcde

范句型当前句柄可前

abbcdebab

aAbcdeAbaAb

aAcdedaAcd

aAcBeaAcBeaAcBe

21

,在文法句型范的程中，自左向右法分析

入用的任何亥IJ,在符号中的符号串均范句

型的活前。

符号人串

$akb>9abbcde$

,如果符号的内容是当前句型的可前，那

已形成当前句型的句柄，行，否U

22

1

如何（符号）的符号成的符号串是

否是

下面是求文法的所有可前的算法：

»方法：任一文法，若已知它有可前xUy,

UeVN9且文法中有生式UTu(xUy=xuy),xu

也是文法的可前。-

》例：拓广文法

(0)S5->S(1)S-^aAcBe

(2)A7b(3)A-»Ab

(4)B―d

24

据拓广文法有：s；S

S当前句型S的句柄，故S可前。

,因S可前，且有生式S-aAcBe,故aAcBe是可

都」

,因V/aAcBe可前，且有生式A->Ab,故aAb是可

刖

,因aAcBe可前，且有生式Arb,故ab是可前

25

,因aAcBe可前，且有生式Bfd,故

aAcd是M前

,因aAb可前，且有生式ATAb,故aAb

是可前（重）「二

,因aAb可前，且有生式A—b,故ab是

可前（重）

26

,因aAcd可前，且有生式A—Ab,故aAb

是可前（重）

/因aAcd可前,且有生式A—b,故ab是

可前（重）

所以文法的可前有：S,aAcBe,aAb,ab,

aAcd

27

可前和活,

文法所有可前所构成的集合，称可

前集。我可以构造出文法活前和

可前的有限自机：

28

符和非符都

看成是有限自机

的人符号°

个

都

可

前

1

。

11

上述有限自机就是文法所有活前和可前

的有限自机。

»中状活前（）；

»所有都是可前的,此分析中形成句柄（

）；

＞星号（*）的状唯一的句子，次到始符号；

4.分析表的构造?

由两部分成，和

⑴作表以一个二数表示，代表状

状，代表当前的，数

元素表示当前状i,而入符号小

,所行的分析作Action[i,aj°

33

入

共有4作：

：新状号状，入符号符；

：用相的生式行；

,接&:当文法符号到只剩下始符号，且

入串束（当前入$）,分析成功；

：当状某一状下，出了不出的

文法符号，°■

35

(2)状表用一个二数表示，列代

表状号，所代表文法符数，

元素表示当前状i面文法符号Xj

,去的新状Goto[i,XJ°

36

■E・

文;

入符

号

a

状

02

1

24

37

作表和状

acc

（1）在控程序的控制下，M左到右理法分析

入串根据分析和入符号的情况，分析表确

定分析作；

⑵分析包括文法符号X[i]和相的状S[i]两

部分（状是指能活前的自机状）°

⑶根据文法所有活前和可前的有限自机

,我可以构造分析表来指移-作；分析

表是LR分析器的核心，它包括作表（Action）

和状表（Goto）两部分；j|

40

第5章自

/5.1自下而上的法分析

/5.2LR分析概

/5.3LR(O)目的有自机与LR(O)分析

■5.4SLR(l)分析

・5.5一般的LR(1)

■5.6LALR⑴分析

■5.7法分析器自生成工具YACC

作

5.3

■LR分析法的主要在于，如何判断活前是可

刖2AO

■可以明一个文法G的所有可前是一个正集

,它可以由DFA加以°

■了由文法G的生式直接构造活前的

DFA,在每个生式的右部串的适当位置插入一

个特殊符号称它是生式的一个目°

1.LR(O)

定：于文法G,其生式的右部添

加一个特殊符号就构成文法的

一个LR(O)目，称°

/若幺一的是生式，其中和是任意

符号串(包括空串)，那就

no

43

例于文法：S'—SS—(S)S|s

有以下LR(O)目：

S—(S.)S

S—tS)・S

S—(S)S.

每个目中点的左部表示在分析程中，要

用生式，句柄已的部分(入符号

),右部表示等待的部分°」

44

2.构造活

根据目的定，我可出文

法中所有生式的目，而每个目都

活前。的一个状。即文法有

多少个目，它所活前的NFA就

有多少个状。

1）NFA的状集：由每个目所的状

成；

2）入字符集合：由文法的文法符号成

包括符、非符和；

3）初：于文法G[S]的拓广文法G[S]有

目S，T.S,由于S，在第一个生式的左

部出，定它初；

4）:于拓广文法G[S]有目Urn.（即

点在最后的目），作NFA的；

46

5)函数f:

若文法中有目i:XTX1…XJI玉…Xn

目j:X^Xp.eXiXi+1...xn

有函数GO(i,Xi)=j

j1)若看，二建函数GO(i,£)=k

目k:%

47

例如：目S—(.S)S的有

ST(・S)S1S|ST(S.)S

SfI|Sf(S)S

考文法：

S'—S(S)SI£的LR(O)目的I

48

例：拓广文法

(0)S-S

⑴S^aAcBe

⑵A->b

(3)A—Ab

(4)Bid

求出其的LR(0)目的NFA

50

S'T.S

上述文法的可前有：？

52

3.构造

■U集范族：每个LR(O)目的集合一个DFA

状，目集的全体称个文法的LR(O)目集范

'族；

■通目集

1.了确保有唯一的接受目，首先拓广文法G

G,引一新的生式S，fS,S，是新增加

的非符作G，的始符°■

2.拓广文法G，一个LR(O)目集合I的

CLOSURE(I)的定女口下：

①I的任何目都属于CLOSURE(I)°

②若A—a.B|3eCLOSURE(I),BeVN,

任何Bf丁eCLOSURE(I)

③重②直至CLOSURE(I)不出新目止

3.I是一个目集，xeVNUVT,

二GO(I9X)的定如下：

GO(I,x)=CLOSURE(J)

其中，J是I入符号x后所到达的

目集,J={A—ax.p|A—>a.x(3eI)

4.基于包函数CLOSURE(I)和移函数GO(I,x)构造

文法活前的DFA的算法如下：

1)令目集DFA的初

2)I是DFA中一个已存在的状(目集)，xeVNUVT,

a)生新的目集作DFA的一个新状

加入DFA的状集，其中，GO(I9X)=

3）重2）直至的DFA的状集中不生新的状（

目集）止；

4）含有目U—U.（即点在最后的目）的目集

，作DFA的°

例：拓广文法

(0)S-S

⑴S^aAcBe

(2)ATb

(3)A—Ab

(4)B-»d

求出其的LR(0)

CLOSURE({S9-».S})

58

SI.S3

•CD

ST.aAcBe@

STaAcBe.

a©

STa.AcBeAS—aA.cBe

AfA.b③

a

bS^aAcBjet

l^^si⑧

A，b.④B-♦(

59

基于LR(O)目集合的DFA构造LR(O)分析

春)：入符号x后到达状，即：

GO(i,x)=j于状i中的目Aia.xB，

若XG置

VT,Action[i,x]=S.J;

若xeVN5置Goto[i,x]=j;

61

(2)于i中的目Ara.,若Ara是G

中第k个生式，

xw,均置Action[»闵=0；

(3)若i中含•置

侨表示入串束符)；

例：文法A-(A)Ia的LR(O)目集合的

----

A—>.(A)IQ)

…(^<U

文法A一(A)la的LR(O)分析表

Ac

5.Lll(C)：：

(i)将入串的左界($)符号和初始状o状

(2)根据状_状i和当前入符号a

Action表行如下工作：

:若Action[i5a]=Sj,当前入符号a符

号，并将入符号所的新的状j状，

法分析入串，即下一个人符号成当

所的人符号.

65

b）:若Action[i,a]=rj,按指定生式行，假

生式右部的符号串度n,

1）符号的n个符号句柄，所以_

2）后的文法符号一一

3）假当前符号j,若Goto[j,A]=k,将后的文法

符号A所的眼服网9；.一（

66

：若作表中“acc”，分析成功；

d），：若作表中空白，告信息。

⑶重以上（2）的工作直到接受或出

止。

考文法的人串（（a））

LR（O）分析算法入串（（a））的分析步如下

67

状S符号X入符号作

10$((a))$S3

203$((a))$S3

3033$((a))$§2

40332$((a))$r2()

50334$((A

603345$((A)

目分的原是根据点所在位置和点之后是符

是非符行的°

1）移二:点之后符的目，A7。.呻，

oc.PeV%aeVT9的状移状；

例如S—aA.cBe

:点之后非符的目，A-a.BB,

，耻V.BeV、，它的状待：状-；1^1

例如STaAc.Be

70

3）S：点之后没有符号（点在最后）的

目，ATQ.aeV%它的快状；例

如：S^aAcBe.

4）接受目:于拓广文法G[S]有目S，TS.

它是一个特殊的目，我称它接受目

,它所的状接受状。

71

1)口集的相容性：我已知，目有4型，在

一个目集(DFA的一个状)中，若能足

下述条件，称目集是相容的目集。

(1)移目和目不并存；一

(2)多个目不并存；

72

2)冲突：目集中含有的目不符合以上两

个条件，称目集中含有冲突。若移

目和目并存，称，

若多,，称冲突。

:若一个文法G的任一目

集中的所有目都是相容的，称文法G

LR(O)文法°

73

第5章自

/5.1自下而上的法分析

/5.2LR分析概

/5.3LR(O)目的有自机与LR(O)分析

/5.4SLR(l)分析

・5.5一般的LR(1)

■5.6LALR⑴分析

■5.7法分析器自生成工具YACC

作

74

5.4SLR⑴分析号

的提出：H

通常的程序言一般不能用LR(O)文

法来描述，即其文法不能足LR(O)文

法的要求°

例如：文法：S'—SS->(S)S|E

的LR(O)目集合的DFA如下：

75

■

若上述文法构造LR(O)分析表,

■从分析表可以：表中Action[]

出了多重定的元素，即冲突。

■于状0,当入“,既要行

又要行移。因而不能做唯一，

从而生冲突。

78

的解决:

LR(O)分析的构造算法行改造，以避免

分析表中分析作的冲突。当分析表出冲

突作，察下一个人符号是什，从而确

/先求Follow（S）={9,于状2,如果要做作

,S之后的下一个人符号可以

'）'或‘$'。（即文法中含有S的句型中，S

之后只能是‘）‘或‘$',而不能含有其他入符

号.・.）・一

/于移ST.（S）S,它所期待的移符号‘（’「

而不碍堪耐符帧°理：当下一个入符

号’（’,做移作，当下一个入符—

号‘）‘和‘$'做作。JM

80

消除冲突的分析表（SLR⑴分析表）：

ActionGoto

庆（）

$S

°S?r2「21

1acc

2S?Lr23

3S4

4Sororo5

51

81

,在文法中，向右看一个符号，所以属于

LR(1)方法。而它只在生冲突才向右看一

个符号，了与普通的LR(1)方法区，它叫

做的LR(1)方法-SLR(l)方法°

ZSLR(1)文法与LR(O)文法其活前目

集合的DFA是一的，

SLR⑴分析表

任意文法G[S]的SLR(l)分析表的构造如下：

(1)状j是状i入符号x后到达的状，即：

GO(i,x)=j于状i中的目A—a.xB,

若置；

xeVT5Action[i9x]=SjJ

若x£VN，置Goto[i,x]=j;

2.于*于一状i中的：A—awi若Afa文法

的第j个生式，，

；]Action^la!>FI

3.若S—>awi,置Action[i,$]=acc（S始符号）；

4.其他情况均置出

于定的文法G,若按上述方法所构造的分析表

不含多重定的元素（无冲突作）°称文法G

SLR（l）文法°■■

84

当且当于任何状i,以下的两个条件均足，

文法SLR(l)文法°

1)于在i中的任何目A7a.x工当x是一个

符，且x在Follow(B)中，i中不存在目

2)于在i中的任何两个目A—a.和

B—P,,Follow(A)nFoliow(B)空。

85

考以下基本算表达式的充文法

（没有括号，只有一运算）：

EC—E

E一E+n

E-n

其活前目集合的DFA如下所示:

86

构造SLR(l)分析表如下：

Follow(E5)={$}Follow(E尸{$,+}

、山ActionGoto

伏L

+n$E

0S21

88

90

第5章自

/5.1自下而上的法分析

/5.2LR分析概

/5.3LR(O)目的有自机与LR(O)分析

/5.4SLR(l)分析

/5.5一般的LR(1)

■5.6LALR⑴分析

■5.7法分析器自生成工具YACC

作

91

55LR

,SLR(l)方法是一用的方法。大多数程序

言基本上都可以用SLR(l)文法来描述°

/在SLR(l)方法中，求出目所的非符号

A的Follow集和移目的移符号集First(P),

只要它不相交就可以解决LR(0)方法中的冲突

但是如果它相交，就无法通SLR(l)分析表

,也就无法行SLR(l)分析。■

92

例如有文法G[S']

(O)S'TS(3)Sfaec

(l)S^aAd(4)STbed

(2)S-»bAc(5)A-»e

dccd

■LR(1)目：在LR(O)目中放置一个向

右搜索符号a,成LR(1)目：

[ATa.隹al

LR(1)分析程中的每个状，就是包含

若干LR(1)目的一个LR(1)目集；

95

响造L1口⑴目集

■目集范族：每个LR(1)目集一个DFA

状，LR(1)目集的全体称个文法的

LR(I)目集范族。

■构造LR(1)目集族的算法似于构造LR(O)

目集族的算法，也需要求两个函数CLOSURE

和GO°

96

I是拓广文法G，的一个LR(1)目集，定和相

造I的包函数CLOSURE(I)如下：

①I的任何目都属于CLOSURE(I)°

b.若[A->oc.BP,a]eCLOSURE(I),BEVN,

任何b]eCLOSURE(I),其中

③重②直至CLOSURE(I)不出新目

I是一个LR(1)目集，xeVNUVT,状移函数

GO(I,x)定如下:

GO(I,x)=CLOSURE(J)

其中J是I入符号x后所到达的

目集，

J={[A7(XX.B,a]I[A-^a.xB,a]e1}

基于包函数和移函数构造文法G的LR(1)目

集的文法活前的DFA,算法如下：

98

1)令DFA的初目集CLOSURE({[S，T.S,$]})

2）I是一个DFA中的状（已存在的目集）,

xeVNUVT,

a)生新的目集CLOSURE。）作DFA的一个新状加

入DFA的状集中：GO（I,x）=CLOSURE（J）

b)同将移函数GO（I,x）=CLOSURED作DFA的函

数。

3）重2）直至DFA中不生新的（目集）止；

4）含有目U7U.（即点在最后的目）的目集，作

DFA的

99

构造文法A-（A）|a的LR（1）目集合

的DFA；

首先展文法：

A'—A

A一（A）

A-a

于文法G[S],其LR⑴分析表的构造：

1.于[Afa.xB,a]e状i,且GO(i,x)=j.

若xeVT9置Action[i9x]=Sj

若x£VN，置Goto[i9x]=j

2.于[A-^a.9a]e状i,若A->a是文法的第j个

生式，置Action[i,a]=r.

J

3.于[S-»a.$]e状i,action[i,$]=acc

4.其它情况置°J

102

根据文法A-(A)|a的LR(1)目集合的

DFA,构造其的LR(1)分析表：

生式号：

(0)AjA

⑴A一(A)

(2)A一a

103

状ActionGoto

)a$A

021

1acc

2S564

3

4S7

5S5$68

6

用LR(1)分析算法入串(a)的分析步

构造下面文法的LR(1)分析表:

(O)E，TE⑴ET(L)(2)E~a

(3)LTL,E(4)LTE

首先构造其LR⑴目的DFA

107

[El.E,$]E[E，7E..]①(O)E—E

[ET.(L).$1a(1)E->(L)

(2)ETa

(3)L—L再

(4)L—E

108

(O)E^E(l)Er(L)

[ET(・L),$](2)E-a(3)L->L,E

(4)L-^E

[LT.EJ]

[LT.L再，][ET(.L),]

[ET.(L),)][LT.L,E,/]

[Efa,][L—.E,/]

LTEr[Ef.(L),/]

•-

LTL,E1[Ef.,/](2)

•’

rET

L•(L,

rEfa1

i•

[E，7E,$1E[E9-»E.$]

⑴

[E-».(L),$I①(0)E~EEf(L)

|E—>.a,$](2)E->a(3)L->L,E

[E.a.$](4)L->E

[LTE.)/,]

[ET(.L),$]E

|L-»L,E,)/,]

[Lr.E)/,|

|E->.(L)

[Efa)|E7(.L)

[L.L,E

[E—a.[L->.E)/,]

[E>(L))/,

[E-»(L.)$]

[Ef.a)/,]笆[Ef(L)J>

[LTL.,E)/,],

sJ

[L-»L,EE

))[LTL,E.)/,]

[E-.(L))/,]

[E-.a)/,][E-»(

[ET(L).$]0

[LTL.,]

J

110

基于DFA构造的LR(1)分析表

(0)EJE

ActionGoto

状(l)E^(L)

EL(2)Efa

0(3)L->L,E

1(4)L―E

254

3

4

5

6510

7

8

911

10

11

12ri

11

第5章自

/5.1自下而上的法分析

/5.2LR分析概

/5.3LR(O)目的有自机与LR(O)分析

/5.4SLR(l)分析

/5.5一般的LR(1)

/5.6LALR⑴分析

■5.7法分析器自生成工具YACC

作

5.6LALR(1.

■R(分析比分析的能力有

明的提高，但是也有缺点：分析

表状数大，使分析的效率降低°解

决二者之的能力与效率之的矛盾，目

前最流行的分析是最佳方案°

113

■LALRf分析(Lookahead-LR)的基

本思想是将LR(1)目集中的同心集合

并，将其小的DFA,若程并未

来新的冲突，分析表可大大地化(状

数与SLR(1),LR(O)的DFA相同)°

114

LALR(l)目集的构造:

同心集：LR(1)

目全部，称两个LR(1)目集具

有相同的心。具有相同心的目集称同

心集。

文法的LR(1)目集范族合并同心集就

得同一文法的LALR(l)目集范族。

合并方法.

(1)相同的心(LR(O)目)不；

(2)合并后目集的搜索符等于合并前

LR(1)目搜索符的并集；

116

合并上述DFA

119

引入合并后的目集后，由同心集出的

弧，改由合并后的目集出，弧上不。

与目集的LR(O)目及文法符号X有

,与搜索符无°

LALR

(1)

DFA

LALR(l)分析表构造与LR⑴构造q

同：

状ActionGoto

A

001

11

22/5