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) +TG|TG|(3) FS(4)S * S|/ S| (5)F （ E）|i在這個(gè)遞歸下降分析器程序中每一個(gè)非終結(jié)符 E、與 F 構(gòu)造相應(yīng)得遞歸函數(shù)，函數(shù)得名字表示文法左部得非終結(jié)符 , 函數(shù)中就就是按文法中每個(gè)非終結(jié)符右部得候選式依次進(jìn)行匹配， 根據(jù)對(duì)輸入串得分析如果非終結(jié)符可以用其中得一個(gè)候選式替代就返回 1, 否則返回 0。因?yàn)樵撐姆ㄖ杏形鍌€(gè)

2、非終結(jié)符 , 所以定義了五個(gè)函數(shù) , 分別為 E(),G( ）， (), （) 與 () 。當(dāng)輸入一串字符串后 , 就對(duì)該字符串進(jìn)行分析，首先從開始符號(hào)分析，所以首先調(diào)用 E（) 函數(shù) , 在 E() 函數(shù)中會(huì)調(diào)用 （ ) 與 G(), 就就是每個(gè)非終結(jié)符得候選式中出現(xiàn)了哪個(gè)非終結(jié)符就調(diào)用哪個(gè)函數(shù)。所以 , 將字符串得第一個(gè)字符與 E 中得每個(gè)候選式匹配 , 如果成功就匹配輸入字符串得下一個(gè)字符 , 當(dāng)最后剩下得字符為時(shí)，匹配成功。其實(shí)這個(gè)工程就就是構(gòu)造一個(gè)語(yǔ)法樹 .程序總流程圖如下：開始輸入字符串以 #結(jié)束對(duì)輸入的字符串進(jìn)行分析最后剩余的字符是#輸入字符串正確輸出 ERROR結(jié)束圖 1 程序

