实验语法分析程序的设计和实现语言.doc
《实验语法分析程序的设计和实现语言.doc》由会员分享,可在线阅读,更多相关《实验语法分析程序的设计和实现语言.doc(25页珍藏版)》请在咨信网上搜索。
1、实验五 LL(1)文法辨认程序设计一、实验目通过LL(1)文法辨认程序设计理解自顶向下语法分析思想。二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素求解,预测分析表构造。三、实验内容与规定实验内容:1 阅读并理解实验案例中LL(1)文法鉴别程序实现;2 参照实验案例,完毕简朴LL(1)文法鉴别程序设计。四、实验学时4学时五、实验设备与环境 C语言编译环境六、实验案例1 实验规定参照教材93页预测分析办法,94页 图5.11 预测分析程序框图,编写表达式文法辨认程序。规定对输入LL(1)文法字符串,程序能自动判断所给字符串与否为所给文法句子,并能给出分析过程。表达式文法为:E
2、E+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.
3、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;
4、/*存储预测分析表,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(
5、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) /
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;/*辨认算法*/void dosome(void)int t;for(;)pop();/*读取栈顶字符存curtocmp中*/curchar=h-char_ch;/*读
7、取输入字符链表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(t
8、ableij) /*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(curt
9、ocmp!=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=N
10、ULL;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();put
11、ch(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
12、 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(
13、);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)=
14、 ),#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-T
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 语法分析 程序 设计 实现 语言
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。