編譯原理語法分析

1、編譯原理語法分析第1頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 自下而上分析法是一種移進(jìn)-歸約法。分析過程中采用了一個(gè)FIFO分析棧。分析開始后，把輸入符號(hào)自左至右逐個(gè)移進(jìn)分析棧，邊移入邊分析，一旦棧頂符號(hào)串形成句柄就進(jìn)行一次歸約，再繼續(xù)查看棧頂是否形成新的句柄，若仍為句柄，則再歸約，如此重復(fù)直至棧頂不是句柄。此時(shí)再繼續(xù)向棧中移進(jìn)后續(xù)輸入符號(hào)。重復(fù)該過程，直到將整個(gè)輸入串處理完畢。若此時(shí)分析棧只有文法開始符，則輸入串是一個(gè)句子，否則輸入串有錯(cuò)。 第2頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 下面通過例子說明這種分析過程。 文法GS：SaAbB AcAc B

2、d 試對(duì)輸入串a(chǎn)ccbd進(jìn)行分析，檢查該 符號(hào)串是否是GS的一個(gè)句子。 假設(shè)“#”為輸入串界符，將輸入串前的“#”放入分析棧，接著將輸入串的符號(hào)依次進(jìn)棧，具體分析過程如下:第3頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二步驟分析棧句柄輸入串動(dòng) 作1#accbd#移進(jìn)2#accbd#移進(jìn)3#accbd#移進(jìn)4#aAccbd#歸約(用Ac)5#aAcbd#移進(jìn)6#aAAcbd#歸約(用AAc)7#aAbd#移進(jìn)8#aAbd#移進(jìn)9#aAbBd#歸約(Bd)10#SaAbB#歸約(SaAbB)第4頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二SaccbdABA(d)ac

3、cbdABA(c)accAA(b)acA(a) 在自下而上分析過程中，每一步歸約都可畫出一棵子樹，隨著歸約的完成，這些子樹連成一棵完整的分析樹。上述分析過程可用分析樹表示如下:第5頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 由上述建樹過程知，自下而上分析過程的每一步歸約都是對(duì)當(dāng)前句型的句柄進(jìn)行歸約，即句柄一旦形成總是出現(xiàn)在分析棧棧頂。由于每一步歸約都把棧頂符號(hào)串用某產(chǎn)生式左部符號(hào)替換，故把棧頂?shù)倪@樣一串符號(hào)稱為可歸約串。 上述第6步若不選AAc而選Ac進(jìn)行歸約，則無法歸約到S。如何確知棧頂?shù)腁c是可歸約串而c不是呢？這需精確定義“可歸約串”的概念。第6頁，共108頁，2022

4、年，5月20日，20點(diǎn)34分，星期二 若文法GS是無二義文法，則規(guī)范推導(dǎo)的逆過程必是規(guī)范歸約(最左歸約)。 對(duì)于移進(jìn)-歸約過程，句柄的最左性和分析棧棧頂相關(guān)。對(duì)于規(guī)范推導(dǎo)所得句型(規(guī)范句型)，句柄后面不會(huì)出現(xiàn)非終結(jié)符，故可用句柄刻畫“可歸約串”，規(guī)范歸約的實(shí)質(zhì)是在移進(jìn)過程中當(dāng)棧頂呈現(xiàn)句柄時(shí)進(jìn)行歸約。第7頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 為加深對(duì)句柄和歸約等概念的理解，用修剪語法樹方法進(jìn)一步闡明自下而上分析過程。 語法樹的一個(gè)子樹由該樹的某結(jié)點(diǎn)及其所有子孫組成，子樹的所有葉結(jié)點(diǎn)的自左至右排列形成一個(gè)相對(duì)于子樹根的短語。一個(gè)句型的句柄是該句型對(duì)應(yīng)的語法樹中最左簡(jiǎn)單子樹的

5、所有樹葉的自左至右排列。第8頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 可采用修剪語法樹方法實(shí)現(xiàn)歸約，即尋找當(dāng)前語法樹的句柄，將句柄中的樹葉剪去(歸約)，不斷修剪直到只剩根結(jié)點(diǎn)，完成整個(gè)歸約過程：SaAbBAcdcSaAbBAcdSaAbBdSaAbBS第9頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 至此討論了句柄和規(guī)范歸約這兩個(gè)基本概念，但并沒有解決規(guī)范歸約的問題，因?yàn)闆]有給出尋找句柄的算法。事實(shí)上，規(guī)范歸約的中心問題就是如何尋找句柄。尋找句柄的不同算法對(duì)應(yīng)不同的規(guī)范歸約方法，這一點(diǎn)將在LR分析器中討論。第10頁，共108頁，2022年，5月20日，20點(diǎn)

6、34分，星期二 算符優(yōu)先分析法是一種簡(jiǎn)單直觀、廣為使用的自下而上分析法，特別適合于表達(dá)式分析且宜于手工實(shí)現(xiàn)。它實(shí)際上是依照表達(dá)式四則運(yùn)算過程來進(jìn)行語法分析。 所謂算符優(yōu)先分析，就是預(yù)先規(guī)定運(yùn)算符(確切地說是終結(jié)符)之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，借助于這種優(yōu)先關(guān)系來比較相鄰運(yùn)算符的優(yōu)先級(jí)，以確定句型的可歸約串并進(jìn)行歸約。 注意：算符優(yōu)先分析不是規(guī)范歸約。3.4.2 算符優(yōu)先分析法第11頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 1. 算符優(yōu)先文法 算符文法: 若一個(gè)文法的任一產(chǎn)生式的 右部都不含兩個(gè)相繼的非終結(jié)符， 即不含QR這樣的右部，則稱 該文法為算符文法。 算符優(yōu)先文法: 算

