編譯原理-第五章習(xí)題答案

1、編譯原理電子教案第五章第五章語法分析語法分析自下而上的分析自下而上的分析上一頁下一頁2本章的主要內(nèi)容本章的主要內(nèi)容規(guī)范歸約與最右推導(dǎo)、短語、直接短語、句柄、素短語算符優(yōu)先分析 LR（0）和SLR(1)分析表的構(gòu)造 與前面章節(jié)的主要聯(lián)系:最右推導(dǎo)NFA通過子集構(gòu)造法，構(gòu)造DFA文法非終結(jié)符的Follow集上一頁下一頁3本章要求本章要求 知識點：算符優(yōu)先分析、LR（0）和SLR(1)分析表的構(gòu)造深刻理解：規(guī)范歸約與最右推導(dǎo)、短語、直接短語、句柄、素短語熟練掌握：（1）給出一句型求短語、直接短語、句柄和素短語；（2）FIRSTVT和LASTVT的計算、算符優(yōu)先分析表的 構(gòu)造及根據(jù)算符優(yōu)先分析表進(jìn)行句

2、子分析的方法；（3）利用項目集閉包和轉(zhuǎn)移函數(shù)構(gòu)造項目集規(guī)范族，以及根據(jù)項目集規(guī)范族和轉(zhuǎn)移函數(shù)構(gòu)造LR(0)分析表；（4）根據(jù)項目集規(guī)范族、轉(zhuǎn)移函數(shù)以及非終結(jié)符的FOLLOW集構(gòu)造SLR(1)分析表。 上一頁下一頁4本章教學(xué)線索本章教學(xué)線索1 自下而上分析基本問題自下而上分析基本問題1.1 歸約的概念1.2 規(guī)范歸約1.3“移進(jìn)歸約”分析法的棧實現(xiàn)2 算符優(yōu)先分析算符優(yōu)先分析3 LR LR分析法分析法4 語法分析器的自動產(chǎn)生工具語法分析器的自動產(chǎn)生工具YACCYACC上一頁下一頁51.1 歸約的概念歸約的概念 G =（VT，VN，S，P）， （VTVN）*，AP，Aw w。 歸約的過程是，已知w

3、和產(chǎn)生式A，用產(chǎn)生式A左部A替換w中的，得到符號串Aw。 從輸入符號串出發(fā)，每次從被歸約的句型中找到一個產(chǎn)生式的右部，用其左部替換之，得到新的句型，直至歸約到文法的開始符號。上一頁下一頁6 例子：文法G的產(chǎn)生式定義為：SaAcBe Ab AAb Bd 輸入句子為：abbcde 首先看看最右推導(dǎo)：SaAcBeaAcdeaAbcdeabbcde（使用產(chǎn)生式的順序為：SaAcBe Bd AAb Ab） edBBbccccbAAAAAAAaaaaaaaaaS步驟：步驟：1 2 3 4 5 6 7 8 9 10動作：進(jìn)動作：進(jìn) 進(jìn)進(jìn) 規(guī)規(guī) 進(jìn)進(jìn) 規(guī)規(guī) 進(jìn)進(jìn) 進(jìn)進(jìn) 規(guī)規(guī) 進(jìn)進(jìn) 規(guī)規(guī) a b Ab b AA

4、b c d Bd e SaAcBe自底向上分析面臨的基本問題：自底向上分析面臨的基本問題： 如何在句型中找出可規(guī)約串？如何在句型中找出可規(guī)約串？ 找到的可規(guī)約串應(yīng)該規(guī)約到哪一個非終結(jié)符？找到的可規(guī)約串應(yīng)該規(guī)約到哪一個非終結(jié)符？ 上一頁下一頁71.2 規(guī)范歸約規(guī)范歸約短語、直接短語、句柄 令G是一個文法，S是文法的開始符號，假定是文法G的一個句型，如果有： S A且A 則稱是句型相對于非終結(jié)符A的短語短語。 特別是，如果有： A，則稱是句型相對于規(guī)則 A的直接短語直接短語，一個句型的最左直接短語稱為該句型的句柄句柄。 +上一頁下一頁8利用語法分析樹找短語、直接短語和句柄對于短語、直接短語、句柄的

5、尋找，可以檢查語法樹中從根結(jié)點開始出發(fā)向下，找每一非終結(jié)符的所有葉子結(jié)點，將這些結(jié)點從左到右組成串，這些串就是該句型的所有短語，其中相對于葉子結(jié)點的直接父結(jié)點的短語為直接短語，在樹中最左的直接短語為該句型的句柄。直接短語肯定是某個產(chǎn)生式的右部候選式之一。句柄的“最左”特征使得在移進(jìn)-歸約方法中，它始終處于符號棧的棧頂。 上一頁下一頁9例：5.1 P85 文法：ET|ETTF|T*F Fi|（E）句型：i1*i2i3其中：短語有i1、i2、i3、i1*i2、i1*i2i3直接短語：i1、i2、i3；句柄：i1例：5.2 P85 文法如上句型：E+T*F+i短語：E+T*F+i，E+T*F，T*F

6、，i直接短語：T*F和i句柄：T*F EET+ET+FiTF*EETTFi3T*Fi2Fi15.25.1上一頁下一頁10規(guī)范歸約假定是文法G的一個句子。稱右句型序列n，n-1， 1，0是的一個規(guī)范歸約規(guī)范歸約，如果序列滿足： 1） n= ，0=S ；（從句子規(guī)約到文法的開始符號） 2）i（0i n）， i i+1（i是i1經(jīng)過把句柄替換成相應(yīng)產(chǎn)生式左部符號而得到的。）規(guī)范歸約是關(guān)于的一個最右推導(dǎo)的逆過程。（注意：并不是所有的歸約都是規(guī)范，比如算符優(yōu)先分析就不是規(guī)范歸約，當(dāng)然就不是一個最右推導(dǎo)的逆過程）如果文法G是無二義的，那么，規(guī)范推導(dǎo)（最右推導(dǎo)）的逆過程必是規(guī)范歸約（最左歸約）。w表示一個規(guī)

