編譯原理語(yǔ)法分析市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

3.4自下而上分析方法3.4.1自下而上分析原理

自下而上分析自左至右掃描輸入串,經(jīng)過(guò)重復(fù)查找當(dāng)前句型句柄,并將找到句柄歸約為對(duì)應(yīng)非終止符,這么逐步歸約,直至文法開始符。即從語(yǔ)法樹末端開始步步向上歸約,直至根結(jié)點(diǎn)。第1頁(yè)自下而上分析法是一個(gè)移進(jìn)-歸約法。分析過(guò)程中采取了一個(gè)FIFO分析棧。分析開始后，把輸入符號(hào)自左至右逐一移進(jìn)分析棧，邊移入邊分析，一旦棧頂符號(hào)串形成句柄就進(jìn)行一次歸約，再繼續(xù)查看棧頂是否形成新句柄，若仍為句柄，則再歸約，如此重復(fù)直至棧頂不是句柄。此時(shí)再繼續(xù)向棧中移進(jìn)后續(xù)輸入符號(hào)。重復(fù)該過(guò)程，直到將整個(gè)輸入串處理完成。若此時(shí)分析棧只有文法開始符，則輸入串是一個(gè)句子，不然輸入串有錯(cuò)。第2頁(yè)下面經(jīng)過(guò)例子說(shuō)明這種分析過(guò)程。文法G[S]：S→aAbBA→c∣AcB→d試對(duì)輸入串a(chǎn)ccbd進(jìn)行分析，檢驗(yàn)該符號(hào)串是否是G[S]一個(gè)句子。假設(shè)“#”為輸入串界符，將輸入串前“#”放入分析棧，接著將輸入串符號(hào)依次進(jìn)棧，詳細(xì)分析過(guò)程以下:第3頁(yè)步驟分析棧句柄輸入串動(dòng)作1#

accbd#移進(jìn)2#a

ccbd#移進(jìn)3#ac

cbd#移進(jìn)4#aAccbd#歸約(用A→c)5#aAc

bd#移進(jìn)6#aAAcbd#歸約(用A→Ac)7#aAb

d#移進(jìn)8#aAbd

#移進(jìn)9#aAbBd#歸約(B→d)10#SaAbB#歸約(S→aAbB)第4頁(yè)SaccbdABA(d)accbdABA(c)accAA(b)acA(a)在自下而上分析過(guò)程中，每一步歸約都可畫出一棵子樹，伴隨歸約完成，這些子樹連成一棵完整分析樹。上述分析過(guò)程可用分析樹表示以下:第5頁(yè)由上述建樹過(guò)程知，自下而上分析過(guò)程每一步歸約都是對(duì)當(dāng)前句型句柄進(jìn)行歸約，即句柄一旦形成總是出現(xiàn)在分析棧棧頂。因?yàn)槊恳徊綒w約都把棧頂符號(hào)串用某產(chǎn)生式左部符號(hào)替換，故把棧頂這么一串符號(hào)稱為可歸約串。上述第6步若不選A→Ac而選A→c進(jìn)行歸約，則無(wú)法歸約到S。怎樣確知棧頂Ac是可歸約串而c不是呢？這需準(zhǔn)確定義“可歸約串”概念。第6頁(yè)若文法G[S]是無(wú)二義文法，則規(guī)范推導(dǎo)逆過(guò)程必是規(guī)范歸約(最左歸約)。對(duì)于移進(jìn)-歸約過(guò)程，句柄最左性和分析棧棧頂相關(guān)。對(duì)于規(guī)范推導(dǎo)所得句型(規(guī)范句型)，句柄后面不會(huì)出現(xiàn)非終止符，故可用句柄刻畫“可歸約串”，規(guī)范歸約實(shí)質(zhì)是在移進(jìn)過(guò)程中當(dāng)棧頂展現(xiàn)句柄時(shí)進(jìn)行歸約。第7頁(yè)為加深對(duì)句柄和歸約等概念了解，用修剪語(yǔ)法樹方法深入說(shuō)明自下而上分析過(guò)程。語(yǔ)法樹一個(gè)子樹由該樹某結(jié)點(diǎn)及其全部子孫組成，子樹全部葉結(jié)點(diǎn)自左至右排列形成一個(gè)相對(duì)于子樹根短語(yǔ)。一個(gè)句型句柄是該句型對(duì)應(yīng)語(yǔ)法樹中最左簡(jiǎn)單子樹全部樹葉自左至右排列。第8頁(yè)可采取修剪語(yǔ)法樹方法實(shí)現(xiàn)歸約，即尋找當(dāng)前語(yǔ)法樹句柄，將句柄中樹葉剪去(歸約)，不停修剪直到只剩根結(jié)點(diǎn)，完成整個(gè)歸約過(guò)程：SaAbBAcdcSaAbBAcdSaAbBdSaAbBS第9頁(yè)至此討論了句柄和規(guī)范歸約這兩個(gè)基本概念，但并沒(méi)有處理規(guī)范歸約問(wèn)題，因?yàn)闆](méi)有給出尋找句柄算法。實(shí)際上，規(guī)范歸約中心問(wèn)題就是怎樣尋找句柄。尋找句柄不一樣算法對(duì)應(yīng)不一樣規(guī)范歸約方法，這一點(diǎn)將在LR分析器中討論。第10頁(yè)算符優(yōu)先分析法是一個(gè)簡(jiǎn)單直觀、廣為使用自下而上分析法，尤其適合于表示式分析且宜于手工實(shí)現(xiàn)。它實(shí)際上是依照表示式四則運(yùn)算過(guò)程來(lái)進(jìn)行語(yǔ)法分析。所謂算符優(yōu)先分析，就是預(yù)先要求運(yùn)算符(確切地說(shuō)是終止符)之間優(yōu)先關(guān)系和結(jié)合性質(zhì)，借助于這種優(yōu)先關(guān)系來(lái)比較相鄰運(yùn)算符優(yōu)先級(jí)，以確定句型可歸約串并進(jìn)行歸約。注意：算符優(yōu)先分析不是規(guī)范歸約。3.4.2算符優(yōu)先分析法第11頁(yè)1.算符優(yōu)先文法

算符文法:若一個(gè)文法任一產(chǎn)生式右部都不含兩個(gè)相繼非終止符，即不含…QR…這么右部，則稱該文法為算符文法。

算符優(yōu)先文法:

