【正文】 動機和正規(guī)表達式進行了上述討論之后 ,我們介紹 詞法分析程序 的 自動 構(gòu)造方法 ,這個方法基于有窮自動機和正規(guī)表達式的等價性 ,即 ： ∑ 上的一個 NFA M，可以構(gòu)造一個 ∑ 上的正規(guī)式 R,使得 L(R)=L(M)。 ∑ 上的一個正規(guī)式 R，可以構(gòu)造一個 ∑ 上的 NFA M， 使 的 L(M)=L(R)。 從 Σ上的一個正規(guī)式 R構(gòu)造 Σ上的一個 NFA M， 使得 L(M)=L(R)的方法。 “ 語法制導(dǎo) ” 的方法，即按正規(guī)式的語法結(jié)構(gòu)指引構(gòu)造過程，構(gòu)造規(guī)則具體描述如下： .“ 對于 ∑ 上的 一個正規(guī)式 R,可以構(gòu)造一個 ∑ 上的 NFA M， ，使得 L(M)=L(R).” 說明一種構(gòu)造方法： (1)R=?,構(gòu)造 任一具有空終態(tài)集的 NFA M (2） R= ? ， 構(gòu)造 的 NFA M=({k0}, ∑,f,k 0.{k0}): f（ k0,a)對于 所有 a?∑ 都沒定義。 (3） R=a,構(gòu)造 的 NFA M=({k0,k1},∑,f,k 0.{k1}): f(k0,a) = k1 (4) R =R1 | R2, 將步驟（ 1）（ 2）（ 3）分別應(yīng)用到 R1,R2 產(chǎn)生 M1= =(K1,∑,f1,k1,F1) , M2=(K2,∑,f2,k2,F2), 其中 K1,K2不相交 .構(gòu)造 的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）分別應(yīng)用到 R1,R2 產(chǎn)生M1==(K1,∑,f1,k1,F1) , M2=(K2,∑,f2,k2,F2), 其中 K1,K2不相交 .構(gòu)造 的 NFA M= (K1?K2,∑,f,k 1,F2) : f包含 f1和 f2,且 f(k,a)=f1(k,a),當(dāng) k?F1時 。 f(k,a)=f2(k,a),當(dāng) k∈ K2時 。 f(k1, ?)=k2, (6)R=R1* 將步驟（ 1）（ 2）（ 3）分別應(yīng)用到 R1,產(chǎn)生 M1==(K1,∑,f1,k1,F1) , 構(gòu)造 的 NFA M= (K1? {k0,F0} ,∑,f,k 0,F0)其中 k0,F0 是新增加的兩個狀態(tài) , f(k,a)=f1(k,a),當(dāng) k?F1時 。 f(k0, ?)=f(F1 , ?)= {k1,F0} , , 再用狀態(tài)圖說明可用方法 對于正規(guī)式 x,x ?∑ 構(gòu)造的 NFA（ 兩種） X 對于正規(guī)式 ? ,構(gòu)造的 NFA（ 三種） F S ? F 對于正規(guī)式 R=? ,構(gòu)造的 NFA F S 對于正規(guī)式 r, r= R1|R2構(gòu)造的 NFA 對于正規(guī)式 r, r=R1 R2構(gòu)造的 NFA 對于正規(guī)式 r, r=R1*構(gòu)造的 NFA R=(a|ab)* b b* 正規(guī)式用于說明 (描述 )單詞的結(jié)構(gòu)十分簡潔方便。而把一個正規(guī)式編譯 (或稱轉(zhuǎn)換 )為一個 NFA進而轉(zhuǎn)換為相應(yīng)的 DFA， 這個NFA或 DFA正是識別該正規(guī)式所表示的語言的句子的識別器?；谶@種方法來構(gòu)造詞法分析程序 詞法分析程序的設(shè)計技術(shù)可應(yīng)用于其它領(lǐng)域，比如查詢語言以及信息檢索系統(tǒng)等，這種應(yīng)用領(lǐng)域的程序設(shè)計特點是，通過字符串模式的匹配來引發(fā)動作，回想LEX， 說明詞法分析程序的語言，可以看成是一個模式動作語言。 詞法分析程序的自動構(gòu)造工具也廣泛應(yīng)用于許多方面，如用以生成一個程序，可識別印刷電路板中的缺陷，又如開關(guān)線路設(shè)計和文本編輯的自動生成等。 習(xí)題 練習(xí) 1 （ 1） 3 4 (b) 5 本章小結(jié) 詞法分析程序是編譯第一階段的工作，它讀入字符流的源程序，按照詞法規(guī)則識別單詞，交由語法分析程序接下去。 本章講述了詞法分析程序設(shè)計原則，并介紹了分別作為正規(guī)集的描述機制和識別機制的正規(guī)式和有窮動機。在此基礎(chǔ)上給出了詞法分析程序自動構(gòu)造工具如 LEX的原理。 識別 Pl0單詞的 FA NFA的確定化 More example DFA的最小化算法 —英 文描述 1. Construct an initial partition∏ of the set of states with two groups:the accepting states F and the nonaccepting states SF. 2. Apply the procedure PP.(Construction of ∏ new) to ∏ to construct a new partition ∏ new. 3. If ∏ new =∏,let ∏ final=∏ and continue with step (4). Otherwise,repeat step(2) with ∏:= ∏ new. 4 . Choose one state in each group of the partition ∏ final as the representative for the representatives will be the states of the reduced DFA M‘.let s be a representative state, and suppose on input a there is a transition from s to t .Let r be the representative of t‘s group(r may be t).Then M‘ has a transition from s to r on the start state of M‘ be the representative of the group containing the start state s0 of let the accepting states of M‘ be the representative that are in that each group of ∏ final either consists only of states in F or has no states in F. 5 . If M‘ has a dead state, that is, a states d that is not accepting and that has transitions to itself on all input symbols, then remove d from M‘,Also remove any states not reachable from the start state. Any transitions to d from other states bee undefined.