計算機(jī)13-3班實驗報告

1、實驗一詞法分析設(shè)計一、實驗功能：對輸入的 txt 文件內(nèi)的內(nèi)容進(jìn)行詞法分析：由文件流輸入 test.txt 中的內(nèi)容，使其輸出要求符合實驗的要求打印出分析后的結(jié)果；二、程序結(jié)構(gòu)描述：（源代碼見附錄）1. 首先構(gòu)造 2 個表，stringkey34=main,prf,short,long,float,double,char,struct,scanf,then,typedef,const,cout,=,=,(,),:,; ,TG（2）G-+TG|TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)（8）F-i二、程序結(jié)構(gòu)：1定義部分 定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。Vt Vn

2、TSym InSt終結(jié)符下標(biāo)集。非終結(jié)符下標(biāo)集。LL1分析表。符號棧 it 為其棧頂 為方便輸出用 vector 模擬。輸出串。規(guī)約時所用產(chǎn)生式。23初始化 設(shè)立LL(1)分析表。分析過程從鍵盤輸入一個表達(dá)式符號串 input把?#?和文法開始符號入 sym 棧把 input 第一個符號給aWhile1X = Sym.pop(); Ifx in Vt thenIfx = a then 把下個輸入符號給 aElse ERROR Else if x = #thenIfx = a then break else ERRORElse if Tx, a = Pi then 產(chǎn)生式 Pi 右側(cè)依次反向入

3、sym 棧Else ERROR分析成功三、實驗結(jié)果：實驗總結(jié)本次試驗，相對來說比較難，比如，如何實現(xiàn)自動產(chǎn)生分析表，這是完成本次實驗的關(guān)鍵，通過參考網(wǎng)上的一些程序，我最終順利完成任務(wù)。通過完成分析法的語法分析程序，我深刻了解了分析法和遞歸子程序法的區(qū)別和聯(lián)系以及語法分析的功能。更重要的是，我清楚地知道了語法分析程序設(shè)計的原理和構(gòu)造方法，同時也掌握了一些開發(fā)應(yīng)用程序的基本方法，提高了自己的專業(yè)素質(zhì)，為以后進(jìn)一步開發(fā)應(yīng)用程序打下基礎(chǔ)。實驗三 LR(1)分析法一實驗原理LR（1）分析法實驗設(shè)計及算法(1)總控程序，也可以稱為驅(qū)動程序。對所有的 LR 分析器總控程序都是相同的。 (2)分析表或分析函數(shù)

4、，不同的文法分析表將不同，同一個文法采用的 LR 分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分析器的動作就是由棧頂狀態(tài)和當(dāng)前輸入符號所決定。二、程序結(jié)構(gòu)LR 分析器由三個部分組成：其中:SP 為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉(zhuǎn)換表用 GOTOi，X=j 表示，規(guī)定當(dāng)棧頂狀態(tài)為i，遇到當(dāng)前文法符號為X 時應(yīng)轉(zhuǎn)向狀態(tài)j，X 為終結(jié)符或非終結(jié)符。ACTIONi，a規(guī)定了棧頂狀態(tài)為 i 時遇到輸入符號a 應(yīng)執(zhí)行。動作有四種可能：(1)移進(jìn)：ac

5、tioni，a= Sj：狀態(tài)j 移入到狀態(tài)棧，把a(bǔ) 移入到文法符號棧，其中i,j 表示狀態(tài)號。歸約：actioni，a=rk：當(dāng)在棧頂形成句柄時，則歸約為相應(yīng)的非終結(jié)符A，即文法中有A- B 的產(chǎn)生式，若 B 的長度為 R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R 個符號，即棧指針SP 減去 R，并把A 移入文法符號棧內(nèi)， j=GOTOi,A移進(jìn)狀態(tài)棧，其中 i 為修改指針后的棧頂狀態(tài)。接受 acc:當(dāng)歸約到文法符號棧中只剩文法的開始符號S 時，并且輸入符號串已結(jié)束即當(dāng)前輸入符是#，則為分析成功。報錯:當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文

