若文法G的任何產(chǎn)生式的右部都不含兩個相繼的非終結(jié)符，稱文法為算符文法。即：不含形如：U···VW···的產(chǎn)生式，U、V、W∈VNG1[S]：√S→＃E＃E→E＋T|TT→T*F|FF→P↑F|PP→(E)|iG2[E]：×E→TE’

E’→+TE’|ε§5.3算符優(yōu)先分析法

§5.3.1算符優(yōu)先文法及優(yōu)先表構(gòu)造1.算符文法2.優(yōu)先關(guān)系：設(shè)G是算符文法，不含P→ε產(chǎn)生式,對于任何一對終結(jié)符a，b⑴abG中存在形如：P→···ab···

或P→···aRb···的產(chǎn)生式；⑵a＜.bG中存在形如：P→

···aR···

的產(chǎn)生式，且Rb···

或RQ

b

···

；⑶a.＞bG中存在形如：P→···Ｒｂ···的產(chǎn)生式，且R···a

或R···a

Q；G1[S]：S→＃E＃E→E＋T|TT→T*F|FF→P↑F|PP→(E)|iS→#E#∴#

#

P→(E)∴(

)2)S→#E#E=>E＋T∴#<·＋

E→E＋TT=>T*F∴＋<·*

3)S→#E#E=>E＋T∴＋·>#E→E＋TE=>E＋T∴＋·>＋設(shè)有算符文法G，如果其任意兩個終結(jié)符號之間，最多只有一種算符優(yōu)先關(guān)系成立，稱G為算符優(yōu)先文法。算符優(yōu)先文法是無二義的。3.算符優(yōu)先文法

4.優(yōu)先表二維表，行標、列標∈VT

，表項：存放優(yōu)先關(guān)系

A[a,b]=‘’ab

A[a,b]=‘＜·’a＜·

b

A[a,b]=‘·＞’

a·＞b

＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.G1[S]：S→＃E＃E→E＋T|TT→T*F|FF→P↑F|PP→(E)|i優(yōu)先表對優(yōu)先關(guān)系：

##()#<·＋＋<·*

＋·>#

＋·>＋沒有優(yōu)先關(guān)系FirstVT(P)={a|Pa…或PQa…a∈VT,

P、Q∈VN}(P推導(dǎo)出的符號串的第一個終結(jié)符構(gòu)成的集合)LastVT(P)={a|P…a或P…aQa∈VT,

P、Q∈VN}(P推導(dǎo)出的符號串的最后一個終結(jié)符構(gòu)成的集合)

6.計算FirstVT集合若有P→a…或P→Qa…，則

a∈FirstVT(P)

若a∈FirstVT(Q)，且P→Q…，則

a∈FirstVT(P)5.定義集合若有P→a…或P→Qa…，則

a∈FirstVT(P)

若a∈FirstVT(Q)，且P→Q…，則

a∈FirstVT(P)For(P∈VN,a∈VT)doF[P,a]=.F.;For(P→a···或P→Qa···)doinsert(P,a);Whilestack非空do{彈出stack棧頂組對(P,a);

R→P···doinsert(R,a);}Procinsert(P,a){ifF[P,a]=.F.then{F[P,a]=.T.；(P,a)入stack；

}}引入：⑴棧stack，存放二元組對(P,a)⑵布爾數(shù)組F,F[P,a]=.T.a∈FirstVT(P)算法：G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i＋*↑i()#S.T.E.T.T.T.F.T.P.T..T.(P,i)P→i(P,()P→(E)(F,↑)F→P↑F(T,*)T→T*F(E,+)E→E+T(S,#)S→#E#For(P∈VN,a∈VT)doF[P,a]=.F.;For(P→a···或P→Qa···)doinsert(P,a);Whilestack非空do{彈出stack棧頂組對(P,a);

