1、編譯方法實驗指導書柴本成 趙晨 編寫浙江萬里學院2010.01目 錄實驗一 有限自動機的構造與實現1實驗二 詞法分析器的設計3實驗三 語法分析遞歸下降分析器5實驗四 LL(1)文法預測分析表的實現6附 錄9附錄一 實驗結果的提交與檢查9附錄二 實驗報告參考格式9附錄三 Visual C+上機環境簡介10附錄四 參考程序13實驗一 有限自動機的構造與實現一、 實驗目的1、 正確理解正規式和正規集以及有限自動機的定義；2、 熟練掌握用狀態轉換圖表示有限自動機的方法。二、 實驗預習提示1、 正規表達式就是一種形式化的表示法，它可以表示單詞符號的結構，從而精確地定義單詞符號集。正規表達式簡稱為正規式，

2、它表示的集合即為正規集。2、 狀態轉換圖是一張當輸入不同內容時選擇不同分析路徑的有向圖。一個狀態轉換圖可用于識別一定的字符串。3、 有限自動機（FA）是更一般化的狀態轉換圖，可用來識別正規集；分為DFA和NFA兩種。三、 實驗內容構造識別如下字符串的狀態轉換圖，并將其編程實現。1、 識別標識符(以字母開始由字母和數字構成的字符串，要求長度不超過10)；參考程序：#include <iostream.h>#include <string.h>/字符串處理的頭文件/判斷一個字符是不是字母bool Isletter(char ch)if(ch>='a'

