語(yǔ)法分析器實(shí)驗(yàn)報(bào)告(可運(yùn)行)

1、大學(xué)XX系實(shí)驗(yàn)報(bào)告XX至XX學(xué)年第X學(xué)期課程名稱(chēng)編譯原理學(xué)號(hào)XXX學(xué)生姓名XXX年級(jí)XXX級(jí)專(zhuān)業(yè)XXX教學(xué)班號(hào)XXX實(shí)驗(yàn)地點(diǎn)XXX實(shí)驗(yàn)時(shí)間XXXX主講教師XXX輔導(dǎo)教師.實(shí)驗(yàn)（二）實(shí)驗(yàn)名稱(chēng)軟件環(huán)境語(yǔ)法分析Windows xpVC+P4硬件環(huán)境實(shí)驗(yàn)?zāi)康囊?、?shí)驗(yàn)?zāi)康模焊鶕?jù)某一文法編制調(diào)試 LL（1）分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次實(shí)驗(yàn)的目的主要是加深對(duì)預(yù)測(cè)分析 LL（1）分析法的理解。二 實(shí)驗(yàn)要求 :LL （ 1）分析法的前提 : 改造文法 : 消除二義性 , 消除左遞歸 , 提取左因子 .設(shè)計(jì)出模塊結(jié)構(gòu) , 測(cè)試數(shù)據(jù) , 初步編制好程序程序要求 : 生成 LL（ 1）分析表 : 程

2、序輸入輸出示例 : 對(duì)文法用 LL（1）分析法對(duì)任意輸入的符號(hào)串進(jìn)行分析 , 輸出的格式如下 : (1)LL （ 1）分析程序，編制人：姓名，學(xué)號(hào)，班級(jí)輸入以 #結(jié)束的符號(hào)串 ( 包括 + */ （） i#) ：在此位置輸入符號(hào)串輸出過(guò)程如下：步驟分析棧剩余輸入串所用產(chǎn)生式1Ei+i*i#E TG輸入符號(hào)串為非法符號(hào)串 ( 或者為合法符號(hào)串 )4. 模塊結(jié)構(gòu) :（1）定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。（2）初始化：設(shè)立 LL(1) 分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時(shí)變量等）；（3）控制部分：從鍵盤(pán)輸入一個(gè)表達(dá)式符號(hào)串；（4）利用 LL(1) 分析算法進(jìn)行表達(dá)式處理：根據(jù) L

3、L(1) 分析表對(duì)表達(dá)式符號(hào)串進(jìn)行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯(cuò)誤則顯示錯(cuò)誤信息。實(shí)驗(yàn)內(nèi)容（應(yīng)包括實(shí)驗(yàn)題目、實(shí)驗(yàn)要求、實(shí)驗(yàn)任務(wù)等）.功能描述 :LL（ 1）分析法是一種不帶回溯的非遞歸的自上而下的分析法. 其基本思想是根據(jù)輸入串的當(dāng)前輸入符號(hào)來(lái)唯一確定選用某條規(guī)則來(lái)進(jìn)行推倒, 當(dāng)這個(gè)輸入符號(hào)與推倒的第一個(gè)符號(hào)相同時(shí)再取輸入串的下一個(gè)符號(hào) , 繼續(xù)確定下一個(gè)推倒應(yīng)選的規(guī)則 , 如此下去 , 直到推倒出被分析的輸入串為止 .LL（1）分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法:#和文法開(kāi)始 符號(hào)進(jìn)棧X 彈棧，將 y1y2 yk逆序放第一個(gè)輸入符號(hào)讀進(jìn) a入S棧中，若右部符號(hào)串棧頂符號(hào)托出去放X 中為

