利用子集法構(gòu)造DFA

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)一：利用子集法構(gòu)造DFA 一實(shí)驗(yàn)?zāi)康恼莆諏⒎谴_定有限自動(dòng)機(jī)確定化的方法和過程。二實(shí)驗(yàn)要求、內(nèi)容及步驟實(shí)驗(yàn)要求：1.輸入一個(gè)NFA，輸出一個(gè)接受同一正規(guī)集的DFA；2.采用C+語言，實(shí)現(xiàn)該算法；3.編制測(cè)試程序；4.調(diào)試程序。實(shí)驗(yàn)步驟：1.輸入一個(gè)NFA關(guān)系圖；2.通過一個(gè)轉(zhuǎn)換算法將NFA轉(zhuǎn)換為DFA；3.顯示DFA關(guān)系圖。三實(shí)驗(yàn)設(shè)備計(jì)算機(jī)、Windows 操作系統(tǒng)、Visual C+ 程序集成環(huán)境。四實(shí)驗(yàn)原理1.NFA-DFA轉(zhuǎn)換原理：從NFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本思路

2、是：DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài)。 DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能到達(dá)的所有狀態(tài)。輸入：一個(gè)NFA N輸出：一個(gè)接受同樣語言的DFA D方法：為D構(gòu)造轉(zhuǎn)換表Dtran，DFA的每個(gè)狀態(tài)是NFA的狀態(tài)集。D的狀態(tài)集合用Dstates表示。D的開始狀態(tài)為-closure(s0)，s0是N的開始狀態(tài)。使用下列算法構(gòu)造D的狀態(tài)集合Dstates和轉(zhuǎn)換表Dtran。如果D的某個(gè)狀態(tài)是至少包含一個(gè)N的接受狀態(tài)的NFA狀態(tài)集，那么它是D的一個(gè)接受狀態(tài)。2.子集構(gòu)造法：初始時(shí), -closure(S0) 是 Dstates 中唯一的狀態(tài)且未被標(biāo)記;while Dstates

3、中存在一個(gè)未標(biāo)記的狀態(tài)T do begin標(biāo)記T; for 每個(gè)輸入符號(hào) a do beginU := -closure ( move (T, a) );if U 沒在Dstates中 then將U作為一個(gè)未被標(biāo)記的狀態(tài)添加到 Dstates.Dtran T, a := Uendend3.-closure的計(jì)算：將T中所有狀態(tài)壓入棧stack;將-closure (T) 初始化為T;while stack不空 do begin將棧頂元素t彈出棧; for 每個(gè)這樣的狀態(tài)u：從t到u有一條標(biāo)記為 的邊do if u 不在-closure ( T )中 do begin 將u 添加到-closur

4、e ( T ); 將u壓入棧stack中 endend五程序設(shè)計(jì)1.總體設(shè)計(jì)讀入字符識(shí)別模塊識(shí)別標(biāo)識(shí)符識(shí)別分界符、運(yùn)算符識(shí)別常數(shù)輸出2.子程序設(shè)計(jì) 識(shí)別模塊讀取字符字母識(shí)別標(biāo)識(shí)符數(shù)字識(shí)別數(shù)字/識(shí)別注釋打印并結(jié)束FTFTFT六程序中的結(jié)構(gòu)說明1.結(jié)構(gòu)體Symbolrecord結(jié)構(gòu)體結(jié)構(gòu)體成員名成員屬性Symbol10用于存儲(chǔ)關(guān)鍵字編碼名id用于存儲(chǔ)關(guān)鍵字對(duì)應(yīng)的編碼entrytype結(jié)構(gòu)體結(jié)構(gòu)體成員名成員屬性idname10用于存儲(chǔ)識(shí)別后標(biāo)識(shí)符名address用于存儲(chǔ)標(biāo)識(shí)符的地址type用于存儲(chǔ)標(biāo)識(shí)符的類型digittype結(jié)構(gòu)體結(jié)構(gòu)體成員名成員屬性num用于存儲(chǔ)識(shí)別后的數(shù)字address用于存儲(chǔ)

5、標(biāo)識(shí)符數(shù)字的地址tokentype結(jié)構(gòu)體結(jié)構(gòu)體成員名成員屬性id用于存儲(chǔ)被識(shí)別的類型名entry用于存儲(chǔ)標(biāo)識(shí)符的地址idname10用于存儲(chǔ)被識(shí)別的標(biāo)識(shí)符名2.符號(hào)編碼表符號(hào)編碼表符號(hào)名代碼符號(hào)名代碼Begin014End1(15If2)16Then317Else421+8=22-9:=23*10 24/11Id25;12Const26133.重要函數(shù)介紹tokentype recogid(char ch) /識(shí)別標(biāo)識(shí)符算法tokentype recogdig(char ch) /識(shí)別數(shù)字函數(shù)tokentype recogdel(char ch) /識(shí)別算符和界符函數(shù)tokentype han

6、dlecom(char ch) /handlecom函數(shù)，識(shí)別注釋函數(shù)void sort(char ch) /sort函數(shù)，讀取文件內(nèi)容，并根據(jù)讀入內(nèi)容調(diào)用不同的識(shí)別函數(shù)void scanner()/scanner函數(shù)，打開文件七.函數(shù)代碼#include #include #include #include /定義單詞編碼表的數(shù)據(jù)結(jié)構(gòu)struct symbolrecord char symbol10; int id; ;/定義符號(hào)表的數(shù)據(jù)結(jié)構(gòu)struct entrytype char idname10; int address; int type;/定義常數(shù)表的數(shù)據(jù)結(jié)構(gòu)struct digi

