遞歸下降分析程序

遞歸下降分析程序遞歸下降分析程序遞歸下降分析程序xxx公司遞歸下降分析程序文件編號：文件日期：修訂次數(shù)：第1.0次更改批準審核制定方案設(shè)計，管理制度一、實驗?zāi)康模焊鶕?jù)某一文法編制調(diào)試遞歸下降分析程序，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對遞歸下降分析法的理解。二、程序算法描述這次的實習主要是根據(jù)以下文法實現(xiàn)一個遞歸下降分析器，依據(jù)文法如下：（1）E->TG（2）G->+TG|－TG|ε（3）T->FS（4）S->*FS|/FS|ε（5）F->(E)|i在這個遞歸下降分析器程序中每一個非終結(jié)符E、G、T、S和F構(gòu)造相應(yīng)的遞歸函數(shù)，函數(shù)的名字表示文法左部的非終結(jié)符，函數(shù)中就是按文法中每個非終結(jié)符右部的候選式依次進行匹配，根據(jù)對輸入串的分析如果非終結(jié)符可以用其中的一個候選式替代就返回1，否則返回0。因為該文法中有五個非終結(jié)符，所以定義了五個函數(shù)，分別為E（），G（），T()，S()和F（）。當輸入一串字符串后，就對該字符串進行分析，首先從開始符號分析，所以首先調(diào)用E()函數(shù)，在E（）函數(shù)中會調(diào)用T（）和G(),就是每個非終結(jié)符的候選式中出現(xiàn)了哪個非終結(jié)符就調(diào)用哪個函數(shù)。所以，將字符串的第一個字符和E中的每個候選式匹配，如果成功就匹配輸入字符串的下一個字符，當最后剩下的字符為’#’時，匹配成功。其實這個工程就是構(gòu)造一個語法樹。程序總流程圖如下：圖1程序總流程圖三、關(guān)鍵性代碼這個工程的主要工作用五個非終結(jié)符生成的句子是否和輸入字符串匹配，所以主要的工作是函數(shù)E（），G（），T()，S()和F（）的編寫。1.對非終結(jié)符E處理的函數(shù)E()這個函數(shù)主要是根據(jù)文法中的E->TG，在E（）中調(diào)用了T（）和G（）來進行遞歸分析，這個就是構(gòu)造生成樹的一個分支。intE(){intf,t;對非終結(jié)符G處理的函數(shù)G()這個函數(shù)主要是根據(jù)文法中G->+TG|-TG|ε，在函數(shù)中調(diào)用了T()和G()函數(shù)。將當前字符和候選式的第一個字符進行匹配，如果匹配成功，就調(diào)用該候選式中涉及到得第一個非終結(jié)符對應(yīng)的函數(shù)，一次遞歸嵌套調(diào)用。如果不是由第一個候選式推出然后依次匹配剩下的候選式。intG(){intf; if(ch=='+'){非終結(jié)符T處理的函數(shù)T()函數(shù)主要是根據(jù)文法中的T->FS,在函數(shù)中調(diào)用F()和S()，進行遞歸分析，也是構(gòu)造語法樹的一個分支。intT(){intf,t; printf("T-->FS\t");對非終結(jié)符S處理的函數(shù)S()函數(shù)的主要是文法要求S->*FS|/FS|ε，在函數(shù)中調(diào)用F()和S()函數(shù)。其實這個過程和對非終結(jié)符G的處理很類似，將當然字符與該非終結(jié)符的每個候選式的第一個字符進行匹配。比如當然字符為‘*’，說明使用第一個候選式，然后調(diào)用F()和S()函數(shù)進行遞歸分析。如果當前字符為‘/’，就使用第二個候選式，然后也調(diào)用F()和S()函數(shù)進行遞歸分析。如果當前字符是在和G中的任何一個候選式的第一個字符都不匹配，就返回1,說明當然字符不能由非終結(jié)符G推出。intS(){ intf,t; if(ch=='*'){非終結(jié)符F處理的函數(shù)F()函數(shù)主要是根據(jù)文法中給出的F->(E)|i，在函數(shù)中調(diào)用E()。這個過程和前面對其他非終結(jié)符的處理差不多，都是根據(jù)候選式中涉及的非終結(jié)符調(diào)用相應(yīng)的函數(shù)。將當前字符和每一個候選式的第一個字符進行匹配，比如如果當然字符是‘（’，就使用第一個候選式，然后調(diào)用E()進行遞歸向下分析。如果當前字符是‘i’,就使用第二個候選式。intF(){intf; if(ch=='('){//當前字符是‘（’ b[i1]=ch;printf("F-->(E)\t");//說明使用的是第一個候選式 e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#'; Compute();//推導式計算 flag=0; outDeduce();//輸出字符串 outputRemain();//輸出剩余字符 ch=a[++i1];//讀取下一個字符 f=E(); if(f==0)return(0);//如果當然分析字符可由非終結(jié)符E推出 if(ch==')'){//當前字符是‘)’ b[i1]=ch;printf("F-->(E)\t");//說明使用的是第一個候選式 flag=0;outDeduce();//輸出字符串 input1();//輸出剩余字符 ch=a[++i1];} else{ printf("error\n"); return(0); }}elseif(ch=='i'){//當前字符是‘i’ b[i1]=ch;printf("F-->i\t");//說明使用的是第二個候選式 e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#'; Compute();//推導式計算 flag=0;outDeduce();//輸出字符串 outputRemain();//輸出剩余字符 ch=a[++i1];} else{printf("error\n");return(0);} return(1);}四、測試結(jié)果這個程序測試時是往命令行中輸入一串字符串，來判斷該字符串是否是給出文法的一個句型，測試過程窗口中都詳細給了出來。這次我測試的字符串是“i+i*i#”。截圖如下：如果輸入的字符串不是文法的一個句型，窗口中會顯示error，說明輸入的字符串不正確。這里我測試的字符串是“i+E”，截圖如下：五、實習總結(jié)這是編譯原理的第二次實習，這次的實習主要是實現(xiàn)一個遞歸下降分析器，主要就是根據(jù)一個文法，判斷用戶輸入的字符串是否是該文法的一個句型。這個實現(xiàn)的過程形象點就是構(gòu)造一個語法樹，從開始字符開始，將輸入字符串的第一個字符與文法中的非終結(jié)符的每個候選式的第一個字符進行匹配，成功后匹配下一個字符，直到字符串的所有字符都能匹配上。這次的實習的過程讓我想起了數(shù)據(jù)結(jié)構(gòu)上學到的樹的構(gòu)建，實現(xiàn)的代碼有的地方也參照了網(wǎng)上的程序，實現(xiàn)的過程中出現(xiàn)了很多錯誤，總之，最后還是實現(xiàn)了。實習中出現(xiàn)的錯誤有的是將過程沒有分析完整，也有的語法出現(xiàn)了錯誤，自己也請教了同學。通過這次的實習，自己對遞歸下降分析有了深入的認識，其實課本上的知識自己看的很簡單，但是實現(xiàn)的過程是很麻煩的，自己以后也會多多練習。附錄：總程序：#include<>#include<>#include<>#include<>chara[50],b[50],d[200],e[10];//a存放輸入的字符串charch;intn1,i1=0,flag=1,n=5;intE();intT();intG();intS();intF();voidoutDeduce();voidoutputRemain();voidCompute();voidmain()/*遞歸分析*/{intf,p,j=0;charx;d[0]='E';d[1]='=';d[2]='>';d[3]='T';d[4]='G';d[5]='#';printf("*************遞歸下降分析器******************\n");printf("請輸入字符串(以#號結(jié)束)\n");do{scanf("%c",&ch);a[j]=ch;j++;}while(ch!='#');n1=j;ch=b[0]=a[0];printf("文法\t分析串\t\t分析字符\t剩余串\n");f=E();if(f==0)return;if(ch=='#'){printf("輸入字符串正確\n");p=0;x=d[p];}else{printf("error\n");getchar();getchar();return;}printf("\n");getchar();getchar();}intE(){intf,t;printf("E--TG\t");flag=1;outDeduce();//輸出分析串outputRemain();//輸出剩余字符f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);}intT(){intf,t;printf("T--FS\t");e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#';Compute();flag=1;outDeduce();outputRemain();f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}intG(){intf;if(ch=='+'){b[i1]=ch;printf("G--+TG\t");e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#';Compute();flag=0;outDeduce();outputRemain();ch=a[++i1];f=T();if(f==0)return(0);G();return(1);}printf("G--^\t");e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';Compute();flag=1;outDeduce();outputRemain();return(1);}intS(){intf,t;if(ch=='*'){b[i1]=ch;printf("S--*FS\t");e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#';Compute();flag=0;outDeduce();outputRemain();ch=a[++i1];f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}printf("S--^\t");e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';Compute();flag=1;a[i1]=ch;outDeduce();outputRemain();return(1);}intF(){intf;if(ch=='('){b[i1]=ch;printf("F--(E)\t");e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#';Compute();flag=0;outDeduce();outputRemain();ch=a[++i1];f=E();if(f==0)return(0);if(ch==')'){b[i1]=ch;printf("F--(E)\t");flag=0;outDeduce();outputRemain();ch=a[++i1];}else{printf("error\n");return(0);}}elseif(ch=='i'){b[i1]=ch;printf("F--i\t");e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';Compute();flag=0;outDeduce();outputRemain();ch=a[++i1];}else{printf("error\n");return(0);}return(1);}voidoutDeduce(){intj=0;for(;j<=i1-flag;j++)printf("%c",b[j]);/*輸出分析串*/printf("\t\t");