《实验5 LL(1)语法分析资料报告程序地设计与实现(C语言)》由会员分享，可在线阅读，更多相关《实验5 LL(1)语法分析资料报告程序地设计与实现(C语言)（19页珍藏版）》请在金锄头文库上搜索。
1、word实验五 LL(1)文法识别程序设计一、实验目的通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。三、实验容与要求实验容：1 阅读并理解实验案例中LL(1)文法判别的程序实现；2 参考实验案例，完成简单的LL(1)文法判别程序设计。四、实验学时4课时五、实验设备与环境 C语言编译环境六、实验案例1 实验要求参考教材93页预测分析方法，94页 图5.11 预测分析程序框图，编写表达式文法的识别程序。要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分
2、析过程。表达式文法为：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
3、#include malloc.h#include conio.h/*定义链表这种数据类型参见：wenku.baidu./link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS#*/struct Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向
4、非终结符堆栈的顶和底*/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=tem
5、p;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:pus
6、h(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=
7、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|
8、curtocmp=E|curtocmp=T|curtocmp=F) /*如果curtocmp圈1*/if(curtocmp!=#) /*如果curtocmp圈1*/changchartoint();if(tableij)圈2*/t=10*i+j; /*计算产生式在数组中的位置*/doforpush(t);圈3*/continue;else圈4*/right=0; /*出错*/break;elseif(curtocmp!=curchar) /*如果curtocmp圈1、1、5、6*/right=0; /*出错*/break;elsebreak;圈1、1、5、7*/elseif(curtocmp!
9、=curchar)圈1、8、9*/right=0; /*出错*/break;else圈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; /*初始化非终结符堆栈，
10、栈底为#，栈顶为文法开始符号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
11、);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
12、(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、判断以下文法是不是LL1文法，写出详细的判断过程：EE+T|E-T|TTT*F|T/F|
13、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
