《編譯原理4語(yǔ)法分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理4語(yǔ)法分析.ppt（74頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第四章 語(yǔ)法分析,4.1語(yǔ)法分析程序的功能 語(yǔ)法分析：逐一分析詞法分析所得的屬性字，檢查其中的語(yǔ)法錯(cuò)誤，如果沒(méi)有發(fā)現(xiàn)語(yǔ)法錯(cuò)誤， 則給出正確的語(yǔ)法結(jié)構(gòu)。 語(yǔ)法分析常用方法： 1、自頂向下分析方法，2、自底向上分析方法。 所謂的自頂向下分析法就是從文法的開始符號(hào)出發(fā)，根據(jù)文法規(guī)則正向推導(dǎo)出給定句子的方法；或者說(shuō)，從樹根開始，往下構(gòu)造語(yǔ)法樹，直到建立每個(gè)樹葉的分析方法。 自底向上分析方法是從給定的輸入串開始，根據(jù)文法規(guī)則逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)；或者說(shuō)，從語(yǔ)法樹的末端開始，步步向上歸約，直至根結(jié)點(diǎn)的分析方法。,4.2自頂向下分析法 4.2.1非確定的自頂向下分析法的思想 對(duì)任何輸入串w

2、試圖用一切可能的辦法，從文法的開始符號(hào)出發(fā)，自上向下地為它建立一棵語(yǔ)法樹。或者說(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。如果試探成功，則w為相應(yīng)文法的一個(gè)句子，否則w就不是文法的句子。這種分析過(guò)程本質(zhì)上是一種窮舉試探過(guò)程，是反復(fù)使用不同規(guī)則，謀求匹配輸入串的過(guò)程。 例：設(shè)有文法GS SaAb,A de|d,判斷adb是否為該文法的句子。 自頂向下分析的難點(diǎn)：對(duì)于形如:U x1|x2||xn 的規(guī)則,可能需要對(duì)所有的規(guī)則都要試探，效率很低。故常使用確定的自頂向下分析法，但確定的自頂向下分析法對(duì)文法有一定的限制，既是要求文法無(wú)左遞歸和無(wú)回溯。,4.2.2文法的左遞歸和回溯的消除 1.左遞歸的消除 (1)引進(jìn)一

3、個(gè)新的非終結(jié)符，把含左遞歸的規(guī)則改寫為右遞歸,一般地，對(duì)于含有左遞歸規(guī)則的文法GA: A A1|A 2||A m|1| 2|| n 消除左遞歸規(guī)則后的文法為： A 1A| 2A|| nA A 1A| 2A|| mA| ,例：E E+T|E-T|T T TF|T/F|F F (E)|i,E TE E +TE|-TE| T FT T *FT|/FT| F (E)|i,(2)擴(kuò)充的BNF表示法 1）專用符號(hào)：擴(kuò)充的BNF又引進(jìn)了三對(duì)專用符號(hào)。 花括號(hào)：表示符號(hào)串可以重復(fù)出現(xiàn)任意次。 使用可以消除規(guī)則的左遞歸現(xiàn)象的出現(xiàn)。 例：N ND|D D 0|1|2||9 用擴(kuò)充的BNF可以表示為： N

4、 DD D 0|1|2||9 方括號(hào)：表示符號(hào)串可有可無(wú) 圓括號(hào)（）：（）表示提因子。 例：A ax|ay||aw 改寫為：A a(x|y||w)。,2）擴(kuò)充的BNF表示法的用途 例：設(shè)有文法GE： E T|E+T T F|T*F F i|(E) 用擴(kuò)充的BNF法可改寫為： E T+T T FF F i|(E) 擴(kuò)充的BNF表示法最大特點(diǎn)就是消除了文法的左遞歸問(wèn)題。,E T+T|-T T FF|/F F i|(E),例：設(shè)有文法A Ac|Aad|bd|e，用擴(kuò)充的BNF表示法對(duì)其改寫,A （bd|e） c|ad,2.回溯的消除 引起回溯的原因：在文法中某個(gè)非終結(jié)符A有多個(gè)候

5、選式，遇到用A去匹配當(dāng)前輸入符號(hào)時(shí)，無(wú)法確定選用唯一的一個(gè)候選式，而只能逐一進(jìn)行試探，從而引起回溯。 具體表現(xiàn)為兩種情況： 第一種情況是相同左部的規(guī)則，其右部左端第一個(gè)符號(hào)相同。 SaAb,A de|d,對(duì)于adb 第二種情況是相同左部的規(guī)則，其中某一右部能推出。 ABx,B x| ,對(duì)于x,常用的符號(hào)集有三種：首符號(hào)集：FIRST；向前看集：FOLLOW；可選集：SELECT。 (1)設(shè)是文法G的任一符號(hào)串，定義符號(hào)串的首符號(hào)集為： FIRST()=a| a，a Vt 若 ，則規(guī)定 FIRST()，既FIRST()是從可以推導(dǎo)出的所有首終結(jié)符或可能的。 (2)設(shè)文法G的開始符號(hào)為S，對(duì)于G的

6、任何非終結(jié)符A，定義非終結(jié)符A的向前看集FOLLOW(A)=a|S Aa，aVt 若有S A ，則規(guī)定$ FOLLOW(A) ，換句話說(shuō)FOLLOW(A) 是文法的所有句型中緊接在A之后出現(xiàn)的終結(jié)符或$，$作為輸入串的結(jié)束符。 (3)設(shè)有文法GS，并有規(guī)則A ，AVN, V*,則該規(guī)則的可選集為： SELECT(A )=,FIRST() 若 ,FIRST() FOLLOW(A)若 ,,,一個(gè)上下文無(wú)關(guān)文法G是LL(1)文法，并且僅當(dāng)對(duì)G中每個(gè)非終結(jié)符A的任何兩個(gè)不同的規(guī)則A |，滿足SELECT(A ) SELECT(A )= ，其中，中至多只有一個(gè)能推出串。 例：判斷下列文法是否為L(zhǎng)L(

7、1)文法 1.SaAb,A de|d 2.A aB|d,B bBA| 3. SaAB，A bB|dA| ，B a|e 4.2.3某些非LL(1)文法到LL(1)文法的改寫 若文法中含有左遞歸或含有公共左因子，則該文法不是LL(1)文法，因此對(duì)于某些非LL(1)文法來(lái)說(shuō)，可以通過(guò)消除左遞歸和反復(fù)提取公共左因子對(duì)文法進(jìn)行等價(jià)變換，將其改造為L(zhǎng)L(1)文法。,提取公共因子： 當(dāng)文法中含有形如A1| 2|| n的規(guī)則，可將它改寫成 AA A 1| 2|| n 若在1，2，n中仍含有公共左因子，這時(shí)可再次提取，這樣反復(fù)進(jìn)行提取，直到引進(jìn)新的非終結(jié)符的有關(guān)規(guī)則再無(wú)公共左因子為止。 例：將下例文法改寫為L(zhǎng)L

8、(1)文法，并驗(yàn)證之。 1.SaAb,A de|d 2. Sad|Ae,A aS|bA,對(duì)于文法S Ae|Bd，A aAe|b，B aBd|b,4.2.4遞歸下降分析法 基本思想：對(duì)文法中的每個(gè)非終結(jié)符編寫一個(gè)函數(shù)（或子程序），每個(gè)函數(shù)（或子程序）的功能是識(shí)別由該非終結(jié)符所表示的語(yǔ)法成分。由于描述語(yǔ)言的文法常常是遞歸定義的，因此相應(yīng)的這組函數(shù)（或子程序）必然以相互遞歸的方式進(jìn)行調(diào)用，所以將此種分析法稱為遞歸下降分析法。 構(gòu)造遞歸下降分析程序時(shí)，每個(gè)函數(shù)名是相應(yīng)的非終結(jié)符，函數(shù)體則是根據(jù)規(guī)則右部符號(hào)串的結(jié)構(gòu)編寫。 1)當(dāng)遇到終結(jié)符a時(shí)，則編寫語(yǔ)句 if (當(dāng)前讀來(lái)的輸入符號(hào)==a) 讀下一個(gè)輸入