6、法能接受的符號串。實驗結(jié)果實驗總結(jié)本次實驗中,我采用 C#語言完成代碼的編寫，主要是為了實現(xiàn)界面顯示，通過構(gòu)造 LR(1)分析程序，利用它進(jìn)行語法分析，判斷給出的符號串是否為該文法識別的句子。本次實驗唯一讓我遺憾的是，本次試驗中分析表的實現(xiàn)未能實現(xiàn)自動產(chǎn)生，但整體上來說，還是滿意的，因為，經(jīng)過本次實驗，我對 LR(1)文法的功能了解的更加清楚，了解了 LR（1）分析方法是嚴(yán)格的從左向右掃描和自底向上的語法分析方法，同時讓我對的理解更加深透，這充分證明我一貫的觀點(diǎn)：動手實踐是鞏固知識的最佳途徑。雖然課程結(jié)束了，但是我對編譯的熱情不會，我會繼續(xù)努力，爭取以后做出好的編譯系統(tǒng)。附錄：實驗一源代碼：#

7、include #include #include#includeusing namespatd;char*key341=main,prf,short,long,float,double,char,struct,scanf,enum,typedef,const,unsigned,signed,or,sic,volatile,void,if,then,else,switch,case,for,do,while,goto,continue,break,default,sizeof,return;/關(guān)鍵字 作為 表 1char*symbol271=+,-,*,/,%,+,-,+=,-=,*=,/算數(shù)

8、運(yùn)算符 作為 表 3 (從 0 到 9) /=,=,=,!=,=,=,/關(guān)系運(yùn)算符 作為 表 4 (從 10 到 16) (, ),:,;/分界符 作為 表 2 (17 到 25)/常量類別為 5標(biāo)識符類別為 6char ch;=0;string strToken; pText=0; line=1;char fileName30;/存放讀進(jìn)的源程序字符/存放單詞的字符串/搜索指示器 文件指針double strLine10010;search(char ch)i; for(i=0;i27;i+)if(*symboli0=ch) /!strstr(symboli,s) return i;retu

9、rn -1;/刪除字符串、字符數(shù)組左邊空格 void strLTrim(char* str)i,j; n=0;n=strlen(str)+1; for(i=0;in;i+)if(stri!= )/找到break;第一個非空格位置/以第一個非空格字符為首字符移動字符串for(j=0;j=a &ch=A &ch=0 &ch=9) return true;return false;FindInSymbol(char* str)for(i=0;i27;i+)if(strcmp(symboli0,str)=0)return i;return -1;bool ReadFileToArray(double

10、strLine10010)/讀文本文件數(shù)據(jù)到數(shù)組，返回數(shù)組及其長度FILE *pFile, *pf; char str1000; char strTemp10;char* p;/定義 kmeans 的文件指針/存放讀出一行文本的字符串/判斷是否注釋行pf=fopen(fileName,r);if(!pf)cout錯誤：文件fileName打開失敗。endl; return false;cout要分析的語句：endl;while(fgets(str,1000,pf)!=NULL)coutstr;coutendlendl;cout.width(8);cout單詞; cout.width(10);c