7、范句型，必定是在歸約之前進(jìn)行的規(guī)范歸約得到的結(jié)果， （VTVN）*，w VT*。 最右推導(dǎo)過程中得到的句型rm上一頁下一頁111.3 “移進(jìn)移進(jìn)歸約歸約”分析法的棧實現(xiàn)分析法的棧實現(xiàn) “移進(jìn)一歸約”分析器使用一個棧和一個存放輸入符號串w的緩沖器。分析器的初始狀態(tài)為： 棧 輸入 w 工作過程：自左至右把串w 的符號一一移進(jìn)棧里，一旦棧頂形成句柄時，就進(jìn)行歸約。這種歸約可能持續(xù)多次，直至棧頂不再呈現(xiàn)句柄為止。然后，繼續(xù)向棧里移進(jìn)符號，重復(fù)這個過程，直至最終形成如下格局： 棧 輸入 S 上一頁下一頁12例：5.3 文法：SaAcBe A bAb B d句子：abbcde 步驟棧輸入動作（1）abbc

8、de移進(jìn)（2）abbcde移進(jìn)（3）abbcde歸約，Ab（4）aAbcde移進(jìn)（5）aAbcde歸約，AAb（6）aAcde移進(jìn)（7）aAcde移進(jìn)（8）aAcde歸約，Bd（9）aAcBe移進(jìn)（10） aAcBe歸約， SaAcBe（11）S接受上一頁下一頁13本章教學(xué)線索本章教學(xué)線索1 自下而上分析基本問題自下而上分析基本問題2 算符優(yōu)先分析算符優(yōu)先分析2.1算符優(yōu)先文法及優(yōu)先表的構(gòu)造2.2 算符優(yōu)先分析算法2.3 優(yōu)先函數(shù)2.4 算符優(yōu)先分析中的出錯處理(自學(xué))3 LR LR分析法分析法4 語法分析器的自動產(chǎn)生工具語法分析器的自動產(chǎn)生工具YACCYACC上一頁下一頁142.1 算符優(yōu)先

9、文法及優(yōu)先表的構(gòu)造算符優(yōu)先文法及優(yōu)先表的構(gòu)造2.1.1 算符文法的定義算符文法的定義設(shè)G是一個文法，如果G中不存在形如A及ABC的產(chǎn)生式(其中A，B，CVN， (VNVT)*，且其中不含有相鄰非終結(jié)符號），即G中右部不含具有相鄰非終結(jié)符號的產(chǎn)生式，則稱G為算符文法。例如：文法：EEE|E-E|E*E|E/E|EE|(E)|-E|id 是算符文法。文法：EEAE|（E）|E|id A|*|/| 不是算符文法。因右部EAE具有相鄰的非終結(jié)符號。上一頁下一頁15算符：這里的算符是指文法中的終結(jié)符。終結(jié)符a、b之間的優(yōu)先關(guān)系有三種：a b a的優(yōu)先性高于b算術(shù)關(guān)系“”與優(yōu)先關(guān)系具有十分不同的性質(zhì)。例如

10、，a. b并不一定意味著b . a，例如：+ . （ 且有（ . +。決定優(yōu)先關(guān)系方法： （a） 直觀方法：代數(shù)規(guī)則； （b）對于一個無二義性文法，有機械方法。上一頁下一頁162.1.2 算符優(yōu)先文法算符優(yōu)先文法假定G是一個不含產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b，如果有以下優(yōu)先關(guān)系：ab 當(dāng)且僅當(dāng)G中含有形如Pab或 PaQb的產(chǎn)生式；a b 當(dāng)且僅當(dāng)G中含有形如PRb的產(chǎn)生式， 而R a或R aQ； 如果算符文法G中的任何終結(jié)符對（a，b）至多只滿足ab，a b三者之一，則稱文法G是一個算符優(yōu)先文法。 上一頁下一頁172.1.3 構(gòu)造算符優(yōu)先關(guān)系表的算法構(gòu)造算符優(yōu)先關(guān)系表的算法優(yōu)先關(guān)

11、系表：表示算符優(yōu)先文法中任何終結(jié)符對之間的優(yōu)先關(guān)系。通過檢查文法的每個候選式?？梢哉页鏊袧M足ab的終結(jié)符對。主要在于求滿足的終結(jié)符對。首先來構(gòu)造G的每個非終結(jié)符P的FIRSTVT（ P ）和LASTVT（P）。 FIRSTVT（P）=a|P a或 P Qa，aVT而QVN LASTVT（P）=a|P a或P aQ，aVT而QVN3）首先構(gòu)造FIRSTVT（P）a. 若有產(chǎn)生式Pa或PQa，則aFIRSTVT（P）；b. 若aFIRSTVT（Q），且有產(chǎn)生式PQ，則aFIRSTVT（P）。 上一頁下一頁184）構(gòu)造文法全部非終結(jié)符FIRSTVT（P）的算法建立布爾數(shù)組FP，a，當(dāng)aFIRSTV

12、T（P）時，F(xiàn)P，atrue，按上述規(guī)則a對FP，a賦初值，將FP，atrue的符號對（P，a）入棧；如果棧不空，將棧定項逐出，此項記為（Q，a），檢查文法中形如PQ的產(chǎn)生式，若FP，afalse，將其變?yōu)檎?，并且將符號對（P，a）入棧；重復(fù)以上過程，直到棧為空。 FISRTVT（P） a | F(P，a) = true 如書上P91的形式化算法 類似可以構(gòu)造LASTVT（P）的算法：1）若Pb，或PbB，bVT，BVN，則bLASTVT（P）；2）若bLASTVT（Q），并且有PQ，則有bLASTVT（P）。上一頁下一頁19使用觀察法求：FIRSTVT和LASTVT首先根據(jù)Pa，或PQa對文

13、法的非終結(jié)符號的FIRSTVT進(jìn)行初始化。其次，檢查每個產(chǎn)生式，再使用PQ，則將FIRSTVT（Q）加入到FIRSTVT（P）中，持續(xù)這個過程，直到集合不再增長。同理可以求出LASTVT（P）：首先根據(jù)Pa，或PaQ對文法的非終結(jié)符號的LASTVT進(jìn)行初始化。其次，檢查每個產(chǎn)生式，再使用PQ，則將LASTVT（Q）加入到LASTVT（P）中，持續(xù)這個過程，直到集合不再增長。上一頁下一頁20例：EE+T|T TT*F|F FPF|P P（E）|iFIRSTVT（E）=+，*，（，iFIRSTVT（T）=*，（，iFIRSTVT（F）=，（，iFIRSTVT（P）=（，iLASTVT（E）=+，

