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