R→P···doinsert(R,a);}Procinsert(P,a){ifF[P,a]=.F.then{F[P,a]=.T.；(P,a)入stack；

}}For(P∈VN,a∈VT)doF[P,a]=.F.;For(P→a···或P→Qa···)doinsert(P,a);Whilestack非空do{彈出stack棧頂組對(P,a);

R→P···doinsert(R,a);}Procinsert(P,a){ifF[P,a]=.F.then{F[P,a]=.T.；(P,a)入stack；

}}G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i＋*↑i()#S.T.E.T..T..T..T..T.T.T..T..T..T.F.T..T..T.P.T..T.(P,i)(F,i)(T,i)(E,i)(P,()(P,()(P,()(P,()(F,()(T,()(E,()(F,↑)(F,↑)(F,↑)(F,↑)(F,↑)(F,↑)(F,↑)(T,↑)(E,↑)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(E,*)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(S,#)(S,#)(S,#)(S,#)(S,#)(S,#)(S,#)(S,#)(S,#)(S,#)G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|iFirstVT(S)={#}FirstVT(E)={+,*,↑,(,i}FirstVT(T)={*,↑,(,i}FirstVT(F)={↑,(,i}FirstVT(P)={(,i}＋*↑i()#S.T.E.T..T..T..T..T.T.T..T..T..T.F.T..T..T.P.T..T.求FirstVT：F[P,a]=.T.a∈FirstVT(P)布爾數(shù)組F若有P→…a或P→…aQ

則

a∈LastVT(P)

若a∈LastVT(Q),且P→…Q,則

a∈LastVT(P)算法：與計算FirstVT集合類似G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|iLastVT(S)={#}

LastVT(E)={+,*,↑,i,)}

LastVT(T)={*,↑,i,)}

LastVT(F)={↑,i,)}

LastVT(P)={i,)}7.計算LastVT集合For(A→X1X2…

XN)doFori:=1ToN－1do{if(Xi∈VT)and(Xi+1∈VT)

then

XiXi+1;if(Xi∈VT)and(Xi+1∈VN)and(Xi+2∈VT)

then

XiXi+2;if(Xi∈VT)and(Xi+1∈VN)

then{b∈FirstVT(Xi+1)Xi<·b;}if(Xi∈VN)and(Xi+1∈VT)

then{a∈LastVT(Xi)a

·>

Xi+1

;}}8.構(gòu)造優(yōu)先表算法S→#E#

#

#

#<·(b∈FirstVT(E))(a∈LastVT(E))·>#2)E→E＋T(a∈LastVT(E))·>＋

＋<·(b∈FirstVT(T))3)E→T不影響＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|iXFirstVTLastVTS{#}{#}E{+,*,↑,(,i}{+,*,↑,i,)}T{*,↑,(,i}{*,↑,i,)}F{↑,(,i}{↑,i,)}P{(,i}{i,)}＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|iXFirstVTLastVTS{#}{#}E{+,*,↑,(,i}{+,*,↑,i,)}T{*,↑,(,i}{*,↑,i,)}F{↑,(,i}{↑,i,)}P{(,i}{i,)}4)T→T*F(a∈LastVT(T))·>

**<·(b∈FirstVT(F))5)T→F不影響6)F→P↑F(a∈LastVT(P))·>↑↑<·(b∈FirstVT(F))＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.7)F→P不影響8)P→(E)

()

(<·(b∈FirstVT(E))(a∈LastVT(E))·>)9)P→i不影響G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|iXFirstVTLastVTS{#}{#}E{+,*,↑,(,i}{+,*,↑,i,)}T{*,↑,(,i}{*,↑,i,)}F{↑,(,i}{↑,i,)}P{(,i}{i,)}短語：令G[S]是一文法，αβδ是文法G的一個句型；如果有：SαAδ，且Aβ；

稱β是句型αβδ相對于非終結(jié)符A的短語。2.素短語：一種短語，它至少包含一個終結(jié)符，且除自身外不再包含更小的素短語。3.最左素短語：處于句型最左邊的素短語。算符優(yōu)先分析法的可歸約串——最左素短語?！?.3.2算符優(yōu)先分析算法句型：P1*(P2)+P3短語：P1,P2,(P2),P1*(P2),P3,P1*(P2)+P3

素短語：(P2)最左素短語：(P2)G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i語法樹PTE+FTEFP3*FTP1)E(FTP2短語：P1,P2,P1*P2,P3,P4,P3*P4,

P1*P2+P3*P4素短語：P1*P2,P3*P4最左素短語：P1*P2句型：P1*P2+P3*P4語法樹P2TE+TEF*FTP1P4F*FTP3G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i若句型為：#N1a1N2a2...Nn

anNn+1#Ni∈VN∪{ε},

ai

∈VT最左素短語是滿足下列條件的最左子串

Nj

aj

Nj+1aj+1

...…Ni-1ai-1

Niai

Ni+11)aj-1＜.