14、*，），iLASTVT（T）= *，），iLASTVT（F）=，），iLASTVT（P）=），i上一頁下一頁215）構(gòu)造算符優(yōu)先文法G的優(yōu)先表的算法 思路：對文法中的每一個產(chǎn)生式的候選式檢查，判斷句型中相鄰符號之間 的關(guān)系來構(gòu)造優(yōu)先表；具體算法：FOR 每條產(chǎn)生式PX1X2Xn FOR i1 TO n1 IF Xi，Xi+1VT，THEN XiXi+1；IF i n-2且Xi，Xi+2VT，Xi+1VN THEN XiXi+2；IF XiVT，Xi+1VN THENFOR FIRSTVT(Xi+1)中的每個a Xi Xi1；NEXT NEXTNEXT上一頁下一頁22構(gòu)造優(yōu)先表的步驟首先構(gòu)造非終

15、結(jié)符的FIRSTVT和LASTVT找出所有終結(jié)符，畫出優(yōu)先表（注意加上句子結(jié)束符）其次根據(jù)上面算法進(jìn)行優(yōu)先表的構(gòu)造，將終結(jié)符號對之間的優(yōu)先關(guān)系填入表中。最后：假設(shè)存在#S#的候選式 上一頁下一頁23例：E EE+T|T TTE+T|T TT* *F|F FPF|P PF|F FPF|P P（E E）|i|iFIRSTVT（E）=+，*，（，i FIRSTVT（T）=*，（，iFIRSTVT（F）=，（，i FIRSTVT（P）=（，iLASTVT（E）=+， *，），i LASTVT（T）= *，），i LASTVT（F）=，），i LASTVT（P）=），i+*i（）#+*i（=）#=優(yōu)先關(guān)

16、系表上一頁下一頁242.2 算符優(yōu)先分析算法算符優(yōu)先分析算法素短語及最左素短語的定義素短語及最左素短語的定義 設(shè)G是一個算符文法，是句型關(guān)于A的短語(即有S A且A )且至少含有一個終結(jié)符號，并且除自身之外不再含有任何更小的帶有終結(jié)符號的短語，則稱是句型關(guān)于A的素短語。 所謂最左素短語是指處于句型最左邊的那個素短語。（素短語用于算符文法中，句柄沒這個要求）。 算符優(yōu)先文法句型的最左素短語是唯一的。 最左素短語就是算法優(yōu)先文法的“可歸約串”。 上一頁下一頁25對于文法：EET|T、TT*F|F、FPF|P、P(E)|i 和句型：ET*Fi短語有：ET*F、T*F、i和ET*Fi但素短語只有：i和

17、T*F最左素短語為：T*F（注意句柄不一定是最左素短語） E+FET+ETi*TF文法G的任何句型的最左素短語算符優(yōu)先文法句型的一般形式：N1a1N2a2NnanNn+1#。算符優(yōu)先文法的任何句型其最左素短語是滿足如下條件的最左子串：NjajNiaiNi1：aj-1 ai+1上一頁下一頁26算符優(yōu)先文法的分析算法 方法：（考察棧頂終結(jié)符，與當(dāng)前輸入符號之間的優(yōu)先關(guān)系） k 1 ； Sk REPEAT把下一輸入符號讀入a中；IF SkVT THEN jk ELSE j k1；WHILE Sj a DO /歸約BEGIN REPEATQ = Sj；IF Sj-1 VT THEN jj-1 ELSE

18、 jj-2； UNTIL Sj Q；把Sj+1Sk歸約為某個非終結(jié)符N；k j+1；Sk = NEND OF WHILE；IF (Sj a) or (Sja) then /移進(jìn)BEGIN k = k+1；Sk = a ENDELSE ERROR /出錯 UNTIL a （檢查相鄰終結(jié)符，當(dāng)出現(xiàn)后續(xù)終結(jié)符的優(yōu)先級低于前一終結(jié)符時，（檢查相鄰終結(jié)符，當(dāng)出現(xiàn)后續(xù)終結(jié)符的優(yōu)先級低于前一終結(jié)符時，將之前的狀態(tài)進(jìn)行歸約為某個非終結(jié)符）將之前的狀態(tài)進(jìn)行歸約為某個非終結(jié)符）上一頁下一頁27注意幾點：注意幾點：算符優(yōu)先分析一般不等價于規(guī)范歸約，文法中的單非終結(jié)產(chǎn)生式不會出現(xiàn)在算符優(yōu)先分析的可歸約串中。在算符優(yōu)先

19、分析中，單非終結(jié)符只用于計算FISTVT和LASTVT算符優(yōu)先算法的速度比規(guī)范歸約速度快，診查錯誤的能力較弱。在算符優(yōu)先分析中，由于單個的非終結(jié)符的產(chǎn)生式被忽略，則每次找到的最左素短語就不一定是當(dāng)前句型的句柄。因此最左素短語也就可能不是相應(yīng)文法的任何產(chǎn)生式的右部。在這種情況下，我們可以按下述策略歸約。形如：NjajNiaiNi+1的最左素短語，在文法中尋找這樣的一個產(chǎn)生式，它的右部形如：UjajUj+1aj+1UiaiUi+1的結(jié)構(gòu)。其中每一個終結(jié)符與最左素短語中對應(yīng)位置上的終結(jié)符相同，而每一個非終結(jié)符Uk與最左素短語相應(yīng)位置上的非終結(jié)符Vk對應(yīng)，當(dāng)Vk不必與Nk相同。如果文法中有這種產(chǎn)生式，

20、就將句型的最左素短語“按此產(chǎn)生式”進(jìn)行歸約。上一頁下一頁28對于P90頁中的分析ii的分析過程：首先：棧 （1）ai，因為S1 a則移進(jìn)，棧： i，輸入為：i；（2）a，因為S2 a，則歸約，又QS2i，j2，jj11，S1Qi，所以將S2歸約為P，棧： P；（3）因為S1 a（a），所以移進(jìn)，棧： P ，輸入i；（4）ai，S3=+，S3 a，所以歸約，又因為S3a，所以繼續(xù)規(guī)約，又S1 S3，所以將S2 S3S4歸約，找形如PP的產(chǎn)生式又EET，所以用其進(jìn)行歸約，棧： E，輸入 ；（7）a，又S1，所以，S1a，則移進(jìn)，棧E，分析結(jié)束。 上一頁下一頁292.3 優(yōu)先函數(shù)優(yōu)先函數(shù)為了節(jié)約存儲

