语法分析程序的设计与实现C语言.doc
《语法分析程序的设计与实现C语言.doc》由会员分享,可在线阅读,更多相关《语法分析程序的设计与实现C语言.doc(26页珍藏版)》请在咨信网上搜索。
1、实验五 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#i
3、nclude 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
4、,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
5、(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 changcharto
6、int()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();/*读取栈顶的字符存curtocm
7、p中*/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.
8、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; /
9、*对的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);
10、 /*初始化非终结符堆栈,栈底为#,栈顶为文法开始符号*/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(
11、请输入要分析的字符串(#号结束)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; /*假如输入错误,提醒输入有错,请重
12、新输入,让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)print
13、f(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)=(
14、,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
- 配套讲稿:
如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。