編譯原理復(fù)習(xí)(參考版)
2025-08-08 19:49本頁面
【正文】 S?bed., d (1)求項目集和 DFA: 狀態(tài) Action Goto a b c d e S A 0 S2 S3 1 1 acc 2 S5 4 3 S7 6 4 S8 5 S9 r5 6 S10 7 r5 S11 8 r1 9 r3 10 r2 11 r4 (0)S39。?.S, S?.aAd, S?.bAc, S?.aec, S?.bed, S1: S39。 (0)S39。 S?bed., d First(?)={} First(d)=nhcuj7d3 First(c)={c} (0)S39。?.S, S?.aAd, S?.bAc, S?.aec, S?.bed, S1: S39。 此外注意：每一個 LR(1)項目與其后繼項目 有相同的向前搜索符 ，如：若有 LR(1)項目為： [A?α?x?,a]，則 其后繼為：[A?αx??,a] (2)轉(zhuǎn)換函數(shù)： GO(Si,x)=CLOSURE(Sj) 在 LR(1)項目集的構(gòu)造過程中，仍以 [S‘?.S,]為初態(tài)集的基本部分 (初始項目 ),然后對其求閉包 ,使其增大 ,再求轉(zhuǎn)換函數(shù)得 其它項目集的基本部分 Sj,再求 Sj的閉包 ,直到項目集不在增大。?.S,]出發(fā)，通過求其閉包再用轉(zhuǎn)換函數(shù)逐步求出整個文法的 LR(1)項目集。?.S,] ?S0 , 它表示：若文法 G[S]中有 S’?S產(chǎn)生式，而且要將 S歸約為 S’時，必須面臨輸入符號 ‘ ’才行。 (1)項目： (1) LR(1)項目的構(gòu)成： 在 LR(0)項目中放置一個向前搜索的符號 a，成為： [A?α.?,a] (2) LR(1)項目集的構(gòu)造： LR(1)分析過程中的每個狀態(tài)，就是包含若干 LR(1)項目的一個 LR(1)項目集，特殊的， [S180。 (2)轉(zhuǎn)換函數(shù) 從一個狀態(tài)出發(fā)，到達下一個狀態(tài)的轉(zhuǎn)換函數(shù)定義為： GO(I,X)=CLOSURE(J) I為某個項目集對應(yīng)的狀態(tài) X為輸入符號 X ?V J= {任何形如 A??x.?的項目 | A??.x??I} 3. DFA的形成過程 (舉例說明 )： 對拓廣文法 G[S’] S’?E E?aA|bB A?cA|d B?cB|d ’?.E ’?E. ?.aA ? ?aA. ?.cA 7. A? 8. A?cA. 9. A?.d ?d. ?.bB ? ?bB. ?.cB ? ?cB. ?.d ?d. 有項目： ? S0 S’?.E肯定包含再 S0中 S’?.E 求 CLOSURE(S0) E?.aA E?.bB E S1: S’?E. S2 a E? A?.cA A?.d b S3 E? B?.cB B?.d c S4 A? A?.cA A?.d A S6: E?aA. d S10: A?d. c S5 B? B?.cB B?.d B S7: E?bB.
電大資料相關(guān)推薦
鄂ICP備17016276號-1