编译原理语法实验

实验二：自上而下语法分析一、实验目的：根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对自上而下分析法的理解。二、实验预习提示自下而上分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法A．递归下降1、递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2、递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构：(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。(2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。具体为：（1）对于每个非终结符号U-u1|u2|…|un处理的方法如下：U(){ch=当前符号;if(ch可能是u1字的开头)处理u1的程序部分;elseif(ch可能是u2字的开头)处理u2的程序部分;…elseerror()}（2）对于每个右部u1-x1x2…xn的处理架构如下：处理x1的程序；处理x2的程序；…处理xn的程序；（3）如果右部为空，则不处理。（4）对于右部中的每个符号xi①如果xi为终结符号：if(xi==当前的符号){NextChar()；return;}else出错处理②如果xi为非终结符号，直接调用相应的过程xi()说明：NextChar为前进一个字符函数。B．LL（1）分析法1、LL（1）分析法的功能LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。2、LL（1）分析法实验设计思想及算法三、实验过程和指导：（一）准备：1.阅读课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：对下列文法，用两种分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG（3）G-ε（4）T-FS（5）S-*FS（6）S-ε（7）F-(E)X∈VN‘#’‘S’进栈，当前输入符送a上托栈顶符号放入X若产生式为XX1X2…Xn按逆序即Xn…X2X1入栈出错X=’#’X∈VTX=aM[X,a]是产生式吗出错X=a读入下一个符号结束是是是是否否否否否是（8）F-i输出的格式如下：(1)递归下降分析程序输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#输出结果：i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。(2)LL（1）分析：输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#输出结果：i+i*i#为合法符号串注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。分析栈剩余输入串所用产生式Ei+i*i#E-TG4.与读文件有关的函数：FILE*fp;if((fp=fopen(E:\\222.txt,r))==NULL){//读取文件内容，并返回文件指针，该指针指向文件的第一个字符fprintf(stderr,erroropening.\n);exit(1);}fgetc（fp）从数据流中区下一个字符fopen文件打开函数，返回指向文件第一个字符的指针（四）程序思路（仅供参考）：递归下降分析法：0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将输入符号串输入到字符缓冲区中。2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。LL（1）分析法：模块结构：1、定义部分：定义常量、变量、数据结构。2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）；3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则；4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。部分代码示例：#includestdio.h#includestdlib.h#includestring.h#includedos.hstructStack{chars[30];inttop;/*栈顶指针*/}S1;charv1[6]={'i','+','*','(',')','#'};/*终结符*/charv2[5]={'E','G','T','S','F'};/*非终结符*//*用二维数组保存预测分析表，可用符号^来代替ε，注意字符串结束位自动加'\0'*/chartable[5][6][4]={{“TG”,””,””,””,”TG”,””},{…},{…},{…},{…}}voidprint()/*输出分析栈*/{inta;/*指针*/for(a=0;aS1.top;a++)coutS1.s[a];coutendl;}/*print*/voidintialstack(){S1.top=0;}voidpush(charch){S1.s[S1.top]=ch;S1.top++;}charpop(){S1.top--;returnS1.s[S1.top];}voidjinzhan(inthang,intlie){…….}intiszhongjie(charX){…..}/*判断X是否为终结符，返回下标*/boolchabiao(charX,charsym){……}/*判断X是否为非终结符，sym是否为终结符，若是查找预测表对应表格是否为空白,是则出错，否则进栈*/voidmain(){FILE*fp;charsym,X;boolflag,cuo;if((fp=fopen(E:\\222.txt,r))==NULL){//读取文件内容，并返回文件指针，该指针指向文件的第一个字符fprintf(stderr,erroropening.\n);exit(1);}initialstack();push('#');push('E');sym=fgetc(fp);/*把第一个输入符号读进sym*/flag=true;cuo=falsewhile(flag&&!error){X=pop();if(X=='#'){….}elseifiszhongjie(X){……}elseif(!chabiao(X,sym))cuo=true;}}（五）练习该实验的目的和思路：需要利用程序设计语言的知识和大量编程技巧，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。五、上交：实验报告：实验名称实验目的和要求（一）实验内容（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。（3）程序源代码（二）实验过程记录：出错次数、出错严重程度、解决办法摘要。（三）实验总结：你在编程过程中花时多少？遇到了哪些难题？你是怎么克服的？你的收获有哪些？自上而下分析算法#includestdio.h#includestdlib.h#defineERROR0charsym;//用于临时存储文件中读出的单个字符FILE*fp;//读取文件的指针//非终结符定义的方法voide();voidg();voidt();voids();voidf();//读取文件中的下一个字符voidadvance();voidmain(){if((fp=fopen(E:\\222.txt,r))==NULL)//读取文件内容，并返回文件指针，该指针指向文件的第一个字符{fprintf(stderr,erroropening.\n);exit(1);}e();}//对应产生式（1）E-TGvoide(){advance();t();g();if(sym=='#'){printf(输入的为合法的字符串\n);}else{printf(非法字符串);}}//对应产生式（2）G-+TG（3）G-ε空：不做任何处理voidg(){if(sym=='+'){printf(+);advance();t();g();}}//对应产生式（4）T-FSvoidt(){f();s();}//对应产生式（5）S-*FS（6）S-εvoids(){if(sym=='*'){printf(*);advance();f();s();}}//对应产生式（7）F-(E)（8）F-ivoidf(){if(sym=='('){advance();e();if(sym==')')advance();else{printf(非法字符串);exit(ERROR);}}elseif(sym=='i'){printf(i);advance();}else{printf(非法字符串);exit(ERROR);}}voidadvance(){sym=fgetc(fp);//从数据流中区下一个字符}预测表分析法#includestdio.h#includestdlib.h#includestring.h#includedos.hstructStack{chars[30];inttop;/*栈顶指针*/}S1;intnum=0;charv1[6]={'i','+','*','(',')','#'};/*终结符*/charv2[5]={'E','G','T','S','F'};/*非终结符*//*用二维数组保存预测分析表，可用符号^来代替ε，注意字符串结束位自动加'\0'*/chartable[5][6][4]={{GT,,,GT,,},{,GT+,,,^,^},{SF,,,SF,,},{,^,SF*,,^,^},{i,,,)E(,,}};voidprint()/*输出分析栈*/{inta;/*指针*/for(a=0;aS1.top;a++)printf(%c,S1.s[a]);printf(\t);}/*print*/voidintialstack(){S1.top=0;}/*初始化栈*/voidpush(charch){S1.s[S1.top]=ch;S1.top++;}/*压栈*/charpop(){S1.top--;returnS1.s[S1.top];}/*出栈*/voidjinzhan(inthang,intlie){char*chuan;chuan=table[hang][lie];chuan[3]='\0';inti=0;while(chuan[i]!=NULL&&chuan[0]!='^'){push(chuan[i]);i++;}}/*进栈操作，将符号串数组压入栈中*/intiszhongjie(charX){for(inti=0;i6;i++)if(X==v1[i])returni;return-1;}/*判断X是否为终结符，返回下标*/intisfzhongjie(charX){for(inti=0;i5;i++)if(X==v2[i])returni;return-1;}/*判断X是否为非终结符，返回下标*/boolchabiao(charX,charsym){inthang=isfzhongjie(X);intlie=iszhongjie(sym