4、，則 不 進(jìn)棧YYNX= #?NX=a?X VT?查 MX,a=X y1y2 ykNNYNYX=a?出錯(cuò)出錯(cuò)將下一個(gè)輸入YSTOP實(shí)驗(yàn)過(guò)程與實(shí)驗(yàn)結(jié)果（可包括實(shí)驗(yàn)實(shí)施的步驟、算法描述、流程、結(jié)論等）.程序流程圖 :實(shí)驗(yàn)過(guò)程記錄 ：實(shí)驗(yàn)過(guò)程中對(duì)文法修改后且輸入相同的符號(hào)串后所形成的分析表是一樣的， 這是一處錯(cuò)誤，另外輸入某個(gè)符號(hào)串后進(jìn)行無(wú)休止運(yùn)行，以上兩種錯(cuò)誤通過(guò)上網(wǎng)查詢(xún)以及和同學(xué)交流得以解決。實(shí)驗(yàn)總結(jié) ：LL(1) 分析器又稱(chēng)預(yù)測(cè)分析法，是一種不帶回溯的非遞歸自上而下分析法，一個(gè) LL(1) 分析器由一張 LL(1) 分析表、一個(gè)先進(jìn)后出分析棧和一個(gè)控制程序組成。附錄（可包括源程序清單或其它說(shuō)明

5、）源程序：#include #include #include #include #include .#define Pro_MidSym_Max 2#define Pro_RightSym_Max 10#define UnTInfo_Fir_Max 10#define UnTInfo_Fol_Max 10#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct ProNode /產(chǎn)生式結(jié)構(gòu)char leftSym;/產(chǎn)生式左邊的符號(hào)char midSymPro_MidSym_Max;/產(chǎn)生式推導(dǎo)符號(hào)char righ

6、tSymPro_RightSym_Max;/產(chǎn)生式右邊的符號(hào)，不超過(guò)十個(gè)intlength;/產(chǎn)生式長(zhǎng)度ProNode;typedef struct UnTInfo /每個(gè)非終結(jié)符的信息結(jié)構(gòu)，包括first和 follow集合char firstUnTInfo_Fir_Max;char followUnTInfo_Fol_Max;UnTInfo;typedef struct /構(gòu)造順序棧 , 存儲(chǔ)符號(hào)char *base;char *top;.int stacksize;SqStack;typedef struct QNode /構(gòu)造單鏈隊(duì)列，存儲(chǔ)輸入符號(hào)串char data;struct Q

7、Node *next;QNode,*QueuePtr;typedef struct QueuePtr front; /隊(duì)頭指針QueuePtr rear;/隊(duì)尾指針LinkQueue;int proNum;/產(chǎn)生式個(gè)數(shù)char UnTerminate15;/非終結(jié)符表char Terminate15;/終結(jié)符表char ProNull20;/記錄能產(chǎn)生空字符的非終結(jié)符ProNode sheet1515; /分析表char select1515;/select集合，以便于構(gòu)造分析表LinkQueue Remain;/剩余符號(hào)串.void InitUnTInfo(UnTInfo unTInfo,i

8、nt unTInfoNum);初始化函數(shù)，對(duì)每個(gè)非終結(jié)符的信息結(jié)構(gòu)進(jìn)行初始化void InitProNode(ProNode proNode,int proNum);初始化函數(shù)，對(duì)每個(gè)非終結(jié)符的產(chǎn)生式結(jié)構(gòu)進(jìn)行初始化void InitStack(SqStack &s);/初始化棧void InitQueue(LinkQueue &q); /初始化隊(duì)列void EnQueue(LinkQueue &q,char c); /在隊(duì)尾插入新的元素void Exit(); /棧溢出處理函數(shù)void Error();/出錯(cuò)處理void Push(SqStack &s, char c);/入棧char Pop

