递归下降分析程序的实现——合肥工业大学编译原理课程.doc

课程设计报告设计题目17.递归下降分析程序的实现设计要求对文法 G:EE+T|T TT*F|FF（E）|i构造出G的递归下降分析程序。程序显示输出匹配过程（即自上而下生成语法分析树的步骤，输出各匹配产生式序号即可）。设计思路（1）分析a) E=E+T=E+T*F=E+T*(E)即有E=E+T*(E)存在左递归。用直接改写法消除左递归，得到如下：E TE E +TE | TE|T FT T *FT | /FT|F (E) | ib) 对于以上改进的方法。可得：对于E:FIRST( E )=FIRST(+TE)FIRST(-TE)=+， 对于T:FIRST( T )=FIRST(*FT)FIRST(/FT)=*， 而且：FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST(E)FIRST(i)=(，i 由此得出各非终结符的FOLLOW集合如下：FOLLOW( E )= )，#FOLLOW(E)= FOLLOW(E)= )，#FOLLOW( T )= FIRST(E)FOLLOW(E)=+，)，#FOLLOW( T ) = FOLLOW( T ) =+，)，#FOLLOW( F )=FIRST(T)FOLLOW(T)=*，+，)，#由以上FOLLOW集可以我们可以得出SELECT集如下：对ESELECT（ETE）=FIRST(TE)=FIRST(T)= (，i 对ESELECT（E+TE）= + SELECT（E TE）= SELECT（E）=，)，#对TSELECT（TFT）=(，i对TSELECT（T*FT）= * SELECT（T FT）= SELECT（T）=，+，)，#对FSELECT（F(E) ）= ( SELECT（Fi）= i SELECT(E+TE)SELECT（E TE）SELECT（E）=FSELECT(T*FT)SELECT（T FT）SELECT（T）=FSELECT（F(E) ）SELECT（Fi）= F由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。因此，转化后的文法可以用递归下降分析法作语法分析。（2）设计这里采用递归下降分析法形象描述递归子程序。程序中将要用到的几个重要数据如下：一个全局变量ch，存放由文件输入得到的字符。一个函数宏READ(ch)，实现读取文件中的字符。五个子函数：P(E)、P(E)、P(T)、P(T)、P(F)。课程设计源程序/* *文件描述：递归下降语法分析器。分析如下方法： *E-E+T | E-T | T *T-T*F | T/F |F *F-(E) | i * 输入：每行含一个表达式的文本文件。 *输出：分析成功或不成功信息。 *创建人：赵有斌*/#include#include#define READ(ch) ch=getc(fp)/*宏：READ(ch)*/charch;/*声明为全局变量*/intright=0;FILE*fp;structstruCHcharch;structstruCH *next;struCH,*temp,*head,*shift;/*head指向字符线性链表的头结点*/*shift指向动态建成的结点(游标)*/void main(intargc,char *argv)voidE ();/* P(E) */voidE1();/* P(E)*/voidT ();/* P(T) */voidT1();/* P(T)*/voidF ();/* P(F) */interrnum=0,k=0,m=0,countchar=0,rownum;intcharerr=0;/*开关控制量*/*以只读方式打开文件*/if(fp=fopen(argv1,r)=NULL)printf(ntCan not open file %s,or not exist it!n,argv1);exit(0); /*文件不存在or打不开时，正常退出程序*/else printf(ntSuccess open file: %sn,argv1);/*成功打开文件*/*遍历整个文件检测是否有非法字符*/*如果用while(!feof(fp)语言，将会多出一个字符 *所以这里采用以下方法遍历整个文件检测其否有非法字符*/*1计算文件中字符数量*/while(!feof(fp)READ(ch);/*这里读取字符只是让文件指针往前移*/countchar+;/*统计文件中的字符数(包括换行符及文件结束符)*/rewind(fp);/*将fp文件指针重新指向文件头处，以备后面对文件的操作*/if(countchar=0)/*空文件*/printf(t%s is a blank file!n,argv1); exit(0);/*正常退出本程序*/*2开始遍历文件*/while(k(countchar-1) ch=getc(fp);if(!(ch=(|ch=)|ch=i|ch=+|ch=-|ch=*|ch=/|ch=#|ch=n)charerr=1;errnum+; /*charerror出错标记，errnum统计出错个数*/k+;rewind(fp);/*将fp文件指针重新指向文件头处，以备后面的建链表操作*/if(charerr=1/*文件中有非法字符*/printf(nt%dUnindentify characters in file %s n,errnum,argv1);exit(0);/*正常退出本程序*/*非空且无非法字符，则进行识别操作*/for(rownum=1;mnext=NULL;head=shift;/*读取一行形成线性链表*/READ(ch);putchar(ch);m+;while(ch!=n&mch=ch;temp-next=NULL;shift-next=temp;shift=shift-next;READ(ch);if(m!=(countchar-1) putchar(ch);/*不输出最后一次读取的文件结束符*/m+;head=head-next;/*消去第一个空头结点,并使head指向非空线性链表头*/shift=head; /*shift指向头结点，以便后面识别操作*/putchar(n);E(); /*开始识别一行*/if(shift-ch=#&right)/*正确提示:文件名 Line 行号:right expression!*/printf(%s Line %d:t right expression!n,argv1,rownum);else /*错误提示:文件名 Line 行号:error expression!*/printf(%s Line %d:t error expression!n,argv1,rownum);putchar(n);printf(Completed!n);fclose(fp);/*关闭文件*/exit(0);/*正常结束程序*/*以下函数分别对应于子模块程序*/void E()T();E1();void E1()if(shift-ch=+|shift-ch=-)shift=shift-next;T();E1();elseif(shift-ch=#|shift-ch=)return;elseright=0;void T(void)F();T1();void T1(void)if(shift-ch=*|shift-ch=/)shift=shift-next;F();T1();elseif(shift-ch!=#&shift-ch!=)&shift-ch!=+&shift-ch!=-)right=0;/*如果不是#or)or+or+or-则出错*/voidF(void)if(shift-ch=i)shift=shift-next;elseif(shift-ch=()shift=shift-next;E();if(shift-ch=)shift=shift-next;elseright=0;elseright=0;运行结果记录程序结果分析通过测试所给数据，测试结果均与预期结果一致，验证了程序的可行性，较好的解决了递归下降分析程序的问题。课程设计总结这次的课程设计让我对编译原理这门课程解决实际的问题有了一个新的认识：解决一个问题首先要对其所属的结构进行一个分析，然后再运用自己所学的文法类型进行编程求解。例如所给文法：E=E+T=E+T*F=E+T*(E)即有E=E+T*(E)存在左递归，因此必须消除左递归，可以采取提取公因子的方法消除左递归。通过这次课程设计，我掌握了自上而下语法分析法的特点。掌握了递归下降语法分析的基本原理和方法。运用递归下降分析法完成了本试验的语法分析构造，并且成功的分析出每种正确的句子和错误的句子。函数的构造是根据文法分析的递归过程，所编写每个函数的功能，以文法的右部为函数名，对应的左部为相应分析过程。此分析法简单，直观，易构造分析程序，但是不适于文法过于复杂的，不易检查出错误。在课