实验二----递归下降语法分析程序设计

实验二递归下降语法分析程序设计[实验目的]：1．了解语法分析的主要任务。2．熟悉编译程序的编制。[实验内容]：根据某文法，构造一基本递归下降语法分析程序。给出分析过程中所用的产生式序列。[实验要求]：1.构造一个小语言的文法，例如，Pascal语言子集的文法，考虑其中的算术表达式文法：G[表达式]：G[E]：表达式→表达式+项|表达式-项|项E→E+T|T项→项*因式|项/因式|因式T→T*F|F因式→标识符|无符号整数|(表达式)F→i|(E)2.设计语法树的输出形式，例如：产生式……3.编写递归下降语法分析程序实现基本的递归下降分析器，能够分析任给的符号串是否为该文法所定义的合法算术表达式。实验报告中要说明分析使用的方法。4.生成并输出分析过程中所用的产生式序列：1产生式12产生式2……[实验步骤]：1.写出一个小语言的算术表达式文法。2.写出该小语言的算术表达式等价的LL(1)文法。例如：G[E]：其中E→TGG为E’E→+TG|^^为εT→FSS为T’T→*FS|^F→i|(E)3.编写递归下降语法分析程序。4.调试运行程序。5.结果分析。6.撰写实验报告。[实验报告]：每位同学撰写一份试验报告，并提交电子版。1.源程序。2.画出流程图。3.实验设计过程中出现的问题及解决的方法。4.实验设计过程中的体会。5.给出程序清单。6.给出测试结果。实验报告命名规则：个人：2013-14（1）医智（1）1107505101蔡菲菲实验二交各班课代表汇总后，由课代表打包后，发送至老师的邮箱班级命名规则：2013-14医智（1）实验二截止日期：第14周周五晚11点30分测试的结果举例源代码:#includestdio.h#includedos.h#includestdlib.h#includestring.hchara[50],b[50],d[200],e[10],ch;/*数组a存输入串，数组d存推导式*/intn1,i1=0,flag=1,n=5;/*flag=1处理非终结符，flag=0处理终结符*/inttotal=0;/*步骤计数器*/intE(),E1(),T();intG();/*E’*/intS();/*T’*/intF();voidinput();voidinput1();voidoutput();voidmain()/*递归分析*/{intf,p,j=0;charx;d[0]='E';d[1]='=';d[2]='';d[3]='T';d[4]='G';d[5]='#';printf(请输入字符串(长度50,以#号结束）\n);do{scanf(%c,&ch);a[j]=ch;j++;}while(ch!='#');n1=j;/*n1输入串实际长度*/ch=b[0]=a[0];printf(步骤\t文法\t分析串\t\t分析字符\t剩余串\n);f=E1();{system(pause);}if(f==0)return;/*有语法错误，失败退出*/if(ch=='#'){printf(accept\n);/*输入串是文法的句子*/p=0;x=d[p];while(x!='#'){printf(%c,x);p=p+1;x=d[p];/*输出推导式*/}}else{printf(error\n);printf(回车返回\n);getchar();getchar();return;}printf(\n);printf(回车返回\n);getchar();getchar();}intE1()/*有语法错误函数返回值为0，否则为1*/{intf,t;printf(%d\tE--TG\t,total);total++;flag=1;input();input1();f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);}intE(){intf,t;printf(%d\tE--TG\t,total);total++;e[0]='E';e[1]='=';e[2]='';e[3]='T';e[4]='G';e[5]='#';output();flag=1;input();input1();f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);}intT(){intf,t;printf(%d\tT--FS\t,total);total++;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);}intG(){intf;if(ch=='+'){b[i1]=ch;printf(%d\tG--+TG\t,total);total++;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(%d\tG--^\t,total);total++;e[0]='G';e[1]='=';e[2]='';e[3]='^';e[4]='#';output();flag=1;input();input1();return(1);}intS(){intf,t;if(ch=='*'){b[i1]=ch;printf(%d\tS--*FS\t,total);total++;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);}printf(%d\tS--^\t,total);total++;e[0]='S';e[1]='=';e[2]='';e[3]='^';e[4]='#';output();flag=1;a[i1]=ch;input();input1();return(1);}intF(){intf;if(ch=='('){b[i1]=ch;printf(%d\tF--(E)\t,total);total++;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(%d\tF--(E)\t,total);total++;flag=0;input();input1();ch=a[++i1];}else{printf(error\n);return(0);}}elseif(ch=='i'){b[i1]=ch;printf(%d\tF--i\t,total);total++;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);}voidoutput()/*推导式计算*/{intm,k,j,q;inti=0;m=0;k=0;q=0;i=n;d[n]='=';d[n+1]='';d[n+2]='#';n=n+2;i=n;i=i-2;while(d[i]!=''&&i!=0)i=i-1;i=i+1;while(d[i]!=e[0])i=i+1;q=i;m=q;k=q;while(d[m]!='')m=m-1;m=m+1;while(m!=q){d[n]=d[m];m=m+1;n=n+1;}d[n]='#';for(j=3;e[j]!='#';j++){d[n]=e[j];n=n+1;}k=k+1;while(d[k]!='='){d[n]=d[k];n=n+1;k=k+1;}d[n]='#';}流程图：E、E1INPUTSYM=”i”?TINPUTSYM=”(“?GError出口YYNN开始输入符号串（#结束）调用函数E1当前字符为#？匹配成功accept，输出最左推导过程结束匹配失败errorYNINPUTSYM=”i”?TINPUTSYM=”(“?GError出口YYNNGINPUTSYM=”+”?NYINPUTSYM=下一个符号TINPUTSYM=”i”?FINPUTSYM=”(“?SError出口YYNNFINPUTSYM=”i”?INPUTSYM=”(“?ErrorYYNNEYNINPUTSYM=下一个符号INPUTSYM=”)“?出口YYNNNYINPUTSYM=”i”?FINPUTSYM=”(“?SError出口SINPUTSYM=”*”?INPUTSYM=下一个符号运行结果：验证i*i+i验证ik5实验设计过程中出现的问题及解决的方法:本次实验最难的问题就是画流程图，解决方法就是通过问同学和通过google和查看书本，了解LL(1)文法是怎么实现的，然后在对每个非终结符进行递归下降的程序分析并画出流程图。实验设计过程中的体会:这次实验比较成功的完成了,由于是C语言,理解上也不是很大问题,不是实验一的那样是C++,有些代码看都看不懂。不过这次实验的重点就是让我们了解LL（1）文法，更能让我们独自地去完成项目，为后面的大作业做准备。