3、&& ch<='z' | ch>='A' && ch<='Z')return true;return false;/判斷一個字符是不是數字bool IsDigit(char ch)if(ch>='0' && ch<='9')return true;return false;/判斷一個字符串是不是標識符bool IsId(char *str)if(!Isletter(str0)return false;int l=strlen(str);/

4、計算字符串的長度for(int i=1;i<l;i+)if(Isletter(stri) | IsDigit(stri)continue;/如果是字母或數字就繼續循環elsereturn false;/否則，返回不是字符串return true;void main()char *str="1abc"/初始化字符串，也可鍵盤輸入if(IsId(str)cout<<"accept!"<<endl;else cout<<" not accept!"<<endl;2、 識別實數(要求正負號

5、可有可無，長度不超過20，不要求識別用科學記數法表示的實數)。3、 （選做）識別實數（包含科學計數法）。四、 實驗要求1、 編程語言可用C/C+中任意一種；2、 自行設計測試數據對程序進行測試，對輸入的字符串（以#作為結束符）如果能識別，則顯示“接受”，否則，顯示“不接受”；3、 書寫實驗報告；實驗報告的格式可參見附錄實驗報告參考格式。實驗二 詞法分析器的設計一、 實驗目的通過設計編制調試一個具體的詞法分析程序，加深對詞法分析原理的理解。并掌握在對程序設計語言源程序進行掃描過程中將其分解為各類單詞的詞法分析方法。編制一個讀單詞過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、

6、標識符、常數、運算符、分隔符五大類。并依次輸出各個單詞的內部編碼及單詞符號自身值。（遇到錯誤時可顯示“Error”，然后跳過錯誤部分繼續顯示）二、實驗預習提示1. 詞法分析器的功能和輸出格式詞法分析器的功能是輸入源程序，輸出單詞符號。詞法分析器的單詞符號常常表示成以下的二元式(單詞種別碼，單詞符號的屬性值)。本實驗中，采用的是一類符號一種別碼的方式。2. 單詞的BNF表示<標識符>-> <字母><字母數字串><字母數字串>-><字母><字母數字串>|<數字><字母數字串>|<下劃線

7、><字母數字串>|<無符號整數>-> <數字><數字串><數字串>-> <數字><數字串> |<加法運算符>-> +<減法運算符>-> -<大于關系運算符>-> ><大于等于關系運算符>-> >=3. “超前搜索”方法詞法分析時，常常會用到超前搜索方法。如當前待分析字符串為“a>+”,當前字符為>，此時，分析器到底是將其分析為大于關系運算符還是大于等于關系運算符呢？顯然，只有知道下一個字符是什么才能

8、下結論。于是分析器讀入下一個字符+，這時可知應將>解釋為大于運算符。但此時，超前讀了一個字符+，所以要回退一個字符，詞法分析器才能正常運行。在分析標識符，無符號整數等時也有類似情況。三、實驗過程和指導 （一）準備：1. 閱讀課本有關章節，花一周時間明確語言的語法，寫出基本保留字、標識符、常數、運算符、分隔符和程序例。2. 初步編制好程序。3. 準備好多組測試數據。（二）上課上機：將源代碼拷貝到機上調試，發現錯誤，再修改完善。第二次上機調試通過。（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（2，”a”

9、）（4，”=”）（3，”10”）（5，”;”）（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”“）（三）程序要求：程序輸入/輸出示例：如源程序為C語言。輸入如下一段：main()int a,b;a = 10; b = a + 20;要求輸出如右圖。具體要求如下：1. 識別保留字：if、int、for、while、do、return、break、continue等2. 其他的都識別為標識符；3. 常數為無符號整形數；4. 運算符包括：+、-、*、/、=、>、<、>=、<=、!=5. 分隔符包括：,、;、(、)（四）程序思路（僅

10、供參考）：1. 定義部分：定義常量、變量、數據結構。2. 初始化：從文件將源程序全部輸入到字符緩沖區中。3. 取單詞前：去掉多余空白。4. 取單詞后：去掉多余空白（可選，看著辦）。5. 取單詞：利用實驗一的成果讀出單詞的每一個字符，組成單詞，分析類型。（關鍵是如何判斷取單詞結束？取到的單詞是什么類型的單詞？）6. 顯示結果。（五）練習該實驗的目的和思路：程序開始變得復雜起來，可能是大家以前編過的程序中最復雜的，但相對于以后的程序來說還是簡單的。因此要認真把握這個過渡期的練習。程序規模大概為200行。本實驗和以后的實驗相關。通過練習，掌握對字符進行靈活處理的方法。（六）為了能設計好程序，注意以下

11、事情：1. 模塊設計：將程序分成合理的多個模塊（函數），每個模塊做具體的同一事情。2. 寫出（畫出）設計方案：模塊關系簡圖、流程圖、全局變量、函數接口等。3. 編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。三、上交：1. 程序源代碼（通過網絡提交），詳細提交方式見附錄。2. 已經測試通過的測試數據3組（全部存在一個文本文件中通過網絡提交，以“第一組輸入/輸出/第二組輸入/輸出/第三組輸入/輸出”的順序存放）；3. 實驗報告：參考格式見附錄實驗三 語法分析遞歸下降分析器一、 實驗目的通過完成語法分析遞歸下降分析器的程序，了解語法分析之一遞歸下降分析法的過程和作用。為每個非終結符設計一

12、個識別的子程序，尋找該非終結符也就是調用相應的子程序。由于單詞在語法分析中作為一個整體，故在語法識別中僅使用其內碼。在這里將詞法分析作為語法分析的一個子程序，當語法分析需要單詞時，就調用相應的詞法分析程序獲得一個單詞。語法分析的作用是識別輸入符號串是否是文法上定義的句子，即判斷輸入符號串是否是滿足“程序”定義的要求。也就是當語法識別程序從正常退出表示輸入符號串是正確的“程序”；若從出錯退出，則輸入符號串不是正確的“程序”。出錯時，可以根據讀字符的位置判斷出錯的位置。二、實驗預習提示在不含左遞歸和每個非終結符的所有候選終結首符集都兩兩不相交的條件下，通過構造一個不帶回溯的自上而下的分析程序，這個

13、分析程序是由一組遞歸過程（或函數）組成，每個過程（或函數）對應文法的一個非終結符。對于文法：三、實驗內容設計對應該文法的遞歸下降分析器（參考教材P46的代碼），并將遞歸函數的調用棧的形式模擬來分析輸入串 的語法分析過程；在此，“”為輸入串的分隔符。進行語法分析時，首先將“”和文法開始符號E壓入棧終，當語法分析進行到棧中僅剩“”而輸入串掃描指針已指向輸入串尾部的“”時，則語法分析成功，分析過程參見教材圖312所示。實驗四 LL(1)文法預測分析表的實現一、實驗目的 通過本次實驗，使學生對自頂向下語法分析的基本概念、基本原理、基本方法等充分理解并掌握預測分析方法。二、實驗主要內容 1. 給定無左遞

14、歸和無回溯的文法，計算FIRST集合和FOLLOW集合，并構造出預測分析表。文法如下：（在這里用e來表示空串）E->TAA->+TAA->eT->FBB->*FBB->eF->(E)F->i2. 根據預測分析表，判斷該文法是否為LL(1)文法。三、實驗過程和指導對給定的無左遞歸和無回溯的上下文無關文法，按以下步驟執行：1. 構造First集合對文法中的每一個非終結符X構造FIRST(X)，其方法是連續使用下述規則，直到每個集合的FIRST不再增大為止。(注：對終結符a而言，FIRST(a)=a，因而無需構造。)1) 若有產生式Xa，且aVT ，則

15、把a加入到FIRST(X)中；若存在X，則將也加入到FIRST(X)中。2) 若有XY，且YVN，則將FIRST(Y)中的所有非元素(記為“”)都加入到FIRST(X)中；若有XY1Y2Yk，且Y1Yi1都是非終結符，而Y1Yi1的候選式都有存在，則把FIRST(Yj)的所有非元素都加入到FIRST(X)中(j=1,2,i)；特別是當Y1Yk均含有產生式時，應把也加到FIRST(X)中。2. 構造FOLLOW集合對文法GS的每個非終結符A構造FOLLOW(A)的方法是連續使用下述規則，直到每個FOLLOW不再增大為止。1) 對文法開始符號S，置#于FOLLOW(S)中(由語句括號“#S#”中的

