詞法分析程序的設計原則,單詞的描述技術,識別機制及詞法(存儲版)
【正文】 d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = ?closure(move({S1, S2,... Sj},a)) 4 S0=?closure(K0)為 M的開始狀態(tài)； 5 St={[Si Sk... Se]，其中 [Si Sk... Se]?S且 {Si , Sk,... Se}?Kt??} 定義對狀態(tài)集合 I的幾個有關運算： 1. 狀態(tài)集合 I的 ε 閉包 ， 表示為 εclosure(I)， 定義為一狀態(tài)集，是狀態(tài)集 I中的任何狀態(tài) S經(jīng)任意條 ε弧而能到達的狀態(tài)的集合。 DFA的最小化就是尋求最小狀態(tài) DFA 最小狀態(tài) DFA的含義 : 沒有多余狀態(tài) (死狀態(tài) ) 沒有兩個狀態(tài)是互相等價（不可區(qū)別） 兩個狀態(tài) s和 t可區(qū)別：不滿足 兼容性 ——同是終態(tài)或同是非終態(tài) 傳播性 ——從 s出發(fā)讀入某個 a?a???和從 t出發(fā) 讀入某個 a到達的狀態(tài)等價。 (3） R=a,構造 的 NFA M=({k0,k1},∑,f,k 0.{k1}): f(k0,a) = k1 (4) R =R1 | R2, 將步驟（ 1）（ 2）（ 3）分別應用到 R1,R2 產(chǎn)生 M1= =(K1,∑,f1,k1,F1) , M2=(K2,∑,f2,k2,F2), 其中 K1,K2不相交 .構造 的NFA M= (K1?K2?{k},∑,f,k,F) : k是新增加的狀態(tài)符號， f包含 f1和 f2,且 f(k,a)=f1(k1,a)?f2(k2,a). 若 k1?F1且 k2?F2則 F=F1 ? F2， 否則 F=F1 ? F2 ?{k} (5)R= 將步驟（ 1）（ 2）（ 3）分別應用到 R1,R2 產(chǎn)生M1==(K1,∑,f1,k1,F1) , M2=(K2,∑,f2,k2,F2), 其中 K1,K2不相交 .構造 的 NFA M= (K1?K2,∑,f,k 1,F2) : f包含 f1和 f2,且 f(k,a)=f1(k,a),當 k?F1時 。 本章講述了詞法分析程序設計原則，并介紹了分別作為正規(guī)集描述和識別機制的正規(guī)式和有窮動機。 詞法分析程序的自動構造工具也廣泛應用于許多方面，如用以生成一個程序，可識別印刷電路板中的缺陷，又如開關線路設計和文本編輯的自動生成等。 從 Σ上的一個正規(guī)式 R構造 Σ上的一個 NFA M， 使得 L(M)=L(R)的方法。一個有窮自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉換成一個最小的與之等價的有窮自動機。 有一種算法，將 NFA轉換成接受同樣語言的 子集法 . 與某一 NFA等價的 DFA不唯一 . NFA確定化算法 : 假設 NFA N=(K, ?,f,K0,Kt)按如下辦法構造一個 DFA M=(S, ?,d,S0,St)， 使得L(M)=L(N)： 1. M的狀態(tài)集 S由 K的一些子集 組成。 – c:=getchar。 有窮自動機分為兩類：確定的有窮自動機(Deterministic Finite Automata)和不確定的有 窮自動機 (Nondeterministic Finite Automata) 。 單詞是語言中具有獨立意義的最小單位，包括保留字、標識符、運算符、標點符號和常量等。 詞法分析程序和語法分析程序的關系 源程序 詞法分析程序 語法分析程序 Token get token …. 源程序 詞法分析程序 語法分析程序源程序 詞法分析程序 語法分析程序 源程序 詞法分析程序的 主要任務： – 讀源程序，產(chǎn)生單詞符號 詞法分析程序的 其他任務： – 濾掉空格，跳過注釋、換行符 – 追蹤換行標志，復制出錯源程序， – 宏展開， …… 詞法分析工作從語法分析工作獨立出來的原因： – 簡化設計 – 改進編譯效率 – 增加編譯系統(tǒng)的可移植性 ? 單詞的描述工具 正規(guī)表達式 ? 單詞的識別系統(tǒng) 有窮自動機 ? 設計詞法分析程序 ,實現(xiàn)詞法分析程序的自動構造 令 ?={a， b}， ?上的正規(guī)式和相應的正規(guī)集的例子 a a?b ab (a?b)(a?b) a ? (a?b)? (a?b)?(aa?bb)(a?b)
教學課件相關推薦
鄂ICP備17016276號-1