遞歸下降分析程序.doc

1、一、實驗?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é)符，所以定義了五

2、個函數(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ù)

3、E()這個函數(shù)主要是根據(jù)文法中的E-TG，在E（）中調(diào)用了T（）和G（）來進行遞歸分析，這個就是構(gòu)造生成樹的一個分支。 int E() int f,t;/變量printf(E-TGt);/輸出根據(jù)的文法 flag=1; outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符f=T();if (f=0) return(0); /表示當前分析字符可由非終結(jié)符T推導(dǎo)出t=G(); if (t=0) return(0); /表示當前分析字符可由非終結(jié)符G推導(dǎo)出else return(1);2. 對非終結(jié)符G處理的函數(shù)G()這個函數(shù)主要是根據(jù)文法中G-+TG|-TG|，在

4、函數(shù)中調(diào)用了T()和G()函數(shù)。將當前字符和候選式的第一個字符進行匹配，如果匹配成功，就調(diào)用該候選式中涉及到得第一個非終結(jié)符對應(yīng)的函數(shù)，一次遞歸嵌套調(diào)用。如果不是由第一個候選式推出然后依次匹配剩下的候選式。int G() int f; if(ch=+) /當前字符式+ bi1=ch; printf(G-+TGt);/說明用的是第一個候選式e0=G;e1=;e2=;e3=+;e4=T;e5=G;e6=#; Compute ();/計算推導(dǎo)式 flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 ch=a+i1;/讀取當前字符的下一個字符 if (f

5、=0) return(0); /表示當前分析字符可由非終結(jié)符T推導(dǎo)出 t=G(); if (t=0) return(0); /表示當前分析字符可由非終結(jié)符G推導(dǎo)出 if(ch=-) /當前字符是-bi1=ch;printf(G-+TGt);/說明用的是第二個候選式e0=G;e1=;e2=;e3=+;e4=T;e5=G;e6=#; Compute();/輸出推導(dǎo)式 flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1;/讀取當前字符的下一個字符f=T();if (f=0) return(0); /表示當前分析字符可由非終結(jié)符T推導(dǎo)出G

6、();/判斷當前分析字符是否是非終結(jié)符G的一個產(chǎn)生式return(1);printf(G-t);e0=G;e1=;e2=;e3=;e4=#;Compute ();/推導(dǎo)式計算flag=1;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 return(1);3.對非終結(jié)符T處理的函數(shù)T()函數(shù)主要是根據(jù)文法中的T-FS,在函數(shù)中調(diào)用F()和S()，進行遞歸分析，也是構(gòu)造語法樹的一個分支。int T() int f,t;printf(T-FSt);/說明所用的推導(dǎo)式是T-FSe0=T;e1=;e2=;e3=F;e4=S;e5=#; Compute ();/推

7、導(dǎo)式計算flag=1;outDeduce ();/輸出字符串outputRemain ();/輸出剩余字符f=F();if (f=0) return(0);/表示當前分析字符可由非終結(jié)符F推導(dǎo)出t=S();/表示當前分析字符可由非終結(jié)符S推導(dǎo)出if (t=0) return(0);else return(1);4. 對非終結(jié)符S處理的函數(shù)S()函數(shù)的主要是文法要求S-*FS|/FS|，在函數(shù)中調(diào)用F()和S()函數(shù)。其實這個過程和對非終結(jié)符G的處理很類似，將當然字符與該非終結(jié)符的每個候選式的第一個字符進行匹配。比如當然字符為*，說明使用第一個候選式，然后調(diào)用F()和S()函數(shù)進行遞歸分析。如果

8、當前字符為/，就使用第二個候選式，然后也調(diào)用F()和S()函數(shù)進行遞歸分析。如果當前字符是在和G中的任何一個候選式的第一個字符都不匹配，就返回1,說明當然字符不能由非終結(jié)符G推出。int S()int f,t;if(ch=*) /當前字符是*bi1=ch;printf(S-*FSt);/說明使用的是第一個候選式e0=S;e1=;e2=;e3=*;e4=F;e5=S;e6=#;Compute ();/推導(dǎo)式計算flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1;/取出當前字符的下一個字符f=F();if (f=0) return(0