9、符號(hào)。 2)當(dāng)遇到非終結(jié)符A時(shí)，則編寫語(yǔ)句調(diào)用A()。 3)當(dāng)遇到A 規(guī)則時(shí)，則編寫語(yǔ)句 if (當(dāng)前讀來(lái)的輸入符號(hào)FOLLOW(A)) error()。 4)當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式時(shí)，按LL(1)文法的條件能唯一地選擇一個(gè)候選式進(jìn)行推導(dǎo)。,例：設(shè)有文法GS: S a||(T) T T,S|S 試構(gòu)造一個(gè)識(shí)別該文法句子的遞歸下降分析程序。 設(shè)函數(shù)scaner()的功能是讀進(jìn)源程序的下一個(gè)單詞符號(hào)并把它放在全局變量sym中；函數(shù)error()是出錯(cuò)處理程序。,4.2.5 LL（1）分析方法（預(yù)測(cè)分析法） LL（1）分析方法也是一種自頂向下的分析技術(shù)。第一個(gè)L表示采用從左到右掃描程序，第

10、二個(gè)L表明采用最左推導(dǎo)，1表示分析時(shí)每一步只需向前看一個(gè)符號(hào)即可決定所選用的規(guī)則，且這種選擇是準(zhǔn)確無(wú)誤的。采用這種方法進(jìn)行語(yǔ)法分析要求描述語(yǔ)言的文法是LL（1）文法。 預(yù)測(cè)分析器由一張預(yù)測(cè)分析表（也稱LL（1）分析表 ）、一個(gè)先進(jìn)后出的分析棧和總控程序三部分組成。,,Sk,Tj,預(yù)測(cè)分析表是一個(gè)MA，a形式的矩陣，其中A為非終結(jié)符，a是終結(jié)符或$，分析表元素MA，a中的內(nèi)容為一條關(guān)于A的規(guī)則，表明當(dāng)A面臨輸入符號(hào)a時(shí)，當(dāng)前推導(dǎo)所應(yīng)采用的候選式，當(dāng)元素的內(nèi)容為出錯(cuò)標(biāo)識(shí)時(shí)，則表明A不應(yīng)該面臨輸入符號(hào)a。 預(yù)測(cè)分析器的總控程序在任何時(shí)候都是根據(jù)棧頂符號(hào)和當(dāng)前符號(hào)a來(lái)決定分析器的動(dòng)作。 分析器工作流程

11、可簡(jiǎn)單表示為： 1.初始化。分析開始時(shí)，首先將棧底符號(hào)$及文法的開始符號(hào)S推入分析棧，并對(duì)各指示器置初值，此時(shí)分析棧與輸入串有如下格局： 之后反復(fù)執(zhí)行下面的第二步。 2.設(shè)在分析的某一時(shí)刻，分析棧和余留的輸入串處于如下的格局：,,時(shí)可視分析棧頂?shù)奈姆ǚ?hào)Xm的不同情況，分別作如下處理： （1）若XmVT$，且Xm= ai，則表明棧頂符號(hào)已與當(dāng)前正掃視的輸入符號(hào)（包括句尾符號(hào)$在內(nèi)）相匹配，此時(shí)應(yīng)將Xm從棧中退出，并將輸入串指示器向前推進(jìn)一個(gè)位置，否則進(jìn)行語(yǔ)法錯(cuò)誤處理； （2）若XmVn，則以符號(hào)對(duì)（ Xm，ai ）查分析表，設(shè)元素A Xm, ai為產(chǎn)生式Xm Y1 Y2 Yk，則將Xm從

12、棧中退出，并將Y1 Y2 Yk按反序推入棧中，從而產(chǎn)生如下格局： 但若AXm, ai為“出錯(cuò)”，則進(jìn)行語(yǔ)法錯(cuò)誤處理。,（3）若Xm=ai =$（即分析棧將被拆空） ，則表明輸入串已完全得到匹配，此時(shí)可宣告分析成功而結(jié)束工作。,構(gòu)造預(yù)測(cè)分析表的算法 (1)計(jì)算文法G的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集。 1）對(duì)每一文法符號(hào)X(VNVT),計(jì)算FIRST(X): a.若X VT,則FIRST(X) =X; b.若XVN,且有規(guī)則Xa,a VT,則a FIRST(X); c.若XVN,且有規(guī)則X, FIRST(X); d.若XY是一個(gè)產(chǎn)生式且YVN,則把FIRST(Y)中的所有非元素都加

13、到FIRST(X)中；若有規(guī)則Xy1y2yn,對(duì)于任意的i(1i n),當(dāng)y1y2yi-1都是非終結(jié)符，且y1y2yi-1 時(shí)，則將FIRST(yi)中的所有非元素都加到FIRST(X)中,特別是，若y1y2yn ，則 FIRST(X)。 e.反復(fù)使用a-d,直到FIRST集不再增大為止。,2）對(duì)每一文法符號(hào)AVN,計(jì)算FOLLOW(A): a.對(duì)文法的開始符號(hào)S，則將$加到FOLLOW(S)中； b.若A B是一條規(guī)則，則把FIRST()中的非元素加到FOLLOW(B)中; c.若A B 或A B是一條規(guī)則且 ，則把FOLLOW(A) 加到FOLLOW(B)中; d.反復(fù)使用b-c直到