aj

2)3)ai

.＞ai+1aj

aj+1...ai-1

ai

S……………aj-1ai+1…A………………Nj

aj…

Niai

Ni+1

4.定理找出句型中的最左素短語，選擇一條合適的產(chǎn)生式，將最左素短語歸約為該產(chǎn)生式的左部符號。重復(fù)上述過程，直至句型中只存在一個符號，并且是非終結(jié)符號，則輸入串是句子。選用合適產(chǎn)生式的標準：最左素短語x1x2…

xn

,

產(chǎn)生式右部y1y2…

yn若：xi∈VT

則yi∈VT

且

xi＝y(tǒng)i

若：xi∈VN

則yi∈VN

(但可以

xi≠yi

）即：終結(jié)符必須位置匹配且為同一符號；

非終結(jié)符必須位置匹配。5.算符優(yōu)先分析算法k=1;S[k]=‘#’;repeat

把下一個單詞讀進a;if(S[k]∈VT)thenj=kelsej=k-1;while(S[j]·>a)do/*可歸約*/{repeat/*找最左素短語的左端終結(jié)符號*/Q:=S[j];if(S[j-1]∈VT)thenj=j-1elsej=j-2;untilS[j]<·Q;

把S[j+1]S[j+2]…S[k]歸約為某個N;K=j+1;S[k]=N;}if(S[j]<·a)or(S[j]a)then{k=k+1;S[k]=a}elseerror;Untila=‘#’步驟棧x輸入串動作備注產(chǎn)生式012345###

i

#P#P*#P*i##i#*ii*i+i#i*i+i#*i+i#*i+i#i+i#+i#預(yù)備移進歸約移進移進歸約#<·ii·>*#<·**<·ii·>+P→iP→i輸入串：i*i+i設(shè)：x=最靠近棧頂?shù)腣T

＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i歸約序列：

i*i+i<=

P*i+i<=P*P+i步驟棧x輸入串動作備注產(chǎn)生式67891011#P*P#T#T+#T+i#T+P#E*#+i+#+i#

+i#i####歸約移進移進歸約歸約*·>+#<·++<·ii·>#+·>#T→T*FP→iE→E+T歸約序列：i*i+i<=P*i+i<=P*P+i<=T+i<=T+P<=E√輸入串：i*i+i設(shè)：x=最靠近棧頂?shù)腣T

＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i算符優(yōu)先分析法，語法樹≠分析樹省去了Q<=P的歸約步驟，所以歸約效率高。6.分析樹歸約序列：i*i+i<=P*i+i<=P*P+i<=T+i<=T+P<=E⑷⑸⑴⑵⑶i*i+iPi+iPP*ii+iPP*iTi+PP*iPiTi+PP*iPiTEPTE+TEF*FTPPFiii語法樹用兩個離散函數(shù)f,g來代表優(yōu)先表，

f(a),g(a)的函數(shù)值為自然數(shù)，其中：a∈VT；要求：⑴若a＜.b則f(a)<g(b)⑵若ab則f(a)=g(b)⑶若a.＞b則f(a)>g(b)f(a)—入棧優(yōu)先函數(shù)(a位于左邊時的函數(shù)值)g(a)—出棧優(yōu)先函數(shù)(a位于右邊時的函數(shù)值)§5.3.2優(yōu)先函數(shù)1.優(yōu)先函數(shù)表示方法優(yōu)先表＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.G[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i優(yōu)先函數(shù)＋*↑i()#f2458080g1377700輸入串：i*iG[S]：S→#E#E→E+T|TT→T*F|FF→P↑F|PP→(E)|i歸約序列：

i*i<=

P*i<=P*P<=

T√優(yōu)先函數(shù)＋*↑i()#f2458080g1377700步驟棧a輸入串bf(a)g(b)動作產(chǎn)生式01234567###i#P#P*#P*i#P*P#T##i#*i*#i*i#i*i#*i#*i#i####i**i##080484733700預(yù)備移進歸約移進移進歸約歸約P→iP→iT→T*F設(shè)：a=最靠近棧頂?shù)腣T

⑴優(yōu)先函數(shù)比優(yōu)先表節(jié)省空間（N2=>2*N）⑵運算方便，優(yōu)先關(guān)系比較=>自然數(shù)比較aba.＞baaf(a)=g(a)—⑴baf(b)=g(a)—⑵a.>

bf(a)>g(b)—⑶bbf(b)=g(b)—⑷f(a)＞

g(b)＝f(b)＝g(a)＝f(a)即：f(a)>f(a)矛盾

⑶

⑷

⑵

⑴2.優(yōu)先函數(shù)優(yōu)點3.優(yōu)先函數(shù)缺點⑴優(yōu)先關(guān)系與優(yōu)先函數(shù)不是一一對應(yīng)關(guān)系。（算符優(yōu)先文法，但不存在優(yōu)先函數(shù)）⑵信息的丟失：兩個終結(jié)符號之間可能存在4種關(guān)系

(大于，小于，等于，無關(guān)），引入優(yōu)先函數(shù)后，只有3種關(guān)系（大于，小于，等于）。使得原來不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于與自然數(shù)對應(yīng)，變得可比較了。當發(fā)生錯誤時不能準確指出錯誤位置。＋*↑i()#…i.＞.＞.＞.＞.＞…＋*↑i()#f2458080g1377700用優(yōu)先關(guān)系：兩個相鄰i沒有優(yōu)先關(guān)系，報錯。用優(yōu)先函數(shù)：f(i)=8,g(i)=7,相當于i.>i歸約成NN時才發(fā)現(xiàn)錯誤。

例：ii

⑴結(jié)點：fa

，

ga

，a∈VT，

共有2n個結(jié)點。⑵如果a.>b或ab，則畫從fa

到gb

的有向邊；如果a<.b或ab，則畫從gb

到fa

的有向邊；⑶f(a)=從fa出發(fā)沿弧可到達的不重復(fù)結(jié)點個數(shù)（包括自己）。

g(a)=從ga出發(fā)沿弧可到達的不重復(fù)結(jié)點個數(shù)（包括自己）。⑷檢查構(gòu)造出的函數(shù)，與原來的優(yōu)先關(guān)系是否矛盾，若不矛盾，就是所需的優(yōu)先函數(shù)；若矛盾，不存在優(yōu)先函數(shù)。4.構(gòu)造優(yōu)先函數(shù)—作圖法例：表達式文法，取子集：VT={＋,i,#

}f+可達結(jié)點={f+,

g+,

f#,

g#}fi可達結(jié)點={fi

,

g+,

f#,

g#}f#可達結(jié)點={f#,

g#}g+可達結(jié)點={g+,

f#,

g#}gi可達結(jié)點={gi

,

f+,

g+,

f#,

g#}g#可達結(jié)點={g#,

f#}優(yōu)先函數(shù)＋i#f442g352優(yōu)先表＋i#＋.＞＜..＞i.＞.＞#＜.＜.fig+f+f#gig#優(yōu)先函數(shù)＋i#f442g352優(yōu)先表＋i#＋.＞＜..＞i.＞.＞#＜.＜.abf(a)g(b)+.＞+4>3+＜.i4<5+.＞#4>2i.＞+4>3i.＞#4>2#＜.+2<3#＜.i2<5##2=2∴優(yōu)先函數(shù)存在，本組函數(shù)可行。可選函數(shù)組2：＋i#f220g130驗證：作業(yè)：P133第3題說明：為簡單起見，不加#號

LR分析器=

總控程序（對所有的LR分析器，相同）

+分析表（ACTION表+GOTO表）

+分析棧（狀態(tài)棧+符號棧）

輸入串：a+b…#輸出Smxm……S1x1S0#狀態(tài)棧符號?？偪爻绦蚍治霰鞟CTIONGOTO§5.4LR分析法介紹不同文法、不同LR分析器，分析表不同⑴動作部分ACTION——二維數(shù)組

ACTION[S,y]當狀態(tài)為S，向前看符號串y時，應(yīng)該采取的動作。(y的長度=1或k)si：將狀態(tài)

i

以及當前符號分別移入狀態(tài)棧、符號棧；rj：按照第

j

個產(chǎn)生式，對棧頂?shù)姆柎M行歸約；Acc：接受輸入符號串，識別出是一個句子；報錯：輸入符號串不是句子；⑵狀態(tài)轉(zhuǎn)換部分GOTO——二維數(shù)組

GOTO[S,P]當前狀態(tài)S,面對非終結(jié)符號P時,轉(zhuǎn)換到的下一個狀態(tài)。LR分析表書P101,LR分析表ACTION表GOTO表狀態(tài)i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1r1r110r3r3r3r311r5r5r5r5G[E]：1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)6.F→iSi:移入i=>狀態(tài)棧a=>符號棧輸入前移0=>狀態(tài)棧，#=>符號棧LR分析器標準分析算法開始S＝棧頂狀態(tài)號；a＝輸入符號執(zhí)行ACTION[S,a]Accept分析成功空白出錯rj:按第j條產(chǎn)生式歸約L=候選式長度;P=左部符號狀態(tài)棧彈出L個狀態(tài)；符號棧彈出L個符號；Go[新棧頂,P]=>狀態(tài)棧；P=>符號棧結(jié)束狀態(tài)棧符號棧輸入A[S,a]規(guī)則G[S,P]0#i*i+i#預(yù)備05#i*i+i#s503#F*i+i#r6F→i302#T*i+i#r4T→F2027#T*i+i#s70275#T*i+i#s502710#T*F+i#r6F→i1002#T+i#r3T→T*F201#E+i#r2E→T1016#E+i#s60165#E+i#s50163#E+F#r6F→i30169#E+T#r4T→F901#E#r1E→E+T101#E#AccG[E]：1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)6.F→iACTION表GOTO表i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1r1r110r3r3r3r311r5r5r5r5LR分析表

例：i*i+i最右推導(dǎo)：E=>E+T=>E+F=>E+i=>T+i=>T*F+i=>T*i+i=>F*i+i=>i*i+iLR分析法—優(yōu)點LR分析法—缺點1)、手工實現(xiàn)工作量大2)、分析表占用空間大1)、適用于大多數(shù)上下文無關(guān)文法2)、分析效率高3)、報錯及時4)、可以自動生成，如：YACC分析表種類的不同，對應(yīng)不同的LR分析器。分析表特點語法分析器SLR(簡單LR表)構(gòu)造簡單,最易實現(xiàn)；具有較高的實用價值。SLR分析器LR(規(guī)范LR表)適用文法類最大；分析表體積太大，目前實用價值小。LALR(超前LR表)適用的文法、實現(xiàn)上難易程度介于上述兩者之間。LALR分析器例：YACCLR分析表種類⑴字的前綴：字的任意首部。如：abc的前綴有：，a，ab，abc。⑵可歸前綴：是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。若：αδβ是句型，δ為句柄，則αδ為可歸前綴。⑶活前綴：可歸前綴的任意首部。因此，只要輸入串的已掃描部分保持可規(guī)約成一個活前綴，則意味著掃描過的部分沒有錯誤。LR(0)項目集族的構(gòu)造文法G[S]：

