正規(guī)式轉換和最小DFA畢業(yè)設計

本文共計34頁，8336字；

正規(guī)式轉換和最小DFA
摘 要
編譯程序的工作過程通常是詞法分析、語法分析、語義分析、代碼生成、代碼優(yōu)化。編譯程序的這些過程的執(zhí)行先后就構成了編譯程序的邏輯結構，但是這些邏輯結構不一定是按照某一個固定順序的，也有可能是按照平行或者互鎖的方式執(zhí)行的。
本文主要介紹基于編譯器構造技術中的由正規(guī)表達式到最小化DFA的算法設計和實現(xiàn)技術；把NFA轉化為與其等價的DFA所使用的子集構造算法最后實現(xiàn)詞法分析。NFA轉化為與其等價的DFA需分兩步進行：a、構造NFA N的狀態(tài)K的子集的算法；b、計算e-closure。c、用分割法對DFA實現(xiàn)最小化。完成這些子模塊的設計后，再通過某一中間模塊的總控程序對其調用，最后再由主程序合并調用。在算法實現(xiàn)過程中，主要使用visual C++進行編程，并且用到了STL（標準模板庫）技術來對邊集、狀態(tài)集進行定義和處理。正規(guī)表達式與自動機理論在詞法構造乃至整個編譯器構造過程中起著至關重要的作用，同時它們被廣泛應用于計算機科學的各個領域，它們與計算機其它學科之間也有著很大的聯(lián)系。

關鍵詞：正則表達式，NFA，DFA，Thompson構造法，子集構造算法， 分割法

目 錄

摘要 ………………………………………………………………………………1
第1章 緒論 ………………………………………………………………………
1.1 實驗環(huán)境與開發(fā)工具 ……………………………………………………5
1.2 有窮動機簡介 ……………………………………………………………6
1.3 基本概念 ……………………………………………………………………6
1.4 NFA向DFA轉換 ……………………………………………………………6
1.5 DFA 的矩陣表示 ……………………………………………………………7
1.6正規(guī)式、正規(guī)表達式、有限自動機之間的關系…………………………….7
第2章 設計任務的組織和分工 …………………………………………………
2.1小組任務分工…………………………………………………………………
2.2 本人主要任務…………………………………………………………………
第3章 需求分析
3.1 總體功能需求 …………………………………………………………………9
3.2 系統(tǒng)主要功能…………………………………………………………………10
3.3 數據流圖………………………………………………………………………11
3.4 數據字典………………………………………………………………………
3.5 數據項………………………………………………………………………
3.6 數據結構………………………………………………………………………
第4章 詳細設計
4.1功能模塊設計………………………………………………………………………13
4.2 算法設計………………………………………………………………………13
4.2.1 將正則表達式轉換為有限自動機………………………………………
4.2.2 實現(xiàn)從NFA構造DFA的算法---子集構造法…………………………………
4.2.3 確定有限自動機的化簡…………………………………………………………
4.3 主函數說明………………………………………………………………………
4.4 流程圖………………………………………………………………………
4.4.1 用Thompson構造法構造NFA……………………………………………
4.4.2 用子集構造法構造DFA…………………………………………………
4.4.3 DFA化簡………………………………………………………………………
第5章 界面設計……………………………………………………………………16
5.1界面用途………………………………………………………………………
5.2界面的建設………………………………………………………………………
5.3界面的優(yōu)點與不足…………………………………………………………………
第六章結論
參考文獻 ……………………………………………………………………………19
總結 …………………………………………………………………………………20
附錄
源程序 ……………………………………………………………………………21
參考資料

1、軟件工程導論（第三版） 清華大學出版社 張海潘著
2、編譯原理（第二版） 西北工業(yè)大學出版社 蔣立源等著（方法全）
3、程序設計語言編譯原理 國防工業(yè)大學出版社 陳火旺著（原理強）
4、編譯程序設計 北京大學出版社 王永寧著（實現(xiàn)佳）
5、Visual C++6.0開發(fā)使用手冊 機械工業(yè)出版社 Brian Siler等著
6、編譯原理（第2版）清華大學出版社 張素琴 呂映之 等著