3、總流程圖三、關(guān)鍵性代碼這個(gè)工程得主要工作用五個(gè)非終結(jié)符生成得句子就是否與輸入字符串匹配 , 所以主要得工作就是函數(shù) E（） ,G(),T() ，（ ) 與 ( ）得編寫。1、 對(duì)非終結(jié)符 E處理得函數(shù) E（)這個(gè)函數(shù)主要就是根據(jù)文法中得 T，在E() 中調(diào)用了 ( ）與G() 來進(jìn)行遞歸分析，這個(gè)就就是構(gòu)造生成樹得一個(gè)分支。int E （）int f ，t;/ 變量print ( ”E Gt ” );/ 輸出根據(jù)得文法 flag=1;outDeduce （ );/ 輸出字符串ou putReain（ );/輸出剩余字符?f=T();f(f = ) return(0） ; / 表示當(dāng)前分析字符可

4、由非終結(jié)符推導(dǎo)出? =G(）；? (t =0) re n（0）;/ 表示當(dāng)前分析字符可由非終結(jié)符推導(dǎo)出 ? s etu n(1 ）;2、 對(duì)非終結(jié)符 G處理得函數(shù) ( ）這個(gè)函數(shù)主要就是根據(jù)文法中- +G TG|, 在函數(shù)中調(diào)用了 ( ）與（ ) 函數(shù)。將當(dāng)前字符與候選式得第一個(gè)字符進(jìn)行匹配, 如果匹配成功 , 就調(diào)用該候選式中涉及到得第一個(gè)非終結(jié)符對(duì)應(yīng)得函數(shù), 一次遞歸嵌套調(diào)用。如果不就是由第一個(gè)候選式推出然后依次匹配剩下得候選式。 i t G()int f; f(ch + ） /當(dāng)前字符式 +? i1 ch； print ( ” G - +T ) ； / 說明用得就是第一個(gè)候選式e 0=

5、G; e = ; e2 ;e3= ； e4= T; e = ; e = ;p e （) ；計(jì)算推導(dǎo)式 g=0；utDeu e （） ; / 輸出字符串?oupu R man ();/輸出剩余字符h= +i1; / 讀取當(dāng)前字符得下一個(gè)字符? if (f= ) ret（） ; / 表示當(dāng)前分析字符可由非終結(jié)符推導(dǎo)出t G(）;?if（t=0)return （ 0）； /表示當(dāng)前分析字符可由非終結(jié)符推導(dǎo)出if( h=- ) / 當(dāng)前字符就是bi =ch;print （ G- +TGt);/ 說明用得就是第二個(gè)候選式e0= G;1 = ； e2= ;e3= +; e4 T ；e5 G； e6 =#;

6、 e（);/ 輸出推導(dǎo)式l g0；outDeduce() ；/ 輸出字符串ou p tReman ( ）； / 輸出剩余字符?c=a+ 1； / 讀取當(dāng)前字符得下一個(gè)字符?f=T （） ;?if（ =0) et r ( ）； / 表示當(dāng)前分析字符可由非終結(jié)符推導(dǎo)出?G();/判斷當(dāng)前分析字符就是否就是非終結(jié)符G得一個(gè)產(chǎn)生式?retu n(1) ；prin (G t）;? 0 =G;e 1= =； 2 ; 3= ;e4=# ；?pute ()； / 推導(dǎo)式計(jì)算fl g=1；outDd e();/輸出字符串ouputR ma （); 輸出剩余字符? u (1 ）； 3、對(duì)非終結(jié)符 T處理得函數(shù) (

7、)函數(shù)主要就是根據(jù)文法中得 T- F , 在函數(shù)中調(diào)用 F（) 與 S(）, 進(jìn)行遞歸分析 , 也就是構(gòu)造語(yǔ)法樹得一個(gè)分支。nt ()intf ，t ；pri tf （” T- FSt ”);/ 說明所用得推導(dǎo)式就是T- FS?e 0=T;e1 = = ;e ；e3 F ; e4= ; #;put () ；/ 推導(dǎo)式計(jì)算 f ag=1;utDeduce （);/ 輸出字符串o tputR i () ；/ 輸出剩余字符?f= () ；if ( =0） return（ 0) ；/ 表示當(dāng)前分析字符可由非終結(jié)符F 推導(dǎo)出t=S() ；/ 表示當(dāng)前分析字符可由非終結(jié)符推導(dǎo)出f ( =0) eturn

8、（0) ；lseetu n(1);4、對(duì)非終結(jié)符 S處理得函數(shù) S(）函數(shù)得主要就是文法要求 *FS| FS , 在函數(shù)中調(diào)用 F( ）與S( ）函數(shù) . 其實(shí)這個(gè)過程與對(duì)非終結(jié)符 G得處理很類似 , 將當(dāng)然字符與該非終結(jié)符得每個(gè)候選式得第一個(gè)字符進(jìn)行匹配比如當(dāng)然字符為, 說明使用第一個(gè)候選式,然后調(diào)用 F（ ) 與 S(）函數(shù)進(jìn)行遞歸分析。如果當(dāng)前字符為/,就使用第二個(gè)候選式 , 然后也調(diào)用 () 與 ( ）函數(shù)進(jìn)行遞歸分析。如果當(dāng)前字符就是在G中得任何一個(gè)候選式得第一個(gè)字符都不匹配， 就返回 1, 說明當(dāng)然字符不能由非終結(jié)符推出。int()nt f，t ；?if （ch= ） /當(dāng)前字符就

9、是?b i1 c;p int （” S- F t ”); 說明使用得就是第一個(gè)候選式e 0= S;1 = e2= ;e3 = ;e =F ；e =S;e6= ;put ();/推導(dǎo)式計(jì)算?fl g=0;?out educ ();/輸出字符串outpu Rean （） ;/ 輸出剩余字符ch=a+i1; / 取出當(dāng)前字符得下一個(gè)字符f=F （) ；?if（f=0) turn( );如果當(dāng)然分析字符可由非終結(jié)符推出?=S();? f (t=0） retu n(0); /如果當(dāng)然分析字符可由非終結(jié)符S推出e e turn （） ; if(ch=/） / 當(dāng)前字符就是?bi1 =ch;prin （”

10、S *FS );/說明使用得就是第二個(gè)候選式0 =S ;e1= e2= ; ;4 = ; e5= S ； e6= ;pute （) ；/ 推導(dǎo)式計(jì)算lag= ；?uDedc （） ; / 輸出字符串 outpu Remai ( ） ;/ 輸出剩余字符ch=a+ 1; / 取出當(dāng)前字符得下一個(gè)字符=() ；/ 如果當(dāng)然分析字符可由非終結(jié)符 F推出if （f=0) return （0);?t=S（ ) ；/ 如果當(dāng)然分析字符可由非終結(jié)符S推出if（t= 0) retrn(0);?elser tur ( ） ; prinf （S- ); S ; e1 =; e =； e3= ； 4 # ;put （

