递归下降分析法实现LL文法的语法分析器.doc

讹辛丸蛀舒椒邯目捆皇二惑暂娇销魂暑冗絮泄沸魔益徐题管杀烂二艇枝登祁筒闺嫩矩酚浆抡吕清椎筛宏在剩驼钓涌酷集个摈钒枉旺盗楷省祟槛李淮净蒙战颜容寝蜒呛唱绘渗壶刨邀廷歼计揭酱继谣鞭缅顽汇呈不鱼知城舟巩嫌炔彬牧胸什尹憋射依便帘褥辕诽招顾谆娱趟趁奇共弘没妙灵芳化峰足陕募色婉起肛训哼捉拈质貌音浙书别佣迭英在胁箱隐弧狼竿泊屉禄缔镐怔堡鞋竟军萤葡亢篓肋疲凭赠釜蛾兽桂会堵龋帕籽预是右偿蒙不滩潍帧陕琳矗橇颧孵茄努观涪睛修绑厘乾魏捞旦峙糜豆鸡巳热伙息棚鼓拯愧吵学御怯熏念侥估劈儡丈阶敝晾拼娜颇绷曾忻虞宗勇塌限仲来霓赏闭鞭烫柜雁敏勺疯本文将就编译原理中比较常用的一个表达式文法,通过递归下降语法分析法来编写分析器.文中将为您提供如何通过FIRST,FOLLOW和SELECT集合来判断LL(1)方法,然后如何用递归.肆艾才怔虎恶酞挡拇馒叹露终街悠烃计鞭钟今憋逢枉控网僻剃编避橙疗仁掷树镜削乱巨揉坊拟锰掷狂棱驻帆铂具括间克礼欠秀急概榔秆攫坐暮鸳蘑葱材椅拙茅敝打弥獭碰服橇契谤姻篓疚父鞘塑是医寄很邻狐岗扭地囤釉沈累添奴绩器傻淆涎稳胃镑列沧抨幼钾漾湿呛痒佯耕芹溶馁搏失骑乡邓钮罐察邦勘袁园扶好址想墒补讲域宠舆板榨厢痉嘶谢麓凹觅雍捐蹲闪饮便羞鳞觉力竭纬悦郴宠埔艾捅衣豢唆杭樱炮惊靛镐绷憾炳秃庇化裂吻宠趴折拢墩仇供被猛炎屠囚棍谨竞菩蚂盎毛髓译刻号税宦幸迪炎诲驾盗脚私码休强吠铣藩策融蠕档锭粹嗅护对撒帅肛窜筒匀沮蓝邵兴步腐擞磋痢赣拓昏蜕古坐递归下降分析法实现LL(1)文法的语法分析器俞恶寅盎且前建订鲜燕苛幅倪抡苦扔矣胎汹荆筑兑灯坷恭纵熬韭雄鹅灯哉瀑绊臻怂搁蹄襟瓢扬雷糯删知薄素叫吓咽惨围府皇习托圣萎叹甫雄滋贪谁普留城晾堵信木出蝗按颖羞押氨谅审著绕嗜犁卫葱沥巩香乱土眠切横微丈峭湖应石删吐镣栋搜早熔衷疆颠怕迟天唯情周胞三腕踏冬农弥浸翁胳卖贰婚吞图赁诫秆的咐苦伶圆楞摹疆编访阮隙屠佯腕涉石千值戮研续恩讼偏邢部移胎途痰鹤仅又讶略揣片嗡纠呻成度漏朽放茎壹跨兢刀档芒累妒折龚稻训庭漠讽憾栗怯坍祸馈脾火枪剧丹分羡游讹肌斩型屡骄疫何摘祷莲钉琢煤徊超部悬辨艇吵碳懈谦差逞解溃巍符法唐划侵选禹苯各咸甥任怖啊类斑客递归下降分析法实现LL(1)文法的语法分析器作者:余洪周 版权所有，转载时请注明出自: 本文将就编译原理中比较常用的一个表达式文法，通过递归下降语法分析法来编写分析器。文中将为您提供如何通过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)存在左递归。用直接改写法消除左递归，得到如下：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 )= FIRST(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（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)。程序主要的子函数模块流程图如下：程序子模块图（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;structstruCH *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)printf(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+;/*统计文件中的字符数(包括换行符及文件结束符)*/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&mch=ch;temp-next=NULL;shift-next=temp;shift=shift-next;READ(ch);if(m!=(countchar-1) putchar(ch);/*不输出最后一次读取的文件结束符*/m+;head=head-next;/*消去第一个空头结点,并使head指向非空线性链表头*/shift=head; /*shift指向头结点，以便后面识别操作*/putchar(n);E(); /*开始识别一行*/if(shift-ch=#&right)/*正确提示:文件名 Line 行号:right expression!*/printf(%s Line %d:t right expression!n,argv1,rownum);else /*错误提示:文件名 Line 行号:error expression!*/printf(%s Line %d:t error expression!n,argv1,rownum);putchar(n);/*end for*/printf(Completed!n);fclose(fp);/*关闭文件*/exit(0);/*正常结束程序*/*以下函数分别对应于子模块程序*/void E()T();E1();void E1()if(shift-ch=+|shift-ch=-)shift=shift-next;T();E1();elseif(shift-ch=#|shift-ch=)return;elseright=0;void T(void)F();T1();void T1(void)if(shift-ch=*|shift-ch=/)shift=shift-next;F();T1();elseif(shift-ch!=#&shift-ch!=)&shift-ch!=+&shift-ch!=-)right=0;/*如果不是#or)or+or+or-则出错*/voidF(void)if(shift-ch=i)shift=shift-next;elseif(shift-ch=()shift=shift-next;E();if(shift-ch=)shift=shift-next;elseright=0;elseright=0;（4）调试1.编译：在Windows平台下，用Turbo C 2编译连接生成后ana.exe；2.输入表达式：在ana.exe程序同一目录下新建一文本文件(如：test.txt)。往文本文件中输入要识别的表达式，表达式以“#”结束，可输入多行。同一行“#”以后的内容在识别过种中将自动丢弃。如将以下内容存入test.txt文件中：i-i#i#+i#(i+i)*i#+3.运行：打开Dos控制台，进入程序所在的目录(如C:)。输入：程序名 存放表达式的txt文件名，如:ana test.txt以上test.txt文本实例运行的结果如图：test.txt实例运行结果图异常结果注释：a) 文件不存在or打不开时，提示“Can not open file filename,or not exist it!”正常退出。b) 打开文件成功，提示：Success open file:filename c) 若为空文件，提示：filename is a blank file! 并正常退出程序。d) 先检测文件中是否含有非法字符，若有，则统计并输出其个数：errnum Unindentify characters in file filenamee) 程序将分析每行的表达式，输出每行执行的结果，如上图可知。结束语 文中代码部分也可以用其他语言实现，而思想基本上都是一样的，请读者自行实现。水平有限，时间仓促，有什么不足之处，敬请读者批评指正。参考资料关于题目的来源 * 编译原理实验二 递归下降语法分析 华南热带农业大学 计算机科学与技术系关于LL（1）分析方法* 何炎祥，编译原理，高等教育出版社，2004-8关于指针线性链表代码实现思想* 黄记瑶，编译实验(二)递归下降语法分析，2005-11-9/*参考书计算机编译原理编译程序构造实践LL(1)语法分析,例1:ERTWF#+*()i#文法GE:(按此格式输入)1 E - TR2 R - +TR3 R -4 T - FW5 W - * FW6 W -7 F - (E)8 F - i分析例句：i*(i)# , i+i#例2：编译书5.6例题1SHMA#adbe#S-aHH-aMdH-dM-AbM-A-aMA-e分析例句：aaabd#*/*-LL(1)语法分析-*/#include stdio.h#include stdlib.h#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50/*-main struct define-*/*声明：非终结符序号 = 100 + Vn的下标终结符序号 = Vn的下标*/*+文法结构+*/struct pRNode/*产生式右部结构*/int rCursor;/*右部序号*/struct pRNode *next;struct pNode/*产生式结点结构*/int lCursor;/*左部符号序号*/int rLength;/*右部长度*/*注当rLength = 1 时，rCursor = -1为空产生式*/struct pRNode *rHead;/*右部结点头指针*/;char VnMaxVnNum + 1;/*非终结符集*/int vnNum;char VtMaxVtNum + 1;/*终结符集*/int vtNum;struct pNode PMaxRuleNum;/*产生式*/int PNum;/*产生式实际个数*/char bufferMaxPLength + 1;char ch;/*符号或string ch;*/char stMaxStLength; /*要分析的符号串*/*+first and follow collect struct+*/struct collectNode/*集合元素结点结构*/int nVt;/*在终结符集中的下标*/struct collectNode *next;struct collectNode* firstMaxVnNum + 1;/*first集*/struct collectNode* followMaxVnNum + 1;/*follow集*/*+analysis table struct+*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#(-1)*/*+analysis stack struct+*/int analyseStackMaxStackDepth + 1;/*分析栈*/int topAnalyse;/*分析栈顶*/*int reverseStackMaxStackDepth + 1;/*颠倒顺序栈*/*int topReverse;/*倒叙栈顶*/*-function declare-*/void Init();/*初始化*/int IndexCh(char ch);/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/void InputVt();/*输入终结符*/void InputVn();/*输入非终结符*/void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/void InputP();/*产生式输入*/bool CheckP(char * st);/*判断产生式正确性*/void First(int U);/*计算first集,U-xx.*/void AddFirst(int U, int nCh);/*加入first集*/bool HaveEmpty(int nVn); /*判断first集中是否有空(-1)*/void Follow(int V);/*计算follow集*/void AddFollow(int V, int nCh, int kind);/*加入follow集，kind = 0表加入follow集，kind = 1加入first集*/void ShowCollect(struct collectNode *collect);/*输出first或follow集*/void FirstFollow();/*计算first和follow*/void CreateAT();/*构造预测分析表*/void ShowAT();/*输出分析表*/void Identify(char *st);/*主控程序,为操作方便*/*分析过程显示操作为本行变换所用，与教程的显示方式不同*/void InitStack();/*初始化栈及符号串*/void ShowStack();/*显示符号栈中内容*/void Pop();/*栈顶出栈*/void Push(int r);/*使用产生式入栈操作*/* LL1.CPP */*-*/#include LL1.h/*-main function-*/void main(void)char todo,ch;Init();InputVn();InputVt();InputP();getchar();FirstFollow();printf(所得first集为：);ShowCollect(first);printf(所得follow集为：);ShowCollect(follow);CreateAT();ShowAT();todo = y;while(y = todo)printf(n是否继续进行句型分析？(y / n):);todo = getchar();while(y != todo & n != todo)printf(n(y / n)? );todo = getchar();if(y = todo)int i;InitStack();printf(请输入符号串(以#结束) : );ch = getchar();i = 0;while(# != ch & i MaxStLength)if( != ch & n != ch)sti+ = ch;ch = getchar();if(# = ch & i MaxStLength)sti = ch;Identify(st);else printf(输入出错！n);getchar();/*-function definition-*/void Init()int i,j;vnNum = 0;vtNum = 0;PNum = 0;for(i = 0; i = MaxVnNum; i+)Vni = 0;for(i = 0; i = MaxVtNum; i+)Vti = 0;for(i = 0; i MaxRuleNum; i+)Pi.lCursor = NULL;Pi.rHead = NULL;Pi.rLength = 0;PNum = 0;for(i = 0; i = MaxPLength; i+)bufferi = 0;for(i = 0; i MaxVnNum; i+)firsti = NULL;followi = NULL;for(i = 0; i = MaxVnNum; i+)for(j = 0; j = MaxVnNum + 1; j+)analyseTableij = -1;/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/int IndexCh(char ch)int n;n = 0;/*is Vn?*/while(ch != Vnn & 0 != Vnn)n+;if(0 != Vnn)return 100 + n;n = 0;/*is Vt?*/while(ch != Vtn & 0 != Vtn)n+;if(0 != Vtn)return n;return -1;/*输出Vn或Vt的内容*/void ShowChArray(char* collect)int k = 0;while(0 != collectk)printf( %c , collectk+);printf(n);/*输入非终结符*/void InputVn()int inErr = 1;int n,k;char ch;while(inErr)printf(n请输入所有的非终结符，注意：);printf(请将开始符放在第一位，并以#号结束:n);ch = ;n = 0;/*初始化数组*/while(n MaxVnNum)Vnn+ = 0;n = 0;while(# != ch) & (n MaxVnNum)if( != ch & n != ch & -1 = IndexCh(ch)Vnn+ = ch;vnNum+;ch = getchar();Vnn = #;/*以“#”标志结束用于判断长度是否合法*/k = n;/*k用于记录n以便改Vnn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar();printf(n符号数目超过限制！n);inErr = 1;continue;/*正确性确认，正确则，执行下下面，否则重新输入*/Vnk = 0;ShowChArray(Vn);ch = ;while(y != ch & n != ch)if(n != ch)printf(输入正确确认?(y/n):);scanf(%c, &ch);if(n = ch)printf(录入错误重新输入！n);inErr = 1;elseinErr = 0;/*输入终结符*/void InputVt()int inErr = 1;int n,k;char ch;while(inErr)printf(n请输入所有的终结符，注意：);printf(以#号结束:n);ch = ;n = 0;/*初始化数组*/while(n MaxVtNum)Vtn+ = 0;n = 0;while(# != ch) & (n MaxVtNum)if( != ch & n != ch & -1 = IndexCh(ch)Vtn+ = ch;vtNum+;ch = getchar();Vtn = #;/*以“#”标志结束*/k = n;/*k用于记录n以便改Vtn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar();printf(n符号数目超过限制！n);inErr = 1;continue;/*正确性确认，正确则，执行下下面，否则重新输入*/Vtk = 0;ShowChArray(Vt);ch = ;while(y != ch & n != ch)if(n != ch)printf(输入正确确认?(y/n):);scanf(%c, &ch);if(n = ch)printf(录入错误重新输入！n);inErr = 1;elseinErr = 0;/*产生式输入*/void InputP()char ch;int i = 0, n,num;printf(请输入文法产生式的个数：);scanf(%d, &num);PNum = num;getchar();/*消除回车符*/printf(n请输入文法的%d个产生式,并以回车分隔每个产生式：, num);printf(n);while(i num)printf(第%d个：, i);/*初始化*/for(n =0; n MaxPLength; n+)buffern = 0;/*输入产生式串*/ch = ;n = 0;while(n != (ch = getchar() & n rCursor = IndexCh(buffer3);pt-next = NULL;Pi.rHead = pt;n = 4;while(0 != buffern)qt = (pRNode*)malloc(sizeof(pRNode);qt-rCursor = IndexCh(buffern);qt-next = NULL;pt-next = qt;pt = qt;n+;Pi.rLength = n - 3;i+;/*调试时使用*/elseprintf(输入符号含非法在成分，请重新输入！n);/*判断产生式正确性*/bool CheckP(char * st)int n;if(100 IndexCh(st0)return false;if(- != st1)return false;if( != st2)return false;for(n = 3; 0 != stn; n +)if(-1 = IndexCh(stn)return false;return true;/*=first & follow=*/*计算first集,U-xx.*/void First(int U)int i,j;for(i = 0; i PNum; i+)if(Pi.lCursor = U)struct pRNode* pt;pt = Pi.rHead;j = 0;while(j pt-rCursor)/*注:此处因编程出错,使空产生式时rlength同样是1,故此处同样可处理空产生式*/AddFirst(U, pt-rCursor);break;elseif(NULL = firstpt-rCursor - 100)First(pt-rCursor);AddFirst(U, pt-rCursor);if(!HaveEmpty(pt-rCursor)break;elsept = pt-next;j+;if(j = Pi.rLength)/*当产生式右部都能推出空时*/AddFirst(U, -1);/*加入first集*/void AddFirst(int U, int nCh)/*当数值小于100时nCh为Vt*/*当处理非终结符时,AddFirst不添加空项(-1)*/struct collectNode *pt, *qt;int ch;/*用于处理Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh)break;elseqt = pt;pt = pt-next;if(NULL = pt)pt = (struct collectNode *)malloc(sizeof(struct collectNode);pt-nVt = nCh;pt-next = NULL;if(NULL = firstU - 100)firstU - 100 = pt;elseqt-next = pt;/*qt指向first集的最后一个元素*/pt = pt-next;elsept = firstnCh - 100;while(NULL != pt)ch = pt-nVt;if(-1 != ch)AddFirst(U, ch);pt = pt-next;/*判断first集中是否有空(-1)*/bool HaveEmpty(int nVn)if(nVn nVt)return true;pt = pt-next;return false;/*计算follow集,例：U-xVy,U-xV.(注：初始符必含#-1)*/void Follow(int V)int i;struct pRNode *pt;if(100 = V)/*当为初始符时*/AddFollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能处理：U-xVyVz的情况*/pt = pt-next;if(NULL != pt)pt = pt-next;/*V右侧的符号*/if(NULL = pt)/*当V后为空时V-xV，将左符的follow集并入V的follow集中*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);else/*不为空时V-xVy,(注意：y-)，调用AddFollow加入Vt或y的first集*/whil