1、實驗一（一）程序設計語言及其編譯器實現概覽（2小時）實驗目的：學習一門簡單的程序設計語言的定義及其編譯器實現實驗任務：針對一門簡單的程序設計語言，閱讀其定義文檔，初步了解其編譯器的源代碼。實驗內容：（1）選擇一門語言：TINY或其它語言也可（需自備其編譯器的源代碼）。（2）閱讀其定義文檔，了解語言定義的方法，包括：詞法、語法、語義、運行時環境、目標機器、目標語言等內容。（3）了解其編譯器源代碼。· 對TINY語言編譯器，其源代碼由多個文件組成，請弄清楚每個文件的作用是什么。詳情請見編譯原理及實踐第1.7節。請做一個C+工程文件（Win32 Console Application, t

2、iny.dsp），把它們組織起來，然后編譯成可執行文件(tiny.exe)，即為TINY語言編譯器。然后用它編譯TINY語言示例源代碼(sample.tny)。看看編譯生成的目標文件(sample.tm)是怎樣的。要運行目標程序，還需要一個虛擬機，名為TM機。TM機是以軟件形式存在的，其源代碼為tm.c，需要編譯生成可執行文件tm.exe。然后將目標程序作為TM機的輸入運行TM機即可得到所期待的結果。要求讀懂main.c、globals.h、util.h、scan.h和util.c、scan.c等文件，三人一組進行討論，給每一行加上注釋，總結你們各自對程序的理解和閱讀程序的收獲，每組提交1份加

3、了注釋的文件和心得。有能力的同學可加上tm.c。實驗一（二）DFA的編程實現（2小時）實驗目的：通過本次實驗，加深對DFA及其識別的語言的理解，學習對一般的DFA的表達方法與編程實現方法。實驗任務：編寫一個C語言程序，模擬實現DFA識別字符串的過程。實驗內容：（1）DFA的輸入；（2）DFA的存儲與讀寫；（3）DFA的正確性檢查；（4）DFA的語言集列表顯示；（5）DFA的規則字符串判定；內容說明：（1）DFA的輸入：分別輸入DFA的“字符集”、“狀態集”、“開始狀態”、“接受狀態集”、“狀態轉換表”等內容，并保存在設定的變量中。（2）DFA的存儲與讀寫：將上述DFA的五元組保存在一個文本文件

4、中，擴展名指定為.dfa。請自行設計DFA文件的存儲格式，并說明其含義。能將保存在內存變量中的DFA寫入DFA文件，也能將DFA文件讀入內存中。（思考：對稀疏DFA（轉換表中為空的地方較多）或用“或”表達轉換的DFA（如下的測試用例三），如何改進DFA轉換表的表達。）（3）DFA的正確性檢查：檢查所有集合的元素的唯一性。檢查“開始狀態”是否唯一，并是否包含在“狀態集”中。檢查“接受狀態集”是否為空，并是否包含在“狀態集”中。檢查“狀態轉換表”是否滿足DFA的要求。檢查“狀態轉換表”并非填滿時的處理是否得當（4）DFA的語言集列表顯示：輸入待顯示的字符串的最大長度N，輸出以上定義的DFA的語言集

5、中長度N的所有規則字符串。（提示：注意算法中while循環的次數）（5）DFA的規則字符串判定：輸入（或用字符集隨機生成）一個字符串，模擬DFA識別字符串的過程判定該字符串是否是規則字符串（屬于DFA的語言集）。測試用例：DFA（一）DFA（二）DFA（三）實驗要求：按照編譯原理及實踐參考書第二章中描述的“while循環+雙層case選擇”的算法編程實現一般的DFA。要求能通過以上三個測試用例的測試。完成內容中（1）（5）部分，可得C。完成內容中（1）（2）（5）部分，可得B。完成內容中（1）（2）（4）（5）部分，可得A。完成全部內容，可得獎勵。判定算法概要：準備：開始狀態s0, 接受狀態集

6、F, 狀態轉換表T(s, c), sÎS, cÎSc = getchar();s = 開始狀態s0;while ( c != EOF ) / 輸入未結束則循環s = T(s, c);if (s = NULL) error();c = getchar();if (s Î 接受狀態集F) accept ();else error ();通用DFA存儲格式的建議：（用以上的第三個測試DFA為例）3 / 字符集中的字符個數 (以下兩行也可合并成一行)/ * o / 以空格分隔的字符集。O代表任意非/和*的字符5 / 狀態個數 (以下兩行也可合并成一行)1 2 3 4 5

