遞歸下降分析程序.doc

1、一、實(shí)驗(yàn)?zāi)康模?根據(jù)某一文法編制調(diào)試遞歸下降分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次實(shí)驗(yàn)的目的主要是加深對(duì)遞歸下降分析法的理解。二、程序算法描述這次的實(shí)習(xí)主要是根據(jù)以下文法實(shí)現(xiàn)一個(gè)遞歸下降分析器，依據(jù)文法如下：（1）E-TG（2）G-+TG|TG|（3）T-FS（4）S-*FS|/FS|（5）F-(E)|i在這個(gè)遞歸下降分析器程序中每一個(gè)非終結(jié)符E、G、T、S和F構(gòu)造相應(yīng)的遞歸函數(shù)，函數(shù)的名字表示文法左部的非終結(jié)符，函數(shù)中就是按文法中每個(gè)非終結(jié)符右部的候選式依次進(jìn)行匹配，根據(jù)對(duì)輸入串的分析如果非終結(jié)符可以用其中的一個(gè)候選式替代就返回1，否則返回0。因?yàn)樵撐姆ㄖ杏形鍌€(gè)非終結(jié)符，所以定義了五

2、個(gè)函數(shù)，分別為E（），G（），T()，S()和F（）。當(dāng)輸入一串字符串后，就對(duì)該字符串進(jìn)行分析，首先從開(kāi)始符號(hào)分析，所以首先調(diào)用E()函數(shù)，在E（）函數(shù)中會(huì)調(diào)用T（）和G(),就是每個(gè)非終結(jié)符的候選式中出現(xiàn)了哪個(gè)非終結(jié)符就調(diào)用哪個(gè)函數(shù)。所以，將字符串的第一個(gè)字符和E中的每個(gè)候選式匹配，如果成功就匹配輸入字符串的下一個(gè)字符，當(dāng)最后剩下的字符為#時(shí)，匹配成功。其實(shí)這個(gè)工程就是構(gòu)造一個(gè)語(yǔ)法樹(shù)。 程序總流程圖如下：圖1 程序總流程圖三、關(guān)鍵性代碼這個(gè)工程的主要工作用五個(gè)非終結(jié)符生成的句子是否和輸入字符串匹配，所以主要的工作是函數(shù)E（），G（），T()，S()和F（）的編寫(xiě)。1. 對(duì)非終結(jié)符E處理的函數(shù)

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

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

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

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

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

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

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

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

11、1);5.對(duì)非終結(jié)符F處理的函數(shù)F()函數(shù)主要是根據(jù)文法中給出的F-(E)|i ，在函數(shù)中調(diào)用E()。這個(gè)過(guò)程和前面對(duì)其他非終結(jié)符的處理差不多，都是根據(jù)候選式中涉及的非終結(jié)符調(diào)用相應(yīng)的函數(shù)。將當(dāng)前字符和每一個(gè)候選式的第一個(gè)字符進(jìn)行匹配，比如如果當(dāng)然字符是（，就使用第一個(gè)候選式，然后調(diào)用E()進(jìn)行遞歸向下分析。如果當(dāng)前字符是i,就使用第二個(gè)候選式。int F() int f; if(ch=() /當(dāng)前字符是（bi1=ch;printf(F-(E)t);/說(shuō)明使用的是第一個(gè)候選式 e0=F;e1=;e2=;e3=(;e4=E;e5=);e6=#;Compute ();/推導(dǎo)式計(jì)算flag=0;ou

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

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

14、習(xí)主要是實(shí)現(xiàn)一個(gè)遞歸下降分析器，主要就是根據(jù)一個(gè)文法，判斷用戶(hù)輸入的字符串是否是該文法的一個(gè)句型。這個(gè)實(shí)現(xiàn)的過(guò)程形象點(diǎn)就是構(gòu)造一個(gè)語(yǔ)法樹(shù)，從開(kāi)始字符開(kāi)始，將輸入字符串的第一個(gè)字符與文法中的非終結(jié)符的每個(gè)候選式的第一個(gè)字符進(jìn)行匹配，成功后匹配下一個(gè)字符，直到字符串的所有字符都能匹配上。這次的實(shí)習(xí)的過(guò)程讓我想起了數(shù)據(jù)結(jié)構(gòu)上學(xué)到的樹(shù)的構(gòu)建，實(shí)現(xiàn)的代碼有的地方也參照了網(wǎng)上的程序，實(shí)現(xiàn)的過(guò)程中出現(xiàn)了很多錯(cuò)誤，總之，最后還是實(shí)現(xiàn)了。實(shí)習(xí)中出現(xiàn)的錯(cuò)誤有的是將過(guò)程沒(méi)有分析完整，也有的語(yǔ)法出現(xiàn)了錯(cuò)誤，自己也請(qǐng)教了同學(xué)。通過(guò)這次的實(shí)習(xí)，自己對(duì)遞歸下降分析有了深入的認(rèn)識(shí)，其實(shí)課本上的知識(shí)自己看的很簡(jiǎn)單，但是實(shí)現(xiàn)的過(guò)

15、程是很麻煩的，自己以后也會(huì)多多練習(xí)。附錄：總程序：#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(請(qǐng)輸入字符串(以#號(hào)結(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;