7、符優(yōu)先文法首先應(yīng)是算符文法, 其次還要定義任意兩個(gè)可能相繼 出現(xiàn)的終結(jié)符的優(yōu)先關(guān)系。 具體定義如下:第12頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二假定G是一個(gè)不含產(chǎn)生式的算符文法, 對(duì)任一對(duì)終結(jié)符a,b, 定義(1) a=b當(dāng)且僅當(dāng)文法G中含有形如 Pab 或 PaQb的產(chǎn)生式;(2) ab當(dāng)且僅當(dāng)G中含有形如 PRb的產(chǎn)生式， 而R a 或 R aQ。+第13頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二若一個(gè)算符文法G中任一終結(jié)符對(duì)(a,b) 至多滿足下述三種關(guān)系之一 : a=b，ab則稱文法G是一個(gè)算符優(yōu)先文法。例3.10 試說明下述文法G是算符文法，

8、但不是算符優(yōu)先文法。 EE+EE*E(E)i解: 由于文法G的任一產(chǎn)生式右部都不 含兩個(gè)相鄰的非終結(jié)符， 故文法G是算符文法。第14頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 (1)由于存在EE+E，而E+E中第二 個(gè)E可推出E*E，故有+* 可見, 運(yùn)算符+和*之間同時(shí)存在兩種不同的優(yōu)先關(guān)系，故文法G不是算符優(yōu)先文法。第15頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二2. 算符優(yōu)先關(guān)系表的構(gòu)造 通過檢查文法的每個(gè)產(chǎn)生式的各個(gè)侯選式,可找出所有滿足a=b的終結(jié)符對(duì)。 為找出所有滿足關(guān)系 “”的終結(jié)符對(duì),需先對(duì)文法的每個(gè)非終結(jié)符P構(gòu)造兩個(gè)集合FIRSTVT(P)

9、和LASTVT(P): FIRSTVT(P)=a | P a或 P Qa, aVT而QVN LASTVT(P)=a | P a或 P aQ, aVT而QVN+第16頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二FIRSTVT集的構(gòu)造方法：(1)若有產(chǎn)生式Pa或PQa， 則aFIRSTVT(P)；(2)若有產(chǎn)生式PQ,且aFIRSTVT(Q), 則aFIRSTVT(P)。第17頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例如 試構(gòu)造文法GE的FIRSTVT集。 GE: EE+TT TT*FF F(E)i解: 根據(jù)規(guī)則(1)知： 由EE+得, FIRSTVT(E)=+

10、； 由TT*得, FIRSTVT(T)=*； 由F(和Fi得,FIRSTVT(F)=(,i 根據(jù)規(guī)則(2)知： 由TF和FIRSTVT(F)=(,i得, FIRSTVT(T)=*, (, i； 由ET和FIRSTVT(T)得, FIRSTVT(E)=+, *, (, i第18頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二LASTVT集構(gòu)造方法：(1)若有產(chǎn)生式Pa或PaQ， 則aLASTVT(P)；(2)若有產(chǎn)生式PQ,且 aLASTVT(Q), 則aLASTVT(P)。第19頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例如 試構(gòu)造文法GE的LASTVT集。 GE

11、: EE+TT TT*FF F(E)i解: 根據(jù)規(guī)則(1)知： 由E+T得, LASTVT(E)=+ 由T*F得, LASTVT(T)=* 由F)和Fi得,LASTVT(F)=),i 根據(jù)規(guī)則(2)知： 由TF和LASTVT(F)得, LASTVT(T)=*, ), i; 由ET和LASTVT(T)得, LASTVT(E)=+, *, ), i。第20頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二構(gòu)造優(yōu)先關(guān)系表的方法：(1) 對(duì)形如Pab或PaQb的 產(chǎn)生式, 有a=b；(2) 對(duì)形如PaR的產(chǎn)生式, 若 bFIRSTVT(R), 則ab。(4) 對(duì)于語句括號(hào)#,有 # = #

12、# #第21頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例3.11 構(gòu)造文法GE的算符優(yōu)先關(guān)系表。 GE: EE+TT TT*FF F(E)i解: 構(gòu)造FIRSTVT集 根據(jù)規(guī)則(1)知： 由EE+得, FIRSTVT(E)=+； 由TT*得, FIRSTVT(T)=*； 由F(和Fi得,FIRSTVT(F)=(,i 根據(jù)規(guī)則(2)知： 由TF和FIRSTVT(F)=(,i得, FIRSTVT(T)=*, (, i； 由ET和FIRSTVT(T)得, FIRSTVT(E)=+, *, (, i第22頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二構(gòu)造LASTVT集根

13、據(jù)規(guī)則(1)知： 由E+T得, LASTVT(E)=+； 由T*F得, LASTVT(T)=*； 由F)和Fi得,LASTVT(F)=),i。根據(jù)規(guī)則(2)知： 由TF和LASTVT(F)得, LASTVT(T)=*, ), i; 由ET和LASTVT(T)得, LASTVT(E)=+, *, ), i。第23頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二構(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知, (

14、FIRSTVT(E), 即( +, ( *, ( (, ( +， 即+ +，* +，) +，i + 由TT*知, LASTVT(T)*， 即* *，) *，i * 由FE)知, LASTVT(E)， 即+ )，* )，) )，i )由#E#知, # = #； #FIRSTVT(E), 即#+,#*,#(,#, 即+#,*#,)#,i#第25頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二故算術(shù)表達(dá)式文法的優(yōu)先關(guān)系表如下:+*i()#+*i(#=第26頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二3. 算符優(yōu)先分析算法的設(shè)計(jì) 由于算符優(yōu)先分析法僅在終結(jié)符之間定義了優(yōu)先關(guān)

