【正文】 G的開始符號(hào)） 第 4章 語(yǔ)法分析 2022/8/21 信息學(xué)院 孫麗云 69 設(shè) I是文法 G的一個(gè) LR(0)項(xiàng)目集合， I的項(xiàng)目閉包 closure(I)定義為： (1) I ? closure(I)。 E→E E→n 3 4 ■ 構(gòu)造識(shí)別文法所有規(guī)范句型活前綴 DFA的方法 （ 1）求 closure({S’?.S})，得到初態(tài)項(xiàng)目集； （ 2）對(duì)初態(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)系。(S)S S→ )S S 3 4 5 第 4章 語(yǔ)法分析 2022/8/21 信息學(xué)院 孫麗云 72 ■ LR(0)分析表的構(gòu)造 若對(duì)于一個(gè)文法 G的拓廣文法 G’的 LR(0)項(xiàng)目集規(guī)范族中的每個(gè)項(xiàng)目集，不存在移進(jìn)項(xiàng)目和歸約項(xiàng)目同時(shí)并存或多個(gè)歸約項(xiàng)目同時(shí)并存，則稱 G為 LR(0)文法?！鶨 S→( S→(S)S S ? aA | bB A ? cA | d B ? cB | d S? B?.cB B?.d 解 : (1)識(shí)別文法活前綴的 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章 語(yǔ)法分析 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)識(shí)別文法活前綴的 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章 語(yǔ)法分析 2022/8/21 信息學(xué)院 孫麗云 77 輸入：一個(gè)輸入串 w和文法 G的一張 LR分析表 M。 解決方法：對(duì)含有沖突的項(xiàng)目集向前查看一個(gè)輸入符號(hào)，這種分析方法稱為 SLR(1)分析方法 。 在 SLR。 ■ 引例 第 4章 語(yǔ)法分析 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)識(shí)別文法的活前綴的 DFA (3)SLR(1)分析表 (4)分析過(guò)程 例：已知文法 G[E]， 并用 SLR(1)方法分析i*i+i∈ L(G[E]) ? E?E+T | T T?T*F | F F? (E) | i SLR(1)的分析過(guò)程與 LR(0)的分析過(guò)程完全一樣，唯一不同的是分析表！ 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)識(shí)別文法的活前綴的 DFA 第 4章 語(yǔ)法分析 2022/8/21 信息學(xué)院 孫麗云 83 若有效項(xiàng)目集中存在沖突動(dòng)作 : I = { X ? ? . b?, A? ? . , B? ? . } 將 b移進(jìn)棧 將 ?歸約為 A 將 ?歸約為 B 解決方法： 設(shè)當(dāng)前輸入符號(hào)為 x, 1. 若 x= b, 則移進(jìn) 。 方法：分別置放 s0(初態(tài) )到棧中和 w$（ w為輸入串， $為界符）到輸入緩沖器中 。)S S 3 4 5 根據(jù)下圖某文法識(shí)別活前綴的 DFA判斷該文法是否為 LR(0)文法 第 4章 語(yǔ)法分析 2022/8/21 信息學(xué)院 孫麗云 74 ■ LR(0)分析表的構(gòu)造 LR(0)分析表包含兩個(gè)子表： ACTION表 和 GOTO表 假定 項(xiàng)目集規(guī)范族 C={I0,I1,… ,In}，令每個(gè)項(xiàng)目集 Ik的下標(biāo) k作為分析器的狀態(tài)，兩個(gè)子表的構(gòu)造過(guò)程如下： （ 1）若項(xiàng)目 A?? . a? 屬于 Ik且 GO(Ik,a)=Ij， a為終結(jié)符，則置 ACTION[k,a]為 ” sj”； （ 2）若項(xiàng)目 A?? . 屬于 Ik，則對(duì)任何終結(jié)符 a（包括終結(jié)符 $），置 ACTION[k,a]為 ” rj”（注： j是產(chǎn)生式 A??的編號(hào)，而不是狀態(tài)集的狀態(tài)號(hào)）； （ 3）若項(xiàng)目 S’→S(S)S S→ +n E→E+n E39。S S→ S39。n E→n + n E→E + (3) closure(I)僅包含上述兩條規(guī)則確定的 LR(0)項(xiàng)目。 E→ S → → 優(yōu)點(diǎn)：對(duì)文法的限制少的多，分析速度快； 缺點(diǎn)：構(gòu)造 LR分析器的工作量大，實(shí)現(xiàn)困難。 識(shí)別串 w=cabd是否是該文法的句子。*是該文法的句型。（ ） 一個(gè)確定的有窮自動(dòng)機(jī) DFA是一個(gè)三元組 （ VN,VT,P）。 （ ） 對(duì)編譯程序而言，可以沒有代碼優(yōu)化的部分。 根據(jù)分析表進(jìn)行自頂向下的語(yǔ)法分析。s s。 第 4章 語(yǔ)法分析 2022/8/21 信息學(xué)院 孫麗云 41 ● 練習(xí) 1 Follow(exp)={$,) } Follow(exp’)={$,)} Follow(addop)={(,number} Follow(term)={ $,+,,)} Follow(term’)={$,+,,)} Follow(mulop)={(,number} Follow(factor)={ $,+,, *,)} (1)First集和 Follow集 First(exp)={(,number} First(exp’)={+,, ε} First(addop)={+,} First(term)={(,number} First(term’)={*, ε} First(mulop)={*} First(factor)={(,number} 文法： exp → exp addop term∣ term addop → + | term → term mulop factor∣ factor mulop →* factor →( exp) ∣ number 注意：先消除左遞歸 第 4章 語(yǔ)法分析 2022/8/21 信息學(xué)院 孫麗云 42 Follow(exp)={$,) } Follow(exp’)={$,)} Follow(addop)={(,number) Follow(term)={ $,+,,)} Follow(term’)={$,+,,)} Follow(mulop)={(,number) Follow(factor)={ $,+,, *,)} (2)First集和 Follow集 First(exp)={(,number) First(exp’)={+,, ε} First(addop)={+,} First(term)={(,number) First(term’)={*, ε} First(mulop)={*} First(factor)={(,number) 11 10 9 7 8 8 8 8 6 6 5 4 2 2 3 3 1 1 factor mulop term’ term addop exp’ exp $ * + ) Number ( M[N,T] (3)LL(1)分析表 解 (1) 文法 1 exp → term exp’ 2 exp’→ addop term exp’ 3 exp’→ ε 4 addop → + 5 addop → 6 term → factor term’ 7 term’ → mulop factor term’ 8 term’ → ε 9 mulop → * 10 factor → (exp) 11 factor → number （ 1）對(duì)于 First(α)中的每個(gè)記號(hào) a，都將 A → α添加到表項(xiàng) M[A, a]中； （ 2）若 ε在 First(α)中，則對(duì)于 Follow(A)的每個(gè)元素 a(記號(hào)或是 $)，都將 A → α添加到 M[A, a]中。 識(shí)別過(guò)程： P64P65 自學(xué) 通常若采用遞歸下降分析法，則文法采用 EBNF表示法。 消除左遞歸與回溯，還可以用 EBNF表示法： ?使用花括號(hào) {a}表示符號(hào)串 a的出現(xiàn)可 0次或多次，即表示 a*。 某些非 LL(1)文法到 LL(1)文法的改寫： （ 1）消除左遞歸； （ 2）提取左因子。 stmt sequence | stmt stmt→s 提取左因子的結(jié)果： stmtsequence→stmt stmt seq’ stmtseq’→。 stmtsequence|ε stmt→s First(stmtsequence)={s} First(stmtseq’)={。特別是 ,若所有的 FIRST(Yj , j=1,2,…,K) 均含有 ?,則把 ?加到FRIST(X)中 . ■ First集合算法 P67 令 X為一個(gè)文法符號(hào)或 ?，則集合 First(X)由終結(jié)符組成，此外還可能有 ?，定義如下： ■ 求 First集合綜合舉例 求下列各種情況下