9、(SqStack &s); /出棧void InitSheet(ProNode* sheet,int m,int n) ;/初始化分析表函數(shù)bool ReadPro(ProNode proNode,char fileName);/從文件讀取產(chǎn)生式函數(shù)void PrintPro(ProNode proNode,int proNum); /顯示產(chǎn)生式void SetUnTerminate(char UnTerminate,ProNode proNode,intproNum);/設(shè)置非終結(jié)符表void SetTerminate(char UnTerminate,ProNode proNode,int

10、 proNum);/設(shè)置終結(jié)符表int GetNumofUT(char UnTerminate); /獲得非終結(jié)符個(gè)數(shù)int GetNumofT(char Terminate); /獲得終結(jié)符個(gè)數(shù)int GetUTLoaction(charUnTerminate,charc);/獲得非終結(jié)符在非終結(jié)符表中的位置int GetTLocaction(char UnTerminate,char c);/獲得終結(jié)符在終結(jié)符表中的位置void First(ProNode proNode,UnTInfo unTInfo);/計(jì)算各非終結(jié)符的.First集voidFollow(ProNodeproNode,

11、UnTInfounTInfo);/計(jì)算各非終結(jié)符的Follow集void AddChar(char chArray,char c);/將非終結(jié)符的所有first值加入 First集voidAddCharToChar(char chArray,charotherArray);/將非終結(jié)符的所有first集加入 First 集void AddFollow(char follow,char c);/將非終結(jié)符的所有follow值加入 Follow 集bool IsNull(char c);/非終結(jié)符能否產(chǎn)生空字符bool IsTerminate(char c); /判斷是否為終結(jié)符號(hào)void Set

12、Sheet(ProNode proNode,UnTInfo unTInfo); /設(shè)置分析表void SetSelect(ProNode proNode,UnTInfo unTInfo);/設(shè)置 Select 集合void InputSym(); /輸入字符串函數(shù)void Scan(); /分析掃描的主控程序char GetSym(LinkQueue &q) ; /獲取下一字符void PrintSym(SqStack &s); /顯示符號(hào)棧符號(hào)void PrintRemain(LinkQueue &q); /顯示剩余符號(hào)串void PrintSheet(int row,int col);/顯