15、系而未對(duì)非終結(jié)符定義優(yōu)先關(guān)系，這就無法使用優(yōu)先關(guān)系表去識(shí)別由單個(gè)非終結(jié)符組成的可歸約串，因此算符優(yōu)先分析法不是用句柄而是用最左素短語來刻畫“可歸約串” 。 所謂句型的素短語是指這樣一種短語,它至少包含一個(gè)終結(jié)符且除自身外不再包含其它更小的素短語。最左素短語是處于句型最左邊的那個(gè)素短語。第27頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二如何讓計(jì)算機(jī)尋找最左素短語？算符優(yōu)先文法的句型的一般形式為 # N1a1N2a2NnanNn+1# 其中, ai是終結(jié)符, Ni是可有可無的 非終結(jié)符。算符優(yōu)先文法任一句型的最左素短語是滿足下述條件的最左子串: NjajNj+1aj+1 Niai

16、Ni+1 aj-1ai+1第28頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二查找最左素短語的方法：(1) 最左子串法 先找出句型中終結(jié)符由左至右滿足aj-1ai+1的最左子串。 再檢查文法的每個(gè)候選式,看其是否滿足:所有終結(jié)符由左至右的排列恰為ajaj+1ai, 即終結(jié)符對(duì)應(yīng)相等而非終結(jié)符僅對(duì)應(yīng)位置相同。若存在這樣的候選式, 則用該候選式進(jìn)行歸約。第29頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 (2) 語法樹法 先畫出句型的語法樹, 再找語法樹中所有相鄰終結(jié)符間的優(yōu)先關(guān)系。 確定相鄰終結(jié)符間優(yōu)先關(guān)系的原則: 語法樹中同層的優(yōu)先關(guān)系為“= ”; 不同層時(shí), 層

17、次在下的優(yōu)先級(jí)高, 層次在上的優(yōu)先級(jí)低; 在句型兩側(cè)加上語句括號(hào)“#”, 則有#。 最后按最左素短語必須具備的條件 確定最左素短語。第30頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例3.12 文法GE: EE+T | T TT*F | F F(E) | i 試確定F+T*i的最左素短語。 解:畫句型F+T*i的語法樹, 根據(jù)語法樹確定相鄰終 結(jié)符間優(yōu)先關(guān)系如圖, 故最左素短語為i。 注意:最左直接短語為FEEE*TFTiF#*i#第31頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二算符優(yōu)先分析算法: k=1; Sk=#; /k代表?xiàng)的使用深度 doa=下一個(gè)輸

18、入符; if (SkVT) j=k;else j=k1; /j指棧頂終結(jié)符 while (Sja) /找最左Sja doQ=Sj; /j從最左素短語末逐步移向首 if (Sj1VT) j=j1; else j=j2; while (Sj=Q); 把Sj+1Sk歸約為某個(gè)N; k=j+1; Sk=N; /把N置于原Sj+1位置 if (Sja) | (Sj=a) k=k+1; Sk=a; else error( ); /若棧頂Sja或=a則將a壓棧 while (a!=#);第32頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 上述算法工作過程中, 若出現(xiàn)j減1后其值小于等于0,

19、則意味著輸入串有錯(cuò)。正確情況下, 算法工作完畢時(shí)符號(hào)棧將呈現(xiàn)#S#。例3.13 文法GE及其優(yōu)先關(guān)系如例3.12 所示, 試給出輸入串i+i*i的算符優(yōu)先 分析過程。解: 輸入串i+i*i的算符優(yōu)先分析過程如下:第33頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二符號(hào)棧輸入串 動(dòng) 作#i+i*i#i#i+i*i#+, 用Fi歸約#F+i*i#+#F+i*i#+i#F+i*i#+*, 用Fi歸約#F+F*i#+*#F+F*i#+*i#F+F*i#*#, 用Fi歸約#F+F*F#+#, 用TT*F歸約#F+T#, 用EE+T歸約#E#E# 結(jié)束第34頁，共108頁，2022年，5月2

20、0日，20點(diǎn)34分，星期二 算符優(yōu)先分析的歸約只關(guān)心句型中由左至右終結(jié)符序列的優(yōu)先關(guān)系,不涉及非終結(jié)符。再以i+i為例, 給出其算符優(yōu)先分析過程和規(guī)范歸約過程。 算符優(yōu)先分析比規(guī)范歸約要快得多。這既是算符優(yōu)先分析的優(yōu)點(diǎn),也是它的缺點(diǎn),因?yàn)檫@可能把本來不成句子的輸入串誤認(rèn)為是句子,這種缺點(diǎn)易于彌補(bǔ)。 第35頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例3.14 試設(shè)計(jì)下述文法的算符優(yōu)先分析表: GS: SiBtSiBtAeSa AiBtAeSa Bb解: 首先構(gòu)造FIRSTVT集和LASTVT集 FIRSTVT(S)=i,a; FIRSTVT(A)=i,a; FIRSTVT(B)

21、=b; LASTVT(S)=t,e,a; LASTVT(A)=e,a; LASTVT(B)=b; 由AS知, LASTVT(S)LASTVT(A) 即 LASTVT(A)=t,e,a第36頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二然后構(gòu)造優(yōu)先關(guān)系表:(1)由產(chǎn)生式SiBtAeS和SiBtS可知: 由SiB得, it； 由StA得, te； 由SeS得, eFIRSTVT(S)； 由SiBt得, i=t； 由StAe得, t=e； 由StS得, te和t=e, 由iBtAeS知, 此時(shí)應(yīng) 將iBtAeS同時(shí)歸約為S或A,即取t=e。第37頁，共108頁，2022年，5月20日，

