语法分析程序的设计与实现C语言

实验五LL(1)文法辨认程序设计一、实验目的通过LL(1)文法辨认程序的设计理解自顶向下的语法分析思想。二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。三、实验内容与规定实验内容：阅读并理解实验案例中LL(1)文法判别的程序实现；参考实验案例，完毕简朴的LL(1)文法判别程序设计。四、实验学时4课时五、实验设备与环境C语言编译环境六、实验案例实验规定参考教材93页预测分析方法，94页图5.11预测分析程序框图，编写表达式文法的辨认程序。规定对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。表达式文法为：EE+T|TTT*F|FFi|(E)参考代码为了更好的理解代码，建议将图5.11做如下标注：/*程序名称：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=#*//************************************/#include"iostream"#include"stdio.h"#include"malloc.h"#include"conio.h"/*定义链表这种数据类型参见：*/structLchar{charchar_ch;structLchar*next;}Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/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",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*/{right=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));h->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;}测试数据及运营结果七、简朴LL(1)文法判别程序设计1、判断以下文法是不是LL（1）文法，写出具体的判断过程：EE+T|E-T|TTT*F|T/F|FFi|(E)消除左递归，文法变为：ETE’E’+TE’|-TE’|εTFT’T’*FT’|/FT’|εFi|(E)可推出的非终结符表为：EE’TT’F否是否是否各非终结符的FIRST集合为：FIRST(E)={(,i}FIRST(E’)={+,-,ε}FIRST(T)={(,i}FIRST(T’)={*,/,ε}FIRST(F)={(,i}各非终结符的FOLLOW集合为：FOLLOW(E)={）,#}FOLLOW(E’)={）,#}FOLLOW(T)={）,#,+,-}FOLLOW(T’)={）,#,+,-}FOLLOW(F)={*,/,+,-,）,#}各产生式的SELECT集合为：SELECT(ETE’)={(,i}SELECT(E’+TE’)={+}SELECT(E’-TE’)={-}SELECT(E’ε)={）,#}SELECT(TFT’)={(,i}SELECT(T’*FT’)={*}SELECT(T’/FT’)={/}SELECT(T’ε)={+,-,）,#}SELECT(F(E))={(}SELECT(Fi)={i}有相同左部产生式的SELECT集合的交集是否为空？该文法是否为LL（1）文法？该文法的预测分析表为:i+-*/()#E+TE’TE’E’+TE’-TE’εεTFT’T’εε*FT’/FT’εεFi(E)2、设计LL(1)文法判别程序设计，源代码如下：/*程序名称：LL(1)语法分析程序*//*E->E+T|E-T/T*//*T->T*F|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=(6=)7=#*//************************************/#include"iostream"#include"stdio.h"#include"malloc.h"#include"conio.h"/*定义链表这种数据类型参见：*/structLchar{charchar_ch;structLchar*next;}Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/charcurchar;//存放当前待比较的字符:终结符charcurtocmp;//存放当前栈顶的字符：非终结符intright;inttable[5][8]={{1,0,0,0,0,1,0,0},{0,1,1,0,0,0,1,1},{1,0,0,0,0,1,0,0},{0,1,1,1,1,0,1,1},{1,0,0,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;case5:push('A');push('T');break;case11:push('A');push('T');push('+');break;case12:push('A');push('T');push('-');break;case20:push('B');push('F');break;case25:push('B');push('F');break;case33:push('B');push('F');push('*');break;case34:push('B');push('F');push('/');break;case40:push('i');break;case45:push(')');push('E');push('(');break;}}/*根据curchar和curtocmp转为数字以判断是否有产生式*/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;break;case')':j=6;break;case'#':j=7;}}/*辨认算法*/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*/{right=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));h->next=NULL;p=h;/*开辟了一个空的链表空间,p和h同时指向该空间,该空间将作为终结符链表的头部。*/printf("请输入要分析的字符串(#号结束)\n");do{/*输入待辨认的表达式*/ch=getchar();putchar(ch);//在屏幕上输出一个字符if(ch=='i'||ch=='+'||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;/*假如输入对的，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错误!表达输入的表达式不可以被该文法辨认