搜索
数学与软件科学学院实验报告学期：2015至2016第2学期2016年3月21日课程名称：编译原理专业：信息与计算科学2013级5班实验编号：2实验名称：递归下降分析器指导教师：王开端姓名：李丹学号：2013060510实验成绩：实验二递归下降分析器实验目的：通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹配，观察输入符号串是否为给定文法的句子。实验内容：根据文法G[E]设计递归下降分析器并分析输入串)(*321iii是否为文法的句子。G[E]：E→E+T|TT→T*F|FF→(E)|i实验步骤：在进行递归下降分析法之前，必须对文法进行左递归和回溯的消除。1消除左递归直接消除见诸于产生式中的左递归比较容易，其方法是引入一个新的非终结符，把含有左递归的产生式改为右递归。文法G[E]经过消去直接左递归后得到文法G’[E]为：G’[E]：iEFFTTFTTTEETEE|)(|'*''|'''2消除回溯回溯发生的原因在于候选式存在公共的左因子。一般情况下，设文法中关于A的产生式为jiiA|...|||...||121，那么，可以把这些产生式改写为ijiAAA|...|'|...||'11经过反复提取左因子，就能把每个非终结符（包括新引进者）的所有候选首字符集变为两两不相交（既不含有公共左因子）。3什么是递归下降分析法递归下降分析法是一种自顶向下的分析方法，文法的每个非终结符对应一个递归过程（函数）。分析过程就是从文法开始符出发执行一组递归过程（函数），这样向下推导直到推出句子；或者说从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一棵语法树。在不含左递归和每个非终结符的所有候选终结首字符集都两两不相交条件下，我们就可能构造出一个不带回溯的自顶向下的分析程序，这个分析程序是由一组递归过程（或函数）组成的，每个过程（或函数）对应文法的而一个非终结符。这样的一个分析程序称为递归下降分析器。4文法分析以G’[E]为例：G’[E]：iEFFTTFTTTEETEE|)(|'*''|'''文法分析过程类似于一个个函数嵌套，我们可以假定函数E()、T()、E’()、F()、T’()，文法开始符E（看做函数E()）嵌套函数T()、E’()；而对于函数E’()，若有字符“+”匹配，则进行匹配，否则进入嵌套函数T()或E’()或为空；对于函数T()，执行其中的嵌套函数F()或T’()；对于函数F()，如果有字符“i”匹配，则进行匹配，否则若待分析串喊字符“(”，进行匹配，并进入嵌套函数E()执行，再匹配“)”；对于函数T’()，若有字符“*”匹配，则进行匹配，否则进入嵌套函数F()或T’()或为空。5文法分析流程图函数间调用情况：图1递归下降分析法函数调用情况流程图（由于用一个流程图画出完整的文法分析过程完成的并不规范，故本实验将其分为4个流程图。）main()函数：图2递归下降分析法main()函数执行流程图E’()函数：图3递归下降分析法E’()函数执行流程图T’()函数：图4递归下降分析法T’()函数执行流程图F()函数：图5递归下降分析法F()函数执行流程图6输入串i*(i+i)#语法分析表1输入串i*(i+i)语法分析表步骤符号栈待分析字符串采用产生式1#Ei*(i+i)#E→TE’2#E’Ti*(i+i)#T→FT’3#E’T’Fi*(i+i)#F→i4#E’T’*(i+i)#T’→*FT’5#E’T’F(i+i)#F→(E)6#E’T’Ei+i)#E→TE’7#E’T’E’Ti+i)#T→FT’8#E’T’E’T’Fi+i)#F→i9#E’T’E’T’+i)#T’→ε10#E’T’E’+i)#E’→+TE’11#E’T’E’Ti)#T→FT’12#E’T’E’T’Fi)#F→i13#E’T’E’T’)#T’→ε14#E’T’E’)#E’→ε15#E’T’#T’→ε16#E’#E’→ε17##分析成功7程序设计本实验在程序设计方面做出了以下定义：一维字符数组a[]：用于存放分析字符串一维字符数组ch[]：用于存放符号栈内容lookahead：用于处理正在分析字符串的哪一个字符length：输入串的长度l：符号栈大小减1n：产生式右部长度（’也算作一个字符）#includestdio.h#includestring.hchara[10];/*defineinputstring’stype&length*/charch[10]={'#','E'};charcha;intlookahead=0;/*definearray’snumber*/intlength=0;intstep=1;intl=1;intn;intmain(void)/*mainprocedure*/{clrscr();printf(Pleaseinputastring(endwith'#'):);/*inputastring*/while(a[lookahead]!='#'){do{scanf(%c,&cha);a[length]=cha;length++;}while(cha!='#');E();if(a[lookahead]=='#')/*whetherthelastcharis‘#’ornot*/printf(\nThestructureofthesentenceisright!);elseprintf(\nNoendsign!);}return0;}intE()/*E()procedure*/{print();printf(E-TE'\n);n=3;l=l+n-1;ch[l]='T';ch[l-1]=39;ch[l-2]='E';step++;T();E1();}intE1()/*E1()procedure*/{if(a[lookahead]=='+')/*ifthenextcharis‘+’*/{print();printf(E'-+TE'\n);n=3;l=l+n-2;ch[l]='T';ch[l-1]=39;ch[l-2]='E';step++;lookahead++;/*turntonextchar*/T();E1();}elseprint();printf(E'-e\n);l=l-2;step++;}intT()/*T()procedure*/{print();printf(T-FT'\n);n=3;l=l+n-1;ch[l]='F';ch[l-1]=39;ch[l-2]='T';step++;F();T1();}intT1()/*T1()procedure*/{if(a[lookahead]=='*'){print();printf(T'-*FT'\n);n=3;l=l+n-2;ch[l]='F';ch[l-1]=39;ch[l-2]='T';step++;lookahead++;F();T1();}elseprint();printf(T'-e\n);l=l-2;step++;}intF()/*F()procedure*/{if(a[lookahead]=='i'){print();printf(F-i\n);n=0;l=l+n-1;step++;lookahead++;}elseif(a[lookahead]=='('){print();printf(F-(E)\n);ch[l]='E';step++;lookahead++;E();if(a[lookahead]==')'){lookahead++;}else{printf(No')'match!\n);exit(0);}}else{printf(No'('match!\n);exit(0);}}intprint(){inti;printf(%d\t,step);for(i=0;i=l;i++)printf(%c,ch[i]);if(l7)printf(\t\t);elseprintf(\t);for(i=0;ilookahead;i++){a[i]='';printf(%c,a[i]);}for(i=lookahead;ilength;i++)printf(%c,a[i]);printf(\t);}实验结果：注：实验结果第一列表示步骤，第二列表示符号栈，第三列表示待分析串，第四列代表所用产生式。实验心得：这个实验相对于词法分析实验而言更加困难，本实验在设计代码的时候是以不存在左递归和回溯的情况下进行的，在一定程度上降低了一定的难度。该实验重点在于需要我们理解什么是递归下降分析器，是如何进行分析的，还需要画出流程图，理清整体思路，再结合书上的代码，整理出相应的内容，然后将之编写为代码，实现递归下降分析器。所编写的代码仍存在问题，欢迎老师指点。