22、20點(diǎn)34分，星期二最后得到優(yōu)先關(guān)系表如下:iteabiteb=第38頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二4. 優(yōu)先函數(shù) 用優(yōu)先關(guān)系表表示終結(jié)符間的優(yōu)先關(guān)系時(shí),存儲(chǔ)量大,查找費(fèi)時(shí)。若給終結(jié)符賦一個(gè)值,值的大小反映其優(yōu)先關(guān)系,則終結(jié)符間的優(yōu)先關(guān)系比較就轉(zhuǎn)為值的比較。 一個(gè)終結(jié)符在棧中與在輸入串中的優(yōu)先值不同,例如,既存在+),又存在)+。因此,對(duì)一個(gè)終結(jié)符a而言,它應(yīng)該有一個(gè)左優(yōu)先數(shù)f(a)和一個(gè)右優(yōu)先數(shù)g(a)。 第39頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 若根據(jù)一個(gè)文法的算符優(yōu)先關(guān)系表,使得文法中每個(gè)終結(jié)符a和b滿足下述條件: (1)若存在a=

23、b，則有f(a)=g(b)； (2)若存在ab，則有f(a)g(b)； (3)若存在ab=第41頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 根據(jù)優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)f和g的方法有兩種: 關(guān)系圖法、直接構(gòu)造法 (1)用關(guān)系圖法構(gòu)造優(yōu)先函數(shù)的步驟 對(duì)每個(gè)終結(jié)符a(包括“#”),令其對(duì)應(yīng)兩個(gè)符號(hào)fa和ga, 畫一張以所有fa和ga為結(jié)點(diǎn)的方向圖： 若ab或a=b,畫一條從fa到gb的有向邊; 若ab而f(a)g(b), 則令f(a)=g(b)+1； 若a*i(#=第45頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二解: (1)用關(guān)系圖法構(gòu)造的優(yōu)先關(guān)系圖如下:ff*f

24、if)gg*gig(g)f(第46頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二+ * i ( )f4 6 6 2 6g3 5 7 7 2由上圖求得優(yōu)先函數(shù)如下:第47頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二迭代函數(shù)函數(shù)+*i()0(初值)f11111g111111f24414g235512f35515g246613f35515g24661(2)由定義直接計(jì)算優(yōu)先函數(shù)的過程如下:第48頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二3.5 LR分 析 法 LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語法分析方法, L指自左向右掃描輸入串, R指最右推導(dǎo)(

25、規(guī)范歸約)。 LR分析法比遞歸下降分析法、LL(1)分析法對(duì)文法的限制要少得多, 大多數(shù)無二義性CFG語言都可用LR分析器識(shí)別, 且速度快, 并能準(zhǔn)確、指出輸入串的語法錯(cuò)誤及出錯(cuò)位置。 LR分析法的主要缺點(diǎn): 手工構(gòu)造工作量相當(dāng)大, 必須求助自動(dòng)產(chǎn)生工具。第49頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二3.5.1 LR分析器的工作原理 規(guī)范歸約(最右推導(dǎo)逆過程)的關(guān)鍵是尋找句柄。LR分析法的基本思想:在規(guī)范歸約過程中,一方面記住已移進(jìn)和歸約出的符號(hào)串,即記住“歷史”; 另一方面根據(jù)所用產(chǎn)生式推測(cè)未來可能遇到的輸入符,即對(duì)未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號(hào)串呈現(xiàn)于分析棧棧頂

26、時(shí),希望能根據(jù)所記載的“歷史”、“展望”及“現(xiàn)實(shí)”材料來確定棧頂符號(hào)是否構(gòu)成句柄。 第50頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 LR分析器的結(jié)構(gòu)示意如下所示,它由分析棧、分析表和總控程序三部分組成:a1a2aian#LR分析表總控程序輸入串：棧頂#x1xm輸出s0s1sm分析棧第51頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出棧的DFA?！皻v史”和“展望”材料被抽象成某些“狀態(tài)”,而分析棧用來存放這些狀態(tài),棧里的每個(gè)狀態(tài)概括了從分析開始直到某一歸約階段的全部“歷史”和“展望”資料。任何時(shí)候,棧頂?shù)臓顟B(tài)都代表了整個(gè)“歷史”

27、和已推測(cè)出的“展望”。第52頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 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)串X1X2Xm是已移進(jìn)歸約出的文法符號(hào)串。第53頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 LR分析表是LR分析器的核心, 它包括兩部分: 動(dòng)作表(ACTION表) (二維數(shù)組) 狀態(tài)轉(zhuǎn)換表(GOTO表)(二維數(shù)組) ACTIONs,a規(guī)定了狀態(tài)s面臨輸入符a時(shí)應(yīng)采取

28、的動(dòng)作。GOTOs,X規(guī)定了狀態(tài)s面對(duì)文法符號(hào)X(終結(jié)符或非終結(jié)符)時(shí)的下一狀態(tài)。顯然, GOTOs,X定義了一個(gè)以文法符號(hào)為字母表的DFA。第54頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二ACTIONs,a的動(dòng)作:(1)移進(jìn): 使(s,a)的下一狀態(tài)s=GOTOs,a和 輸入符a進(jìn)棧,下一輸入符變現(xiàn)行輸入符。 注:對(duì)終結(jié)符a,下一狀態(tài)s的值GOTOs,a 實(shí)際上放在ACTIONs,a中(2)歸約: 用某一產(chǎn)生式A進(jìn)行歸約。 若的長度為,則歸約動(dòng)作是去掉棧頂 的個(gè)項(xiàng),使?fàn)顟B(tài)sm-變成棧頂狀態(tài),然后 使(sm-,A)的下一狀態(tài)s=GOTOsm-,A 和文法符號(hào)A進(jìn)棧。 歸約不改