21、空間和便于執(zhí)行比較運算 ，用兩個優(yōu)先函數(shù)f和g，它們是從終結(jié)符號映射到整數(shù)的函數(shù)。對于終結(jié)符號a和b選擇f和g，使之滿足：當(dāng)a b時，f(a) g(b)。于是a和b之間的優(yōu)先關(guān)系可以由比較f(a) 與g(b)的大小來決定。損失：錯誤檢測能力降低，例如，i i不存在，f(i) g(i) 可比較。1）構(gòu)造優(yōu)先函數(shù)的算法不是唯一的。2）存在一組優(yōu)先函數(shù)，那就存在無窮組優(yōu)先函數(shù)。算法：從優(yōu)先關(guān)系表構(gòu)造優(yōu)先函數(shù)方法： 1）aVT#，建立兩個符號fa和ga； 2）a，b VT， 若a b，則從，則從fa至至gb畫一條箭?。划嬕粭l箭??； 若若a b，則從，則從gb至至fa畫一條箭??；畫一條箭??； 3）若圖中

22、無環(huán)，則存在優(yōu)先函數(shù)，）若圖中無環(huán)，則存在優(yōu)先函數(shù)，f(a)和和g(b)等于從等于從fa和和gb出發(fā)的最長路徑。出發(fā)的最長路徑。上一頁下一頁30例P95 優(yōu)先關(guān)系表對應(yīng)P90表5.1+*（）f46629g35882f f+ +f f* *f ff f( (f f) )g g+ +g g* *g gg g( (g g) )上一頁下一頁312.4 算符優(yōu)先分析中的出錯處理算符優(yōu)先分析中的出錯處理(自學(xué)自學(xué))若在棧頂終結(jié)符與下一輸入符號之間不存在任何優(yōu)先關(guān)系若找到某一最左素短語，但不存在任一產(chǎn)生式可用來歸約 上一頁下一頁32本章教學(xué)線索本章教學(xué)線索1 自下而上分析基本問題自下而上分析基本問題2 算符

23、優(yōu)先分析算符優(yōu)先分析3 LR LR分析法分析法3.1 LR分析器的邏輯結(jié)構(gòu)及工作過程3.2 LR（0）項目集規(guī)范族和LR（0）分析表的構(gòu)造3.3 SLR分析表的構(gòu)造3.4 規(guī)范LR分析表的構(gòu)造3.5 LALR分析表的構(gòu)造3.6 LR分析的出錯處理4 語法分析器的自動產(chǎn)生工具語法分析器的自動產(chǎn)生工具YACCYACC上一頁下一頁333 LR分析法分析法LR(k)分析技術(shù)。這里的“L”是指從左至右掃描輸入符號串，“R”是指構(gòu)造一個最右推導(dǎo)的逆過程，“k”是指為了作出分析決定而向前看的輸入符號的個數(shù)。LR分析方法是當(dāng)前最廣義的無回溯的“移進(jìn)- 歸約”方法。根據(jù)棧中的符號串和從左向右順序查看輸入串的k（

24、k0）個符號，就能唯一確定分析器的動作是移進(jìn)還是歸約，以及用哪個產(chǎn)生式進(jìn)行歸約。LR（k）分析技術(shù)是knuth于1965年首先提出來的。優(yōu)點：適用范圍廣；分析速度快；報錯準(zhǔn)確。構(gòu)造分析器的工作量很大，不大可能手工構(gòu)造；用軟件工具YACC（Yet Another Compiler Compiler，Bell，1974。）來構(gòu)造。上一頁下一頁343.1 LR分析器的邏輯結(jié)構(gòu)及工作過程分析器的邏輯結(jié)構(gòu)及工作過程a1a2.aian#LR分析程序輸出sm Xms1 X0s0 #action goto分析表棧輸入串LR分析器的邏輯模型 棧：棧的每一項內(nèi)容包括狀態(tài)s和文法符號X兩部分，（s0，）為分析開始前

25、預(yù)先放置的初態(tài)和句子結(jié)束符。LR分析器的核心部分就是一張分析表，它包括“動作”和“狀態(tài)轉(zhuǎn)換”兩部分，都是用二維數(shù)組來表示。ACTIONs，a規(guī)定了當(dāng)前狀態(tài)s面臨輸入a應(yīng)該采取的動作，GOTOs，X規(guī)定了狀態(tài)s面對文法符號X（終結(jié)符或非終結(jié)符）時下一狀態(tài)是什么。GOTOs，X定義了一個以文法符號為字母表的DFA。 上一頁下一頁35ACTIONs，a所規(guī)定的動作有以下四種可能：移進(jìn)移進(jìn) 把（s，a）的下一狀態(tài)s= GOTOs，a和輸入符號a推進(jìn)棧，下一輸入符號變成現(xiàn)行輸入符號；歸約歸約 指用某一產(chǎn)生式A進(jìn)行歸約。假設(shè)的長度為r，歸約的動作是A，去除棧頂?shù)膔個項，使?fàn)顟B(tài)sm-r變成棧頂狀態(tài)，然后把（

26、sm-r，A）的下一狀態(tài)sGOTOsm-r，A和文法符號A進(jìn)棧。歸約動作不改變現(xiàn)行輸入符號。執(zhí)行歸約動作意味著（Xm-r+1Xm）已呈現(xiàn)于棧頂而且是一個相對于A的句柄。接受接受 宣布分析成功，停止分析器的工作。1.報錯報錯 發(fā)現(xiàn)源程序含有錯誤，調(diào)用出錯處理程序。上一頁下一頁36LR分析器的工作過程 格局：（棧中符號序列，已歸約串和剩余輸入符號串）開始：（s0，a1 a2 an)中間：（s0s1s2sm，X1X2Xm，aiai+1an) 分析器的下一步動作是由棧頂狀態(tài)sm和現(xiàn)行輸入符號ai所唯一決定的，執(zhí)行ACTIONs，ai所規(guī)定的動作。1）若ACTION sm，ai為“移進(jìn)”，且sGOTOs