7、ttype int num; int address;/Token字的數(shù)據(jù)結(jié)構(gòu)struct tokentype int id; int entry; char idname10;FILE *fp; /源文件指針struct digittype d10; /定義常數(shù)表，個(gè)數(shù)指針struct entrytype a40;int k=0,t=0;/單詞編碼表初始化struct symbolrecord s26= Begin,0, End,1, If,2, Then,3, Else,4, for,5, do,6, while,7, +,8, -,9, *,10, /,11, ;,12, ,13, ,1

8、4, (,15, ),16, ,17, ,21, =,22, :=,23, ,24, const,26;/識(shí)別標(biāo)識(shí)符算法tokentype recogid(char ch) tokentype tokenid; FILE *fs; int flag,fflag; char word10=0; int i,j; i=0; while(isalpha(ch)|isdigit(ch) wordi=ch; ch=fgetc(fp); i=i+1; ungetc(ch,fp); wordi=0; for(j=0;j=8;j+) flag=strcmp(word, sj.symbol); if(flag=

9、0) /是關(guān)鍵字 tokenid.id=j; tokenid.entry=-1; break; if(flag!=0) for(j=0;j=k;j+)fflag=strcmp(aj.idname,word); if(fflag=0) /在符號(hào)表中可以找到 tokenid.id=25; tokenid.entry=aj.address; break; if(fflag!=0) fs=fopen(symbol.txt,a); /符號(hào)表中不存在的標(biāo)識(shí)符 strcpy(ak.idname, word); ak.address=k; ak.type=25; tokenid.id=25; tokenid.

10、entry=k; for(j=0;j9;j+) fprintf(fs,%c,wordj); fprintf(fs,%c,t); fprintf(fs,%d,ak.address); fprintf(fs,%c,t); fprintf(fs,%d,ak.type); fprintf(fs,%c,n); fclose(fs); k=k+1; strcpy(tokenid.idname, word);/自行添加的 return tokenid;/識(shí)別數(shù)字函數(shù)tokentype recogdig(char ch) int flag; int i=0,j; int num=0; tokentype to

11、kenid; while(isdigit(ch) num=(ch-48)+num*10; ch=fgetc(fp); i=i+1; for(j=0;jchar return tokenid;/識(shí)別算符和界符函數(shù)tokentype recogdel(char ch) tokentype tokenid; switch(ch) case: tokenid.id=13; strcpy(tokenid.idname, );/自行添加的break; case: tokenid.id=14; strcpy(tokenid.idname, );break; case;: tokenid.id=12; str

12、cpy(tokenid.idname, ;);break; case=: tokenid.id=19; strcpy(tokenid.idname, =);break; case:ch=fgetc(fp); if(ch=) tokenid.id=23; break; case!: ch=fgetc(fp); if(ch=) tokenid.id=20; strcpy(tokenid.idname, !=); break; case: ch=fgetc(fp); if(ch=) tokenid.id=18; strcpy(tokenid.idname, =); else tokenid.id=1

13、7; strcpy(tokenid.idname, :ch=fgetc(fp); if(ch=) tokenid.id=22; strcpy(tokenid.idname, =); else tokenid.id=21; strcpy(tokenid.idname, ); ungetc(ch,fp); break; case+: tokenid.id=8; strcpy(tokenid.idname, +); break; case*: tokenid.id=10; strcpy(tokenid.idname, *); break; case(: tokenid.id=15; strcpy(t

14、okenid.idname, (); break; case): tokenid.id=16; strcpy(tokenid.idname, ); break; tokenid.entry=-1; return tokenid; /handlecom函數(shù)/tokentype handlecom(char ch) tokentype tokenid; char ch1; int flag=0; if(ch!=* ) tokenid.id=25; tokenid.entry=-1; else while(flag=0) ch1=ch; ch=fgetc(fp); if(ch1=*)&(ch=/)

15、flag=1; return tokenid;/sort函數(shù)/void sort(char ch) struct tokentype tokenword; FILE * fq = fopen(tokenfile.txt,a);if(isalpha(ch) tokenword=recogid(ch); /字母else if(isdigit(ch) tokenword=recogdig(ch); /數(shù)字 else if(ch=/) tokenword=handlecom(ch); elsetokenword=recogdel(ch);printf(%st%dt%dn,tokenword.idnam

16、e,tokenword.id,tokenword.entry); fprintf(fq,%d,tokenword.id); fprintf(fq,%c,t); fprintf(fq,%d,tokenword.entry); fprintf(fq,%c,n); fclose(fq);/scanner函數(shù)/void scanner() char ch; fp=fopen(source.txt,r); ch=getc(fp); while(ch!=EOF) if(!isspace(ch) sort(ch); ch=fgetc(fp); fclose(fp);int main() int i; pri

17、ntf(輸出token字如下:n); printf(idnamettypetaddressn); scanner(); printf(*n); printf(輸出符號(hào)表如下：n); printf(%st%st%sn,idname,address,type); for(i=0;i=k-1;i+) printf(%st%dt%dn,ai.idname,ai.address,ai.type); printf(*n); printf(輸出常數(shù)表如下：n); printf(%st%sn,num,address); for(i=0;i=t-1;i+) printf(%dt%dn,di.num,di.address); printf(nn); system(pause);八程序測(cè)試Source源文件程序截圖main() If a!=35end;do while end;36九實(shí)驗(yàn)小結(jié)子集構(gòu)造法的基本思