實驗三詞法分析——有窮自動機的應用
一、 實驗目的：
一： 輸入正則文法
二：fa
1． 生成fa(dfa或nfa)
2． 執行fa，dfa（自動）；nfa（互動）
3． **nfa→dfa
二、 實驗設想：
對輸入的文法儲存並判斷是確定的有窮狀態自動機還是不確定是有窮狀態自動機，並給出標準的表示形式，若是dfa，可直接測試乙個符號串是否是文法的句子， 即能否被有窮狀態機接受，給出過程及結果；若是nfa，首先將其轉化為dfa，再測試乙個符號串是否是文法的句子，亦即是否能被dfa接受。
例如：輸入文法規則的數目：7
輸入開始狀態: s
輸入文法 z::=za z::=bb z::=aa b::=ab b::=b a::=ba a::=a
此為確定有窮狀態自動機!
dfa d=(,,m,s,)
其中m:
m(z,a)=z
m(b,b)=z
m(b,a)=a
m(a,a)=z
m(a,b)=b
m(s,b)=b
m(s,a)=a
輸入要推導的符號串:ababaa
m(s,ababaa)
=m(m(s,a),babaa)
=m(a,babaa)
=m(m(a,b),abaa)
=m(b,abaa)
=m(m(b,a),baa)
=m(a,baa)
=m(m(a,b),aa)
=m(b,aa)
=m(m(b,a),a)
=m(a,a)
=z該符號串能被有窮狀態所接受!
輸入文法規則的數目：7
輸入開始狀態: s
輸入規則:z::=ab z::=ba z::=zc a::=ba a::=a b::=ab b::=b
文法規則儲存完畢!
此為非確定有窮狀態自動機!
nfa n=(,,m,,)
其中m:
m(a,a)=$
m(a,b)=
m(a,c)=$
m(b,a)=
m(b,b)=$
m(b,c)=$
m(z,a)=$
m(z,b)=$
m(z,c)=
m(s,a)=
m(s,b)=
m(s,c)=$
將nfa轉化為dfa!
dfa n'=(,, m',[s],f')
其中m':
m'([s],b)=[b]
m'([s],a)=[a]
m'([b],a)=[az]
m'([a],b)=[bz]
m'([az],b)=[bz]
m'([az],c)=[z]
m'([bz],a)=[az]
m'([bz],c)=[z]
m'([z],c)=[z]
其中f'=
輸入要推導的字串:ababc
m'([s],ababc)
=m'(m'([s],a),babc)
=m'([a],babc)
=m'(m'([a],b),abc)
=m'([bz],abc)
=m'(m'([bz],a),bc)
=m'([az],bc)
=m'(m'([az],b),c)
=m'([bz],c)
=[z]
[z]屬於終止狀態集合!
該字串能被有窮狀態所接受!
三、 參考程式
#include<>
#include<>
struct leftitem;
struct rightnode儲存狀態轉換關係中弧與終止狀態結點結構
};struct leftitem儲存狀態轉換關係中初始狀態結點結構
;struct stateitem存放確定化的nfa狀態結點結構
};int checkstate(leftitem array,int size)
}return 1;
}int checkexist(stateitem sarray,int& length,char temp)
//將nfa確定化建立二維矩陣時判別新產生的狀態是否在狀態陣列中儲存過
i++;
}if(i>length)
else
return k;
}int getcount1(leftitem array,int size取得fa中狀態的個數
}return count;
}int getcount2(leftitem array,int size取得fa中輸入字母的個數
}return count;
}int getstate(rightnode* pnode,char arc) //判定乙個狀態是否能通過一條弧進入下一狀態
return 0;
}void sort(char a,int n將取得的新狀態進行排序
}void bianli1(leftitem array,int size輸出fa中有窮非空的狀態集合
}}void bianli2(leftitem array,int size
//輸出fa中有窮的輸入字母表
{ char temp[20];
int len=0;
int i,j;
rightnode* pnode;
for(i=0;i {
pnode=array[i].link;
實驗專案一指導上詞法分析程式的設計與實現
屬性字，結構為二元組 類別，值 typedef struct attrib words 列舉型別定義的示例 typedef enum symbol symbol 怎樣建屬性值表，怎樣查表？10,11,for 2,variable一般變數 基本功能宣告 函式1 讀程式原始檔，提取文字檔案中的資訊，結果...
頻譜分析法在單擺實驗中的應用
墅！墮 實驗室科學第 卷第 期 年 月 頻譜分析法在單擺實驗中的應用 鍾季康 上海師範大學天華學院科研處，上海 摘要 以現代化的實驗手段改造傳統實驗，給予學生豐富的綜合性實驗技能訓練，是各類實驗課程改革的 一項重要任務。作為訊號分析和基礎物理實驗相結合的乙個範例，引入感測技術和計算機技術，特別是頻譜...
1110多種地質找礦手段的綜合應用分析 3300
多種地質找礦手段的綜合應用分析 摘要 隨著科技的不斷發展，其在各個領域中的應用也更加的廣泛，特別是在地質找礦中的使用。礦物質對社會經濟的發展有著極為重要的影響，這就導致礦物質的勘測成了一項非常重要的工作，只有採用科學的方法和手段進行礦物質勘測，並找出隱藏的礦物質，國家經濟的發展才能得到保證。本文主要...