LL(1)语法分析程序实验报告

LL1实验报告1.设计原理所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言来编写，其逻辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析过程。（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。2.分析LL(1)分析表是一个二维表，它的表列符号是当前符号，包括文法所有的终结和自定义。的句子结束符号#，它的表行符号是可能在文法符号栈SYN中出现的所有符号，包括所有的非终结符，所有出现在产生式右侧且不在首位置的终结符，自定义的句子结束符号#表项。为当前栈符号与当前符号匹配后，所要求的栈操作和输入操作。表项表明了文法的终结符与非终结符是否可能相遇。其中，栈操作包括两种，一是弹栈;二是弹栈后，将符号串ABc反转后压栈;输入操作包括两种，一是读入下一符号，是保持当前符号不变。具体的造算法为171。(1)设A,B为文法的非终结符，C为文法的终结符和非终结符组成的字符串，a为文法的终结符将所有产生式分为四类:6)A-aB，则(A,a)项填写为(B调向后压栈，读入下一个字符):(ii)A-a;A-a,则将〔A,a)项填写为(弹栈，读入下一个字符):(iii)A-BC，则将(A,select(A-BC))项全部填写为(将BC调向后压栈，保持当前字符不读入):(iv)A-N，则将(A,follow(A))项全部填写为(弹栈，保持当前字符不读)。(2)对表行和表列的所有字符进行循环；(3)如果当前表行的字符是非终结符，它必有产生式，依据此产生式的类型，填写表项。(4)如果当前表列的字符不在此产生式的选择集合中，该项填写为Eror。(5)对(#，#)项填写为OK；(6)对当前表行字符为终结符的，只有它与表列字符相同时，才填写为(弹栈，读入下一个字符)，否则填入Eror。3.流程图是是开始读入文法有效？是LL(1)文法？判断句型报错结束数据结构#includeiostream.h#includestdio.h#includemalloc.h#includeconio.hstructLchar{charchar_ch;structLchar*next;}Lchar,*p,*h,*temp,*top,*base;charcurchar;charcurtocmp;intright;inttable[5][8]={{1,0,0,1,0,0},{0,1,0,0,1,1},{1,0,0,1,0,0},{0,1,1,0,1,1},{1,0,0,1,0,0}};inti,j;voidpush(charpchar){temp=(structLchar*)malloc(sizeof(Lchar));temp-char_ch=pchar;temp-next=top;top=temp;}voidpop(void){curtocmp=top-char_ch;if(top-char_ch!='#')top=top-next;}voiddoforpush(intt){switch(t){case0:push('A');push('T');break;case5:push('A');push('T');break;case11:push('A');push('T');push('+');break;case20:push('B');push('F');break;case23:push('B');push('F');break;case32:push('B');push('F');push('*');break;case40:push('i');break;case43:push(')');push('E');push('(');}}voidchangchartoint(){switch(curtocmp){case'A':i=1;break;case'B':i=3;break;case'E':i=0;break;case'T':i=2;break;case'F':i=4;}switch(curchar){case'i':j=0;break;case'+':j=1;break;case'*':j=2;break;case'(':j=3;break;case')':j=4;break;case'#':j=5;}}voiddosome(void){intt;for(;;){pop();curchar=h-char_ch;printf(\n%c\t%c,curchar,curtocmp);if(curtocmp=='#'&&curchar=='#')break;if(curtocmp=='A'||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F'){if(curtocmp!='#'){changchartoint();if(table[i][j]){t=10*i+j;doforpush(t);continue;}else{right=0;break;}}elseif(curtocmp!=curchar){right=0;break;}elsebreak;}elseif(curtocmp!=curchar){right=0;break;}else{h=h-next;continue;}}}voidmain(void){charch;cout*文件名称:语法分析endl;coutendl;cout/*程序相关说明*/endl;cout---------------------------------------------------------------------endl;cout-/*A=E’B=T’*/endl;cout-*目的:对输入LL(1)文法字符串，本程序能自动判断所给字符串是-endl;cout-*否为所给文法的句子，并能给出分析过程。-endl;cout-*-------------------------------------------------------------------endl;cout表达式文法为：endl;coutE-E+T|Tendl;coutT-T*F|Fendl;coutF-(E)|iendl;cout请在下行输入要分析的串(#号结束)：endl;right=1;base=(structLchar*)malloc(sizeof(Lchar));base-next=NULL;base-char_ch='#';temp=(structLchar*)malloc(sizeof(Lchar));temp-next=base;temp-char_ch='E';top=temp;h=(structLchar*)malloc(sizeof(Lchar));h-next=NULL;p=h;do{ch=getch();putch(ch);if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'){temp=(structLchar*)malloc(sizeof(Lchar));temp-next=NULL;temp-char_ch=ch;h-next=temp;h=h-next;}else{temp=p-next;printf(\nInputawrongchar!Inputagain:\n);for(;;){if(temp!=NULL)printf(%c,temp-char_ch);elsebreak;temp=temp-next;}}}while(ch!='#');p=p-next;h=p;dosome();if(right)printf(\n成功!\n);elseprintf(\n错误!\n);getch();}截图：