編譯原理課程設(shè)計(jì)-nfa的確定化

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：29 大小：412.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩28頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　計(jì)算機(jī)系　　編譯原理課程設(shè)計(jì)　課程名稱:編譯原理　課程代碼:436105　題目:NFA的確定化　年級/專業(yè)

2、/班:　學(xué) 生姓名:　學(xué) 號:　指導(dǎo) 老師:　開題時間:　完成時間:　　目錄

3、　一、引言- 4 -　　二、設(shè)計(jì)目的與任務(wù)- 4 -　　1、設(shè)計(jì)目的：- 4 -　　2、設(shè)計(jì)任務(wù)：- 4 -　　三、設(shè)計(jì)方案- 5 -　　1、總體設(shè)計(jì)- 5 -　　2、詳細(xì)

4、設(shè)計(jì)- 11 -　　3、程序清單- 14 -　　4、程序調(diào)試與體會- 23 -　　5、運(yùn)行結(jié)果- 24 -　　四、結(jié) 論- 26 -　　五、致謝- 26 -　　六、參考文獻(xiàn)

5、- 26 -　　2 設(shè)計(jì)進(jìn)度完成情況- 27 -　　摘要　　確定有限自動機(jī)確定的含義是在某種狀態(tài)，面臨一個特定的符號只有一個換，進(jìn)入唯一的一個狀態(tài)。不確定的有限自動機(jī)則相反．在某種狀態(tài)下，面臨個特定的符號是存在不止一個轉(zhuǎn)換即是可以允許進(jìn)入一個狀態(tài)集合。在非確定的有限自

6、動機(jī)NFA中．由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進(jìn)行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。這種不確定性給識別過程帶來的反復(fù)，無疑會影響到NFA的工作效率。而DFA則是確定的，將NFA轉(zhuǎn)化為DFA將大大提高工作效率，因此將NFA轉(zhuǎn)化為DFA是必要的。對任意的一個不確定有限自動機(jī)（NFA），都會存在一個等價的確定的有限自動機(jī)（DFA），即L（N）=L(M)。本文主要是介紹如何將NFA轉(zhuǎn)換為與之等價的簡化DFA，通

7、過具體實(shí)例，結(jié)合圖形，詳細(xì)說明轉(zhuǎn)換的算法原理。　　關(guān)鍵詞：有限自動機(jī)；確定有限自動機(jī)（DFA），不確定有限自動機(jī)（NFA）　　Abstract　　Finite automata are determinate and indeterminate two classes. De

8、termine the meaning is in a certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata are the opposite. In a certain state, Faces a symbol is the presence of mo

9、re than one conversion, which is to be allowed to enter a state set.　　Non deterministic finite state automata NFA, because of some state are transferred from a number of possible follow-up states are

10、 chosen, so NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated. Will undoubtedly affect the efficiency of the NFA .While the DFA is determined, co

11、nvening NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary.　　For any a nondeterministic finite automaton (NFA) can be an equivalent deterministic fini

12、te automaton (DFA), L (N) =L (M). This paper mainly introduces how to convert NFA to equivalent simplified DFA, through concrete examples, combined with graphics, a detailed description of the algorithm principle of conv

13、ersion.　　Keywords: finite automata; deterministic finite automaton (DFA), nondeterministic finite automaton (NFA).　　《編譯原理》課程設(shè)計(jì)　　-- NFA的確定化設(shè)計(jì)<p

14、>　　一、引言　　在編譯系統(tǒng)中,詞法分析階段是整個編譯系統(tǒng)的基礎(chǔ)。對于單詞的識別，有限自動機(jī)FA是一種十分有效的工具。有限自動機(jī)由其映射f是否為單值而分為確定的有限自動機(jī)DFA和非確定的有限自動機(jī)NFA。在非確定的有限自動機(jī)NFA中,由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進(jìn)行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。這種不確定性

15、給識別過程帶來的反復(fù)，無疑會影響到FA的工作效率。而DFA引擎在任意時刻必定處于某個確定的狀態(tài)，它搜索是無需象NFA一樣必須記錄所有的可能路徑（trace multiple possible routes through the NFA），這也是DFA運(yùn)行效率高于DFA的原因。而已經(jīng)證明DFA是NFA的一個特例，即對于每一個NFA M存在一個DFA M’’，使得L(M)=L(M’’)。<b