27、m，ai，則三元式變?yōu)椋╯0s1sms，X1X2Xmai，ai+1an）2）若ACTION sm，aiA，則按產(chǎn)生式A進(jìn)行“歸約”，則三元式變?yōu)椋╯0s1smrs，X1X2XmrA，aiai+1an）此處：sGOTOsmr，A，r為的長度，Xm-r+1Xm。3）若ACTION sm，ai為“接受”，則三元式不再變化，分析成功；4）若ACTION sm，ai為“報錯”，則三元式變化過程終止，報告錯誤。上一頁下一頁37例：5.7 P102 分析表 為P101圖5.5文法： （1）EE+T （2）ET （3）TT*F （4）TF （5）F（E） （6）Fi狀態(tài)狀態(tài)ACTION（動作）（動作）GOTO

28、（轉(zhuǎn)換）（轉(zhuǎn)換）i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5上一頁下一頁38分析過程中三元式的工作過程 狀態(tài)符號輸入串備注（1） 0i*i+i# 0狀態(tài)面臨i輸入，由表的s5，將5進(jìn)棧（2） 05# i *i+i# 5面臨*，由表得r6，用Fi歸約，長度為1則ACTION0，F(xiàn)對應(yīng)3GOTO0，F(xiàn)（3） 03# F*i+i# 3面臨 * 則 r4 TF（4） 02# T*i+i# 2面臨*，則s7（5） 027#T*i+i#

29、7面臨i，則s5（6） 0275#T*i+i# 5面臨+，則r6 Fi 7面臨F則有10（7） 02710#T*F+i# 10面臨，則有r3，則用TT*F歸約，長度為3，則GOTO0，T2（8） 02#T+i#（9） 01#E+i#（10） 016#E+i#（11）0165#E+i#（12） 0163#E+F#（13） 0169#E+T# 9面臨#，則r1 EE+T 0面臨E有1（14） 01#E# 接受上一頁下一頁393.2 LR（0）項目集規(guī)范族和）項目集規(guī)范族和LR（0）分析表的構(gòu)造）分析表的構(gòu)造3.2.1 規(guī)范句型（右句型）的規(guī)范句型（右句型）的“活前綴活前綴” 一個句型的一個前綴，若

30、不含句柄之后的任何符號 ，則稱它為該規(guī)范句型的一個活前綴。 分析過程的每一步驟，棧里的文法符號串加上剩余輸入符號串恰好是一個規(guī)范句型。分析過程的每一步驟，棧里的文法符號串加上剩余輸入符號串恰好是一個規(guī)范句型。而且棧里的文法符號串正好是這個句型的一個活前綴。因此而且棧里的文法符號串正好是這個句型的一個活前綴。因此LR分析首先將構(gòu)造識別文分析首先將構(gòu)造識別文法法G的所有活前綴的有限自動機，然后將這種自動機轉(zhuǎn)換為的所有活前綴的有限自動機，然后將這種自動機轉(zhuǎn)換為LR分析表。分析表。補充：活前綴與句柄的關(guān)系：活前綴不含有句柄的任何符號活前綴含有句柄的部分符號1；活前綴已含有句柄的全部符號；識別活前綴的自

31、動機處于的格局： 010101212上一頁下一頁403.2.2 LR（0）項目）項目文法G每個產(chǎn)生式的右部添加一個圓點稱為G的一個LR（0）項目（簡稱項目）；例如產(chǎn)生式AXYZ對應(yīng)的四個項目為：AXYZ，AXYZ，AXYZ，AXYZ如果是A則其項目僅有：A 。例5.8 P105 文法的項目：文法為SE EaA|bB AcA|d BcB|d SE SEEaA EaA EaA上一頁下一頁413.2.3 LR（0）項目集規(guī)范族的構(gòu)造）項目集規(guī)范族的構(gòu)造1）拓廣文法：）拓廣文法：為了使接受狀態(tài)易于識別，總是將文法G進(jìn)行拓廣，假定G是一個以S為開始符號的文法，構(gòu)造一個G，它包含了整個G，但引進(jìn)一個不出現(xiàn)

32、在G中的非終結(jié)符S，并加進(jìn)一個新產(chǎn)生式SS，而S是G的開始符號。2）構(gòu)造）構(gòu)造NFA：狀態(tài)集：文法G所有項目；字母表為：文法G中的所有文法符號（包括終結(jié)符和非終結(jié)符）；初態(tài)集：規(guī)定開始符號S的產(chǎn)生式項目SS為NFA的唯一初態(tài)；終態(tài)集：G的任何項目均可認(rèn)為是NFA的終態(tài)（活前綴識別態(tài)活前綴識別態(tài)）；狀態(tài)轉(zhuǎn)換函數(shù)：如果狀態(tài)i和j出自同一產(chǎn)生式，而且狀態(tài)j的圓點位置只落后于狀態(tài)i一位，如狀態(tài)i為：XX1Xi-1XiXn而狀態(tài)j為XX1XiXi1Xn則從狀態(tài)i畫一條標(biāo)記為Xi的箭弧到狀態(tài)j，假如狀態(tài)i的圓點之后的那個符號為非終結(jié)符，如i為項目XA，A為非終結(jié)符，則從狀態(tài)i畫弧到所有A狀態(tài)。（用帶雙圈的

33、狀態(tài)表示句柄識別態(tài)：圓點在最后的項目）3)確定化確定化：將NFA確定化（使用子集構(gòu)造法），轉(zhuǎn)化為DFA，這個DFA是一個以項目集合為狀態(tài)的DFA。構(gòu)成識別一個文法活前綴的項目集的全體稱為這個文法的LR（0）項目集規(guī)范族）項目集規(guī)范族。 上一頁下一頁42文法為SE EaA|bB AcA|d BcB|d 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. A cA 7. A cA 8. A cA 9. Ad 10. Ad 11. EbB 12 EbB13.E bB 14. B cB 15. BcB 16. BcB 17. Bd 18. Bd 12E E3456798101112