16、S#得到)。2) 若有AB(可為空)，則將FIRST()加入到FOLLOW(B)中。3) 若有AB或AB，且(即FIRST()，則把FOLLOW(A)加到FOLLOW(B)中(此處的也可為空)。 3. 構造預測分析表M1) 對文法GS的每個產生式A執行以下2)、3)步。2) 對每個終結符aFIRST(A)，把A加入到MA,a中，其中為含有首字符a的候選式或為惟一的候選式。3) 若FIRST(A),則對任何屬于FOLLOW(A)的終結符b，將A加入到MA,b中。4) 把所有無定義的MA,a標記為“出錯”。 4. 判斷該文法是否為LL(1)文法若預測分析表M無多重定義，則該文法為LL(1)文法；否

17、則，該文法不是LL(1)文法。四、實驗提示1. 為了簡化實驗過程，我們這里假定要分析的文法都是無左遞歸的；即我們編程序時無需考慮文法是否左遞歸了。下面給出文法結構體和文法符號集合的程序定義#define MAX_GRAM_LEN 255/文法符號的最大長度#define MAX_ELE_NUM 40/文法符號的最大個數#define MAX_GRAM_ELE_NUM 300/所有文法符號的個數/-定義文法結構體 -typedef structchar mSetenceMAX_GRAM_LEN;grammerElement;grammerElement GrammerSetMAX_GRAM_EL

18、E_NUM;/定義文法符號的結構體typedef structint len;char eleMAX_ELE_NUM;simpleGroup;simpleGroup groupFirstMAX_ELE_NUM;/ First集simpleGroup groupFollowMAX_ELE_NUM;/ Follow集int grammerNum;/文法符號個數char VTSetMAX_ELE_NUM;/ 終結符char VNSetMAX_ELE_NUM;/ 非終結符int VNProduceZMAX_ELE_NUM;/ 產生式int vtSetLen;/終結符的個數int vnSetLen;/非

