实验5 LL(1)语法分析程序的设计与实现(C语言).doc

实验五LL(1)文法识别程序设计一、实验目的通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素的求解,预测分析表的构造。三、实验内容与要求实验内容:阅读并理解实验案例中LL(1)文法判别的程序实现;参考实验案例,完成简单的LL(1)文法判别程序设计。四、实验学时4课时五、实验设备与环境C语言编译环境六、实验案例实验要求参考教材93页预测分析方法,,编写表达式文法的识别程序。要求对输入的LL(1)文法字符串,程序能自动判断所给字符串是否为所给文法的句子,并能给出分析过程。Apkct。表达式文法为:EE+T|TTT*F|FFi|(E)参考代码为了更好的理解代码,:/*程序名称:LL(1)语法分析程序*//*E->E+T|T*//*T->T*F|F*//*F->(E)|i*//*目的:对输入LL(1)文法字符串,本程序能自动判断所给字符串是否为所给文法的句子,并能给出分析过程。gxc5g。/********************************************//*程序相关说明*//*A=E'B=T'*//*预测分析表中列号、行号*//*0=E1=E'2=T3=T'4=F*//*0=i1=+2=*3=(4=)5=#*//************************************/#include"iostream"#include""#include""#include""/*定义链表这种数据类型参见:*/structLchar{charchar_ch;structLchar*next;}Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表的头结点,h指向动态建成的终结符线性链表节点,top和base分别指向非终结符堆栈的顶和底*/QJrLi。charcurchar;//存放当前待比较的字符:终结符charcurtocmp;//存放当前栈顶的字符:非终结符intright;inttable[5][6]={{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}};/*存放预测分析表,1表示有产生式,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;case3: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('(');}}/*根据curchar和curtocmp转为数字以判断是否有产生式*/voidchangchartoint(){switch(curtocmp)/*非终结符:栈顶*/{case'E':i=0;break;case'A':i=1;break;case'T':i=2;break;case'B':i=3;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();/*读取栈顶的字符存curtocmp中*/curchar=h->char_ch;/*读取输入字符链表h中一个字符存入curchar*/printf("\n%c\t%c"