34、131415171618a aA AA Ac cd db bd dB Bc cB B0:SE EaA EbB2:EaA AcA Ad1:SE3:EbB BcB Bd6:EaA4:AcA AcA Ad8:AcA10:Ad5:EcB BcB Bd7:EbB11:Bd9:BcBE Ea ac cA Ad dd dA AB BB Bd dd db bc cc cc c上一頁下一頁43 凡是圓點在最右端的項目，稱為一個“歸約項目”。 對于文法開始符號的歸約項目稱為“接受”項目； 形如Aa的項目，稱為“移進(jìn)”項目； 形如AB的項目稱為“待約”項目。（期待從余留的輸入符號中進(jìn)行歸約得到B，所以稱為待約項目）

35、 DFA工作過程中，從初態(tài)出發(fā)，沿著有向邊指示的方向前進(jìn)，可以使DFA在所經(jīng)歷的任何狀態(tài)上中止它的工作（每一狀態(tài)都是終態(tài)），當(dāng)DFA到達(dá)某一狀態(tài)時，把從初態(tài)I0出發(fā)到達(dá)該狀態(tài)所經(jīng)過的全部有向邊上的標(biāo)記符依次連接起來就得到了DFA在到達(dá)該狀態(tài)時所識別出的某規(guī)范句型的一個活前綴。特別是當(dāng)M到達(dá)那些只含歸約的項目集，表明活前綴中已含有相應(yīng)句柄的全部符號（句柄已經(jīng)在棧頂形成），因此將這些狀態(tài)稱為句柄識別態(tài)。 上一頁下一頁44項目集項目集I的閉包：的閉包：定義：假定I是文法G的任一項目集，定義和構(gòu)造I的閉包CLOSURE（I）的辦法是：I的任何項目都屬于CLOSURE（I）；若AB屬于CLOSURE（I

36、），那么，對于任何關(guān)于B的產(chǎn)生式B，項目B也屬于CLOSURE（I）；重復(fù)上述兩步驟，直到CLOSURE（I）不再增大為止。 （注意：對任何非終結(jié)符B，若某個圓點在左邊的項目B進(jìn)入CLOSURE（I），則B的所有其它圓點在左邊的項目B也將進(jìn)入同一個CLOSURE集中上一頁下一頁45項目集項目集I的轉(zhuǎn)移函數(shù)：的轉(zhuǎn)移函數(shù)：定義：若I是G的一個LR(0)項目集，X VTVN GO(I，X)=CLOSURE（J）其中，J=AX | 當(dāng)AX I時 GO (I，X)稱為轉(zhuǎn)移函數(shù)。項目AX稱為AX的后繼。（直觀的說：若I是對某個活前綴有效的項目集，那么GO（I，X）便是對X有效的項目集。） 上一頁下一頁46

37、LR（0）項目集規(guī)范族的構(gòu)造算法：（利用I的閉包和轉(zhuǎn)移函數(shù)）Procedure Itemsets（G）BEGINC = CLOURE(S S)；REPEAT FOR C中的每個項目集I和G的每個符號X DOIF GO（I，X）非空且不屬于C THEN 把 GO（I，X）放入C族中 END IF UNTIL C 不再增大END識別文法G的所有活前綴的DFA： DFA M= (VTVNS ，Q項目集規(guī)范族，q0= closureS S，Q， =go(I，X) 上一頁下一頁47例子：例子：SA|B Ac|aAb Bd|aBb 求求 I0拓廣文法 SS所以：I0=closure(S S )I0= S

38、S ，S A，S B，Ac，AaAb，B aBb，Bd P106中的文法： G：SE、EaA|bB、AcA|d、BcB|d（1）C：CLOSURE(S S )I0 S E，EaA，EbB（2）I1GO（I0，E）closure（ S E ）= S E I2GO（I0，a）= closure（ EaA ）= EaA，AcA，Ad I3GO（I0，b）= closure（ EbB）= EbB，BcB，Bd （3）C I0，I1，I2，I3 I0、I1不用再看，看不用再看，看I2：I4=GO(I2，A)=closure( EaA )= EaA I5GO(I2，c)=closure（ AcA ） Ac

39、A 、AcA、Ad I6GO（I2，d）closure（ Ad ） Ad 看看I3：I7GO（I3，B）closure（ EbB ） EbB I8GO（I3，c）=closure（ BcB ）= BcB 、BcB、Bd I9GO（I3，d）closure（ Bd ）Bd 略。略。 上一頁下一頁48有效項目有效項目如果存在一個規(guī)范推導(dǎo)S Aw rm12w ，項目A12對識別活前綴=1是有效的。有下面的結(jié)論： 若項目AB對識別活前綴 =是有效的且若BP，則項目B 對識別活前綴 =也是有效的。 推導(dǎo)如下： 若項目AB對識別活前綴 =是有效，則存在一個規(guī)范AwrmBw ，設(shè)wrmxw，則對任何BP，A

40、wrmBwrmBxwrm推導(dǎo)S有Sxw 則B 對識別活前綴 = 也是有效的。AB 和B 在同一個項目集中。 識別文法G的某個活前綴的所有有效項目組成的集合稱為的有效項目集。文法G的所有有效項目集組成的集合稱為G的LR(0)項目集規(guī)范族。 *rm*rm*rm上一頁下一頁493.2.4 LR（0）分析表的構(gòu)造）分析表的構(gòu)造LR（0）文法：假設(shè)一個文法G的拓廣文法G的活前綴識別自動機中的每個狀態(tài)（項目集）不存在下述情況：（1）既含移進(jìn)項目又含歸約項目；（2）或者含有多個歸約項目，則稱G是一個LR(0)文法。構(gòu)造算法：若項目Aa屬于Ik且GO（Ik，a）=Ij，a為終結(jié)符，則置ACTIONk，a為“把

41、（j，a）移進(jìn)?！?，記為“sj”；若項目A屬于Ik，那么，對任何終結(jié)符a（或結(jié)束符），置ACTIONk，a為“用產(chǎn)生式A進(jìn)行歸約”，記為“rj”；若項目SS屬于Ik，則置ACTIONk，#為“接受”，記為“acc”；若GO（Ik，A）Ij，A為非終結(jié)符，則置GOTOk，A = j；將空白格均置為“報錯標(biāo)志”。 上一頁下一頁50例5.10 P110文法：（0）SE（1）EaA （2）EbB （3）AcA （4）Ad（5）BcB （6）Ed SEEaAEbB SEEEaAAcAAdEbBBcBBdabEaA Ac A AcA AdA012345 EcB BcB Bd 6781011dccBBcB

42、9AcAAcEbBAddcdBBdd上一頁下一頁51 結(jié)論：對于拓廣文法G的每一個活前綴，識別它的有效項目集恰好是從它的識別活前綴的DFA的初態(tài)出發(fā)經(jīng)過道路所到達(dá)的那個狀態(tài)所代表的項目集。事實上，在任何時候分析棧中的活前綴X1X2Xm的有效項目集恰恰是棧頂狀態(tài)Sm所代表的那個集合。這也表示棧頂狀態(tài)體現(xiàn)了棧里一切有用的信息。 對同一個活前綴存在若干不同的項目對它是有效的，而且它告訴我們應(yīng)做的事情可能各不相同，互相沖突。這種沖突通過向前看幾個輸入符號或許能夠解決。上一頁下一頁523.3 SLR分析表的構(gòu)造分析表的構(gòu)造 從前面對LR（0）文法的分析可知，LR（0）文法是一種非常簡單的文法，這種文法的

43、活前綴識別自動機的每一個狀態(tài)（項目集）都不含沖突的項目。在實際應(yīng)用中的文法要復(fù)雜得多，因此，必須使用具有一定“展望”材料的LR分析法。本節(jié)研究SLR法。上一頁下一頁533.3.1 項目集中的沖突問題項目集中的沖突問題首先看一下項目集（狀態(tài)）I：IXb，A，B其中第一個項目是移進(jìn)項目，第二、三項目是歸約項目。第一個項目告訴我們應(yīng)該將下一輸入符號b移進(jìn)，第二個項目則要求把棧頂?shù)臍w約為A，第三個項目要求將棧頂?shù)臍w約為B。上一頁下一頁543.3.2 解決的辦法解決的辦法解決這種沖突的簡單方法就是分析所有含有A或B的句型，考察句型可能直接跟在A或B之后的終結(jié)符，也就是說，考察集合FOLLOW（A）和FO

