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