14、每個(gè)非終結(jié)符的FOLLOW集不再增大為止。 (2)對(duì)文法的每個(gè)規(guī)則A ，若a FIRST(),則置MA,a= A 。 (3)若 FIRST(),則對(duì)任何b FOLLOW(A)，則MA,b= A 。 (4)把分析表中無(wú)定義的元素標(biāo)上出錯(cuò)標(biāo)識(shí)error(表中用空白表示) P67 例4.10,4.3自下向上分析法的一般原理 自下向上分析法是按照移進(jìn)歸約法的原理建立起來(lái)的一種語(yǔ)法分析方法，這種分析法的基本思想是：用一個(gè)寄存文法符號(hào)的先進(jìn)后出的棧，將輸入符號(hào)一個(gè)一個(gè)地按從左到右掃描順序移入棧中，邊移入邊分析，當(dāng)棧頂符號(hào)串形成某條規(guī)則右部時(shí)就進(jìn)行一次歸約，即用該規(guī)則左部非終結(jié)符替換相應(yīng)規(guī)則右部符號(hào)串，我們

15、把棧頂被歸約的這一符號(hào)串稱為可歸約串。重復(fù)這一過(guò)程直到整個(gè)輸入串分析完畢。最終若棧中剩下句子界符“$”和文法的開始符號(hào)，則所分析的輸入符號(hào)串是文法的正確句子，否則，就不是文法正確的句子，報(bào)告錯(cuò)誤。 例：設(shè)有文法GA: AaBcDe,B b,B Bb,D d,實(shí)現(xiàn)自下而上分析法的關(guān)鍵問(wèn)題是如何精確定義可歸約串，以及怎樣識(shí)別可歸約串,4.4算符優(yōu)先分析法 4.4.1方法概述 所謂的算符優(yōu)先分析法就是依照算術(shù)表達(dá)式的四則運(yùn)算過(guò)程而設(shè)計(jì)的一種語(yǔ)法分析方法，這種方法首先要規(guī)定運(yùn)算符之間（確切的說(shuō)是終結(jié)符之間）的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后借助這種關(guān)系，比較相鄰運(yùn)算符的優(yōu)先級(jí)來(lái)確定句型的可歸約串，并進(jìn)行歸約。

16、 例：E E+E|E*E|(E)|i對(duì)于句子i+i*i有兩種不同的規(guī)范歸約。 第一種： i+i*i E+i*i E+E*i E+E*E E+E E 第二種： i+i*i E+i*i E+E*i E*i E*E E 問(wèn)題原因：沒(méi)有定義+和*的優(yōu)先關(guān)系，在第一種規(guī)范歸約中是假定*優(yōu)先于+，所以不能立即把E+E歸約為E,而在第二種歸約中是假定+優(yōu)先于*，因此必須把E+E歸約為E。可見(jiàn)在歸約過(guò)程中起決定因素的是相鄰兩個(gè)終結(jié)符號(hào)的優(yōu)先關(guān)系。,任意兩個(gè)相鄰終結(jié)符號(hào)a和b之間的優(yōu)先關(guān)系有三種： ab a的優(yōu)先級(jí)大于b 優(yōu)先關(guān)系與出現(xiàn)的左右次序有關(guān)： a a 一個(gè)文法的終結(jié)符號(hào)之間的優(yōu)先

17、關(guān)系可用一個(gè)矩陣來(lái)表示，矩陣的每一行每一列都是文法的終結(jié)符，矩陣元素是兩個(gè)終結(jié)符之間可能的優(yōu)先關(guān)系。算符優(yōu)先分析法并不是對(duì)所有的文法都適合，他對(duì)文法有一定的要求，即要求文法是算符優(yōu)先文法。,4.4.2算符優(yōu)先文法的定義 1.算符文法的定義 設(shè)有文法G，若G中沒(méi)有形如U VW的規(guī)則，其中V、W為非終結(jié)符，則稱G為算符文法，也稱OG文法。也就是說(shuō)在算符文法中任何一個(gè)規(guī)則右部都不存在兩個(gè)非終結(jié)符相鄰的情況。 算符文法有兩個(gè)重要性質(zhì)： 1）在算符文法中任何句型都不含有兩個(gè)相鄰的非終結(jié)符。 2）若Ab或bA出現(xiàn)在算符文法的句型中，其中AVN,b VT, 則中任何含有b的短語(yǔ)必含有A.,4.4.3算符優(yōu)先

18、關(guān)系表的構(gòu)造 首先對(duì)文法每個(gè)非終結(jié)符A定義兩個(gè)集合： FIRSTVT(A)=b|A b或A Bb,bVT,B VN LASTVT(A)=a| A a或A aB,aVT,B VN 構(gòu)造文法G的優(yōu)先關(guān)系表算法如下： 1）為每個(gè)非終結(jié)符A計(jì)算FIRSTVT(A)和LASTVT(A)。 2）執(zhí)行程序 for (每個(gè)產(chǎn)生式Ax1x2xn) for(i=1;i<=n-1;i++) if (xiVT且Xi+1 VT)置xi Xi+1 ； if (i<=n-2且xiVT且Xi+2 VT，而Xi+1 VN)置xi Xi+2 ；,if (xiVT,Xi+1 VN) for(FIRSTVT(Xi+1

19、)中的每個(gè)b)置xi xi+1; 3)對(duì)FIRSTVT(S )中的所有b置$ $；置$ $，S為文法的開始符號(hào) 例：設(shè)有文法：GE E E+T|T T TF|F F (E)|i,4.4.4算符優(yōu)先分析算法的設(shè)計(jì) 算術(shù)優(yōu)先分析法并不是一種規(guī)范歸約的分析法，它不是用句柄來(lái)刻畫可歸約串，而是用最左素短語(yǔ)來(lái)刻畫可歸約串。 1.最左素短語(yǔ) 所謂句型的素短語(yǔ)是指這樣一種短語(yǔ)，它至少包含一個(gè)終結(jié)符，并且除自身之外，不再包含其他的素短語(yǔ)。句型最左邊的素短語(yǔ)稱為最左素短語(yǔ)。 如上例對(duì)句型T+T*F+i求其素短語(yǔ)和最左素短語(yǔ)。 2.識(shí)別句型最左素短語(yǔ)的方法 由算符文法的性質(zhì)可知，算符優(yōu)先文法的任何句型都沒(méi)有相鄰