算符優(yōu)先文法首先應(yīng)是算符文法,其次還要定義任意兩個(gè)可能相繼出現(xiàn)終止符優(yōu)先關(guān)系。詳細(xì)定義以下:第12頁(yè)假定G是一個(gè)不含ε產(chǎn)生式算符文法,對(duì)任一對(duì)終止符a,b,定義(1)a=b當(dāng)且僅當(dāng)文法G中含有形如P→…ab…或P→…aQb…產(chǎn)生式;(2)a<b當(dāng)且僅當(dāng)G中含有形如P→…aR…產(chǎn)生式，而R

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

aQ。++++第13頁(yè)若一個(gè)算符文法G中任一終止符對(duì)(a,b)

至多滿足下述三種關(guān)系之一:a=b，a<b，a>b則稱文法G是一個(gè)算符優(yōu)先文法。例3.10試說(shuō)明下述文法G是算符文法，但不是算符優(yōu)先文法。E→E+E∣E*E∣(E)∣i解:因?yàn)槲姆℅任一產(chǎn)生式右部都不含兩個(gè)相鄰非終止符，故文法G是算符文法。第14頁(yè)(1)因?yàn)榇嬖贓→E+E，而E+E中第二個(gè)E可推出E*E，故有+<*(2)因?yàn)榇嬖贓→E*E，而E*E中第一個(gè)E可推出E+E，即有+>*可見,運(yùn)算符+和*之間同時(shí)存在兩種不一樣優(yōu)先關(guān)系，故文法G不是算符優(yōu)先文法。第15頁(yè)2.算符優(yōu)先關(guān)系表結(jié)構(gòu)經(jīng)過(guò)檢驗(yàn)文法每個(gè)產(chǎn)生式各個(gè)侯選式,可找出全部滿足a=b終止符對(duì)。為找出全部滿足關(guān)系“<”和“>”終止符對(duì),需先對(duì)文法每個(gè)非終止符P結(jié)構(gòu)兩個(gè)集合FIRSTVT(P)和LASTVT(P):FIRSTVT(P)={a|P?a…或PQa…,a∈VT而Q∈VN｝LASTVT(P)={a|P?…a或P…aQ,a∈VT而Q∈VN｝++++第16頁(yè)FIRSTVT集結(jié)構(gòu)方法：(1)若有產(chǎn)生式P→a…或P→Qa…，則a∈FIRSTVT(P)；(2)若有產(chǎn)生式P→Q…,且a∈FIRSTVT(Q),則a∈FIRSTVT(P)。第17頁(yè)比如試結(jié)構(gòu)文法G[E]FIRSTVT集。G[E]:E→E+T∣T?T→T*F∣F?F→(E)∣i解:①依據(jù)規(guī)則(1)知：由E→E+…得,FIRSTVT(E)={+}；由T→T*…得,FIRSTVT(T)={*}；由F→(…和F→i得,FIRSTVT(F)={(,i}②依據(jù)規(guī)則(2)知：由T→F和FIRSTVT(F)={(,i}得,FIRSTVT(T)={*,(,i}；由E→T和FIRSTVT(T)得,FIRSTVT(E)={+,*,(,i}第18頁(yè)LASTVT集結(jié)構(gòu)方法：(1)若有產(chǎn)生式P→…a或P→…aQ，則a∈LASTVT(P)；(2)若有產(chǎn)生式P→…Q,且a∈LASTVT(Q),則a∈LASTVT(P)。第19頁(yè)比如試結(jié)構(gòu)文法G[E]LASTVT集。G[E]:E→E+T∣T?T→T*F∣F?F→(E)∣i解:①依據(jù)規(guī)則(1)知：由E→…+T得,LASTVT(E)={+}由T→…*F得,LASTVT(T)={*}由F→…)和F→i得,LASTVT(F)={),i}②依據(jù)規(guī)則(2)知：由T→F和LASTVT(F)得,LASTVT(T)={*,),i};由E→T和LASTVT(T)得,LASTVT(E)={+,*,),i}。第20頁(yè)結(jié)構(gòu)優(yōu)先關(guān)系表方法：(1)對(duì)形如P→…ab…或P→…aQb…產(chǎn)生式,有a=b；(2)對(duì)形如P→…aR…產(chǎn)生式,若b∈FIRSTVT(R),則a<b；(3)對(duì)形如P→…Rb…產(chǎn)生式,若a∈LASTVT(R)，則a>b。(4)對(duì)于語(yǔ)句括號(hào)#,有

#=#

#

<FIRSTVT(S)中元素LASTVT(S)中元素>#第21頁(yè)例3.11結(jié)構(gòu)文法G[E]算符優(yōu)先關(guān)系表。G[E]:E→E+T∣T?T→T*F∣F?F→(E)∣i解:結(jié)構(gòu)FIRSTVT集①依據(jù)規(guī)則(1)知：由E→E+…得,FIRSTVT(E)={+}；由T→T*…得,FIRSTVT(T)={*}；由F→(…和F→i得,FIRSTVT(F)={(,i}②依據(jù)規(guī)則(2)知：由T→F和FIRSTVT(F)={(,i}得,FIRSTVT(T)={*,(,i}；由E→T和FIRSTVT(T)得,FIRSTVT(E)={+,*,(,i}第22頁(yè)結(jié)構(gòu)LASTVT集①依據(jù)規(guī)則(1)知：由E→…+T得,LASTVT(E)={+}；由T→…*F得,LASTVT(T)={*}；由F→…)和F→i得,LASTVT(F)={),i}。②依據(jù)規(guī)則(2)知：由T→F和LASTVT(F)得,LASTVT(T)={*,),i};由E→T和LASTVT(T)得,LASTVT(E)={+,*,),i}。第23頁(yè)結(jié)構(gòu)優(yōu)先關(guān)系表①依據(jù)規(guī)則(1),由“(E)”知,(=)。②依據(jù)規(guī)則(2),由E→…+T知,+<FIRSTVT(T),即+<*,+<(,+<i由T→…*F知,*<FIRSTVT(F),即*<(,*<i由F→(E…知,(<FIRSTVT(E),即(<+,(<*,(<(,(<i第24頁(yè)③依據(jù)規(guī)則(3)知：由E→E+…知,LASTVT(E)>+，即+>+，*>+，)>+，i>+由T→T*…知,LASTVT(T)>*，即*>*，)>*，i>*由F→…E)知,LASTVT(E)>)，即+>)，*>)，)>)，i>)④由#E#知,#

=#；

#<FIRSTVT(E),即#<+,#<*,#<(,#<iLASTVT(E)>#,即+>#,*>#,)>#,i>#第25頁(yè)故算術(shù)表示式文法優(yōu)先關(guān)系表以下:

+*i()#+><<<>>*>><<>>i>>

>>(<<<<)>>

>>#<<<<

==第26頁(yè)3.算符優(yōu)先分析算法設(shè)計(jì)因?yàn)樗惴麅?yōu)先分析法僅在終止符之間定義了優(yōu)先關(guān)系而未對(duì)非終止符定義優(yōu)先關(guān)系，這就無(wú)法使用優(yōu)先關(guān)系表去識(shí)別由單個(gè)非終止符組成可歸約串，所以算符優(yōu)先分析法不是用句柄而是用最左素短語(yǔ)來(lái)刻畫“可歸約串”。所謂句型素短語(yǔ)是指這么一個(gè)短語(yǔ),它最少包含一個(gè)終止符且除本身外不再包含其它更小素短語(yǔ)。最左素短語(yǔ)是處于句型最左邊那個(gè)素短語(yǔ)。第27頁(yè)怎樣讓計(jì)算機(jī)尋找最左素短語(yǔ)？算符優(yōu)先文法句型普通形式為#N1a1N2a2…NnanNn+1#其中,ai是終止符,Ni是可有可無(wú)非終止符。算符優(yōu)先文法任一句型最左素短語(yǔ)是滿足下述條件最左子串:NjajNj+1aj+1

…Niai

Ni+1aj-1<aj=aj+1=…=ai

>ai+1第28頁(yè)查找最左素短語(yǔ)方法：(1)最左子串法先找出句型中終止符由左至右滿足aj-1<aj=aj+1=…=ai>ai+1最左子串。再檢驗(yàn)文法每個(gè)候選式,看其是否滿足:全部終止符由左至右排列恰為ajaj+1…ai,即終止符對(duì)應(yīng)相等而非終止符僅對(duì)應(yīng)位置相同。若存在這么候選式,則用該候選式進(jìn)行歸約。第29頁(yè)(2)語(yǔ)法樹法

先畫出句型ω語(yǔ)法樹,再找語(yǔ)法樹中全部相鄰終止符間優(yōu)先關(guān)系。確定相鄰終止符間優(yōu)先關(guān)系標(biāo)準(zhǔn):①語(yǔ)法樹中同層優(yōu)先關(guān)系為“=”;②不一樣層時(shí),層次在下優(yōu)先級(jí)高,層次在上優(yōu)先級(jí)低;③在句型ω兩側(cè)加上語(yǔ)句括號(hào)“#”,則有#<ω和ω>#。

最終按最左素短語(yǔ)必須具備條件確定最左素短語(yǔ)。第30頁(yè)例3.12文法G[E]:E→E+T|TT→T*F|FF→(E)|i試確定F+T*i最左素短語(yǔ)。解:畫句型F+T*i語(yǔ)法樹,依據(jù)語(yǔ)法樹確定相鄰終結(jié)符間優(yōu)先關(guān)系如圖,故最左素短語(yǔ)為i。注意:最左直接短語(yǔ)為FE＋EE*TFTiF#＜＋＜*＜i＞#第31頁(yè)算符優(yōu)先分析算法:

k=1;S[k]=‘#’;//k代表?xiàng)使用深度

do{a=下一個(gè)輸入符;

if(S[k]VT)j=k;elsej=k?1;//j指棧頂終止符

while(S[j]>a){//找最左S[j]<…=…=S[k]>a

do{Q=S[j];//j從最左素短語(yǔ)末逐步移向首

if(S[j?1]∈VT)j=j?1;elsej=j?2;}while(S[j]=Q);把S[j+1]…S[k]歸約為某個(gè)N;

k=j+1;S[k]=N;//把N置于原S[j+1]位置

}if((S[j]<a)||(S[j]=a)){k=k+1;S[k]=a;}elseerror();//若棧頂S[j]<a或=a則將a壓棧

}while(a!=‘#’);第32頁(yè)上述算法工作過(guò)程中,若出現(xiàn)j減1后其值小于等于0,則意味著輸入串有錯(cuò)。正確情況下,算法工作完成時(shí)符號(hào)棧將展現(xiàn)#S#。例3.13文法G[E]及其優(yōu)先關(guān)系如例3.12所表示,試給出輸入串i+i*i算符優(yōu)先分析過(guò)程。解:輸入串i+i*i算符優(yōu)先分析過(guò)程以下:第33頁(yè)符號(hào)棧輸入串動(dòng)作#i+i*i##<i#i+i*i##<i>+,用F→i歸約#F+i*i##<+#F+i*i##<+<i#F+i*i#…+<i>*,用F→i歸約#F+F*i##<+<*#F+F*i##<+<*<i#F+F*i#…*<i>#,用F→i歸約#F+F*F#…+<*>#,用T→T*F歸約#F+T##<+>#,用E→E+T歸約#E##E#結(jié)束第34頁(yè)算符優(yōu)先分析歸約只關(guān)心句型中由左至右終止符序列優(yōu)先關(guān)系,不包括非終止符。再以i+i為例,給出其算符優(yōu)先分析過(guò)程和規(guī)范歸約過(guò)程。算符優(yōu)先分析比規(guī)范歸約要快得多。這既是算符優(yōu)先分析優(yōu)點(diǎn),也是它缺點(diǎn),因?yàn)檫@可能把原來(lái)不成句子輸入串誤認(rèn)為是句子,這種缺點(diǎn)易于填補(bǔ)。第35頁(yè)例3.14試設(shè)計(jì)下述文法算符優(yōu)先分析表:G[S]:S→iBtS∣iBtAeS∣aA→iBtAeS∣aB→b解:首先結(jié)構(gòu)FIRSTVT集和LASTVT集FIRSTVT(S)={i,a};FIRSTVT(A)={i,a};FIRSTVT(B)=;LASTVT(S)={t,e,a};LASTVT(A)={e,a};LASTVT(B)=;

由A→…S知,LASTVT(S)LASTVT(A)即LASTVT(A)={t,e,a}第36頁(yè)然后結(jié)構(gòu)優(yōu)先關(guān)系表:(1)由產(chǎn)生式S→iBtAeS和S→iBtS可知:①由S→iB…得,i<FIRSTVT(B)；②由S→…Bt…得,LASTVT(B)>t；③由S→…tA…得,t<FIRSTVT(A)；④由S→…Ae…得,LASTVT(A)>e；⑤由S→…eS得,e<FIRSTVT(S)；⑥由S→…iBt…得,i=t；⑦由S→…tAe…得,t=e；⑧由S→…tS…得,t<FIRSTVT(S)。(2)因?yàn)榇嬖趖>e和t=e,由iBtAeS知,此時(shí)應(yīng)將iBtAeS同時(shí)歸約為S或A,即取t=e。第37頁(yè)最終得到優(yōu)先關(guān)系表以下:

iteabi

<t<<e<><a

>b

>==第38頁(yè)4.優(yōu)先函數(shù)用優(yōu)先關(guān)系表表示終止符間優(yōu)先關(guān)系時(shí),存放量大,查找費(fèi)時(shí)。若給終止符賦一個(gè)值,值大小反應(yīng)其優(yōu)先關(guān)系,則終止符間優(yōu)先關(guān)系比較就轉(zhuǎn)為值比較。一個(gè)終止符在棧中與在輸入串中優(yōu)先值不一樣,比如,既存在+>),又存在)>+。所以,對(duì)一個(gè)終止符a而言,它應(yīng)該有一個(gè)左優(yōu)先數(shù)f(a)和一個(gè)右優(yōu)先數(shù)g(a)。第39頁(yè)若依據(jù)一個(gè)文法算符優(yōu)先關(guān)系表,使得文法中每個(gè)終止符a和b滿足下述條件:(1)若存在a=b，則有f(a)=g(b)；(2)若存在a>b，則有f(a)＞g(b)；(3)若存在a<b，則有f(a)＜g(b)。則稱f和g為優(yōu)先函數(shù),其中,f稱為入棧優(yōu)先函數(shù),g稱為比較優(yōu)先函數(shù)。第40頁(yè)表中若存在f和g,則有f(a)=g(a);f(a)＞g(b)f(b)=g(a);f(b)=g(b)這將造成以下矛盾:f(a)＞g(b)=f(b)=g(a)=f(a)注意:對(duì)應(yīng)一個(gè)優(yōu)先關(guān)系表優(yōu)先函數(shù)f和g不唯一;若存在一對(duì),則存在無(wú)窮多對(duì);有些優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)。比如,下述優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)。