16、>　　二、設(shè)計(jì)目的與任務(wù)　　通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是：充分理解和掌握NFA，DFA以及NFA確定化過程的相關(guān)概念和知識，編程實(shí)現(xiàn)對輸入NFA轉(zhuǎn)換成DFA輸出的功能。　　1、設(shè)計(jì)目的：　　掌握從NFA到DFA的轉(zhuǎn)換，以及用子集法把NFA轉(zhuǎn)換

17、成DFA理論，編程實(shí)現(xiàn)將NFA(不確定有窮自動機(jī))轉(zhuǎn)換為DFA(確定有窮自動機(jī))。　　2、設(shè)計(jì)任務(wù)：　　通過編程實(shí)現(xiàn)NFA轉(zhuǎn)換為DFA。　　三、設(shè)計(jì)方案　　1、總體設(shè)計(jì)</

18、b>　　完成該設(shè)計(jì)所用到的理論知識、及對問題的功能進(jìn)行分析，并總結(jié)出實(shí)現(xiàn)整個問題的程序模塊，及其功能。　　基本概念　　NFA和DFA的概念　　NFA (nondeterministic finite-state automata

19、)是不確定性有限狀態(tài)自動機(jī)的簡寫，NFA的定義為：　　一個不確定性有限狀態(tài)自動機(jī)由以下部分所組成：　　一個有限的輸入字符集I 　　一個有限的狀態(tài)集S　　狀態(tài)轉(zhuǎn)換函數(shù)f: S x I -> P(S)，P(S)為s的冪集 </

20、p>　　一個結(jié)束狀態(tài)集Q，Q是S的子集　　一個初始狀態(tài)s0 (屬于S)　　表示為A(I, S, f, Q, s0)　　例如，下圖就是一個不確定性有限狀態(tài)自動機(jī)：　　圖1：不確定性有限狀態(tài)自動機(jī)　　圖中，

21、有一種特殊的轉(zhuǎn)換Epsilon轉(zhuǎn)換，表示輸入一個空字符，由一個狀態(tài)轉(zhuǎn)換為另一個狀態(tài)。例如，狀態(tài)s3到s4，s3到s5之間的轉(zhuǎn)換就是Eplison轉(zhuǎn)換。Epsilon轉(zhuǎn)換是NFA的一種特有的轉(zhuǎn)換。另外，狀態(tài)s0輸入字符a，可以轉(zhuǎn)換為s1或者s3，是不確定的，這也就是NFA成為不確定性有限狀態(tài)自動機(jī)的原因。圖中有兩個圈的狀態(tài)(s2, s6, s7)表示終結(jié)狀態(tài)，即找到匹配正則表達(dá)式的字符串。　　與N

22、FA相對應(yīng)，DFA (deterministic finite-state automata)表示確定性有限狀態(tài)自動機(jī)。與NFA不同，DFA不存在Epsilon轉(zhuǎn)換，并且每一個狀態(tài)轉(zhuǎn)換函數(shù)的值只對應(yīng)一個狀態(tài)，即一個狀態(tài)輸入一個字符，只能有一個狀態(tài)相對應(yīng)。　　NFA與DFA的區(qū)別　　顯然，DFA更加適合我們進(jìn)行字符串匹配，因?yàn)檩斎胍粋€字符，總能從一個狀態(tài)確

23、定地轉(zhuǎn)換為另一個狀態(tài)，直到終結(jié)狀態(tài)。NFA一個輸入可能對應(yīng)多個狀態(tài)，因此需要進(jìn)行回溯，先嘗試一條路徑，發(fā)現(xiàn)走不通，再回退到原來的狀態(tài)嘗試另外一條路徑，顯然匹配算法不如DFA簡單。給定一個NFA，總有一個DFA與之對應(yīng)，即一個NFA可以轉(zhuǎn)換成一個等價的DFA，我們將使用子集構(gòu)造算法實(shí)現(xiàn)NFA到DFA的轉(zhuǎn)換。　　轉(zhuǎn)換算法&