S→EE→aA|bB

A→cA|d

B→cB|d

產(chǎn)生式序號

0123456

項目:1.S→·E

2.S→E·

（

S→E）3.E→·aA

4.E→a·A

5.E→aA·

（

E→aA

）6.A→·cA

7.A→c·A

8.A→cA·

（

A→cA

）

9.A→·d

10.A→d·

（

A→d

）

11.E→·bB

12.E→b·B

13.E→bB·

（E→bB

）14.B→·cB

15.B→c·B

16.B→cB·

（B→cB

）17.B→·d

18.B→d·

（

B→d

）

⑷

項目：在文法G的每個產(chǎn)生式右部添加一個圓點，就成為G的一個LR(0)項目。根據(jù)圓點所在的位置和圓點后的符號，把項目分為四種：移進項目，形如A→

?

a

a∈VT

如：3，6，9，11等待約項目，形如A→

?

BB∈VN如：1，4，7，12等歸約項目，形如A→

?如：2，5，8，10等接受項目，形如

S’→S

?如：2項目:1.S→·E

2.S→E·

3.E→·aA

4.E→a·A

5.E→aA·

6.A→·cA

7.A→c·A

8.A→cA·

9.A→·d

10.A→d·

11.E→·bB

12.E→b·B

13.E→bB·

