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

资源ID：35944564 资源大小：3.96MB 全文页数：19页
资源格式： DOC 下载积分：15金币

快捷下载

会员登录下载

微信登录下载

三方登录下载：

微信扫一扫登录

下载资源需要15金币

邮箱/手机：
温馨提示：	快捷下载时，用户名和密码都是您填写的邮箱或者手机号，方便查询和重复下载（系统自动生成）。如填写123，账号就是123，密码也是123。
支付方式：
验证码：	换一换

账号：
密码：
验证码：	换一换
当日自动登录忘记密码？

友情提示

1、下载资料失败解决办法

2、PDF文件下载后，可能会被浏览器默认打开，此种情况可以点击浏览器菜单，保存网页到桌面，就可以正常下载了。

3、本站不支持迅雷下载，请使用电脑自带的IE浏览器，或者360浏览器、谷歌浏览器下载即可。

4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩，下载后原文更清晰。

5、试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓。

网站客服

侵权投诉

实验5 LL(1)语法分析程序的设计与实现(C语言)(20页).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=# */*/#include"iostream"#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=# */*/#include"iostream"#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: 时间：-第 19 页-

注意事项

本文（实验5 LL(1)语法分析程序的设计与实现(C语言)(20页).doc）为本站会员（1595****071）主动上传，淘文阁 - 分享文档赚钱的网站仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知淘文阁 - 分享文档赚钱的网站（点击联系客服），我们立即给予删除！

温馨提示：如果因为网速或其他原因下载失败请重新下载，重复下载不扣分。