24、lt;/p>　　子集構(gòu)造算法　　首先，我們將正則表達(dá)式轉(zhuǎn)換為NFA，采用的算法是Thompson算法。對Epsilon和字符a，我們構(gòu)造如下之等價的NFA如圖2：　　圖2：Epsilon和字符a等價的NFA　　對基本的操作符RS, R|S, R*，

25、我們構(gòu)造如下與之等價的NFA如圖3：　　圖3：RS, R|S, R*與之等價的NFA　　有了這些基本的NFA，我們可以根據(jù)這些NFA構(gòu)造更為復(fù)雜的NFA。構(gòu)造的方法可以采用類似計(jì)算表達(dá)式的方法。例如正則表達(dá)式(a|b)*cd，計(jì)算過程為： PUSH a PUSH b

27、SH (a|b)*c) PUSH d CONCAT (POP d, POP (a|b)*c, 構(gòu)造與(a|b)*cd等價的NFA, PUSH (a|b)*cd) POP R (POP result) 在上面的例子中，我們需要比較運(yùn)算符的優(yōu)先級，比如"("的

28、優(yōu)先級比UNION高，UNION的優(yōu)先級比")"高，CONCAT的優(yōu)先級比UNION高。 　　利用上面方法我們已經(jīng)將正則表達(dá)式轉(zhuǎn)換成了等價的NFA，現(xiàn)在我們使用子集構(gòu)造算法將一個NFA轉(zhuǎn)換為DFA 。　　給定如圖4所示的NFA,　　圖4：NFA&

29、lt;/p>　　與之等價的DFA如圖5：　　圖5：與圖4等價的DFA　　通過NFA的介紹，我們知道NFA存在兩種轉(zhuǎn)換，Epsilon轉(zhuǎn)換和輸入字符轉(zhuǎn)換。對NFA中的初始狀態(tài)s1，我們構(gòu)造s1的Epsilon閉包(s1通過Epsilon轉(zhuǎn)換所能到達(dá)的狀態(tài)集)，為{s1,s2,s4}，對應(yīng)DFA中的初始狀態(tài)。從{s1,s2,s4}

30、我們可以構(gòu)造NFA對輸入字符a的轉(zhuǎn)換狀態(tài)集{s3,s4}，{s3,s4}的Epsilon閉包為{s3,s4}（產(chǎn)生新的狀態(tài)集），對應(yīng)DFA中初始狀態(tài){s1,s2,s4}對輸入字符a的轉(zhuǎn)換狀態(tài)。同理，{s1,s2,s4}對輸入字符b的轉(zhuǎn)換狀態(tài)集為{s5}，{s5}的Epsilon閉包也為{s5}（產(chǎn)生新的狀態(tài)集），對應(yīng)DFA中初始狀態(tài){s1,s2,s4}對輸入字符b的轉(zhuǎn)換狀態(tài)。從{s3,s4},{s5}，我們又可以構(gòu)造對每個輸入字符的狀態(tài)

31、轉(zhuǎn)換集，直到不再產(chǎn)生新的狀態(tài)集。就得到與NFA等價的DFA。DFA中的狀態(tài)集中只要包含一個NFA中的終結(jié)狀態(tài)，該狀態(tài)集就是DFA中的終結(jié)狀態(tài)。得到DFA，我們還可以進(jìn)一步地優(yōu)化DFA，找出DFA中只有入邊沒有出邊的狀態(tài)，假如節(jié)點(diǎn)不是終結(jié)狀態(tài)，則該狀態(tài)可以刪除。（DFA的優(yōu)化不在本設(shè)計(jì)考慮之內(nèi)）　　轉(zhuǎn)換過程</p&

32、gt;　　為了說明跟清晰，我們使用實(shí)例說明，構(gòu)造正規(guī)式1(0|1)*101的DFA？　　解：于求上式的DFA可以先求出其對應(yīng)的NFA，如圖6：　　圖6：正規(guī)式1(0|1)*101的NFA　　注：＃表示空輸入。

