《递归下降分析法实现LL文法的语法分析器》由会员分享，可在线阅读，更多相关《递归下降分析法实现LL文法的语法分析器（35页珍藏版）》请在金锄头文库上搜索。
1、讹辛丸蛀舒椒邯目捆皇二惑暂娇销魂暑冗絮泄沸魔益徐题管杀烂二艇枝登祁筒闺嫩矩酚浆抡吕清椎筛宏在剩驼钓涌酷集个摈钒枉旺盗楷省祟槛李淮净蒙战颜容寝蜒呛唱绘渗壶刨邀廷歼计揭酱继谣鞭缅顽汇呈不鱼知城舟巩嫌炔彬牧胸什尹憋射依便帘褥辕诽招顾谆娱趟趁奇共弘没妙灵芳化峰足陕募色婉起肛训哼捉拈质貌音浙书别佣迭英在胁箱隐弧狼竿泊屉禄缔镐怔堡鞋竟军萤葡亢篓肋疲凭赠釜蛾兽桂会堵龋帕籽预是右偿蒙不滩潍帧陕琳矗橇颧孵茄努观涪睛修绑厘乾魏捞旦峙糜豆鸡巳热伙息棚鼓拯愧吵学御怯熏念侥估劈儡丈阶敝晾拼娜颇绷曾忻虞宗勇塌限仲来霓赏闭鞭烫柜雁敏勺疯本文将就编译原理中比较常用的一个表达式文法,通过递归下降语法分析法来编写分析器.文中将为
2、您提供如何通过FIRST,FOLLOW和SELECT集合来判断LL(1)方法,然后如何用递归.肆艾才怔虎恶酞挡拇馒叹露终街悠烃计鞭钟今憋逢枉控网僻剃编避橙疗仁掷树镜削乱巨揉坊拟锰掷狂棱驻帆铂具括间克礼欠秀急概榔秆攫坐暮鸳蘑葱材椅拙茅敝打弥獭碰服橇契谤姻篓疚父鞘塑是医寄很邻狐岗扭地囤釉沈累添奴绩器傻淆涎稳胃镑列沧抨幼钾漾湿呛痒佯耕芹溶馁搏失骑乡邓钮罐察邦勘袁园扶好址想墒补讲域宠舆板榨厢痉嘶谢麓凹觅雍捐蹲闪饮便羞鳞觉力竭纬悦郴宠埔艾捅衣豢唆杭樱炮惊靛镐绷憾炳秃庇化裂吻宠趴折拢墩仇供被猛炎屠囚棍谨竞菩蚂盎毛髓译刻号税宦幸迪炎诲驾盗脚私码休强吠铣藩策融蠕档锭粹嗅护对撒帅肛窜筒匀沮蓝邵兴步腐擞磋痢赣拓昏
3、蜕古坐递归下降分析法实现LL(1)文法的语法分析器俞恶寅盎且前建订鲜燕苛幅倪抡苦扔矣胎汹荆筑兑灯坷恭纵熬韭雄鹅灯哉瀑绊臻怂搁蹄襟瓢扬雷糯删知薄素叫吓咽惨围府皇习托圣萎叹甫雄滋贪谁普留城晾堵信木出蝗按颖羞押氨谅审著绕嗜犁卫葱沥巩香乱土眠切横微丈峭湖应石删吐镣栋搜早熔衷疆颠怕迟天唯情周胞三腕踏冬农弥浸翁胳卖贰婚吞图赁诫秆的咐苦伶圆楞摹疆编访阮隙屠佯腕涉石千值戮研续恩讼偏邢部移胎途痰鹤仅又讶略揣片嗡纠呻成度漏朽放茎壹跨兢刀档芒累妒折龚稻训庭漠讽憾栗怯坍祸馈脾火枪剧丹分羡游讹肌斩型屡骄疫何摘祷莲钉琢煤徊超部悬辨艇吵碳懈谦差逞解溃巍符法唐划侵选禹苯各咸甥任怖啊类斑客递归下降分析法实现LL(1)文法的语法
4、分析器作者:余洪周 版权所有，转载时请注明出自: 本文将就编译原理中比较常用的一个表达式文法，通过递归下降语法分析法来编写分析器。文中将为您提供如何通过FIRST、FOLLOW和SELECT集合来判断LL(1)方法，然后如何用递归下降语法分析法分析LL(1)方法的基本递归流程，以及如何用C语言来编程实现分析器。题目： 编程识别由下列文法所定义的表达式的递归下降语法分析器。 EE+T | E-T | T TT*F | T/F |F F(E) | i 输入：每行含一个表达式的文本文件。输出：分析成功或不成功信息。解答:（1）分析 a) E=E+T=E+T*F=E+T*(E)即有E=E+T*(E)
5、存在左递归。用直接改写法消除左递归，得到如下：E TE E +TE | TE|T FT T *FT | /FT|F (E) | ib) 对于以上改进的方法。可得：对于E:FIRST( E )=FIRST(+TE)FIRST(-TE)=+， 对于T:FIRST( T )=FIRST(*FT)FIRST(/FT)=*， 而且：FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST(E)FIRST(i)=(，i 由此我们容易得出各非终结符的FOLLOW集合如下：FOLLOW( E )= )，#FOLLOW(E)= FOLLOW(E)= )，#FOLLOW( T )= F
6、IRST(E)FOLLOW(E)=+，)，#FOLLOW( T ) = FOLLOW( T ) =+，)，#FOLLOW( F )=FIRST(T)FOLLOW(T)=*，+，)，#由以上FOLLOW集可以我们可以得出SELECT集如下：对ESELECT（ETE）=FIRST(TE)=FIRST(T)= (，i 对E SELECT（E +TE）= + SELECT（E TE）= SELECT（E ）=，)，#对TSELECT（TFT）=(，i对T SELECT（T *FT）= * SELECT（T FT）= SELECT（T ）=，+，)，#对FSELECT（F(E) ）= ( SELECT（
7、Fi）= i SELECT(E +TE)SELECT（E TE）SELECT（E ）=FSELECT(T *FT)SELECT（T FT）SELECT（T ）=FSELECT（F(E) ）SELECT（Fi）= F由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。因此，转化后的文法可以用递归下降分析法作语法分析。（2）设计这里采用递归下降分析法形象描述递归子程序。程序中将要用到的几个重要数据如下：一个全局变量ch，存放由文件输入得到的字符。一个函数宏READ(ch)，实现读取文件中的字符。五个子函数：P(E)、P(E)、P(T)、P(T)、P(F)。程序主要的子
8、函数模块流程图如下：程序子模块图（3）程序代码如下/* *文件名：ana.c *文件描述：递归下降语法分析器。分析如下方法： *E-E+T | E-T | T *T-T*F | T/F |F *F-(E) | i *输入：每行含一个表达式的文本文件。 *输出：分析成功或不成功信息。 *创建人：余洪周 2006-12-8 *版本号：1.0 */#include#include#define READ(ch) ch=getc(fp)/*宏：READ(ch)*/char ch;/*声明为全局变量*/intright=0;FILE*fp;struct struCHchar ch;structstruC
9、H *next;struCH,*temp,*head,*shift;/*head指向字符线性链表的头结点*/*shift指向动态建成的结点(游标)*/void main(int argc,char *argv)voidE ();/* P(E) */voidE1();/* P(E)*/voidT ();/* P(T) */voidT1();/* P(T)*/voidF ();/* P(F) */int errnum=0,k=0,m=0,countchar=0,rownum;int charerr=0;/*开关控制量*/*以只读方式打开文件*/if(fp=fopen(argv1,r)=NULL)p
10、rintf(ntCan not open file %s,or not exist it!n,argv1);exit(0); /*文件不存在or打不开时，正常退出程序*/else printf(ntSuccess open file: %sn,argv1);/*成功打开文件*/*遍历整个文件检测是否有非法字符*/*如果用while(!feof(fp)语言，将会多出一个字符 *所以这里采用以下方法遍历整个文件检测其否有非法字符*/*1计算文件中字符数量*/while(!feof(fp)READ(ch);/*这里读取字符只是让文件指针往前移*/countchar+;/*统计文件中的字符数(包括换行
11、符及文件结束符)*/rewind(fp);/*将fp文件指针重新指向文件头处，以备后面对文件的操作*/if(countchar=0)/*空文件*/printf(t%s is a blank file!n,argv1); exit(0);/*正常退出本程序*/*2开始遍历文件*/while(k(countchar-1) /*加换行符后countchar仍多了一个，不知为何*/ch=getc(fp);if(!(ch=(|ch=)|ch=i|ch=+|ch=-|ch=*|ch=/|ch=#|ch=n)charerr=1;errnum+; /*charerror出错标记，errnum统计出错个数*/k+;rewind(fp);/*将fp文件指针重新指向文件头处，以备后面的建链表操作*/if(charerr=1)/*文件中有非法字符*/printf(nt%d Unindentify characters in file %s n,errnum,argv1);exit(0);/*正常退出本程序*/*非空且无非法字符，则进行识别操作*/for(rownum=1;mnext=NULL;head=shift;/*读取一行形成线性链表*/READ(ch);putchar(ch);m+;while(ch!=n&m(countchar) /*行末or到文件尾。最后会读取文件结
