【文章內(nèi)容簡介】 國防科技大學(xué)計算機系 602教研室 ? 分析開始時 : 狀態(tài) 已歸約串 輸入串 (s0， ， a1a2 ? an ) ? 以后每步的結(jié)果可以表示為 : (s0 s1 ? sm ， X1 ? Xm ， aiai+1 ? an ) 國防科技大學(xué)計算機系 602教研室 (s0 s1 ? sm ， X1 ? Xm ， aiai+1 ? an ) ?分析器根據(jù) ACTION(sm , ai)確定下一步動作 1. 若 ACTION(sm , ai)為移進(jìn)，且 s，則三元式格局變?yōu)?: (s0 s1 ? sms ， X1 ? Xm ai， ai+1 ? an )) 2. 若 ACTION(sm , ai)為按 A??歸約，三元式變?yōu)?: (s0 s1 ? smrs ， X1 ? XmrA ， aiai+1 ? an )) 此處 , s=GOTO(smr, A), r為 ?的長度 , ?= Xmr+1? Xm 3. 若 ACTION(sm , ai)為 接受 ，則三元式不再變化，變化過程終止，宣布分析成功 . 4. 若 ACTION(sm , ai)為 報錯 ，則三元式變化過程終止，報告錯誤 . 國防科技大學(xué)計算機系 602教研室 LR分析器示例： 文法 G(E)： (1) E→E ＋ T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i 國防科技大學(xué)計算機系 602教研室 AC TION GOTO狀態(tài) i + * ( ) E T F0 s5 s4 1 2 31 s6 acc2 r2 s7 r2 r23 r4 r4 r4 r44 s5 s4 8 2 35 r6 r6 r6 r66 s5 s4 9 37 s5 s4 108 s6 s119 r1 s7 r1 r110 r3 r3 r3 r311 r5 r5 r5 r5其 LR分析表為 : 國防科技大學(xué)計算機系 602教研室 ? 假定輸入串為 i*i+i， LR分析器的工作過程 : 步驟 狀態(tài) 符號 輸入串 (1) 0 i*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 (10) 016 E+ i 國防科技大學(xué)計算機系 602教研室 步驟 狀態(tài) 符號 輸入串 (11) 0165 E+i (12) 0163 E+F (13) 0169 E+T (14) 01 E (15) 接受 E E * T T + F F F i i i 國防科技大學(xué)計算機系 602教研室 ? 定義：對于一個文法，如果能夠構(gòu)造一張分析表，使得它的每個入口均是唯一確定的，則這個文法就稱為 LR文法 。 ? 定義：一個文法，如果能用一個每步頂多向前檢查 k個輸入符號的 LR分析器進(jìn)行分析，則這個文法就稱為 LR(k)文法 . ? 非 LR結(jié)構(gòu) ?LR文法不是二義的，二義文法肯定不會是 LR的。 S ? iCtS | iCtSeS 棧 輸入 …iCtS e… 國防科技大學(xué)計算機系 602教研室 LR(0)項目集族和 LR(0)分析表的構(gòu)造 ? 字的前綴 ：是指字的任意首部，如字 abc的前綴有 ?， a， ab， abc ? 活前綴 ：是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。即，對于規(guī)范句型 ???， ?為句柄，如果 ??=u1u2…u r，則符號串 u1u2…u i(1?i?r)是 ???的 活前綴 。 (?必為終結(jié)符串 ) ? 對于一個文法 G, 可以構(gòu)造一個 DFA,它能識別 G的所有活前綴 . 國防科技大學(xué)計算機系 602教研室 ? 文法 G的每個產(chǎn)生式的右部添加一個圓點稱為 G的 LR(0)項目 ? 如 :A?XYZ有四個項目： A?.XYZ A? A? A?XYZ. ?A?? . 稱為 歸約項目 ?歸約項目 S??? . 稱為 接受項目 ?A?? .a? (a?VT) 稱為 移進(jìn)項目 ? A?? .B? (B?VN) 稱為 待約項目 . 國防科技大學(xué)計算機系 602教研室 ?文法 G(S?) S?→E E→aA|bB A→cA|d B→cB|d ? 該文法的項目有： 1. S?→E 2. S?→E 3. E→aA 4. E→aA 5. E→aA 6. A→cA 7. A→cA 8. A→cA 9. A→d 10. A→d 11. E→bB 12. E→bB 13. E→bB 14. B→cB 15. B→cB 16. B→cB 17. B→d 18. B→d 國防科技大學(xué)計算機系 602教研室 ? 構(gòu)造識別文法所有活前綴的 NFA方法 1. 若狀態(tài) i為 X?X1 … X … X n ， 狀態(tài) j為 X?X1 … X i1Xi .Xi+1 … X n ， 則從狀態(tài) i畫一條標(biāo)志為 Xi的有向邊到狀態(tài) j； 2. 若狀態(tài) i為 X?? .A? ， A為非終結(jié)符， 則從狀態(tài) i畫一條 ?邊到所有狀態(tài) A?.?。 ? 把識別文法所有活前綴的 NFA確定化。 ? 構(gòu)成識別一個文法活前綴的 DFA的項目集(狀態(tài) )的全體稱為文法的 LR(0)項目集規(guī)范族 。 國防科技大學(xué)計算機系 602教研室 6 7 8 9 10 4 5 3 1 2 11 12 13 14 15 16 18 17 ? ? ? ? ? ? ? a ? ? ? A E b B B c A c d 識別活前綴的 NFA 國防科技大學(xué)計算機系 602教研室 識別活前綴的 DFA 0: S?→E E→aA E→bB 4: A→cA A→cA A→d 2: E→aA A→cA A→d 1: S?→E 3: E→bB B→cB B→d 5: B→cB B→cB B→d 11: B→d 9: B→cB 7: E→bB 10: A→d 6: E→aA 8: A→cA c c b E a d A c c d d d B A B 國防科技大學(xué)計算機系 602教研室 有效項目 ? 我們說項目 A? ?1.?2對活前綴 ??1是有效的，其條件是存在規(guī)范推導(dǎo) ?????? 21R*RAS ????在任何時候，分析棧中的活前綴 X1X2 … Xm的有效項目集正是棧頂狀態(tài) Sm所代表的那個集合。也正是從識別活前綴的 DFA的初態(tài)出發(fā)，讀出 X1X2 … X m后到達(dá)的那個項目集 (狀態(tài) )。 國防科技大學(xué)計算機系 602教研室 ? 結(jié)論 : 若項目 A?? .B?對活前綴 ?=??是有效的且 B ? ?是一個產(chǎn)生式，則項目 B ? .?對 ?=??也是有效的。 ?????? BASRR???* 所以， B ? .?對 ?=??也是有效的。 ? ? ? ? ???????????RRRRBBAS ????**????*R?設(shè) ，那么 國防科技大學(xué)計算機系 602教研室 ? 文法 G(S?) S?→E E→aA|bB A→cA|d B→cB|d ? 考慮： 項目： B ? B ? . cB B ? . d 活前綴： bc S?? E ? bB ? bcB S?? E ? bB ? bcB ?bccB S?? E ? bB ? bcB ? bcd 國防科技大學(xué)計算機系 602教研室 LR(0)項目集規(guī)范族的構(gòu)造 ? 假定文法 G是一個以 S為開始符號的文法 ，我們構(gòu)造一個 G?， 它包含了整個 G， 但它引進(jìn)了一個不出現(xiàn)在 G中的非終結(jié)符 S?，并加進(jìn)一個新產(chǎn)生式 S?→S ， 而這個 S?是G?的開始符號 。 那么 ， 我們稱 G?是 G的 拓廣文法 。 這樣 ， 便會有一個僅含項目S?→S .的狀態(tài) ， 這就是唯一的 “ 接受 ” 態(tài) 。 國防科技大學(xué)計算機系 602教研室 ? 假定 I是文法 G?的任一項目集，定義和構(gòu)造I的閉包 CLOSURE(I)如下： 1. I的任何項目都屬于 CLOSURE(I)； 2. 若 A→ ?B ?屬于 CLOSURE(I)，那么，對任何關(guān)于 B的產(chǎn)生式 B→ ?，項目 B→ ?也屬于 CLOSURE(I)； 3. 重復(fù)執(zhí)行上述兩步驟直至 CLOSURE(I) 不再增大為止。 國防科技大學(xué)計算機系 602教研室 ? 為了識別活前綴，我們定義一個狀態(tài)轉(zhuǎn)換函數(shù) GO是一個狀態(tài)轉(zhuǎn)換函數(shù)。 I是一個項目集， X是一個文法符號。函數(shù)值 GO(I，X)定義為： GO(I， X)＝ CLOSURE(J) 其中 J＝ {任何形如 A→ ?X?的項目 | A→ ? X?屬于 I}。 ? 直觀上說，若 I是對某個活前綴 ? 有效的項目集，那么， GO(I， X)便是對 ?X 有效的項目集。 國防科技大學(xué)計算機系 602教研室 ? 文法 G(S?) S?→E E→aA|bB A→cA|d B→cB|d ? I0={S?→E, E→aA, E→bB} GO(I0, E)= c