33、將其寫成M五元式則為：　　M=({0,1,2,3,4,5,6},{0,1},&,0,{6})　　其中&為：　　&(0,1)=1　　&(1,#)=2

34、　　&(2,#)=3&(2,0)=2&(2,1)=2　　&(3,1)=4　　&(4,0)=5　　&(5

35、,1)=6　　它所對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如表1：　　表1：狀態(tài)轉(zhuǎn)換矩陣　　根據(jù)NFA轉(zhuǎn)化為DFA的子集法轉(zhuǎn)換法進(jìn)行轉(zhuǎn)換。則按照子集法構(gòu)造正規(guī)表達(dá)式1(0|1)*101對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣見表2：　　表2

36、：狀態(tài)轉(zhuǎn)換矩陣　　對上表重新命名后的狀態(tài)轉(zhuǎn)換矩陣見表3：　　表3：重新命名后的狀態(tài)轉(zhuǎn)換矩陣　　將其寫成M五元式則為：　　M=({0,1,2,3,4,5},{0,1},&,0,{5})

37、　其中&為：　　&(0,1)=1　　&(1,0)=2&(1,1)=3　　&(2,0)=2&(2,1)=3　　&(3,0)=4&(3,1)=

38、3　　&(4,0)=2&(4,1)=5　　&(5,0)=4&(5,1)=3　　與表3對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖7所示：　　圖7：與表3對應(yīng)狀態(tài)轉(zhuǎn)換圖　　這樣就完成了從正規(guī)表達(dá)式1(0|1)*101

39、到DFA的轉(zhuǎn)化。　　2、詳細(xì)設(shè)計(jì)　　常量定義　　#define MAX 10//運(yùn)行最大值，用于限制狀態(tài)和邊的數(shù)量　　#define INFINIT 32767//特殊函數(shù)返回值&l

40、t;/p>　　#define NumMaxChar 10//最大字符數(shù)量　　#define NumMAXTN 10//最大結(jié)點(diǎn)數(shù)量　　數(shù)據(jù)結(jié)構(gòu)定義　　typedef struct edge<b

41、>　　{//邊　　int dest;//　　char cost; //代價　　struct edge *link;//指向下一邊　　}*Edge;

42、　　typedef struct vertex　　{//頂點(diǎn)　　char data;//狀態(tài)　　Edge adj;//邊　　}*Vertex; 　　typedef struct

43、 graph　　{//圖　　Vertex NodeTable;　　int NumVertex;//頂點(diǎn)（狀態(tài)）數(shù)量　　int MaxNumVertex;//最大允許頂點(diǎn)（狀態(tài)）數(shù)量

44、　int NumEdge;//該圖邊數(shù)量　　}*Graph;　　//////////////////////////////////////////////////////////////////////　　//////////////////////////狀態(tài)轉(zhuǎn)換表

45、機(jī)構(gòu)//////////////////////////////　　typedef struct tablenode　　{//轉(zhuǎn)換表節(jié)點(diǎn)　　char newname;//狀態(tài)集的新命名　　char ch[MAX];//頂點(diǎn)集

46、合，如{1,2,3}　　}*TableNode; 　　typedef struct tablequeue　　{//轉(zhuǎn)換表列　　TableNode TN[MAX];//轉(zhuǎn)換表節(jié)點(diǎn)數(shù)組　　cha

47、r transword;//轉(zhuǎn)換輸入字符，即轉(zhuǎn)換條件　　int NumTn;//添加的頂點(diǎn)數(shù)　　}*TableQueue; 　　typedef struct transmatrix　　{//狀態(tài)轉(zhuǎn)換矩陣

48、　　TableQueue TQ;//轉(zhuǎn)換表列組　　int transnum;//轉(zhuǎn)換表列數(shù)　　}*TranMatrix; 　　/////////////////////////////////////////////////////////////////&l

49、t;p>　　部分關(guān)鍵函數(shù)說明　　int GraphEmpty(Graph g)/判斷圖是否為空　　int GraphFull(Graph g)//判斷圖是否以滿　　char GetValue(Graph g,int i)//在圖g中尋找下標(biāo)為i的頂點(diǎn)</p

50、>　　void Insert_Vertex(Graph g,char vertex)//向圖g插入新頂點(diǎn)　　void Insert_Edge(Graph g,int v1,int v2,char weight)//向圖g插入新邊　　int GetVertexPos(Graph g,char v)//得到頂點(diǎn)在圖中

51、的下標(biāo)　　void Construct_Graph(Graph g)//構(gòu)建圖，要求輸入每個邊和每個頂點(diǎn)　　void Destruct_Graph(Graph g)//銷毀圖　　void Show_Graph(Graph g)//顯示圖　　void Ini

52、t_Matrix(TranMatrix TM)　　//始化狀態(tài)轉(zhuǎn)換矩陣，要輸入接受字符數(shù)和轉(zhuǎn)換字符　　void BubbleSort(char a[],int len)　　//冒泡排序，為了顯示狀態(tài)集時讓字符按升序排列　　int CheckChar(char

53、t[],char ti)　　//檢查數(shù)組t中是否有與ti相同的字符　　int CheckTable(TranMatrix TM,char str[])　　//檢查轉(zhuǎn)換矩陣的第一列中是否有與str相同的字符串　　void Smove(Graph g,char t1

54、[],char t2[],char transword)　　//№根據(jù)NFA，將t1中的狀態(tài)接受了transword后轉(zhuǎn)為對應(yīng)的t2中的狀態(tài)　　void E_Closure(Graph g,char t[])　　//進(jìn)行了Smove后的狀態(tài)集合求閉包，并將結(jié)果按升序排列<p&

55、gt;　　void Show_TranMatrix(TranMatrix TM)　　//顯示轉(zhuǎn)換矩陣　　void NFA_to_DFA(Graph g,TranMatrix TM)　　//實(shí)現(xiàn)從NFA轉(zhuǎn)換為DFA,要求輸入新狀態(tài)名稱

56、　　void Show_DFA(TranMatrix TM)　　//根據(jù)狀態(tài)轉(zhuǎn)換表顯示DFA圖　　3、程序清單　　#include <stdio.h>　　#include <stdlib.h></p

57、>　　#include <string.h>　　#define MAX 10　　#define INFINIT 32767　　#define NumMaxChar 10　　#define NumMAXTN 10

58、　　typedef struct edge　　{//邊　　int dest;　　char cost;　　struct edge *link;//指向下一邊

59、;　　}*Edge; 　　typedef struct vertex　　{//頂點(diǎn)　　char data;//狀態(tài)　　Edge adj;//邊&l

60、t;p>　　}*Vertex; 　　typedef struct graph　　{//圖　　Vertex NodeTable;　　int NumVertex;　　int MaxNumVe

61、rtex;　　int NumEdge;　　}*Graph;　　typedef struct tablenode　　{//轉(zhuǎn)換表節(jié)點(diǎn)　　char newna

62、me;//新命名　　char ch[MAX];//頂點(diǎn)集合　　}*TableNode; 　　typedef struct tablequeue　　{//轉(zhuǎn)換表列　　TableNode TN[M

63、AX];//轉(zhuǎn)換表節(jié)點(diǎn)數(shù)組　　char transword;//轉(zhuǎn)換條件　　int NumTn;//添加的頂點(diǎn)數(shù)　　}*TableQueue; 　　typedef struct transmatrix　　{//狀

64、態(tài)轉(zhuǎn)換矩陣　　TableQueue TQ;//轉(zhuǎn)換表列組　　int transnum;//轉(zhuǎn)換表列數(shù)　　}*TranMatrix; 　　int GraphEmpty(Graph g)　　{//

65、圖判空　　return g->NumVertex==0;　　} 　　int GraphFull(Graph g)　　{//判圖滿

66、　　return g->NumVertex==g->MaxNumVertex;　　} 　　char GetValue(Graph g,int i)　　{//尋找下標(biāo)為i的頂點(diǎn)　　return (i>0 &&a

67、mp; i<g->NumVertex? g->NodeTable[i].data:' ');　　}　　void Insert_Vertex(Graph g,char vertex)　　{//插入新的頂點(diǎn)&

68、lt;/p>　　g->NodeTable[g->NumVertex].data=vertex;　　g->NodeTable[g->NumVertex].adj=NULL;　　g->NumVertex++;　　} <