11、out二元序列;coutt類型;couttt=0&n=10)couttokent(3 ,token)tt算數(shù)運(yùn)算符t(line,)=11&n=17)couttokent(4 ,token)tt關(guān)系運(yùn)算符t(line,)=18&n=26)couttokent(2 ,token)tt分界符tt(line,)endl;elsecouttokent(ERROR ,token)tERRORtt(line,)endl;elseif(IsDigit()i=0;while(IsDigit()&i=strlen(token)couttokent(5,atoi(token)tt常量tt(line,)endl;el

12、secouttokent(ERROR ,token)tERRORtt(line,)endl;elsefor(i=0;i33;i+)if(strcmp(token,keyi0)=0) flag=true;if(flag)couttokent(1 ,token;cout.width(4);cout)ttt(line,)endl;elsep=token; j=0;while(j=strlen(token)/couttokent( 6 ,token;cout.width(4); cout)t標(biāo)識符tt(line,)endl;elsecouttokent(ERROR ,token)tERRORtt(li

13、ne,)endl;+=strlen(token);token = strtok(NULL, );line+;=0;fclose(pFile); /關(guān)閉文件 return true;void choice()i;cout.setf(ios:left);/控制左對齊輸出 cout表 1 關(guān)鍵字表endl; for(i=0;i0&i%5=0) coutendl;cout.width(4);couti; cout.width(10);coutkeyi0;coutendlendl;cout表 2 分界符表endl; for(i=18;i0&i%3=0) coutendl;cout.width(4);co

14、uti-17; cout.width(10);coutsymboli0;coutendlendl;cout表 3 算術(shù)運(yùn)算符表endl; for(i=0;i0&i%3=0) coutendl;cout.width(4);couti; cout.width(10);coutsymboli0coutendlendl;cout表 4 關(guān)系運(yùn)算符表endl; for(i=11;i0&i%3=0) coutendl;cout.width(4);couti-10; cout.width(10);coutsymboli0;coutendl;main()choice();prf(Please Input fi

15、leName(.txt): );gets(fileName);/ 輸入文件名.txtif(!ReadFileToArray(strLine)/fileName, exit(0);system(pause);return 0;實驗二源代碼：#include #include #include #include#includeusing namespatd;/用于指向輸入輸出文件的指針 FILE *inparse,*outparse,*inscan;/用于接收輸入輸出文件名char inparsefile300,outparsefile300,inscanfile300;/定義產(chǎn)生式的語法集結(jié)構(gòu)

16、typedef structchar formula200; /產(chǎn)生式grammarElement;grammarElement gramOldSet200;/原始文法的產(chǎn)生式集 grammarElement gramNewSet200;/消除左遞歸后文法的產(chǎn)生式集/變量定義grammarNum=0; Pcount=0; startSymbol; terSymbol200; non_ter200; allSymbol400; leftStr200;rightStr200200;/原始的產(chǎn)生式數(shù)目/分解的產(chǎn)生式的個數(shù)/開始符號/消除左遞歸前 終結(jié)符號/消除左遞歸前 非終結(jié)符號/所有符號/消除左遞

17、歸后產(chǎn)生式左部(不包括-)/消除左遞歸后產(chǎn)生式右部(不包括-)char char char char charcharchar char char到 char char char char char charcharSET100100;followSET100100;/各產(chǎn)生式右部的集合/各產(chǎn)生式左部的 FOLLOW 集合single100100;/所有單個符號的集合,函數(shù) findSingle(i)用selectSET100100; tempFOLLOW100;ForFollow100; ed100;followed100;epsilon100; tempEpsilon100;/各單個產(chǎn)生式

18、的 SELECT 集合/求 FOLLOW 集合時使用/求 FOLLOW 時存放某一符號串的集合/求各符號的是否已求過,0 和 1 表示其狀態(tài)各符號的 FOLLOW 是否已求過,0 和 1 表示其狀態(tài)可直接推出()的符號someDerivateEpsilon()時使用,標(biāo)識此字符已查找其是否可推出空字validity=1; isLL1=1; M200200;char choice;/表示輸入文法是否有效/表示輸入文法是否為 LL(1)文法/分析表/用戶輸入時使用/設(shè)置彩色文字void setcolor(unsigned short ForeColor=4,unsigned short BackG

19、roundColor=0)HANDLE hCon=GetStdHandle(STD_OUTPUT_HANDLE);SetConsoleTextribute(hCon,ForeColor|BackGroundColor);/查找字符是否在指定字符串中bool FindChar(char ch,char *p)i; if(strlen(p)=0)return false;for(i=0;i90)return($);/如果大寫字母已經(jīng)用完,出錯 return(ch);void DirectLetfRecursive(char *poi,j; m=0,n=3;char temp20,ch;)for(j

20、=0;j/此下 11 行為本人自己調(diào)整，為了在同一個函數(shù)里面處理所有的產(chǎn)生式（包括左遞歸和不是左遞歸）j=n+1; ch=get_Char(); if(ch=$)cprf(消除左遞歸時出錯.原因:沒有足夠的符號(字母)可用.n);fprf(outparse,消除左遞歸時出錯.原因:沒有足夠的符號(字母)可用.n);system(pause);exit(0);i=strlen(non_ter); non_teri=ch; non_teri+1=0;while(poj!=|&poj!=0)tempm+=poj+;leftStrPcount=po0;rightStrPcount0=ch; right

21、StrPcount1=0; Pcount+; leftStrPcount=ch;memcpy(rightStrPcount,temp,m); rightStrPcountm=ch; rightStrPcountm+1=0; m=0;Pcount+;if(poj=|)n=j+1;leftStrPcount=ch; rightStrPcount0=; rightStrPcount1=0;Pcount+;else/如果|后的首符號和左部不同-A-ABa|Cc j=n;while(poj!=|&poj!=0)tempm+=poj+;leftStrPcount=po0;memcpy(rightStrPc

22、ount,temp,m); rightStrPcountm=0;m=0;Pcount+;if(poj=|)n=j+1;/ 最終的產(chǎn)生式void lastProduce()i;for(i=0;i; strcat(gramNewSeti.formula,rightStri);/*從文件讀入一個文法文法中出現(xiàn)的終結(jié)符和非終結(jié)符，并將文法的產(chǎn)生式進(jìn)行分解（并消除左并且遞歸）*/void getGrammar(char *t,char *n,char *leftStr,char rightStr200200)char char charcharNTtmp; rightTmp200;Vn200;/非終結(jié)符

23、集 non-terSymbol setVt200;/終結(jié)符集 terSymbol settmpIndex;/產(chǎn)生式的數(shù)目vtIndex,vnIndex; i,j,k;vtLen,vnLen;/終結(jié)符,非終結(jié)符 char p200200;/保存產(chǎn)生式 tmpIndex=0;vtIndex=0; vnIndex=0; while(!feof(inparse)if(fscanf(inparse,%c-%srn,&NTtmp,&rightTmp)!=2)validity=0;break;/產(chǎn)生式無效if(tmpIndex=0)startSymbol=NTtmp; /開始符號 如 SgramOldSet

24、tmpIndex.formula0=NTtmp; gramOldSettmpIndex.formula1=-; gramOldSettmpIndex.formula2=;strcat(gramOldSettmpIndex.formula,rightTmp);strcpy(ptmpIndex,gramOldSettmpIndex.formula); tmpIndex+;for(i=0;i=65&rightTmpi=90|rightTmpi=|)/(如果是終結(jié)符)for(j=0;j=65&rightTmpi=90)for(k=0;kvnIndex;k+) if(rightTmpi=Vnk)brea

25、k;if(k=vnIndex) /擴(kuò)展非終結(jié)符集合VnvnIndex=rightTmpi; vnIndex+; i+;VtvtIndex=0;VnvnIndex=0; vtLen=vtIndex; vnLen=vnIndex;grammarNum=tmpIndex;memcpy(n,Vn,vnLen);/求得的非終結(jié)符保存到 n,n 指向 non_termemcpy(t,Vt,vtLen);/終結(jié)符 terSymbolfor(i=0;igrammarNum;i+)prf(讀入的產(chǎn)生式 %d:t%sn,i+1,gramOldSeti.formula);fprf(outparse,讀入的產(chǎn)生式 %

26、d:t%sn,i+1,gramOldSeti.formula);for(i=0;i=grammarNum-1;i+)/分解文法的各產(chǎn)生式DirectLetfRecursiv);/分解所有產(chǎn)生式if(pi3=pi0) /如果是左遞歸文法DirectLetfRecursiv); /分解含有左遞歸的產(chǎn)生式elsenonLeftRecursiv);*/ 檢查讀入文法的正確性 checkproduce void checkP()i,j; for(i=0;i=Pcount-1;i+)if(!FindChar(leftStri,non_ter)pr fpr prfprf(n 文法錯誤.n); f(outpa

27、rse,n 文法錯誤.n);f(原因:非終結(jié)符 %c 不在非終結(jié)符集合中!n,leftStri);f(outparse, 原 因 : 非 終 結(jié) 符%c 不 在 非 終 結(jié) 符 集 合中!n,leftStri);prf(n 按回車鍵結(jié)束.);system(pause);exit(0);for(j=0;j=65&rightStrij=90&!FindChar(rightStrij,leftStr) /原來的程序的條件！FindChar(rightStrij,leftStr)/判斷右邊的當(dāng)前字符 如果是非終結(jié)符 并且出現(xiàn)在左部的非終結(jié)符集合中，則出錯；prfpr prf(n 文法錯誤.n);f(o

28、utparse,n 文法錯誤.n);f( 原 因 : 非 終 結(jié) 符%c 未 曾 在 產(chǎn) 生 式 左 部 出現(xiàn)!n,rightStrij);fprf(outparse, 原因 : 非終結(jié)符 %c 未曾 在產(chǎn)生式左部出 現(xiàn)!n,rightStrij);prf(n 按回車鍵結(jié)束.);system(pause);exit(0);/連接符號 destination 為目標(biāo)符號串 source 為源符號串type 為真是空字并入目串否則不并入void join(char *destination,char *source,bool type)i,j;for(i=0;i=()strlen(source)-

29、1;i+)if(type=false&sourcei=);elsefor(j=0;j+)if(j()strlen(destination)&sourcei=destinationj)break; if(j=()strlen(destination)destinationj=sourcei; destinationj+1=0;break;/求所有能直接推出()空字的符號結(jié)果保存到 epsilon中void allHasEpsilon(char ch) /參數(shù) ch 是此程序中所定義的的空字char temp10; i;for(i=0;i=Pcount-1;i+)if(rightStri0=ch&

30、strlen(rightStri)=1)temp0=leftStri; temp1=0; join(epsilon,temp,true);someDerivateEpsilon(char c)/求某一符號能否推出空字i,j,k,result=1,mark=0; char temp20;temp0=c;temp1=0;joempEpsilon,temp,true);if(FindChar(c,epsilon) return(1);for(i=0;i+)if(i=Pcount)return(0); if(leftStri=c)/找一個左部為 c 的產(chǎn)生式j(luò)=strlen(rightStri);/j

31、 為 c 所在產(chǎn)生式右部的長度if(j=1&FindChar(rightStri0,epsilon) return(1);else if(j=1&FindChar(rightStri0,terSymbol) return(0);elsefor(k=0;k=j-1;k+) if(FindChar(rightStrik,tempEpsilon)mark=1; if(mark=1)continue; elsefor(k=0;k=j-1;k+)result*=someDerivateEpsilon(rightStrik);if(result=0&iPcount) continue;else if(re

32、sult=1&iPcount)return(1);void findSingle(i)/i 為符號在所有輸入符號中的序號char X,temp20; j,k,m;X=allSymboli; char ch=;/求所有能直接推出()空字的符號,結(jié)果保存到 epsilon中allHasEpsilon(ch);if(FindChar(X,terSymbol)/若為終結(jié)符-XVT，則(X)=Xsinglesinglei0=X;i1=0;else if(FindChar(X,non_ter)for(j=0;j=Pcount-1;j+)if(leftStrj=X)/若 X 為非終結(jié)符/j 為在所有產(chǎn)生式中

33、的序列if(FindChar(rightStrj0,terSymbol)|rightStrj0=)temp0=rightStrj0;temp1=0;join(singlei,temp,true);else if(FindChar(rightStrj0,non_ter)/產(chǎn)生式右部第一個字符為非終結(jié)符if(rightStrj0=X) continue;for(k=0;k+)if(allSymbolk=rightStrj0)break;/求當(dāng)前非終結(jié)符在所有字符集中的位置 kif(edk=0)/5-5-2findSingle(k);edk=1;/標(biāo)識其為查找狀態(tài)join(single for(k=

34、0;k=(i,singlek,false);)strlen(rightStrj)-1;k+)tempEpsilon0=0;/存放到一個臨時數(shù)組里,標(biāo)識此字符已查找其是否可推出空字if(someDerivateEpsilon(rightStrjk)=1&k=0)SETi0=;/標(biāo)識右部符號串的長度/如果右部為單個符號(長度為 1)/右部符號串第一個字符為空字/把加入到當(dāng)前字符的集SETi1=0;elseForFollow0=;ForFollow1=0;elsefor(j=0;j+)if(allSymbolj=p0)/求右部符號的第一個字符 p0在所有字符集中的位置 jbreak; if(i=0)

35、memcpy(SETi,singlej,strlen(singlej)=0;j);SETistrlen(singleelsememcpy(ForFollow,singlej,strlen(singlej)=0;j);ForFollowstrlen(singleelsefor(j=0;j+)/如果右部為多個符號if(allSymbolj=p0) break;if(i=0)join( elsejoin(SETi,singlej,false);ForFollow,singlej,false);for(k=0;k=length-1;k+)tempEpsilon0=0; /tempEpsilon 是全局

36、變量if(someDerivateEpsilon(pk)=1&k=0)join( elsejoin(SETi,singlem,false);ForFollow,singlem,false);else if(someDerivateEpsilon(pk)=1&k=length-1)temp0=;temp1=0; if(i=0)join( elsejoin(SETi,temp,true);ForFollow,temp,true);else if(someDerivateEpsilon(pk)=0) break;void FOLLOW(i)j,k,m,n,result=1; char X,temp2

37、0; X=non_teri; temp0=X;temp1=0;/X 為待求的非終結(jié)符joempFOLLOW,temp,false);if(X=startSymbol)temp0=#;temp1=0; join(followSETi,temp,false);for(j=0;j=Pcount-1;j+)if(FindChar(X,rightStrj)for(k=0;k+)if(rightStrjk=X) break;for(m=0;m+)if(allSymbolm=leftStrj) break;if(k=()strlen(rightStrj)-1)if(FindChar(allSymbolm,t

38、empFOLLOW)join(followSETi,followSETm,false); continue;if(followedm=0)FOLLOW(m);followedm=1;join(followSETi,followSETm,false);elsefor(n=k+1;n=()strlen(rightStrj)-1;n+)tempEpsilon0=0;result*=someDerivateEpsilon(rightStrjn);if(result=1)if(FindChar(allSymbolm,tempFOLLOW)join(followSETi,followSETm,false)

39、; continue;if(followedm=0)FOLLOW(m);followedm=1;join(followSETi,followSETm,false);/FOLLOW(A)FOLLOW(B)for(n=k+1;n=()strlen(rightStrj)-1;n+)tempn-k-1=rightStrjn;tempstrlen(rightStrj)-k-1=0;(-1,temp); join(followSETi,空元素加入到 FOLLOW(B)中/求()ForFollow,false);/把()中所有非followedi=1;/標(biāo)識當(dāng)前要求的非終結(jié)符的 FOLLOW 集已求過/*判

40、斷讀入文法是否為一個 LL(1)文法判斷方法:具有相同左部的規(guī)則的 SELECT 集兩兩不相交*/judgeLL1()i,j,length,result=1; char temp100; for(j=0;j=99;j+)SETj0=0;followSETj0=0;/初始化singlej0=0;selectSETj0=0; ForFollowj=0;tempj=0;edj=0; /用來該字符的集是否已求過.1 表示已求,0 表示未求followedj=0;/用來該字符的FOLLOW 集是否已求過.1 表示已求,0 表示未求for(j=0;j=()strlen(allSymbol)-1;j+)fi

41、ndSingle里(j);/ 求單個符號的集合, 結(jié)果保存在singlepr fprf(n 單個符號的集合:n);f(outparse,n 單個符號的集合:n);for(j=0;j=()strlen(allSymbol)-1;j+)prf(t( %c ) = %s n,allSymbolj,singlej);fprf(outparse,t( %c ) = %s n,allSymbolj,singlej);prfprf(n 可推出空字的非終結(jié)符:%s,epsilon);f(outparse,n 可推出空字的非終結(jié)符:%s,epsilon);/求集for(i=0;i=Pcount-1;i+)(i,

42、rightStri);/求 FOLLOW 集for(j=0;j=()strlen(non_ter)-1;j+)if(tempFOLLOWj=0)tempFOLLOW0=0; FOLLOW(j);/打印各產(chǎn)生式右部符號串的集prf(n 消除左遞歸后各產(chǎn)生式右部符號串的集:n);fprf(outparse,n 消除左遞歸后各產(chǎn)生式右部符號串的集:n);for(i=0;i=Pcount-1;i+)prf(t( %s ) = %s n,rightStri,SETi);fprf(outparse,t( %s ) = %s n,rightStri,SETi);/打印各非終結(jié)符 FOLLOWprf(n 消除

43、左遞歸后各非終結(jié)符的 FOLLOW 集:n);fprf(outparse,n 消除左遞歸后各非終結(jié)符的 FOLLOW 集:n);for(i=0;i=()strlen(non_ter)-1;i+)prf(tFOLLOW( %c ) = %s n,non_teri,followSETi);fprf(outparse,tFOLLOW( %c ) = %s n,non_teri,followSETi);/求每一產(chǎn)生式的 selectsetfor(i=0;i=Pcount-1;i+) /對所有的產(chǎn)生式掃描一遍join(selectSETi,SETi,false);for(j=0;j=()strlen(r

44、ightStri)-1;j+)result*=someDerivateEpsilon(rightStrij);if(strlen(rightStri)=1&rightStri0=)result=1; if(result=1)for(j=0;j+)if(allSymbolj=leftStri) break;join(selectSETi,followSETj,false);/打印每一產(chǎn)生式的 selectset 集prf(n 消除左遞歸后各產(chǎn)生式的 SELECT 集:n);fprf(outparse,n 消除左遞歸后各產(chǎn)生式的 SELECT 集:n);for(i=0;i=Pcount-1;i+)

45、prf(tSELECT( %s ) = %s n,gramNewSeti.formula,selectSETi);fprf(outparse,tSELECT(%s)= %s n,gramNewSeti.formula,selectSETi);prf(n);fprf(outparse,n);/判斷輸入文法是否為 LL(1)文法 memcpy(temp,selectSET0,strlen(selectSET0); tempstrlen(selectSET0)=0; for(i=1;i=Pcount-1;i+)length=strlen(temp); if(leftStri=leftStri-1)j

46、oemp,selectSETi,true);if(strlen(temp),則 MX,a=X-,其中 aVt#M 中不能由 1)定義的元素均置為空(-1 表示出錯)*/void MM()i,j;X;a;/X 表示當(dāng)前產(chǎn)生式左部在非終結(jié)符數(shù)組中的位置/a 表示在當(dāng)前產(chǎn)生式的 SELECT 集中的位置/初始化分析表,全部置為空(-1)for(i=0;i=()strlen(non_ter);i+)for(j=0;j=()strlen(terSymbol)+1;j+)Mij=-1;i=strlen(terSymbol); terSymboli=#; terSymboli+1=0; for(i=0;i=

47、Pcount-1;i+)for(X=0;X+)if(non_terX=leftStri) break;for(j=0;j=()strlen(selectSETi)-1;j+)if(FindChar(selectSETij,terSymbol)for(a=0;a+)if(terSymbola=selectSETij) break;MXa=i;/總控程序算法void syntax()l:if(inscan=fopen(inscanfile,rb)=NULL)prf(請輸入詞法分析文件名（包括路徑）:);scanf(%s,inscanfile);goto l;i=0,j,k,m,n,o,p,q; l

48、=0;ch; Stack200;temp200200;sentence200; TopChar; isshow=0;matchchar;char char char charchar/分析句子當(dāng)前指向的字符/定義存放文法符號的棧/保存要分析的句子/棧頂符號/判斷是否要輸出產(chǎn)生式.0 表示不輸出,1 表示輸出/當(dāng)前匹配的字符char/讀詞法分析文件里的單詞類型while(!feof(inscan)fscanf(inscan,%st%srn,&sentence); strcpy(tempi+,sentence);j=i; for(i=0;ij;i+)for(k=0;k(/詞法分析文件里的行數(shù))st

49、rlen(tempi);k+)sentencel+=tempik;sentencel=0;Stack0=#; Stack1=startSymbol; Stack2=0;j=0; o=1;ch=sentencej;prfprf(步驟t 分析棧tt輸入串tt 所用產(chǎn)生式n);f(outparse,步驟t 分析棧tt輸入串tt 所用產(chǎn)生式n);prfprf(%dt%stt,o,Stack);f(outparse,%dt%stt,o,Stack);for(p=j;p,則僅將 X 從棧出);若 MX,a中為空,則表示出錯,調(diào)用相應(yīng)的出錯處理程序處理.*/if(FindChar(TopChar,terSy

50、mbol)if(TopChar!=ch)prf(語法分析失敗!該符號串不是文法的句型!n);fprf(outparse,語法分析失敗!該符號串不是文法的句型!n);prf(|-|n);system(pause);exit(0);else if(TopChar=#)prf(語法分析成功!該符號串是文法的句型.n);fprf(outparse,語法分析成功!該符號串是文法的句型.n);prf(|-|n);system(pause);exit(0);elseisshow=0; matchchar=sentencej; Stackstrlen(Stack)-1=0;j+;ch=sentencej;el

51、sefor(i=0;i+)if(non_teri=TopChar) break;for(k=0;k+)if(terSymbolk=ch) break;if(k=(pr fpr)strlen(terSymbol)f(詞法錯誤!n);f(outparse,詞法錯誤!n);system(pause);exit(0);if(Mik=-1)/MX,a中為空,則表示出錯-分析表提示出錯prf(語法錯誤!n);fprf(outparse,語法錯誤!n);system(pause);exit(0);else/若 MX,a中為一個規(guī)則,則m=Mik; if(rightStrm0=)isshow=1; Stack

52、strlen(Stack)-1=0;elseisshow=2; p=strlen(Stack)-1; q=p;for(n=strlen(rightStrm)-1;n=0;n-) Stackp+=rightStrmn;Stackq+strlen(rightStrm)=0;o+;prf(%dt%stt,o,Stack);fprf(outparse,%dt%stt,o,Stack);for(p=j;p=0;i-)prf(%c,rightStrmi);prf();fprf(outparse,ttt%s,gramNewSetm.formula);if(isshow=1)prf(ttt %s tt POP

53、,gramNewSetm.formula);if(isshow=0)prf(ttt%c 匹配tt POP,GETNEXT(I),matchchar);fprf(outparse,ttt%c 匹配tPOP,GETNEXT(I),matchchar);prf(n);fprf(outparse,n);fclose(inscan); fclose(outparse);/主函數(shù)main()i,j; strcpy(inparsefile, );strcpy(outparsefile, ); strcpy(inscanfile, );setcolor(10);prf(|文法文件里的規(guī)則格式為形如 E-E+T

54、|T 的產(chǎn)生式，如果左部字符可推出多條產(chǎn)|n);prf(|生式，即 E-E+T 和 E-T 寫法為：E-E+T|T 且文法的開始符號所在的產(chǎn)生式需寫在第|n);pr|n);prf(|一條。文法中的空字用代表！f(|-|nn); setcolor(11);lab1:if(inparse=fopen(inparsefile,rb)=NULL)prf(請輸入語法源程序文件名（包括路徑）n 如果在同一文件夾下,則只須輸入文件名:);scanf(%s,inparsefile); goto lab1;lab2:if (outparse=fopen(outparsefile,w)=NULL)prf(n 請輸

55、入語法分析輸出文件的文件名:);scanf(%s,outparsefile);goto lab2;getGrammar(terSymbol,non_ter,leftStr,rightStr); if(validity=0)pr prprf(n 讀入的文法無效!n);f(n 文法格式為: A-，其中 （VnVt）n); f(nPS:按回車結(jié)束本程序.);system(pause);exit(0);lastProduce();/消除左遞歸后的最終產(chǎn)生式pr fpr prfprf(n 消除左遞歸后的產(chǎn)生式總條數(shù) = %dn,Pcount); f(outparse,n 消除左遞歸后的產(chǎn)生式總條數(shù) =

56、%dn,Pcount); f(消除左遞歸后的產(chǎn)生式:n);f(outparse,消除左遞歸后的產(chǎn)生式:n);for(i=0;i=Pcount-1;i+)prf(t%sn,gramNewSeti.formula);fprf(outparse,t%sn,gramNewSeti.formula);prf(n 開始符號 = %c ,startSymbol);fprf(outparse,n 開始符號 = %c ,startSymbol);strcpy(allSymbol,non_ter);strcat(allSymbol,terSymbol);pr fpr pr fpr prfprf(n 所有符號 =

57、%s ,allSymbol); f(outparse,n 所有符號 = %s ,allSymbol); f(n 非終結(jié)符 = %s ,non_ter); f(outparse,n 非終結(jié)符 = %s ,non_ter); f(n 終 結(jié) 符 = %s n,terSymbol);f(outparse,n 終 結(jié) 符 = %s n,terSymbol);checkP(); if(validity=1)isLL1=judgeLL1(); if(isLL1=0)prf(n 輸入的文法不是一個有效的 LL(1)文法!n);fprf(outparse,n 輸入的文法不是一個有效的 LL(1)文法!n);s

58、ystem(pause);exit(0);elseMM();setcolor(10);prf(|-|n);prf(n 輸入的文法是一個有效的 LL(1)文法!n 分析表如下:n);fprf(outparse, 輸入的文法是一個有效的 LL(1) 文法!n 分析表如下:n);/ 輸出分析表prf(|- - - -|- - -t);fprf(outparse,|- - - -|- - -t);for(i=0;i=()strlen(terSymbol)-1;i+)prf(- - -t);fprf(outparse,- - -t);prf(|n);fprf(outparse,|n);prf(|t|t)

59、;fprf(outparse,|t|t);for(i=0;i()strlen(terSymbol);i+)prf(%ct,terSymboli);fprf(outparse,%ct,terSymboli);pr fpr prfprf(|n);f(outparse,|n); f(|- - - -|- - -t);f(outparse,|- - - -|- - -t);for(i=0;i=()strlen(terSymbol)-1;i+)prf(- - -t);fprf(outparse,- - -t);prf(|n);fprf(outparse,|n);for(i=0;i()strlen(non

60、_ter);i+)prf(| %ct|t,non_teri);fprf(outparse,| %ct|t,non_teri);for(j=0;j()strlen(terSymbol);j+)if(-1!=Mij)prfprf(%st,gramNewSetMij.formula);f(outparse,%st,gramNewSetMij.formula);elsepr fprf(t);f(outparse,t);prf(|n);fprf(outparse,|n);pr fprf(|- - - -|- - -t);f(outparse,|- - - -|- - -t);for(i=0;i=()st