9、); /如果當然分析字符可由非終結(jié)符F推出t=S();if (t=0) return(0); /如果當然分析字符可由非終結(jié)符S推出 else return(1);if(ch=/) /當前字符是/bi1=ch;printf(S-*FSt);/說明使用的是第二個候選式e0=S;e1=;e2=;e3=*;e4=F;e5=S;e6=#;Compute ();/推導(dǎo)式計算flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1; /取出當前字符的下一個字符f=F();/如果當然分析字符可由非終結(jié)符F推出if (f=0) return(0);t=S

10、();/如果當然分析字符可由非終結(jié)符S推出if (t=0) return(0);else return(1); printf(S-t); e0=S;e1=;e2=;e3=;e4=#; Compute ();/推導(dǎo)式計算 flag=1; ai1=ch; outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 return(1); printf(S-t); e0=S;e1=;e2=;e3=;e4=#; output();/推導(dǎo)式計算 flag=1; ai1=ch; outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 return(

11、1);5.對非終結(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,就使用第二個候選式。int F() int f; if(ch=() /當前字符是（bi1=ch;printf(F-(E)t);/說明使用的是第一個候選式 e0=F;e1=;e2=;e3=(;e4=E;e5=);e6=#;Compute ();/推導(dǎo)式計算flag=0;ou

12、tDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1;/讀取下一個字符f=E();if (f=0) return(0); /如果當然分析字符可由非終結(jié)符E推出if(ch=) /當前字符是)bi1=ch;printf(F-(E)t);/說明使用的是第一個候選式 flag=0;outDeduce ();/輸出字符串 input1();/輸出剩余字符ch=a+i1;else printf(errorn);return(0); else if(ch=i) /當前字符是ibi1=ch;printf(F-it);/說明使用的是第二個候選式e0=F;e1=;e2=

13、;e3=i;e4=#;Compute ();/推導(dǎo)式計算flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1; else printf(errorn);return(0); return(1);四、測試結(jié)果這個程序測試時是往命令行中輸入一串字符串，來判斷該字符串是否是給出文法的一個句型，測試過程窗口中都詳細給了出來。這次我測試的字符串是“i+i*i#”。截圖如下：如果輸入的字符串不是文法的一個句型，窗口中會顯示error，說明輸入的字符串不正確。這里我測試的字符串是“i+E”，截圖如下：五、實習總結(jié)這是編譯原理的第二次實習，這次的實

14、習主要是實現(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)的過

15、程是很麻煩的，自己以后也會多多練習。附錄：總程序：#include #include#include#includechar a50 ,b50,d200,e10;/a存放輸入的字符串char ch;int n1,i1=0,flag=1,n=5;int E();int T();int G();int S();int F();void outDeduce();void outputRemain();void Compute();void main()/*遞歸分析*/ int f,p,j=0; char x; d0=E; d1=; d2=; d3=T; d4=G; d5=#; printf(*遞歸下

16、降分析器*n); printf(請輸入字符串(以#號結(jié)束)n); do scanf(%c,&ch); aj=ch; j+; while(ch!=#); n1=j; ch=b0=a0; printf(文法t分析串tt分析字符t剩余串n); f=E(); if (f=0) return; if (ch=#) printf(輸入字符串正確n); p=0; x=dp; else printf(errorn); getchar(); getchar(); return; printf(n); getchar(); getchar();int E() int f,t; printf(E-TGt); fla

17、g=1; outDeduce();/輸出分析串 outputRemain();/輸出剩余字符 f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1);int T() int f,t; printf(T-FSt); e0=T; e1=; e2=; e3=F; e4=S; e5=#; Compute(); flag=1; outDeduce(); outputRemain(); f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1);i

18、nt G() int f; if(ch=+) bi1=ch; printf(G-+TGt); e0=G; e1=; e2=; e3=+; e4=T; e5=G; e6=#; Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); printf(G-t); e0=G; e1=; e2=; e3=; e4=#; Compute(); flag=1; outDeduce(); outputRemain(); return(1);int S() int f,t

19、; if(ch=*) bi1=ch; printf(S-*FSt); e0=S; e1=; e2=; e3=*; e4=F; e5=S; e6=#; Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1); printf(S-t); e0=S; e1=; e2=; e3=; e4=#; Compute(); flag=1; ai1=ch; outDeduce(); outputRemain(); return(1);int F() int f; if(ch=() bi1=ch; printf(F-(E)t); e0=F; e1=; e2=; e3=(; e4=E; e5=); e6=#; Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=E(); if (f=0) return(0); if(ch=) bi1=ch;