aba>b===第41頁(yè)依據(jù)優(yōu)先關(guān)系表結(jié)構(gòu)優(yōu)先函數(shù)f和g方法有兩種:關(guān)系圖法、直接結(jié)構(gòu)法(1)用關(guān)系圖法結(jié)構(gòu)優(yōu)先函數(shù)步驟①對(duì)每個(gè)終止符a(包含“#”),令其對(duì)應(yīng)兩個(gè)符號(hào)fa和ga,畫一張以全部fa和ga為結(jié)點(diǎn)方向圖：若a>b或a=b,畫一條從fa到gb有向邊;若a<b或a=b,畫一條從gb到fa有向邊;第42頁(yè)②對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù),此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能抵達(dá)結(jié)點(diǎn)(包含出發(fā)結(jié)點(diǎn)本身)個(gè)數(shù),賦給fa數(shù)作為f(a),賦給gb數(shù)作為g(b);③檢驗(yàn)所結(jié)構(gòu)函數(shù)f和g,看它們同原來(lái)關(guān)系表是否有矛盾。若沒(méi)有矛盾,則f和g就是所要優(yōu)先函數(shù);若有矛盾,則不存在優(yōu)先函數(shù)。第43頁(yè)(2)直接結(jié)構(gòu)法由定義直接結(jié)構(gòu)優(yōu)先函數(shù)步驟:對(duì)每個(gè)終止符a(包含“#”),令f(a)=g(a)=1①若a>b而f(a)≤g(b),則令f(a)=g(b)+1；②若a<b而f(a)≥g(b),則令g(b)=f(a)+1；③若a=b而f(a)≠g(b),則令f(a)=g(b)=max{f(a),g(b)}④重復(fù)①～③步直到過(guò)程收斂。若重復(fù)過(guò)程中有一個(gè)值大于2n,則表明該文法不存在優(yōu)先函數(shù)。第44頁(yè)使用優(yōu)先函數(shù)好處：一是節(jié)約空間；二是便于進(jìn)行比較運(yùn)算。例3.15試用關(guān)系圖法和直接定義法求下述優(yōu)先關(guān)系表優(yōu)先函數(shù)(不含“#”)。

+*i()#+><<<>>*>><<>>i>>

>>(<<<<)>>

>>#<<<<

==第45頁(yè)解:(1)用關(guān)系圖法結(jié)構(gòu)優(yōu)先關(guān)系圖以下:f＋f*fif)g＋g*gig(g)f(第46頁(yè)

+*i()f46626g35772由上圖求得優(yōu)先函數(shù)以下:第47頁(yè)迭代函數(shù)函數(shù)+*i()0(初值)f11111g111111f24414g235512f35515g246613f35515g24661(2)由定義直接計(jì)算優(yōu)先函數(shù)過(guò)程以下:第48頁(yè)3.5LR分析法LR分析法是一個(gè)自下而上進(jìn)行規(guī)范歸約語(yǔ)法分析方法,L指自左向右掃描輸入串,R指最右推導(dǎo)(規(guī)范歸約)。LR分析法比遞歸下降分析法、LL(1)分析法對(duì)文法限制要少得多,大多數(shù)無(wú)二義性CFG語(yǔ)言都可用LR分析器識(shí)別,且速度快,并能準(zhǔn)確、指出輸入串語(yǔ)法錯(cuò)誤及犯錯(cuò)位置。LR分析法主要缺點(diǎn):手工結(jié)構(gòu)工作量相當(dāng)大,必須求援自動(dòng)產(chǎn)生工具。第49頁(yè)3.5.1LR分析器工作原理規(guī)范歸約(最右推導(dǎo)逆過(guò)程)關(guān)鍵是尋找句柄。LR分析法基本思想:在規(guī)范歸約過(guò)程中,一方面記住已移進(jìn)和歸約出符號(hào)串,即記住“歷史”;其次根據(jù)所用產(chǎn)生式推測(cè)未來(lái)可能遇到輸入符,即對(duì)未來(lái)進(jìn)行“展望”。當(dāng)一串貌似句柄符號(hào)串呈現(xiàn)于分析棧棧頂時(shí),希望能根據(jù)所記載“歷史”、“展望”及“現(xiàn)實(shí)”材料來(lái)確定棧頂符號(hào)是否構(gòu)成句柄。第50頁(yè)LR分析器結(jié)構(gòu)示意以下所表示,它由分析棧、分析表和總控程序三部分組成:a1a2…ai…an#LR分析表總控程序輸入串：棧頂#x1…xm輸出s0s1…sm分析棧第51頁(yè)LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出棧DFA?！皻v史”和“展望”材料被抽象成一些“狀態(tài)”,而分析棧用來(lái)存放這些狀態(tài),棧里每個(gè)狀態(tài)概括了從分析開始直到某一歸約階段全部“歷史”和“展望”資料。任何時(shí)候,棧頂狀態(tài)都代表了整個(gè)“歷史”和已推測(cè)出“展望”。第52頁(yè)LR分析器每一步工作都由棧頂狀態(tài)和現(xiàn)行輸入符唯一決定。為了易于歸約,把已歸約出文法符號(hào)也放在棧中。棧每一項(xiàng)內(nèi)容包含狀態(tài)s和文法符號(hào)X兩部分。(s0,#)為分析開始前預(yù)先放入棧里初始狀態(tài)和句子括號(hào)。棧頂狀態(tài)為sm,符號(hào)串X1X2…Xm是已移進(jìn)歸約出文法符號(hào)串。第53頁(yè)

LR分析表是LR分析器關(guān)鍵,它包含兩部分:動(dòng)作表(ACTION表)(二維數(shù)組)狀態(tài)轉(zhuǎn)換表(GOTO表)(二維數(shù)組)

ACTION[s,a]要求了狀態(tài)s面臨輸入符a時(shí)應(yīng)采取動(dòng)作。GOTO[s,X]要求了狀態(tài)s面對(duì)文法符號(hào)X(終止符或非終止符)時(shí)下一狀態(tài)。顯然,GOTO[s,X]定義了一個(gè)以文法符號(hào)為字母表DFA。第54頁(yè)ACTION[s,a]動(dòng)作:(1)移進(jìn):使(s,a)下一狀態(tài)s'=GOTO[s,a]和輸入符a進(jìn)棧,下一輸入符變現(xiàn)行輸入符。注:對(duì)終止符a,下一狀態(tài)s'值GOTO[s,a]實(shí)際上放在ACTION[s,a]中(2)歸約:用某一產(chǎn)生式A→β進(jìn)行歸約。若β長(zhǎng)度為γ,則歸約動(dòng)作是去掉棧頂γ個(gè)項(xiàng),使?fàn)顟B(tài)sm-γ變成棧頂狀態(tài),然后使(sm-γ,A)下一狀態(tài)s'=GOTO[sm-γ,A]和文法符號(hào)A進(jìn)棧。歸約不改變現(xiàn)行輸入符。執(zhí)行歸約意味著棧頂符號(hào)串Xm-γ+1…Xm是句柄。第55頁(yè)(3)接收:宣告分析成功,分析器停頓工作。(4)報(bào)錯(cuò):匯報(bào)發(fā)覺(jué)源程序有錯(cuò),調(diào)用犯錯(cuò)處理程序。LR分析器總控程序工作十分簡(jiǎn)單,它任一步只需按分析棧棧頂狀態(tài)s和現(xiàn)行輸入符a執(zhí)行ACTION[s,a]所要求動(dòng)作。LR分析器工作過(guò)程可看成是棧中狀態(tài)序列、已歸約串和輸入串組成三元式改變過(guò)程。第56頁(yè)比如,算術(shù)表示式文法G[E]以下:G[E]:(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i文法G[E]LR分析表見表3.13,試給出語(yǔ)句i+i*iLR分析過(guò)程。第57頁(yè)表3.13算術(shù)表示式文法LR分析表狀態(tài)ACTIONGOTOi+*()#ETF0s5