29、變現(xiàn)行輸入符。執(zhí)行歸約意味 著棧頂符號(hào)串Xm-+1Xm是句柄。 第55頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二(3)接受: 宣布分析成功,分析器停止工作。(4)報(bào)錯(cuò): 報(bào)告發(fā)現(xiàn)源程序有錯(cuò),調(diào)用出錯(cuò)處 理程序。LR分析器總控程序的工作十分簡(jiǎn)單,它的任一步只需按分析棧棧頂狀態(tài)s和現(xiàn)行輸入符a執(zhí)行ACTIONs,a所規(guī)定的動(dòng)作。LR分析器的工作過程可看成是棧中狀態(tài)序列、已歸約串和輸入串構(gòu)成的三元式的變化過程。第56頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例如, 算術(shù)表達(dá)式文法GE如下: GE: (1) EE+T (2) ET (3) TT*F (4) TF (

30、5) F(E) (6) Fi文法GE的LR分析表見表3.13, 試給出語句i+i*i的LR分析過程。第57頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二表3.13 算術(shù)表達(dá)式文法的LR分析表狀態(tài)ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5第58頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二步驟狀態(tài)棧符號(hào)棧輸入串動(dòng) 作 說 明10#i+i*i#ACTION0,i=s5,狀態(tài)5入棧2

31、0 5# i+i*i#r6:Fi歸約,GOTO(0,F)=3入棧30 3# F+i*i#r4:TF歸約,GOTO(0,T)=2入棧40 2# T+i*i#r2:ET歸約,GOTO(0,E)=1入棧50 1# E+i*i#ACTION1,+=s6,狀態(tài)6入棧60 1 6# E+i*i#ACTION6,i=s5,狀態(tài)5入棧表3.14 i+i*i的LR分析過程第59頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二70 1 6 5# E+i*i#r6:Fi歸約,GOTO(6,F)=3入棧80 1 6 3# E+F*i#r4:TF歸約,GOTO(6,T)=9入棧90 1 6 9# E+T*i

32、#ACTION9,*=s7, 狀態(tài)7入棧100 1 6 9 7#E+T*i#ACTION7,i=s5,狀態(tài)5入棧110 1 6 9 7 5# E+T*i#r6:Fi歸約,GOTO(7,F)=10入棧12016 9 7 10# E+T*F#r3:TT*F歸,GOTO(6,T)=9入棧130 1 6 9# E+T#r1:EE+T,GOTO(0,E)=1入棧140 1# E#Acc: 分析成功第60頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二如何由文法構(gòu)造LR分析表? LR文法: 對(duì)于一個(gè)文法, 如果能夠構(gòu)造一張LR分析表使得它的每個(gè)入口均是唯一確定的, 則稱該文法為LR文法。 對(duì)于

33、LR文法, 當(dāng)分析器對(duì)輸入串進(jìn)行自左至右掃描時(shí), 一旦句柄呈現(xiàn)于棧頂, 能及時(shí)對(duì)它實(shí)行歸約。 有些情況下LR分析器需“展望”和實(shí)際檢查未來的k個(gè)輸入符才能決定應(yīng)采取什么樣的“移進(jìn)-歸約”決策。第61頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 LR(k)文法: 一個(gè)文法如果能用一個(gè)每步最多向前檢查k個(gè)輸入符的LR分析器進(jìn)行分析, 則稱該文法為LR(k)文法。 若一個(gè)文法的任何“移進(jìn)-歸約”分析器都存在下述情況: 盡管棧的內(nèi)容和下一輸入符都已了解, 但仍無法確定是“移進(jìn)”還是“歸約”, 或無法從幾種可能的歸約中確定其一, 則該文法為非LR(1)文法。 注意: (1) LR文法肯定

34、是無二義的, 一個(gè)二義文法不會(huì)是LR文法。(2) LR分析技術(shù)可適當(dāng)修改以適于一定的二義文法。第62頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二四種LR分析表的構(gòu)造方法: (1) LR(0)表的構(gòu)造方法: 該法局限性很大, 但它是建立一般LR分析表的基礎(chǔ)。 (2)SLR(1)表(簡(jiǎn)單LR表)的構(gòu)造方法: 該法較易實(shí)現(xiàn)又極有使用價(jià)值。 (3)LR(1)表(規(guī)范LR表)的構(gòu)造方法: 該法適用于大多數(shù)CFG文法,但分析表 體積龐大。 (4)LALR表(向前LR表)的構(gòu)造方法: 該法介于SLR(1)和LR(1)之間。第63頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二3.

35、5.2 LR(0)分析表的構(gòu)造 希望僅由一種只概括“歷史”資料而不包含推測(cè)性“展望”材料的簡(jiǎn)單狀態(tài)就能識(shí)別呈現(xiàn)在棧頂?shù)哪承┚浔?，LR(0)項(xiàng)目集就是這樣一種簡(jiǎn)單狀態(tài)。 討論LR分析法時(shí),需要定義一個(gè)重要概念,這就是文法規(guī)范句型的活前綴。字的前綴是指該字的任意首部,例如,字abc的前綴有、a、ab或abc。 所謂活前綴是指規(guī)范句型的一個(gè)前綴, 這種前綴不含句柄之后的任何符號(hào)。第64頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 在LR分析過程中的任何時(shí)候，棧里的文法符號(hào)X1X2Xm應(yīng)構(gòu)成活前綴。把輸入串的剩余部分匹配于其后應(yīng)成為規(guī)范句型(如果整個(gè)輸入串確為一個(gè)句子的話)。因此，只要