69、;/p>　　void Insert_Edge(Graph g,int v1,int v2,char weight)　　{//插入邊　　Edge p;　　p=(Edge)malloc(sizeof(struct

70、edge));　　p->cost=weight;　　p->dest=v2;　　p->link=g->NodeTable[v1].adj;　　g->NodeTable[v1].adj=p; <b&

71、gt;　　} 　　int GetVertexPos(Graph g,char v)　　{//得到頂點(diǎn)在圖中的下標(biāo)　　int i=0;　　while(i<g->NumVertex)

72、　　{　　if(g->NodeTable[i].data==v)　　return i;　　i++;　　}</b

73、>　　return INFINIT;　　} 　　void Construct_Graph(Graph g)　　{//創(chuàng)建圖　　int k,j,i,v

74、exn,edgen;　　char head,tail,name;　　char weight;　　g->NumVertex=0;　　g->NumEdge=0;　　g->MaxNumVertex=MAX;</p

75、>　　g->NodeTable=(Vertex)malloc((g->MaxNumVertex)*sizeof(struct vertex));　　printf("輸入NFA狀態(tài)數(shù):");　　scanf("%d",&vexn);

76、;　　printf("輸入NFA狀態(tài)名稱:\n");　　flushall();　　//依次獲取狀態(tài)名稱，并將這些頂點(diǎn)插入圖中　　for(i=0;i<vexn;i++)　　{ <

77、p>　　scanf("%c",&name);　　flushall();　　Insert_Vertex(g,name);　　}　　printf("輸入NFA的邊數(shù):");</p

