第五章语法自底向上方法

第五章自底向上分析方法主要内容自底向上分析的基本思想简单优先分析方法LR类分析方法基本思想从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文法的开始符。(移入-归约分析)两种分析方法简单优先和LR类分析方法5.1

自底向上语法分析方法介绍例：SaAcBe[1] Ab[2] AAb[3]Bd[4]输入流：abbcde。规范推导过程为：

逆过程:(符号栈，输入流)(-,abbcde)(a,bbcde)(ab,bcde)(aA,bcde)(aAb,cde)(aA,cde)(aAc,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-)SaAcBe[1]

aAcd[4]e[1]

aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]5.2简单优先分析一种shift-reduce分析方法根据文法符号的优先关系确定句柄文法符号的优先关系的确定简单优先分析中的三种关系XY：当且仅当存在一个产生式A→…XY…X⊲Y：当且仅当存在一个产生式A→…XB…

并有B+Y…。X⊳Y：当且仅当存在一个产生式A→…BC…

并有B+…X，C*Y…。

文法G为简单优先文法如果满足：

对于任意两个语法符号X和Y，至多成立一种优先关系；

任意两个产生式都具有不同的右部。文法优先关系的确定

FIRST(W)={S|W+S…，S(VNVT)}LAST(W)={S|W+…S，S(VNVT)}若有U…SiSj…:则有Si

Sj;若有U…SiW…:任SjFIRST(W),有Si⊲Sj若有U…VW…:任SiLAST(V),

Sj(FIRST(W){W})则有Si⊳Sj

输入流的开始和结束标志‘＃’，文法的开始符为Z，SFIRST(Z),有#⊲S，;且＃⊲ZSLAST(Z)，有S⊳

#，;且Z⊳＃优先关系矩阵一个文法的全部优先关系可以用矩阵来表示，称作优先关系矩阵。

例：

ZbMbMaM(LLMa)#)a(bLMZ#)a(bLMZ)a

