編譯原理-南京大學(xué)-自下而上語法分析.ppt
《編譯原理-南京大學(xué)-自下而上語法分析.ppt》由會員分享,可在線閱讀,更多相關(guān)《編譯原理-南京大學(xué)-自下而上語法分析.ppt(100頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、第五章 語法分析自下而上分析,本章內(nèi)容 自下而上分析基本問題 直觀算符優(yōu)先分析法 算符優(yōu)先分析 LR分析法,自下而上分析法 從輸入串開始,逐步進行“歸約”,直至 歸約到文法的開始符號; 一、自下而上分析基本問題,1 、歸約 利用棧,輸入符號移進棧,當棧頂形成P的候選式時,就歸約為它的左P符號,例5.1 文法G2: S-aAcBe A-b A-Ab B-d 輸入串:abbcde,自下而上法,即“移進-歸約”法,最右推導(dǎo):,a,a,b,a,A,a,A,b,a,A,a,A,c,a,A,c,d,a,A,c,B,a,A,c,B,e,S,1,2,3,4,5,6,7,8,9,10,棧,S,= aAcB
2、e,= aAcde,=aAbcde,= a b b c d e,,,,,,S-aAcBe,輸入串:abbcde,A-Ab,B-d,A-b,S,a,A,c,B,e,A,b,d,b,,,,,,,,,,分 析 樹,最左歸約:,= S,= aAcBe,= aAcde,= aAbcde,a b b c d e,S-aAcBe,輸入串:abbcde,A-Ab,B-d,A-b,2 規(guī)范歸約,短語:令G是一個文法,S是文法的開始符號,若是文法G的一個句型,如果有S A且 A ,則稱是句型相對于非終結(jié)符A的短語。,句柄:一個句型的最左直接短語稱為該句型的句柄。,規(guī)范推導(dǎo):即最右推導(dǎo); 規(guī)范句型:由規(guī)范推導(dǎo)所得的
3、句型稱為規(guī)范句型; 規(guī)范歸約:是關(guān)于句型的一個最右推導(dǎo)的逆過程,也稱最左歸約。,例5.2 文法G E T | E +T T F | T * F F i |(E) 的一個句型 i1*i2+i3,語 法 樹,,,T,F,E,E,F,F,+,T,*,,,,,,,,,,i1,i2,i3,T,,i1 ,i2 ,i3 , i1*i2 , i1*i2+i3,i1 ,i2 ,i3,i1,短語:,直接短語:,句柄:,3 符號棧的使用,規(guī)范歸約用來作語法分析需要解決的問題: 如何在句型中找出句柄? 在相同的右部有不止一個產(chǎn)生式時,選哪一個?,實現(xiàn)移進-歸約分析的一個方便途徑是用一個棧和一個輸 入
4、緩沖區(qū),用#表示棧底和輸入的結(jié)束, 分析程序的動作 移進: 下一輸入符號移進棧頂 歸約: 把句柄按產(chǎn)生式的左部進行歸約 接收: 分析程序報告成功 出錯: 發(fā)現(xiàn)了一個語法錯,調(diào)用出錯處理程序,注意: 可歸約的串在棧頂,不會在內(nèi)部,二 直觀算符優(yōu)先分析法 1 定義: 任二個相繼出現(xiàn)的終結(jié)符a與b(可能中間有VN),可能有以下優(yōu)先關(guān)系: a b a的優(yōu)先性低于b a b a的優(yōu)先性等于b a b a的優(yōu)先性高于b,2 例5.3 文法G: E E + E | E * E | EE | ( E ) | i 的終結(jié)符的優(yōu)先關(guān)系見下表。,優(yōu) 先 表,E E+E | E*E | EE |(
5、E )| i,3 使用如上分析表,構(gòu)造分析算法(直觀算符優(yōu)先分析法),分析算法步驟: 下一個輸入符號讀至a中; 若a為i,則aOPND,轉(zhuǎn)第一步; 若 a,則調(diào)用關(guān)于的處理程序(語義程序),處理子表達式 : E(1)E(2) ;然后重新進入第3步;(其中, E(1) 、E(2)分別為OPND棧的次棧頂和棧頂),a,OPTR,OPND,#,,,,E (1),E (2),E(3),,,=,若 a,則 若=(,a=),則逐出OPTR棧頂?shù)?,放棄a中的 ),轉(zhuǎn)第 1步; 若=a=#,分析成功結(jié)束; 若 a,aOPTR棧,轉(zhuǎn)第1步; 與a不存在優(yōu)先關(guān)系,則輸入串錯誤,調(diào)出錯處理,),OPTR,O
6、PND,#,(,,,E (1),E (2),a,,,,#,,,成功!,2 例5.4 由文法G: E E + E | E * E | EE | ( E ) | i 的終結(jié)符的優(yōu)先關(guān)系表及上述分析算法 分析算術(shù)表達式 i1 + i2 * i3 # 的過程。,OPTR,OPND,分析過程, OPND棧為空, # -OPTR棧, i1-OPND # OPTR i2-OPND,,,,,,,,,#,+,i1,i2,i3,*,t,e,輸入串 :,i1 + i2 * i3 #,+OPTR i3-OPND,* # , *彈出OPTR棧; i2 * i3 = t -OPND, + # , +彈出OP
7、TR棧; t + i1 = e -OPND, # =# , 分析成功; e 為整個表達式的結(jié)果,1 算符優(yōu)先文法 定義一 如果一個文法的任何產(chǎn)生式右部都不含兩個相繼(并列)的非終結(jié)符,即不含有如下形式的產(chǎn)生式右部: QR 則我們稱該文法為算符文法。,三 算符優(yōu)先分析,定義二 假定G是一個不含-產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b,我們說: a b, 當且僅當文法G中含有形如P-ab 或P-aQb的產(chǎn)生式; (如:(E),則( )) a b, 當且僅當G中含有形如P-aR的產(chǎn)生式,而R b 或 R Qb; a b, 當且僅當G中含有形如P-Rb的產(chǎn)生式,而R a 或
8、R aQ。,定義三 如果一個算符文法G中的任何終結(jié)符對(a,b)至多只滿足下述三種關(guān)系之一: a b,a b,a b 則稱G是一個算符優(yōu)先文法。,2 從算符優(yōu)先文法構(gòu)造優(yōu)先關(guān)系表,構(gòu)造優(yōu)先關(guān)系表,就是要找出所有VT對之間的三種關(guān)系,而對于 可以直接檢查所有的G中P來得到。而 , 關(guān)系不易檢查,故要定義二個集合。 FIRSTVT(P)=a|P a或P Qa,aVT 而QVN LASTVT(P)=a|P a或P aQ,aVT 而QVN 如該二集合成功,檢查P,就可確定滿足 , 的(a,b)對。 這是因為,假定有個產(chǎn)生式候選式: aP,那么對任何 bFIRSTVT(P),有a b;
9、 Pb,那么對任何 aLASTVT(P),有a b;,構(gòu)造該二個集合的算法,對每一 VN的FIRSTVT(P) 、LASTVT(P) 使用每個VN的FIRSTVT(P) 、LASTVT(P),檢查每一個產(chǎn)生式,找出所有(a,b)的關(guān)系,就完成了構(gòu)造優(yōu)先關(guān)系表。,因此,問題歸結(jié)為:,3 構(gòu)造集合FIRSTVT(P)的算法 P-a或P-Qa,則aFIRSTVT(P); 若aFIRSTVT(Q),且有產(chǎn)生式P-Q,則aFIRSTVT(P),4 構(gòu)造集合LASTSTVT(P)的算法 P-a 或 P-aQ,則aLASTVT(P); 若aLASTVT(Q),且有產(chǎn)生式P-Q,則aLASTVT(P),5 構(gòu)
10、造優(yōu)先表方法 對形如 P-ab和形如P-aQb,有a b; 對形如 P-aR,而bFIRSTVT(R),有a b; 對形如 P-Rb,而aLASTVT(R),有a b; 對文法開始符號S,有# FIRSTVT(S),LASTVT(S) #, 且對 #S#,有# #。,FIRSTVT(P)的自動構(gòu)造,過程INSERT: PROCEDURE INSERT(P,a) IF NOT FP,a THEN BEGIN FP,a := TRUE; 把(P,a)下推進STACK棧 END;,主程序:,BEGIN FOR 每個非終結(jié)符P和終結(jié)符a DO FP,a := FALSE; FOR 每個形如P-
11、a 或P-Qa的產(chǎn)生式 DO INSERT(P,a); WHILE STACK 非空 DO BEGIN 把STACK的頂項,記為(Q,a),彈出去 FOR 每條形如P-Q的產(chǎn)生式 DO INSERT(P,a) END OF WHILE; END,LASTVT(P)的自動構(gòu)造,過程INSERT: PROCEDURE INSERT(P,a) IF NOT LP,a THEN BEGIN LP,a := TRUE; 把(P,a)下推進STACK棧 END;,主程序:,BEGIN FOR 每個非終結(jié)符P和終結(jié)符a DO LP,a := FALSE; FOR 每個形如P- a 或P- aQ
12、的產(chǎn)生式 DO INSERT(P,a); WHILE STACK 非空 DO BEGIN 把STACK的頂項,記為(Q,a),彈出去 FOR 每條形如P- Q的產(chǎn)生式 DO INSERT(P,a) END OF WHILE; END,優(yōu)先表的自動構(gòu)造,FOR 每條產(chǎn)生式P-X1X2Xn DO FOR i := 1 TO n-1 DO BEGIN IF Xi和Xi+1均為終結(jié)符 THEN 置Xi Xi+1 IF in2且Xi和Xi+2都為終結(jié)符 但Xi+1為非終結(jié)符 THEN 置Xi Xi+2; IF Xi為終結(jié)符而Xi+1為非終結(jié)符THEN FOR FIRSTVT(Xi+1)
13、中的每個a DO 置 Xi a; IF Xi為非終結(jié)符而Xi+1為終結(jié)符 THEN FOR LASTVT(Xi)中的每個a DO 置 a Xi+1 END,6 算符優(yōu)先分析算法的設(shè)計 定義 1)文法G,開始符號S,若S ,如果 S 且 A , 則稱是句型的一個短語。 2)所謂素短語是指這樣一個短語,它至少含有一個終結(jié)符,并且,除自身之外,不再含任何更小的素短語。 3)句型最左邊的那個素短語叫最左素短語。,最左素短語滿足以下條件的最左子串 Njaj NiaiNi+1, aj-1 aj aj aj+1 , , ai-1 ai ai ai
14、+1,定理 算符優(yōu)先文法的句型一般形式:#N1a1N2a2NnanNn+1# 其中,ai VT,Ni VN|,算法分析:,也即: aj-1 ai+1 Nj aj ai Ni+1,2 例5.5 i1 *( i2 + i3) # # i1 * ( i2 + i3 ) # i1,i2,i3是素短語;i1是最左素短語。,,IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR UNTIL a=#,k:=1; Sk:=#; REPEAT 把下一個輸入符號讀進a中; IF SkVT THEN j
15、:=k ELSE j:=k-1; WHILE Sj a DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q 把Sj+1Sk歸約為某個N; k:=j+1; Sk:=N; END OF WHILE;,,7 優(yōu)先函數(shù) 定義: 我們把每個終結(jié)符與兩個自然數(shù)f() 和g()相對應(yīng),使得: 若1 2,則f(1)g(2) 函數(shù) f 稱為入棧優(yōu)先函數(shù),g 稱為比較優(yōu)先函數(shù)。,使用優(yōu)先函數(shù)的優(yōu)缺點: 優(yōu):便于比較運算;節(jié)省存儲空間。 缺:對不存在優(yōu)先關(guān)系的兩個終結(jié)符,由于與自然數(shù)相 對應(yīng),變成可比較。,優(yōu)先
16、函數(shù)的性質(zhì): 1)正確性: 優(yōu)先函數(shù)掩蓋了矩陣中出錯元素對,若f(id) 17、應(yīng)兩個符號fa,ga。 把所建立的符號盡可能劃分為許多組: 若a b,則fa和gb就在一組; 若a b,c b,則fa和fc同組; 建立一個有向圖,其結(jié)點是上一步中找出的組。 對于任何a和b,若 a b,畫 fagb 弧,意味著f(a)g(b); 若 a b,畫 gbfa 弧,意味著f(a) 18、,,,,,,,,,,,,,,,,,,,,*,,,,,,,,,,,,,,,,,,其余類同,4,6,6,2,9,3,5,8,8,2,LR分析法,語法分析概述(見圖1) LR分析程序(器):自左向右掃描,識別句柄,自下而上歸約的 語法分析程序。 LR分析程序生成器:自動生成LR分析程序的程序。 LR分析程序(見圖2),圖 1(返回),,圖 2(返回),分析表的構(gòu)造方法(見圖3),圖 3,1、 LR分析程序 A、LR分析程序的實質(zhì):分析棧DFA(見圖4),圖 4,B、LR分析的核心分析表,分析表由ACTION表和GOTO表兩部分組成。 ACTION(s,a):表示當狀態(tài)s面臨輸入a時的動作 GOTO( 19、s,x):表示面對文法符號x的下一狀態(tài),ACTIONs,a表中的動作種類: 移進 歸約 接受 報錯,C、給出下述文法G的LR分析表, 文法G (1)EE+T (2) ET (3) TT *F (4) TF (5) F(E) (6) Fi, 分析表(圖 5), 分析表中記號的含義 sj: 把下一狀態(tài) j 和現(xiàn)行輸入符號 a 移進棧; rj: 按第 j 個產(chǎn)生式進行歸約; acc: 接受; 空白格:出錯標志,報錯,圖 5,例 5.8 利用上述分析表,假定輸入串為 i * i + i ,描述LR分析器的工作過程。,狀 態(tài),符 號,輸入串,(1) 0#i * 20、 i + i # (2) 05#i * i + i # (3) 03#F * i + i # (4) 02#T * i + i # (5) 027#T* i + i # (6) 0275#T*i + i # (7) 02710#T*F + i # (8) 02#T + i # (9) 01#E + i #,,,,,ACTION 0, i =s5 移進 5 和 i,,,,,ACTION 5, * =r6 按第6個產(chǎn)生式進行歸約,即: (6) Fi,,,,,,GOTO0,F=3 移進狀態(tài)3,,,,,ACTION 10, + =r3 按第3個產(chǎn)生式進行歸約,即 (3) TT *F,,,,, 21、,,,GOTO0,T=2 移進狀態(tài)2,,例5.8 利用上述分析表,假定輸入串為 i * i + i ,描述LR分析器的工作過程。(續(xù)),狀 態(tài),符 號,輸入串,(10) 016#E+ i # (11) 0165#E+i # (12) 0163#E+F # (13) 0169#E+T # (14) 01#E #,,,ACTION1,#=acc 接受輸入串!,D、LR文法, LR(k)文法:一個文法,如果能用一個每步頂多向前檢查k個輸入符號的LR分析器進行分析,則這個文法就稱為LR(k)文法。,定義:對于一個文法,如果能夠構(gòu)造一張分析表,使得它的每個入口均是唯一確定的,則我們把這個文法稱為 22、LR文法。,A、LR(0)分析表的構(gòu)造步驟 確定G的LR(0)項目 以LR(0)項目為狀態(tài),構(gòu)造一個能識別文法G的所有活前綴的NFA 利用子集法,將NFA確定化,成為以項目集合為狀態(tài)的DFA根據(jù) 上述DFA可直接構(gòu)造出LR分析表,2、LR(0)分析表的構(gòu)造,定義:文法G每一個產(chǎn)生式的右部添加一個圓點,稱為 G的一個LR(0)項目。 如:AXY對應(yīng)三個項目: AXY AXY AXY 而: A的項目 A,B、LR(0)項目(簡稱項目),項目的意義:指明在分析過程的某時刻,我們看到產(chǎn) 生式多大一部分 項目在計算機中的表示:(m,n) int m,n m:代表 23、產(chǎn)生式編號 n:指出圓點的位置,如:abc前綴:,a,ab,abc 活前綴:規(guī)范句型的一個前綴,該前綴是不含句柄之后 的任何符號。,C、字的前綴:指該字的任意首部,D、對文法G,構(gòu)造能識別G的所有活前綴的NFA,NFA的狀態(tài):是一個LR(0)項目 構(gòu)造方法:,,a.文法開始符號的形如SS的項目為NFA的唯一初態(tài); b.若狀態(tài)i和j出自同一個產(chǎn)生式,而且j的圓點只落后于I 的圓點一個位置,就從i畫一條標志為Xi的弧到j(luò)。 (即,i:XX1Xi-1XiXn j:XX1 Xi-1XiXn) c.若狀態(tài)i的圓點之后的符號為非終結(jié)符,如I為 XA,其中A屬于VN,就從狀態(tài)i畫弧到 24、所有 A狀態(tài)。,例2.構(gòu)造以下文法的NFA,文法G的所有LR(0)項目,文法 G S E E aA|bB A cA|d B cB|d,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 ,利用上述規(guī)則a,b,c 25、構(gòu)造NFA,如圖所示:,E、使用子集方法,將NFA確定化,使之成為一個以項目集合為狀態(tài)的DFA。 相關(guān)定義: LR(0)項目集規(guī)范族:構(gòu)成識別一個文法活前綴的DFA 的項目集(狀態(tài))的全體。 歸約項目:A 接受項目:S(S文法的開始符號) 移進項目:Aa(a終結(jié)符) 待約項目:AB(B非終結(jié)符),利用CLOSURE方法構(gòu)造LR(0)項目集規(guī)范族 拓廣文法,CLOSURE(I)算法(其中I為G的任一項目集) I的任何項目都屬于CLOSURE(I); 若A-B屬于CLOSURE(I),那么,對任何關(guān)于B的 產(chǎn)生式B-,項目B-也屬于CLOSURE(I); 重復(fù)執(zhí)行上述兩步驟直至C 26、LOSURE(I)不再增大為止。,構(gòu)造項目集規(guī)范族方法(見下頁),步驟一:令NFA的初態(tài)為I,求其CLOSURE(I),得到初態(tài)項目集。即: 求CLOSURE(SS) 步驟二:對所得項目集I和文法G的每個文法符號X(包括VT和VN) 計算GO(I,X) =CLOSURE(J),得到新的項目集。 其中J=任何形如A X 的項目| A X 屬于I 步驟三:重復(fù)步驟二,直至沒有新的項目集出現(xiàn)。 經(jīng)過以上步驟構(gòu)造出的項目集的全體即為LR(0)項目集規(guī)范族。,利用LR(0)項目集規(guī)范族和GO函數(shù)畫出DFA, 相關(guān)定義: LR(0)文法:不存在以下兩種沖突的文法 移進歸約沖 27、突 歸約歸約沖突 LR(0)表:由LR(0)文法得到的分析表 LR(0)分析器:使用LR(0)表的分析器,F、LR(0)分析表的構(gòu)造,分析表的構(gòu)造方法 如下: a、若項目Aa屬于Ik且GO(Ik,a) Ij,a為終結(jié)符,且置 ACTIONk,a為“把(j,a)移進?!保営洖椤皊j”; b、若項目A屬于Ik,那么,對任何輸入符號a(或者結(jié)束符) 置ACTIONk,a為“用產(chǎn)生式A進行歸約”,簡記為“rj”;其 中,假定A為文法G的第j個產(chǎn)生式; c、若項目SS屬于Ik,則置ACTIONk,為“接受”,簡記為 “acc”; d、若GO(Ik,A)Ij,A為非終結(jié) 28、符,則置GOTOk,Aj; e、分析表中凡不能使用規(guī)則1至4填入信息的空白格均置上“出錯標 志”。,例3.根據(jù)例2的結(jié)果,將其NFA確定化 ,并構(gòu)造該文法的 LR(0)分析表。假定這個文法的各個產(chǎn)生式的編號如 下: 0、S E 1、E aA 2、E bB 3、A cA 4、A d 5、B cB 6、B d,DFA構(gòu)造:(部分),CLOSURE ( S-E ) = S-E, E-aA, E-bB 此即為DFA的狀態(tài)0,令I(lǐng) = S-E, E-aA, E-bB GO( I, a ) = CLOSURE( E-aA ) //即I中所有圓點之后緊跟a的 29、= E-aA, A-cA, A-d GO( I, b ) = CLOSURE( E-bB ) = E-bB, B-cB, B-d GO( I, E ) = CLOSURE( S-E ) = S-E ,同上步驟,依次對各項目集進行計算(略) LR(0)分析表構(gòu)造,(DFA部分圖,全圖見下頁),該文法的LR(0)分析表如下所示:,A、若LR(0)規(guī)范族中含有沖突項目,采用向前展望方法解決 例4. 若I=Xb,A,B 若當前輸入符號為b,則含有移進歸約沖突; 而A和B,又含有歸約歸約沖突。 解決辦法: 考察FOLLOW(A)和FOLLOW(B) (設(shè)FOLLOW( 30、A)FOLLOW(B)為空,且均不含b),3、SLR表的構(gòu)造方法,則當 I 面臨任何輸入符號a時,可做出如下“移進歸約 決策: 若a=b,移進; 若a屬于FOLLOW(A),則用A歸約; 若a屬于FOLLOW(B),則用B歸約; 此外,報錯。 B、回顧FOLLOW(A)的計算。(其中A是非終結(jié)符) 注:FIRST集是針對終結(jié)符、非終結(jié)符和產(chǎn)生式構(gòu)造的; FOLLOW集僅對非終結(jié)符構(gòu)造。,C、SLR表的構(gòu)造方法 若項目Aa屬于Ik且GO(Ik,a) Ij,a為終結(jié)符,且置 ACTIONk,a為“把狀態(tài)j和符號a移進棧”,簡記為“sj”; 若項目A屬于Ik,那么,對任 31、何輸入符號a, aFOLLOW(A),置ACTIONk,a為“用產(chǎn)生式A進 行歸約”,簡記為“rj”;其中,假定A為文法G的第j個 產(chǎn)生式; 若項目SS屬于Ik,則置ACTIONk,為“接受”,簡 為“acc”; 若GO(Ik,A)=Ij,A為非終結(jié)符,則置GOTOk,A= j; 分析表中凡不能使用規(guī)則1至4填入信息的空白格均置上“出 錯標志”。,只在歸約時 32、 展望,即已到產(chǎn)生式末尾,則去判斷FOLLOW(A),文法 G: (0) SE (1) EE+T (2) ET 33、 (3) TT*F (4) TF (5) F(E) (6) Fi,例4:對如下文法構(gòu)造其SLR分析表。,該文法的LR(0)項目集規(guī)范族 由這些項目集的轉(zhuǎn)換函數(shù)GO表示成的DFA 文法G的非終結(jié)符的FOLLOW集如下: FOLLOW(S)= # FOLLOW(E)= +,),# FOLLOW(T)= +, * , ) , # FOLLOW(F)= +, * , ) , # SLR分析表,文法 G 的SLR分析表如下所示:,問題:有些無二義文法會產(chǎn)生“移進/歸約”沖突 或“歸約/歸約”沖突 產(chǎn)生原因:SLR分析法未包含足夠多的“展望”信息 解決辦法:讓每個狀態(tài)含有更多的“ 34、展望”信息,4、規(guī)范LR分析表的構(gòu)造,方法:重新定義項目,使得每個項目都附帶有k個終結(jié)符; 即每個項目的形式為:A- , a1a2ak,向前搜索符串僅對歸約項目A-, a有意義; 歸約項目A-, a意味著:當它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的k個輸入符號為a1a2ak 時,才可以把棧頂上的歸約為A 只研究k1的情形,定義:如上形式的項目稱為一個LR(k)項目。,說明:,A、構(gòu)造規(guī)范LR分析表的步驟:,確定LR(1)項目; 根據(jù)LR(1)項目構(gòu)造NFA; 利用函數(shù)CLOSURE和GO求DFA; 根據(jù)DFA,構(gòu)造LR分析表。,B、確定LR(1)項目,確定LR(1)項目的方法: 對S和S,只向前搜索 # 35、 ; 其它產(chǎn)生式,對每一個VT均向前搜索。,由: S-S,#S-S,# S-BB,#S-BB,#S-BB,#,由: B-aB,a B-aB,b B-aB,# B-aB,a B-aB,b B-aB,# B-aB,a B-aB,b B-aB,# B-b,a B-b,b B-b,# B-b,a B-b,b B-b,#,C、 利用LR(1)項目構(gòu)造NFA 構(gòu)造方法:同LR(0)構(gòu)造識別活前綴的NFA方法相同,D、構(gòu)造有效的LR(1)項目集族(即求DFA),項目集I的閉包CLOSURE(I)構(gòu)造方式 函數(shù)GO(I,X)的定義 LR(1)項目集族C的構(gòu)造算法,E、根據(jù)DFA,構(gòu)造LR分析表,a、若項目Aa 36、,b屬于Ik且GO(Ik,a) Ij,a為終結(jié)符,則置 ACTIONk,a為“把(j,a)移進?!?,簡記為“sj”; b、若項目A,a屬于Ik,則置ACTIONk,a為“用產(chǎn)生式A歸約”,簡記為“rj”;其中,假定A為文法G的第j個產(chǎn)生式; c、若項目SS,#屬于Ik,則置ACTIONk,為“接受”,簡記為 “acc”; d、若GO(Ik,A)Ij,A為非終結(jié)符,則置GOTOk,Aj; e、分析表中凡不能使用規(guī)則1至4填入信息的空白格均置上“出錯標 志”。,5、LALR分析表的構(gòu)造,問題:對于一般的語言,規(guī)范LR分析表要用幾千個狀態(tài),無法實際應(yīng)用 分析:由例6中可以看到, 37、有些狀態(tài)集除了搜索符不同外是兩兩相同的 解決辦法:合并同心集,構(gòu)造LALR分析表,我們稱兩個LR(1)項目集具有相同的心,如果除去搜索符之后,這兩個集合是相同的。,將所有同心的LR(1)項目集合并后,得到一個心就是一個LR(0)項目集。,說明:,合并同心集不會產(chǎn)生新的移進-歸約沖突,但有可能產(chǎn)生新的“歸約-歸約”沖突。,對于同一個文法,LALR分析表和SLR分析表永遠具有相同數(shù)目的狀態(tài),卻能處理一些SLR所不能對付的事情。,合并項目集時不用修改轉(zhuǎn)換函數(shù),即GO(I,X);動作ACTION應(yīng)進行修改,使得能夠反映各被合并的集合的既定動作。,A、構(gòu)造LALR分析表的第一個算法,步驟: 構(gòu)造文法G的 38、LR(1)項目集族C=I0,I1,In 把所有的同心集合并在一起,記C=J0,J1,Jm為合并后的新族。那個含有項目S-S,#的Jk為分析表的初態(tài) 從C構(gòu)造ACTION表 構(gòu)造GOTO表 分析表中凡不能用3、4天入信息的空白格均填上“出錯標志”,,a、若項目Aa,b屬于Jk且GO(Jk,a) Jj,a為終結(jié)符,則置ACTIONk,a為 “sj”; b、若項目A,a屬于Jk,則置ACTIONk,a為“用產(chǎn)生式A歸約”,簡記為“rj”;其中,假定A為文法G的第j個產(chǎn)生式; c、若項目SS,#屬于Jk,則置ACTIONk,為“接受”,簡記為“acc”;,從C構(gòu)造ACTION表,把狀態(tài)3,6、4, 39、7和8,9分別合并成,I36: B-aB,a /b/# B-aB,a /b/# B-b,a /b/# I47: B-b,a /b/# I89:B-aB,a /b/#,由合并后的集族所構(gòu)成的LALR分析表,B、構(gòu)造LALR分析表的另一算法,問題:對任何文法G,通過構(gòu)造它的LR(1)項目集,合并同心集,最后形成LALR(1)項目集 ,該算法太費存儲空間。 解決辦法:注意到各種項目集都是以一定項目為核的閉包。若用核代替閉包,則不論哪一種項目集都將大大縮小它的存儲空間,相關(guān)定義,使用核構(gòu)造分析表,任何項目集的核是由此集中所有那些圓點不在最左端的項目組成的。 初態(tài)項目集的核含有(而且只含有)項目S-S, 40、#,通過核構(gòu)造GOTO表: 若GO(I,X)=J,I的核為K,J的核為L。顯然,若A- X,a屬于K,則A- X,aA- X,a屬于L。,對每對非終結(jié)符C和A都預(yù)先計算出它們是否有關(guān)系: C A ,通過核構(gòu)造ACTION表: 令I(lǐng)是一個項目集,K是它的核。若ACTIONI,a為用“A-歸約”。那么, 若,則項目 A- 必屬于K; 若=,則K中必有某個項目B- C,b, 其中C A,且a屬于FIRST(b)。,為每個LR(0)集核的每個項目都配上一個搜索符集,使得這個核成為一個LALR(1)集的核,SPONSOR算法 LR(0)初態(tài)集核的唯一項目 S-S 具有搜索符#; 應(yīng)用SPONSOR算 41、法從初態(tài)集核開始計算每個核各個項目的全部自生搜索符。,LALR(1)項目集(核)的構(gòu)造算法 利用三元式(I,A- ,a)棧來跟蹤由前述算法產(chǎn)生的自生搜索符的傳播;,構(gòu)造G的所有LR(0)集的核; 從CLOSURE(S-S,#)開始,利用SPONSOR算每個狀態(tài)的核的自生搜索符; 利用LALR(1)項目集核構(gòu)造算法逐個進行傳播計算。,綜上,構(gòu)造拓廣文法的LALR(1)項目集(核)的步驟如下:,從初態(tài)開始: I0:CLOSURE S-S,# = S-S,# S-L=R,# S-R,# L-*R,= L-i,= R-L,# L-*R,# L-i,# ,初態(tài)中具有搜索符#的 S-S 進棧; 即: 42、( I0, S-S, # ) 入棧,I0:CLOSURE S-S,# = S-S,# S-L=R,# S-R,# L-*R,= L-i,= R-L,# L-*R,# L-i,# ,( I0, S-S, # ),( I4, L-*R, = ),( I5, L-i, = ),,( I7, L-*R, = ),( I8, R-L, = ),( I2,S-L=R, # ),( I3, S-R, # ),( I2,R-L, # ),( I4, L-*R, # ),( I5, L-i, # ),( I1, S-S, # ),( I8,R-L, # ),( I9, S-L=R, # ),棧的變 43、化狀態(tài),( I6,S-L=R, # ),I4:CLOSURE L-*R, = = L-*R, = R-L,= L-*R,= L-i,= ,I2:CLOSURE S-L=R, # = S-L=R, # ,I6:CLOSURE S-L=R, # = S-L=R, # R-L,# L-*R,# L-i,# ,I4:CLOSURE L-*R, # = L-*R, # R-L,# L-*R,# L-i,# ,( I7, L-*R, # ),最終得到該文法的LALR(1)集核為:,參考資料,陳火旺,程序設(shè)計語言編譯原理(第三版),國防工業(yè)出版社,83129 馮博琴譯,現(xiàn)代編譯程序設(shè)計,郵電出版社,2.2.3,2.2.4 Kenneth C. Louden,馮博琴 等譯,編譯原理與實踐,機械工業(yè)出版社,
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 6.煤礦安全生產(chǎn)科普知識競賽題含答案
- 2.煤礦爆破工技能鑒定試題含答案
- 3.爆破工培訓(xùn)考試試題含答案
- 2.煤礦安全監(jiān)察人員模擬考試題庫試卷含答案
- 3.金屬非金屬礦山安全管理人員(地下礦山)安全生產(chǎn)模擬考試題庫試卷含答案
- 4.煤礦特種作業(yè)人員井下電鉗工模擬考試題庫試卷含答案
- 1 煤礦安全生產(chǎn)及管理知識測試題庫及答案
- 2 各種煤礦安全考試試題含答案
- 1 煤礦安全檢查考試題
- 1 井下放炮員練習(xí)題含答案
- 2煤礦安全監(jiān)測工種技術(shù)比武題庫含解析
- 1 礦山應(yīng)急救援安全知識競賽試題
- 1 礦井泵工考試練習(xí)題含答案
- 2煤礦爆破工考試復(fù)習(xí)題含答案
- 1 各種煤礦安全考試試題含答案