36、輸入串的已掃描部分保持可歸約成一個(gè)活前綴，就意味著所掃描的部分沒有錯(cuò)誤。第65頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 對(duì)于文法GS,首先要構(gòu)造一個(gè)NFA,它能識(shí)別GS的所有活前綴,這個(gè)NFA的每個(gè)狀態(tài)稱為一個(gè)項(xiàng)目。 項(xiàng)目:文法GS中每一產(chǎn)生式的右部添加一個(gè)圓點(diǎn),稱為文法GS的一個(gè)LR(0)項(xiàng)目, 簡(jiǎn)稱項(xiàng)目。 例如,產(chǎn)生式AXYZ對(duì)應(yīng)四個(gè)項(xiàng)目： AX Y Z A XY Z A X YZ A X Y Z注意,產(chǎn)生式A只對(duì)應(yīng)一個(gè)項(xiàng)目A第66頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 一個(gè)項(xiàng)目指明了在分析過程的某個(gè)時(shí)刻看到產(chǎn)生式的多大一部分。 通過使用文法的項(xiàng)目

37、可構(gòu)造一個(gè)NFA來識(shí)別文法的所有活前綴，再用子集法把識(shí)別活前綴的NFA確定化，使之成為一個(gè)以項(xiàng)目集合為狀態(tài)的DFA，這個(gè)DFA就是建立LR分析算法的基礎(chǔ)。第67頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 識(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)目; 形如Aa的項(xiàng)目(a為終結(jié)符),稱為移進(jìn)項(xiàng)目; 形如AB的項(xiàng)目(B為非終結(jié)符)，稱為待約項(xiàng)目。第68頁，共108頁，2022年，5月

38、20日，20點(diǎn)34分，星期二1. LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 可用_CLOSURE構(gòu)造一個(gè)文法的LR(0)項(xiàng)目集規(guī)范族。 首先構(gòu)造文法GS的拓廣文法GS，它包含整個(gè)GS并引進(jìn)一個(gè)不出現(xiàn)在GS中的非終結(jié)符S，同時(shí)加進(jìn)了一個(gè)新產(chǎn)生式SS。這樣，僅含項(xiàng)目SS的狀態(tài)是唯一的接受狀態(tài)。第69頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 假定I是文法GS的任一項(xiàng)目集, 定義和構(gòu)造CLOSURE(I)的方法: (1)I的任何項(xiàng)目都屬于CLOSURE(I)； (2)若AB屬于CLOSURE(I)， 則對(duì)任何關(guān)于B的產(chǎn)生式B, 其項(xiàng)目B屬于CLOSURE(I)。 (3)重復(fù)(1)(2)直至CL

39、OSURE(I)不再 增大為止。第70頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 假定I是文法GS的任一項(xiàng)目集,X是一個(gè)文法符號(hào)(終結(jié)符或非終結(jié)符),則狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)的定義為 GO(I,X)=CLOSURE(J) 其中J=任何形如AX的項(xiàng)目 | AX屬于I。 若I是對(duì)某個(gè)活前綴有效的項(xiàng)目集(狀態(tài)), 則GO(I,X)是對(duì)X有效的項(xiàng)目集(狀態(tài))。第71頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 通過CLOSURE(I)和GO(I,X)構(gòu)造拓廣文法GS的LR(0)項(xiàng)目集規(guī)范族的方法: (1)求出I的閉包CLOSURE(I) (2)先用GO(I,X)求

40、出J, 再對(duì)J求其閉包CLOSURE(J)。 以此類推, 最終可構(gòu)造出拓廣文法GS的LR(0)項(xiàng)目集規(guī)范族。第72頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二2. LR(0)分析表的構(gòu)造 若文法GS的拓廣文法GS的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)(項(xiàng)目集)不存在下述情況：既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目或含有多個(gè)歸約項(xiàng)目,則GS是一個(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)構(gòu)造出其LR(0)分析表。第73頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 假定C=

41、I0,I1,In, 令每個(gè)項(xiàng)目集Ik的下標(biāo)k作為分析器的狀態(tài), 并令包含項(xiàng)目SS的集合Ik的下標(biāo)k為分析器的初態(tài), 則LR(0)分析表的構(gòu)造算法如下: (1)若項(xiàng)目Aa屬于Ik且 GO(Ik,a)=Ij, a為終結(jié)符, 則置ACTIONk,a為“將(j,a)移進(jìn) 棧”, 簡(jiǎn)記為sj。第74頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 (2)若項(xiàng)目A屬于Ik, 則對(duì)任何終結(jié)符a或#,置 ACTIONk,a為“用A歸約”, 簡(jiǎn)記為rj(其中j是第j個(gè)產(chǎn)生式。 (3)若項(xiàng)目SS屬于Ik, 則置ACTIONk,#為接受,簡(jiǎn)記acc。 (4)若GO(Ik,A)=Ij, A為非終結(jié)符,則置

42、 GOTOk,A=j。 (5)分析表中凡不能用規(guī)則(1)(4)填 入的空白格均置為“出錯(cuò)標(biāo)志”。第75頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例3.16 試構(gòu)造文法GS的LR(0)分析表: GS: SBB BaBb 解: 將文法GS拓廣為文法GS： GS: (0) SS (1) SBB (2) BaB (3) Bb第76頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二該文法的LR(0)項(xiàng)目集規(guī)范族為: I0: SS SBB BaB Bb I1: SS I2: SBB BaB Bb I3: BaB BaB Bb I4: Bb I5: SBB I6: BaB 第77

43、頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二S I0:SSSBB BaB Bb I1:SSS I2:SBBBaBBb I5:SBBB I4:B bbb I3:BaBBaBBbab I6:B aBBaa識(shí)別該文法活前綴的DFA為:第78頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二該文法的LR(0)分析表為:狀態(tài)ACTIONGOTOab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2第79頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二3.5.3 SLR(1)分析表的構(gòu)造 LR(0)文法是一類非常簡(jiǎn)單的文法,

