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

本文共計34頁，8336字；

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

關(guān)鍵詞：正則表達式，NFA，DFA，Thompson構(gòu)造法，子集構(gòu)造算法， 分割法

目 錄

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

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