19、終結符的個數char startedSign;/開始符號2. 為了便于分析程序，在實驗中要求把分析的文法保存在一個文本文件中，同時輸出的結果也保存在一個文本文件中。3. 在附錄中，我們給出了求First集的參考程序。大家可以參考該程序，并在此基礎上寫出求Follow集以及構造分析表的程序。附 錄附錄一 實驗結果的提交與檢查1. 提交實驗結果每個實驗的結果包括兩項：實驗報告和程序源代碼。實驗報告中請寫明姓名、班號、學號、Email等個人信息，以便遇到問題時老師可以及時與你聯系。實驗報告的格式可參見實驗報告參考格式，也可自行擬定報告的格式，但要求實驗報告中至少包含如下內容：實驗題目及內容，所用的狀

20、態轉換圖，主要數據結構的設計，重要算法的流程，關鍵的代碼段及注釋，所用的測試數據及測試結果，以及實驗中遇到的問題和解決方法。請把實驗的結果放入一個目錄中，并將上述所有的文件打包成rar文件，文件名為“自己的學號.rar”，例如“01001.zip”，通過ftp或Email提交。2. 檢查方式與評分標準在大家提交實驗后，我們將對提交的程序進行測試。評分的主要標準是實驗報告以及程序輸出與標準輸出相符合的程度。附錄二 實驗報告參考格式以實驗二（詞法分析器的設計為例），實驗報告格式如下：一、實驗目的與任務編制一個讀單詞過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標識符、常數、運

21、算符、分隔符五大類。并依次輸出各個單詞的內部編碼及單詞符號自身值。（遇到錯誤時可顯示“Error”，然后跳過錯誤部分繼續顯示）二、實驗步驟1. 仔細閱讀實驗要求和書上的相關內容，寫出基本保留字、標識符、常數、運算符、分隔符和要測試的程序例。（在這里寫出基本保留字、標識符、常數、運算符、分隔符和要測試的程序實例）2. 程序的功能描述。（在這里描述你的程序的功能）3. 程序的模塊描述。（在這里寫出：重要的全局變量及其用途，主要函數的定義、功能、參數與返回值的含義）4. 關鍵程序代碼（在這里寫出：實驗中關鍵的程序代碼，不用把所有代碼都寫上）三、實驗總結（可以從以下幾個方面來總結：你在編程過程中花時多

22、少？時間是怎么分配的？多少時間在思考問題？遇到了哪些難題？你是怎么克服的？你對你的程序的評價？你的收獲有哪些？）附錄三 Visual C+上機環境簡介上機實驗環境亦可選擇Microsoft Visual C+（以下簡稱VC）。VC是美國微軟公司生產的基于其Windows系統的軟件開發工具。它具有使用靈活，并與32位Windows內核（使用于Windows 2000/Windows XP）高度兼容的特點，從而被Windows程序員們廣泛使用。同時，VC同樣可以加工處理C語言程序，與標準的ANSI C語言兼容。VC提供了一種控制臺操作方式，初學者使用它應該從這里開始。下面我們將對使用VC編寫簡單的

23、控制臺程序作一個最初步的介紹。一、控制臺程序簡介Win32控制臺程序(Win32 Console Application)是一類Windows程序，它不使用復雜的圖形用戶界面，程序與用戶交互時通過一個標準的正文窗口，通過幾個標準的輸入輸出流（I/O Streams）進行。它們分別是stdin（標準輸入），stdout（標準輸出）以及stderr（標準錯誤輸出）。這些流都是ANSI C語言標準庫提供的，通過printf()等函數可以訪問這些流。一個最簡單的控制臺程序如下：/* hello.c */#include<stdio.h>/* 包含使用標準輸入輸出的頭文件聲明 */int m

