編譯原理實(shí)驗(yàn)報告-語法分析2預(yù)測分析法目錄24190_WPSOffice_Level11.摘要： 311059_WPSOffice_Level12、實(shí)驗(yàn)?zāi)康模?324984_WPSOffice_Level13、任務(wù)概述 312877_WPSOffice_Level14、實(shí)驗(yàn)依據(jù)的原理 318479_WPSOffice_Level15、程序設(shè)計思想 5887_WPSOffice_Level16、實(shí)驗(yàn)結(jié)果分析 923557_WPSOffice_Level17、總結(jié) 1828572_WPSOffice_Level18、程序代碼 181.摘要：用C／C++實(shí)現(xiàn)并運(yùn)用預(yù)測分析法對Pascal的子集程序設(shè)計語言進(jìn)行語法識別程序，并對語言進(jìn)行判斷，找出錯誤。2、實(shí)驗(yàn)?zāi)康模和ㄟ^預(yù)測分析法進(jìn)行設(shè)計、編程、調(diào)試出一個語法分析程序，加深對預(yù)測分析法的語法分析原理的理解，掌握其設(shè)計方法。3、任務(wù)概述1）將源程序轉(zhuǎn)換成內(nèi)碼流，然后用預(yù)測分析法進(jìn)行分析。2）構(gòu)造預(yù)測分析表，并利用分析表和一個棧來實(shí)現(xiàn)對Pascal的子集程序設(shè)計語言的分析程序。4、實(shí)驗(yàn)依據(jù)的原理4.1Pascal的子集程序設(shè)計語言的文法Pascal的子集程序設(shè)計語言的文法如下：<程序>→<程序首部><分程序>。<程序首部>→PROGRAM標(biāo)識符；<分程序>→<常量說明部分><變量說明部分><過程說明部分><復(fù)合語句><常量說明部>→CONST<常量定義><常量定義后綴>|ε<常量定義>→標(biāo)識符=無符號整數(shù)<常量定義后綴>→，<常量定義><常量定義后綴>|ε<變量說明部分>→VAR<變量定義><變量定義后綴>|ε<變量定義>→標(biāo)識符<標(biāo)識符后綴>：<類型>；<標(biāo)識符后綴>→，標(biāo)識符<標(biāo)識符后綴>|ε<變量定義后綴>→<變量定義><變量定義后綴>|ε<類型>→INTEGER|LONG<過程說明部分>→<過程首部><分程序>；<過程說明部分后綴>|ε<過程首部>→PROCEDURE標(biāo)識符<參數(shù)部分>；<參數(shù)部分>→(標(biāo)識符：<類型>)|ε<過程說明部分后綴>→<過程首部><分程序>；<過程說明部分后綴>|ε<語句>→<賦值或調(diào)用語句>|<條件語句>|<當(dāng)型循環(huán)語句>|<讀語句>|<寫語句>|<復(fù)合語句>|ε<賦值或調(diào)用語句>→標(biāo)識符<后綴><后綴>→：=<表達(dá)式>|(<表達(dá)式>)|ε<條件語句>→IF<條件>THEN<語句><當(dāng)型循環(huán)語句>→WHILE<條件>DO<語句><讀語句>→READ（標(biāo)識符<標(biāo)識符后綴>）<寫語句>→WRITE（<表達(dá)式><表達(dá)式后綴>）<表達(dá)式后綴>→，<表過式><表達(dá)式后綴>|ε<復(fù)合語句>→BEGIN<語句><語句后綴>END<語句后綴>→；<語句><語句后綴>|ε<條件>→<表達(dá)式><關(guān)系運(yùn)算符><表達(dá)式>|ODD<表達(dá)式><表達(dá)式>→+<項(xiàng)><項(xiàng)后綴>|-<項(xiàng)><項(xiàng)后綴>|<項(xiàng)><項(xiàng)后綴><項(xiàng)后綴>→<加型運(yùn)算符><項(xiàng)><項(xiàng)后綴>|ε<項(xiàng)>→<因子><因子后綴><因子后綴>→<乘型運(yùn)算符><因子><因子后綴>|e<因子>→標(biāo)識符|無符號整數(shù)|（<表達(dá)式>）<加型運(yùn)算符>→+|-<乘型運(yùn)算型>→*|/<關(guān)系運(yùn)算符>→=|<>|<|<=|>|>=4.2內(nèi)碼對照表1-1終結(jié)符的內(nèi)部碼對照表內(nèi)碼單詞內(nèi)碼單詞內(nèi)碼單詞內(nèi)碼單詞1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ12WRITE13BEGIN14END15ODD16+17-18*19/20=21<>22<23<=24>25>=26.27,28;29:30:=31(32)33無符號整數(shù)34標(biāo)識符35#表1-2非終結(jié)符和內(nèi)碼對照表內(nèi)碼非終結(jié)符內(nèi)碼非終結(jié)符內(nèi)碼非終結(jié)符128〈程序〉129〈程序首部〉130〈分程序〉131〈常量說明部分〉132〈常量定義〉133〈常量定義后綴〉134〈變量說明部分〉135〈變量定義〉136〈變量定義后綴〉137〈類型〉138〈過程說明部分〉139〈過程首部〉140<過程說明部分后綴>141〈語句〉142〈賦值或調(diào)用語句〉143〈后綴〉144〈條件語句〉145〈當(dāng)型循環(huán)語句〉146〈讀語句〉147〈標(biāo)識符后綴〉148〈寫語句〉149〈表達(dá)式后綴〉150〈復(fù)合語句〉151〈語句后綴〉152〈條件〉153〈表達(dá)式〉154〈項(xiàng)后綴〉155〈項(xiàng)〉156〈因子后綴〉157〈因子〉158〈參數(shù)部分〉159〈加型運(yùn)算符〉160〈乘型運(yùn)算符〉161〈關(guān)系運(yùn)算符〉5、程序設(shè)計思想5.1文法轉(zhuǎn)化將上述文法轉(zhuǎn)換成內(nèi)碼：128→129130260129→134280130→1311341381500131→2132133280131→0132→3420330133→271321330133→0134→31351360134→0135→3414729137280136→1351360136→0137→40137→50138→139130281400138→0139→634158280140→139130281400140→0141→1420141→1440141→1450141→1460141→1480141→1500141→0142→341430143→301530143→31153320143→0144→715281410145→9152101410146→113134147320147→27341470147→0148→1231153149320149→271531490149→0150→13141151140151→281411510151→0152→1531611530152→151530153→161551540153→171551540153→1551540154→1591551540154→0155→1571560156→1601571560156→0157→340157→330157→31153320158→313429137320158→0159→160159→170160→180160→190161→200161→210161→220161→230161→240161→2505.2求非終結(jié)符的First集的方法：1.直接收?。喝鬠－>a…（其中a是終結(jié)符）,把a(bǔ)收入到First(U)中；2.反復(fù)傳送：若U－>P…（其中P是非終結(jié)符）,應(yīng)把First(P)中的全部內(nèi)容傳送到First(U)中。5.3求非終結(jié)符的Follow集的方法（Follow集是從開始符號S開始推導(dǎo)，初始定義Follow（S）={#}）：1.直接收?。喝鬗－>Ua,把a(bǔ)直接收入到Follow(U)中；2.直接收?。喝鬗－>UP(P是非終結(jié)符),把First(P)除去ε后直接收入到Follow(U)中；3.反復(fù)傳送：若P－>…U（U是非終結(jié)符）,把Follow(P)中的全部內(nèi)容傳送到Follow(U)中。5.4求產(chǎn)生式的First集的方法：若M－>U1U2U3……Un若非終結(jié)符U1的First集含ε，則First(U1)除去ε后直接收入到該產(chǎn)生式的First集，再依次判斷U2（方法類似U1）；若非終結(jié)符U1的First集不含ε，則First(U1)直接收入到該產(chǎn)生式的First集；若U1為終結(jié)符，則將U1直接收入到該產(chǎn)生式的First集。5.5預(yù)測分析表的構(gòu)造：對于文法中的每一個產(chǎn)生式A->α,執(zhí)行以下2步：1.for?a∈FIRST(α)，將A->α填入M[A,a];2.if（ε∈FIRST(α)）?a∈FOLLOW(A)，將A->ε填入M[A,a]。5.6預(yù)測分析法分析對于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動作之一：（1）若X=a=‘#’，則宣布分析成功，停止分析過程。（2）若X=a≠‘#’，則把X從STACK棧頂彈出，讓a指向下一個輸入符號。（3）若X是一個非終結(jié)符，則查看預(yù)測分析表M。若M[X，a]中存放著關(guān)于X的一個產(chǎn)生式，那么，首先把X彈出STACK棧頂，然后，把產(chǎn)生式的右部符號串按反序一一彈出STACK棧（若右部符號為ε，則不推什么東西進(jìn)STACK棧）。若M[X，a]中存放著的數(shù)值表示出錯，則表示該程序有錯。5.7錯誤情況在預(yù)測分析表中引入同步符后，程序出錯分一下三種情況：（1）若X為終結(jié)符，但X≠a，表示X前缺少符號；（2）若X為非終結(jié)符，但M[X，a]=-1（-1表示不存在對應(yīng)產(chǎn)生式），表示X多余；（3）若X為非終結(jié)符，但M[X，a]=-2（-2表示同步符），表示X前缺少符號。programhelloworld;beginwrite(1);a:=2end.5.8程序流程圖是否計算每個產(chǎn)生式右部的FIRST集是否計算每個產(chǎn)生式右部的FIRST集計算所有非終結(jié)符號的FOLLOW集根據(jù)FIRST集和FOLLOW集生成預(yù)測分析表讀取文件中的程序根據(jù)預(yù)測分析表對程序進(jìn)行分析詞法分析是否正確語法分析正確提醒程序錯誤、錯誤的位置在哪里程序結(jié)束計算所有非終結(jié)符號的FIRST集語法分析是否正確程序入口語法分析失敗是否6、實(shí)驗(yàn)結(jié)果分析6.1文件內(nèi)容：6.2程序運(yùn)行結(jié)果如下：6.2.1所有非終結(jié)符的First集6.2.2所有非終結(jié)符的Follow集6.2.3所有產(chǎn)生式的First集6.2.4預(yù)測分析表6.2.5源程序顯示6.2.6詞法分析結(jié)果（1）若詞法分析無誤，則顯示如下圖所示并進(jìn)行語法分析：（2）若詞法分析有誤，則顯示如下圖所示，即指出錯誤之處，但不能進(jìn)行語法分析。text內(nèi)容：結(jié)果如下：6.2.7語法分析結(jié)果（1）若語法分析無誤，則顯示如下圖所示：（2）若語法分析有誤，則顯示如下圖所示，即指出錯誤之處：=1\*romani）棧中終結(jié)符與輸入串中終結(jié)符不相匹配時的情況：text內(nèi)容：結(jié)果顯示:=2\*romanii）棧中非終結(jié)符與輸入串中終結(jié)符所對應(yīng)的預(yù)測分析表中的數(shù)值為同步符時的情況：text內(nèi)容：結(jié)果顯示：=3\*romaniii）棧中非終結(jié)符與輸入串中終結(jié)符所對應(yīng)的預(yù)測分析表中的數(shù)值為不存在時的情況：text內(nèi)容：結(jié)果顯示：7、總結(jié)（1）本次實(shí)驗(yàn)完成了語法分析器-預(yù)測分析法的算法分析到實(shí)現(xiàn)的全部過程，結(jié)果滿足設(shè)計要求，驗(yàn)證無誤。通過本次實(shí)驗(yàn)讓我了解了如何設(shè)計、編制并調(diào)試預(yù)測分析法的語法分析程序，在設(shè)計、實(shí)現(xiàn)、調(diào)試自己的語法分析器的同時，加深了我對語法分析器原理的理解；熟悉了預(yù)測分析法構(gòu)造語法分析器的方法和相關(guān)原理，并能基本使用C語言直接編寫語法分析器。（2）通過這次實(shí)驗(yàn)使我懂得了理論與實(shí)際相結(jié)合的重要性，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實(shí)踐相結(jié)合起來，才能更好地理解、消化、掌握所學(xué)知識，同時也可以提高自己的實(shí)際動手能力和獨(dú)立思考的能力。在設(shè)計的過程中遇到很多問題，可以說是困難重重，畢竟很多問題是無法預(yù)料和避免的，所以難免會遇到過各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對課程所學(xué)的知識理解得不夠深刻，掌握得不夠牢固等等。（3）在本實(shí)驗(yàn)中，我鍛煉了自己的上機(jī)操作能力及編程能力，并對理論知識有了進(jìn)一步的了解。程序的難點(diǎn)是分析表的構(gòu)造，解決實(shí)驗(yàn)中遇到的問題也花費(fèi)了一部分的時間，增長了處理程序錯誤的能力。雖然這個程序還有許許多多的不足和欠缺，但它包含了我的想法和努力?？偟膩碚f，和成員一次完成這個語法分析器的設(shè)計很有意義。8、程序代碼#include<stdio.h>#include<iostream>#include<string>#include<stack>#include<stdlib.h>usingnamespacestd;#defineMAX_11000#defineMAX_2100000//產(chǎn)生式的左右部以及右部的長度typedefstructproduction{ intleft; intright[MAX_1]; intlength;}PRO;//程序每個字符的對應(yīng)內(nèi)碼以及所在行數(shù)typedefstructcharacter{ stringch; intcode; introw;}CHAR;//詞法分析時發(fā)現(xiàn)的錯誤typedefstructerror{ charch; introw;}ERR;//集合結(jié)構(gòu)typedefstructaggregate{ intstr[MAX_1]; intlen;}AGG;PRO*p=newPRO[MAX_1];//產(chǎn)生式CHARchara[MAX_2];//程序字符流ERRerror[MAX_2];//詞法分析時發(fā)現(xiàn)的錯誤AGGFirst[MAX_1];//用于存放每個非終結(jié)符的First集AGGFollow[MAX_1];//用于存放每個非終結(jié)符的Follow集intNONE[MAX_1]={0};//求每個非終結(jié)符的Follow集時避免死循環(huán)的變量AGGPro_First[MAX_1];//用于存放每個產(chǎn)生式右部的First集intTable[MAX_1][MAX_1];//預(yù)測分析表,-1表示不匹配，-2表示同步符號synchintN;//產(chǎn)生式的個數(shù)charset[MAX_2];//用于存儲初始代碼charstr[MAX_2];//用于存儲初步處理后的代碼interrorNum=0;//詞法分析發(fā)現(xiàn)錯誤數(shù)interrorNum2=0;//語法分析發(fā)現(xiàn)錯誤數(shù)intk=0;//程序字符流數(shù)intProgram_row=1;//程序初始行數(shù)stack<int>Stack;//符號棧//非終結(jié)符stringkey[15]={"PROGRAM","CONST","VAR","INTEGER","LONG","PROCEDURE","IF","THEN","WHILE","DO","READ","WRITE","BEGIN","END","ODD"};stringpunctuation[17]={"+","-","*","/","=","<>","<","<=",">",">=",".",",",";",":",":=","(",")"};//判斷字符串是否是關(guān)鍵字，若是，則返回該關(guān)鍵字對應(yīng)的內(nèi)碼；若不是，則返回0intIsKeyWord(stringc){ inti; for(i=0;i<15;i++) { if(key[i].compare(c)==0) returni+1; } return0;}//判斷字符串c是否是符號，若是，則返回該符號對應(yīng)的內(nèi)碼；若不是，則返回0intIsPunctuation(stringc){ inti; for(i=0;i<17;i++) { if(punctuation[i].compare(c)==0) returni+16; } return0;}//判斷字符c是否是字母，若是，則返回true；若不是，則返回falseboolIsLetter(charc){ if((c>='a'&&c<='z')||(c>='A'&&c<='Z')) returntrue; else returnfalse;}//判斷字符c是否是數(shù)字，若是，則返回true；若不是，則返回falseboolIsFigure(charc){ if(c>='0'&&c<='9') returntrue; else returnfalse;}//判斷該詞法錯誤是否已被檢測booltest(interrorNum,introw,charch){ inti; for(i=0;i<errorNum;i++) if(error[i].row==row&&error[i].ch==ch) returnfalse; returntrue;}//詞法分析voidlexical_analysis(){ FILE*f; stringtem=""; charch; intn=0,m=0;//程序代碼儲存數(shù) inti; if((f=fopen("test.txt","r"))==NULL){printf("cannotopenthefile!\n");exit(0);} else { while(!feof(f)) { ch=getc(f);//getc函數(shù)帶回一個字符，賦給ch set[n]=ch;//將文件的每一個字符都放入set[]數(shù)組中 n++; } } fclose(f);//關(guān)閉文件 set[n-1]='\0'; i=0; while(set[i]!='\0') { if(set[i]=='') { while(set[i]=='')//掃描到有連續(xù)的空格 i++; str[m]='';//用一個空格代替掃描到的連續(xù)空格放入str[] m++; } elseif(set[i]=='\n') { while(set[i]=='\n')//掃描到有連續(xù)的換行符 i++; str[m]='\n';//用一個換行符代替掃描到的連續(xù)換行符放入str[] m++; } else { //若當(dāng)前字符不為空格或換行符就直接放入str[] if(set[i]>='a'&&set[i]<='z') str[m]=set[i]-32; else str[m]=set[i]; m++; i++; } } str[m]='\0'; //顯示源程序 printf("\n---------------------------源程序顯示---------------------------\n\n"); for(i=0;i<m;i++) printf("%c",str[i]); printf("\n"); i=0; //將源程序轉(zhuǎn)換成字符流 for(i=0;i<m;i++) { tem=""; if(IsLetter(str[i])||str[i]=='_') { while(IsLetter(str[i])||IsFigure(str[i])||str[i]=='_') { tem=tem+str[i]; i++; } if(IsKeyWord(tem)>0) { chara[k].ch=tem; chara[k].code=IsKeyWord(tem); chara[k].row=Program_row; k++; } else { chara[k].ch=tem; chara[k].code=34; chara[k].row=Program_row; k++; } } elseif(IsFigure(str[i])) { while(IsFigure(str[i])) { tem=tem+str[i]; i++; } if(IsLetter(str[i])) { error[errorNum].row=Program_row; error[errorNum].ch=str[i]; errorNum++; } else { chara[k].ch=tem; chara[k].code=33; chara[k].row=Program_row; k++; } } tem=""; tem=tem+str[i]; switch(str[i]) { case':': case'>': i++; if(str[i]=='=') tem=tem+str[i]; else i--; chara[k].ch=tem; chara[k].code=IsPunctuation(tem); chara[k].row=Program_row; k++; break; case'<': i++; if(str[i]=='='||str[i]=='>') tem=tem+str[i]; else i--; chara[k].ch=tem; chara[k].code=IsPunctuation(tem); chara[k].row=Program_row; k++; break; case';': case',': case'.': case'(': case')': case'+': case'-': case'*': case'/': case'=': chara[k].ch=tem; chara[k].code=IsPunctuation(tem); chara[k].row=Program_row; k++; break; case'#': chara[k].ch=tem; chara[k].code=35; chara[k].row=Program_row; k++; break; case'': break; case'\n': Program_row++; break; default: if(test(errorNum,Program_row,str[i])) { error[errorNum].row=Program_row; error[errorNum].ch=str[i]; errorNum++; } } }}//所有產(chǎn)生式voidproduction(){ N=67;//產(chǎn)生式共有67個 //128→129130260 p[0].left=128; p[0].right[0]=129; p[0].right[1]=130; p[0].right[2]=26; p[0].length=3; //129→134280 p[1].left=129; p[1].right[0]=1; p[1].right[1]=34; p[1].right[2]=28; p[1].length=3; //130→1311341381500p[2].left=130; p[2].right[0]=131; p[2].right[1]=134; p[2].right[2]=138; p[2].right[3]=150; p[2].length=4; //131→2132133280 p[3].left=131; p[3].right[0]=2; p[3].right[1]=132; p[3].right[2]=133; p[3].right[3]=28; p[3].length=4; //131→0 p[4].left=131; p[4].right[0]=0; p[4].length=1; //132→3420330 p[5].left=132; p[5].right[0]=34; p[5].right[1]=20; p[5].right[2]=33; p[5].length=3; //133→271321330 p[6].left=133; p[6].right[0]=27; p[6].right[1]=132; p[6].right[2]=133; p[6].length=3; //133→0 p[7].left=133; p[7].right[0]=0; p[7].length=1; //134→31351360 p[8].left=134; p[8].right[0]=3; p[8].right[1]=135; p[8].right[2]=136; p[8].length=3; //134→0 p[9].left=134; p[9].right[0]=0; p[9].length=1; //135→3414729137280 p[10].left=135; p[10].right[0]=34; p[10].right[1]=147; p[10].right[2]=29; p[10].right[3]=137; p[10].right[4]=28; p[10].length=5; //136→1351360 p[11].left=136; p[11].right[0]=135; p[11].right[1]=136; p[11].length=2; //136→0 p[12].left=136; p[12].right[0]=0; p[12].length=1; //137→40 p[13].left=137; p[13].right[0]=4; p[13].length=1; //137→50 p[14].left=137; p[14].right[0]=5; p[14].length=1; //138→139130281400 p[15].left=138; p[15].right[0]=139; p[15].right[1]=130; p[15].right[2]=28; p[15].right[3]=140; p[15].length=4; //138→0 p[16].left=138; p[16].right[0]=0; p[16].length=1; //139→634158280 p[17].left=139; p[17].right[0]=6; p[17].right[1]=34; p[17].right[2]=158; p[17].right[3]=28; p[17].length=4; //140→139130281400 p[18].left=140; p[18].right[0]=139; p[18].right[1]=130; p[18].right[2]=28; p[18].right[3]=140; p[18].length=4; //140→0 p[19].left=140; p[19].right[0]=0; p[19].length=1; //141→1420 p[20].left=141; p[20].right[0]=142; p[20].length=1; //141→1440 p[21].left=141; p[21].right[0]=144; p[21].length=1; //141→1450 p[22].left=141; p[22].right[0]=145; p[22].length=1; //141→1460 p[23].left=141; p[23].right[0]=146; p[23].length=1; //141→1480 p[24].left=141; p[24].right[0]=148; p[24].length=1; //141→1500 p[25].left=141; p[25].right[0]=150; p[25].length=1; //141→0 p[26].left=141; p[26].right[0]=0; p[26].length=1; //142→341430 p[27].left=142; p[27].right[0]=34; p[27].right[1]=143; p[27].length=2; //143→301530 p[28].left=143; p[28].right[0]=30; p[28].right[1]=153; p[28].length=2; //143→31153320 p[29].left=143; p[29].right[0]=31; p[29].right[1]=153; p[29].right[2]=32; p[29].length=3; //143→0 p[30].left=143; p[30].right[0]=0; p[30].length=1; //144→715281410 p[31].left=144; p[31].right[0]=7; p[31].right[1]=152; p[31].right[2]=8; p[31].right[3]=141; p[31].length=4; //145→9152101410 p[32].left=145; p[32].right[0]=9; p[32].right[1]=152; p[32].right[2]=10; p[32].right[3]=141; p[32].length=4; //146→113134147320 p[33].left=146; p[33].right[0]=11; p[33].right[1]=31; p[33].right[2]=34; p[33].right[3]=147; p[33].right[4]=32; p[33].length=5; //147→27341470 p[34].left=147; p[34].right[0]=27; p[34].right[1]=34; p[34].right[2]=147; p[34].length=3; //147→0 p[35].left=147; p[35].right[0]=0; p[35].length=1; //148→1231153149320 p[36].left=148; p[36].right[0]=12; p[36].right[1]=31; p[36].right[2]=153; p[36].right[3]=149; p[36].right[4]=32; p[36].length=5; //149→271531490 p[37].left=149; p[37].right[0]=27; p[37].right[1]=153; p[37].right[2]=149; p[37].length=3; //149→0 p[38].left=149; p[38].right[0]=0; p[38].length=1; //150p[39].left=150; p[39].right[0]=13; p[39].right[1]=141; p[39].right[2]=151; p[39].right[3]=14; p[39].length=4; //151→281411510 p[40].left=151; p[40].right[0]=28; p[40].right[1]=141; p[40].right[2]=151; p[40].length=3; //151→0 p[41].left=151; p[41].right[0]=0; p[41].length=1; //152→1531611530 p[42].left=152; p[42].right[0]=153; p[42].right[1]=161; p[42].right[2]=153; p[42].length=3; //152→151530 p[43].left=152; p[43].right[0]=15; p[43].right[1]=153; p[43].length=2; //153→161551540 p[44].left=153; p[44].right[0]=16; p[44].right[1]=155; p[44].right[2]=154; p[44].length=3; //153→171551540 p[45].left=153; p[45].right[0]=17; p[45].right[1]=155; p[45].right[2]=154; p[45].length=3; //153→1551540 p[46].left=153; p[46].right[0]=155; p[46].right[1]=154; p[46].length=2; //154→1591551540 p[47].left=154; p[47].right[0]=159; p[47].right[1]=155; p[47].right[2]=154; p[47].length=3; //154→0 p[48].left=154; p[48].right[0]=0; p[48].length=1; //155→1571560 p[49].left=155; p[49].right[0]=157; p[49].right[1]=156; p[49].length=2; //156→1601571560 p[50].left=156; p[50].right[0]=160; p[50].right[1]=157; p[50].right[2]=156; p[50].length=3; //156→0 p[51].left=156; p[51].right[0]=0; p[51].length=1; //157→340 p[52].left=157; p[52].right[0]=34; p[52].length=1; //157→330 p[53].left=157; p[53].right[0]=33; p[53].length=1; //157→31153320 p[54].left=157; p[54].right[0]=31; p[54].right[1]=153; p[54].right[2]=32; p[54].length=3; //158→313429137320 p[55].left=158; p[55].right[0]=31; p[55].right[1]=34; p[55].right[2]=29; p[55].right[3]=137; p[55].right[4]=32; p[55].length=5; //158→0 p[56].left=158; p[56].right[0]=0; p[56].length=1; //159→160 p[57].left=159; p[57].right[0]=16; p[57].length=1; //159→170 p[58].left=159; p[58].right[0]=17; p[58].length=1; //160→180 p[59].left=160; p[59].right[0]=18; p[59].length=1; //160→190 p[60].left=160; p[60].right[0]=19; p[60].length=1; //161→200 p[61].left=161; p[61].right[0]=20; p[61].length=1; //161→210 p[62].left=161; p[62].right[0]=21; p[62].length=1; //161→220 p[63].left=161; p[63].right[0]=22; p[63].length=1; //161→230 p[64].left=161; p[64].right[0]=23; p[64].length=1; //161→240 p[65].left=161; p[65].right[0]=24; p[65].length=1; //161→250 p[66].left=161; p[66].right[0]=25; p[66].length=1;}//在str[]中查找t,若找到t,則返回t所在的數(shù)組下標(biāo);否則返回大數(shù)，設(shè)定該大數(shù)為MAXintsearch(AGGset,intt){ inti; for(i=0;i<set.len;i++) { if(set.str[i]==t) returni; } returnMAX_1;}//對每個非終結(jié)符A求First集AGGCharacter_First(PRO*p,intcode){ intk,flag=1;//若某個產(chǎn)生式的右側(cè)字符均為非終結(jié)符，且所有非終結(jié)符的First集中均含有ε，則flag的值為1 //遍歷所有產(chǎn)生式求該非終結(jié)符A的First集for(inti=0;i<N;i++){if(p[i].left==code)//在產(chǎn)生式的左部找到該非終結(jié)符A{if(p[i].right[0]>=1&&p[i].right[0]<=35)//該非終結(jié)符A所在的產(chǎn)生式的右側(cè)第一個字符是終結(jié)符，則將此終結(jié)符加入該非終結(jié)符的First集{ if(search(First[code],p[i].right[0])==MAX_1)//該非終結(jié)符A的First集無此終結(jié)符，則將此終結(jié)符加入該非終結(jié)符的First集{ First[code].str[First[code].len]=p[i].right[0]; First[code].len++; }} if(p[i].right[0]==0)//該非終結(jié)符所在的產(chǎn)生式的右側(cè)是ε，則將此終結(jié)符加入該非終結(jié)符的First集{ if(search(First[code],p[i].right[0])==MAX_1){ First[code].str[First[code].len]=p[i].right[0]; First[code].len++; }}if(p[i].right[0]>=128&&p[i].right[0]<=161)//該非終結(jié)符A所在的產(chǎn)生式的右側(cè)第一個字符是非終結(jié)符{if(p[i].length==1)//該非終結(jié)符A所在的產(chǎn)生式的右側(cè)僅有一個非終結(jié)符B,則將非終結(jié)符B的First集加入到非終結(jié)符A的First集{AGGset1; set1.len=0;set1=Character_First(p,p[i].right[0]);for(intj=0;j<set1.len;j++){ if(search(First[code],set1.str[j])==MAX_1) { First[code].str[First[code].len]=set1.str[j]; First[code].len++; }}}else//該非終結(jié)符A所在的產(chǎn)生式的右側(cè)符號數(shù)大于1{for(intj=0;j<p[i].length;j++){AGGset; set.len=0;if(p[i].right[j]>=128&&p[i].right[j]<=161)//該非終結(jié)符A所在的產(chǎn)生式的右側(cè)第j符號為非終結(jié)符{set=Character_First(p,p[i].right[j]);if(search(set,0)<MAX_1)//非終結(jié)符p[i].right[j]的First集中含有ε{for(k=0;k<set.len;k++){if(search(First[code],set.str[k])==MAX_1&&set.str[k]!=0)//將非終結(jié)符p[i].right[j]的First集中除ε之外的元素均加入所求非終結(jié)符A的First集中 { First[code].str[First[code].len]=set.str[k]; First[code].len++; }}}else//非終結(jié)符p[i].right[j]的First集中不含ε{flag=0;for(k=0;k<set.len;k++){if(search(First[code],set.str[k])==MAX_1)//將非終結(jié)符p[i].right[j]的First集中所有元素均加入所求非終結(jié)符A的First集中{ First[code].str[First[code].len]=set.str[k]; First[code].len++; }}break;}}else//該非終結(jié)符所在的產(chǎn)生式的右側(cè)符號中遇到終結(jié)符{flag=0;if(search(First[code],p[i].right[j])==MAX_1) { First[code].str[First[code].len]=p[i].right[j]; First[code].len++; }break;}} //該非終結(jié)符所在的產(chǎn)生式的右側(cè)符號均為非終結(jié)符，且所有非終結(jié)符的First集中均含有ε，則將0加入該非終結(jié)符的First集中,其中0表示空集εif(flag==1) { First[code].str[First[code].len]=0; First[code].len++; }}}}} returnFirst[code];}//求每個非終結(jié)符A的Follow集AGGCharacter_Follow(PRO*p,intcode){ intt,k,flag=1;//若該非終結(jié)符A的右側(cè)字符均為非終結(jié)符，且所有非終結(jié)符的First集中均含有ε，則flag的值為1 NONE[code]++;//避免死循環(huán)的變量值自增 if(NONE[code]==2)//當(dāng)出現(xiàn)所求非終結(jié)符的Follow集需要將自身加入時，將避免死循環(huán)的變量值設(shè)為0，并跳出死循環(huán){ NONE[code]=0; returnFollow[code];} //遍歷所有產(chǎn)生式求該非終結(jié)符A的Follow集for(inti=0;i<N;i++){ for(intj=0;j<p[i].length;j++) { if(p[i].right[j]==code)//在產(chǎn)生式的右部找到該非終結(jié)符A { if(j+1==p[i].length)//該非終結(jié)符A在其所在的產(chǎn)生式的最右側(cè) { AGGset1; set1.len=0; set1=Character_Follow(p,p[i].left); for(k=0;k<set1.len;k++) { if(search(Follow[code],set1.str[k])==MAX_1)//該非終結(jié)符A的Follow集無此終結(jié)符，則將此終結(jié)符加入該非終結(jié)符A的Follow集 { Follow[code].str[Follow[code].len]=set1.str[k]; Follow[code].len++; } } } else//該非終結(jié)符A不在其所在的產(chǎn)生式,即非終結(jié)符A的右側(cè)還有符號 { AGGset2; set2.len=0; for(intq=j+1;q<p[i].length;q++) { AGGset3; set3.len=0; if(p[i].right[q]>=1&&p[i].right[q]<=35)//該非終結(jié)符A右側(cè)的符號是終結(jié)符 { flag=0; if(search(set2,p[i].right[q])==MAX_1) { set2.str[set2.len]=p[i].right[q]; set2.len++; } break; } elseif(p[i].right[q]>=128&&p[i].right[q]<=161)//該非終結(jié)符A右側(cè)的符號是非終結(jié)符 { set3=Character_First(p,p[i].right[q]); if(search(set3,0)<MAX_1)//該非終結(jié)符A右側(cè)的非終結(jié)符p[i].right[q]的First集中含有ε { for(t=0;t<set3.len;t++) { if(search(set2,set3.str[t])==MAX_1&&set3.str[t]!=0)//將非終結(jié)符p[i].right[q]的First集中除ε之外的元素均加入set2集中 { set2.str[set2.len]=set3.str[t]; set2.len++; } } } else//該非終結(jié)符A右側(cè)的非終結(jié)符p[i].right[q]的First集中不含有ε { flag=0; for(t=0;t<set3.len;t++) { if(search(set2,set3.str[t])==MAX_1)//將非終結(jié)符p[i].right[q]的First集中所有元素均加入set2集中 { set2.str[set2.len]=set3.str[t]; set2.len++; } } break; } } } //該非終結(jié)符所在的產(chǎn)生式的右側(cè)符號均為非終結(jié)符，且所有非終結(jié)符的First集中均含有ε，則將0加入set2集中,其中0表示空集ε if(flag==1) { set2.str[set2.len]=0; set2.len++; } if(search(set2,0)==MAX_1)//set2集中不含ε，則將set2集中的所有元素均加入該非終結(jié)符A的Follow集中 { //B->aAC,把First(C)去掉ε加入到Follow(A)中(First(C)不含ε) for(k=0;k<set2.len;k++) { if(search(Follow[code],set2.str[k])==MAX_1) { Follow[code].str[Follow[code].len]=set2.str[k]; Follow[code].len++; } } } else//set2集中含有ε，則將set2集中除ε之外的元素均加入該非終結(jié)符A的Follow集中 { //B->aAC,把First(C)去掉ε加入到Follow(A)中(First(C)含ε) for(k=0;k<set2.len;k++) { if((search(Follow[code],set2.str[k])==MAX_1)&&set2.str[k]!=0) { Follow[code].str[Follow[code].len]=set2.str[k]; Follow[code].len++; } } //B->aAC,ε在First(C)中，把Follow(B)加入到Follow(A)中 AGGset4; set4.len=0; set4=Character_Follow(p,p[i].left); for(k=0;k<set4.len;k++) { if(search(Follow[code],set4.str[k])==MAX_1) { Follow[code].str[Follow[code].len]=set4.str[k]; Follow[code].len++; } } } } } } } returnFollow[code];}//求所有非終結(jié)符的First集voidKeep_Character_First(){ inti=0; for(i=128;i<=161;i++) { AGGset; set.len=0;set=Character_First(p,i); }}//求所有非終結(jié)符的Follow集voidKeep_Character_Follow(){ inti; for(i=128;i<=161;i++) { AGGset; set.len=0;set=Character_Follow(p,i); }}//求每個產(chǎn)生式右部的First集voidProduction_First(){ inti,j,k; intflag=1; //遍歷所有產(chǎn)生式,求每個產(chǎn)生式右部的First集 for(i=0;i<N;i++) { Pro_First[i].len=0; intflag=0;//求Pro_First集結(jié)束標(biāo)志,flag=1表示Pro_First集已經(jīng)求完 //遍歷產(chǎn)生式p[i]的所有右部 for(j=0;j<p[i].length;j++) { if(p[i].right[j]>=1&&p[i].right[j]<=35)//p[i].right[j]符號是終結(jié)符 { if(search(Pro_First[i],p[i].right[j])==MAX_1) { Pro_First[i].str[Pro_First[i].len]=p[i].right[j]; Pro_First[i].len++; } flag=1; } else//p[i].right[j]符號是非終結(jié)符或ε { //將非終結(jié)符p[i].right[j]的First集中除ε之外的元素均加入該產(chǎn)生式p[i]右部的Pro_First集中 for(k=0;k<First[p[i].right[j]].len;k++) { if(First[p[i].right[j]].str[k]!=0) { if(search(Pro_First[i],First[p[i].right[j]].str[k])==MAX_1) { Pro_First[i].str[Pro_First[i].len]=First[p[i].right[j]].str[k]; Pro_First[i].len++; } flag=1; } else flag=0; } } if(flag==1) break; if(flag==0&&j==p[i].length-1)//該產(chǎn)生式p[i]的最右部為非終結(jié)符且該非終結(jié)符的First集含ε或該產(chǎn)生式p[i]的最右部為ε { Pro_First[i].str[Pro_First[i].len]=0; Pro_First[i].len++; } } }}//構(gòu)造預(yù)測分析表voidStructura_Table(){ inti,j,k,t,q; intflag;//標(biāo)志，flag=0表示產(chǎn)生式的First集中不包含ε //初始化 for(i=0;i<=34;i++) for(j=0;j<=35;j++) Table[i][j]=-1; //預(yù)測表的第一行為終結(jié)符的內(nèi)碼 for(i=1;i<=35;i++) Table[0][i]=i; //預(yù)測表的第一列為非終結(jié)符的內(nèi)碼 for(j=1;j<=34;j++) Table[j][0]=j+127; for(k=0;k<N;k++) { flag=0; for(t=0;t<Pro_First[k].len;t++) { if(Pro_First[k].str[t]!=0)//若產(chǎn)生式k的First集中的第t個元素α不是ε，則在預(yù)測表中該產(chǎn)生式左部的非終結(jié)符A對應(yīng)的α列下填上該產(chǎn)生式k Table[p[k].left-127][Pro_First[k].str[t]]=k; else//若產(chǎn)生式k的First集中的第t個元素α是ε，則需參考該產(chǎn)生式左部的非終結(jié)符A的Follow集 { flag=1; for(q=0;q<Follow[p[k].left].len;q++)//該產(chǎn)生式左部的非終結(jié)符A的Follow集的第q個元素β，在預(yù)測表中該產(chǎn)生式左部A的非終結(jié)符對應(yīng)的β列下填上該產(chǎn)生式k Table[p[k].left-127][Follow[p[k].left].str[q]]=k; } } //添上同步符號 if(flag==0) for(t=0;t<Follow[p[k].l