編譯原理第五章：語(yǔ)法分析-自下而上分析

第五章語(yǔ)法分析—自下而上分析5.1自下而上分析的基本問(wèn)題

5.2算符優(yōu)先分析

5.3LR分析法

5.4語(yǔ)法分析器的自動(dòng)生成工具YACC

復(fù)習(xí)題5.1自下而上分析的基本問(wèn)題一．有關(guān)術(shù)語(yǔ)1.短語(yǔ)令G是一個(gè)文法，S是文法的開(kāi)始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有SαA

δ且

Aβ，則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。2.簡(jiǎn)單短語(yǔ)

S是文法G的開(kāi)始符號(hào)，αβδ是文法G的一個(gè)句型，如果有SαAδ且Aβ，則稱β是句型αβδ相對(duì)于規(guī)則A→β的直接短語(yǔ)。3.句柄一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。4.規(guī)范歸約假定α是文法G的一個(gè)句子，我們稱序列αn，αn-1，…,α0是α的一個(gè)規(guī)范歸約，若此序列滿足（1）αn=α（2）α0=S（3）對(duì)任意的i（0<i≤n）αi-1是從αi經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部符號(hào)而得到的。

規(guī)范歸約是關(guān)于α的一個(gè)最右推導(dǎo)的逆過(guò)程。規(guī)范歸約實(shí)質(zhì)：在移進(jìn)過(guò)程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時(shí)就用相應(yīng)產(chǎn)生式的左部符號(hào)進(jìn)行替換。規(guī)范歸約的中心問(wèn)題：如何尋找或確定一個(gè)句型的句柄。例5.1考慮文法E→T|E+TT→F|T*F

F→i|(E)的兩個(gè)句型i1*i2+i3,E+T*F+i的短語(yǔ)，直接短語(yǔ)和句柄解：對(duì)于i1*i2+i3,首先見(jiàn)語(yǔ)法樹(shù)

短語(yǔ)：i1，i2，i3，i1*i2，

i1*i2+i3

直接短語(yǔ)：i1，i2，i3

句柄：i1對(duì)于E+T*F+i,首先見(jiàn)語(yǔ)法樹(shù)短語(yǔ)：E+T*F,T*F,E+T*F+i,i直接短語(yǔ)：T*F,i句柄：T*F二.語(yǔ)法樹(shù)與尋找規(guī)范推導(dǎo)1.語(yǔ)法樹(shù)（語(yǔ)法分析樹(shù)）表示某一句型推導(dǎo)（歸約）過(guò)程的樹(shù)2．舉例有文法G

A→BaD

B→bB|b

D→BaD|d

句型為bbabad

解:ABaD

bBaD

bbaD

bbaBaD

bbabaD

bbabad3．語(yǔ)法樹(shù)性質(zhì)和有關(guān)結(jié)論（1）每個(gè)句型都有一棵語(yǔ)法樹(shù)（2）每棵語(yǔ)法樹(shù)葉子組成一個(gè)句型（3）每棵子樹(shù)的葉子組成一個(gè)短語(yǔ)（4）每棵簡(jiǎn)單子樹(shù)（只有單層分支）的葉子組成直接短語(yǔ)（5）最左簡(jiǎn)單子樹(shù)葉子組成一個(gè)句柄（6）用語(yǔ)法樹(shù)可以證明每一個(gè)句子一定有一個(gè)規(guī)范推導(dǎo)（剪枝法）4．剪枝法尋找規(guī)范推導(dǎo)方法：（1）找出句子的一個(gè)推導(dǎo)，并畫(huà)出語(yǔ)法樹(shù)（2）用語(yǔ)法樹(shù)（保留樹(shù)根剪去簡(jiǎn)單子樹(shù)的葉子）剪枝法得多個(gè)語(yǔ)法樹(shù)（3）用性質(zhì)（2）構(gòu)造句型（4）用規(guī)范推導(dǎo)定義驗(yàn)證（最右推導(dǎo)）

三．符號(hào)棧的使用（移進(jìn)—?dú)w約）（移進(jìn)歸約接受出錯(cuò)）

1．工作原理分析開(kāi)始時(shí)符號(hào)棧輸入串

#ω#

分析工作過(guò)程：自左至右把輸入串ω的符號(hào)一一移進(jìn)符號(hào)棧里，一旦發(fā)現(xiàn)棧頂形成一個(gè)可歸約串時(shí)，就把這個(gè)串用相應(yīng)的歸約符號(hào)代替，持續(xù)多次，直至不再出現(xiàn)可歸約串為止，然后繼續(xù)移進(jìn)符號(hào)，重復(fù)整個(gè)過(guò)程。直至分析結(jié)束形成符號(hào)棧輸入串

