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

《编译原理》实验报告实验序号：4实验项目名称：递归下降语法分析程序设计学号姓名专业、班实验地点指导教师实验时间一、实验目的及要求编程识别由下列文法所定义的表达式的递归下降语法分析器。EE+T|E-T|TTT*F|T/F|FF(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)对于以上改进的方法。可得：对于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（ETE’）=FIRST(TE’)=FIRST(T)={(，i}对E’SELECT（E’+TE’）={+}SELECT（E’−TE’）={−}SELECT（E’ε）={ε，)，#}对TSELECT（TFT’）={(，i}对T’SELECT（T’*FT’）={*}SELECT（T’∕FT’）={∕}SELECT（T’ε）={ε，+，−，)，#}对FSELECT（F(E)）={(}SELECT（Fi）={i}∴SELECT(E’+TE’)∩SELECT（E’−TE’）∩SELECT（E’ε）=SELECT(T’*FT’)∩SELECT（T’∕FT’）∩SELECT（T’ε）=SELECT（F(E)）∩SELECT（Fi）=由上可知，有相同左部产生式的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/F|F*F-(E)|i*输入：每行含一个表达式的文本文件。*输出：分析成功或不成功信息。*创建人：余洪周[e-mail]2006-12-8*版本号：1.0***********************************************************************/#includestdio.h#includemalloc.h#defineREAD(ch)ch=getc(fp)/*宏：READ(ch)*/charch;/*声明为全局变量*/intright=0;FILE*fp;structstruCH{charch;structstruCH*next;}struCH,*temp,*head,*shift;/*head指向字符线性链表的头结点*//*shift指向动态建成的结点(游标)*/voidmain(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(argv[1],r))==NULL){printf(\n\tCannotopenfile%s,ornotexistit!\n,argv[1]);exit(0);/*文件不存在or打不开时，正常退出程序*/}elseprintf(\n\tSuccessopenfile:%s\n,argv[1]);/*成功打开文件*//******************遍历整个文件检测是否有非法字符********************//*如果用while(!feof(fp))语言，将会多出一个字符*所以这里采用以下方法遍历整个文件检测其否有非法字符*//*[1]计算文件中字符数量*/while(!feof(fp)){READ(ch);/*这里读取字符只是让文件指针往前移*/countchar++;/*统计文件中的字符数(包括换行符及文件结束符)*/}rewind(fp);/*将fp文件指针重新指向文件头处，以备后面对文件的操作*/if(countchar==0){/*空文件*/printf(\t%sisablankfile!\n,argv[1]);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(\n\t%dUnindentifycharactersinfile%s\n,errnum,argv[1]);exit(0);/*正常退出本程序*/}/*******************非空且无非法字符，则进行识别操作*****************/for(rownum=1;m(countchar-1);rownum++){/*识别所有行,rownum记录行号*//*初始变量及堆栈和*/right=1;/*初始存放待识别的表达式的线性链表头*/shift=malloc(sizeof(struCH));/**/shift-next=NULL;head=shift;/*读取一行形成线性链表*/READ(ch);putchar(ch);m++;while(ch!='\n'&&m(countchar)){/*行末or到文件尾。最后会读取文件结束符*//*读取ch,读取存入结点，这样每行便形成一个线性链表*/temp=malloc(sizeof(struCH));temp-ch=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[行号]:rightexpression!*/printf(%sLine%d:\trightexpression!\n,argv[1],rownum);else/*错误提示:[文件名]Line[行号]:errorexpression!*/printf(%sLine%d:\terrorexpression!\n,argv[1],rownum);putchar('\n');}/*endfor*/printf(Completed!\n);fclose(fp);/*关闭文件*/exit(0);/*正常结束程序*/}/*以下函数分别对应于子模块程序*/voidE(){T();E1();}voidE1(){if(shift-ch=='+'||shift-ch=='-'){shift=shift-next;T();E1();}else{if(shift-ch=='#'||shift-ch==')')return;elseright=0;}}voidT(void){F();T1();}voidT1(void){if(shift-ch=='*'||shift-ch=='/'){shift=shift-next;F();T1();}else{if(shift-ch!='#'&&shift-ch!=')'&&shift-ch!='+'&&shift-ch!='-')right=0;/*如果不是'#'or')'or'+'or'+'or'-'则出错*/}}voidF(void){if(shift-ch=='i')shift=shift-next;else{if(shift-ch=='('){shift=shift-next;E();if(shift-ch==')')shift=shift-next;elseright=0;}elseright=0;}}（4）调试1.编译：在Windows平台下，用TurboC2编译连接生成后test4.exe；2.输入表达式：在ana.exe程序同一目录下新建一文本文件(如：test.txt)。往文本文件中输入要识别的表达式，表达式以“#”结束，可输入多行。同一行“#”以后的内容在识别过种中将自动丢弃。如将以下内容存入test.txt文件中：i-i##i#++i#(i+i)*i#++3.运行：打开Dos控制台，进入程序所在的目录(如C:\)。输入：[程序名][存放表达式的txt文件名]，如:testtest.txt四、实验结果与数据处理1.在Windows平台下，用TurboC2编译连接生成后test4.exe。文件与输入表达式如下图：2.打开Dos控制台，进入程序所在的目录，运行test4test.txt结果如下图：五、分析与讨论所给文法E=E+T=E+T*F=E+T*(E)即有E=E+T*(E)存在左递归，因此必须消除左递归，可以采取提取公因子的方法消除左递归通过该实验，让自己更加的了解递归下降语法分析器。六、教师评语签名：日期：成绩