20、的兩個(gè)非終結(jié)符，其句型總可以表示成$N1a1N2a2NnanNn+1$，其中Ni為非終結(jié)符或空，ai為終結(jié)符（1i n ）,對(duì)算符優(yōu)先文法有如下定理： 一個(gè)算符優(yōu)先文法G的任何句型的最左素短語(yǔ)是滿足下列條件的最左子串NiaiNi+1ai+1ajNj+1 ai-1 aj+1 具體方法是：從左到右掃描句型中的各個(gè)符號(hào)，且在掃描過(guò)程中，依次查看兩相繼終結(jié)符號(hào)間的優(yōu)先關(guān)系，直至找出滿足關(guān)系aj aj+1的終結(jié)符aj為止，記下aj的位置，再?gòu)腶j開始向左掃描，直至找到滿足關(guān)系ai-1 < ai的終結(jié)符ai為止，此時(shí)形如NiaiNi+1ai+1ajNj+1的子串即為句型應(yīng)歸約的最左素短語(yǔ)。,3.算符優(yōu)先分

21、析法 用一個(gè)存放文法符號(hào)的先進(jìn)后出的棧，并利用優(yōu)先關(guān)系確定最左素短語(yǔ)是否已經(jīng)形成來(lái)決定分析器的動(dòng)作，如果當(dāng)前棧頂?shù)慕K結(jié)符號(hào)和待輸入符號(hào)之間的優(yōu)先關(guān)系是 ，則表示已找到最左素短語(yǔ)的尾，再?gòu)臈ｍ旈_始，按優(yōu)先關(guān)系在棧內(nèi)向前尋找最左素短語(yǔ)的頭，然后分析器將歸約最左素短語(yǔ)，如果出現(xiàn)兩個(gè)終結(jié)符號(hào)之間不存在優(yōu)先關(guān)系，則表示存在語(yǔ)法錯(cuò)誤，分析器調(diào)用出錯(cuò)處理程序。 算法：設(shè)K為棧的使用深度，a用來(lái)存放當(dāng)前輸入符號(hào)，j是棧的查找指針，Q是工作單元，則算法流程圖如下：,在算法中沒(méi)有指明應(yīng)將棧頂?shù)淖钭笏囟陶Z(yǔ)歸約到哪一個(gè)非終結(jié)符N，這是因?yàn)榉墙K結(jié)符在分析過(guò)程中對(duì)識(shí)別最左素短語(yǔ)沒(méi)有任何影響，因此可以不關(guān)心非終結(jié)符到底是哪

22、一個(gè)具體符號(hào)，故可取任意的名字N來(lái)代替它們。分析成功的標(biāo)志是棧中僅剩下$N. 4.4.5優(yōu)先函數(shù)的構(gòu)造 1.優(yōu)先函數(shù)f和g的定義 當(dāng)ab則令f(a)g(b) 我們把f和g分別稱為棧內(nèi)優(yōu)先函數(shù)和棧外優(yōu)先函數(shù)。這樣a和b之間的優(yōu)先關(guān)系可以由比較f(a)和g(b)的大小來(lái)決定。,2.優(yōu)先函數(shù)的構(gòu)造方法 方法一：逐次加1法 1)確定初值，對(duì)所有的終結(jié)符(包括$)a，令f(a)=g(a)=0(可為其它任意正數(shù)) 2)對(duì)所有終結(jié)符a和b 如果ab，而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(

23、a)=g(b)=max(f(a),g(b)) 3)重復(fù)執(zhí)行2)直到過(guò)程收斂。重復(fù)過(guò)程中若f(a)或g(b)的值大于2n(n為終結(jié)符個(gè)數(shù))則表明該函數(shù)關(guān)系表不存在優(yōu)先函數(shù)。 對(duì)優(yōu)先函數(shù)每個(gè)元素的值都增加同一常數(shù)，仍為原優(yōu)先關(guān)系表的優(yōu)先函數(shù)，即一個(gè)文法的優(yōu)先關(guān)系表對(duì)應(yīng)的優(yōu)先函數(shù)不唯一，當(dāng)然有一些優(yōu)先關(guān)系表不存在對(duì)應(yīng)的優(yōu)先函數(shù)。,方法二：Bell有向圖法 1）對(duì)每個(gè)終結(jié)符a(包括$)，令其對(duì)應(yīng)兩個(gè)符號(hào)fa和ga，畫一張以所有符號(hào)fa和ga為結(jié)點(diǎn)的方向圖，若ab或a b，就要畫一條從fa到gb的方向??；若a

24、發(fā)所能到達(dá)的結(jié)點(diǎn)（包括該結(jié)點(diǎn)自身在內(nèi)）的個(gè)數(shù)，賦給結(jié)點(diǎn)fa的數(shù)等于fa的值，賦給結(jié)點(diǎn)gb的數(shù)等于gb的值。 3）對(duì)構(gòu)造出的優(yōu)先函數(shù)f和g進(jìn)行檢查，看他們同原先的優(yōu)先關(guān)系表是否矛盾，若沒(méi)有矛盾，則f和g既為所求優(yōu)先函數(shù)，否則不存在優(yōu)先函數(shù)。,4.5 LR分析方法 所謂LR（K）方法：是指從左到右掃描和自底向上的語(yǔ)法分析方法。L是指從左到右掃描輸入符號(hào)串，R是指構(gòu)造最右推導(dǎo)的逆過(guò)程，K指最多向前看K個(gè)符號(hào)就可惟一確定是歸約還是移進(jìn)。 LR（K）理論證明：1)每個(gè)LR（K）文法都是無(wú)二義性文法2)一個(gè)由LR（K）文法產(chǎn)生的語(yǔ)言也可由LR（1）文法產(chǎn)生。而且通常的程序設(shè)計(jì)語(yǔ)言一般都能由LR（1）文法產(chǎn)

25、生，因此對(duì)程序設(shè)計(jì)語(yǔ)言的編譯，我們僅需要考慮K1的情況即可。 4.5.1 LR分析器的原理和過(guò)程 LR分析法確定句柄的基本思想：在規(guī)范歸約分析過(guò)程中，根據(jù)分析棧中記錄的已移進(jìn)和歸約的整個(gè)符號(hào)串（即歷史）和使用的規(guī)則推測(cè)未來(lái)可能遇到的輸入符號(hào)（即展望），以及現(xiàn)實(shí)讀到的輸入符號(hào)這三方面的信息來(lái)確定分析棧棧頂?shù)姆?hào)串是否構(gòu)成句柄。 一個(gè)LR分析器的結(jié)構(gòu)示意圖如下：,,,分析棧用來(lái)存放分析過(guò)程中的歷史和展望信息。LR分析法將歷史和展望信息抽象成狀態(tài)，并放在分析棧中，這就是說(shuō)分析棧中的每個(gè)狀態(tài)概括了從分析開始到某一歸約階段的整個(gè)分析歷史和對(duì)未來(lái)進(jìn)行的展望。,LR分析表是LR分析法的核心，一張LR分析表由