#S#分析成功，否則串ω含語(yǔ)法錯(cuò)誤2．舉例:對(duì)于文法GE→T|E+TT→F|T*F

F→i|(E)對(duì)輸入串i1*i2+i3的分析解：步驟符號(hào)棧輸入串動(dòng)作

0#i1*i2+i3#預(yù)備

1#i1*i2+i3#移進(jìn)

2#F*i2+i3#歸約F→i3#T*i2+i3#歸約T→F4#T*i2+i3#移進(jìn)

5#T*i2+i3#移進(jìn)

6#T*F+i3#歸約F→i

7#T+i3#歸約T→T*F8#E+i3#歸約E→T9#E+i3#移進(jìn)

10#E+i3#移進(jìn)

11#E+F#歸約F→i12#E+T#歸約T→F13#E#歸約E→E+T14#E#接受5.2算符優(yōu)先分析

算符優(yōu)先分析過(guò)程是自下而上的歸約過(guò)程，但不是一種規(guī)范歸約法。算符優(yōu)先分析就是定義算符之間（終結(jié)符之間）的某種優(yōu)先關(guān)系，借助于這種優(yōu)先關(guān)系尋找“可歸約串”和進(jìn)行歸約。一、算符文法和算符優(yōu)先文法1.算符文法一個(gè)文法，若它的任何一個(gè)產(chǎn)生式右部都不含兩個(gè)相繼（并列）的非終結(jié)符，即不含如下形式的產(chǎn)生式的右部：…QR…,則稱該文法為算符文法。2.算符優(yōu)先文法假定G是一個(gè)不含ε產(chǎn)生式的算符文法，對(duì)于任何一對(duì)終結(jié)符a,b至多只滿足三種關(guān)系之一a>b,a=b,a<b,則稱G是一個(gè)算符優(yōu)先文法。

(1)a=b當(dāng)且僅當(dāng)文法中含有形如P→…ab…,或P→…aQb…的產(chǎn)生式；

(2)a<b當(dāng)且僅當(dāng)文法G中含有形如P→…aR…的產(chǎn)生式而Rb…或RQb…；

(3)a>b當(dāng)且僅當(dāng)文法G中含有形如P→…Rb…的產(chǎn)生式而R…a或R…aQ

注:a>bb<aa=bb=aa<b,b<ca<c3．算符優(yōu)先文法的判別

①是算符文法

②構(gòu)造文法優(yōu)先關(guān)系表

③每個(gè)格子至多出現(xiàn)<，=，>之一，則為算符優(yōu)先文法二．算符優(yōu)先文法優(yōu)先關(guān)系表的構(gòu)造1．構(gòu)造FIRSTVT和LASTVTFIRSTVT(P)={a|Pa…或PQa…,a∈VT,Q∈VN}

LASTVT(P)={a|P

…a或P…aQ,a∈VT,Q∈VN}(1) 構(gòu)造FIRSTVT(P)1.若有產(chǎn)生式P→a…或P→Qa…，則a∈FIRSTVT(P)；2.若有a∈FIRSTVT(Q)，且有產(chǎn)生式P→Q…，則a∈FIRSTVT(P)3.重復(fù)2,直至文法G中所有P∈VN的FIRSTVT(P)不再擴(kuò)大(2) 構(gòu)造LASTVT(Q)1.若有產(chǎn)生式P→…a或P→…aQ，則a∈LASTVT(P)2.若a∈LASTVT(Q)，且有產(chǎn)生式P→…Q，則a∈LASTVT(P)；3.重復(fù)2，直至文法G中所有P∈VN的LASTVT(P)不再擴(kuò)大例：對(duì)于文法G：E’→#E#E→E+T|TT→T*F|FF→P↑F|P

P→(E)|i

求FIRSTVT（R）和LASTVT(R)。2.構(gòu)造優(yōu)先關(guān)系表

FOR每條產(chǎn)生式P→X1X2…..XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均為VTTHEN置Xi=Xi+1IFi≤n-2且Xi和Xi+2

均為VT

但Xi+1∈VNTHEN置Xi=Xi+2IFXi∈VT

而Xi+1∈VNTHENFORFIRSTVT(Xi+1)中的每個(gè)a,DO置Xi<a;IFXi∈VN

且Xi+1∈VTTHENFORLASTVT(Xi)中的每個(gè)a置a>Xi+1END例：對(duì)于文法G：E’→#E#構(gòu)造其算符優(yōu)先關(guān)系表。

E→E+T|TT→T*F|FF→P↑F|P

P→(E)|i

