編譯技術(shù)課程設(shè)計(jì)--正則式到有限自動(dòng)機(jī)的轉(zhuǎn)換

1、編譯技術(shù)課程設(shè)計(jì)一正則式到有限自動(dòng)機(jī)的轉(zhuǎn)換課程設(shè)計(jì)報(bào)告（2010-2011年度第一學(xué)期）課程名稱： 編譯技術(shù)課程設(shè)計(jì)題 0：正則式到有限自動(dòng)機(jī)的轉(zhuǎn)換院 系：控制與計(jì)算機(jī)工程學(xué)院2011 年 1 月 1 口班 級(jí)：軟件0801學(xué)號(hào)：1081250115學(xué)生姓名：盛利指導(dǎo)教師：齊林海設(shè)計(jì)周數(shù)：1周成績(jī)：口期:摘要用c語(yǔ)言實(shí)現(xiàn)的從正規(guī)式到有窮自動(dòng)機(jī)的轉(zhuǎn)化，包括正規(guī)式轉(zhuǎn)化成nfa, nfa 轉(zhuǎn)化成dfa, dfa的最小化。從文件讀入正規(guī)式，nfa或dfa。如果讀入正規(guī)式，則先將其轉(zhuǎn)換為nfa,再將此nfa轉(zhuǎn)換為dfa并最小化。如果讀入nfa,則將其轉(zhuǎn)化為dfa并最小化。如果讀入dfa,則直接將其最小

2、化。通過(guò)編程實(shí)現(xiàn)正規(guī)式到有窮自動(dòng)機(jī)的轉(zhuǎn)化，讓我們對(duì)課本上的轉(zhuǎn)化過(guò)程更加 清楚，明了。關(guān)鍵字：正規(guī)式nfa dfa 有窮自動(dòng)機(jī) 轉(zhuǎn)化abstractc language from regular type to the realization of the transformation of finite automaton, including regular type into nfa, nfa into dfa, dfa minimization. from the document into normal type, nfa or dfa if read in formal type,

3、the first convert to nfa, then the nfa converted to dfa and mini mizcd if read nfa, then con ver t it to dfa and minimized. if read dfa, is directly minimize. through the programming formal type to the finite automaton transformation, 1 et us in the process of transformation of the textbook, more cl

4、early understoodkeyword: formal type, nfa, dfa, fin ite automato n transformation目錄一、課程設(shè)計(jì)的目的5二、課程設(shè)計(jì)的要求 5三、系統(tǒng)設(shè)計(jì) 51. 算法設(shè)計(jì)說(shuō)明52. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說(shuō)明6四、系統(tǒng)實(shí)現(xiàn)81. 程序流程圖82. 重要編碼實(shí)現(xiàn)說(shuō)明8五、課程設(shè)計(jì)總結(jié)及結(jié)論 13六、參考文獻(xiàn)14附錄14課程設(shè)計(jì)的目的木次課程設(shè)計(jì)的時(shí)間為1周，目的是通過(guò)實(shí)際的題目如：詞法分析、語(yǔ)法分 析、代碼優(yōu)化等，使學(xué)生了解和掌握編譯程序的工作原理，同時(shí)培養(yǎng)學(xué)生用相關(guān) 的程序設(shè)計(jì)語(yǔ)言進(jìn)行程序設(shè)計(jì)，實(shí)現(xiàn)編譯的功能，從而提高學(xué)生的綜合能力。課

5、程設(shè)計(jì)的要求自己選一正規(guī)式；將其轉(zhuǎn)換為dfa；編程實(shí)現(xiàn)此dfa；任意輸入一串符號(hào)判斷是否符合。系統(tǒng)設(shè)計(jì)算法設(shè)計(jì)說(shuō)明程序可以以文件方式讀取文法或自動(dòng)機(jī)。nfa的確定化子集法1. 先把dfa w中的/和v置為空集；2. m'的開(kāi)始狀態(tài)qo' qo,把qo置為未標(biāo)記后加入到q'中；3. 如果q'中存在未標(biāo)記的狀態(tài)ql,q2, ，qi,則對(duì)每個(gè)aes定義：l ql, q2,，qi, a pl, p2,pi當(dāng)且僅當(dāng) 5 ql, q2,，qi ,且 pl, p2,pi。如果ql,q2,，qi不在q'中,則把它置為為標(biāo)記后加入到q' 中；如果pl, p2,pi

