《递归下降分析器》由会员分享，可在线阅读，更多相关《递归下降分析器（12页珍藏版）》请在金锄头文库上搜索。
1、题目：编程识别由下列文法所定义的表达式的递归下降语法分析器。E3E+T I E-T I TT3T*F I T/F IFF3(E) I i输入：每行含一个表达式的文本文件。输出：分析成功或不成功信息。解答：(1) 分析a) .E=E+T=E+T*F=E+T*(E)即有E=E+T*(E)存在左递归。用直接改写法消除 左递归，得到如下：E 3 TEE 3 +TE | -TE5|sT 3 FTT 3 *FT | ZFT5|F 3 (E) I ib) 对于以上改进的方法。可得：对于 E： FIRST( E)=FIRST(+TE)UFIRST(-TE)U =+, -, 对于 T： FIRST( T)=FI
2、RST(*FT)UFIRST(/FT)U =*,/, 而且： FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST(E) UFIRST(i)=(, i 由此我们容易得出各非终结符的FOLLOW集合如下：FOLLOW( E )= ), #FOLLOW(E)= FOLLOW(E)=( ), #FOLLOW( T )= FIRST(E) U FOLLOW(E)=+, -, ), #FOLLOW( T ) = FOLLOW( T ) =+, -, ), #FOLLOW( F )=FIRST(T) UFOLLOW(T)=*, /, +, -, ), # 由以上FOLLOW
3、集可以我们可以得出SELECT集如下：对 E SELECT (E3TE，)=FIRST(TE)=FIRST(T)= (, i 对 E SELECT (E 3+TE)= + SELECT (E 今-TE)= - SELECT (E * =s, ), #对 T SELECT (T3FT)=(, i对 T SELECT (T 3*FT)= * SELECT (T 今/FT)= /SELECT (T * =s, +, -, ), #对 F SELECT (F3(E) ) = ( SELECT (F3i) = i . SELECT(E 3+TESELECT (E 3 -TE)ASELECT (E * =
4、O SELECT(T 3*FT)ASELECT (T 3/FT)ASELECT (T 3s) =O SELECT (F3(E) ) ASELECT (F3i)=中由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL(1) 文法。因此，转化后的文法可以用递归下降分析法作语法分析。(2) 设计这里采用递归下降分析法形象描述递归子程序。程序中将要用到的几个重要数据 如下：一个全局变量ch,存放由文件输入得到的字符。一个函数宏READ(ch)，实现读取文件中的字符。五个子函数：P(E)、P(E)、P(T)、P(T)、P(F)。程序主要的子函数模块流程图如下：程序子模块图(3) 程序代
5、码如下3、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上vt /*文件名：ana.c*文件描述：递归下降语法分析器。分析如下方法:E-E+T I E-T I TT-T*F I T/F IFF-(E) I i输入：每行含一个表达式的文本文件。输出：分析成功或不成功信息。* 创建人：余洪周 2006-12-8*版本号：1.0“*/#include#include#define READ
6、(ch) ch=getc(fp)/*宏：READ(ch)*/char ch;/*声明为全局变量*/int right=0;FILE *fp;struct struCHchar ch;struct struCH *next;struCH,*temp,*head,*shift;/*head指向字符线性链表的头结点*/*shift指向动态建成的结点(游标)*/void main(int argc,char *argv)voidE ();/*P(E)*/voidE1();/* P(E)*/voidT ();/*P(T)*/voidT1();/* P(T)*/voidF ();/*P(F)*/int e
7、rrnum=0,k=0,m=0,countchar=0,rownum;int charerr=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);/* 成功打开文件 */*遍历整个文件检测是否有非法字符a a a a a a a a a a a a a a a a a a a /*/
8、*如果用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
9、)/*加换行符后 countchar 仍多了一个，不知为何*/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%d Unindentify characters in file %s n”,errnum,argv1);exit(0);/*正常退出本程序*/则
10、进行识别操作/*非空且无非法字符，十十十十十十十十十十十十十十十十十/*/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;/*s
11、hift指向头结点，以便后面识别操作*/putchar(n);E();/*开始识别一行*/if(shift-ch=#&right) /* 正确提示:文件名Line 行号:right expression!*/printf(%s Line %d:t right expression!n”,argv1,rownum);else/*错误提示:文件名Line 行号:errorexpression!*/printf(%s Line %d:t error expression!n”,argv1,rownum);putchar(n);/*end for*/printf(Completed!n);fclose
12、(fp); /* 关闭文件 */exit(0);/*正常结束程序*/*以下函数分别对应于子模块程序*/void E()T()；E1()；void E1()if(shift-ch=+llshift-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=*llshift-ch=/)shift=shift-next;F()；T1();elseif(shift-ch!=#&shift-ch!=)&shift-ch!=+&shift-ch!=-) right=0; /* 如果不是#or)or+or+or-则出错*/