7、/ 狀態編號。若約定總是用從1開始的連續數字表示，則此行可省略1 / 開始狀態的編號。若約定為1，則此行可省略1 / 結束狀態個數。若約定為1，則此行可省略5 / 結束狀態的編號2 -1 -1 / 狀態1的所有出去的轉換。按字符集中的字符順序給出。-1表示出錯狀態-1 3 -13 4 35 4 3-1 -1 -1實驗報告：同時上交紙質報告與電子版報告。紙質報告以實驗分析、實驗中遇到的問題及解決方法、實驗測試（含屏幕截圖）、實驗心得等為主，不得大量引用源程序（引用源程序總行數不得超過100行）。電子版報告以源程序、測試用例、輸出文件等為主，包括紙質報告的電子版，須確保提并的源程序能編譯運行，否則

8、不要上交。電子版請發送到248133074，郵件標題請寫明學號、姓名與實驗編號，形如：<實驗一> <學號> <姓名>。不得抄襲實驗報告與源程序，否則后果自負！提高內容：（1）圖形化的用戶界面；（2）任意DFA的狀態轉換圖、狀態轉換表的圖形繪制；附實驗報告 源碼實驗一DFA的編程實現實驗目的：通過本次實驗，加深對DFA及其識別的語言的理解，學習對一般的DFA的表達方法與編程實現方法。實驗任務：編寫一個C語言程序，模擬實現DFA識別字符串的過程。實驗內容：（1）DFA的輸入；（2）DFA的存儲與讀寫；（3）DFA的正確性檢查；（4）DFA的語言集列表顯示；（5）

9、DFA的規則字符串判定；實驗分析：DFA的初始化一個DFA的基本信息 狀態集、字符集、開始狀態、結束狀態集、狀態轉換表；在程序中狀態集、字符集、開始狀態、結束狀態集都用string類型來表示，即可不用考慮用戶輸入內容的長度。但缺點是字符集只能是字符而不可以是字符串。狀態轉換表：為三個字符的字符串，第一個為當前狀態，第二個為輸入字符，第三個為下一狀態。 用vector容器存放轉換函數的內容字符串判斷初始化一個DFA，后可以通過一下算法判斷一個字符串是否符合該DFA。判定算法概要：準備：開始狀態s0, 接受狀態集F, 狀態轉換表T(s, c), sÎS, cÎSc = getc

