自上而下语法实验

1、自上而下语法分析1、 实验目的：1.根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。（选做）2.根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。（必做）2、 本次实验的目的主要是加深对自上而下分析法的理解。实验内容：（1） 程序的功能描述LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。具体描述如下： 对下列文法，对任意输入的符号串进行分析：（1）E->TG（2）G->+TG （3）G->（4）T->FS（5）S->*FS（6）S->

2、（7）F->(E)（8）F->i输入一以#结束的符号串(包括+*/（）i#)：输出结果：包括分析栈、数组中的剩余字符串以及所用的产生式，形如：分析栈剩余输入串所用产生式Ei+i*i#E->TG其中有如下两点要求：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；（二）LL（1）分析法实验设计思想及算法XVN#S进栈，当前输入符送sym上托栈顶符号放入X若产生式为X® X1X2Xn按逆序即XnX2X1入栈出错X=#XVTX=aMX,sym是产生式吗出错X=读入下一个符号结束是是是

3、是否否否否否是三、程序设计的过程以及关键函数的功能（一）模块结构：1、定义部分：定义常量、变量、数据结构。2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）；3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则；4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。（二）程序的整体流程及关键函数解析：1、定义一个栈，用于存放非终结符2、 将终结符和非终结符各存放在一个数组中，用于判断栈顶元素是否是终结符或非终结符，然后根据情况判断接下来是查表，还是进行匹

4、配移进。3、 定义一个全局变量f，用于指示从文件中读出的匹配后的剩余字符串中的首个字符在数组中的位置。当输出栈时，同时输出剩余字符串。4、对于chaxun( )函数，X在 v25中的位置相当于表的行位置，sym在v16中的位置，相当于表的列位置。根据查表操作可以判断（X，sym）对于的表中是否有产生式。bool chaxun(char X,char sym)int m=feizhongjie(X );int n=iszhongjie(sym);char str10; strcpy(str,tablemn);if (strlen(str)=0)return false;elseif (str0!

5、='')for (int i=strlen(str)-1;i>=0;i-) push(stri);print();cout<<'t'<<v2m<<"->"<<str<<endl;return true;5、 读文件，并将文件里的内容读入数组b 中。6、根据表中的产生式，对栈顶元素根据情况进行移进匹配操作，知道剩余表达式中无非终结符为止，即匹配成功。否则，则匹配失败，给出的字符表达式无法由给定的文法推出。while (flag&&!cuo) X=pop();

6、/把符号栈的式子付给xif (X='#') if(sym=X)cout<<"输入的是合法符号串"<<endl;flag=false;elsecout<<"非法的符号串"<<endl;else if(iszhongjie(X)!=-1) /如果是终结符跳到if if(X=sym) f+; sym=fgetc(fp); else printf("错误"); else if(!chaxun(X,sym) cuo=true;四、运行结果：输入文件内容：i+i*i若输入i+i*i，

7、显示如下：若输入i*(i+i)，显示如下：五、实验总结 通过本次实验，我初步掌握了ll（1）文法，在写代码的过程中也加深了我对栈的理解，老师课上已经讲解了许多，而且实验时也指导了我们一些该注意的地方，中间还是有一些小问题但是，在判断输入串是否匹配的时候，还是有些问题，不过总体目标还是完成了，当然问题最多的还是栈顶元素与剩余字符串的移进匹配过程，这一点我老是搞不太清楚。不过在同学的帮助和指导下这些问题都慢慢的解决了。不过总体来说，使我的编程能力得到了很大的提高。附录:#include<iostream.h>#include<stdio.h>#include<stdl

8、ib.h>#include<string.h>#include<dos.h>#include <fstream.h>#define error 0struct Stackchar s30;int top; /栈顶指针S1;int f=0;char b20;char v16='i','+','*','(',')','#'/终结符char v25='E','G','T','S','F'

9、;/非终结符 /*用二维数组保存预测分析表，可用符号来代替，注意字符串结束位自动加'0' */char table564="TG"," "," ","TG"," "," "," ","+TG"," "," ","","","FS"," "," ","FS",&qu

10、ot; "," "," ","","*FS"," ","","","i"," "," ","(E)"," "," "void printbiao()cout<<"TG TG "<<endl; cout<<" +TG "<<endl; cout

11、<<"FS FS "<<endl; cout<<" *FS "<<endl; cout<<"i (E) "<<endl;void print()/*输出分析栈 */int a;/*指针*/for(a=0;a<S1.top;a+)cout<<S1.sa;cout<<'t'int len=strlen(b);for(int n=f;n<len;n+)cout<<bn;/*print*/void intia

12、lstack() S1.top=0;void push(char ch) S1.sS1.top=ch;S1.top+;char pop( ) S1.top-;return S1.sS1.top; int iszhongjie(char X )for(int k=0;k<6;k+)if (X=v1k) return k; return -1;/判断X是否为终结符，是返回数组下标int feizhongjie(char f )for(int k=0;k<5;k+)if (f=v2k) return k; return -1;/判断X是否为非终结符，是返回数组下标bool chabiao

13、(char X,char sym)int m=feizhongjie(X );int n=iszhongjie(sym);char str10; strcpy(str,tablemn);if (strlen(str)=0)/cout<<"匹配失败！"<<endl;return false;elseif (str0!='')for (int i=strlen(str)-1;i>=0;i-) push(stri);print();cout<<'t'<<v2m<<"->

14、;"<<str<<endl;return true;/*判断X是否为非终结符，sym是否为终结符，若是查找预测表对应表格是否为空白,是则出错，否则进栈*/void main() printbiao();ifstream file("d:111.txt");file.getline(b,sizeof file);FILE *fp; char sym,X; bool flag,cuo; if(fp=fopen("D:111.txt","r")=NULL) /读取文件内容，并返回文件指针，该指针指向文件的第一个字符 fprintf(stderr,"读取文件失败!n"); exit(1); intialstack();push('#');push('E');sym=fgetc(fp);/把第一个输入符号读进symflag=true;cuo=false;print();cout<<endl;while (flag&&!cuo)