s4

1231

s6

acc

2

r2s7

r2r2

3

r4r4

r4r4

4s5

s4

8235

r6r6

r6r6

6s5

s4

937s5

s4

108

s6

s11

9

r1s7

r1r1

10

r3r3

r3r3

11

r5r5

r5r5

第58頁(yè)步驟狀態(tài)棧符號(hào)棧輸入串動(dòng)作說(shuō)明10#i+i*i#ACTION[0,i]=s5,狀態(tài)5入棧205#i+i*i#r6:F→i歸約,GOTO(0,F)=3入棧303#F+i*i#r4:T→F歸約,GOTO(0,T)=2入棧402#T+i*i#r2:E→T歸約,GOTO(0,E)=1入棧501#E+i*i#ACTION[1,+]=s6,狀態(tài)6入棧6016#E+i*i#ACTION[6,i]=s5,狀態(tài)5入棧表3.14i+i*iLR分析過(guò)程第59頁(yè)70165#E+i*i#r6:F→i歸約,GOTO(6,F)=3入棧80163#E+F*i#r4:T→F歸約,GOTO(6,T)=9入棧90169#E+T*i#ACTION[9,*]=s7,狀態(tài)7入棧1001697#E+T*i#ACTION[7,i]=s5,狀態(tài)5入棧11016975#E+T*i#r6:F→i歸約,GOTO(7,F)=10入棧120169710#E+T*F#r3:T→T*F歸,GOTO(6,T)=9入棧130169#E+T#r1:E→E+T,GOTO(0,E)=1入棧1401#E#Acc:分析成功第60頁(yè)怎樣由文法結(jié)構(gòu)LR分析表?

