【正文】 國防科技大學計算機系 602教研室 ? 定義：假定 ?是文法 G的一個句子，我們稱序列 ?n， ?n1， ? ， ?0 是的一個 規(guī)范歸約 ，如果此序列滿足： 1 ?n= ? 2 ?0為文法的開始符號，即 ?0=S 3 對任何 i， 0 ? i ? n， ?i1是從 ?i經(jīng)把句柄替換成為相應產(chǎn)生式左部符號而得到的。 特別是，如果有 A??,則稱 ?是句型 ???相對于規(guī)則 A? ?的 直接短語 。 ? 具有規(guī)范的 LR(1)分析表的文法稱為一個LR(1)文法 。 國防科技大學計算機系 602教研室 ? 按上述算法構(gòu)造的分析表，若不存在多重定義的入口 (即，動作沖突 )的情形，則稱它是文法 G的一張 規(guī)范的 LR(1)分析表 。 4. 若 GO(Ik， A)＝ Ij，則置 GOTO[k, A]=j。 3. 若項目 [S?→S 2. 若項目 [A→ ? 國防科技大學計算機系 602教研室 ? 動作 ACTION和狀態(tài)轉(zhuǎn)換 GOTO構(gòu)造如下： 1. 若項目 [A→ ? ?令每個 Ik的下標 k為分析表的狀態(tài)，令含有 [S?→S ， ]})}。?, a]的項目 | [A→ ? 3. 重復執(zhí)行步驟 2，直至 CLOSURE(I)不再增大為止。B ?, a]屬于 CLOSURE(I)， B→ ? 是一個產(chǎn)生式，那么，對于 FIRST(?a) 中的每個終結(jié)符 b，如果 [B→B ?, a]對 ?＝ ??有效， 則有規(guī)范推導 ?????? aBAaS ??* ??? ?)a(FI R S Tb ?? ?是產(chǎn)生式若 ??B????????? bBbaBS ??? **則是有效的對于項目 ?? ],.[ bB ????? ba *??國防科技大學計算機系 602教研室 ?項目集 I 的閉包 CLOSURE(I)構(gòu)造方法： 1. I的任何項目都屬于 CLOSURE(I)。 ?, b]對 ?也是有效的。 國防科技大學計算機系 602教研室 ? [A→ ??, a]對于活前綴 ?是 有效的 ，如果存在規(guī)范推導 ? ? ? ??? ?? AS*其中， 1) ?＝ ??； 2) a是 ?的 第一個符號，或者 a為 而 ?為 ?。 ? 我們只對 k?1的情形感興趣，向前搜索 (展望 )一個符號就多半可以確定“移進”或“歸約”。 國防科技大學計算機系 602教研室 ? 歸約項目 [A→ ?對于任何移進或待約項目 [A→ ? ? 向前搜索符串僅對歸約項目 [A→ ??, a1a2…a k] ，這樣的一個項目稱為一個 LR(k)項目 。 國防科技大學計算機系 602教研室 規(guī)范 LR分析表的構(gòu)造 ? 我們需要重新定義項目，使得每個項目都附帶有 k個終結(jié)符。因此，在這種情況下，用“ A?? ”歸約不一定合適。 國防科技大學計算機系 602教研室 R S = i L R * L * * R i i L 活前綴識別器1203467589國防科技大學計算機系 602教研室 ? SLR在方法中 ,如果項目集 Ii含項目 A??.而且下一輸入符號 a?FOLLOW(A),則狀態(tài) i面臨 a時 ,可選用“用 A??歸約”動作。 I9： S→L=R*R L→R R→i I5： L→iL L→ I4： L→*=R R→LL I1： S?→S*R L→L=R S→ 國防科技大學計算機系 602教研室 這個文法的 LR(0)項目集規(guī)范族為： I0： S?→ 國防科技大學計算機系 602教研室 ? I I2和 I9都含有“移進－歸約”沖突。*F I10: T→T*F +T I9: E→E+Ti I8: F→(EF F→(E) F→T*F T→ I6: E→E+ (E) F→T*F T→E+T E→ I4: F→( T→T E→E (E) F→T*F T→T T→E E→ ? 每個 SLR(1)文法都是無二義的。 國防科技大學計算機系 602教研室 ? 按上述方法構(gòu)造出的 ACTION與 GOTO表如果不含多重入口，則稱該文法為 SLR(1)文法 。 屬于 Ik，則置 ACTION[k,]為“ acc”。a ?屬于 Ik且 GO(Ik,a)=Ij， a為終結(jié)符，則置 ACTION[k,a]為 “ sj”； 2. 若項目 A→ ?S 的集合 Ik的下標 k為分析器的初態(tài)。 ? 沖突性動作的這種解決辦法叫做 SLR(1)解決辦法 。 … ， Bn→ ?a m?m， B1→ ?a 1?1，A2→ ?FOLLOW(A)和 FOLLOW(B)的交集為 ?，且不包含 b， 那么，當狀態(tài) I面臨任何輸入符號 a時，可以 : 1. 若 a=b，則移進； 2. 若 a?FOLLOW(A)，用產(chǎn)生式 A→ ?進行歸約； 3. 若 a?FOLLOW(B)，用產(chǎn)生式 B→ ?進行歸約； 4. 此外，報錯。 B→ ? 國防科技大學計算機系 602教研室 ? LR(0)分析表為 ACTI ON GO TO狀態(tài) a b c d E A B0 s2 s3 11 acc2 s4 s10 63 s5 s11 74 s4 s10 85 s5 s116 r1 r1 r1 r1 r1 97 r2 r2 r2 r2 r28 r3 r3 r3 r3 r39 r5 r5 r5 r5 r510 r4 r4 r4 r4 r411 r6 r6 r6 r6 r6國防科技大學計算機系 602教研室 ? 例 : 按上表對 acccd進行分析 ? 步驟 狀態(tài) 符號 輸入串 1 0 acccd 2 02 a cccd 3 024 ac ccd 4 0244 acc cd 5 02444 accc d 6 0244410 acccd 7 024448 acccA 8 02448 accA 9 0248 acA 10 026 aA 11 01 E 國防科技大學計算機系 602教研室 SLR分析表的構(gòu)造 ? LR(0)文法太簡單， 沒有實用價值 . ? 假定一個 LR(0)規(guī)范族中含有如下的一個項目集(狀態(tài) )I＝ {X→ ? 4. 若 GO(Ik,A)＝ Ij， A為非終結(jié)符，則置GOTO[k,A]=j。 3. 若項目 S?→S 2. 若項目 A→ ? 國防科技大學計算機系 602教研室 ? 分析表的 ACTION和 GOTO子表構(gòu)造方法： 1. 若項目 A→ ? 國防科技大學計算機系 602教研室 構(gòu)造 LR(0)分析表的算法 ? 令每個項目集 Ik的下標 k作為分析器的狀態(tài)，包含項目 S?→ A 7: E→bB d d 9: B→cB d 8: A→cAcA A→ E 2: E→acB B→d c 3: E→bB B→cA A→bB 4: A→cE E→S})}； REPEAT FOR C中每個項目集 I和 G?的每個符號 X DO IF GO(I， X)非空且不屬于 C THEN 把 GO(I， X)放入 C族中 。cA, A→A}) ={ E→a}) = {S?→EaA, E→ 國防科技大學計算機系 602教研室 ? 文法 G(S?) S?→E E→aA|bB A→cA|d B→cB|d ? I0={S?→ X?屬于 I}。函數(shù)值 GO(I，X)定義為： GO(I， X)＝ CLOSURE(J) 其中 J＝ {任何形如 A→ ?X 國防科技大學計算機系 602教研室 ? 為了識別活前綴，我們定義一個狀態(tài)轉(zhuǎn)換函數(shù) GO是一個狀態(tài)轉(zhuǎn)換函數(shù)。B ?屬于 CLOSURE(I)，那么，對任何關(guān)于 B的產(chǎn)生式 B→ ?，項目 B→ 這樣 ， 便會有一個僅含項目S?→S .的狀態(tài) ， 這就是唯一的 “ 接受 ” 態(tài) 。 ? ? ? ? ???????????RRRRBBAS ????**????*R?設 ，那么 國防科技大學計算機系 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 國防科技大學計算機系 602教研室 LR(0)項目集規(guī)范族的構(gòu)造 ? 假定文法 G是一個以 S為開始符號的文法 ，我們構(gòu)造一個 G?，