26、分析動(dòng)作表（ACTION）和狀態(tài)轉(zhuǎn)換表（GOTO）組成。 分析動(dòng)作表,分析動(dòng)作表元素ACTIONSi,a規(guī)定了當(dāng)狀態(tài)Si面臨符號(hào)a（a為文法的全部終結(jié)符和句子界符$）時(shí)應(yīng)當(dāng)執(zhí)行的動(dòng)作，有四種可能的動(dòng)作： 1）移進(jìn)：把狀態(tài)Sj=ACTIONSi,a和輸入符號(hào)a移入分析棧。 2）歸約：當(dāng)棧頂符號(hào)串形成句柄，且文法中有A 的規(guī)則，其中| |=,則歸約動(dòng)作是從分析棧棧頂去掉個(gè)文法符號(hào)和個(gè)狀態(tài)，并把歸約符A和GOTO Si- ,A= Sj移入分析棧。,3）接受（acc）:表示分析成功。此時(shí)，分析棧中只剩下文法開始符號(hào)S和當(dāng)前讀到的輸入符號(hào)$，即輸入符號(hào)串已經(jīng)結(jié)束。 4）報(bào)錯(cuò)：表示輸入串含有錯(cuò)誤，此時(shí)出現(xiàn)

27、棧頂?shù)哪骋粻顟B(tài)遇到了不該遇到的輸入符號(hào)。,動(dòng)作轉(zhuǎn)換表,狀態(tài)轉(zhuǎn)換表GotoSi,x規(guī)定了當(dāng)狀態(tài)Si遇到文法符號(hào)x（x為文法的全部符號(hào)）時(shí)應(yīng)轉(zhuǎn)移到的下一個(gè)狀態(tài)。 為了節(jié)省存儲(chǔ)空間，通常把兩個(gè)表重疊，即把當(dāng)前狀態(tài)下面臨終結(jié)符的下一個(gè)狀態(tài)與分析動(dòng)作表的移進(jìn)動(dòng)作用數(shù)組元素表示。,總控程序也稱為驅(qū)動(dòng)程序，對(duì)所有的LR分析器總控程序是相同的，其過(guò)程如下：,1.分析開始時(shí)，首先將初始狀態(tài)S0及句子界符$推入分析棧。 2.設(shè)在分析的某一步，分析棧和余留輸入符號(hào)串處于如下格局： 則用當(dāng)前棧頂?shù)臓顟B(tài)Sm及正掃視的輸入符號(hào)ai組成的符號(hào)對(duì)（ Sm， ai ）去查分析動(dòng)作表，并根據(jù)分析表元素ACTIONSm， ai

28、的指示采取相應(yīng)的分析動(dòng)作，每一分析表元素所指示的僅能是下列動(dòng)作之一：,1）若ACTIONSm， ai =“移進(jìn)”，則表明句柄尚未在棧頂部形成，正期待繼續(xù)移進(jìn)輸入符號(hào)以形成句柄，故將當(dāng)前輸入符號(hào)ai推入棧中，即 然后，以符號(hào)對(duì)（ Sm， ai ）去查狀態(tài)轉(zhuǎn)移表，設(shè)相應(yīng)的表元素GOTOSm， ai = Sm+1，再將此新的狀態(tài)Sm+1（即要轉(zhuǎn)移到的下一個(gè)狀態(tài)）推入棧中，則有如下格局：,2）若ACTIONSm， ai =rj其中rj意指按文法的第j個(gè)產(chǎn)生式A Xm-r+1Xm-r+2 Xm進(jìn)行規(guī)約。這表明棧頂?shù)姆?hào)串Xm-r+1Xm-r+2 Xm已是當(dāng)前的句型的句柄，按第j個(gè)產(chǎn)生式進(jìn)行規(guī)約，也就是

29、將分析棧從頂向下的r個(gè)符號(hào)和r個(gè)狀態(tài)退出，然后將文法符號(hào)A進(jìn)棧，此時(shí)分析棧格局為 然后再以（ Sm-r， A）去查狀態(tài)轉(zhuǎn)移表，設(shè)GOTOSm-r， A = Sk，再將此新的狀態(tài)推入棧中，則有如下格局：,3）若ACTIONSm， ai =“接受”，則表明當(dāng)前的輸入串已被成功地分析完畢，應(yīng)終止分析工作。 4）若ACTIONSm， ai =“ERROR”，則表明當(dāng)前的輸入串中有語(yǔ)法錯(cuò)誤，應(yīng)該調(diào)用出錯(cuò)處理程序進(jìn)行處理。 3.重復(fù)步驟2的工作，直到在分析的某一步，棧頂出現(xiàn)“接受”狀態(tài)為止。此時(shí)，分析棧的最終格局應(yīng)為 其中Z為文法的開始符號(hào)， Sz為使ACTIONSz，$=“接受”的唯一狀態(tài)。,用稍微

30、程序化的寫法可描述為： 初始化(初始狀態(tài)S0在分析棧棧頂，輸入串的第一個(gè)符號(hào)讀入a)； while(ACTIONS,a!=acc) if(ACTIONS,a==Si) 將狀態(tài)Si和輸入符號(hào)a進(jìn)棧； 將下一個(gè)輸入符號(hào)讀入a; else if(ACTIONS,a==rj) 用第j條規(guī)則A 歸約； 將| |個(gè)狀態(tài)和| |個(gè)輸入符號(hào)退棧： 當(dāng)前棧頂狀態(tài)為S,將A和GOTOS， A = S進(jìn)棧； else if(ACTIONS,a==ERROR) error();,例：設(shè)有文法 0.S S 1.S A 2.S B 3.A aAb 4.A c 5.B aBb 6.B d,對(duì)aacbb$進(jìn)行分析,4.5.2