LR文法:對(duì)于一個(gè)文法,假如能夠結(jié)構(gòu)一張LR分析表使得它每個(gè)入口均是唯一確定,則稱該文法為L(zhǎng)R文法。對(duì)于LR文法,當(dāng)分析器對(duì)輸入串進(jìn)行自左至右掃描時(shí),一旦句柄展現(xiàn)于棧頂,能及時(shí)對(duì)它實(shí)施歸約。有些情況下LR分析器需“展望”和實(shí)際檢驗(yàn)未來(lái)k個(gè)輸入符才能決定應(yīng)采取什么樣“移進(jìn)-歸約”決議。第61頁(yè)

LR(k)文法:一個(gè)文法假如能用一個(gè)每步最多向前檢驗(yàn)k個(gè)輸入符LR分析器進(jìn)行分析,則稱該文法為L(zhǎng)R(k)文法。若一個(gè)文法任何“移進(jìn)-歸約”分析器都存在下述情況:盡管棧內(nèi)容和下一輸入符都已了解,但仍無(wú)法確定是“移進(jìn)”還是“歸約”,或無(wú)法從幾個(gè)可能歸約中確定其一,則該文法為非LR(1)文法。注意:(1)LR文法必定是無(wú)二義,一個(gè)二義文法不會(huì)是LR文法。(2)LR分析技術(shù)可適當(dāng)修改以適于一定二義文法。第62頁(yè)四種LR分析表結(jié)構(gòu)方法:(1)LR(0)表結(jié)構(gòu)方法:該法不足很大,但它是建立普通LR分析表基礎(chǔ)。(2)SLR(1)表(簡(jiǎn)單LR表)結(jié)構(gòu)方法:該法較易實(shí)現(xiàn)又極有使用價(jià)值。(3)LR(1)表(規(guī)范LR表)結(jié)構(gòu)方法:該法適合用于大多數(shù)CFG文法,但分析表體積龐大。(4)LALR表(向前LR表)結(jié)構(gòu)方法:該法介于SLR(1)和LR(1)之間。第63頁(yè)3.5.2LR(0)分析表結(jié)構(gòu)希望僅由一個(gè)只概括“歷史”資料而不包含推測(cè)性“展望”材料簡(jiǎn)單狀態(tài)就能識(shí)別展現(xiàn)在棧頂一些句柄，LR(0)項(xiàng)目集就是這么一個(gè)簡(jiǎn)單狀態(tài)。討論LR分析法時(shí),需要定義一個(gè)主要概念,這就是文法規(guī)范句型活前綴。字前綴是指該字任意首部,比如,字abc前綴有ε、a、ab或abc。所謂活前綴是指規(guī)范句型一個(gè)前綴,這種前綴不含句柄之后任何符號(hào)。第64頁(yè)在LR分析過(guò)程中任何時(shí)候，棧里文法符號(hào)X1X2…Xm應(yīng)組成活前綴。把輸入串剩下部分匹配于其后應(yīng)成為規(guī)范句型(假如整個(gè)輸入串確為一個(gè)句子話)。所以，只要輸入串已掃描部分保持可歸約成一個(gè)活前綴，就意味著所掃描部分沒(méi)有錯(cuò)誤。第65頁(yè)對(duì)于文法G[S],首先要結(jié)構(gòu)一個(gè)NFA,它能識(shí)別G[S]全部活前綴,這個(gè)NFA每個(gè)狀態(tài)稱為一個(gè)項(xiàng)目。