78、>　　scanf("%d",&edgen);　　printf("輸入起始狀態(tài)，接受字符和到達(dá)狀態(tài):\n");　　flushall();　　//依次獲取邊的信息（起始頂點(diǎn)，接受字符，到達(dá)的頂點(diǎn)），并將這些邊插入圖中

79、　　for(i=0;i<edgen;i++)　　{ 　　flushall();　　scanf("%c %c %c",&tail,&weight,&head);

80、　　k=GetVertexPos(g,tail);　　j=GetVertexPos(g,head);　　Insert_Edge(g,k,j,weight);　　}　　} &

81、lt;p>　　void Destruct_Graph(Graph g)　　{//銷毀圖 　　int i;　　Edge p;　　for(i=0;i<

82、;g->NumVertex;i++)　　{　　p=g->NodeTable[i].adj;　　while(p!=NULL)　　{　　g->

83、;NodeTable[i].adj=p->link;　　p->link=NULL;　　free (p);　　p=g->NodeTable[i].adj;　　}

84、　　}　　g->NumEdge=0;　　g->NumVertex=0;　　printf("圖已銷毀\n");　　}&l

85、t;p>　　void Show_Graph(Graph g)　　{//顯示圖 　　int i; 　　Edge p;　　for(i=0;i<g-

86、>NumVertex;i++)　　{　　p=g->NodeTable[i].adj;　　while(p!=NULL)　　{　　printf(&

87、quot;(%c,%c):%c ",g->NodeTable[i].data,g->NodeTable[p->dest].data,p->cost);　　p=p->link;　　}　　printf("\n");&l

88、t;/p>　　}　　}　　void Init_Matrix(TranMatrix TM)　　{　　int i,j,k;</p

89、>　　printf("輸入接受字符數(shù):");　　scanf("%d",&TM->transnum);　　TM->TQ=(TableQueue)malloc((TM->transnum+1)*sizeof(struct tablequeue));

90、;　　//初始化轉(zhuǎn)換矩陣的第一列　　for(j=0;j<MAX;j++)　　{　　TM->TQ[0].TN[j]=(TableNode)malloc(sizeof(struct tablenode));

91、;　　TM->TQ[0].TN[j]->newname='\0';　　for(k=0;k<NumMaxChar;k++)　　TM->TQ[0].TN[j]->ch[k]='\0';　　}&l

92、t;p>　　TM->TQ[0].transword='I';　　TM->TQ[0].NumTn=0;　　//初始化轉(zhuǎn)換矩陣的其它列　　for(i=1;i<=TM->transnum;i++)　　{</b

93、>　　printf("輸入第%d個轉(zhuǎn)換字符:\n",i);　　flushall();　　scanf("%c",&TM->TQ[i].transword);　　for(j=0;j<MAX;j++)</p

94、>　　{ 　　TM->TQ[i].TN[j]=(TableNode)malloc(sizeof(struct tablenode));　　TM->TQ[i].TN[j]->newname='\0';　　for(

95、k=0;k<NumMaxChar;k++)　　TM->TQ[i].TN[j]->ch[k]='\0';　　}　　TM->TQ[i].NumTn=0;　　}&