解：三、算符優(yōu)先分析算法1． 素短語(yǔ)（1）短語(yǔ):S是文法G的開(kāi)始符號(hào)，αβδ是文法G的一個(gè)句型。若有SαAδ且Aβ，則β是αβδ相對(duì)于A∈VN的短語(yǔ)。（2）素短語(yǔ)：至少含有一個(gè)終結(jié)符，并且除它自身之外不再含任何更小的素短語(yǔ)。至少含有一個(gè)終結(jié)符的最小短語(yǔ)。（3）最左素短語(yǔ)：處于句型最左邊的那個(gè)素短語(yǔ)。（4）最左素短語(yǔ)與句柄

i）最左素短語(yǔ)不一定是句柄

ii）若文法沒(méi)有單非終結(jié)符產(chǎn)生式A→B，則句柄是最左素短語(yǔ)例：對(duì)文法G:E→E+T|TT→T*F|FF→P↑F|P

P→(E)|i

中句型P*P+i,求短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)、最左素短語(yǔ)解：短語(yǔ)P1，P2，P*P，i，P*P+i

直接短語(yǔ)P1，P2，i

句柄P1

素短語(yǔ)P*P，i

最左素短語(yǔ)P*P2.定理一個(gè)算符優(yōu)先文法G的任何句型#N1a1N2a2……NnanNn+1#的最左素短語(yǔ)是滿足如下條件的最左子串Njaj……NiaiNi+1,aj-1<aj,aj=aj+1,……,ai-1=ai,ai>ai+1，算符優(yōu)先文法G的句型中的可歸約串就是最左素短語(yǔ)。3.算符優(yōu)先分析算法使用一個(gè)符號(hào)棧S，存放終結(jié)符、非終結(jié)符。K代表符號(hào)棧S使用深度。S[K]表示棧頂，a表示讀入字符。S[j]表示終結(jié)符棧頂，j表示終結(jié)符棧頂指針?biāo)惴ㄈ缦拢篵egink:=1;s[k]:=”#”;j:=1;a:=“”;輸入串尾:=”#”;Q:=“”;REPEAT{找最左素短語(yǔ)的尾并輸入進(jìn)棧}

把下一個(gè)輸入符號(hào)讀入a中；

IFS[k]∈VTTHENj:=kELSEj:=k-1;WHILES[j]>aDOBEGINREPEATQ:=S[j];IFS[j-1]∈VTTHENj:=j-1ELSEj:=j-2;UNTILS[j]<Q;

把S[j+1]…..S[k]歸約為某個(gè)N；

k:=j+1;S[k]:=NENDOFWHILE;IFS[j]<aORS[j]=aTHENBEGINk:=k+1;S[k]:=aENDELSEERRORUNTILa=”#”例：文法G：E’→#E#,E→E+T|T,T→T*F|F,

F→P↑F|P,P→(E)|i對(duì)于句子i*i+i語(yǔ)法分析的過(guò)程解:分析步驟如下：

棧S#串i*i+i#動(dòng)作

#i*i+i#移進(jìn)

#N*i+i#歸約

#N*i+i#移進(jìn)

#N*i+i#移進(jìn)

#N*N+i#歸約

#N+i#歸約

#N+i#移進(jìn)

#N+i#移進(jìn)

#N+N#歸約

#N#接受

四、優(yōu)先函數(shù)節(jié)省存儲(chǔ)空間便于執(zhí)行比較運(yùn)算從優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)方法1．對(duì)于每個(gè)終結(jié)符a（包括#），令其對(duì)應(yīng)兩個(gè)符號(hào)fa和ga，畫(huà)一張以所有符號(hào)fa和ga為結(jié)點(diǎn)的方向圖。若a>=b，則從fa畫(huà)一箭弧到gb。如果a<=b，則畫(huà)一條從gb到fa的箭弧。2．對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn)（包括出發(fā)結(jié)點(diǎn)自身在內(nèi)）的個(gè)數(shù)，則賦給fa的數(shù)作為f(a)，賦給gb的數(shù)作為g(b)。3．檢查所構(gòu)造出來(lái)的函數(shù)f和g,看它們同原來(lái)的關(guān)系表是否有矛盾，若無(wú)矛盾，則f和g就是所要的優(yōu)先函數(shù)，若有矛盾就不存在優(yōu)先函數(shù)。布置實(shí)驗(yàn)三解：構(gòu)造過(guò)程：作業(yè)：P13335.3LR分析法一、LR分析器二、LR（0）項(xiàng)目集族和LR（0）分析表的構(gòu)造三、SLR分析表的構(gòu)造四、規(guī)范LR分析表的構(gòu)造五、LALR分析表的構(gòu)造六、二義文法的應(yīng)用5.3LR分析法

LR分析法：L表示從左到右掃描輸入串，R表示構(gòu)造一個(gè)最右推導(dǎo)的逆過(guò)程。能用LR分析器分析的文法類，包含能用LL（1）分析器分析的全部文法類，LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)其中的任何錯(cuò)誤，并能準(zhǔn)確地指出出錯(cuò)位置。一、LR分析器1．LR分析器組成