項(xiàng)目:文法G[S]中每一產(chǎn)生式右部添加一個(gè)圓點(diǎn),稱為文法G[S]一個(gè)LR(0)項(xiàng)目,簡(jiǎn)稱項(xiàng)目。比如,產(chǎn)生式A→XYZ對(duì)應(yīng)四個(gè)項(xiàng)目：A→·XYZA→X·YZA→XY·ZA→XYZ·注意,產(chǎn)生式A→ε只對(duì)應(yīng)一個(gè)項(xiàng)目A→·第66頁(yè)一個(gè)項(xiàng)目指明了在分析過(guò)程某個(gè)時(shí)刻看到產(chǎn)生式多大一部分。經(jīng)過(guò)使用文法項(xiàng)目可結(jié)構(gòu)一個(gè)NFA來(lái)識(shí)別文法全部活前綴，再用子集法把識(shí)別活前綴NFA確定化，使之成為一個(gè)以項(xiàng)目集合為狀態(tài)DFA，這個(gè)DFA就是建立LR分析算法基礎(chǔ)。第67頁(yè)識(shí)別一個(gè)文法活前綴DFA項(xiàng)目集全體稱為這個(gè)文法LR(0)項(xiàng)目集規(guī)范族。這個(gè)規(guī)范族提供了建立一類LR(0)和SLR(1)分析器基礎(chǔ)。圓點(diǎn)在最右端項(xiàng)目,如A→α·,稱為一個(gè)歸約項(xiàng)目;對(duì)文法開始符號(hào)S‘歸約項(xiàng)目,如S’→α·,稱為接收項(xiàng)目;形如A→α·aβ項(xiàng)目(a為終止符),稱為移進(jìn)項(xiàng)目;形如A→α·Bβ項(xiàng)目(B為非終止符)，稱為待約項(xiàng)目。第68頁(yè)1.LR(0)項(xiàng)目集規(guī)范族結(jié)構(gòu)可用ε_(tái)CLOSURE結(jié)構(gòu)一個(gè)文法LR(0)項(xiàng)目集規(guī)范族。首先結(jié)構(gòu)文法G[S]拓廣文法G'[S']，它包含整個(gè)G[S]并引進(jìn)一個(gè)不出現(xiàn)在G[S]中非終止符S'，同時(shí)加進(jìn)了一個(gè)新產(chǎn)生式S'→S。這么，僅含項(xiàng)目S'→S·狀態(tài)是唯一接收狀態(tài)。第69頁(yè)假定I是文法G‘[S’]任一項(xiàng)目集,定義和結(jié)構(gòu)CLOSURE(I)方法:(1)I任何項(xiàng)目都屬于CLOSURE(I)；(2)若A→α·Bβ屬于CLOSURE(I)，則對(duì)任何關(guān)于B產(chǎn)生式B→γ,其項(xiàng)目B→·γ屬于CLOSURE(I)。(3)重復(fù)(1)～(2)直至CLOSURE(I)不再增大為止。第70頁(yè)假定I是文法G‘[S’]任一項(xiàng)目集,X是一個(gè)文法符號(hào)(終止符或非終止符),則狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)定義為

GO(I,X)=CLOSURE(J)其中J={任何形如A→αX·β項(xiàng)目|A→α·Xβ屬于I}。若I是對(duì)某個(gè)活前綴γ有效項(xiàng)目集(狀態(tài)),則GO(I,X)是對(duì)γX有效項(xiàng)目集(狀態(tài))。第71頁(yè)經(jīng)過(guò)CLOSURE(I)和GO(I,X)結(jié)構(gòu)拓廣文法G'[S']LR(0)項(xiàng)目集規(guī)范族方法:(1)求出I閉包CLOSURE(I)(2)先用GO(I,X)求出J,再對(duì)J求其閉包CLOSURE(J)。以這類推,最終可結(jié)構(gòu)出拓廣文法G'[S']LR(0)項(xiàng)目集規(guī)范族。第72頁(yè)2.LR(0)分析表結(jié)構(gòu)若文法G[S]拓廣文法G‘[S’]活前綴識(shí)別自動(dòng)機(jī)中每個(gè)狀態(tài)(項(xiàng)目集)不存在下述情況：既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目或含有多個(gè)歸約項(xiàng)目,則G[S]是一個(gè)LR(0)文法。換言之,LR(0)文法項(xiàng)目集規(guī)范族中任一項(xiàng)目集均不包含沖突項(xiàng)。對(duì)于LR(0)文法,可直接從它項(xiàng)目集規(guī)范族C和狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)結(jié)構(gòu)出其LR(0)分析表。第73頁(yè)假定C={I0,I1,…,In},令每個(gè)項(xiàng)目集Ik下標(biāo)k作為分析器狀態(tài),并令包含項(xiàng)目S‘→·S集合Ik下標(biāo)k為分析器初態(tài),則LR(0)分析表結(jié)構(gòu)算法以下:(1)若項(xiàng)目A→α·aβ屬于Ik且GO(Ik,a)=Ij,a為終止符,則置ACTION[k,a]為“將(j,a)移進(jìn)?！?簡(jiǎn)記為sj。第74頁(yè)(2)若項(xiàng)目A→α·屬于Ik,則對(duì)任何終止符a或#,置ACTION[k,a]為“用A→α歸約”,簡(jiǎn)記為rj(其中j是第j個(gè)產(chǎn)生式。(3)若項(xiàng)目S‘→S·屬于Ik,則置ACTION[k,#]為接收,簡(jiǎn)記acc。(4)若GO(Ik,A)=Ij,A為非終止符,則置GOTO[k,A]=j。(5)分析表中凡不能用規(guī)則(1)～(4)填入空白格均置為“犯錯(cuò)標(biāo)志”。第75頁(yè)例3.16試結(jié)構(gòu)文法G[S]LR(0)分析表:G[S]:S→BBB→aB∣b解:將文法G[S]拓廣為文法G'[S']：G'[S']:(0)S'→S(1)S→BB(2)B→aB(3)B→b第76頁(yè)該文法LR(0)項(xiàng)目集規(guī)范族為:I0:S‘→·S?S→·BBB→·aBB→·bI1:S’→S·I2:S→B·BB→·aBB→·bI3:B→a·BB→·aBB→·b I4:B→b·I5:S→BB· I6:B→aB·第77頁(yè)SI0:S→·SS→·BBB→·aBB→·bI1:S→S·SI2:S→B·BB→·aBB→·bI5:S→BB·BI4:B→b·bbI3:B→a·BB→·aBB→·babI6:B→aB·Baa識(shí)別該文法活前綴DFA為:第78頁(yè)該文法LR(0)分析表為:狀態(tài)ACTIONGOTOab#SB0s3s4