44、其特點(diǎn)是該文法的活前綴識(shí)別自動(dòng)機(jī)的每一狀態(tài)都不含沖突項(xiàng)。但即使是算術(shù)表達(dá)式文法也不是LR(0)的,因此需要研究一種簡(jiǎn)單“展望”材料的LR分析法,即SLR(1)法。 實(shí)際上,許多沖突性的動(dòng)作都可以通過考察有關(guān)非終結(jié)符的FOLLOW集而獲得解決。第80頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二SLR(1)沖突解決辦法如下：假定LR(0)規(guī)范族的任一項(xiàng)目集I中含有m個(gè)移進(jìn)項(xiàng)目: A1a11, A2a22, Amamm 同時(shí)含有n個(gè)歸約項(xiàng)目: B1, B2, , Bn 若集合a1,am, FOLLOW(B1), FOLLOW(Bn)兩兩不相交, 則隱含在I中的動(dòng)作沖突可通過檢查 現(xiàn)行

45、輸入符a屬于上述n+1個(gè)集合中 的哪個(gè)集合而獲得解決, 即: 第81頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 (1)若a是某個(gè)ai, i=1,2,m,則移進(jìn); (2)若aFOLLOW(Bi), i=1,2,n, 則用產(chǎn)生式Bi進(jìn)行歸約; (3)對(duì)(1)(2)以外的情況, 報(bào)錯(cuò)。 沖突性動(dòng)作的這種解決辦法叫做 SLR(1)沖突解決辦法。第82頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二文法GS的SLR(1)分析表的構(gòu)造方法: 先把GS拓廣為GS，對(duì)GS構(gòu)造LR(0)項(xiàng)目集規(guī)范族C和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)GO，然后再使用C和GO按下面的算法構(gòu)造GS的SL

46、R(1)分析表: 假定C=I0,I1,In, 令每個(gè)項(xiàng)目集Ik的下標(biāo)k為分析器的一個(gè)狀態(tài), 并令含項(xiàng)目SS的Ik的下標(biāo)k為初態(tài), 則SLR(1)分析表可按如下方法構(gòu)造:第83頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二(1)若項(xiàng)目Aa屬于Ik且GO(Ik,a)=Ij, a為終結(jié)符, 則置ACTIONk,a為“將狀 態(tài)j和符號(hào)a移進(jìn)?！? 即sj。(2)若項(xiàng)目A屬于Ik, 則對(duì)任何輸入符a, aFOLLOW(A), 置ACTIONk,a為“用產(chǎn)生式A進(jìn) 行歸約”, 即rj。 (3)若項(xiàng)目SS屬于Ik, 則置ACTIONk,#為接受, 即acc。(4)若GO(Ik,A)=Ij, A

47、為非終結(jié)符, 則置GOTOk,A=j。第84頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 (5) 凡不能用規(guī)則(1)(4)填入信息的空 白格均置“出錯(cuò)標(biāo)志”。 若按上法構(gòu)造的ACTION表和GOTO表不含多重入口,則稱它為文法GS的SLR(1)表。具有SLR(1)表的文法稱為一個(gè)SLR(1)文法。使用SLR(1)表的分析器叫做SLR(1)分析器。 若按上述算法構(gòu)造的分析表存在多重入口, 則不能用上述算法構(gòu)造分析器。第85頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二例3.18 構(gòu)造例3.16文法SLR(1)分析表。解: 先拓廣文法, 再求文法的LR(0)項(xiàng)目集 規(guī)

48、范族及DFA, 求所有形如A 的 項(xiàng)目的FOLLOW(A), 即 對(duì)SBB,BaB,Bb求FOLLOW集: 由FOLLOW集的構(gòu)造方法得： FOLLOW(S)=#； FIRST(B)FOLLOW(B), 即 FOLLOW(B)=a,b； 由SS, FOLLOW(S)FOLLOW(S), 即FOLLOW(S)=#； 由SBB,FOLLOW(S)FOLLOW(B), 即FOLLOW(B)=a,b,#。第86頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二最后求GS的SLR(1)分析表如下: 狀 態(tài)ACTIONGOTOab#SB0s3s4121acc2s3s453s3s464r3r3r3

49、5r16r2r2r2第87頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二*3.5.4 LR(1)分析表的構(gòu)造 在SLR(1)方法中，若項(xiàng)目集Ik含有A，那么在狀態(tài)k時(shí)，只要當(dāng)前輸入符aFOLLOW(A)，就采取“用A歸約”的動(dòng)作。但在某種情況下，當(dāng)狀態(tài)k呈現(xiàn)于棧頂時(shí)，棧里的符號(hào)串所構(gòu)成的活前綴未必允許把歸約為A，因?yàn)榭赡軟]有一個(gè)規(guī)范句型含有前綴Aa。因此，在這種情況下，用A進(jìn)行歸約未必有效。第88頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 可設(shè)想讓每個(gè)狀態(tài)含有更多的展望信息,這些信息將有助于克服動(dòng)作沖突和排除無效歸約,必要時(shí)對(duì)狀態(tài)進(jìn)行分裂,使得LR分析器的每個(gè)狀