14.B→·cB

15.B→c·B

16.B→cB·

17.B→·d

18.B→d·⑷構(gòu)造識別活前綴的NFA

1).狀態(tài)：每一個項目對應(yīng)一個狀態(tài)；

2).定義文法G[S]的拓廣文法G[S’]，增加S’S，并令項目S’?S

為初態(tài)，S’S?

稱為接受項目；

3).定義狀態(tài)轉(zhuǎn)換弧，

若狀態(tài)i為：XX1…Xi-1·XiXi+1

…Xn

，狀態(tài)j為：XX1…Xi-1Xi·Xi+1…Xn

，則從狀態(tài)i畫一條標志為Xi的有向邊到狀態(tài)j；

若狀態(tài)i為X·A

，A∈VN，則從狀態(tài)i

畫一條

邊到所有狀態(tài)A·

。識別活前綴的NFA1.S→·E2.S→E·3.E→·aA4.E→a·A5.E→aA·6.A→·cA7.A→c·A8.A→cA·9.A→·d10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B16.B→cB·17.B→·d18.B→d·狀態(tài)轉(zhuǎn)換弧

狀態(tài)i：X…Xi-1·Xi…

狀態(tài)j：X…Xi·Xi+1…

從i畫標志為Xi的有向邊到j(luò)

