用C語(yǔ)言采用模擬DFA算法編寫一個(gè)掃描器

1、精選優(yōu)質(zhì)文檔-傾情為你奉上用C語(yǔ)言采用模擬DFA算法編寫一個(gè)掃描器/*第一章：相關(guān)知識(shí)DFA定義：一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，f，S，Z）其中 K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)； 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào)字母表； f是轉(zhuǎn)換函數(shù)，是K×K上的映射，即，如 f（ki，a）=kj， （kiK，kjK）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj， 我們把kj稱作ki的一個(gè)后繼狀態(tài)； S K是唯一的一個(gè)初態(tài)； Z?K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。第二章：題目用C語(yǔ)言采用模擬DFA算法

2、編寫一個(gè)掃描器（詞法分析器）用來(lái)識(shí)別：由任意個(gè)a或b開始后接aa再自加或自減1的字符串，即正規(guī)式r=(a|b)*aa(+|-)1描述的語(yǔ)言L（r）。該詞法分析器的任務(wù)：（1）濾掉源程序中的無(wú)用成分，如空格；（2）識(shí)別正規(guī)式r=(a|b)*aa(+|-)1描述的字符串。從鍵盤讀入或打開文件讀入字符串，詞法分析器讀入字符ywe串后掃描源字符串，若發(fā)現(xiàn)符合符合正規(guī)式r描述的字符串時(shí)，輸出“yes”或“可接受”或“可識(shí)別”，否則輸出“no”或“不可識(shí)別”。第三章：分析第一節(jié). 根據(jù)正規(guī)式(a|b)*aa(+|-)1，我們可以分析出 K有10個(gè)狀態(tài)，也就是10個(gè)元素： 狀態(tài) s0:這時(shí)候已經(jīng)識(shí)別的字符個(gè)

3、數(shù)為0，也就是開始狀態(tài) 狀態(tài) s1:從狀態(tài)s0開始接受連續(xù)的字母 'a'，轉(zhuǎn)到狀態(tài) s1 狀態(tài) s2:從狀態(tài)s0開始接受連續(xù)的字母 'b'，轉(zhuǎn)到狀態(tài) s2 狀態(tài) s3:從s2開始接受了一個(gè)字母 'a'，轉(zhuǎn)到狀態(tài) s3 狀態(tài) s4:從s3開始接受了一個(gè)字母 'a'，轉(zhuǎn)到狀態(tài) s4 狀態(tài) s5:如果s1已經(jīng)連續(xù)接受了至少兩個(gè)字母 'a',從s4開始接受一個(gè)符號(hào) '+'，轉(zhuǎn)到狀態(tài) s5 。 或 從s4開始接受了一個(gè)符號(hào) '+'，轉(zhuǎn)到狀態(tài) s5 。 狀態(tài) s6:如果s1已經(jīng)連續(xù)接受了至少兩個(gè)

4、字母 'a',從s4開始接受一個(gè)符號(hào) '-'，轉(zhuǎn)到狀態(tài) s6 。 或 從s4開始接受了一個(gè)符號(hào) '-'，轉(zhuǎn)到狀態(tài) s6 。 狀態(tài) s7:從s5或s6開始接受了一個(gè)數(shù)字 '1'，轉(zhuǎn)到 s7。 狀態(tài) s8:從s7開始接受了一個(gè)字符串結(jié)束符號(hào) '0'，轉(zhuǎn)到狀態(tài)s8?！具@是成功狀態(tài)】。 狀態(tài) s9:【這是出錯(cuò)狀態(tài)】。 第二節(jié). 根據(jù)正規(guī)式(a|b)*aa(+|-)1，我們可以分析出包含的字母有：a,b,+,-,1第三節(jié). 根據(jù)正規(guī)式(a|b)*aa(+|-)1，我們分析出轉(zhuǎn)換函數(shù) f 有： F0. s0 -(輸入一個(gè)字母&

5、#39;a') -> s1 F1. s0 -(輸入一個(gè)字母'b') -> s2 F2. s1 -(輸入一個(gè)字母'a') -> s1 F3. s2 -(輸入一個(gè)字母'b') -> s2 F4. s2 -(輸入一個(gè)字母'a') -> s3 F5. s3 -(輸入一個(gè)字母'a') -> s4 F6. 如果狀態(tài) s1中已經(jīng)累積有至少兩個(gè)字母'a' s1 -(輸入一個(gè)符號(hào)'+') -> s5 F7h. s4 -(輸入一個(gè)字母'+'

6、;) -> s5 F8. 如果狀態(tài) s1中已經(jīng)累積有至少兩個(gè)字母'a' s1 -(輸入一個(gè)符號(hào)'-') -> s6 F9. s4 -(輸入一個(gè)字母'-') -> s6 F10. s5 -(輸入一個(gè)數(shù)字'1') -> s7 F11. s6 -(輸入一個(gè)數(shù)字'1') -> s7 F12. s7 -(輸入一個(gè)字符串結(jié)束符'0') -> s8(成功狀態(tài)) F13. 其他情況，統(tǒng)一進(jìn)入狀態(tài) s9(出錯(cuò)狀態(tài)) 第四節(jié). 根據(jù)正規(guī)式(a|b)*aa(+|-)1，我們分析出【唯一

7、的】初態(tài)S即K中的 s0第五節(jié). 根據(jù)正規(guī)式(a|b)*aa(+|-)1，我們分析出結(jié)束狀態(tài)有兩個(gè)，即K中的 s8（成功狀態(tài)）,s9(出錯(cuò)狀態(tài)) */#include <stdio.h>/* 下面的一組全局參數(shù)是作為自動(dòng)機(jī)的參數(shù) */ 正則式const char regex="(a|b)*aa(+|-)1"/ 狀態(tài)集合int states10=0;/ 狀態(tài)總數(shù)const int statesAmount = sizeof(states)/sizeof(int);/ 可接受的字符集合const char letterSet="ab+-1"/ 開