96、lt;/p>　　}　　void BubbleSort(char a[],int len)　　{//冒泡排序　　int i,j;

97、char temp;　　for(i=0;i<len;i++)　　{　　for(j=0;j<len-i-1;j++)　　{　　if(a[j]&g

98、t;a[j+1])　　{　　temp=a[j+1];　　a[j+1]=a[j];　　a[j]=temp;　　}&

99、lt;b>　　}　　}　　} 　　int CheckChar(char t[],char ti)//檢查數(shù)組t中是否有與ti相同的字符　　{//0 有重復(fù)，1 無重復(fù)&l

100、t;/p>　　int i;　　for(i=0;i<NumMaxChar;i++)　　{　　if(t[i]==ti) return 0;　　}&l

101、t;/b>　　return 1;　　} 　　int CheckTable(TranMatrix TM,char str[])//檢查轉(zhuǎn)換矩陣的第一列中是否有與str相同的字符串　　{// i

102、有重復(fù)（并返回重復(fù)的位置），1 無重復(fù)　　int i;　　for(i=0;i<TM->TQ[0].NumTn;i++)　　{　　if(!strcmp(TM->TQ[0].TN[

103、i]->ch,str))　　return i;　　}　　return 1;　　} <

104、p>　　void Smove(Graph g,char t1[],char t2[],char transword)　　{//根據(jù)NFA，將t1中的狀態(tài)接受了transword后轉(zhuǎn)為對應(yīng)的t2中的狀態(tài)　　int i,j,k=0,check,len;　　Edge p;&l

105、t;/p>　　while(t2[k]!='\0') k++;　　for(i=0;i<MAX;i++)　　{　　for(j=0;j<g->NumVertex;j++)<

106、b>　　{　　if(g->NodeTable[j].data==t1[i])　　{ 　　p=g->NodeTable[j].adj;　　while(p!=NULL)<

107、p>　　{　　if(p->cost==transword)　　{ 　　check=CheckChar(t2,g->NodeTable[p->dest].data);

108、if(check==1)　　{ 　　t2[k]=g->NodeTable[p->dest].data;　　k++;　　}

109、　　p=p->link;　　}　　else　　p=p->link;　　}<b&

110、gt;　　}　　}　　}　　len=k;　　BubbleSort(t2,k);

111、　　} 　　void E_Closure(Graph g,char t[])　　{//對進(jìn)行了Smove后的狀態(tài)集合求閉包，并將結(jié)果按升序排列　　int i=0,j,k=0,check,len;　　Edge p;&

112、lt;/p>　　//找到字符數(shù)組中的最后一個字符的位置　　while(t[k]!='\0') k++;　　for(i=0;t[i]!='\0';i++)　　{ //每個頂點(diǎn)都要查看一次　　for(j=0;j&l

113、t;g->NumVertex;j++)　　{//　　if(g->NodeTable[j].data==t[i])　　{　　p=g->NodeTable[j].adj;</

114、p>　　while(p!=NULL)　　{　　if(p->cost=='*')//空輸入　　{ 　　check=CheckChar(t,g-&g

115、t;NodeTable[p->dest].data);　　if(check==1)　　{　　t[k]=g->NodeTable[p->dest].data;　　k++;</

116、p>　　} 　　}　　p=p->link;　　}　　}<