121

acc

2s3s4

53s3s4

64r3r3r3

5r1r1r1

6r2r2r2

第79頁(yè)3.5.3SLR(1)分析表結(jié)構(gòu)LR(0)文法是一類非常簡(jiǎn)單文法,其特點(diǎn)是該文法活前綴識(shí)別自動(dòng)機(jī)每一狀態(tài)都不含沖突項(xiàng)。但即使是算術(shù)表示式文法也不是LR(0),所以需要研究一個(gè)簡(jiǎn)單“展望”材料LR分析法,即SLR(1)法。實(shí)際上,許多沖突性動(dòng)作都能夠經(jīng)過(guò)考查相關(guān)非終止符FOLLOW集而取得處理。第80頁(yè)SLR(1)沖突處理方法以下：假定LR(0)規(guī)范族任一項(xiàng)目集I中含有m個(gè)移進(jìn)項(xiàng)目:A1→α·a1β1,A2→α·a2β2,…,Am→α·amβm同時(shí)含有n個(gè)歸約項(xiàng)目:B1→α·,B2→α·,…,Bn→α·若集合{a1,…,am},FOLLOW(B1),…,FOLLOW(Bn)兩兩不相交,則隱含在I中動(dòng)作沖突可經(jīng)過(guò)檢驗(yàn)現(xiàn)行輸入符a屬于上述n+1個(gè)集合中哪個(gè)集合而取得處理,即:第81頁(yè)(1)若a是某個(gè)ai,i=1,2,…,m,則移進(jìn);(2)若a∈FOLLOW(Bi),i=1,2,…,n,則用產(chǎn)生式Bi→α進(jìn)行歸約;(3)對(duì)(1)(2)以外情況,報(bào)錯(cuò)。沖突性動(dòng)作這種處理方法叫做