10、har();s = 開始狀態s0;while ( c != EOF ) / 輸入未結束則循環s = T(s, c);if (s = NULL) error();c = getchar();if (s Î 接受狀態集F) accept ();elseerror ();在實際編寫代碼中的體現為void identify()/判斷字符串cout<<"請輸入字符串"<<endl;string str;cin>>str;int i=0;char present=StartStates;while(i<str.length()pres

11、ent=move(present,stri);/move函數即去遍歷轉換表，返回下個狀態if(present='N')/ N 即為move返回錯誤的狀態，break;i+;if(FinalStates.find(present)!=FinalStates.npos)/如果返回的狀態用find函數 屬于最終狀態集則表示識別cout<<"該自動機識別此字符串"<<endl;elsecout<<"該自動機不識別此字符串"<<endl;對DFA的存儲與讀寫將DNF的信息寫入文件中，第一行：字符集；第

12、二行：狀態集;第三行：開始狀態；第四行：結束狀態集；以下行寫入狀態轉換表按照既定的規定讀取文件中的數據將其賦值，然后初始化DFA即可；DFA的語言集列表顯示：這一個模塊應該是這個實驗中比較難的一部分了。我并沒有使用while循環的這個做法。而是用函數遞歸，通過所有字符集的路徑去遍歷整個DFA。最后將符合條件的字符串輸出；void Traversal(char present, int N,string strass="")/遍歷DFA的語言集列表if(present='N'|N<0)/若路徑已經大于N或者當前狀態錯誤，停止遞歸return;N-;if(

13、FinalStates.find(present)!=FinalStates.npos)cout<<"該自動機識別字符串:"<<strass<<endl;for(int i=0;i<Alphabet.length();i+)string temp;temp=strass;strass+=Alphabeti;Traversal(move(present,Alphabeti),N,strass);strass=temp;遞歸終止條件的判斷。當N- 時， N小于0，或者遍歷到無路可走是便終止遇到的問題:對于遞歸的終止條件寫得不夠明確。 遞

14、歸前對字符串賦值strass賦值，遞歸后應該還原，這一點沒有想到。調試了很久。 總結，對遞歸的具體編寫 還是不熟悉。目前的代碼，字符集和狀態只能是一個字符，若要優化可以用vector<string>容器存儲即可；實驗用例：實驗結果：DFA的初始化判斷字符串：顯示小于N的語言集：讀取DFA文件：實驗總結：在這次實驗中，學習對一般的DFA的表達方法與編程實現方法。對課本提供的算法有了更深刻的認識。在編寫和調試代碼的過程中對自身的編程能力也有了很大的提高。對自動機和其識別語言有了更透徹的理解。在動手編程之前一定要好好明確實驗的理論準備和思路的理清，能幫助我們在實驗過程中少走更多的彎路?？?/p>

15、之在這次實驗中收獲很多，提高了動手能力和分析問題的能力。源代碼：/構造一個DFA#include<iostream>#include<string>#include<vector>#include<fstream>using namespace std;class TransitionTablepublic:char present;/當前狀態char next;/下一狀態char input;/輸入字符TransitionTable(char P,char I,char D)present=P;next=D;input=I;class DFAp

16、ublic:DFA()cout<<"1、手動輸入，2、讀取txt文件"<<endl;int select;cin>>select;if(select=1)inti();if(select=2)read();string States;/狀態集char StartStates;/開始狀態string FinalStates;/結束狀態集string Alphabet;/字符集vector<TransitionTable> Trans; /轉換函數void inti()/初始化自動機cout<<"請輸入有限狀

17、態集S："<<endl;cin>>States;cout<<"請輸入字符集A："<<endl;cin>>Alphabet;cout<<"請輸入轉換函數MOVE -格式為：當前狀態-輸入字符-下一狀態：(輸入#結束輸入)"<<endl;int j=0;while(true)char input4;cin>>input;if(strcmp(input,"#")=0)break;TransitionTable Temp(input0,i

18、nput1,input2);Trans.push_back(Temp);cout<<"請輸入開始狀態集S0："<<endl;cin>>StartStates;cout<<"請輸入結束狀態集F："<<endl;cin>>FinalStates;void identify()/識別字符串 cout<<"請輸入字符串："<<endl;string str;cin>>str;int i=0;char present=StartState

19、s;while(i<str.length()present=move(present,stri);/move函數即去遍歷轉換表，返回下個狀態if(present='N')/ N 即為move返回錯誤的狀態，break;i+;if(FinalStates.find(present)!=FinalStates.npos)/如果返回的狀態用find函數 屬于最終狀態集則表示識別cout<<"該自動機識別此字符串"<<endl;elsecout<<"該自動機不識別此字符串"<<endl;cha

20、r move(char P,char I)/move 轉換函數for(int i=0;i<Trans.size();i+)if(Transi.present=P&&Transi.input=I)return Transi.next;return 'N'void read()/從txt文件中讀取DNF的信息char temp10;fstream ff("DNF.txt",ios:in);ff.getline(temp,10);Alphabet=temp;ff.getline(temp,10);States=temp;ff.getline(

21、temp,10);StartStates=temp0;ff.getline(temp,10);FinalStates=temp0;while(!ff.eof()ff.getline(temp,10);TransitionTable Temp(temp0,temp1,temp2);Trans.push_back(Temp);/*將DNF的信息寫入文件中，第一行：字符集；第二行：狀態集;第三行：開始狀態；第四行：結束狀態集；以下行寫入狀態轉換表*/void write()fstream ff("DNF.txt",ios:out);ff<<Alphabet<<endl;ff<<States<<endl;ff<<StartStates<<endl;ff<<FinalStates<<endl;for(int i=0;i<Trans.size();i+)ff<<Transi.present<<Transi.input<<Transi.next<<endl;