若狀態(tài)i為X·A，A∈VN

從i畫邊到所有狀態(tài)A·678910453121112131415161817aAEbBBcAcdd⑸將NFA確定化，得到識別活前綴的DFA0:S→·E

E→·aA

E→·bB

4:A→c·A

A→·cA

A→·d

2:E→a·A

A→·cAA→·d1:S→E·3:E→b·B

B→·cBB→·d5:B→c·B

B→·cBB→·d11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBAB歸約項目LR(0)分析表的構(gòu)造假若一個文法G的拓廣文法G，識別活前綴的DFA中，每個狀態(tài)(項目集)不存在下述情況：

1)既含移進項目，又含歸約項目；

{A→

?

a，A→

?}移進-歸約沖突

2)含有多個歸約項目

{

A→·，B→·}歸約-歸約沖突則稱G是一個LR(0)文法。若I是文法G的項目集，定義I的閉包CLOSURE(I)：a)I的項目都在CLOSURE(I)中

b)若A→

?

B屬于CLOSURE(I)，則每一形如B→?

的項目也屬于CLOSURE(I)

c)重復(fù)b)直到CLOSURE(I)不再擴大定義轉(zhuǎn)換函數(shù)：

GO（I，X）=CLOSURE（J）

其中：I為項目集，X為一文法符號

J={任何形如A→X

?

的項目|A→

?

X屬于I}分析表的ACTION和GOTO子表構(gòu)造方法：⑴.若項目[A→·a]∈Ik，且GO(Ik,a)＝Ij，a∈VT，則：ACTION[k,a]=“sj”。⑵.若項目[A→·]∈Ik，對a∈VT∪{#}，

ACTION[k,a]=“rj”(設(shè)A→

是文法G的第j個產(chǎn)生式)。⑶.若項目[S→S·]∈Ik，則：ACTION[k,#]=“acc”。⑷.若GO(Ik,A)＝Ij，A∈VN，則：GOTO[k,A]=“j”。⑸.其他填上“報錯標志”。0:S→·EE→·aAE→·bB

4:A→c·AA→·cAA→·d

2:E→a·AA→·cAA→·d1:S→E·3:E→b·BB→·cBB→·d5:B→c·BB→·cBB→·d

11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBABLR(0)分析表為ACTIONGOTO狀態(tài)abcd#EAB0s2s311acc2s4s1063s5s1174s4s1085s5s1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6產(chǎn)生式：0.S→E1.E→aA2.E→bB3.A→cA4.A→d5.B→cB6.B→d在出現(xiàn)移進-歸約沖突，或歸約-歸約沖突時，通過觀察當前輸入符號、非終結(jié)符的后跟符號集，來確定動作。若LR(0)規(guī)范族中含有如下狀態(tài)：

I＝{X→·b，A→·，B→·}，其中，F(xiàn)OLLOW(A)∩FOLLOW(B)＝，且不包含b，SLR(1)分析法移進-歸約沖突歸約-歸約沖突那么，當狀態(tài)I面臨輸入符號a時，若a=b，則移進；若aFOLLOW(A)，用產(chǎn)生式A→進行歸約；若aFOLLOW(B)，用產(chǎn)生式B→進行歸約；此外，報錯。沖突性動作的這種解決辦法叫做SLR(1)解決辦法。該文法的LR(0)項目集規(guī)范族為：I0:S→·E E→·E+TE→·T T→·T*FT→·T*FT→·FF→·(E)F→·iI1:S→E·

E→E·+TI2:E→T·

T→T·*FI3:T→F·I4:F→(·E)