50、態(tài)能確切指出當(dāng)后跟哪些終結(jié)符時(shí)才允許把歸約為A。 為此,需重新定義項(xiàng)目,使得每個(gè)項(xiàng)目都附帶有k個(gè)終結(jié)符?，F(xiàn)在每個(gè)項(xiàng)目的一般形式為 A, a1a2ak 此處, A是一個(gè)LR(0)項(xiàng)目,ai是終結(jié)符, 這種項(xiàng)目稱為LR(k)項(xiàng)目,其中, a1a2ak稱為向前搜索串(或展望串)。第89頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 向前搜索串僅對(duì)歸約項(xiàng)目A, a1a2ak有意義, 對(duì)移進(jìn)或待約項(xiàng)目不起作用。歸約項(xiàng)目A,a1a2ak意味著當(dāng)它所屬狀態(tài)呈現(xiàn)在棧頂且后續(xù)的k個(gè)輸入符為a1a2ak時(shí),才把棧頂?shù)臍w約為A。這里只對(duì)k1的情形感興趣。 構(gòu)造有效的LR(1)項(xiàng)目集族的方法和構(gòu)造LR(

51、0)項(xiàng)目集規(guī)范族的方法本質(zhì)上一樣,也需兩個(gè)函數(shù):CLOSURE(I)和GO(I,X)。第90頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二項(xiàng)目集I的閉包可按如下方式構(gòu)造： (1) I的任何項(xiàng)目都屬于CLOSURE(I)。 (2)若項(xiàng)目AB, a 屬于CLOSURE(I), B是 一產(chǎn)生式, 則對(duì)于FIRST(a)中的每個(gè)終結(jié)符b, 若B, b原來不在CLOSURE(I)中,把它加進(jìn)去。 (3)重復(fù)(2)直到CLOSURE(I)不再增大。函數(shù)GO(I, X)定義為: GO(I, X) =CLOSURE(J) 其中J=形如AX, a的項(xiàng)目 | AX, a屬于I第91頁，共108頁，2

52、022年，5月20日，20點(diǎn)34分，星期二構(gòu)造LR(1)分析表的算法: 假定C=I0,I1,In,令每個(gè)Ik的下標(biāo)k為分析表的狀態(tài),令含有SS, #的Ik的k為分析器的初態(tài)。LR(1)分析表可按如下方法構(gòu)造： (1)若項(xiàng)目Aa, b屬于Ik且GO(Ik,a)=Ij, a為終結(jié)符,則置ACTIONk,a為“將狀態(tài)j和符號(hào)a移進(jìn)棧”,簡(jiǎn)記為sj；第92頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 (2)若項(xiàng)目A, a屬于Ik, 則置ACTIONk,a為“用產(chǎn)生式A歸約”,簡(jiǎn)記為rj, 其中j是產(chǎn)生式的編號(hào); (3)若項(xiàng)目SS,#屬于Ik, 則置ACTIONk,#為接受, 簡(jiǎn)記為ac

53、c; (4)若GO(Ik, A)=Ij, A為非終結(jié)符, 則置GOTO(Ik, A)=j; (5)分析表中凡不能用規(guī)則(1)(4)填入信息的空白欄均填“出錯(cuò)標(biāo)志”。第93頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 對(duì)于LR(1), 有些狀態(tài)(項(xiàng)目集)除向前搜索符不同外,其核心部分都相同,即LR(1)比SLR(1)和LR(0)存在更多的狀態(tài)。因此, LR(1)的構(gòu)造比LR(0)和SLR(1)更復(fù)雜, 占用的存儲(chǔ)空間也更多。第94頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二3.5.5 LALR分析表的構(gòu)造 自學(xué) 對(duì)LR(1)來說,存在著某些狀態(tài)(項(xiàng)目集),這些狀態(tài)

54、除向前搜索符不同外,其核心部分都相同,能否將核心部分相同的諸狀態(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分析法稱為LALR方法。第95頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 對(duì)于同一個(gè)文法, LALR分析表和LR(0)以及SLR分析表永遠(yuǎn)具有相同數(shù)目的狀態(tài)。LALR方法本質(zhì)上是一種折中方法，LALR分析表比LR(1)分析表要小得多，能力也差一點(diǎn)，但它卻能對(duì)付一些SLR(1)所不能對(duì)付的情況。第

55、96頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 由于GO(I,X)的心僅僅依賴于I的心，因此LR(1)項(xiàng)目集合并之后的轉(zhuǎn)換函數(shù)GO可通過GO(I,X)自身的合并而得到，因而在合并項(xiàng)目集時(shí)無需考慮修改轉(zhuǎn)換函數(shù)問題(假定I1與I2的心相同，即項(xiàng)目集相同，則GO(I1,X) =GO(I2,X)，但這里的項(xiàng)目集是不包括搜索符的)。但是，動(dòng)作ACTION必須進(jìn)行修改，使之能夠反映被合并的集合的既定動(dòng)作。第97頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 假定有一個(gè)LR(1)文法,它的LR(1)項(xiàng)目集不存在動(dòng)作沖突,但如果把同心集合并為一,就可能導(dǎo)致產(chǎn)生沖突。這種沖突不會(huì)

56、是移進(jìn)/歸約的沖突,因?yàn)槿舸嬖谶@種沖突,則意味著面對(duì)當(dāng)前的輸入符號(hào)a,有一個(gè)項(xiàng)目A,a要求采取歸約動(dòng)作,而同時(shí)有另一項(xiàng)目Ba,b要求把a(bǔ)移進(jìn);這兩個(gè)項(xiàng)目同處于(合并前的)某一個(gè)集合中,則意味著合并前必有某個(gè)c使得A,a和Ba,c同處于(合并前的)某一集合,這意味著原來的LR(1)項(xiàng)目集已存在移進(jìn)/歸約沖突。第98頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二 因此, 同心集的合并不會(huì)產(chǎn)生新的移進(jìn)/歸約沖突(因是同心合并,故只改變搜索符,不改變移進(jìn)或歸約操作,故不可能存在移進(jìn)/歸約沖突)。同時(shí)說明,若原LR(1)存在著移進(jìn)/歸約沖突, 則LALR必定有移進(jìn)/歸約沖突。 但是同心集的合并可能產(chǎn)生新的歸約/歸約沖突。例如, 假定對(duì)活前綴ac有效的項(xiàng)目集為Ac,d,Bc,e,對(duì)bc有效的項(xiàng)目集Ac,e,Bc,d,這兩集合不含沖突且同心,但合并后變成Ac,d/e,Bc,d/e,含歸/歸沖突。第99頁，共108頁，2022年，5月20日，20點(diǎn)34分，星期二構(gòu)造LALR分析表的算法: 基本思想: 首先構(gòu)