①總控（驅(qū)動(dòng)）程序

②分析表LR（0）表簡(jiǎn)單LR表（SLR表）規(guī)范LR表（LR（1）表）向前LR表（LALR表）2．LR分析方法的基本思想

記住歷史、展望未來(lái)、定奪現(xiàn)在在規(guī)范歸約過(guò)程中，一方面記住已移進(jìn)和歸約的整個(gè)符號(hào)串，即記住“歷史”，另一方面根據(jù)所用產(chǎn)生式推測(cè)未來(lái)可能碰到的輸入符號(hào)，即對(duì)未來(lái)進(jìn)行“展望”。根據(jù)“歷史”，“展望”以及現(xiàn)實(shí)輸入符號(hào)三方面材料，來(lái)確定棧頂?shù)姆?hào)是否構(gòu)成相對(duì)某一產(chǎn)生式的句柄。3．LR分析器結(jié)構(gòu)一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器(棧)的確定有限狀態(tài)自動(dòng)機(jī)(1) 分析表與棧①棧用來(lái)存放狀態(tài)和移進(jìn)歸約的符號(hào)串（s0，#）為分析開(kāi)始前預(yù)先放到棧里的初始狀態(tài)和句子括號(hào)，sm表?xiàng)ｍ敔顟B(tài)，X1X2……Xm是至今已移進(jìn)歸約出的部分②分析表-------LR分析器的核心部分動(dòng)作表ACTION[s,a]s面臨a采取的動(dòng)作狀態(tài)轉(zhuǎn)換表GOTO[s,X]s面對(duì)X(X∈VT∪VN)時(shí)下一狀態(tài)是什么

ACTION[s,a]規(guī)定動(dòng)作有四種移進(jìn)、歸約、接受、報(bào)錯(cuò)1．移進(jìn)把(s,a)的下一狀態(tài)s’=GOTO[s,a]和輸入符號(hào)a入棧，下一符號(hào)變成現(xiàn)行輸入符號(hào)2．歸約指用某一產(chǎn)生式A→β進(jìn)行歸約。若β長(zhǎng)度為r，歸約動(dòng)作是A。去除棧頂r項(xiàng)，使?fàn)顟B(tài)sm-r變成棧頂狀態(tài)，然后把(sm-r,A)的下一狀態(tài)s’=GOTO[sm-r,A]和文法符號(hào)A進(jìn)棧。歸約動(dòng)作不改變現(xiàn)行輸入符號(hào)。執(zhí)行歸約動(dòng)作意味著β=(Xm-r+1…..Xm)呈現(xiàn)于棧頂而且是一個(gè)相對(duì)于A的句柄。3．接受宣布分析成功，停止分析器的工作4．報(bào)錯(cuò)發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序(2)分析過(guò)程一個(gè)LR分析器工作過(guò)程可看成是棧里的狀態(tài)序列,已歸約串和輸入串所構(gòu)成的三元式的變化過(guò)程初始三元式(s0,#,a1a2……an#)

中間三元式(s0s1s2….sm,#X1X2….Xm,aiai+1….an#)

變化后的三元式由棧頂狀態(tài)sm和現(xiàn)行輸入符號(hào)ai唯一決定,ACTION[sm,ai]所規(guī)定的動(dòng)作ACTION[sm,ai]所規(guī)定的動(dòng)作：(i)若ACTION[sm,ai]為移進(jìn),且s=GOTO[sm,ai],,則三元式變?yōu)?s0s1s2….sms,#X1X2….Xmai,ai+1….an#)(ii)若ACTION[sm,ai]={A→β},則按A→β進(jìn)行歸約,則三元式變?yōu)?s0s1s2….sm-rs,#X1X2….Xm-rA,aiai+1….an#)，其中s=GOTO[sm-r,A],r=|β|，β=Xm-r+1……Xm(iii)若ACTION[sm,ai]為”接受”,三元式不再變化,分析成功

(iv)若ACTION[sm,ai]為”報(bào)錯(cuò)”,三元式變化過(guò)程終止,報(bào)告錯(cuò)誤LR文法

(1)LR文法對(duì)于一個(gè)文法,如果能夠構(gòu)造一張分析表,使得它的每個(gè)入口均是唯一確定的,稱這個(gè)文法為L(zhǎng)R文法.(2)LR(k)文法一個(gè)文法,如果能用一個(gè)每步頂多向前檢查k個(gè)輸入符號(hào)的LR分析器進(jìn)行分析,則這個(gè)文法為L(zhǎng)R(k)文法

(3)有關(guān)LR文法的幾個(gè)結(jié)論①LR文法肯定是無(wú)二義的,一個(gè)二義文法決不是LR的②存在不是LR的上下文無(wú)關(guān)文法③對(duì)于一個(gè)LR文法,當(dāng)分析器對(duì)輸入串進(jìn)行自左至右掃描時(shí),一旦句柄呈現(xiàn)于棧頂,就能及時(shí)對(duì)它進(jìn)行歸約.④LR方法比預(yù)測(cè)法更加一般化.二、LR（0）項(xiàng)目集族和LR（0）分析表的構(gòu)造1．LR（0）項(xiàng)目（1）前綴、活前綴

字的前綴：該字的任意首部如abc的前綴為ε,a,ab,abc

活前綴：規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)，在右邊增添一些終結(jié)符號(hào)之后就可以使它成為一個(gè)規(guī)范句型。在LR分析工作過(guò)程中的任何時(shí)候，棧里的文法符號(hào)（自棧底而上）X1X2….Xm應(yīng)構(gòu)成活前綴，把輸入串剩余部分配上之后應(yīng)成為規(guī)范句型（如果整個(gè)輸入串確實(shí)構(gòu)成一個(gè)句子）對(duì)于一個(gè)文法G可構(gòu)造一個(gè)有限自動(dòng)機(jī)，它能識(shí)別G的所有活前綴。

