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

第五章語法分析—自下而上分析5.1自下而上分析的基本問題

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

5.3LR分析法

5.4語法分析器的自動生成工具YACC

復習題5.1自下而上分析的基本問題一．有關術語1.短語令G是一個文法，S是文法的開始符號，假定αβδ是文法G的一個句型，如果有SαA

δ且

Aβ，則稱β是句型αβδ相對于非終結符A的短語。2.簡單短語

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

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

F→i|(E)的兩個句型i1*i2+i3,E+T*F+i的短語，直接短語和句柄解：對于i1*i2+i3,首先見語法樹

短語：i1，i2，i3，i1*i2，

i1*i2+i3

直接短語：i1，i2，i3

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

A→BaD

B→bB|b

D→BaD|d

句型為bbabad

解:ABaD

bBaD

bbaD

bbaBaD

bbabaD

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

三．符號棧的使用（移進—歸約）（移進歸約接受出錯）

1．工作原理分析開始時符號棧輸入串

#ω#

分析工作過程：自左至右把輸入串ω的符號一一移進符號棧里，一旦發(fā)現棧頂形成一個可歸約串時，就把這個串用相應的歸約符號代替，持續(xù)多次，直至不再出現可歸約串為止，然后繼續(xù)移進符號，重復整個過程。直至分析結束形成符號棧輸入串

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

F→i|(E)對輸入串i1*i2+i3的分析解：步驟符號棧輸入串動作

0#i1*i2+i3#預備

1#i1*i2+i3#移進

2#F*i2+i3#歸約F→i3#T*i2+i3#歸約T→F4#T*i2+i3#移進

5#T*i2+i3#移進

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

7#T+i3#歸約T→T*F8#E+i3#歸約E→T9#E+i3#移進

10#E+i3#移進

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

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

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

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

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

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

①是算符文法

②構造文法優(yōu)先關系表

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

LASTVT(P)={a|P

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

P→(E)|i

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

FOR每條產生式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)中的每個a,DO置Xi<a;IFXi∈VN

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

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

P→(E)|i

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

i）最左素短語不一定是句柄

ii）若文法沒有單非終結符產生式A→B，則句柄是最左素短語例：對文法G:E→E+T|TT→T*F|FF→P↑F|P

P→(E)|i

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

直接短語P1，P2，i

句柄P1

素短語P*P，i

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

把下一個輸入符號讀入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]歸約為某個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對于句子i*i+i語法分析的過程解:分析步驟如下：

棧S#串i*i+i#動作

#i*i+i#移進

#N*i+i#歸約

#N*i+i#移進

#N*i+i#移進

#N*N+i#歸約

#N+i#歸約

#N+i#移進

#N+i#移進

#N+N#歸約

#N#接受

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

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

①總控（驅動）程序

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

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

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

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

變化后的三元式由棧頂狀態(tài)sm和現行輸入符號ai唯一決定,ACTION[sm,ai]所規(guī)定的動作ACTION[sm,ai]所規(guī)定的動作：(i)若ACTION[sm,ai]為移進,且s=GOTO[sm,ai],,則三元式變?yōu)?s0s1s2….sms,#X1X2….Xmai,ai+1….an#)(ii)若ACTION[sm,ai]={A→β},則按A→β進行歸約,則三元式變?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]為”報錯”,三元式變化過程終止,報告錯誤LR文法

(1)LR文法對于一個文法,如果能夠構造一張分析表,使得它的每個入口均是唯一確定的,稱這個文法為LR文法.(2)LR(k)文法一個文法,如果能用一個每步頂多向前檢查k個輸入符號的LR分析器進行分析,則這個文法為LR(k)文法

(3)有關LR文法的幾個結論①LR文法肯定是無二義的,一個二義文法決不是LR的②存在不是LR的上下文無關文法③對于一個LR文法,當分析器對輸入串進行自左至右掃描時,一旦句柄呈現于棧頂,就能及時對它進行歸約.④LR方法比預測法更加一般化.二、LR（0）項目集族和LR（0）分析表的構造1．LR（0）項目（1）前綴、活前綴

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

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

規(guī)范句型：用最右推導導出的句型（右句型）（2）LR（0）項目文法G的每一個產生式的右部添加一個圓點稱為G的一個LR（0）項目。如產生式A→XYZ，對應項目有A→·XYZ

