【正文】 ” 改為“ ...是從狀態(tài) si經(jīng) ch(或 ε )到達(dá)的下一狀態(tài) sj。 每個終結(jié)符 a A→ α . 狀態(tài) i： B→ β . x 習(xí)題 設(shè)整型數(shù)組聲明的形式為 int A[d1,d2,…,d3]， 并且假設(shè)每個整型 數(shù)占據(jù) 4個字節(jié) 。 end loop。 對于正規(guī)語言 ， 可用正規(guī)式表示 。 p(a+b, a, a)。 → E . E → E . + T E → T . T → T . * F T → F . F → ( . E ) E → . E + T E → . T T → . T * F T → . F F → . ( E ) F → . F F → . i d F → . F F → . ( E ) F → . F F → . i d F → i d .I 1I 0I 2I 3I 4I 5I 6ETF(i d E → E + . T T → . T * F T → . F F → . ( E ) F → . F F → . i d+ T → T * . F F → . ( E ) F → . F F → . i d F → ( E . ) E → E . + T F → F .( E → E + T . T → T . * FE*T(i dFI 7I 8I 9I 1 0 T → T * F . F → ( E ) .I 1 1I 1 2I 1 3*F(Ti dI 5I 6Fi d+)F(I 6I 5i d 沖突的項(xiàng)目集 :I2， I11 計(jì)算 FOLLOW(E)， 看 *是否在其中 （ 略 ） 構(gòu)造 SLR（ 1） 分析表的方法： 1． 可移進(jìn)項(xiàng)直接從 DFA上看： action[I,a]:=sj goto[I,A]:=k 2． 可歸約項(xiàng)分兩步走：若在 I狀態(tài)中有 [A→α .]， 首先計(jì)算： FOLLOW(A), 然后填寫： action[I,b]:=Ri 其中： b∈FOLLOW(A) 且 A→α 是第 i個產(chǎn)生式 。其中 …代表不含 */的字符串 思路： 注釋中若遇到 *：若后邊是 /則結(jié)束注釋否則仍然是注釋 步驟： 1. 注釋串是空； 2. 考慮沒有 *的注釋； 3. 考慮含 *的注釋 結(jié)果： (4) /* ([^*]|*[^/])* */ （ 2） 所有不含子串 011的 01串： 1*(01|0)* （ 3） 每個 a后面至少緊隨兩個 b的 ab串： (b|abb)* 習(xí)題 有一 NFA的狀態(tài)轉(zhuǎn)換矩陣下表，其中 S為初態(tài)， D為終態(tài) a b c ε S A,B C,D D A,B,C A A C B B A D C C B A A D C B S 1. 求出它的最小 DFA 2. 用正規(guī)式描述 DFA所接受的語言 問題： 根據(jù) DFA寫出對應(yīng)的正規(guī)式 ， 通常的考慮和步驟是什么 ？ 再重復(fù)一遍： 正規(guī)式 、 DFA是從兩個不同的側(cè)面表示一個集合 (即正規(guī)集 )。 emit(+,。 (b)（ 3分 ） 寫出與該自動機(jī)等價的正規(guī)式 r。 也可以用歸納法證明（提示：以 ab重復(fù) 0次、 1次作為歸納基礎(chǔ)，假設(shè) ab重復(fù) n次成立，證明 ab重復(fù) n+1次也成立）。 ? 自己要會辨別什么是主要的什么是次要的，抓什么丟什么。 14 4 自下而上分析 1. 分析方法： 歸約 (推導(dǎo)的逆過程 )，從葉子到根構(gòu)造分析樹； 2. 基本概念： 短語、直接短語、句柄、歸約、規(guī)范歸約； 3. 采用的方法 : 用移進(jìn) 歸約方法實(shí)現(xiàn)剪句柄（格局中的兩個關(guān)鍵動作），關(guān)鍵問題是如何確定棧頂已經(jīng)形成句柄，當(dāng)句柄形成時，如何判定采用哪個產(chǎn)生式進(jìn)行規(guī)約； 4. 識別活前綴的 DFA： 活前綴與 LR(0)項(xiàng)目 (NFA狀態(tài) )，拓廣文法與子集法構(gòu)造 DFA； T → . T * F. . .αT → T . * FTT → T * . F*T → T * F .F? 一個產(chǎn)生式是一個識別活前綴的 NFA ? 一個 LR(0)項(xiàng)目是 NFA的一個狀態(tài) 15 4 自下而上分析（續(xù)） 5. DFA分析輸入序列： 有效項(xiàng)目、可移進(jìn)項(xiàng)目、可規(guī)約項(xiàng)目、移進(jìn) /歸約沖突、歸約 /歸約沖突；解決沖突的方法－SLR(1)：簡單向前看一個終結(jié)符（計(jì)算歸約項(xiàng)非終結(jié)符的FOLLOW，與可移進(jìn)終結(jié)符比較）； 6. 移進(jìn) 歸約分析表： 動作表＋轉(zhuǎn)移表； 7. LR文法與 LR分析： LR(0)、 SLR(1)、 LALR(1)、 LR(1)。 4 從正規(guī)式到詞法分析器 ? 構(gòu)造 NFA的 Thompson算法 (與 NFA定義的對應(yīng)關(guān)系 )； ? 模擬 NFA的 “ 并行 ” 算法； ? 從 NFA構(gòu)造 DFA－子集法： smove(S, a)與 ε 閉包 (T)的計(jì)算； ? DFA的最小化－可區(qū)分的概念：所有不可區(qū)分的狀態(tài)看作是一個狀態(tài)； ? 靈活運(yùn)用各種方法構(gòu)造 DFA(正規(guī)式化簡、狀態(tài)轉(zhuǎn)換圖等 )，特別是手工構(gòu)造和算法構(gòu)造的區(qū)別。 3 第一章 引言 1 語言的翻譯 不同的翻譯形式： 匯編 、 編譯 、 轉(zhuǎn)換 （ 預(yù)編譯 ） 、 逆向翻譯 翻譯方法： 編 譯 器目 標(biāo) 程 序源 程 序 目 標(biāo) 程 序輸 入 數(shù) 據(jù)輸 出解 釋 器源 程 序輸 入 數(shù) 據(jù)輸 出4 2 編譯器的基本組成 詞 法 分 析語 法 分 析語 義 分 析中 間 代 碼 生 成代 碼 優(yōu) 化目 標(biāo) 代 碼 生 成源 程 序目 標(biāo) 代 碼符號表管理出錯處理5 3 編譯器的分析－綜合模式 4 編譯器的掃描遍數(shù)與編譯器的編寫 編 譯 器分 析 （ 前 端 ） 綜 合 （ 后 端 ）語 法 / 語 義 分 析 代 碼 生 成 / 優(yōu) 化源 程 序 中 間 代 碼 目 標(biāo) 代 碼6 第二章 詞法分析 構(gòu)詞規(guī)則與詞法分析： 首先規(guī)定單詞形成的規(guī)則，稱為 構(gòu)詞規(guī)則 ；然后根據(jù)