規(guī)范句型：用最右推導(dǎo)導(dǎo)出的句型（右句型）（2）LR（0）項(xiàng)目文法G的每一個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)稱為G的一個(gè)LR（0）項(xiàng)目。如產(chǎn)生式A→XYZ，對(duì)應(yīng)項(xiàng)目有A→·XYZ

A→X·YZ

A→XY·Z

A→XYZ·

產(chǎn)生式A→ε，只對(duì)應(yīng)一個(gè)項(xiàng)目

A→·例：文法G：S’→E的LR（0）項(xiàng)目

E→aA|bB

A→cA|d

B→cB|d解：1S’→·E10A→d·2S’→E·11E→·bB3E→·aA12E→b·B4E→a·A13E→bB·5E→aA·14B→·cB6A→·cA15B→c·B7A→c·A16B→cB·8A→cA·17B→·d9A→·d18B→d·(3)由項(xiàng)目狀態(tài)構(gòu)造NFA以及確定化、最少化可以使用項(xiàng)目狀態(tài)構(gòu)造一個(gè)NFA，用來(lái)識(shí)別這個(gè)文法的所有活前綴①找出初態(tài)（唯一），其它為終態(tài)（活前綴識(shí)別態(tài)）②若狀態(tài)i和j出自同一產(chǎn)生式，且狀態(tài)j的圈點(diǎn)落后于狀態(tài)i的圈點(diǎn)一個(gè)位置i：X→X1X2……Xi-1·Xi…Xn，

j：X→X1X2……Xi-1Xi·Xi+1…Xn就從狀態(tài)i畫(huà)出一條標(biāo)志為Xi的弧到狀態(tài)j③若狀態(tài)i的圓點(diǎn)后的符號(hào)為非終結(jié)符A，從狀態(tài)i畫(huà)ε弧到所有A→·γ狀態(tài)（即所有那些圓點(diǎn)出現(xiàn)在最左邊的A的項(xiàng)目）(4)項(xiàng)目分類歸約項(xiàng)目A→α·

接受項(xiàng)目S’→α·

移進(jìn)項(xiàng)目A→α·aβ,a∈VT,α,β∈(VN∪VT)*

待約項(xiàng)目A→α·Bβ,B∈VN2、LR（0）項(xiàng)目集規(guī)范族的構(gòu)造

LR（0）項(xiàng)目集規(guī)范族：構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集（狀態(tài)）的全體稱為這個(gè)文法的LR（0）項(xiàng)目集規(guī)范族。（1）拓廣文法（使“接受”狀態(tài)易于識(shí)別）文法G是一個(gè)以S為開(kāi)始符號(hào)的文法，拓廣G為G’（包含整個(gè)G），增加一個(gè)不出現(xiàn)在G中的非終結(jié)符S’，并加進(jìn)一個(gè)新產(chǎn)生式S’→S。S’為G’的開(kāi)始符號(hào)，稱G’為G的拓廣文法。（2）定義和構(gòu)造I的閉包CLOSURE（I）

I是文法G’的任一項(xiàng)目集①I(mǎi)的任何項(xiàng)目都屬于CLOSURE(I)；②

若A→α?Bβ∈CLOSURE（I），那么，對(duì)于任何關(guān)于B的產(chǎn)生式B→γ，項(xiàng)目B→?

γ也屬于CLOSURE（I）；③重復(fù)執(zhí)行上述兩步驟直至CLOSURE（I）不再增大為止。例：對(duì)文法5.7，若I={S’→?

E}

