递归下降分析程序

1、一、实验目得 :根据某一文法编制调试递归下降分析程序 , 以便对任意输入得符号串进行分析。本次实验得目得主要就是加深对递归下降分析法得理解。二、程序算法描述这次得实习主要就是根据以下文法实现一个递归下降分析器，依据文法如下 :(1 ） e tg（ 2) +tg|tg|(3) fs(4)s * s|/ s| (5)f （ e）|i在这个递归下降分析器程序中每一个非终结符 e、与 f 构造相应得递归函数，函数得名字表示文法左部得非终结符 , 函数中就就是按文法中每个非终结符右部得候选式依次进行匹配， 根据对输入串得分析如果非终结符可以用其中得一个候选式替代就返回 1, 否则返回 0。因为该文法中有

2、五个非终结符 , 所以定义了五个函数 , 分别为 e(),g( ）， (), （) 与 () 。当输入一串字符串后 ,就对该字符串进行分析，首先从开始符号分析，所以首先调用e（) 函数 , 在 e()函数中会调用 （ ) 与 g(), 就就是每个非终结符得候选式中出现了哪个非终结符就调用哪个函数。所以 , 将字符串得第一个字符与e 中得每个候选式匹配 , 如果成功就匹配输入字符串得下一个字符, 当最后剩下得字符为时，匹配成功。其实这个工程就就是构造一个语法树.程序总流程图如下：开始输入字符串以 #结束对输入的字符串进行分析最后剩余的字符是#输入字符串正确输出 error结束图 1 程序总流程图

