詞法分析核心算法(1)正規(guī)式》NFA

1、正規(guī)式轉換為不確定的有窮自動機的算法.目的與要求：通過設計、編寫和調試將正規(guī)式轉換為不確定的有窮自動機的程序， 掌握轉換過程中的相關概念和方法，NFA的表現(xiàn)形式可以是圖標或 者圖形。.問題描述：任意給定一個正規(guī)式r （包括鏈接、或、閉包運算），根據(jù)如下算法， 設計一個程序，生成與該正規(guī)式等價的NFAN.算法：首先，分析給定的正規(guī)式r,將其分解成最基本的子表達式，使用下 面的規(guī)那么（1）和規(guī)那么（2）為r中的每個基本符號（8或字母表中的 符號）構造NFA。如果符號a在r中出現(xiàn)屢次，那么要為它的每次出現(xiàn) 構造一個NFA。然后，使用規(guī)那么（3）逐步地組合前面構造的NFA,直到獲得整個正 規(guī)式的NFA

2、為止?；疽?guī)那么如下：（1）對于,構造如下列圖所示的NFA,它識別儲;(2)對于匯中的每個符號a,構造如下列圖所示的NFA,它識別a； a (3)如果N(s)和N(t)分別是正規(guī)式s和t的NFA,那么：1對正規(guī)式s It,構造合成的NFAN(s I t),結果如下列圖所示：加入x和y節(jié)點，從x弓|弧到N(s)和N(t)的開始狀態(tài)，從N(s)和 N(t)的接受狀態(tài)引8弧到y(tǒng)節(jié)點;2對正規(guī)式st,構造合成的NFAN(st),結果如下列圖所示：CD Ms) 1 0 N(t)(Q)N(s)的開始狀態(tài)成為合成后的NFA的開始狀態(tài)，N(t)的接受狀態(tài) 成為合成后的NFA的接受狀態(tài)，N(s)的接受狀態(tài)和N(

3、t)的開始狀 態(tài)合并；3對于正規(guī)式s*,構造合成的NFAN(s*),如下列圖所示：4對于括號括起來的正規(guī)式，使用N(s)本身作為他的NFA.基本要求：(1)輸入一個正規(guī)式r;(2)輸出與正規(guī)式r等價的NFA(可以是表格形式或圖形形式)。測試數(shù)據(jù)：輸入正規(guī)式:r=(a I b)*(aa I bb)(a I b)*.實現(xiàn)提示：NFA的表示可以是圖形或者表格形式，狀態(tài)之間的變換也可以 直接表示為每兩個狀態(tài)一組，表示為“起始狀態(tài) 輸入字符 到達狀態(tài)”，如“a”表示在狀態(tài)下讀入輸入字符a, 變換到狀態(tài)。(2)實現(xiàn)時的數(shù)據(jù)結構的定義：1用字符串存儲正規(guī)式；2用結構體鏈表存放狀態(tài)轉換圖struct NFA int from;int to;char varch; 表而正態(tài)fh)m到達狀,態(tài)to,經(jīng)過多符varch3中間過程使用堆棧結合正規(guī)式算符優(yōu)先關系表來完成正規(guī)式的優(yōu)先關系表：a*1()#aerrerr*1(err#err將#壓入堆棧，并從左到右掃描輸入符號串，遇到下一個優(yōu)先性低 的運算符那么出棧并構造NFA;遇到下一個優(yōu)先性高的運算符那么入 棧。為了方便處理，將*運算符改為前綴，如：r=(a I b)*(aa I bb)(a I b)*=r=* (a I b) (aea I beb) *(a I b)注意：處理過程中，當前運算符作用域的處理。如：* (a I