117、p>　　}　　}　　len=k;　　BubbleSort(t,k);//結(jié)果按升序排列　　} </

118、p>　　void Show_TranMatrix(TranMatrix TM)　　{　　int i,j,k;　　printf("狀態(tài)轉(zhuǎn)換矩陣:\n");　　for(j=0;j<=T

119、M->transnum;j++) 　　printf("轉(zhuǎn)換字符:%c ",TM->TQ[j].transword);　　printf("\n");　　for(k=0;k<MAX;k++)

120、　　{ 　　for(j=0;j<=TM->transnum;j++) 　　{　　if(TM->TQ[j].TN[k]->newname=='\0') printf("NULL ");</

121、p>　　else printf("%c:",TM->TQ[j].TN[k]->newname);　　for(i=0;TM->TQ[j].TN[k]->ch[i]!='\0';i++)　　{ <p&

122、gt;　　printf("%c",TM->TQ[j].TN[k]->ch[i]);　　}　　if(TM->TQ[j].TN[k]->ch[0]=='\0') printf("NULL");　　pr

123、intf("\t\t");　　}　　printf("\n");　　}　　}

124、　　void NFA_to_DFA(Graph g,TranMatrix TM)　　{　　int j=0,i,check;　　char temp[2]={'\0','\0'};　　TM->TQ[0

125、].TN[0]->ch[0]=g->NodeTable[0].data;　　for(i=1;i<=TM->transnum;i++)　　E_Closure(g,TM->TQ[0].TN[0]->ch);　　printf("輸入新狀態(tài)名:");</p&g

126、t;　　flushall();　　scanf("%c",&TM->TQ[0].TN[0]->newname);　　TM->TQ[0].NumTn++;　　while(j<TM->TQ[0].NumTn)<

127、p>　　{　　for(i=1;i<=TM->transnum;i++)　　{　　Smove(g,TM->TQ[0].TN[j]->ch,TM->TQ[i].TN[j]->ch,TM->TQ[

128、i].transword);　　E_Closure(g,TM->TQ[i].TN[j]->ch);　　if (TM->TQ[i].TN[j]->ch[0]!='\0')//如果為空則可忽略，不記入結(jié)果狀態(tài)　　{

129、　　check=CheckTable(TM,TM->TQ[i].TN[j]->ch);　　if(check==1)　　{ 　　printf("輸入新狀態(tài)名:");　　flushall(

130、);　　scanf("%c",&TM->TQ[i].TN[j]->newname);　　strcpy(TM->TQ[0].TN[TM->TQ[0].NumTn]->ch,TM->TQ[i].TN[j]->ch);　　TM->TQ[0].T

131、N[TM->TQ[0].NumTn]->newname=TM->TQ[i].TN[j]->newname;　　TM->TQ[0].NumTn++;　　}　　else TM->TQ[i].TN[j]->newname=TM->TQ

132、[0].TN[check]->newname;　　}　　}　　j++;　　}<p&g

133、t;　　} 　　void Show_DFA(TranMatrix TM)　　{　　int i,j;　　for(j=0;TM->TQ[0].TN[j]-&

134、gt;newname!='\0';j++)　　{　　for(i=1;i<=TM->transnum;i++)　　{ 　　if (TM->TQ[i].TN[j]-&

135、gt;newname!='\0')　　printf("(%c,%c,%c) ",TM->TQ[0].TN[j]->newname,TM->TQ[i].transword,TM->TQ[i].TN[j]->newname);　　}

136、　　printf("\n");　　}　　} 　　void main()　　{

137、;　　Graph g;　　TranMatrix TM;　　g=(Graph)malloc(sizeof(struct graph));　　TM=(TranMatrix)malloc(sizeof(struct transmatrix));<p&g

138、t;　　Construct_Graph(g);　　Init_Matrix(TM);　　printf("\nNFA圖:\n");　　Show_Graph(g);　　printf("\n(初始狀態(tài)):\n");&

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

編譯原理課程設(shè)計(jì)-nfa的確定化

文檔簡介

溫馨提示

最新文檔

評論

編譯原理課程設(shè)計(jì)-nfa的確定化

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載