递归下降

清华大学实验报告课程名称编译原理实验名称递归下降分析技术班级学号学生姓名成绩指导教师张幸儿2010年12月一．实验目的：应用递归下降分析技术，关于各非终结符号构造相应子程序来识别相对于它的短语。二．实验内容：递归下降识别程序的例1：对于文法G[E]：E::=E+T|TT::=T*F|FF::=(E)|i经消去左递归同时也就消去了回溯性后的等价文法G’[E]：E::=TE’E’::=+TE’|εT::=FT’T’::=*FT’|εF=(E)|i递归下降识别程序的例2：对于文法G[S]：S::=S;TS::=TT::=ifethenSelseST::=ifethenST::=a经消去左递归同时也就消去了回溯性后的等价文法G’[S]：S::=TS’S’::=;TS’|εT::=ifethenST’|aT’::=elseS|ε+三.流程图:递归下降例１的流程图ETE’exitE’+取符号TE’exitTT’’FYNET’FT’取符号出错取符号F取符号exit*exitYN()ｉE取符号出错YNNYNYexit总控exit递归下降例2的流程图四.实验方法:1．用C语言写出递归下降识别程序1如下:#includeiostream.h#includestring.hvoidT();//声明函数voidF();//声明函数voidE1();//声明函数voidT1();//声明函数charsym;charstr[10];//存放输入的字符串inti=0;charGetSymbol(){//取字符sym=str[i];i++;returnsym;}voidError(){//出错判断couterror!endl;}voidE(){//递归下降的入口STS’exitS’；取符号TS’exitTT’’YNS取符号取符号取符号出错取符号取符号exitａYNifeelseS取符号出错YNNYNYexit总控exitthenT’SexitYNT();E1();}voidE1(){if(sym=='+'){//判断取的字符是否为＋sym=GetSymbol();T();E1();}}voidT(){F();T1();}voidT1(){if(sym=='*'){//判断取的字符是否为*sym=GetSymbol();F();T1();}}voidF(){if(sym=='i'){sym=GetSymbol();}//判断取的字符是否为i取下一个字符else{if(sym=='('){//判断取的字符是否为（取下一个字符sym=GetSymbol();E();if(sym==')'){sym=GetSymbol();}//判断取的字符是否为）取下一个字符else{Error();}}elseError();}}voidmain(){for(intj=0;j10;j++){str[j]=0;}cinstr;sym=GetSymbol();E();if(sym!=0)Error();}2．用C语言写出递归下降识别程序2如下:#includeiostream.h#includestring.h#includeconio.hvoidT();//声明函数voidS1();//声明函数voidT1();//声明函数charsym;charstr[100];//放输入的字符串charstr1[5];//存放取出的字符串inti=0;charGetSymbol(){//取字符sym=str[i];i++;returnsym;}voidError(){//判断错误couterror!endl;}voidgj()//取字符串{for(intj=0;j5;j++){str1[j]=0;}str1[0]=sym;intk=0;sym=GetSymbol();while(sym='a'&&sym='z'){k++;str1[k]=sym;sym=GetSymbol();}}voidS(){T();S1();}voidS1(){if(sym==';'){sym=GetSymbol();T();S1();}}voidT(){if(sym=='a'){sym=GetSymbol();}else{gj();if(strcmp(str1,if)==0){//判断是否为ifsym=GetSymbol();if(sym=='e'){sym=GetSymbol();sym=GetSymbol();gj();if(strcmp(str1,then)==0){//判断是否为thensym=GetSymbol();S();T1();}elseError();}elseError();}elseError();}}voidT1(){if(sym!='$'){sym=GetSymbol();gj();if(strcmp(str1,else)==0){//判断是否为elsesym=GetSymbol();S();}}}voidmain(){intj;charch;for(j=0;j100;j++){str[j]=0;}//清空数组j=0;do{//输入字符以$结束ch=getche();str[j]=ch;j++;}while(ch!='$');coutendl;sym=GetSymbol();S();if(sym!='$')//判断是否输入完Error();}五.实验结果:⒈递归下降识别程序1的结果如下：⑴．若输入i+i*i,则有结果如下：说明输入的i+i*i为该文法的句子⑵．若输入i-i,则有结果如下：说明输入的i-i不是该文法的句子⒉.递归下降识别程序2的结果如下：⑴．若输入ifethenaelsea$,其中$用来表示结束符,则有结果如下：说明输入的ifethenaelsea是该文法的句子⑵．若输入ife$,其中$用来表示结束符,则有结果如下：说明输入的ife不是该文法的句子由递归下降分析法可以看出，要是输入字符串的为该文法的句子，就没有错误，直接结束语句执行，要是不是该文法的句子就会有错误信息提示，再结束语句执行。程序1和程序2的原理是一样的，不过程序2涉及到了ifelse这样的语句，并且输入的字符串中有空格，我们要对空格进行处理。在程序的设计过程中难度加大了。在取字符的时候一定得加一个结束运算符标志着语句输入完，否则，在while语句中不知道怎样结束循环。六.实验总结:此次实验是应用递归下降分析技术构造相应程序来识别文法的句子。在程序编写之前，一定检查该文法是否有消除左递归和回溯性。如果存在得先消除左递归和回溯行，再进行程序编写。通过这次实验,更加深刻的理解到了有关递归下降分析技术的实现思想，再以后对分析句子是否是一个文法的句子又多了一种方法。同时也了解到递归下降分析技术的优点，如能灵活地在各个程序中添加语意加工工作。在这次的试验过程也遇到了很多问题，如程序2中，不知道怎么去掉空格分析，不知道怎么标示语句的结束，通过多次的修改，才把程序编写完善。通过实验程序的编写，将理论与实践相结合，总的说来,在此次实验中，收获颇多，收益匪浅。这样自己去分析文法写程序使我们对文法的了解更深了。