44、LLOW（B）。如果這兩個集合不相交，而且都不包含b，那么，當(dāng)狀態(tài)I面臨任何輸入符號a時，我們就可以采取如下的“移進(jìn)歸約”決策：若ab，則移進(jìn)；若aFOLLOW（A），則用產(chǎn)生式A進(jìn)行歸約；若aFOLLOW（B），則用產(chǎn)生式B進(jìn)行歸約；此外，就報錯。一般地：假定LR（0）規(guī)范族的一個項目集I中含有m個移進(jìn)項目：A1a11，A2a22，Amamm；同時含有n個歸約項目：B1，B2，Bn，如果集合a1，am，F(xiàn)OLLOW(B1)，F(xiàn)OLLOW（B2），F(xiàn)OLLOW（Bn）兩兩不相交（包括不得有兩個FOLLOW集合中含有），則隱含在I中的動作沖突可通過檢查現(xiàn)行輸入符號a輸入上述n+1個集合的哪個集合

45、而獲得解決。即：若a是某個ai，i1，2，m，則移進(jìn)；若aFOLLOW（Bi），i1，2，n，則用產(chǎn)生式Bi進(jìn)行歸約；此外，報錯。這種沖突性動作解決方法就是SLR（1）解決方法。 上一頁下一頁55例：求其例：求其LR（0）項目集的規(guī)范族：）項目集的規(guī)范族：S E （1）EET（2）ET （3）TT*F （4）TF （5）F（E）（）（6）F i注意I1、I2、I9都含有“移進(jìn)歸約”沖突。例如I2，由于FOLLOW（E）#，），所以，當(dāng)狀態(tài)I2面臨輸入符號為、）或時，應(yīng)用ET進(jìn)行歸約；當(dāng)面臨*時，應(yīng)實行移進(jìn)；若面臨其它符號則應(yīng)報錯。 I0：SE EET ETTT*FTFF(E)FiI1：SEEE