31、 LR（0）分析法 LR(0)根據(jù)當(dāng)前分析棧頂狀態(tài)確定應(yīng)完成何種分析動(dòng)作。 LR分析器的關(guān)鍵部分是分析表的構(gòu)造。構(gòu)造LR分析表的的基本思想是從給定的上下文無(wú)關(guān)文法直接構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA，然后將DFA轉(zhuǎn)換成一張LR分析表。 一、幾個(gè)基本概念 1.文法規(guī)范句型的活前綴 1）字符串的前綴是指字符串的任意首部。例：字符串a(chǎn)bc的前綴有、a、ab、abc 2）規(guī)范句型的活前綴是指規(guī)范句型的前綴，這種前綴不包含句柄右邊的任何符號(hào)。若是含句柄的活前綴，并且每個(gè)句柄都是的后端，則稱是可歸前綴或可規(guī)范前綴。,例：設(shè)有文法GS SS S CbBA A Aab A ab B c B Db C

32、 a D a 對(duì)于句子ababab有規(guī)范推導(dǎo)： S S CbBA CbBab CbDbab Cbabab ababab,2.LR（0）項(xiàng)目 活前綴與句柄之間的關(guān)系有三種： 1）活前綴中已含有句柄的全部符號(hào)，表明此時(shí)某一規(guī)則A的右部符號(hào)串已經(jīng)出現(xiàn)在棧頂，其相應(yīng)的分析動(dòng)作是用此規(guī)則規(guī)歸約。 2）活前綴只含有句柄的一部分符號(hào)，此時(shí)意味著形如A12規(guī)則的右部子串1已經(jīng)出現(xiàn)在棧頂，正期待著從剩余的輸入串中進(jìn)行歸約得到2。 3）活前綴全然不含有句柄的任何符號(hào)，此時(shí)意味著期望從剩余的輸入串中能看到有某一規(guī)則A的右部所推出的符號(hào)串。,為了刻畫在分析過(guò)程中，文法的一個(gè)規(guī)則右部符號(hào)串已有多大一部分被識(shí)

33、別，我們可在文法中每個(gè)規(guī)則右部適當(dāng)位置加上一個(gè)圓點(diǎn)來(lái)表示。針對(duì)上面三種情況，標(biāo)有圓點(diǎn)的規(guī)則分別為： A A1 2 A 我們把文法G中右部標(biāo)有圓點(diǎn)的規(guī)則稱為G的一個(gè)項(xiàng)目。對(duì)于空規(guī)則A僅有項(xiàng)目A。 一個(gè)LR（0）項(xiàng)目指明了對(duì)文法規(guī)范句型活前綴的不同識(shí)別狀態(tài)，文法G的全部LR（0）項(xiàng)目是構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA的基礎(chǔ)。,由于不同的LR（0）項(xiàng)目反映了在分析過(guò)程中棧頂?shù)牟煌闆r，因此根據(jù)圓點(diǎn)的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符，將一個(gè)文法全部LR（0）項(xiàng)目進(jìn)行分類： 1）規(guī)約項(xiàng)目，形如A，其中（VT VN ）*，既圓點(diǎn)在最右端的項(xiàng)目，他表示一個(gè)規(guī)則的右部已分析完，句柄已形成，應(yīng)該按此規(guī)則進(jìn)

34、行歸約。 2）移進(jìn)項(xiàng)目，形如Aa，其中， （VT VN ）*，a VT ，既圓點(diǎn)后為終結(jié)符的項(xiàng)目，他表示期待從輸入串中移進(jìn)一個(gè)符號(hào)，以待形成句柄。 3）待約項(xiàng)目，形如AB，其中， （VT VN ）*，B VN ，既圓點(diǎn)后為非終結(jié)符的項(xiàng)目，他表示期待從剩余的輸入串中進(jìn)行歸約而得到B，然后才能繼續(xù)分析A的右部。 4）接受項(xiàng)目，形如SS，其中S為文法的開始符號(hào)，既文法開始符號(hào)的歸約項(xiàng)目。 S為左部的規(guī)則僅有一個(gè)，他是歸約項(xiàng)目的特殊情況，他表示整個(gè)句子已經(jīng)分析完畢，可以接受。,3.項(xiàng)目集： 構(gòu)成識(shí)別文法規(guī)范句型活前綴的DFA的每一個(gè)狀態(tài)是由若干個(gè)LR（0）項(xiàng)目所組成的集合，稱為L(zhǎng)R（0）項(xiàng)目集。 4.

35、項(xiàng)目集的相容性 定義：滿足下列兩個(gè)條件的項(xiàng)目集稱為相容的項(xiàng)目集： ）無(wú)移進(jìn)項(xiàng)目和歸約項(xiàng)目并存 對(duì)于項(xiàng)目集： Aa ，B 對(duì)于棧頂元素，我們無(wú)法確定是進(jìn)行移進(jìn)還是歸約。 )無(wú)多個(gè)歸約項(xiàng)目并存 對(duì)于項(xiàng)目集： A ，B 對(duì)于棧頂元素，我們無(wú)法確定是把它歸約到A還是B。,二、構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA的方法 可以利用閉包函數(shù)（CLOSURE）來(lái)求DFA一個(gè)狀態(tài)的項(xiàng)目集。 為了使“接受”項(xiàng)目唯一，我們可對(duì)文法G進(jìn)行拓廣。假定文法G的開始符號(hào)為S，在文法G中引入一個(gè)新的開始符號(hào)S，，并引進(jìn)規(guī)則S，S,從而得到文法G的拓廣文法G，。 1）定義閉包函數(shù) 設(shè)I是拓廣文法G，的一個(gè)LR（0）項(xiàng)目集，

36、定義和構(gòu)造I的閉包CLOSURE（I）如下： I中的任何一個(gè)項(xiàng)目都屬于CLOSURE（I） 若AB屬于CLOSURE（I），則每一形如Br的項(xiàng)目也屬于CLOSURE（I） 重復(fù)直到CLOSURE（I）不在增大為止。 例：設(shè)有文法GS： 0、SS1、SA2、SB3、AaAb 4、Ac5、BaBa6、Bd 求SS的閉包函數(shù)。,2）定義狀態(tài)轉(zhuǎn)移函數(shù)GO 設(shè)I是拓廣文法G，的一個(gè)LR（0）項(xiàng)目集，X為一文法符號(hào)，定義狀態(tài)轉(zhuǎn)移函數(shù)GO（I，X）如下： GO（ I，X ）= CLOSURE（J） J=AX| AXI 3）構(gòu)造識(shí)別文法規(guī)范句型活前綴的DFA的方法 求CLOSURE（S，S），得到初態(tài)項(xiàng)目集。