A→X·YZ

A→XY·Z

A→XYZ·

產生式A→ε，只對應一個項目

A→·例：文法G：S’→E的LR（0）項目

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)由項目狀態(tài)構造NFA以及確定化、最少化可以使用項目狀態(tài)構造一個NFA，用來識別這個文法的所有活前綴①找出初態(tài)（唯一），其它為終態(tài)（活前綴識別態(tài)）②若狀態(tài)i和j出自同一產生式，且狀態(tài)j的圈點落后于狀態(tài)i的圈點一個位置i：X→X1X2……Xi-1·Xi…Xn，

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

接受項目S’→α·

移進項目A→α·aβ,a∈VT,α,β∈(VN∪VT)*

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

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

I是文法G’的任一項目集①I的任何項目都屬于CLOSURE(I)；②

若A→α?Bβ∈CLOSURE（I），那么，對于任何關于B的產生式B→γ，項目B→?

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

E}

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

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

REPEATFORC中的每個項目集I和G’的每個符號XDOIFGO（I，X）非空且不屬于CTHEN

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

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

對C中每個項目集I和文法G’的每個符號X做若GO（I，X）非空且不屬于C，則把GO（I，X）加入C

3o

重復2o，直至C不再增大為止。轉換函數GO把這些集合聯接成一張DFA轉換圖

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

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

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

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

1o若項目A→α

?

aβ∈Ik

且GO（Ik

,a）=Ij

,

a∈VT

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

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

3o若項目S’→S?

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

4o若GO（Ik,A）=Ij

,

A∈VN,則置

GOTO[k,A]=j。

5o

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

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

（1）E→aA

（2）E→bB

（3）A→cA

（4）A→d

（5）B→cB

（6）B→d補1：為下述拓廣文法G’，構造LR（0）項目集規(guī)范族，并判斷是否為LR（0）文法，若是構造LR（0）分析表。文法G’：S’→E

E→ωX|xY

X→yX|z

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

2o若a∈FOLLOW（A），則用產生式A→α進行歸約3o若a∈FOLLOW（B），則用產生式B→α進行歸約4o此外，報錯。

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

，B2→α?

，……Bn→α?

，若集合{a1,a2,

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

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

3o若項目S’→S?∈IK

，則置ACTION[k,#]“接受”，簡記為”acc”。

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

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

ifaction[s,a]=sjthen/*移進*/begin

將a和j壓入分析棧修改ip使其指向下一個輸入符號

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

begin

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

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

endif;

endif;

endif;endofwhile;end;4.實例

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

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

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

，a1a2……ak]有意義，歸約項目[A→α·

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

若項目[A→α·Bβ，a]∈CLOSUER（I），B→ζ是一個產生式，那么對于FIRST（βa）中每一個終結符b，如果[B→·ζ，b]，原來不在CLOSUER（I）中，則把它加進去。30

重復執(zhí)行20

，直至CLOSUER（I）不再增大為止。(3)GO函數的定義令I是一個項目集，X是一個文法符號，函數GO（I，X）定義為

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

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

對C中的每個項目集I和G’的每個符號X做若GO（I，X）非空且不屬于C，則把GO（I，X）加入C中

30重復20

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

，

I2

，…，

In}，令每個Ik的下標k為分析表的狀態(tài)，令那個含有[S’→·S，#]的Ik的k為分析表的初態(tài)，動作ACTION和狀態(tài)轉換表GOTO表可構造如下：10若項目[A→α·aβ，b]∈Ik且GO（Ik，a）=Ij,a∈VT則置ACTION[k,a]為“把狀態(tài)j和符號a移進?！薄Ｓ洖閟j20

若項目[A→α·

，a]∈Ik

，則置ACTION[k,a]為用產生式A→α歸約。記為rj30若項目[S’→S·

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

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

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

（2）求LR（1）項目集族和GO函數（3）LR（1）分析表構造作業(yè):

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

LALR分析法是處于SLR(1)與LR(1)間的分析方法。（1）兩個LR（1）項目集具有相同的心，若除去搜索符之后，這兩個集合是相同的。（2）同心集合并不會產生“移進—歸約”沖突，但可能產生“歸約—歸約”沖突2．LALR分析表構造

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

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

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