24、ain()/* 主函數 */    printf(“Hello, World!n”);/* 向標準輸出stdout輸出一個字符串 */    return 0;/* 主函數返回 */該程序的運行結果如圖3-4所示。  圖3-4 控制臺程序運行結果圖中顯示的黑色窗口稱為控制臺窗口，程序的輸入、輸出均在這個窗口中進行。二、使用VC編寫控制臺程序很簡單，只需要按照下面幾個步驟進行：1. 打開MSVC集成開發環境。雙擊桌面或“開始”菜單中的Microsoft Visual C+6.0，不久將看到VC的編輯窗口，如圖3-5：圖3-5

25、VC啟動界面2. 選擇菜單“File | New”,在彈出的對話框中 1) 單擊上方的選項卡“File”，2) 選擇“C+ Source File”， 3) 在“File name”一欄中填寫文件名例如hello.c，4) 在“Location”一欄中填寫你想把文件存放的位置（目錄）。然后按“OK”。見圖3-6。 注意： 第3）步中一定寫明擴展名“.c”（不要用“.cpp”。那樣VC將按C+的方式編譯，C+與C有一些的不兼容性）； 第4）步中指定你自己的目錄，不要使用系統的缺省目錄或者隨便放在根目錄或者其他的目錄下。 圖3-6 應用程序向導主界面3. 在右側的窗口中鍵入程序的內容，然后點擊圖標

26、存盤。進入VC編輯界面，如圖3-7。圖3-7 VC編輯界面4. 試編譯。點擊圖標，或者選擇菜單“Build | Build”（啟動程序加工，這樣系統將連續進行編譯和連接操作。另一種更穩妥的方式是先做編譯，檢查無誤后再做連接）。這時VC將彈出一個對話窗口，說明這個命令需要一個工程（Project），問：是否創建一個默認的工程？點擊“Yes”。如圖3-8所示。 圖3-8 是否創建一個工程5. 編輯器中編譯窗口開始顯示編譯的結果。如果顯示“hello.exe - 0 error(s), 0 warning(s)”， 則表示編譯已經通過！ 6. 點擊快捷工具欄上的紅色的感嘆號（或者選擇菜單“Build

27、 | Execute”或按Ctrl-F5），查看運行結果（VC將自動打開一個顯示結果的窗口，如上圖3-4所示）。   三、如何調試程序利用VC編寫程序，還需要學會如何調試程序。我們都會發現，在編寫較長的程序時，能夠一次成功而不含有任何錯誤決非易事（當然，鼓勵同學們以此為目標，進行長期大量的練習）。對于程序中的錯誤，VC提供了易用且有效的調試手段。在工具欄上單擊鼠標右鍵，在彈出的菜單中對“Debug”項打勾，發現如圖3-9所示的許多按鈕。其中，較常用的工具有：單步跟蹤進入子函數（Step Into），單步跟蹤跳過子函數（Step Over），運行至當前函數的末尾（Step Out）以及

28、觀察變量的值（Watch）等，這些VC中常用的調試功能詳見有關參考文獻。圖3-9 VC調試工具條附錄四 參考程序1.詞法分析器的設計-參考程序/*cifa fenxi chengxu*/#include <stdio.h>#include "stdlib.h"#include <string.h>#define N 100/定義要分析的標識符或常數的最大個數#define M 20/標識符的長度char *sourceFile="1.txt"/定義進行詞法分析的源文件char *key8="if","

29、else","for","while","do","return","break","continue"/關鍵字char *border6=",","","","","(",")"/界符定義char *arithmetic4="+","-","*","/"/算術運算符定

30、義char *relation6="<","<=","=",">",">=","<>" /關系運算符定義char *constsN;/常數定義char *labelN;/標識符int constnum=0,labelnum=0;/constnum-常數個數;labelnum-標識符個數/判斷一個字符是不是字母int Isletter(char ch)if(ch>='a' && ch<='z

31、' | ch>='A' && ch<='Z')return 1;return 0;/判斷一個字符是不是數字int IsDigit(char ch)if(ch>='0' && ch<='9')return 1;return 0;/判斷單詞符號類型int search(char searchchar,int wordtype)int i=0;switch (wordtype) case 1:for (i=0;i<=7;i+) if (strcmp(keyi,sear

32、chchar)=0)/返回具體的關鍵字 return(i+1); case 2:for (i=0;i<=5;i+) if (strcmp(borderi,searchchar)=0)/返回具體的界符 return(i+1); return(0); case 3:for (i=0;i<=3;i+) if (strcmp(arithmetici,searchchar)=0)/返回具體的算術運算符 return(i+1); return(0); case 4:for (i=0;i<=5;i+) if (strcmp(relationi,searchchar)=0)/返回具體的關系運