11、） ;/ 推導(dǎo)式計(jì)算 flag=1 ； i1=c ;o tDeduce ( ）； / 輸出字符串 tput e a n ( ） ; 輸出剩余字符et r (1);r ntf( ” - t);e0=S ；e1 =;e 2= ; 3 ；e4= #；oupu( ）;/ 推導(dǎo)式計(jì)算 l g=1；i1= h；o D due () ；/ 輸出字符串output main ( ）；輸出剩余字符return( );5、對(duì)非終結(jié)符 F處理得函數(shù) F()函數(shù)主要就是根據(jù)文法中給出得 F（） | ，在函數(shù)中調(diào)用 E(）。這個(gè)過程與前面對(duì)其她非終結(jié)符得處理差不多， 都就是根據(jù)候選式中涉及得非終結(jié)符調(diào)用相應(yīng)得函數(shù)。將當(dāng)

12、前字符與每一個(gè)候選式得第一個(gè)字符進(jìn)行匹配 , 比如如果當(dāng)然字符就是 ( ，就使用第一個(gè)候選式 , 然后調(diào)用（ ) 進(jìn)行遞歸向下分析 . 如果當(dāng)前字符就是 ，就使用第二個(gè)候選式。int F(）nt ;f(ch= （) / 當(dāng)前字符就是 ( ? b i1=ch ；prin ( ”F (E） ” ) ； / 說明使用得就是第一個(gè)候選式 0 F ； 1 = ； e2= ; e3 （; e4= E； e = ）； e6 = #;?ute（）；/ 推導(dǎo)式計(jì)算?fl g=0; ?out d e ( ）;/ 輸出字符串 uputRem in ();/ 輸出剩余字符?ch a+i ；/ 讀取下一個(gè)字符 f= (

13、) ；i (f=0) return(0);/ 如果當(dāng)然分析字符可由非終結(jié)符E推出?if(c = ） ） /當(dāng)前字符就是 ) b =ch;rintf（ (E)t);/說明使用得就是第一個(gè)候選式?flag=0;outDedce （) ； / 輸出字符串? npu1（ ); / 輸出剩余字符?c=a+ ;?else? r nt ( ” rr n ”);r rn(0 ）;? els f( h= i )/ 當(dāng)前字符就是 i b 1=ch ；printf(F ）； / 說明使用得就是第二個(gè)候選式?e0 F;e 1 = ；e2= ;e3= i ; = #；?put （）；/ 推導(dǎo)式計(jì)算 flag 0;ut

14、duc () ； / 輸出字符串 ? out Re a (); / 輸出剩余字符ch a +i ;esepri tf( ” ) ；return(0);?r turn(1);四、測(cè)試結(jié)果這個(gè)程序測(cè)試時(shí)就是往命令行中輸入一串字符串 ,來判斷該字符串就是否就是給出文法得一個(gè)句型， 測(cè)試過程窗口中都詳細(xì)給了出來。 這次我測(cè)試得字符串就是“ +i*i# ”截圖如下 :如果輸入得字符串不就是文法得一個(gè)句型 , 窗口中會(huì)顯示 error, 說明輸入得字符串不正確 . 這里我測(cè)試得字符串就是“ i+ ” , 截圖如下：五、實(shí)習(xí)總結(jié)這就是編譯原理得第二次實(shí)習(xí)， 這次得實(shí)習(xí)主要就是實(shí)現(xiàn)一個(gè)遞歸下降分析器 ,主要就

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

16、己以后也會(huì)多多練習(xí)。附錄 :總程序 : clu st io、h# clude d s、h#inl d stdli 、 h#i cl ; e3= * ;e4 F; e=S ; e #; put(） ;lag=0；otDduce(）；ut uRemain(）; ch= +i1;f=F();if （f=0) e rn(); t=(）; if （t= 0） return(） ;else rtrn（） ;prntf( ” St ” ); e0= S; e1= =;e2= ; =; e4= #;pute(）; f ag=1;i1 h；ouDe（ )；ut tRmai()；eturn(1）；int F（）n

17、t ；( h=()b1=ch；prn ( ” -（ t ”）; e0=F;e1= ;e; e = （；e4= E; e5= ；)e = ；# p te（） ; g ;ouD uce()；ot tReai（ )；c=a+ 1；f=();if (f= ) re rn（0); if( h= )b 1=ch; printf( ”F-(E)t) ；flag= ;otDedce();outputRemain(); c +i1 ;elseprintf （”erorn); return（ 0)；elsei（ c =i )bi1 =ch;pi tf( ”F-it ”); 0=; e1= ；e2=； 3= i ;e4= #; pte(）;flag=;outDduce（); outputeman（）；cha+ 1;