实验语法分析程序的设计和实现语言.doc

实验五 LL(1)文法辨认程序设计一、实验目通过LL(1)文法辨认程序设计理解自顶向下语法分析思想。二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素求解，预测分析表构造。三、实验内容与规定实验内容：1 阅读并理解实验案例中LL(1)文法鉴别程序实现；2 参照实验案例，完毕简朴LL(1)文法鉴别程序设计。四、实验学时4学时五、实验设备与环境 C语言编译环境六、实验案例1 实验规定参照教材93页预测分析办法，94页 图5.11 预测分析程序框图，编写表达式文法辨认程序。规定对输入LL(1)文法字符串，程序能自动判断所给字符串与否为所给文法句子，并能给出分析过程。表达式文法为：EE+T|TTT*F|FFi|(E) 2 参照代码为了更好理解代码，建议将图5.11做如下标注：/* 程序名称： LL(1)语法分析程序 */* E-E+T|T */* T-T*F|F */* F-(E)|i */*目 ：对输入LL(1)文法字符串，本程序能自动判断所给字符串与否为所给文法句子，并能给出分析过程。/*/* 程序有关阐明 */* A=E B=T */* 预测分析表中列号、行号 */* 0=E 1=E 2=T 3=T 4=F */* 0=i 1=+ 2=* 3=( 4=) 5=# */*/#includeiostream#include stdio.h#include malloc.h#include conio.h/*定义链表这种数据类型参见：*/struct Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表头结点，h指向动态建成终结符线性链表节点，top和base分别指向非终结符堆栈顶和底*/char curchar；/存储当前待比较字符:终结符char curtocmp；/存储当前栈顶字符：非终结符int right;int table56=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表达无产生式。*/int i,j; void push(char pchar) /*入栈函数*/temp=(struct Lchar*)malloc(sizeof(Lchar);temp-char_ch=pchar;temp-next=top;top=temp; void pop(void) /*出栈函数*/curtocmp=top-char_ch;if(top-char_ch!=#)top=top-next;void doforpush(int t) /*依照数组下标计算值找相应产生式，并入栈*/switch(t)case 0:push(A);push(T);break;case 3:push(A);push(T);break;case 11:push(A);push(T);push(+);break;case 20:push(B);push(F);break;case 23:push(B);push(F);break;case 32:push(B);push(F);push(*);break;case 40:push(i);break;case 43:push();push(E);push();/*依照curchar和curtocmp转为数字以判断与否有产生式*/void changchartoint()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;/*辨认算法*/void dosome(void)int t;for(;)pop();/*读取栈顶字符存curtocmp中*/curchar=h-char_ch；/*读取输入字符链表h中一种字符存入curchar*/printf(n%ct%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(tableij) /*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;else if(curtocmp!=curchar) /*如果curtocmp不是终结符，并且是结束符，判断终结符链表字符与否也为终结符P94 图5.11圈1、1、5、6*/right=0；/*出错*/break;elsebreak；/*对的P94 图5.11圈1、1、5、7*/else if(curtocmp!=curchar) /* 如果curtocmp是终结符,并且不等于当前终结符链表中终结符，则出错。P94 图5.11圈1、8、9*/right=0；/*出错*/break;else /*如果curtocmp是终结符,并且等于当前终结符链表中终结符，则匹配成功，可以读取下一种链表头终结符P94 图5.11圈10*/h=h-next；/*读取下一字符*/continue;int main(void)char ch;right=1;base=(struct Lchar*)malloc(sizeof(Lchar)；/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号*/base-next=NULL；base-char_ch=#;temp=(struct Lchar*)malloc(sizeof(Lchar);temp-next=base;temp-char_ch=E;top=temp；/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号E*/*初始化存储待辨认表达式（终结符）线性链表头*/h=(struct Lchar*)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=(struct Lchar*)malloc(sizeof(Lchar);temp-next=NULL;temp-char_ch=ch;h-next=temp;h=h-next;/*如果输入对的，h不断指向新输入字符，而p始终指向输入终结符字符串头位置，即前面开辟空链表空间。*/elsetemp=p-next；/*如果输入错误，提示输入有错，请重新输入，让temp指向输入字符串头部，并将前面对的输出字符串再次输出*/printf(nInput a wrong char!Input again: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();return 0;3 测试数据及运营成果七、简朴LL(1)文法鉴别程序设计1、判断如下文法是不是LL（1）文法，写出详细判断过程：EE+T|E-T|TTT*F|T/F|FFi|(E)（1） 消除左递归，文法变为：ETEE+TE | -TE | TFTT*FT | /FT |Fi | (E)（2） 可推出非终结符表为：EETTF否是否是否（3） 各非终结符FIRST集合为：FIRST(E) = (,iFIRST(E) =+,-,FIRST(T)=(,iFIRST(T) =*,/,FIRST(F) =(,i（4） 各非终结符FOLLOW集合为：FOLLOW(E) = ）,#FOLLOW(E)= ）,#FOLLOW(T) = ）,#,+,-FOLLOW(T)= ）,#,+,-FOLLOW(F) = *,/,+,-,）,#（5） 各产生式SELECT集合为：SELECT(ETE)=(,iSELECT(E+TE)=+SELECT(E-TE)=-SELECT(E)= ）,#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T/FT)=/SELECT(T)= +,-,）,#SELECT(F(E)=(SELECT(Fi)=i（6） 有相似左部产生式SELECT集合交集与否为空？该文法与否为LL（1）文法？（7） 该文法预测分析表为:i+-*/()#E+TETEE+TE-TETFTT*FT/FTFi(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=E 1=E 2=T 3=T 4=F */* 0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=# */*/#includeiostream#include stdio.h#include malloc.h#include conio.h/*定义链表这种数据类型参见：*/struct Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表头结点，h指向动态建成终结符线性链表节点，top和base分别指向非终结符堆栈顶和底*/char curchar；/存储当前待比较字符:终结符char curtocmp；/存储当前栈顶字符：非终结符int right;int table58=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表达无产生式。*/int i,j; void push(char pchar) /*入栈函数*/temp=(struct Lchar*)malloc(sizeof(Lchar);temp-char_ch=pchar;temp-next=top;top=temp; void pop(void) /*出栈函数*/curtocmp=top-char_ch;if(top-char_ch!=#)top=top-next;void doforpush(int t) /*依照数组下标计算值找相应产生式，并入栈*/switch(t)case 0:push(A);push(T);break;case 5:push(A);push(T);break;case 11:push(A);push(T);push(+);break;case 12:push(A);push(T);push(-);break;case 20:push(B);push(F);break;case 25:push(B);push(F);break;case 33:push(B);push(F);push(*);break;case 34:push(B);push(F);push(/);break;case 40:push(i);break;case 45:push();push(E);push();break;/*依照curchar和curtocmp转为数字以判断与否有产生式*/void changchartoint()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;/*辨认算法*/void dosome(void)int t;for(;)pop();/*读取栈顶字符存curtocmp中*/curchar=h-char_ch；/*读取输入字符链表h中一种字符存入curchar*/printf(n%ct%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(tableij) /*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;else if(curtocmp!=curchar) /*如果curtocmp不是终结符，并且是结束符，判断终结符链表字符与否也为终结符P94 图5.11圈1、1、5、6*/right=0；/*出错*/break;elsebreak；/*对的P94 图5.11圈1、1、5、7*/else if(curtocmp!=curchar) /* 如果curtocmp是终结符,并且不等于当前终结符链表中终结符，则出错。P94 图5.11圈1、8、9*/right=0；/*出错*/break;else /*如果curtocmp是终结符,并且等于当前终结符链表中终结符，则匹配成功，可以读取下一种链表头终结符P94 图5.11圈10*/h=h-next；/*读取下一字符*/continue;int main(void)char ch;right=1;base=(struct Lchar*)malloc(sizeof(Lchar)；/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号*/base-next=NULL；base-char_ch=#;temp=(struct Lchar*)malloc(sizeof(Lchar);temp-next=base;temp-char_ch=E;top=temp；/*初始化非终结符堆栈，栈底为#，栈顶为文法开始符号E*/*初始化存储待辨认表达式（终结符）线性链表头*/h=(struct Lchar*)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=(struct Lchar*)malloc(sizeof(Lchar);temp-next=NULL;temp-char_ch=ch;h-next=temp;h=h-next;/*如果输入对的，h不断指向新输入字符，而p始终指向输入终结符字符串头位置，即前面开辟空链表空间。*/elsetemp=p-next；/*如果输入错误，提示输入有错，请重新输入，让temp指向输入字符串头部，并将前面对的输出字符串再次输出*/printf(nInput a wrong char!Input again: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();return 0;3、测试数据及运营成果,运营成果截图应包括姓名或学号信息.截图应包括一种正例 i*(i+i)-i/i# 一种反例i*(i+i)-i-/i# 正例成功截图如下：反例成功截图如下：4、实验总结、心得体会在进行本次实验上机前应当做好准备：按照教师提供教材P93页图4.11预测分析程序流程图熟悉预测分析工作过程。计算出要分析文法FIRST集合、FOLLOW集合和SELECT集合。依照得出各个集合得出构造预测分析表。在教师解说其实验目、规定和分析后，选取相应数据，使用C语言参照算法中流程编写词法分析程序。将编写好程序上次调试（涉及正例和反例）。通过本次程序设计，更加清晰明白了LL(1)分析法过程，从而也比较纯熟掌握了自上而下语法分析基本思想，此外，在教师解说下初步结识了数据构造知识，加上自己理解，与所学知识加以联系，将知识归纳在系统中。在实现和调试时采用模块化思想，是本次课程设计比较顺利，增强了自己信心，提高了自己编程能力和动手能力以及独立分析问题、解决问题能力和综合运用所学知识能力。5.思考：词法分析与语法分析不同区别：顾名思义，词法分析器检查是词法，语法分析器分析是语法，什么是词法，什么是语法。所谓词法，源代码由字符流构成，字符流中涉及核心字，变量名，办法名，括号等等符号，其中变量名要满足不能涉及标点符号，不能以数字开头数字与字母字符串这个条件，对于括号要成对浮现等等，这就是词法;而语法，词法没有问题才干进入语法分析，语法就是词排列办法，字面意义， 语法分析器就是分析类似这样语法。教师评语：与否完毕实验程序预备设计？ 是： 不是：程序能否正常运营？ 是： 不是：有无测试数据及成果分析 是： 不是：与否在本次规定期间完毕所有项目？ 是： 不是：实验成绩级别：教师签名：N0： 时间：