13、示所使用產(chǎn)生式void Success(); /分析成功void main() .char fileName10;cout編制人：涂君蘭，20042003，三班 endl;cout請(qǐng)輸入放有產(chǎn)生式的文件（如：pro.txt） :fileName;ProNode proNode20;InitProNode(proNode,20);if(ReadPro(proNode,fileName) /*輸出文法產(chǎn)生式*/cout該文法產(chǎn)生式為：endl;PrintPro(proNode,proNum);/*設(shè)置非終結(jié)符表和終結(jié)符表*/SetUnTerminate(UnTerminate,proNode,pr

14、oNum);SetTerminate(Terminate,proNode,proNum);/*輸出 First集 */int NumofUT = GetNumofUT(UnTerminate);int NumofT = GetNumofT(Terminate);UnTInfo unTinfo20;InitUnTInfo(unTinfo,20);/*輸出 First集 */First(proNode,unTinfo);/*輸出 Follow 集 */.Follow(proNode,unTinfo);/*設(shè)置 select*/SetSelect(proNode,unTinfo);/*輸出 shee

15、t*/coutendl分析表 :endl;SetSheet(proNode,unTinfo);coutt;for(int jj = 0 ; jj NumofT ; jj+)coutTerminatejjt;coutendl;for(int mm = 0 ; mm NumofUT ; mm+) coutUnTerminatemmt;for(int mn = 0 ; mn NumofT; mn+) PrintSheet(mm,mn);coutt;coutendl;InputSym(); /輸入字符串Scan();/主控程序else.Error();void InitProNode(ProNode

16、proNode,int proNum) /初始化函數(shù)，對(duì)每個(gè)非終結(jié)符的產(chǎn)生式結(jié)構(gòu)進(jìn)行初始化for(int i = 0 ; i proNum ; i+) proNodei.leftSym = 0;memset(proNodei.midSym,0,Pro_MidSym_Max);memset(proNodei.rightSym,0,Pro_RightSym_Max);proNodei.length = 0;void InitUnTInfo(UnTInfo unTInfo,int unTInfoNum) /初始化函數(shù)，對(duì)每個(gè)非終結(jié)符的信息結(jié)構(gòu)進(jìn)行初始化for(int i = 0 ; i = s.st

17、acksize) /棧滿(mǎn)，追加存儲(chǔ)空間s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(char);if(!s.base) Exit(); /存儲(chǔ)分配失敗s.top = s.base + s.stacksize;s.stacksize += STACKINCREMENT;*(s.top) = c;s.top = s.top + 1;char Pop(SqStack &s) /出棧.if(s.top = s.base ) return NULL;s.top = s.top - 1;char tmpChar = *

18、(s.top);return tmpChar;void InitQueue(LinkQueue &q) /初始化隊(duì)列q.front = q.rear = (QueuePtr)malloc(sizeof(QNode);if(!q.front) Exit();/存儲(chǔ)分配失敗q.front-next = NULL;void EnQueue(LinkQueue &q,char c) /在隊(duì)尾插入新的元素QueuePtr p = (QueuePtr)malloc(sizeof(QNode);if(!p) Exit();/存儲(chǔ)分配失敗p-data = c;p-next = NULL;q.rear-next

19、 = p;q.rear = p;void Exit() /溢出處理.cout溢出！ endl;void Error() /出錯(cuò)處理cout分析出錯(cuò)！ endl;void InitSheet(ProNode* sheet,int m,int n) /初始化分析表函數(shù), 以便將無(wú)定義的表格定義為errorfor (int i = 0 ; i m;i+)for(int j = 0 ; j n ; j+) sheetij.leftSym= 0;/用 0 標(biāo)記無(wú)定義的表格bool ReadPro(ProNode proNode,char fileName) FILE* pFile;if(pFile =

20、fopen(fileName,r) = NULL) cout打開(kāi)文件出錯(cuò)！endl;.return false;char tmpChar;int tmpIndex = 0;fscanf(pFile,%c,&tmpChar);while(tmpChar != #) /求出產(chǎn)生式的個(gè)數(shù)if(tmpChar = ;)tmpIndex+;fscanf(pFile,%c,&tmpChar);proNum = tmpIndex;rewind(pFile);for(int i = 0;i proNum;i+) /讀出各產(chǎn)生式并置于已定義的數(shù)據(jù)結(jié)構(gòu) ProNode 中 ,/同時(shí)可將非終結(jié)符置于非終結(jié)符號(hào)表fs

21、canf(pFile,%c %c %c,&proNodei.leftSym,&proNodei.midSym0,&proNodei.midSym1);proNodei.midSym2 = 0;fscanf(pFile,%c,&tmpChar);int j = 0;while(tmpChar != ;) proNodei.rightSymj = tmpChar;.fscanf(pFile,%c,&tmpChar);j+;proNodei.rightSymj = 0;proNodei.length = j;return true;void PrintPro(ProNode proNode,int

22、proNum) /顯示產(chǎn)生式for(int i = 0 ; i proNum ; i+) coutproNodei.leftSymproNodei.midSym0proNodei.midSym1;for(int j = 0; j proNodei.length;j+)coutproNodei.rightSymj;coutendl;void SetUnTerminate(char UnTerminate,ProNode proNode,int proNum) /獲得非終結(jié)符，存儲(chǔ)于非終結(jié)符表for(int i = 0; i proNum; i+) /從第一個(gè)產(chǎn)生式開(kāi)始.bool flag = t

23、rue;int tmpLength = strlen(UnTerminate);for(int j = 0; j = tmpLength; j+) if(UnTerminatej = proNodei.leftSym) /若已存在，則進(jìn)入下個(gè)產(chǎn)生式flag = false;break;if(flag) UnTerminatetmpLength= proNodei.leftSym; /將非終結(jié)符加入到非終結(jié)符表UnTerminatetmpLength + 1 = 0;void SetTerminate(char Terminate,ProNode proNode,int proNum) /獲得終

24、結(jié)符，存儲(chǔ)于終結(jié)符表int tmpLength;bool flag ;for(int i = 0; i proNum; i+) /從第一個(gè)產(chǎn)生式開(kāi)始.for(int k = 0 ; k proNodei.length; k+) flag = true;tmpLength = strlen(Terminate);if(isupper(proNodei.rightSymk)/若為非終結(jié)符號(hào)，則進(jìn)入下一個(gè)字符flag = false;else if ( proNodei.rightSymk = ) int tmpLength = strlen(ProNull);flag = false;ProNul

25、ltmpLength=proNodei.leftSym;記錄能產(chǎn)生空字符的產(chǎn)生式ProNulltmpLength + 1 = 0;else if(flag)for(int j = 0; j = tmpLength; j+) if(Terminatej=proNodei.rightSymk) /若已存在，則進(jìn)入下一個(gè)字符flag = false;break;if(flag)/將終.結(jié)符加入到終結(jié)符表TerminatetmpLength=proNodei.rightSymk;TerminatetmpLength + 1 = 0;int GetNumofUT(char UnTerminate) /獲

26、得非終結(jié)符個(gè)數(shù)return strlen(UnTerminate);int GetNumofT(char Terminate) /獲得終結(jié)符個(gè)數(shù)return strlen(Terminate);bool IsNull(char c) /非終結(jié)符能否產(chǎn)生空字符int len = strlen(ProNull);for(int i = 0;i len;i+) if(ProNulli = c)return true;.return false;bool IsTerminate(char c) /判斷是否為終結(jié)符號(hào)int num = GetNumofT(Terminate);bool flag = f

27、alse;for(int i = 0 ; i num; i+ ) if(Terminatei = c) flag = true;break;return flag;int GetUTLoaction(char UnTerminate,char c) /獲得非終結(jié)符在非終結(jié)符表中的位置for(int i = 0 ; i GetNumofUT(UnTerminate);i+)if(UnTerminatei = c)return i;return -1;.int GetTLocaction(char Terminate,char c) /獲得終結(jié)符在終結(jié)符表中的位置for(int i = 0 ; i

28、 GetNumofT(Terminate);i+)if(Terminatei = c)return i;return -1;void AddChar(char chArray,char c)/將非終結(jié)符的所有first值加入 First集bool flag = true;int tmpLength = strlen(chArray);for(int i = 0; i = tmpLength; i+) if(chArrayi = c) /若已存在，則不加入flag = false;break;if(flag) chArraytmpLength = c;/將 first值加入 First集chAr

29、raytmpLength + 1 = 0;.void AddCharToChar(char chArray,char otherArray) int otherLength = strlen(otherArray);for(int j = 0 ; j otherLength; j+) bool flag = true;int tmpLength = strlen(chArray);for(int i = 0; i = 0 ; i-) /從最后一個(gè)產(chǎn)生式開(kāi)始進(jìn)行分析char leftSym = proNodei.leftSym;char c = proNodei.rightSym0;int le

30、ftSymLoc = GetUTLoaction(UnTerminate,leftSym);if(IsNull(leftSym)/如果產(chǎn)生式推出空字符，則把空字符加入 First集合AddChar(unTInfoleftSymLoc.first,c);else if(IsTerminate(c) /如果產(chǎn)生式右邊第一個(gè)符號(hào)為終結(jié)符號(hào)AddChar(unTInfoleftSymLoc.first,c); /將符號(hào)加入 First集合else for(int k = 0; k proNodei.length; k+) if(!IsNull(proNodei.rightSymk) /判斷能否產(chǎn)生空字

31、符，直到找到不為空的停止break;if(k = proNodei.length)./若對(duì)于產(chǎn)生式右邊的一切非終結(jié)符, 均可推出，則將加進(jìn)FIRST 集AddChar(unTInfoleftSymLoc.first,);else for(int l = 0 ; l k;l+) /*將產(chǎn)生式右邊能推出空字符的非終結(jié)符的Frist集中不含的終結(jié)符加入到該非終結(jié)符的Fisrt集 */charrightChar=proNodei.rightSyml;intrightSymLoc=GetUTLoaction(UnTerminate,rightChar);intfirstLen=strlen(unTInf

32、orightSymLoc.first);for(intm = 0 ; m firstLen;m+)if(unTInforightSymLoc.firstm != )AddChar(unTInfoleftSymLoc.first,unTInforightSymLoc.firstm);/*將產(chǎn)生式右邊不能推出空字符的非終結(jié)符的 Frist集加入到該非終結(jié)符的Fisrt集 */intrightSymLoc=GetUTLoaction(UnTerminate,proNodei.rightSymk);AddCharToChar(unTInfoleftSymLoc.first,unTInforightSy

33、mLoc.first);.void Follow(ProNode proNode,UnTInfo unTInfo)/計(jì)算各非終結(jié)符的Follow集AddChar(unTInfo0.follow,#);/開(kāi)始符號(hào)，則把“#”加入 FOLLOW中；int numOfUnT = GetNumofUT(UnTerminate);for(int i = 0; i numOfUnT ; i+) for(int j = 0 ;j proNum; j+) /從第一個(gè)產(chǎn)生式開(kāi)始進(jìn)行分析，逐個(gè)進(jìn)行掃描bool flag = false ;for(int k = 0 ; k , 則把 FOLLOW(B)加入 FOL

34、LOW(A) 中if(proNodej.leftSym!=UnTerminatei) intleftSymLoc=GetUTLoaction(UnTerminate,proNodej.leftSym);AddCharToChar(unTInfoi.follow,unTInfoleftSymLoc.follow);if(proNodej.rightSymk+1 != 0)/若 B A ( ) ，則把FIRST( )- 加入 FOLLOW(A)中if(IsTerminate(proNodej.rightSymk+1)/如果為終結(jié)符， 則將其直接加入FOLLOW(A)中AddChar(unTInfo

35、i.follow,proNodej.rightSymk+1);else /如果為非終結(jié)符，則將FIRST( )- 加入 FOLLOW(A)中intrightSymLoc=GetUTLoaction(UnTerminate,proNodej.rightSymk+1);intlen=strlen(unTInforightSymLoc.first);for(int l = 0; l len ;l+) .if(unTInforightSymLoc.firstl != )AddChar(unTInfoi.follow,unTInforightSymLoc.firstl);void SetSelect(P

36、roNode proNode,UnTInfo unTInfo) /設(shè)置 Select集合bool isNull,isVT;for(int i = 0 ;i proNum; i+) /掃描每一個(gè)產(chǎn)生式，求出Select集合if(IsTerminate(proNodei.rightSym0) /如果產(chǎn)生式的右邊第一字符為終結(jié)符，則將其加入select集AddChar(selecti,proNodei.rightSym0);else if(proNodei.rightSym0 = )/如果產(chǎn)生式的右邊字符為, 則應(yīng)將左邊字符的follow集加入 select集.AddCharToChar(selec

37、ti,unTInfoGetUTLoaction(UnTerminate,proNodei.leftSym).follow);else isVT = false;isNull = true;for(int j = 0; j proNodei.length; j+) /產(chǎn)生式右邊的第一個(gè)字符為非終結(jié)符，則逐個(gè)分析if(!IsTerminate(proNodei.rightSymj) /若 =X1X2Xn ，其中Xi VN , 1i n；/若 FIRST(X1), 則將FIRST(X2) 中的一切非的終結(jié)符加進(jìn)FIRST( ),/FIRST( ) 則應(yīng)加入select集；以此類(lèi)推intrightSy

38、mLoc=GetUTLoaction(UnTerminate,proNodei.rightSymj);intfirLen=strlen(unTInforightSymLoc .first);for(int k = 0 ; k ABa的產(chǎn)生式的情況AddChar(selecti,proNodei.rightSymj);if(j = proNodei.length) /若 =X1X2Xn ，其中Xi VN , 1 i n；/若對(duì) 于 一切1 i n, FIRST(Xi) ，則將follow( ) 加入 select集合intleftSymLoc=GetUTLoaction(UnTerminate,

39、proNodei.leftSym);AddCharToChar(selecti,unTInfoleftSymLoc.follow);.void SetSheet(ProNode proNode,UnTInfo unTInfo) /構(gòu)造分析表int selLen ;int rowLoc,colLoc;for(int i = 0; i proNum ; i+) selLen = strlen(selecti);for(int j = 0 ; j selLen ; j+) rowLoc=GetUTLoaction(UnTerminate,proNodei.leftSym);colLoc = GetTLocaction(Terminate,selectij);sheetrowLoccolLoc = proNodei;void InputSym() /輸入字符串函數(shù)InitQueue(Remain);cout請(qǐng)輸入要分析的字符串( 以 # 結(jié)束 ):tmpChar;while(tmpChar != #) EnQueue(Remain,tmpChar);cintmpChar;EnQueue(Remain,tmpChar);void Scan() /分析掃描的主控程序int i = 0