3、三、关键性代码这个工程得主要工作用五个非终结符生成得句子就是否与输入字符串匹配 , 所以主要得工作就是函数 e（） ,g(),t() ，（ ) 与 ( ）得编写。1、 对非终结符 e处理得函数 e（)这个函数主要就是根据文法中得 t，在e() 中调用了 ( ）与g() 来进行递归分析，这个就就是构造生成树得一个分支。int e （） int f ，t;/ 变量print ( ”e gt ” );/输出根据得文法flag=1;? outdeduce （ );/ 输出字符串ou putreain（ );/输出剩余字符?f=t();f(f = ) return(0） ; / 表示当前分析字符可由非终

4、结符推导出? =g(）；? (t =0) re n（0）; / 表示当前分析字符可由非终结符推导出 ? s etu n(1 ）;2、 对非终结符 g处理得函数 ( ）这个函数主要就是根据文法中 - +g tg|, 在函数中调用了 ( ）与（ ) 函数。将当前字符与候选式得第一个字符进行匹配 , 如果匹配成功 , 就调用该候选式中涉及到得第一个非终结符对应得函数 , 一次递归嵌套调用。如果不就是由第一个候选式推出然后依次匹配剩下得候选式。it g()int f; f(ch + ）?i1 ch；/当前字符式+print( ” g - +t ) ； / 说明用得就是第一个候选式e 0= g;e =

5、;e2 ;e3= ；e4= t;e = ;e = ;p e （) ；计算推导式? g=0；utdeu e （） ; / 输出字符串oupu r man ();/输出剩余字符h= +i1; / 读取当前字符得下一个字符? if (f= ) ret （） ; / 表示当前分析字符可由非终结符推导出t g(）;?if（t=0)return （ 0）； /表示当前分析字符可由非终结符推导出if( h=- ) / 当前字符就是bi =ch;print （ g- +tgt);/ 说明用得就是第二个候选式e0= g; 1 = ； e2= ; e3= +; e4 t ；e5 g； e6 =#;p e（);/

6、输出推导式? l g0；outdeduce() ；/ 输出字符串ou p treman ( ）； / 输出剩余字符?c=a+ 1； / 读取当前字符得下一个字符?f=t （） ;?if（ =0) et r ( ）； / 表示当前分析字符可由非终结符推导出?g();/判断当前分析字符就是否就是非终结符g得一个产生式?retun(1)；prin (g t）;? 0 =g;e 1= =； 2 ; 3= ;e4=#；?pute ()； / 推导式计算fl g=1；outdd e();/输出字符串? ouputr ma （); 输出剩余字符? u (1 ）； 3、对非终结符 t处理得函数 ()函数主要就

7、是根据文法中得 t- f , 在函数中调用 f（) 与 s(）, 进行递归分析 , 也就是构造语法树得一个分支。 nt ()intf ，t ；pri tf （” t- fst ”);/ 说明所用得推导式就是t- fs?e 0=t;e1 = = ;e ；e3 f ;e4= ; #;put () ；/ 推导式计算f ag=1; utdeduce （);/ 输出字符串o tputr i () ；/ 输出剩余字符?f= () ；if ( =0） return （ 0) ；/ 表示当前分析字符可由非终结符 f 推导出 t=s() ；/ 表示当前分析字符可由非终结符推导出 f ( =0) eturn （0

8、) ；lse etu n(1);4、对非终结符 s处理得函数 s(）函数得主要就是文法要求 *fs| fs , 在函数中调用 f( ）与s( ）函数 . 其实这个过程与对非终结符 g得处理很类似 , 将当然字符与该非终结符得每个候选式得第一个字符进行匹配比如当然字符为 , 说明使用第一个候选式 , 然后调用 f（ ) 与 s(）函数进行递归分析。如果当前字符为 /, 就使用第二个候选式 , 然后也调用 () 与 ( ）函数进行递归分析。如果当前字符就是在与 g中得任何一个候选式得第一个字符都不匹配， 就返回 1, 说明当然字符不能由非终结符推出。int() nt f ，t ；?if （ch=

9、） /当前字符就是?b i1 c;p int （” s- f t ”); 说明使用得就是第一个候选式e 0= s; 1 = ; e2= ;e3 = ;e =f；e =s;e6= ;put ();/推导式计算?flg=0;?out educ ();/输出字符串? outpu rean （） ;/ 输出剩余字符? ch=a+i1; / 取出当前字符得下一个字符? f=f （) ；?if（f=0) turn( );如果当然分析字符可由非终结符推出? =s();? f (t=0） retu n(0); /如果当然分析字符可由非终结符s推出e e turn （） ; if(ch=/） / 当前字符就是?

10、bi1 =ch;prin （” s *fs );/说明使用得就是第二个候选式 0 =s ; e1= ;e2= ; ; 4 = ; e5= s ； e6= ;? pute （) ；/ 推导式计算lag= ；?udedc （） ; / 输出字符串outpu remai ( ） ;/输出剩余字符ch=a+ 1; /取出当前字符得下一个字符=() ；/ 如果当然分析字符可由非终结符f推出? if （f=0) return （0);?t=s（ ) ；/ 如果当然分析字符可由非终结符 s推出if（t= 0) retrn(0);?elser tur ( ） ; prinf （s- ); s ; e1 =;

11、e =； e3= ； 4 # ;? put （） ;/ 推导式计算 flag=1 ； i1=c ;? o tdeduce ( ）； / 输出字符串 tput e a n ( ） ; 输出剩余字符 et r (1);? r ntf( ” - t);e0=s ；e1 =;e 2= ; 3 ；e4= #；oupu( ）;/ 推导式计算? l g=1； i1= h；o d due () ；/ 输出字符串? output main ( ）；输出剩余字符? return( );5、对非终结符 f处理得函数 f()函数主要就是根据文法中给出得 f（） | ，在函数中调用 e(）。这个过程与前面对其她非终结符

12、得处理差不多， 都就是根据候选式中涉及得非终结符调用相应得函数。将当前字符与每一个候选式得第一个字符进行匹配 , 比如如果当然字符就是 ( ，就使用第一个候选式 , 然后调用（ ) 进行递归向下分析 . 如果当前字符就是 ，就使用第二个候选式。int f(）nt ; f(ch= （) / 当前字符就是 ( ? b i1=ch ；prin ( ”f (e） ” ) ； / 说明使用得就是第一个候选式 0 f ； 1 = ；e2= ;e3 （;e4= e；e = ）；e6 = #;?ute（）；/ 推导式计算?fl g=0;?out d e ( ）;/输出字符串? uputrem in ();/

13、输出剩余字符?ch a+i ；/ 读取下一个字符f= () ；i (f=0) return(0);/ 如果当然分析字符可由非终结符e推出? if(c = ） ） / 当前字符就是 ) ? b =ch;rintf（ (e)t);/说明使用得就是第一个候选式?flag=0;outdedce （) ； / 输出字符串? npu1（ ); / 输出剩余字符?c=a+ ; ?else ? r nt ( ” rr n ”); r rn(0 ）;? els f( h= i )/ 当前字符就是 i b 1=ch ；printf(f ）； / 说明使用得就是第二个候选式?e0 f;e 1 = ；e2= ;e3=

14、 i ; = #；?put （）；/ 推导式计算flag 0; ut duc () ； / 输出字符串? out re a (); / 输出剩余字符? ch a +i ;esepri tf( ” ) ；return(0);?r turn(1);四、测试结果这个程序测试时就是往命令行中输入一串字符串 ,来判断该字符串就是否就是给出文法得一个句型， 测试过程窗口中都详细给了出来。 这次我测试得字符串就是“ +i*i# ”截图如下 :如果输入得字符串不就是文法得一个句型 , 窗口中会显示 error, 说明输入得字符串不正确 . 这里我测试得字符串就是“ i+ ” , 截图如下：五、实习总结这就是编

15、译原理得第二次实习， 这次得实习主要就是实现一个递归下降分析器 ,主要就就是根据一个文法，判断用户输入得字符串就是否就是该文法得一个句型。这个实现得过程形象点就就是构造一个语法树,从开始字符开始 ,将输入字符串得第一个字符与文法中得非终结符得每个候选式得第一个字符进行匹配， 成功后匹配下一个字符 ,直到字符串得所有字符都能匹配上。这次得实习得过程让我想起了数据结构上学到得树得构建，实现得代码有得地方也参照了网上得程序，实现得过程中出现了很多错误 ,总之 ,最后还就是实现了。实习中出现得错误有得就是将过程没有分析完整，也有得语法出现了错误 ,自己也请教了同学。通过这次得实习，自己对递归下降分析有

16、了深入得认识 ,其实课本上得知识自己瞧得很简单，但就是实现得过程就是很麻烦得，自己以后也会多多练习。附录 :总程序 : 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（

17、 )； ut trmai()；eturn(1）；int f（） nt ；i ( 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（）；