37、 對(duì)初態(tài)項(xiàng)目集或其他已構(gòu)造的項(xiàng)目集，應(yīng)用轉(zhuǎn)移函數(shù)GO（I，X）求出新的項(xiàng)目集（后繼狀態(tài)）。 重復(fù)直到不再出現(xiàn)新的項(xiàng)目集（新狀態(tài)）為止。 轉(zhuǎn)移函數(shù)GO建立狀態(tài)之間的連接關(guān)系。 構(gòu)成識(shí)別一個(gè)文法活前綴的DFA的狀態(tài)（項(xiàng)目集）的全體稱為這個(gè)文法的LR（0）項(xiàng)目集規(guī)范族。,4） LR（0）分析表的構(gòu)造 若對(duì)于一個(gè)文法G的拓廣文法G，的LR（0）項(xiàng)目集規(guī)范族的每個(gè)項(xiàng)目集，不存在移進(jìn)項(xiàng)目和規(guī)約項(xiàng)目同時(shí)并存或多個(gè)規(guī)約項(xiàng)同時(shí)共存，則稱G為L(zhǎng)R（0）文法。對(duì)LR（0）文法構(gòu)造LR（0）分析表算法如下： 用整數(shù)0，1，2，n分別表示狀態(tài)I0 ，I1 ，I2 ，In ，令包含S，S項(xiàng)目的集合Ik 的下標(biāo)k為分析器的

38、初態(tài) 若項(xiàng)目Ax屬于Ik ，且轉(zhuǎn)換函數(shù)GO（ Ik ，x） = Ij，當(dāng)x為終結(jié)符時(shí)，則置ACTIONk，x= Sj 若項(xiàng)目A屬于Ik ，則對(duì)任何終結(jié)符和$（統(tǒng)一記為a）置ACTIONk，a= rj ，（假定A 為文法第j條規(guī)則） 若GO（ Ik ，A）= Ij，A為非終結(jié)符，則置 GOTOk，A= j 若項(xiàng)目S，S屬于Ik ，則置ACTIONk， $= acc 分析表中凡不能用規(guī)則至填入信息的元素均置為“出錯(cuò)標(biāo)志”,為了使分析表清晰，僅使用空白表示出錯(cuò)標(biāo)志。,例：設(shè)有文法GS： 1、SA2、SB3、AaAb 4、Ac5、BaBb6、Bd 為了處理方便，我們給上述文法引入一個(gè)新的開始符號(hào)S，且

39、定義： SS 作為第0個(gè)產(chǎn)生式,從而得到原來(lái)的文法的拓廣文法GS： 0、SS1、SA2、SB3、AaAb 4、Ac5、BaBb6、Bd,4.5.3 SLR(1)分析法 例：文法GE E E+T| T T T*F| F F (E)| i 將文法進(jìn)行拓廣并編號(hào)： (0)SE(1)E E+T (2)E T(3)T T*F (4)T F(5)F (E)(6)F i 得到如下DFA和分析表,為了對(duì)句子進(jìn)行確定性分析，需要解決移進(jìn)歸約或歸約歸約沖突，我們采用對(duì)含有沖突的項(xiàng)目集向前查看一個(gè)輸入符號(hào)的辦法來(lái)解決沖突，這種分析法稱為簡(jiǎn)單的LR分析法，即SLR(1)分析法。 出現(xiàn)問(wèn)題的原因：LR分析表構(gòu)造算法的第

40、二條，即對(duì)于每個(gè)項(xiàng)目集IK中的歸約項(xiàng)目A ,不管當(dāng)前輸入符號(hào)是什么，都將ACTION表中第K行的各個(gè)元素均置rj，其中j為規(guī)則A 的編號(hào)，因此假設(shè)有如下項(xiàng)目集： IK=X bB, A ,Br 在分析表第K行中遇到輸入符號(hào)b時(shí)，必然會(huì)出現(xiàn)多重定義元素。 解決辦法：向前查看一個(gè)輸入符號(hào)以考察當(dāng)前所處的環(huán)境，對(duì)歸約項(xiàng)目A 和Br，只需考察將句柄或 r歸約為A或B時(shí)，直接跟在A或B后的終結(jié)符的集合即FOLLOW(A)和FOLLOW(B)互不相交且不包含移進(jìn)符號(hào)b,即滿足：,FOLLOW(A)FOLLOW(B)= FOLLOW(A)b= FOLLOW(B)b= 那么當(dāng)狀態(tài)K面臨輸入符號(hào)aVT$時(shí)，可以按

41、照以下規(guī)則解決沖突： 1)a=b,則移進(jìn)。 2) a FOLLOW(A)，則用規(guī)則A 進(jìn)行歸約。 3) a FOLLOW(B)，則用規(guī)則Br進(jìn)行歸約。 4)此外報(bào)錯(cuò)。,一般而言，若一個(gè)LR(0)項(xiàng)目集I中有m個(gè)移進(jìn)項(xiàng)目和n個(gè)歸約項(xiàng)目時(shí)： I:A 1 a11, A 2 a22, , A m amm, B1r1, B2r2,, Bnrn 對(duì)于所有的移進(jìn)項(xiàng)目向前看一符號(hào)集合a1, a2, , am和FOLLOW(B1), FOLLOW(B2), ,FOLLOW(Bn)兩兩相交為時(shí)，則項(xiàng)目集I中沖突仍可用下述規(guī)則解決沖突。對(duì)當(dāng)前輸入符號(hào)aVT$： 1)a a1, a2, , am,則移進(jìn)。 2) a

42、FOLLOW(Bi)，i=1,2,,3則用規(guī)則Biri進(jìn)行歸約。 3)此外報(bào)錯(cuò)。 這種用來(lái)解決分析動(dòng)作沖突的方法稱為SLR(1)方法。如果對(duì)于一個(gè)文法的某些LR(0)項(xiàng)目集或LR(0)分析表所含有的動(dòng)作沖突都能用SLR(1)方法解決，則稱這個(gè)文法是SLR(1)文法。,SLR(1)分析表的構(gòu)造與LR(0)分析表的構(gòu)造基本相同，僅對(duì)LR(0)分析表的構(gòu)造算法中的規(guī)則2進(jìn)行如下修改： 若項(xiàng)目A屬于Ik ，則對(duì)任何終結(jié)符a FOLLOW(A) , 置ACTIONk，a= rj ，（假定A 為文法第j條規(guī)則）,4.5.4 LR（1）分析法,例：有拓廣文法 0、SS1、SL=R 2、SR3、L*R 4、L

43、i5、RL,L,一個(gè)事實(shí)：如果棧里的符號(hào)串為$，規(guī)約后變?yōu)?，當(dāng)讀到的輸入符號(hào)是a，若文法中不存在以a為前綴的規(guī)范句型，那么這種歸約無(wú)效。 對(duì)上例針對(duì)句型i=i的SLR（1）分析過(guò)程為： S S L=R L=L L=i i=i 狀態(tài)棧 符號(hào)棧 輸入串 0 $ i=i$ 05 $i =i$ 02 $L =i$ 03 $R =i$ 當(dāng)狀態(tài)2呈現(xiàn)于棧頂且面臨的輸入符號(hào)是=時(shí),由于這個(gè)文法不含有以R=為前綴的規(guī)范句型,因此用RL進(jìn)行的歸約是無(wú)效歸約,也就是說(shuō)并不是FOLLOW(R)