6、中至少有一個(gè)是m的終態(tài)，則同吋把pl, p2,pi加入 到f，中；然后給q'中所有的狀態(tài)都標(biāo)記為止；4. 重復(fù)執(zhí)行(3),直到不能向q'中加入新?tīng)顟B(tài)，并且q'中所有的狀態(tài)都 有標(biāo)記為止；重新命名q'中的狀態(tài)，最后獲得等價(jià)的dfa w數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說(shuō)明const int op 0;/操作符const int 0p_d 1;/操作數(shù)typedef class edgepublic:int start;char input;int end;friend bool operator const _edge& a, const _edge& ba. endr

7、eturn a. startb. start && a. input b. input ib. end ;edge;/自動(dòng)機(jī)的邊typedef struct _nfaint start;int end;nfa; /class remanagcpublic:remanage ;remanage string re ;virtual remanage ;/處理新的輸入void process ;/測(cè)試輸入字符串，判斷能否由生成的dfa識(shí)別bool teststring string str ;設(shè)置正規(guī)式void setre string re ;/設(shè)置nfavoid setnfa

8、vector edge,vector start,vector end ;設(shè)置dfavoid setdfa vector edge, int start,vector end ; private:清空所有容器變量void clear ;/輸岀處理結(jié)果void outputresult ;系統(tǒng)實(shí)現(xiàn)程序流程圖重要編碼實(shí)現(xiàn)說(shuō)明/*分析 re 函數(shù)*/*正規(guī)式到nfa的轉(zhuǎn)換*/void processretonfa ;int state; /計(jì)數(shù)狀態(tài)int type char re ;/判斷輸入字符的類型：op, 0p_dre到nfa轉(zhuǎn)換有關(guān)函數(shù)/*對(duì)單個(gè)輸入字符構(gòu)造相應(yīng)的nfa*/void make

9、nfa_s char input, nfa* n,vector & edge ;/*構(gòu)造某個(gè)nfa的閉包*/void makenfa_cl nfa* result, nfa* op,vector & edge ;/*構(gòu)造兩個(gè)nfa的或運(yùn)算*/void makenfa or nfa* result, nfa* left, nfa* right, vector & edge ;/*構(gòu)造兩個(gè)nfa的與運(yùn)算*/void makenfa_and nfa* result, nfa* left, nfa* right, vector & edge ;/*nfa到dfa的轉(zhuǎn)換*

10、/void processnfatodfa ;/*找到集合input的$閉包，結(jié)果保存在集合output中*/void find_null_closure vector input, vector &output,vector edge ;/*計(jì)算集合input在輸入為in時(shí)的所能達(dá)到的狀態(tài)集合result*/void move vector input,char in,vector &result,vector edge ;/*dfa 最小化有關(guān)函數(shù)*/ /*最小化dfa*/void minimizedfa ;/*在dfa中當(dāng)初態(tài)為start,輸入為input時(shí)，返回終態(tài)*/

11、int movddfa int start,char input ;/*找到輸入終態(tài)end所在的集合*/int findgather int end,vector vector gather ;/*消除dfa中的無(wú)用狀態(tài)*/void rcmovefutility ;/*合并dfa中的等價(jià)狀態(tài)*/void combineequality/| | i i 1ztx!" !" !" !" !" !" !" !“ !“ !“ !“ 7“ !“ r、r、r、r、r、r、/ofstream out;正規(guī)式對(duì)應(yīng)的變量string re;v

12、ector reinput; bool isreupdate;/nfa對(duì)應(yīng)的變量/輸入的正規(guī)式正規(guī)式的輸入符正規(guī)式是否已更新vector nfainput; /nfa 的輸入符vector startnfa; /nfa 的起始狀態(tài)集vectorendnfa;/nfa的終態(tài)集vector nfa_edge;/構(gòu)造出的nfa的所有邊的集合bool isnfaupdate;/nfa 是否己更新/dfa對(duì)應(yīng)的變量vector dfainput; /dfa 的輸入符int startdfa;/dfa 的起始狀態(tài)vector enddfa;/dfa 的終態(tài)集vector nonenddfa;/dfa 的非