8、始狀態(tài) const int startStateId=0;/ 可接受的結(jié)束狀態(tài)集const int endStateIds=8,9;/ 可接受的結(jié)束狀態(tài)總數(shù)const int endStatesAmount = sizeof(endStateIds)/sizeof(int);/ 成功狀態(tài)集const int succeedStateIds = 8;/ 成功狀態(tài)總數(shù)const int succeedStateAmount = sizeof(succeedStateIds)/sizeof(int);/ 當(dāng)前狀態(tài)int currentStateId = startStateId;/ 轉(zhuǎn)換過(guò)程中的狀態(tài)

9、變化堆棧const int MAX_STACK_SIZE = 2000;int statesTransStackMAX_STACK_SIZE;int statesTransStackTop = -1;/ 是否輸出狀態(tài)變化日志開關(guān)（開:1，關(guān)：0）。根據(jù)需要選擇。const int isStateChangLogOn = 0; / 初始化自動(dòng)機(jī)void init() int i; / 當(dāng)前狀態(tài)號(hào)重置 currentStateId = startStateId; / 所有狀態(tài)數(shù)組清零 for(i=0;i<statesAmount;i+) statesi=0; / 記錄狀態(tài)出現(xiàn)次數(shù) state

10、scurrentStateId+; / 轉(zhuǎn)換過(guò)程中的狀態(tài)變化堆棧指針重置 statesTransStackTop = -1; / 狀態(tài)變化堆棧中放入初始狀態(tài) statesTransStack+statesTransStackTop = currentStateId;/* 判斷當(dāng)前自動(dòng)機(jī)是否已經(jīng)進(jìn)入結(jié)束狀態(tài) 返回： 已經(jīng)進(jìn)入結(jié)束狀態(tài)：1 還未進(jìn)入結(jié)束狀態(tài)：0*/int isEnd() int i; for(i=0;i<endStatesAmount;i+) if(currentStateId = endStateIdsi) return 1; return 0; /* 判斷當(dāng)前自動(dòng)機(jī)是否已

11、經(jīng)進(jìn)入成功狀態(tài) 返回： 已經(jīng)進(jìn)入成功狀態(tài)：1 還未進(jìn)入成功狀態(tài)：0*/int isSucceed() int i; for(i=0;i<succeedStateAmount;i+) if(currentStateId = succeedStateIdsi) return 1; return 0; /* 自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換函數(shù) 參數(shù)： ch ：當(dāng)前讀到的字符*/void trans(char ch) if(isEnd() return ; /* F0. s0 -(輸入一個(gè)字母'a') -> s1 F1. s0 -(輸入一個(gè)字母'b') -> s2 F

12、2. s1 -(輸入一個(gè)字母'a') -> s1 F3. s2 -(輸入一個(gè)字母'b') -> s2 F4. s2 -(輸入一個(gè)字母'a') -> s3 F5. s3 -(輸入一個(gè)字母'a') -> s4 F6. 如果狀態(tài) s1中已經(jīng)累積有至少兩個(gè)字母'a' s1 -(輸入一個(gè)符號(hào)'+') -> s5 F7h. s4 -(輸入一個(gè)字母'+') -> s5 F8. 如果狀態(tài) s1中已經(jīng)累積有至少兩個(gè)字母'a' s1 -(輸入一個(gè)符號(hào)&

13、#39;-') -> s6 F9. s4 -(輸入一個(gè)字母'-') -> s6 F10. s5 -(輸入一個(gè)數(shù)字'1') -> s7 F11. s6 -(輸入一個(gè)數(shù)字'1') -> s7 F12. s7 -(輸入一個(gè)字符串結(jié)束符'0') -> s8(成功狀態(tài)) F13. 其他情況，統(tǒng)一進(jìn)入狀態(tài) s9(出錯(cuò)狀態(tài)) */ switch(currentStateId) case 0: / F0. s0 -(輸入一個(gè)字母'a') -> s1 if(ch = 'a'

14、) currentStateId = 1; / F1. s0 -(輸入一個(gè)字母'b') -> s2 else if(ch = 'b') currentStateId = 2; / F13 else currentStateId = 9; break; case 1: / F2. s1 -(輸入一個(gè)字母'a') -> s1 if(ch = 'a') currentStateId = 1; / F6 . 如果狀態(tài) s1中已經(jīng)累積有至少兩個(gè)字母'a', / s1 -(輸入一個(gè)符號(hào)'+') -&

15、gt; s5 else if(ch = '+' && states1>=2) currentStateId = 5; / F8 . 如果狀態(tài) s1中已經(jīng)累積有至少兩個(gè)字母'a' / s1 -(輸入一個(gè)符號(hào)'-') -> s6 else if(ch = '-' && states1>=2) currentStateId = 6; / F13 else currentStateId = 9; break; case 2: / F3. s2 -(輸入一個(gè)字母'b') -&

16、gt; s2 if(ch = 'b') currentStateId = 2; / F4. s2 -(輸入一個(gè)字母'a') -> s3 else if(ch = 'a') currentStateId = 3; / F13 else currentStateId = 9; break; case 3: / F5. s3 -(輸入一個(gè)字母'a') -> s4 if(ch = 'a') currentStateId = 4; / F13 else currentStateId = 9; break; cas

17、e 4: / F7 . s4 -(輸入一個(gè)字母'+') -> s5 if(ch = '+') currentStateId = 5; / F9 . s4 -(輸入一個(gè)字母'-') -> s6 else if(ch = '-') currentStateId = 6; / F13 else currentStateId = 9; break; case 5: / F10. s5 -(輸入一個(gè)數(shù)字'1') -> s7 if(ch = '1') currentStateId = 7; /

18、 F13 else currentStateId = 9; break; case 6: / F11. s6 -(輸入一個(gè)數(shù)字'1') -> s7 if(ch = '1') currentStateId = 7; / F13 else currentStateId = 9; break; case 7: / F12. s7 -(輸入一個(gè)字符串結(jié)束符'0') -> s8(成功狀態(tài)) if(ch = '0') currentStateId = 8; / F13 else currentStateId = 9; break;

19、 case 8: / 實(shí)際不可能執(zhí)行這個(gè)分支 break; case 9: / 實(shí)際不可能執(zhí)行這個(gè)分支 break; default: / 實(shí)際不可能執(zhí)行這個(gè)分支 currentStateId = 9; / 記錄狀態(tài)出現(xiàn)次數(shù) statescurrentStateId+; / 記錄狀態(tài)變化 statesTransStack+statesTransStackTop = currentStateId;/* 根據(jù)正則式 regex 進(jìn)行識(shí)別字符串 str 參數(shù)： str ：要識(shí)別的字符串 返回： 識(shí)別成功，符合正則式 regex ：1 識(shí)別失?。? */int recognize(char str) int i,len = strlen(str); / 每次開始識(shí)別前都要重新初始化自動(dòng)機(jī) init(); / 逐個(gè)字母識(shí)別，直到全部字母被識(shí)別完(包括字符串結(jié)束符'0')， / 或自動(dòng)機(jī)進(jìn)入結(jié)束狀態(tài) for(i=0;i<=len&&!isEnd();i+) trans(stri); / 如果需要輸出轉(zhuǎn)換狀態(tài)變化的日志 if(isStateChangLogOn) printf(&