递归下降分析实验报告

1实习二递归下降分析一、实验目的：根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、实验预习提示1、递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2、递归下降分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，3、递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构：(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。(2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。具体为：（1）对于每个非终结符号U-u1|u2|…|un处理的方法如下：U(){ch=当前符号;if(ch可能是u1字的开头)处理u1的程序部分;elseif(ch可能是u2字的开头)处理u2的程序部分;…elseerror()}（2）对于每个右部u1-x1x2…xn的处理架构如下：处理x1的程序；处理x2的程序；…处理xn的程序；（3）如果右部为空，则不处理。（4）对于右部中的每个符号xi①如果xi为终结符号：if(xi==当前的符号){NextChar()；/%NextChar为前进一个字符函数。%/return;}else出错处理2②如果xi为非终结符号，直接调用相应的过程xi()三、实验要求程序输入/输出示例：对下列文法，用递归下降分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG|－TG|ε（3）T-FS（4）S-*FS|/FS|ε（5）F-(E)|i输出的格式如下：(1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#(2)输出结果：i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。四、实验内容4.1功能描述这个程序是一个递归下降分析程序，能够判定输入的一个字符串是否属于给定的文法。如果不是，则会给出一定的出错信息，并且列出每一步使用的产生式。4.2全局变量及其定义chara[50];//-----------存储输入的字符串charch;//-----------暂时存储输入的字符chard[200];//--------记录当前堆栈中的产生式intn1;//----------输入字符串的长度chartoken;//--------------当前待分析字符4.3模块设计intE();//-----------------E过程，对应产生式E-TGintT();//-----------------T过程，对应产生式T-FSintG();//-----------------G过程，对应产生式G-+TG|-TG|εintS();//-----------------S过程，对应产生式S-*FS|/FS|εintF();//-----------------F过程，对应产生式F-(E)|ivoidoutput();//-----------------输出已分析字符串和当前字符voidinput1();//-----------------输出剩余字符34.4程序流程图图1主函数main（）流程图图2E函数（）流程图图3T函数（）流程图结束输出分析信息进行递归下降分析得到第一个字符将开始符放入堆栈获取字符串长度开始输入要处理的字符串YN开始输出分析栈内容和当前动作将分析栈的E换为TGTGreturn1return0结束N结束Yreturn1return0FS将分析栈的T换为FS开始输出分析栈内容和当前动作4图4G函数（）流程图5图5F函数（）流程图图6S函数（）流程图五、核心代码清单：函数功能描述：根据文法E-TG,先从主函数开始调入第一个非终结符函数执行，并且显示调用产生式，根据程序的状态，调用非终结符函数T（）或G（），进行递归向下分析。intE(){intf,t;printf(E--TG\t);e[0]='E';e[1]='=';e[2]='';e[3]='T';e[4]='G';e[5]='#';output();flag=1;6input();input1();f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);}函数功能描述：根据文法G-+TG|—TG|ε，如果当前字符变量ch为“+”，则显示调用产生式，首先判断是算式递归向下分析是否结束，若没有结束则继续依次嵌套调用非终结符函数T（）和G（）；如果当前字符变量ch为“-”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，继续依次嵌套调用非终结符函数T（）和G（）；如果当前字符变量ch既不为“+”也不为“-”，非终结符G指向为空，函数只用于显示指向为空，找不到可以和文件中字符匹配的非终结符。intT(){intf,t;printf(T--FS\t);e[0]='T';e[1]='=';e[2]='';e[3]='F';e[4]='S';e[5]='#';output();flag=1;input();input1();f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}函数功能描述：根据文法T-FS,先显示算式匹配所用的显示调用的产生式，然后依次嵌套调用非终结符函数F（）和S（），进行递归向下分析。intG(){intf;if(ch=='+'){b[i1]=ch;7printf(G--+TG\t);e[0]='G';e[1]='=';e[2]='';e[3]='+';e[4]='T';e[5]='G';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=T();if(f==0)return(0);G();return(1);}if(ch=='-'){b[i1]=ch;printf(G--+TG\t);e[0]='G';e[1]='=';e[2]='';e[3]='+';e[4]='T';e[5]='G';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=T();if(f==0)return(0);G();return(1);}printf(G--^\t);e[0]='G';8e[1]='=';e[2]='';e[3]='^';e[4]='#';output();flag=1;input();input1();return(1);｝intS(){intf,t;if(ch=='*'){b[i1]=ch;printf(S--*FS\t);e[0]='S';e[1]='=';e[2]='';e[3]='*';e[4]='F';e[5]='S';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}if(ch=='/'){b[i1]=ch;printf(S--*FS\t);e[0]='S';e[1]='=';e[2]='';9e[3]='*';e[4]='F';e[5]='S';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}printf(S--^\t);e[0]='S';e[1]='=';e[2]='';e[3]='^';e[4]='#';output();flag=1;a[i1]=ch;input();input1();return(1);printf(S--^\t);e[0]='S';e[1]='=';e[2]='';e[3]='^';e[4]='#';output();flag=1;a[i1]=ch;input();input1();return(1);}函数功能描述：根据文法S-*FS|/FS|ε，如果当前字符变量ch为“*”，则显示调用产生式，10从文件文档中读取下一个字符，让字符指针变量指向下一个字符，依次嵌套调用非终结符函数F（）和递归调用自身S（）；如果当前字符变量ch为“/”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，依次嵌套调用非终结符函数F（）和递归调用自身S（）；如果当前字符变量ch既不为“*”也不为“/”，G中找不到可以匹配的算式则非终结符G指向为空。intF(){intf;if(ch=='('){b[i1]=ch;printf(F--(E)\t);e[0]='F';e[1]='=';e[2]='';e[3]='(';e[4]='E';e[5]=')';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=E();if(f==0)return(0);if(ch==')'){b[i1]=ch;printf(F--(E)\t);flag=0;input();input1();ch=a[++i1];}else{printf(error\n);return(0);}}elseif(ch=='i')11{b[i1]=ch;printf(F--i\t);e[0]='F';e[1]='=';e[2]='';e[3]='i';e[4]='#';output();flag=0;input();input1();ch=a[++i1];}else{printf(error\n);return(0);}return(1);}voidinput(){intj=0;for(;j=i1-flag;j++)printf(%c,b[j]);/*输出分析串*/printf(\t\t);printf(%c\t\t,ch);/*输出分析字符*/}voidinput1(){intj;for(j=i1+1-flag;jn1;j++)printf(%c,a[j]);/*输出剩余字符*/printf(\n);}六、程序运行结果：12}七、实验中遇到的问题：因为前面的好多实习，都是用JAVA编程实现老师规定的任务，所以对C语言的编程有点淡忘了。于是，这次决定用C语言编程实现，以巩固我的C语言编程能力。在这次实习的过程中，遇到了很多问题。最令我印象深刻的是内存分配问题上。因为在JAVA中不涉及手动分配内存的问13题，而在C语言中对于数组等变量要手动分配内存。所以，在实习中，总是忘了手动分配内存，出现内存读写错误。于是，经过一步一步的Debug后，发现了问题的所在。还有一个问题是：在添加打印出分析栈内容的时候，打印出来的分析栈内容与自己的预期很不吻合，经过调试才发现在匹配成功后，没有返回1，然后就程序只能接着执行后面的语句，所以导致分析错误。八、实验总结：通过这次实习，不仅使我对递归下降分析过程有了更进一步的了解，而且使我对C语言的编程进行了温习。这次实验前，花了一个半小时理解书中的理论并且自己在纸上模拟了一遍分析过程。递归下降分析就是对每个非终结符按其产生式结构来构造相应语法分析子程序，其中终结符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法