46、TI2： ETTT*FI3： TFI4： F(E)EETETTT*FTFF(E)FiI5：FiI6： EETTT*FTFF(E)FiI7：TT*FF(E)FiI8： F (E)EE+TI9： EE+TTT*FI10：TT*FI11：F(E)TEF+TI5*F(iiiEI7T(FI3I6+F(I4I5i上一頁下一頁563.3.3 SLR（1）分析表的構(gòu)造）分析表的構(gòu)造對于文法G，首先把G拓廣為G，對G構(gòu)造LR（0）項目集規(guī)范族C和活前綴識別自動機的狀態(tài)轉(zhuǎn)換函數(shù)GO。使用C和GO，然后再按下面的算法構(gòu)造G的SLR分析表。假定CI0，I1，In，令每個項目集Ik的下標(biāo)k為分析器的一個狀態(tài)，因此，G的

47、分析表含有狀態(tài)0，1，n。令那些含有項目SS的Ik為初態(tài)。函數(shù)ACTION和GOTO可按如下方法構(gòu)造： 若項目Aa屬于Ik且GO（Ik，a）Ij，a為終結(jié)符，則置ACTIONk，a為“把狀態(tài)j 和符號a移進(jìn)棧”，簡記為：“sj”； 若項目A屬于Ik，那么，對任何終結(jié)符a，且aFOLLOW（A），則置ACTIONk，a為“用產(chǎn)生式A進(jìn)行歸約”，簡記為：“rj”；其中，假定A為文法G的第j的產(chǎn)生式； 若項目SS屬于Ik，則置ACTIONk，#為“接受”，簡記為“acc”； 若GO(Ik ，A)=Ij，A為非終結(jié)符，則置GOTOk，A=j； 分析表中凡不能用上述四個規(guī)則填入信息的空白格均置“出錯標(biāo)志

48、”。按上述方法構(gòu)造的含ACTION和GOTO兩部分的分析表，若每個入口不含多重定義，則稱它為SLR分析表，具有SLR分析表的文法G稱為SLR（1）文法。 參見P101SLR分析表的構(gòu)造上一頁下一頁573.4 規(guī)范規(guī)范LR分析表的構(gòu)造分析表的構(gòu)造3.4.1 LR(k)項目項目 形式：A， a1a2ak 移進(jìn)或待歸約項目（）， a1a2ak不起作用。 歸約項目A， a1a2ak，僅當(dāng)前輸入符號串開始的前k個符號是a1a2ak時，才能用A進(jìn)行歸約。 a1a2ak稱向前搜索符號串。上一頁下一頁583.4.2 LR(1)的有效項目集、項目集的閉包和轉(zhuǎn)移函數(shù)的有效項目集、項目集的閉包和轉(zhuǎn)移函數(shù) LR(1)

49、的有效項目：如果一個LR(1)項目A，a對于活前綴是有效的，則存在一個規(guī)范推導(dǎo)SAR其中=，的第一個符號為a，或=而a為#。 *R，推論：若項目AB，a對活前綴=是有效的，則存在一個規(guī)范推導(dǎo) SAaRBa 假定ab，則對每一個形如B的產(chǎn)生式有規(guī)范推導(dǎo)： SBbRb 因此，項目B，b對于活前綴=也是有效的。注意到b或者是從推出的第一個終結(jié)符號，或者而b=a，因此有bFIRST(a)。 *R*R*R*R上一頁下一頁59LR(1)項目集的閉包項目集的閉包：設(shè)I是G的一個LR(1)項目集，closure(I)是從I出發(fā)用下面三個規(guī)則構(gòu)造的項目集 ：1) 每一個I中的項目都屬于closure(I)。2)

50、 若項目AB，a屬于closure(I) 且 B P，則對任何bFIRST(a)，把原來不屬于closure(I)中的項目B，b加進(jìn)closure(I)中。3) 重復(fù)執(zhí)行(2)直到closure(I)不再增大為止。轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)GO(I，X)令I(lǐng)是一個項目集，X是一個文法符號，函數(shù)GO(I，X)定義為：GO(I，X) = CLOSURE(J)其中：J=任何形如AX，a的項目|AX，aI上一頁下一頁603.4.3 G的的LR(1)項目集族項目集族C的構(gòu)造算法的構(gòu)造算法BEGIN I0： C = closure(SS，#) FOR C中的每個項目集I和G的每個符號X DO IF GO(I，X)非

51、空且不屬于C，THEN把GO(I，X)加入C中 UNTIL C不再增大 END 上一頁下一頁61例：拓廣文法：（0）SS （1）SBB （2）BaB （3）BbC=I0=closureS.S,#=S.S,# S.BB,# B.aB,a/b B.b,a/b圓點后：S，B，a，b則：GO(I0,S)=closure(SS.,#) = SS.,# = I1GO(I0,B)=closure(SB.B,#)=SB.B,# B.aB,# B.b,# = I2GO(I0,a)=closure(Ba.B,a/b) =Ba.B,a/b B.aB,a/b B.d,a/b = I3GO(I0,b)=closure(

52、Bb.,a/b) = Bb.,a/b = I4所以：C=I0， I1，I2，I3，I4看I2，I3：GO(I2,B)=closure(SBB.,#) = SBB.,# = I5GO(I2,a)=closure(Ba.B,#) =Ba.B,# B.aB,# B.b,#=I6GO(I2,b)=closure(Bb.,#) = Bb.,# = I7GO(I3,B)=closure(BaB.,a/b) = BaB.,a/b = I8GO(I3,a)=closure (Ba.B,a/b) = I3GO(I3,b)= closure(Bb.,a/b) = I4所以C=I0,I1，I2，I3，I4，I5，I

53、6，I7，I8GO(I6,B)= closure(BaB.,#) =BaB.,# = I9GO(I6,a)=I6GO(I6,b)=I7 所以：C=I0,I1，I2，I3，I4，I5，I6，I7，I8 ， I9上一頁下一頁623.4.4 LR(1)分析表的構(gòu)造分析表的構(gòu)造 若項目Aa，b屬于Ik且GO（Ik，a）=Ij，a為終結(jié)符，則置ACTIONk，a為“把（j，a）移進(jìn)?！?，記為“sj” 若項目A，a屬于Ik，置ACTIONk，a為“用產(chǎn)生式A進(jìn)行歸約”，記為“rj” 若項目SS，#屬于Ik，則置ACTIONk，#為“接受”，記為“acc” 若GO（Ik，A）Ij，則置GOTOk，A = j

54、 將空白格均置為“報錯標(biāo)志” 上一頁下一頁63I0: S.S, # S.BB , #B.aB , a/bB.b , a/bI3:Ba.B, a/b B.aB,a/b B.b , a/bI1: SS., #I2: SB.B , # B.aB , # B.b , #I4:Bb. , a/bI7:Bb. , #I5:SBB. , #I6:Ba.B , # B.aB , # B.b , #I9:BaB. , #I8:BaB. , a/baSBBaabbBaBbb例例 P115 拓廣文法：拓廣文法： （0） SS （1）SBB （2）BaB （3）Bbab#SB0s3s4121acc2s6s753s3s

55、484r3r35r1上一頁下一頁643.5 LALR分析表的構(gòu)造分析表的構(gòu)造LALR(lookahead-LR)技術(shù)。這種方法在實際中是經(jīng)常使用的。心：如果兩個LR(1)項目集去掉搜索符之后是相同的，則稱這兩個項目集具有相同的心（core）。 一個心就是一個LR(0)項目集。 核：除去初態(tài)項目集外，一個項目集的核（kernel）是由此集中那些圓點不在最左端的項目組成。LR（1）初態(tài)項目集的核含有也僅含有SS，#。改進(jìn)思路： 合并同心集可達(dá)到縮小構(gòu)造分析表的狀態(tài)數(shù)目；利用核代替項目集可以達(dá)到縮小項目集所占用的存儲空間。介紹兩種方法： 第一種方法：對于G，構(gòu)造LR（1）項目集規(guī)范族（DFA），然后，合并同心集，若合并后的同心集中沒有沖突，則用其構(gòu)造LR分析表，這種分析表稱作LALR分析表。 上一頁下一頁65討論：由于GO（I，X）僅僅依賴于I的心，因此 LR（1）項目集合并后的轉(zhuǎn)換函數(shù)GO（I，X）隨自身的合并而得到。動作ACTION應(yīng)當(dāng)進(jìn)行修改，使得能反映各被合并集合的既定動作。把同心的項目集合并為一，有可能導(dǎo)致沖突，這種沖突不會是移進(jìn)歸約沖突；但可能引起歸約歸約沖突