33、算符 return(i+1); return(0); case 5:for (i=0;i<=constnum;i+) if (strcmp(constsi,searchchar)=0)/返回具體的整型常數 return(i+1); constsi-1=(char *)malloc(sizeof(searchchar);strcpy(constsi-1,searchchar);constnum+;return(i); case 6:for (i=0;i<labelnum;i+) if(labeli!=NULL) if (strcmp(labeli,searchchar)=0)/返回標

34、識符 return(i+1); labeli-1=(char *)malloc(sizeof(searchchar);strcpy(labeli-1,searchchar);labelnum+;return(i); return -1;/標識符或關鍵字char alphaprocess(char buffer,FILE* fp)int atype;int i=-1;char alphatpM;while (Isletter(buffer)|(IsDigit(buffer)alphatp+i=buffer;buffer=fgetc(fp);alphatpi+1='0'if (at

35、ype=search(alphatp,1)/輸出關鍵字printf("%s (1,%d)n",alphatp,atype-1);elseatype=search(alphatp,6);/輸出標識符printf("%s (6,%d)n",alphatp,atype-1);return(buffer);/常數處理char digitprocess(char buffer,FILE* fp)int i=-1;char digittpM;int dtype;while (IsDigit(buffer)digittp+i=buffer;buffer=fgetc(f

36、p);digittpi+1='0'dtype=search(digittp,5);/輸出整型常數printf("%s (5,%d)n",digittp,dtype-1);return(buffer);/其它處理(運算符,界符等)char otherprocess(char buffer,FILE* fp)int i=-1;char othertpM;int otype,otypetp;othertp0=buffer;othertp1='0'if (otype=search(othertp,3)printf("%s (3,%d)n&q

37、uot;,othertp,otype-1);buffer=fgetc(fp);goto out;if (otype=search(othertp,4)buffer=fgetc(fp);othertp1=buffer;othertp2='0'if (otypetp=search(othertp,4)printf("%s (4,%d)n",othertp,otypetp-1);goto out;elseothertp1='0'printf("%s (4,%d)n",othertp,otype-1);goto out;if (b

38、uffer=':')buffer=fgetc(fp);if (buffer='=')printf(":= (2,2)n");buffer=fgetc(fp);goto out; else if (otype=search(othertp,2) printf("%s (2,%d)n",othertp,otype-1); buffer=fgetc(fp); goto out; if (buffer!='n')&&(buffer!=' ') printf("%c erro

39、r,not a wordn",buffer); buffer=fgetc(fp);out: return(buffer);void main()int i;FILE *fp;/文件指針,指向要分析的源程序char cbuffer;/保存最新讀入的字符for (i=0;i<=N;i+)labeli=NULL;/初始化標識符constsi=NULL;/初始化常數;if (fp=fopen(sourceFile,"rb")=NULL)/判斷源文件是否存在printf("文件%s不存在",sourceFile);elsecbuffer = fge

40、tc(fp);/讀入字符while (cbuffer!=EOF)/如果文件沒有結束,就一直循環if (Isletter(cbuffer)/若為字母cbuffer=alphaprocess(cbuffer,fp);else if (IsDigit(cbuffer)/若為數字cbuffer=digitprocess(cbuffer,fp);else cbuffer=otherprocess(cbuffer,fp);printf("overn");getchar();2. LL(1)文法預測分析表的實現-參考程序/*程序說明*grammer.txt用于輸入相應的文法，第一行字母表

41、示起始字符。*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_GRAM_LEN 255/文法符號的最大長度#define MAX_ELE_NUM 40/文法符號的最大個數#define MAX_GRAM_ELE_NUM 300/所有文法符號的個數/-文件指針-FILE* grammerFile;char* grammerFileName="grammer.txt"/輸入文法文件FILE* testFile;char* testFileName=&qu

42、ot;outputData.txt"/輸出文件/-文法結構體 -typedef structchar mSetenceMAX_GRAM_LEN;grammerElement;grammerElement GrammerSetMAX_GRAM_ELE_NUM;typedef structint len;char eleMAX_ELE_NUM;simpleGroup;simpleGroup groupFirstMAX_ELE_NUM;/ First集simpleGroup groupFollowMAX_ELE_NUM;/ Follow集int grammerNum;/文法符號個數char

43、 VTSetMAX_ELE_NUM;/ 終結符char VNSetMAX_ELE_NUM;/ 非終結符int VNProduceZMAX_ELE_NUM;/ 產生式int vtSetLen;int vnSetLen;char startedSign;/開始符號voidreadInGrammer();void cal_first_set();/計算First集void main()/首先讀入文法文件if(grammerFile=fopen(grammerFileName,"rb")=NULL)printf("open file:grammerFile error.n

44、");return;if(testFile=fopen(testFileName,"wb")=NULL)printf("open file:testFile error.n");return;readInGrammer();/計算First集,Follow集cal_first_set();/GrammerSetcal_follow_set();/GrammerSetfclose(grammerFile);fclose(testFile);getchar();/從文件中讀入文法void readInGrammer()char tmpChar;ch

45、ar tmpStrMAX_GRAM_LEN;int tmpIndex;int vtIndex,vnIndex;int i,j;tmpIndex=0;vtIndex=0;vnIndex=0;fscanf(grammerFile,"%crn",&startedSign);while(!feof(grammerFile)if(fscanf(grammerFile,"%c->%srn",&tmpChar,&tmpStr)!=2)break;GrammerSettmpIndex.mSetence0=tmpChar;GrammerSet

46、tmpIndex.mSetence1='0'strcat(GrammerSettmpIndex.mSetence,tmpStr);tmpIndex+;for(i=0;i<vnIndex;i+)if(tmpChar=VNSeti)break;if(i=vnIndex)/新的文法符號;VNSetvnIndex=tmpChar;vnIndex+;i=0;while(tmpStri!='0')if(!(tmpStri>=65&&tmpStri<=90)/不是大寫字母(不是非終結符)for(j=0;j<vtIndex;j+)if(t

47、mpStri=VTSetj)break;if(j=vtIndex) /新的文法符號VTSetvtIndex=tmpStri;vtIndex+;i+;VTSetvtIndex='0'VNSetvnIndex='0'vtSetLen=vtIndex;vnSetLen=vnIndex;grammerNum=tmpIndex;/計算First集合void cal_first_set()int i,j,k;int* relationMatrix;int matrixSize;int vnIndex;int rowIndex,colIndex;matrixSize=vnSe

48、tLen+vtSetLen;relationMatrix=(int*)malloc(sizeof(int*)*matrixSize);for(i=0;i<matrixSize;i+)relationMatrixi=(int*)malloc(sizeof(int)*matrixSize);if(relationMatrix=NULL)printf("in cal_first_set,mem apply failure.n");return;for(i=0;i<matrixSize;i+)for(j=0;j<matrixSize;j+)relationMatrixij=0;/創建一個圖vnIndex=0;for(i=0;i<grammerNum;i+)if(GrammerSeti.mSetence0!=VNSetvnIndex)vnIndex+;j=1;while(GrammerSeti.mSetencej!='0')/A->Beta , Beta是非終結符if(GrammerSeti.mSetencej>=65&&GrammerSeti.mSetencej<=90)for(k=0;k<vnSetLen;k+)/找到相應的非終結符if(VNSetk=Gramme