【正文】 f(b)=g(b) 導(dǎo)致如下矛盾 : f(a) g(b) = f(b) = g(a) = f(a) ?如果優(yōu)先函數(shù)存在，則不唯一 (無窮多 ) 國防科技大學(xué)計算機系 602教研室 ? 如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù) : 1 對于每個終結(jié)符 a，令其對應(yīng)兩個符號 fa和 ga，畫一以所有符號和為結(jié)點的方向圖。 3 檢查所構(gòu)造出來的函數(shù) f和 g是否與原來的關(guān)系矛盾。因為，若 a b，則既有從 fa到 gb的弧，又有從 gb到 fa的弧。也就是，gb能到達(dá)的任何結(jié) fa也能到達(dá)。假若 f(a)＝ g(b)，那么必有如下的回路： 國防科技大學(xué)計算機系 602教研室 因此有 a b, a1 b, a1 b1, …, a m bm, a bm 對任何優(yōu)先函數(shù) f?和 g?來說，必定有 f?(a) g?(b)? f?(a1)? g?(b1)? … ? f?(am)? g?(bm)? f?(a) 從而導(dǎo)致 f?(a) f?(a)，產(chǎn)生矛盾。 S ? iCtS | iCtSeS 棧 輸入 …iCtS e… 國防科技大學(xué)計算機系 602教研室 LR(0)項目集族和 LR(0)分析表的構(gòu)造 ? 字的前綴 ：是指字的任意首部，如字 abc的前綴有 ?， a， ab， abc ? 活前綴 ：是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。 3. E→cA 7. A→c 11. E→cB 15. B→c 國防科技大學(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?.?。E E→cA A→d 1: S?→Ed 5: B→c 9: B→cB 8: A→cA ?????? BASRR???* 所以， B ? .?對 ?=??也是有效的。 國防科技大學(xué)計算機系 602教研室 ? 假定 I是文法 G?的任一項目集，定義和構(gòu)造I的閉包 CLOSURE(I)如下： 1. I的任何項目都屬于 CLOSURE(I)； 2. 若 A→ ? I是一個項目集， X是一個文法符號。 ? 直觀上說，若 I是對某個活前綴 ? 有效的項目集，那么， GO(I， X)便是對 ?X 有效的項目集。bB} GO(I0, E)= closure(J)=closure({S?→EA, A→ UNTIL C 不再增大 END ?轉(zhuǎn)換函數(shù) GO把項目集連接成一個 DFA轉(zhuǎn)換圖 . 國防科技大學(xué)計算機系 602教研室 0: S?→A A→cB B→d b 1: S?→Ed a 11: B→d B 6: E→aAS 的集合 Ik的下標(biāo) k為分析器的初態(tài)。屬于 Ik，那么，對任何終結(jié)符 a(或結(jié)束符 )，置 ACTION[k,a]為 “ rj”(假定產(chǎn)生式A→ ?是文法 G?的第 j個產(chǎn)生式 )。 5. 分析表中凡不能用規(guī)則 1至 4填入信息的空白格均置上“報錯標(biāo)志”。} 。a 2?2， … ， Am→ ?} 如果集合 {a1， … ， am}，F(xiàn)OLLOW(B1)， … ， FOLLOW(Bn)兩兩不相交 (包括不得有兩個 FOLLOW集合有 )，則： 1. 若 a是某個 ai， i=1,2,…,m ，則移進(jìn)； 2. 若 a?FOLLOW(Bi)， i=1,2,…,n ，則用產(chǎn)生式Bi→ ?進(jìn)行歸約； 3. 此外，報錯。 國防科技大學(xué)計算機系 602教研室 ?分析表的 ACTION和 GOTO子表構(gòu)造方法： 1. 若項目 A→ ? 4. 若 GO(Ik,A)＝ Ij， A為非終結(jié)符，則置GOTO[k,A]=j； 5. 分析表中凡不能用規(guī)則 1至 4填入信息的空白格均置上“出錯標(biāo)志”。但也存在許多無二義文法不是 SLR(1)的 . 國防科技大學(xué)計算機系 602教研室 ? 例 考察下面的拓廣文法： (0) S?→E (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i 國防科技大學(xué)計算機系 602教研室 ? 這個文法的 LR(0)項目集規(guī)范族為： I0: S?→T*F T→i I1: S?→E*F I3: T→FT T→i I5 : F→iF F→(E) F→ T→T ? FOLLOW(E)＝ {, ), +}， I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 E + T * T T i F ( i ( F E ( F i + F * ( ) 國防科技大學(xué)計算機系 602教研室 AC TION GO TO狀態(tài) i + * ( ) E T F0 s5 s4 1 2 31 s6 a cc2 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 s1 19 r1 s7 r1 r110 r3 r3 r3 r311 r5 r5 r5 r5其分析表如下 : 國防科技大學(xué)計算機系 602教研室 ? 非 SLR文法示例：考慮如下文法： (0) S?→S (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L 計算 FOLLOW集合所得到的超前符號集合可能大于實際能出現(xiàn)的超前符號集。R S→ I2： S→LR R→ I6： S→L=i I7： L→*R但在有些情況下 ,當(dāng)狀態(tài) i顯現(xiàn)于棧頂時 ,棧里的 活前綴 未必允許把 ?歸約為 A，因為可能根本就不存在一個形如“ ?Aa”的規(guī)范句型。每個項目的一般形式是 [A→ ?a1a2…a k]有意義。, a1a2…a k]意味著：當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的 k個輸入符號為 a1a2…a k 時，才可以把棧頂上的 ?歸約為 A。 國防科技大學(xué)計算機系 602教研室 ? 為構(gòu)造有效的 LR(1)項目集族我們需要兩個函數(shù) CLOSURE和 GO。 ? 證明：若項目 [A→ ? ?, b]原來不在CLOSURE(I)中，則把它加進(jìn)去。X ?, a]?I} 國防科技大學(xué)計算機系 602教研室 ? 文法 G?的 LR(1)項目集族 C的構(gòu)造算法： BEGIN C:={CLOSURE({[S?→S, ] 的 Ik的 k為分析器的初態(tài)。 a]屬于 Ik，則置 ACTION[k, a]為 “ rj”；其中假定 A→ ?為文法 G?的第 j個產(chǎn)生式。 5. 分析表中凡不能用規(guī)則 1至 4填入信息的空白欄均填上“出錯標(biāo)志”。 ? LR(1)狀態(tài)比 SLR多， LR(0)?SLR ? LR(1) ?無二義文法 國防科技大學(xué)計算機系 602教研室 ? 例 ()的拓廣文法 G( S?) (0) S?→S (1) S→BB (2) B→aB (3) B→b 國防科技大學(xué)計算機系 602教研室 LR(1)的項目集 C和函數(shù) GO I0: S’??S, S??BB, B??aB, a/b B? ?b, a/b S I1: S’?S ?, B I2: S?B ? B, B??aB, B? ?b, a I3: B?a?B, a/b B??aB, a/b B? ?b, a/b b I4: B? b ?, a/b B I5: S?BB?, a I6: B?a?B, B??aB, B? ?b, b I7: B? b ?, B I8: B? aB?, a/b a b a I9: B? aB?, B b 國防科技大學(xué)計算機系 602教研室 AC TI ON GOTO狀態(tài) a b S B0 s3 s4 1 21 acc2 s6 s7 53 s3 s4 84 r3 r35 r16 s6 s7 97 r38 r2 r29 r2LR(1)分析表為 : 國防科技大學(xué)計算機系 602教研室 ? 例 : 按上表對 aabab進(jìn)行分析 步驟 狀態(tài) 符號 輸入串 0 0 aabab 1 03 a abab 2 033 aa bab 3 0334 aab ab 4 0338 aaB ab 5 038 aB ab 6 02 B ab 7 026 Ba b 8 0267 Baa 9 0269 BaB 10 025 BB 11 01 S acc 國防科技大學(xué)計算機系 602教研室 ? 例 : 按上表對 abab進(jìn)行分析 步驟 狀態(tài) 符號 輸入串 0 0 abab 1 03 a bab 2 034 ab ab 3 038 aB ab 4 02 B ab 5 026 Ba b 6 0267 Bab 7 0269 BaB 8 025 BB 9 01 S acc 國防科技大學(xué)計算機系 602教研室 基本概念 ? 定義：令 G是一個文法， S是文法的開始符號，假定 ???是文法 G的一個句型，如果有 且 ?? AS *? ???A則 ?稱是句型 ???相對于非終結(jié)符 A的 短語 。 國防科技大學(xué)計算機系 602教研室 作業(yè) ? P133—1， 2， 3 ? P134—5 (1)， (2)， (3), (4) ? P134—8(選作 )