13、終態(tài)集vector dfa_edge; /由nfa所構(gòu)造成的dfa的邊的集合vector vector dfastategathcr;/dfa 中各個(gè)狀態(tài)對(duì)應(yīng)于nfa中的狀態(tài)集bool isdfaupdate; /dfa 是否已更新/dfa最小化后對(duì)應(yīng)的變量vectorminidfatnput;/最小化后dfa的輸入符int ministartdfa;/最小化后dfa的起始狀態(tài)vectorminienddfa;/最小化后dfa的終態(tài)集vectormininonenddfa;/最小化后dfa的非終態(tài)集vectorminidfa_edge;/最小化后dfa中的邊的集合vector vector m

14、inistategather;/最小化后 dfa 中各個(gè)狀態(tài)對(duì)應(yīng)于初始dfa中的狀態(tài)集程序運(yùn)行效果截圖說(shuō)明課程設(shè)計(jì)總結(jié)及結(jié)論編譯原理是一門(mén)很重要的課程。我們平常寫(xiě)小的c語(yǔ)言程序會(huì)感到困難，而編譯原理則是關(guān)于編寫(xiě)編譯器的技術(shù)，難度之大可想而知。編譯器的編寫(xiě)一直被認(rèn)為是十分困難的事情，第一 fortran的編譯器據(jù)說(shuō)花了 18年的時(shí)間才完成。#pragma warning disable:4786ttincludeincludettincludettincludeusing namespace std;#include "remanage.hvoid waitforinputcout e

15、ndl;cout 輸入完畢后，請(qǐng)按任意鍵開(kāi)始處理.；cout endl endl;getch ;11wnd note findwindow "notepad", null ;:sendmessage note, wm close,0,0 ;void readre string& reifstrcani in re txt"in re;void readteststring vector & strifstream in "tcststring. txt"string temp;for ;getline in, temp , te

16、mp, size 0;str. push_back temp ;vector & endvoid readnfa vector & edgegather, vector & start, ifstream innfa ，znfa. txt"edge edge;int edgenum, startnum, endnum, temp;edgcgather. clear ;start, clear ;end. clear ;innfa edgenum;for int i 0;i edgenum;i+innfa edge.start edge, input edge.

17、end;cdgcgathcr. push back edge ;innfa startnum;for i 0;i startnum;i+innfa temp;start.pushback temp ;innfa cndnum;for i 0;i endnum;i+innfa temp;end.push_back temp ;vector & endvoid rcaddfa vcctor & cdgcgathcr, int start, ifstream indfa dfa. txt"edge edge;int edgenum, startnum, endnum, te

18、mp;edgcgather. clear ;end. clearindfa edgenum;for int i 0;i edgenum;i+indfa edge, start edge, input edgegather. push_back edge ;indfa startnum;indfa start;indfa cndnum;for i 0;i endnum;i+indfa temp;end.push_back temp ;void outtcstrcsult vcctor str,vcctorofstream out testresu；for int i 0;i str.size ;

19、i+edge, end;ispassout str i" if ispassiout "pass" endl;elseout faile endl;void mainremanage test;shellexccutenull, "open", "instructions, txt', null, null, sw_sh0wn0rmal ;cout "說(shuō)明： 詳見(jiàn) instructions. txt" endl;cout "請(qǐng)閱讀后按任意鍵開(kāi)始.；getch ;hwnd note findwind

20、ow "notepad",null ;:sendmessage note, wm close, 0,0 ;/end state gather for both nfa andcout endl cndl;string re;/regular expressionvector stringgather;/test string gathervector edgegather;/edge gather for both nfa and deaint startdfa 0;/start state for dfavectorstartnfa;/start state gather

21、 for nfavectorend;dfavector ispass;for ;stringgather. clear edgegather. clear startnfa. clear ; end. clear ; ispass. clear ;int choice 0:cout選擇你的輸入方式："endl;cout"1.輸入正規(guī)式"endl;cout2.輸入 7fa endl ;cout”3.輸入 dfa" endl;cout"0.退岀 endl;cout輸入你的選擇廣4 ：cinchoice;switch choicecase 1:shc

22、llexccutcnull,open，re. txt，null, null, sw_sh0wn0rmal ; waitforlnput ;readre re ;test. setre re ;test. process ;break;case 2:shellexecutenull, "open", "nfa. txt", null, null, sw_shownormal ;waitforlnput ;readnfa edgegather, startnfa, end ; test. setnfa edgegather, startnfa, end ; test.process ;break;case 3:shellexecutenull, opcn，dfa txt", null, null, sw_siiownormal ;waitforlnput ;readdfa edgegather, startdfa, end ; test.setdfa edgegather, startdfa, e