則CLOSURE（I）所含項(xiàng)目為S’→?EE→?aAE→?bB(3)狀態(tài)轉(zhuǎn)換函數(shù)GO的定義GO（I，X）I是一個(gè)項(xiàng)目集，X∈（VN∪VT）GO（I，X）=CLOSURE（J）其中J={任何形如A→αX?β的項(xiàng)目|A→α?Xβ屬于I}，直觀上說(shuō)：若I是對(duì)某個(gè)活前綴γ有效的項(xiàng)目集，那么GO（I，X）便是對(duì)γX有效的項(xiàng)目集。例：I0

：{S’→?E，E→?aA，E→?bB}GO（I，a）={E→a?A，A→?cA,A→?d}(4)LR(0)項(xiàng)目集規(guī)范族C構(gòu)造算法PROCEDUREITEMSETS（G’）；BEGINC：={CLOSURE（{S’→?S}）}；

REPEATFORC中的每個(gè)項(xiàng)目集I和G’的每個(gè)符號(hào)XDOIFGO（I，X）非空且不屬于CTHEN

把GO（I，X）放入C族中

UNTILC不再增大即：1oCLOSURE（{S’→?S}）C2o

對(duì)C中每個(gè)項(xiàng)目集I和文法G’的每個(gè)符號(hào)X做若GO（I，X）非空且不屬于C，則把GO（I，X）加入C

3o

重復(fù)2o，直至C不再增大為止。轉(zhuǎn)換函數(shù)GO把這些集合聯(lián)接成一張DFA轉(zhuǎn)換圖

3．LR(0)分析表的構(gòu)造

(1)LR(0)文法若一個(gè)文法G的拓廣文法G’的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)（項(xiàng)目集）不存在①既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目；②或含多個(gè)歸約項(xiàng)目，稱G是一個(gè)LR(0)文法。換言之，LR(0)文法規(guī)范族的每個(gè)項(xiàng)目集不包含任何沖突項(xiàng)目。

(2)LR(0)分析表的構(gòu)造假定C={I0，I1，…，In}，令每個(gè)項(xiàng)目集Ik的下標(biāo)k作為分析器的狀態(tài)，令包含項(xiàng)目S’→?

S的集合Ik的下標(biāo)k為分析器的狀態(tài)（初態(tài)）。則分析表的ACTION子表和GOTO子表的構(gòu)造如下：

1o若項(xiàng)目A→α

?

aβ∈Ik

且GO（Ik

,a）=Ij

,

a∈VT

則置ACTION[k,a]為”把(j,a)移進(jìn)?！?簡(jiǎn)記為”sj”.2o若項(xiàng)目A→α