SLR(1)沖突處理方法。第82頁(yè)文法G[S]SLR(1)分析表結(jié)構(gòu)方法:先把G[S]拓廣為G‘[S’]，對(duì)G‘[S’]結(jié)構(gòu)LR(0)項(xiàng)目集規(guī)范族C和活前綴識(shí)別自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換函數(shù)GO，然后再使用C和GO按下面算法結(jié)構(gòu)G‘[S’]SLR(1)分析表:假定C={I0,I1,…,In},令每個(gè)項(xiàng)目集Ik下標(biāo)k為分析器一個(gè)狀態(tài),并令含項(xiàng)目S‘→·SIk下標(biāo)k為初態(tài),則SLR(1)分析表可按以下方法結(jié)構(gòu):第83頁(yè)(1)若項(xiàng)目A→α·aβ屬于Ik且GO(Ik,a)=Ij,a為終止符,則置ACTION[k,a]為“將狀態(tài)j和符號(hào)a移進(jìn)?！?即sj。(2)若項(xiàng)目A→α·屬于Ik,則對(duì)任何輸入符a,a∈FOLLOW(A),置ACTION[k,a]為“用產(chǎn)生式A→α進(jìn)行歸約”,即rj。(3)若項(xiàng)目S‘→S·屬于Ik,則置ACTION[k,#]為接收,即acc。(4)若GO(Ik,A)=Ij,A為非終止符,則置GOTO[k,A]=j。第84頁(yè)(5)凡不能用規(guī)則(1)～(4)填入信息空白格均置“犯錯(cuò)標(biāo)志”。若按上法結(jié)構(gòu)ACTION表和GOTO表不含多重入口,則稱它為文法G[S]SLR(1)表。含有SLR(1)表文法稱為一個(gè)SLR(1)文法。使用SLR(1)表分析器叫做SLR(1)分析器。若按上述算法結(jié)構(gòu)分析表存在多重入口,則不能用上述算法結(jié)構(gòu)分析器。第85頁(yè)例3.18結(jié)構(gòu)例3.16文法SLR(1)分析表。解:先拓廣文法,再求文法LR(0)項(xiàng)目集規(guī)范族及DFA,求全部形如A→α·項(xiàng)目標(biāo)FOLLOW(A),即對(duì)S→BB·,B→aB·,B→b·求FOLLOW集:由FOLLOW集結(jié)構(gòu)方法得：①FOLLOW(S')={#}；②FIRST(B)FOLLOW(B),即FOLLOW(B)={a,b}；③由S‘→S,FOLLOW(S')FOLLOW(S),即FOLLOW(S)={#}；由S→BB,FOLLOW(S)FOLLOW(B),即FOLLOW(B)={a,b,#}。第86頁(yè)最終求G‘[S’]SLR(1)分析表以下:狀態(tài)ACTIONGOTOab#SB0s3s4

121

acc

2s3s4

53s3s4

64r3r3r3

5

r1

6r2r2r2

第87頁(yè)*3.5.4LR(1)分析表結(jié)構(gòu)在SLR(1)方法中，若項(xiàng)目集Ik含有A→α·，那么在狀態(tài)k時(shí)，只要當(dāng)前輸入符a∈FOLLOW(A)，就采取“用A→α歸約”動(dòng)作。但在某種情況下，當(dāng)狀態(tài)k展現(xiàn)于棧頂時(shí)，棧里符號(hào)串所組成活前綴βα未必允許把α歸約為A，因?yàn)榭赡軟](méi)有一個(gè)規(guī)范句型含有前綴βAa。所以，在這種情況下，用A→α進(jìn)行歸約未必有效。第88頁(yè)可構(gòu)想讓每個(gè)狀態(tài)含有更多展望信息,這些信息將有利于克服動(dòng)作沖突和排除無(wú)效歸約,必要時(shí)對(duì)狀態(tài)進(jìn)行分裂,使得LR分析器每個(gè)狀態(tài)能確切指出當(dāng)α后跟哪些終止符時(shí)才允許把α歸約為A。為此,需重新定義項(xiàng)目,使得每個(gè)項(xiàng)目都附帶有k個(gè)終止符?，F(xiàn)在每個(gè)項(xiàng)目標(biāo)普通形式為[A→α·β,a1a2…ak]此處,A→α·β是一個(gè)LR(0)項(xiàng)目,ai是終止符,這種項(xiàng)目稱為L(zhǎng)R(k)項(xiàng)目,其中,a1a2…ak稱為向前搜索串(或展望串)。第89頁(yè)向前搜索串僅對(duì)歸約項(xiàng)目[A→α·,a1a2…ak]有意義,對(duì)移進(jìn)或待約項(xiàng)目不起作用。歸約項(xiàng)目[A→α·,a1a2…ak]意味著當(dāng)它所屬狀態(tài)展現(xiàn)在棧頂且后續(xù)k個(gè)輸入符為a1a2…ak時(shí),才把棧頂α歸約為A。這里只對(duì)k≤1情形感興趣。結(jié)構(gòu)有效LR(1)項(xiàng)目集族方法和結(jié)構(gòu)LR(0)項(xiàng)目集規(guī)范族方法本質(zhì)上一樣,也需兩個(gè)函數(shù):CLOSURE(I)和GO(I,X)。第90頁(yè)項(xiàng)目集I閉包可按以下方式結(jié)構(gòu)：(1)I任何項(xiàng)目都屬于CLOSURE(I)。(2)若項(xiàng)目[A→α·Bβ,a]屬于CLOSURE(I),B→γ是一產(chǎn)生式,則對(duì)于FIRST(βa)中每個(gè)終止符b,若[B→·γ,b]原來(lái)不在CLOSURE(I)中,把它加進(jìn)去。(3)重復(fù)(2)直到CLOSURE(I)不再增大。函數(shù)GO(I,X)定義為:GO(I,X)=CLOSURE(J)其中J={形如[A→αX·β,a]項(xiàng)目|[A→α·Xβ,a]屬于I}第91頁(yè)結(jié)構(gòu)LR(1)分析表算法:假定C={I0,I1,…,In},令每個(gè)Ik下標(biāo)k為分析表狀態(tài),令含有[S‘→·S,#]Ikk為分析器初態(tài)。LR(1)分析表可按以下方法結(jié)構(gòu)：(1)若項(xiàng)目[A→α·aβ,b]屬于Ik且GO(Ik,a)=Ij,a為終止符,則置ACTION[k,a]為“將狀態(tài)j和符號(hào)a移進(jìn)?！?簡(jiǎn)記為sj；第92頁(yè)(2)若項(xiàng)目[A→α·,a]屬于Ik,則置ACTION[k,a]為“用產(chǎn)生式A→α歸約”,簡(jiǎn)記為rj,其中j是產(chǎn)生式編號(hào);(3)若項(xiàng)目[S‘→S·,#]屬于Ik,則置ACTION[k,#]為接收,簡(jiǎn)記為acc;(4)若GO(Ik,A)=Ij,A為非終止符,則置GOTO(Ik,A)=j;(5)分析表中凡不能用規(guī)則(1)～(4)填入信息空白欄均填“犯錯(cuò)標(biāo)志”。第93頁(yè)對(duì)于LR(1),有些狀態(tài)(項(xiàng)目集)除向前搜索符不一樣外,其關(guān)鍵部分都相同,即LR(1)比SLR(1)和LR(0)存在更多狀態(tài)。所以,LR(1)結(jié)構(gòu)比LR(0)和SLR(1)更復(fù)雜,占用存放空間也更多。第94頁(yè)3.5.5LALR分析表結(jié)構(gòu){自學(xué)}對(duì)LR(1)來(lái)說(shuō),存在著一些狀態(tài)(項(xiàng)目集),這些狀態(tài)除向前搜索符不一樣外,其關(guān)鍵部分都相同,能否將關(guān)鍵部分相同諸狀態(tài)合并為一個(gè)狀態(tài),這種合并是否會(huì)產(chǎn)生沖突?下面將對(duì)此進(jìn)行討論。

兩個(gè)LR(1)項(xiàng)目集含有相同心是指除去搜索符之后這兩個(gè)集合是相同。假如把全部同心LR(1)項(xiàng)目集合并為一,將看到這個(gè)心就是一個(gè)LR(0)項(xiàng)目集,這種LR分析法稱為L(zhǎng)ALR方法。第95頁(yè)對(duì)于同一個(gè)文法,LALR分析表和LR(0)以及SLR分析表永遠(yuǎn)含有相同數(shù)目標(biāo)狀態(tài)。LALR方法本質(zhì)上是一個(gè)折中方法，LALR分析表比LR(1)分析表要小得多，能力也差一點(diǎn)，但它卻能對(duì)付一些SLR(1)所不能對(duì)付情況。第96頁(yè)因?yàn)镚O(I,X)心僅僅依賴于I心，所以LR(1)項(xiàng)目集合并之后轉(zhuǎn)換函數(shù)GO可經(jīng)過(guò)GO(I,X)本身合并而得到，因而在合并項(xiàng)目集時(shí)無(wú)需考慮修改轉(zhuǎn)換函數(shù)問(wèn)題(假定I1與I2心相同，即項(xiàng)目集相同，則GO(I1,X)=GO(I2,X)，但這里項(xiàng)目集是不包含搜索符)。不過(guò)，動(dòng)作ACTION必須進(jìn)行修改，使之能夠反應(yīng)被合并集合既定動(dòng)作。第97頁(yè)假定有一個(gè)LR(1)文法,它LR(1)項(xiàng)目集不存在動(dòng)作沖突,但假如把同心集合并為一,就可能造成產(chǎn)生沖突。這種沖突不會(huì)是移進(jìn)/歸約沖突,因?yàn)槿舸嬖谶@種沖突,則意味著面對(duì)當(dāng)前輸入符號(hào)a,有一個(gè)項(xiàng)目[A→α·,a]要求采取歸約動(dòng)作,而同時(shí)有另一項(xiàng)目[B→β·aγ,b]要求把a(bǔ)移進(jìn);這兩個(gè)項(xiàng)目同處于(合并前)某