44、的每個(gè)元素在含R的所有句型中都會(huì)出現(xiàn)在R的后面.解決這一問(wèn)題的方法是采用LR(1)分析法.,LR(1)分析法的思想是在分析過(guò)程中,當(dāng)試圖用某一規(guī)則A歸約棧頂?shù)姆?hào)串時(shí),不僅應(yīng)該查看棧中符號(hào)串,還應(yīng)向前掃視一個(gè)輸入符號(hào)a,只有當(dāng)a的確構(gòu)成文法某一規(guī)范句型的前綴時(shí),才能用此規(guī)則進(jìn)行歸約。為此可以考慮在原來(lái)LR（0）項(xiàng)目集中增加更多的展望信息，這些信息有助于克服動(dòng)作沖突和排除無(wú)效歸約。也就是需要重新定義稱之為L(zhǎng)R（1）的項(xiàng)目。 一個(gè)LR（1）項(xiàng)目是一個(gè)二元組A，a，其中A是一個(gè)LR（0）項(xiàng)目，每個(gè)a是終結(jié)符且aFollow(A) ，稱為展望符或搜索符。當(dāng)時(shí)，搜索符是無(wú)意義的；當(dāng)=時(shí)，搜索符a明確指出

45、當(dāng)A，a是棧頂狀態(tài)的一個(gè)LR（1）項(xiàng)目時(shí)，僅在輸入符號(hào)是a時(shí)才能用A歸約，而不是對(duì)FOLLOW（A）中的所有符號(hào)都用A歸約。,構(gòu)造LR（1）項(xiàng)目集族的方法： （1）構(gòu)造LR（1）項(xiàng)目集I的閉包函數(shù) I的任何項(xiàng)目都屬于CLOSURE（I） 若項(xiàng)目AB，a，屬于CLOSURE（I）， Br是文法的一條規(guī)則，bFIRST（ a），則Br，b也屬于CLOSURE（I） 重復(fù)直到CLOSURE（I）不在增大為止。,（2）構(gòu)造轉(zhuǎn)換函數(shù) 令I(lǐng)是一個(gè)LR（1）項(xiàng)目集，X是一個(gè)文法符號(hào)，函數(shù) GO（ I，X ）= CLOSURE（J） J=AX，a| AX，aI （3）構(gòu)造DFA同LR（0）分析法相同（注：構(gòu)造

46、初態(tài)是從基本項(xiàng)目SS，$開始的） （4）構(gòu)造LR（1）分析表的方法與構(gòu)造LR（0）分析表的方法基本相同，僅對(duì)歸約項(xiàng)目作如下修改： 若歸約項(xiàng)目A，a屬于Ik，則對(duì)搜索符a置ACTIONk，a= rj，（假定A 為文法第j條規(guī)則）,2.5.5 LALR(1)分析法,LALR（1）分析法是界于SLR（1）和LR（1）分析法之間的一種語(yǔ)法分析方法，這種分析法能解決SLR（1）分析法所不能解決的沖突動(dòng)作，并且其分析表的狀態(tài)個(gè)數(shù)與SLR（1）相同。 LALR（1）分析法的基本思想是將LR（1）項(xiàng)目集規(guī)范族中所有同心的項(xiàng)目集合并為一，以減少項(xiàng)目集個(gè)數(shù)。所謂同心的LR（1）項(xiàng)目集是指在兩個(gè)LR（1）項(xiàng)目集中，

47、除搜索符不同之外，核心部分相同。,I4： L* R, =/$ R L, =/ $ L *R ,=/ $ L i, =/ $ I5： L i , =/ $ I12： L i , $ I7 ： L*R , =/ $ I13 L*R , $ I8 ： RL , =/ $ I10 ： R L, $ 將同心集合并為(合并時(shí)核心部分保持不變，僅搜索符合并)： I 4,11：L* R, =/$ I 5,12：L i , =/$ R L, =/$ I 7,13 ：L*R , =/$ L *R ,=/$ I 8 ,10

48、： RL , =/$ L i, =/$,I11：L* R, $ R L, $ L *R , $ L i, $,對(duì)合并同心集后的項(xiàng)目集的轉(zhuǎn)換函數(shù)為GO（I，X）自身的合并，這是因?yàn)橄嗤牡霓D(zhuǎn)換函數(shù)仍屬同心集。 GO（I4，11，i）= GO（I4，i） GO（I11，i）= I5 I12 = I5，12 GO（I4，11，R）= GO（I4，R） GO（I11，R）= I7 I13= I7，13 GO（I4，11，*）= GO（I4，*） GO（I11，*）= I4 I11 = I4，11 對(duì)于LALR（1）項(xiàng)目集族，有以下若干事實(shí)： 1.盡管原來(lái)各LR（1）項(xiàng)目集均不存在沖突，但

49、合并同心集后就有可能出現(xiàn)沖突，但由此引入的沖突只能是歸約歸約沖突，決不會(huì)是移進(jìn)歸約沖突。 Ik：A，W1 Ij：A，W2 Aa，b Aa，c 設(shè)Ik與Ij均無(wú)沖突故有：W1a=， W2a= 從而（W1W2 ）a= 將Ik與Ij合并，有Ik,j：A， W1W2 Aa，bc 若有移進(jìn)歸約沖突，則有（W1W2 ）a與假設(shè)矛盾，故僅有歸約歸約沖突。,2.對(duì)一給定文法而言，其LALR（1）分析表比LR（1）分析表狀態(tài)要少 3.在分析文法G的某一個(gè)含有錯(cuò)誤的符號(hào)時(shí)， LALR（1）分析速度比LR（1）分析速度慢。 構(gòu)造LALR（1）分析表的方法： 1）構(gòu)造拓廣文法G，的LR（1）項(xiàng)目集族 2）若LR（1）項(xiàng)目集族不含沖突的項(xiàng)目集，則合并所有同心集構(gòu)造出文法的LALR（1）項(xiàng)目集族 3）若LALR（1）項(xiàng)目集族中不存在歸約歸約沖突，則該文法是LALR（1）文法 4） LALR（1）項(xiàng)目集族構(gòu)造該文法的LALR（1）分析表的方法與LR（1）分析表的構(gòu)造方法相同。,