?∈Ik,對(duì)任意a∈VT(包括#),置ACTION[k,a]為用“產(chǎn)生式A→α”進(jìn)行歸約,簡(jiǎn)記為“rj”(假定A→α是文法G’的第j個(gè)產(chǎn)生式)。

3o若項(xiàng)目S’→S?

∈Ik，則置ACTION[k,#]“接受”，簡(jiǎn)記為“acc”。

4o若GO（Ik,A）=Ij

,

A∈VN,則置

GOTO[k,A]=j。

5o

分析表中凡不能用規(guī)則1o-4o填入信息的空白格置“出錯(cuò)”標(biāo)志。

LR(0)表：按上述構(gòu)造的分析表的每個(gè)入口都是唯一的，稱此分析表是一張LR(0)表。LR(0)分析表構(gòu)造舉例例：對(duì)文法G’：（0）S’→E構(gòu)造LR(0)分析表

（1）E→aA

（2）E→bB

（3）A→cA

（4）A→d

（5）B→cB

（6）B→d補(bǔ)1：為下述拓廣文法G’，構(gòu)造LR（0）項(xiàng)目集規(guī)范族，并判斷是否為L(zhǎng)R（0）文法，若是構(gòu)造LR（0）分析表。文法G’：S’→E

E→ωX|xY

X→yX|z

Y→yY|z三、SLR分析表的構(gòu)造有點(diǎn)簡(jiǎn)單“展望”材料的LR分析法，即SLR法。1.引例若一個(gè)LR（0）規(guī)范族中，有如下一個(gè)項(xiàng)目集I，I={X→α·bβ，A→α·，B→α·}存在沖突，若FOLLOW（A）∩FOLLOW（B）=φ且不含b，若I狀態(tài)面臨a時(shí)，可采取如下“移進(jìn)-歸約”決策1o若a=b，則移進(jìn)

2o若a∈FOLLOW（A），則用產(chǎn)生式A→α進(jìn)行歸約3o若a∈FOLLOW（B），則用產(chǎn)生式B→α進(jìn)行歸約4o此外，報(bào)錯(cuò)。

一般而言，若LR（0）項(xiàng)目集規(guī)范族的一個(gè)項(xiàng)目集中含有m個(gè)移進(jìn)項(xiàng)目A1→α?a1β1，A2→α?a2β2，……,Am→α?amβm；同時(shí)含有n個(gè)歸約項(xiàng)目：B1→α?

，B2→α?

，……Bn→α?

，若集合{a1,a2,

……am}，F(xiàn)OLLOW（B1）……FOLLOW（Bn）兩兩不相交，則隱含在I中的動(dòng)作沖突可通過(guò)檢查現(xiàn)行輸入符號(hào)a屬于上述n+1個(gè)集合中的哪個(gè)集合而獲得解決，即1o若a是某個(gè)ai,i=1,2,…m,則移進(jìn)2o若a∈FOLLOW（Bi），i=1,2,…n,則用產(chǎn)生式Bi→α進(jìn)行歸約3o此外，報(bào)錯(cuò)。2.SLR分析表的構(gòu)造（1）文法G拓廣成G’（2）構(gòu)造G’的LR（0）項(xiàng)目集族C和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)GO（3）使用項(xiàng)目集族C和GO函數(shù)構(gòu)造G’的SLR分析表假定C={I0，I1，I2，……，In}，令每個(gè)項(xiàng)目集Ik的下標(biāo)k為分析器的一個(gè)狀態(tài)，含項(xiàng)目S’→S的Ik的下標(biāo)為初態(tài)，構(gòu)造ACTION子表和GOTO子表。1o若項(xiàng)目A→α?aβ∈Ik且GO（Ik,a）=Ij,a∈VT

置ACTION[k,a]為”把狀態(tài)j和符號(hào)a移進(jìn)?！?記為sj2o若項(xiàng)目A→α?∈Ik,對(duì)任意a，a∈FOLLOW（A）,置ACTION[k,a]為“用產(chǎn)生式A→α?進(jìn)行歸約”,記為rj(假定A→α是文法G’的第j個(gè)產(chǎn)生式)。

3o若項(xiàng)目S’→S?∈IK

，則置ACTION[k,#]“接受”，簡(jiǎn)記為”acc”。

4o若GO（Ik,A）=Ij,A∈VN,則置GOTO[k,A]=j.5o分析表中凡不能用規(guī)則1o----4o填入信息的空白格置“出錯(cuò)”標(biāo)志3.LR分析算法（總控程序）輸入：一個(gè)輸入串ω和一張LR分析表輸出：若ω∈L（G），輸出對(duì)于ω的一個(gè)自下而上的分析,否則出錯(cuò)開(kāi)始時(shí)，分析棧頂（s0，#）輸入緩沖區(qū)ω#ip指向輸入串ω#的第一個(gè)輸入符號(hào)while（t=TRUE）dobegin

使s是棧頂狀態(tài)，a是ip指向的符號(hào)

ifaction[s,a]=sjthen/*移進(jìn)*/begin

將a和j壓入分析棧修改ip使其指向下一個(gè)輸入符號(hào)

end;elseifaction[s,a]=rj(A→β)then/*歸約*/

begin

從分析棧頂彈出2×|β|個(gè)符號(hào)（狀態(tài)符號(hào)）令s’是當(dāng)前棧頂狀態(tài)將A和goto[s’,A]壓入分析棧

{輸出產(chǎn)生式A→β}endelseifaction[s,a]=accthenreturn/*成功*/elseerror()/*出錯(cuò)*/

endif;

endif;

endif;endofwhile;end;4.實(shí)例

對(duì)文法G：E→E+T|TT→T*F|FF→（E）|i

構(gòu)造SLR分析表，并分析輸入串i*i+i作業(yè)：考慮文法G：S→（SR|aR→，SR|）

構(gòu)造文法G的LR（0）項(xiàng)目集族，并判斷該文法是否為SLR文法，若是構(gòu)造SLR分析表，若不是請(qǐng)說(shuō)明原因。四、規(guī)范LR分析表的構(gòu)造1.LR（k）項(xiàng)目形如[A→α·β，a1a2……ak]，且A→α·β是一個(gè)LR（0）項(xiàng)目，每一個(gè)ai∈VT.(1≤i≤k),則該項(xiàng)目為L(zhǎng)R（k）項(xiàng)目。其中a1a2……ak稱為它的向前搜索符串（展望串）。向前搜索符串僅對(duì)歸約項(xiàng)目[A→α·

，a1a2……ak]有意義，歸約項(xiàng)目[A→α·

，a1a2……ak]意味著：當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的k個(gè)輸入符號(hào)為a1a2……ak時(shí)，才可以把棧頂上的α歸約為A。2.構(gòu)造有效的LR（1）項(xiàng)目集規(guī)范族及LR（1）分析表的構(gòu)造(1)對(duì)文法進(jìn)行拓廣(2)I的閉包求法假定I是一個(gè)項(xiàng)目集，它的閉包CLOSUER（I）可按如下方式構(gòu)造10I的任何項(xiàng)目都屬于CLOSUER（I）20

若項(xiàng)目[A→α·Bβ，a]∈CLOSUER（I），B→ζ是一個(gè)產(chǎn)生式，那么對(duì)于FIRST（βa）中每一個(gè)終結(jié)符b，如果[B→·ζ，b]，原來(lái)不在CLOSUER（I）中，則把它加進(jìn)去。30

重復(fù)執(zhí)行20

，直至CLOSUER（I）不再增大為止。(3)GO函數(shù)的定義令I(lǐng)是一個(gè)項(xiàng)目集，X是一個(gè)文法符號(hào)，函數(shù)GO（I，X）定義為

GO（I，X）=CLOSUER（J），其中J={任何形如[A→αX·β，a]的項(xiàng)目|[A→α·Xβ，a]∈I}(4)LR（1）項(xiàng)目集規(guī)范族構(gòu)造算法

10C：={CLOSUER（{[S’→·S，#]}）}20

對(duì)C中的每個(gè)項(xiàng)目集I和G’的每個(gè)符號(hào)X做若GO（I，X）非空且不屬于C，則把GO（I，X）加入C中

30重復(fù)20

，直至C不再增大為止。(5)LR（1）分析表的構(gòu)造假定C={I0，I1

，

I2

，…，

In}，令每個(gè)Ik的下標(biāo)k為分析表的狀態(tài)，令那個(gè)含有[S’→·S，#]的Ik的k為分析表的初態(tài)，動(dòng)作ACTION和狀態(tài)轉(zhuǎn)換表GOTO表可構(gòu)造如下：10若項(xiàng)目[A→α·aβ，b]∈Ik且GO（Ik，a）=Ij,a∈VT則置ACTION[k,a]為“把狀態(tài)j和符號(hào)a移進(jìn)?！?。記為sj20

若項(xiàng)目[A→α·

，a]∈Ik

，則置ACTION[k,a]為用產(chǎn)生式A→α歸約。記為rj30若項(xiàng)目[S’→S·

，#]∈Ik，則置ACTION[k,#]為“接受”，記為“acc”.40若GO(Ik

，A)=Ij,則置GOTO[k,A]=j。50凡不能用規(guī)則10——40填入信息的空白欄均填入“出錯(cuò)標(biāo)志”。按上述算法構(gòu)造的分析表，若不存在多重定義入口的情形，則稱它是文法G的一張規(guī)范的LR(1)分析表，具有規(guī)范的LR(1)分析表的文法稱為一個(gè)LR（1）文法。3、實(shí)例對(duì)文法G：S→BB構(gòu)造其LR（1）分析表

B→aB|b解：（1）對(duì)文法G進(jìn)行拓廣成G’0：S’→S1：S→BB2：B→aB3：B→b

（2）求LR（1）項(xiàng)目集族和GO函數(shù)（3）LR（1）分析表構(gòu)造作業(yè):

為下述拓廣文法G’構(gòu)造LR（1）項(xiàng)目集規(guī)范族并判斷它是否為L(zhǎng)R（1）文法，若是構(gòu)造其LR（1）分析表文法G’為S’→EE→E+T|TT→（E）|a五．LALR分析表的構(gòu)造對(duì)于同一文法，LALR分析表和SLR分析表永遠(yuǎn)具有相同數(shù)目的狀態(tài)。1．項(xiàng)目集同心

LALR分析法是處于SLR(1)與LR(1)間的分析方法。（1）兩個(gè)LR（1）項(xiàng)目集具有相同的心，若除去搜索符之后，這兩個(gè)集合是相同的。（2）同心集合并不會(huì)產(chǎn)生“移進(jìn)—?dú)w約”沖突，但可能產(chǎn)生“歸約—?dú)w約”沖突2．LALR分析表構(gòu)造

基本思想：首先構(gòu)造LR（1）項(xiàng)目集族，若不存在沖突，就把同心集合并在一起，若合并后的集族不存在歸約-歸約沖突，就按這個(gè)集族構(gòu)造分析表。(1)對(duì)文法進(jìn)行拓廣(2)構(gòu)造文法G’的LR(1)項(xiàng)目集規(guī)范族記C={I0,I1…In}(3)把所有同心集合并在一起記C’={J0,J1…Jm}為合并后的新族，那個(gè)含有項(xiàng)目[S’→·S,#]的Jk

為分析表的初態(tài)(4)從C’構(gòu)造ACTION表及GOTO表(4)從C’構(gòu)造ACTION表及GOTO表①

若[A→α·aβ，b]∈Jk且GO（Jk，a）=Jj,a∈VT，置ACTION[k,a]為“sj”②若[A→α·