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

班级:学号:姓名:1实验五LL(1)文法识别程序设计一、实验目的通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。三、实验内容与要求实验内容：1．阅读并理解实验案例中LL(1)文法判别的程序实现；2．参考实验案例，完成简单的LL(1)文法判别程序设计。四、实验学时4课时五、实验设备与环境C语言编译环境六、实验案例1．实验要求参考教材93页预测分析方法，94页图5.11预测分析程序框图，编写表达式文法的识别程序。要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。表达式文法为：EE+T|TTT*F|FFi|(E)2．参考代码班级:学号:姓名:2班级:学号:姓名:3为了更好的理解代码，建议将图5.11做如下标注：班级:学号:姓名:4/*程序名称：LL(1)语法分析程序*//*E-E+T|T*//*T-T*F|F*//*F-(E)|i*//*目的:对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。/********************************************//*程序相关说明*//*A=E'B=T'*//*预测分析表中列号、行号*//*0=E1=E'2=T3=T'4=F*//*0=i1=+2=*3=(4=)5=#*//************************************/#includeiostream#includestdio.h#includemalloc.h#includeconio.h/*定义链表这种数据类型参见：=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/structLchar{charchar_ch;structLchar*next;}Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/班级:学号:姓名:5charcurchar;//存放当前待比较的字符:终结符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)/*非终结符：栈顶*/班级:学号:姓名:6{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,curchar,curtocmp);if(curtocmp=='#'&&curchar=='#')/*如果都是终结符P94图5.11圈1、圈5、圈7*/break;if(curtocmp=='A'||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F')/*如果curtocmp不是终结符P94图5.11圈1*/{if(curtocmp!='#')/*如果curtocmp不是终结符，也不是结束符，则根据预测分析表找到产生式并入栈P94图5.11圈1*/{changchartoint();if(table[i][j])/*[1.1]有产生式P94图5.11圈2*/{t=10*i+j;/*计算产生式在数组中的位置*/doforpush(t);/*找对应t的产生式并入栈P94图5.11圈3*/continue;}else/*[1.2]没有产生式P94图5.11圈4*/{班级:学号:姓名:7right=0;/*出错*/break;}}elseif(curtocmp!=curchar)/*如果curtocmp不是终结符，并且是结束符，判断终结符链表字符是否也为终结符P94图5.11圈1、1、5、6*/{right=0;/*出错*/break;}elsebreak;/*正确P94图5.11圈1、1、5、7*/}elseif(curtocmp!=curchar)/*如果curtocmp是终结符,并且不等于当前终结符链表中的终结符，则出错。P94图5.11圈1、8、9*/{right=0;/*出错*/break;}else/*如果curtocmp是终结符,并且等于当前终结符链表中的终结符，则匹配成功，可以读取下一个链表头的终结符P94图5.11圈10*/{h=h-next;/*读取下一字符*/continue;}}}intmain(void){charch;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;/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号E*//*初始化存放待识别的表达式（终结符）的线性链表头*/h=(structLchar*)malloc(sizeof(Lchar));班级:学号:姓名:8h-next=NULL;p=h;/*开辟了一个空的链表空间,p和h同时指向该空间,该空间将作为终结符链表的头部。*/printf(请输入要分析的字符串(#号结束)\n);do{/*输入待识别的表达式*/ch=getch();putch(ch);//在屏幕上输出一个字符if(ch=='i'||ch=='+'||ch=='*'||ch=='('||ch==')'||ch=='#'){/*将输入的ch存入链表*/temp=(structLchar*)malloc(sizeof(Lchar));temp-next=NULL;temp-char_ch=ch;h-next=temp;h=h-next;/*如果输入正确，h不断的指向新输入的字符，而p始终指向输入终结符字符串的头位置，即前面开辟的空的链表空间。*/}else{temp=p-next;/*如果输入错误，提示输入有错，请重新输入，让temp指向输入字符串的头部，并将前面正确输出的字符串再次输出*/printf(\nInputawrongchar!Inputagain:\n);for(;;){if(temp!=NULL)printf(%c,temp-char_ch);elsebreak;temp=temp-next;}}}while(ch!='#');p=p-next;/*消去第一个空头节点，并使头结点指向非空线性链表表头*//*如果输入正确，h不断的指向新输入的字符，而输入字符串的头位置被记录在p里面。*/h=p;/*h重新指向头结点，以便后面识别操作*/dosome();/*开始识别*/if(right)printf(\n成功!输入的表达式可以被该文法识别！\n);elseprintf(\n错误!表示输入的表达式不可以被该文法识别！\n);getch();return0;}3．测试数据及运行结果班级:学号:姓名:9七、简单LL(1)文法判别程序设计1、判断以下文法是不是LL（1）文法，写出详细的判断过程：EE+T|E-T|TTT*F|T/F|FFi|(E)（1）消除左递归，文法变为：ETE’E’+TE’|-TE’|εTFT’T’*FT’|/FT’|εFi|(E)（2）可推出的非终结符表为：EE’TT’F否是否是否（3）各非终结符的FIRST集合为：班级:学号:姓名:10FIRST(E)={(,i}FIRST(E’)={+,-,ε}FIRST(T)={(,i}FIRST(T’)={*,/,ε}FIRST(F)={(,i}（4）各非终结符的FOLLOW集合为：FOLLOW(E)={）,#}FOLLOW(E’)={）,#}FOLLOW(T)={）,#,+,-}FOLLOW(T’)={）,#,+,-}FOLLOW(F)={*,/,+,-,）,#}（5）各产生式的SELECT集合为：SELECT(ETE’)={(,i}SELECT(E’+TE’)={+}SELECT(E’-TE’)={-}SELECT(E’ε)={）,#}SELECT(TFT’)={(,i}SELECT(T’*FT’)={*}SELECT(T’/FT’)={/}SELECT(T’ε)={+,-,）,#}SELECT(F(E))={(}SELECT(Fi)={i}（6）有相同左部产生式的SELECT集合的交集是否为空？该文法是否为LL（1）文法？（7）该文法的预测分析表为:i+-*/()#E+TE’TE’E’+TE’-TE’εεTFT’T’εε*FT’/FT’εεFi(E)2、设计LL(1)文法判别程序设计，源代码如下：/*程序名称：LL(1)语法分析程序*//*E-E+T|E-T/T*//*T-T*F|T/F/F*//*F-(E)|i*//*目的:对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。/********************************************/班级:学