实验报告四递归下降语法分析程序设计

1、编译原理实验报告实验序号：4实验项目名称：递归下降语法分析程序设计学号姓名专业、班实验地点指导教师实验时间一、实验目的及要求编程识别由下列文法所定义的表达式的递归下降语法分析器。 EE+T | E-T | T TT*F | T/F |F F(E) | i 输入：每行含一个表达式的文本文件。输出：分析成功或不成功信息。二、实验设备（环境）及要求装有 VC+ 的PC机三、实验内容与步骤（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) 对

2、于以上改进的方法。可得：对于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 )=FIR

3、ST(T)FOLLOW(T)=*，+，)，#由以上FOLLOW集可以我们可以得出SELECT集如下：对ESELECT（ETE）=FIRST(TE)=FIRST(T)= (，i 对E SELECT（E +TE）= + SELECT（E TE）= SELECT（E ）=，)，#对TSELECT（TFT）=(，i对T SELECT（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）

4、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)。（3）程序代码如下/* *文件名：ana.c *文件描述：递归下降语法分析器。分析如下方法： *E-E+T | E-T | T *T-T*F | T/

5、F |F *F-(E) | i *输入：每行含一个表达式的文本文件。 *输出：分析成功或不成功信息。 *创建人：余洪周 2006-12-8 *版本号：1.0 */#include#include#define READ(ch) ch=getc(fp)/*宏：READ(ch)*/char ch;/*声明为全局变量*/intright=0;FILE*fp;struct struCHchar ch;structstruCH *next;struCH,*temp,*head,*shift;/*head指向字符线性链表的头结点*/*shift指向动态建成的结点(游标)*/void main(int ar

6、gc,char *argv)voidE ();/* P(E) */voidE1();/* P(E)*/voidT ();/* P(T) */voidT1();/* P(T)*/voidF ();/* P(F) */int errnum=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 p

7、rintf(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 bl

8、ank file!n,argv1); exit(0);/*正常退出本程序*/*2开始遍历文件*/while(k(countchar-1) /*加换行符后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

9、 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;/*消去第

10、一个空头结点,并使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(

11、n);/*end for*/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();els

12、eif(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;（4）调试1.编译：在Windows平台下，用Turbo C 2编译连接生成后test4.exe；2.输入表达式：在ana.exe程序同一目录下新建一文本文件(如：test.txt)。往文本文件中输入要识别的表达式，表达式以“#”结束，可输入多行。同一行“#”以后的内容在识别过种中将自动丢弃。如将以下内容存入test.txt文件中：i-i#i#+i#(i+i)*i#+3.运行：打开Dos控制台，进入程序所在的目录(如C:)。输入：程序名 存放表达式的txt文件名，如:test test.txt四、实验结果与数据处理 1.在Windows平