L)bM(aa(bLMZFIRST

LAST⊲⊲⊳⊳⊳⊲⊲⊲⊳⊳⊳⊳⊳⊲⊲定理： 设X1…XiXi+1…Xj…Xn是一个句型，若有 Xi

⊲Xi+1

Xi+2

…Xj-1Xj

⊳Xj+1 则Xi+1Xi+2…Xj-1Xj一定是该句型的简单短语。结论：

⊲用来确定句柄的头；用来确定句柄的内部；⊳用来确定句柄的结束。简单优先分析算法要点找第一个使Sj⊳Sj+1的Sj。从Sj开始往前(左)找第一个使Si-1⊲Si的Si。用SiSi+1…Sj去查产生式的右部，并用相应的左部符号代替句柄SiSi+1…Sj

(归约)。重复上述过程，直至输入符结束。如果归约出文法的开始符号则成功。否则失败。简单优先分析实例符号栈关系输入流#⊲

b(aa)b##b⊲(aa)b##b(⊲aa)b##b(a⊳a)b##b(M

a)b##b(Ma)b##b(Ma)⊳b##b(L⊳b##bMb##bMb⊳##Z⊳#规范句型：用最右推导导出的句型(也称右句型）。规范前缀：若存在规范句型，且是终极符串或空串，则称为规范前缀。规范活前缀：若规范前缀不含句柄或含一个句柄并且具有形式=(是句柄)，则称规范前缀为规范活前缀(简称活前缀）。归约规范活前缀：若活前缀是含句柄的活前缀，即有=，且是句柄，则称活前缀为归约规范活前缀（简称归约活前缀）。5.3LR类分析方法活前缀的描述性定义：形成可归前缀之前，包括可归前缀在内所有规范句型的前缀都称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。线性正则式状态机－LRSM线性正则式：不含*符号的正则表达式LRSM：(LinearRegularStatesMachine) (1)从LRSM可构造出恰好接受给定所有正则式的确定自动机DA； (2)从LRSM的终止状态可判定接受的是哪个正则式； (3)从LRSM的状态可判定一个正则式是不是另一正则式的前缀。

项目：假设[P]是一个正则式，则我们称形如[P]的表示为项目，其中P是正则式编号。其中黑点可出现于任何位置上。项目集：用IS表示IS(X)：SubItems(IS,X)={X[P]|X[P]IS,XSymbSet}简记为IS(X)

假设有线性正则项集:IS={abd[1],abc[2],bc[3],de[4],dec[5]},

则有：IS(a)={abd[1],abc[2]}IS(b) ={bc[3]}IS(c)={dec[4]}线性正则式到LRSM的构造给定正则式集{1,2,…n}：■构造初始项目集IS0={1[1],...,n[n]}，并给IS0标上NO(表示未处理）。■从已构造的LRSM部分图选择被标为NO的任一项目集ISi，并做下面动作：[1]对每个符号XSymbSet：若ISiX非空，给ISiX标上NO，并在ISi和ISiX之间画有向X边:ISi

→

ISiX。[2]给ISi标上OK。■

重复上述步骤二，直至在LRSM中没有被标记为NO的状态（项目集）节点为止。abdcdbecd•abc[1]•abd[2]•ad[3]•bec[4]•bed[5]S0a•bc[1]a•bd[2]a•d[3]S1=S0aab•c[1]ab•d[2]S3b•ec[4]b•ed[5]S2be•c[4]be•d[5]S5abc•[1]S6abd•[2]S7ad•[3]S4bec•[4]S8bed•[5]S9正则式到LRSM的转换例LRSM的性质展望符：Lookup(S)有效前缀集

Prefix(S)状态Si中的项目•[P]表示部分已被输入，而且是Si的前缀的后缀，表示待输入部分。可构造接受给定正则式集合的DA严格前缀：某状态中既含有定位点在尾处的项目又含有定位点不在尾处的项目，则一个正则式是另一个正则式的严格前缀。派生定理

开始符产生式的右部是归约活前缀。如果A是归约活前缀，且A→是产生式，则也是归约活前缀。任何归约活前缀，都可按上述方式被派生。设文法开始符的产生式是： S→1|2|…|n

RPSG={1,…,n}{|ARPSG,A→P}识别规约活前缀的LRSM的构造

例有文法G[S]: S→aAc[1] A→Abb[2] A→b[3]

可归前缀集：

aAcaAbbabLR(0)项目：若A→是产生式，则称A→为LR(0)项目(简称项目），也写作[p]形式。项目集的投影：假设IS是LR(0)项目集，则称下面IS(X)

为IS关于X的投影集：

IS(X)={A→X|A→XIS, X(VTVN)}.项目集的闭包：假设IS是LR(0)项目集，则称下面CLOSURE(IS)为IS的闭包集：

CLOSURE(IS)=IS

{A→|Y→ACLOSURE(IS)A→是产生式}两个重要的性质归约活前缀的性质：若A是归约活前缀，A→是产生式，则也是归约活前缀。活前缀状态机性质：若有

Prefix(ISi

)，且A→ISi

，则

是归约活前缀。若有Prefix(ISi

)，Y→AISi

，则根据性质2—(活前缀状态机的性质），

A是归约活前缀。再根据派生原理，若

A→是A的产生式，则也是归约活前缀。构造LRSM的思想：

如果在状态项目集ISi

中有项目A→B，且B→是B的产生式，则在ISi

中增加项目B→；对于ISi

这个过程继续到不可再扩充为止。

构造LR(0)活前缀状态机LRSM的算法要点

构造初始状态IS0：IS0=CLOSURE({Z→S})，并给IS0标上NO。从已构造的LRSM部分图选择被标为NO的任一状态IS，并做

[1]对每个符号XVTVN，做下面动作：

1)令ISj

=CLOSURE(IS(X))，若非空。2)若在LRSM部分图中已有ISk与ISj有相同项目集，则令m=k；否则构造ISj的状态点ISj，

并给ISj标上NO，同时令m=j。3)在IS和ISm之间画有向X边：IS

ISm

。

[2]给IS标上OK。重复上一步骤，直至没有被标记为NO的状态节点为止。x例：构造LR(0)状态机SE$EE+TETTidT(E)0

S→E$E→E+TE→TT→idT→(E)1

S→E$E→E+T

5

T→id

3

E→E+TT→idT→(E)

4

E→E+T

9

E→T

6

T→(E)E→E+TE→TT→idT→(E)7

T→(E)E→E+T

8

T→(E)

TT(idETid)E+id((GE的LRSM+2

S→E$

$LRSM给出了所有的可归活前缀LRSM中的每个状态将对应一个饱和项目集：

（1）其中一部分是由先驱状态分出来(称为基本项目)；（2）一部分则是由基本项目扩展出来的(称为扩展项目或派生项目)。派生部分项目的特点是其中的“”出现在产生式右部的最左侧。形如A→•[P]的项目称为归约型项目形如A→•[P]的项目称为移入型项目

移入－归约冲突

归约－归约冲突

LRSM不能直接用于LR分析

LRSM提供的信息：（1）合法性检查信息[A→a]

（2）移入/归约信息[A→a]；[A→]

（3）移入/归约后的转向状态信息#X1X2…Xk…XtSi0Si1Si2…Sik…Sitaiai+1…an#移入动作：设Sit的ai输入边所指向的状态为S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*归约动作：设按A→Xk+1Xk+2…Xt进行归约，则首先归约为ASik的A输出边所指向的状态设为S*，则格局变为：#X1X2…XkSi0Si1Si2…SikAS*设当前格局是：#X1X2…XkSi0Si1Si2…SikALR分析模型OutputStack#an…ai…a1LR分析驱动器gotoactionInputStXt……LR(0)分析LR分析表Action矩阵：行代表状态，列代表输入符，而矩阵元素则表示相应的分析动作：Shift/Reduce/Accept/Error。GoTo矩阵：行代表状态，而列则代表语法符号（非终极符，终极符），而矩阵元素则表示移入或归约后的转向状态。定义若IS是一个LR(0)项目集，X是一个文法符号，函数GO（IS,X）定义为 GO（IS,X）=CLOSURE（IS(X)），其中IS(X)为LR(0)项目集IS的投影。

假设ISk为LR(0)项目集，则若AaISk，且GO(ISk,a)=ISi，aVT，则action(ISk,a)=Si，表示把状态ISi和展望符a入栈。若AISk，则对任意aVT{#}，令action(ISk,a)=Rj，其中产生式A的编号为j，表示用编号为j的产生式进行归约。若ZISk，且Z为拓广产生式的左部非终极符，则action(ISk,#)=Accept。若GO(ISk,A)=ISi，AVN，则goto(ISk,A)=i。其它情形，则Error(n)，表示出错标志，也可不填。LR(0)分析表的构造LR(0)分析例文法如下： S→E$ E→E+T|T T→id|(E)$+id()#ETS0S5S619S1S2S3S2AccS3S5S64S4R2

R2R2R2R2R2S5R4R4R4R4R4R4S6S5S679S7S3S8S8R5R5R5R5R5R4S9R3R3R3R3R3R3GoTo表Action表LR(0)驱动程序首先置状态栈、符号栈和输入流的开始格局为： （#S1, #, a1a2…an#），则：若当前格局为（#S1S2…Sn, #X1X2…Xn, aiai+1…an#），且action(Sn,ai)=Sj，aiVT，则ai入符号栈，第j个状态Sj入状态栈。即移入后的格局变为： （#S1S2…SnSj, #X1X2…Xnai, ai+1…an#）若当前格局为（#S1S2…Sn, #X1X2…Xn, aiai+1…an#），且action(ISn,a)=Rj，aVT{#}，则按照第j个产生式进行归约，符号栈和状态栈相应元素退栈，归约后的文法符号入栈。假设第j个产生式为A，k=||(=Xn-k+1…Xn)，则归约后的格局变为： （#S1S2…Sn-kS, #X1X2…Xn-kA, aiai+1…an#） 其中S=goto(Sn-k,A)。若状态栈的栈顶状态为Si，输入流当前值为#，且action(Si,#)=Accept，则分析成功。若状态栈的栈顶状态为Si，输入流当前值为a，且action(Si,a)=Error或空，则转向出错处理程序。

LR(0)分析实例状态栈符号栈输入串ActionGoto0id+id$#shift505id+id$#reduce4909T+id$#reduce3101E+id$#shift3013E+id$#shift50135E+id$#reduce440134E+T$#reduce2101E$#shift2012E$#accept

id+id$文法G：Z→aAc[1]

A→bB[2]|ba[3]B→dB[4]|e[5]

构造文法的LR(0)状态机，Action表和

goto表，并给出符号串abdec的LR(0)

分析过程。

SLR(1)分析方法LR(0)分析方法的不足LR(0)方法对文法的要求严格。LR(0)方法容易出现冲突状态。一个文法例:GE:S→E$ [1] E→E+T[2] E→T [3] T→TP[4] T→P [5] P→id [6] P→(E)[7]

图

GE

的LRSM0+EPid$+Pid(TTid(

idE(P)

4

E→T

T→T

P7

P→id

5

E→E+T

T→TP

T→P

P→id

P→(E)

3

T→P

4

S→E$

E→E+T

1S→E$

[1]

E→E+T[2]E→T[3]T→TP[4]T→P[5]P→id[6]P→(E)[7]0T→T

P

P→id

P→(E)8

T→T*P

9

E→E+T

T→T

P

11

P→(E)

E→E+T

12

P→(E)

10P(T

P→(E)

E→E+T

E→T

T→TP

T→P

P→id

P→(E)

678

S→E$

2如果某个状态有如下项目集：{A→

,B→

,D→

d}，则存在着归约-归约，移入-归约冲突若用A→

归约，则当前输入符应在A的Follow集中若用B→

归约，则当前输入符应在B的Follow集若移入，则当前输入符应为d。SLR(1)分析条件LRSM0中存在着状态{A1→1，…，An→n，B1→1

a1r1，…，Bm→

mamrm}则集合： Follow(A1)、…、Follow(An)、{a1,…,am}

两两相交为空SLR(1)分析表的构造假设ISk为LR(0)项目集，则若AaISk，且GO(ISk,a)=ISi，aVT，则action(ISk,a)=Si，表示把状态ISi和展望符a入栈。若AISk，则对任意aVT，aFollow(A)，令action(ISk,a)=Rj，其中产生式A的编号为j，表示用编号为j的产生式进行归约。若ZISk，且Z为拓广产生式的左部非终极符，则action(ISk,#)=Accept。若GO(ISk,A)=ISi，AVN，则goto(ISk,A)=i。其它情形，则Error(n)，表示出错标志，也可不填。

SLR(1)文法定义对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为SLR(1)文法。从定义可以看出SLR(1)分析方法是用LR(0)项目构成的LRSM0来识别活前缀，因此它们的状态数相同，但是，由于LR(0)方法只看状态栈的内容而SLR(1)方法还要向前看展望符，因此SLR(1)文法要比LR（0）文法广。

图

GE

的LRSM0+EPid$+Pid(TTid(

idE(P)

4

E→T

T→T

P7

P→id

5

E→E+T

T→TP

T→P

P→id

P→(E)

3

T→P

4

S→E$

E→E+T

1S→E$

[1]

E→E+T[2]E→T[3]T→TP[4]T→P[5]P→id[6]P→(E)[7]0T→T

P

P→id

P→(E)8

T→T*P

9

E→E+T

T→T

P

11

P→(E)

E→E+T

12

P→(E)

10P(T

P→(E)

E→E+T

E→T

T→TP

T→P

P→id

P→(E)

678

S→E$

2Follow(S)={#}Follow(E)={$,+,)}Follow(T)={$,+,),*}Follow(P)={$,+,),*}#＋id()$ETP0S5S61741S3S22Acc3S5S61144R5R5R5R55R6R6R6R66S5S612747R3S8R3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10StateAction－Lookahead

GoToSLR(1)驱动器初始格局(#S0, #, a1a2…an#)若当前格局为(#S0S1…Sn, #X1X2…Xn,aiai+1…an#)，则若action(Sn,ai)=Sk，则当前格局变为： (#S0S1…SnSk, #X1X2…Xnai,ai+1…an#)若action(Sn,ai)=Rp，则当前格局变为： (#S0…Sn-kS’,#X1X2…Xn-kA,aiai+1…an#)

其中goto(Sn-k,A)=S’若action(Sn,ai)=Accept，则成功其它情形，出错分析栈符号栈

输入串分析动作转向状态

0idid+id$#S50,5idid+id$#R640,4Pid+id$#R570,7Tid+id$#S80,7,8Tid+id$#S50,7,8,5Tid+id$#R690,7,8,9TP+id$#R470,7T+id$#R310,1E+id$#S30,1,3E+id$#S50,1,3,5E+id$#R640,1,3,4E+P$#R5110,1,3,11E+T$#R210,1E$#S20,1,2E$#AcceptSLR(1)与LR(0)SLR(1)和LR(0)具有相同的状态机LR(0)只看分析栈的内容，不考虑当前输入符SLR(1)考虑输入符，用follow集来解决冲突，因此SLR(1)要比LR(0)分析能力强

括号文法定义如下：Z→S$S→(S)S|

构造该文法的SLR(1)分析表，并给出输入流()()$＃的SLR(1)分析过程。主要内容：

LR(1)分析方法ZEE(L,E)ESLL,ELESidS(S)ZEE(L,E)ESSidS(S)0E(L,E)S(S)LL,ELEE(L,E)ESSidS(S)1ESS(S)2(S状态2存在移入--归约冲突LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。SLR(1)方法简单的把非终极符的follow集做为可归约的依据，并不精确。一个非终极符在不同的位置上出现，它所允许的后继符是不同的。LR(1)针对不同产生式上的非终极符，分别定义其后继符集（展望符集Reducelookup），减少了移入/归约冲突。LR(1)项目：[A→,a]。LR(0)项目及一个VT{#}的展望符集合IS:LR(1)项目集IS(X):IS(X)={[A→X,a]|[A→X,a]IS}CLOSURE(IS)=IS∪{[B→,b]|[A→B,a]CLOSURE(IS),B→是产生式,

bFirst(a)}GO:若IS是一个LR(1)项目集，X是一个文法符号,则

GO（IS,X）=CLOSURE（IS(X)），其中IS(X)为LR(1)项目集IS的投影

LRSM1的构造算法初始项目集：ISS=CLOSURE({[Z→S,{#}]})若所有状态都处理完，则结束选一未处理完状态IS，对所有语法符号X（VTVN

{#}),求ISX,令IS’=CLOSURE(ISX)，若IS’不为空：

若IS’为新状态，则增加ISIS’,把IS’加入LRSM1中；否则为图中某个状态ISj，则在IS和ISj之间增加一条转换边：ISISj转到步骤2XX

非SLR(1)文法：

Z→SS→L=RS→RL→aRL→bR→L

0ZSSL=RSRLaRLbRL###=#=##1ZS#2SL=RRL##6SL=RRLLaRLb####7SL=R#3SR#4Lb=#10LaR#=5LaRRLLaRLb#=#=#=#=11RL#=8LaRRLLaRLb####9RL#12Lb#13LaR#SLabRb=RLRLabaaLRbLR(1)分析表的构造假设ISk为LR(1)项目集则：若[Z,#]ISk，且Z为拓广产生式的左部非终极符，则action(ISk,#)=Accept。若[A,a]ISk，且产生式A的编号为j，则action(ISk,a)=Rj，表示用编号为j的产生式进行归约。若[Aa,b]ISk，且GO(ISk,a)=ISi，aVT，则action(ISk,a)=Si，表示把状态ISi和展望符a入栈。若GO(ISk,A)=ISi，AVN，则goto(ISk,A)=i。其它情形，则Error(n)，表示出错标志，也可不填。

LR(1)文法的定义对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为LR(1)文法。R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62A1321S4S50RLS#=baLR(1)驱动程序LR(1)的驱动程序与SLR(1)的驱动程序是相同的，可共用一个。状态栈符号栈

输入串ActionGoTo0aab=b#S50,5aab=b#S50,5,5aab=b#S40,5,5,4aab=b#R5 110,5,5,11aaL=b#R6 100,5,5,10aaR=b#R4 110,5,11aL=b#R6 100,5,10aR=b#R4 20,2L=b#S60,2,6L=b#S120,2,6,12L=b#R5 90,2,6,9L=L#R6 70,2,6,7L=R#R2 10,1S#A设文法G[S]为： SAS|AaA|b 证明G[S]是LR(1)文法；构造它的LR(1)分析表；给出符号串abab#的分析过程LALR(1)方法它具有SLR(1)的状态数少的优点