【正文】 在 SLR。 2. 對于狀態(tài) Ii的分析動作如下： (a) 若 A?? . aB ? Ii且 go (Ii ,a)= Ij action[i,a] = shift j (b) 若 A?? . ? Ii, 對于所有 a ? Follow(A) action[i,a] = reduce A?? , A? S? (c) 若 S??S. ? Ii, action[i, $]= accept 3. 若 go(Ii, A) = Ij, A?VN , 則 goto[i,A] = j 4. 分析表其余位置為 error 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 86 (3)SLR分析表 Follow(E)={$, +,)} ACTION GOTO + * ( ) id $ E T F 0 S4 S5 1 2 3 1 S6 ACC 2 R2 S7 R2 R2 3 R4 R4 R4 R4 4 S4 S5 8 2 3 5 R6 R6 R6 R6 6 S4 S5 9 3 7 S4 S5 10 8 S6 S11 9 R1 S7 R1 R1 10 R3 R3 R3 R3 11 R5 R5 R5 R5 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 87 (4) id*id+id的 LR分析過程 分析棧 輸入串 動作 (1) 0 (2) 0id5 (3) 0F3 (4) 0T2 (5) 0T2*7 (6) 0T2*7id5 (7) 0T2*7F10 (8) 0T2 (9) 0E1 (10) 0E1+6 (11) 0E1+6id5 (12) 0E1+6F3 (13) 0E1+6T9 (14) 0E1 id*id+id$ *id+id$ *id+id$ *id+id$ id+id$ +id$ +id$ +id$ +id$ id$ $ $ $ $ shift reduce by F?id reduce by T?F shift shift reduce by F?id reduce by T?T*F reduce by E?T shift shift reduce by F?id reduce by T?F reduce by E?E+T accept 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 88 例：已知文法 G[E] ： E→ E + n | n，請使用恰當(dāng)?shù)淖韵露戏治龇椒ㄟM(jìn)行語法分析，并判斷n+n∈ L(G)? (3)SLR(1)分析表 (2)識別文法活前綴的 DFA 解 : (1)拓廣文法 (4)分析過程 ■ 課堂練習(xí) 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 89 例：已知文法 G[S] ： S → (S)S| ε，求其 SLR(1)的分析表，并判斷 ( )( )∈ L(G)? (3)SLR(1)分析表 (2)構(gòu)造 識別文法活前綴的 DFA，并判斷用何種方法進(jìn)行分析 解 : (1)拓廣文法 (4)分析過程 注意： |ε|=0，所以用 S → ε 進(jìn)行歸約時，不用出棧，直接將 S入棧即可。 3. 若 x?Follow(B), 則用 B? ? 進(jìn)行歸約 。 ■ 引例 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 81 解 ： (1)拓廣文法 G的拓廣文法 G?[E?]： (0) E? ? E (4) T?F (1) E?E+T (5) F? (E) (2) E?T (6) F? i (3) T?T*F (2)識別文法的活前綴的 DFA (3)SLR(1)分析表 (4)分析過程 例：已知文法 G[E]， 并用 SLR(1)方法分析i*i+i∈ L(G[E]) ? E?E+T | T T?T*F | F F? (E) | i SLR(1)的分析過程與 LR(0)的分析過程完全一樣，唯一不同的是分析表！ E ’??E E ??E+T E ??T T ??T*F T ??F F ? ?(E) F ??id E E’?E? E ?E ? +T T E ?T? T ?T?*F ( F ? (? E) E ??E+T E ??T T ??T*F T ??F F ? ?(E) F ??id I0 I1 I2 I6 F T ?F? I3 F ?id? id I5 T I2 F I3 id I5 ( E ?E+ ? T T ??T*F T ??F F ? ?(E) F ??id + * T ?T* ? F F ? ?(E) F ??id I7 F ? (E ?) E ?E?+T E I8 T E ?E+ T ? T ?T?*F I9 F I3 id I5 ( F T ?T* F ? I10 id I4 ( I4 * I7 ) F ? (E) ? + I6 I11 G?： (0) E? ? E (1) E?E+T (2) E?T (3) T?T*F (4) T?F (5) F? (E) (6) F? id (2)識別文法的活前綴的 DFA 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 83 若有效項(xiàng)目集中存在沖突動作 : I = { X ? ? . b?, A? ? . , B? ? . } 將 b移進(jìn)棧 將 ?歸約為 A 將 ?歸約為 B 解決方法： 設(shè)當(dāng)前輸入符號為 x, 1. 若 x= b, 則移進(jìn) 。 解決方法：對含有沖突的項(xiàng)目集向前查看一個輸入符號，這種分析方法稱為 SLR(1)分析方法 。 ■ 右句型的可行前綴 viable prefix（活前綴） 例 x中， ε ， a, ac, acA都是右句型 acA的活前綴。 作業(yè)： P101 并用 LR(0)方法分析a01是否為該文法的句子。 方法：分別置放 s0(初態(tài) )到棧中和 w$（ w為輸入串， $為界符）到輸入緩沖器中 。 S ? aA | bB A ? cA | d B ? cB | d S? B?.cB B?.d 解 : (1)識別文法活前綴的 DFA A?d. A? A?.cA A?.d S? A?.cA A?.d B? B?.cB B?.d S??.S S?.aA S?.bB start S??S. A?cA. S?aA. A d d A c a b S S?bB. B?cB. B?d. B d d B c c c 0 1 2 3 4 5 6 7 8 9 10 11 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 76 狀態(tài) action goto a b c d $ S A B 0 1 2 3 4 5 6 7 8 9 10 11 s2 s3 acc s5 s6 s8 s9 r1 r1 r1 r1 r1 s5 s6 r4 r4 r4 r4 r4 r2 r2 r2 r2 r2 s8 s9 r6 r6 r6 r6 r6 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 1 4 7 10 11 (2)LR(0)分析表 (1)識別文法活前綴的 DFA A?d. A? A?.cA A?.d S? A?.cA A?.d S? B?.cB B?.d B? B?.cB B?.d S??.S S?.aA S?.bB start S??S. A?cA. S?aA. A d d A c a b S S?bB. B?cB. B?d. B d d B c c c 0 1 2 3 6 7 8 9 10 11 4 5 0 S??S 1 S?aA 2 S?bB 3 A?cA 4 A?d 5 B?cB 6 B?d 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 77 輸入：一個輸入串 w和文法 G的一張 LR分析表 M。 （ 5）分析表凡不能用規(guī)則 (1)(4)填入的空白格均置為“ error”。表示整個句子已輸入并歸約結(jié)束 )，則置 ACTION[k,$]為 “ acc”，表示接受。)S S 3 4 5 根據(jù)下圖某文法識別活前綴的 DFA判斷該文法是否為 LR(0)文法 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 74 ■ LR(0)分析表的構(gòu)造 LR(0)分析表包含兩個子表： ACTION表 和 GOTO表 假定 項(xiàng)目集規(guī)范族 C={I0,I1,… ,In}，令每個項(xiàng)目集 Ik的下標(biāo) k作為分析器的狀態(tài)，兩個子表的構(gòu)造過程如下： （ 1）若項(xiàng)目 A?? . a? 屬于 Ik且 GO(Ik,a)=Ij， a為終結(jié)符，則置 ACTION[k,a]為 ” sj”； （ 2）若項(xiàng)目 A?? . 屬于 Ik，則對任何終結(jié)符 a（包括終結(jié)符 $），置 ACTION[k,a]為 ” rj”（注： j是產(chǎn)生式 A??的編號，而不是狀態(tài)集的狀態(tài)號）； （ 3）若項(xiàng)目 S’→S S→(S)S S39。S S→(S)S S→ S→(S S→n 3 4 根據(jù)右圖某文法識別活前綴的 DFA判斷該文法是否為LR(0)文法 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 73 S39。 +n E→E+n→En E→n E E→ E39。)S S 3 4 5 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 72 ■ LR(0)分析表的構(gòu)造 若對于一個文法 G的拓廣文法 G’的 LR(0)項(xiàng)目集規(guī)范族中的每個項(xiàng)目集，不存在移進(jìn)項(xiàng)目和歸約項(xiàng)目同時并存或多個歸約項(xiàng)目同時并存，則稱 G為 LR(0)文法。 S→(S)S S39。S S→(S)S S→ S→(S S→ S39。n 3 4 ■ 構(gòu)造識別文法所有規(guī)范句型活前綴 DFA的方法 （ 1）求 closure({S’?.S})，得到初態(tài)項(xiàng)目集； （ 2）對初態(tài)項(xiàng)目集或其他已構(gòu)造的項(xiàng)目集，應(yīng)用狀態(tài)轉(zhuǎn)移函數(shù) GO(I,X)求出新的項(xiàng)目集； （ 3）重復(fù)（ 2）直到不出現(xiàn)新的項(xiàng)目集為止； （ 4）轉(zhuǎn)移函數(shù) GO建立狀態(tài)之間的連接關(guān)系。 +n E→E+n→En E→n E E→ DFA E39。 E→ + n E→E + E→ ■ 構(gòu)造識別文法所有規(guī)范句型活前綴 DFA的方法 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 70 E’→ go(I, X) = closure(J) 其中 J ={A??X . ? | A?? . X??I } 稱函數(shù) go(I, X)為轉(zhuǎn)移函數(shù)。 (3) closure(I)僅包含上述兩條規(guī)則確定的 LR(0)項(xiàng)目。 （設(shè) S為文法 G的開始符號） 第 4章 語法分析 2022/8/21 信息學(xué)院 孫麗云 69 設(shè) I是文法 G的一個 LR(0)項(xiàng)目集合， I的項(xiàng)目閉包 closure(I)定義為： (1) I ? closure(I)。 為了使“接受”項(xiàng)目唯一，對文法 G進(jìn)行拓廣。 解 ：