北郵編譯原理LL(1)語法分析程序.docx

LL(1)語法分析程序2010211306班 趙雪瑩（10211310）語法分析程序：該語法分析程序?qū)崿F(xiàn)對算術(shù)表達式的語法分析，并且在對輸入表達式進行分析的過程中，輸出所采用的產(chǎn)生式。該程序使用的是LL（1）語法分析程序，為給定文法構(gòu)造預(yù)測分析表，并通過預(yù)測分析表對輸入的表達式進行預(yù)測分析，并將棧頂狀態(tài)和預(yù)測分析過程詳細輸出，如果匹配成功則接受，如果匹配不成功則返回錯誤信息。給定文法的產(chǎn)生式：E-E+T | E-T | TT-T*F | T/F | FF- id | (E) | num源代碼：#include #include #include #include #include using namespace std;struct Node1 char vn; char vt; char s12;MAP22;/存儲分析預(yù)測表每個位置對應(yīng)的終結(jié)符，非終結(jié)符，產(chǎn)生式 int k;char G1212=E-TR,R-+TR,R-TR,R-e,T-FW,W-*FW,W-/FW,W-e,F-(E),F-i,F-n;/存儲文法中的產(chǎn)生式 ,用R代表E,W代表T,e代表空char VN6=E,R,T,W,F;/存儲非終結(jié)符 char VT9=i,n,+,-,*,/,(,),#;/存儲終結(jié)符 char FOLLOW1212=(,i,n,+,-,),#,(,i,n,*,/,+,-,),#,(,i,n;/存儲文法中每個產(chǎn)生式對應(yīng)的FOLLOW集合 char Right128=-TR,-+TR,-TR,-e,-FW,-*FW,-/FW,-e,-(E),-i,-n;stack stak,stak1,stak2;bool compare(char *a,char *b) int i,la=strlen(a),j,lb=strlen(b); for(i=0;ila;i+) for(j=0;jlb;j+) if(ai=bj) return 1; return 0;char *Find(char vn,char vt) int i; for(i=0;ik;i+) if(MAPi.vn=vn & MAPi.vt=vt) return MAPi.s; return error;char * Analyse(char * word) char p,c,action10,output10; int i=1,l=strlen(word),j,k=0,l_act,m,x; printf(_n); printf(n 對符號串%s的分析過程n,word); for(x=0;xl;x+)/把用字母數(shù)字表示的輸入串轉(zhuǎn)換為token序列的表示方法 c=wordx; if(c=a)|(c=A) wordx=i; else if(c=0&c=9) wordx=n; else wordx=c; while(!stak.empty()/判斷棧中是否為空，若不空就將棧頂元素與分析表匹配進行相應(yīng)操作 stak.pop(); stak.push(#);/棧底標(biāo)志 stak.push(E);/起始符號先入棧 printf( 步驟 棧頂元素 輸入串 推到所用產(chǎn)生式或匹配n); p=stak.top(); while(p!=#)/查預(yù)測分析表將棧頂元素進行匹配，若棧頂元素與輸入串匹配成功則向前匹配，否則生成式反序入棧 printf(%7d ,i+); p=stak.top();/從棧中彈出一個棧頂符號，由p記錄并輸出 stak.pop(); printf(%6c ,p); for(j=k,m=0;j1;j-) stak.push(actionj); if(strcmp(output,#)!=0)/匹配不成功 return ERROR; int main () freopen(in.txt,r,stdin); char source100; int i,j,flag,l,m; printf(n*R代表E,W代表T,e代表空*nn); printf(算術(shù)表達式對應(yīng)的文法產(chǎn)生式如下：n); for(i=0;i8;i+) printf( %sn,Gi); printf(_n); printf(n該文法的FOLLOW集如下：n); /手動生成集合 for(i=0;i8;i+) printf( FOLLOW(%s) = %s n,Gi,FOLLOWi); printf(_n); for(i=0,k=0;i11;i+)/通過集合生成預(yù)測分析表 l=strlen(FOLLOWi); for(j=0;jl;j+=2) MAPk.vn=Gi0; MAPk.vt=FOLLOWij; strcpy(MAPk.s,Righti); k+; printf(n表達式文法的預(yù)測分析表如下：nn); printf( ); for(i=0;i9;i+) printf(%7c,VTi); printf(n); for(i=0;i5;i+) printf( -n); printf(%7c,VNi); for(j=0;j9;j+) for(m=0;msource)/輸入源文件串進行預(yù)測分析 printf(n分析結(jié)果：%snn,Analyse(source); while(1); return 0;將其改寫LL（1）文法：