编译原理课程设计LR(1)分析法

课程设计说明书课程名称:＿编译原理课程设计＿题目:LR(1)分析法院系：＿专业班级：学号：＿＿学生姓名：＿＿＿指导教师：＿＿＿2012年6月22日2安徽理工大学课程设计（论文）任务书院系教研室学号学生姓名专业（班级）信计09-1设计题目LR（1）分析法设计技术参数Windowsxp操作系统VC++6.0设计要求1．掌握LR(1)分析法的基本原理2．掌握LR(1)分析表的构造方法3．掌握LR(1)驱动程序的构造方法工作量3kb的程序代码13页的课程设计说明书工作计划2012.6.14---2012.6.16需求分析2012.6.16---2112.6.18编写代码2012.6.19---2012.6.20调试运行参考资料[1]张素琴.吕映芝等.《编译原理》[M.]清华大学出版.2004年[2]王宏.李玉东.李罡.《VisualC++实战演练》[M.]人民邮电出版.2003年3月[3]胡元义等.《编译原理实践教程》[M.]西安电子科技大学出版社.2005年7月[4]胡伦骏.《编译原理》.[M.]电子工业出版社，2002[5]高仲仪.《编译原理及编译程序构造.[M.]北京航空航天大学出版社.1990指导教师签字教研室主任签字2012年6月22日3安徽理工大学课程设计（论文）成绩学生姓名：学号：专业班级：课程设计题目：LR(1)分析法指导教师评语：成绩：指导教师：年月日4LR(1)分析法一、系统简介及需求分析1.1设计目的及要求（1）掌握LR(1)分析法的基本原理；（2）掌握LR(1)分析表的构造方法；（3）掌握LR(1)驱动程序的构造方法。（4）构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子.1.2实验内容根据某一文法编制调试LR(1)分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对LR(1)分析法的理解。对下列文法，用LR(1)分析法对任意输入的符号串进行分析：（0）E-S（1）S-BB（2）B-aB（3）B-b程序输入一以#结束的符号串(包括a、b、#)，如：abb#。输出过程如下：步骤状态栈符号栈输入串ACTIONGOTO10#abb#S3..................图1-1二、设备与环境2.1硬件设备内存容量2GB硬盘容量320GB硬盘描述7200转，SATA流处理器个数3252.2软件环境操作系统：WINDOWSXP开发平台：C语言开发软件:VC++6.0三、系统分析3.1LR(1)分析法定义LR分析法是一种有效的自底向上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右扫描输入单词串，R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号中的k是指在决定当前分析动作时向前看的符号个数。3.2LR(1)分析方法的主要思想(1)严格地进行最左归约（识别句柄并归约它）。(2)将识别句柄的过程划分为由若干状态控制，每个状态控制识别出句柄的一个符号。(3)分析栈：存放已识别的文法符号和状态,描述的是分析过程中的历史和展望信息;(4)由一个总控程序来控制整个识别过程。3.3LR(1)分析器的工作过程(1)将初始状态S0和输入串的左边界(#)分别进分析栈；(2)根据状态栈栈顶和当前输入符号查动作表进行如下工作;移进:若动作表中对应“移进”，那么当前输入符号进符号栈，并据状态转换表查得输入符号所对应的新的状态进状态栈，继续扫描，即下一个输入符号变成当前得输入符号；归约:若动作表中对应“归约”，则按指定产生式进行归约，若产生式右部的符号串长度为n，则符号栈栈顶的n个符号为句柄，所以符号栈栈顶n个符号出栈，同时，状态栈顶的n个元素也出栈，归约后的文法符号(非终结符)进符号栈，并据状态转换表查归约后的文法符号所对应的新状态进状态栈；接受:若动作表中对应“acc”，则分析成功；出错:若动作表中对应空白，则报告错误信息。(3)重复以上(2)的工作直到接受或出错为止。3.4LR(1)的优点(1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的6结构。(2)LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进-归约方法一样有效地实现。(3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。(4)LR分析器能及时察觉语法错误,快到自左向右扫描输入的最大可能。为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。3.5LR分析器的组成(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。3.6LR分析器结构图Sp图3-1图3-1分析表输入串a1a2…aiai+1…an#总控程序ACTION表GOTO表输出Xn。。。X1##Sm。。。S1S07(1)在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作；(2)分析表是LR分析器的核心，它跟文法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作；(3)分析栈包括文法符号栈X[i]和相应的状态栈S[i]两部分(状态是指能识别活前缀的自动机状态)，LR分析器通过判断栈顶元素和输入符号查分析表确定下步分析动作。3.7举例构造下面文法的LR(1)分析表(0)S'S(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)Ae解：1.求项目集合图3-2SaS4:AedcbAS10:ceS11;d82.根据项目集合得到分析表如下表3-1状态ACTIONGOTOabcde#SA0S2S311acc2S543S764S85S9r56S107r5S118r19r310r211r4四、测试运行4.1程序运行截图4.1.1输入字符串ABSD#图4-194.1.2输入字符串abbb#图4-24.1.3输入字符串ababababab#图4-34.1.4输入i+i*i()i#图4-410五、总结经过这个实验的练习，通过对程序的分析，让我进一步了解LR（1）算法的思想以及它的进一步程序实现，让我对它的了解从简单的理论上升到程序实现的级别，有理论上升到实际，让我更清楚它的用途。在对实验的分析的时候，也遇到很多的问题，刚开始根本想不到用程序怎么实现这么繁杂的LR（1）文法，后来看了程序才知道，才转过来弯，通过对这个程序的分析与揣摩，让自己对这方面文法的实现有了一定的头绪，对以后的的一些文法的程序实现会有很大的帮助，通过练习我也感到理论仅留在理论是远远不行的，用通过一定方式实现才有实用价值。通过本次课程设计，我加深了对预测分析LR（1）分析法的理解，同时体验到了编译原理中一些算法的巧妙。由于LR（1）分析法程序是一个相当复杂的程序，它需要利用到大量的编译原理，编程技巧和数据结构。由于先前掌握的知识不够牢固深刻使之在实验过程中出现了大量的问题。由于课前的充分准备，加上同学和老师的帮助，最后顺利完成了实验。编译原理的在整个计算机体系课程中有着重要的地位，我现在才刚刚入门，所以，我会在以后的课程和实验中继续努力，学好编译原理课程，为以后的学习打下基础。参考文献[1]张素琴.吕映芝等.《编译原理》[M.]清华大学出版.2004年[2]王宏.李玉东.李罡.《VisualC++实战演练》[M.]人民邮电出版.2003年3月[3]胡元义等.《编译原理实践教程》[M.]西安电子科技大学出版社.2005年7月[4]胡伦骏.《编译原理》.[M.]电子工业出版社，2002[5]高仲仪.《编译原理及编译程序构造.[M.]北京航空航天大学出版社.199011源代码#includestdio.h#includestring.hchar*action[10][3]={S3#,S4#,NULL,/*ACTION表*/NULL,NULL,acc,S6#,S7#,NULL,S3#,S4#,NULL,r3#,r3#,NULL,NULL,NULL,r1#,S6#,S7#,NULL,NULL,NULL,r3#,r2#,r2#,NULL,NULL,NULL,r2#};intgoto1[10][2]={1,2,/*QOTO表*/0,0,0,5,0,8,0,0,0,0,0,9,0,0,0,0,0,0};charvt[3]={'a','b','#'};/*存放非终结符*/charvn[2]={'S','B'};/*存放终结符*/char*LR[4]={E-S#,S-BB#,B-aB#,B-b#};/*存放产生式*/inta[10];charb[10],c[10],c1;inttop1,top2,top3,top,m,n;voidmain(){12intg,h,i,j,k,l,p,y,z,count;charx,copy[10],copy1[10];top1=0;top2=0;top3=0;top=0;a[0]=0;y=a[0];b[0]='#';count=0;z=0;printf(--------------编译原理课程设计--------------\n);printf(-------------------许涛-------------------\n);printf(----------------2009303506----------------\n);printf(----------------请输入表达式--------------\n);do{scanf(%c,&c1);c[top3]=c1;top3=top3+1;}while(c1!='#');printf(步骤\t状态栈\t\t符号栈\t\t输入串\t\tACTION\tGOTO\n);do{y=z;m=0;n=0;/*y,z指向状态栈栈顶*/g=top;j=0;k=0;x=c[top];count++;printf(%d\t,count);while(m=top1){/*输出状态栈*/printf(%d,a[m]);m=m+1;}printf(\t\t);while(n=top2){/*输出符号栈*/printf(%c,b[n]);n=n+1;}printf(\t\t);while(g=top3){/*输出输入串*/printf(%c,c[g]);g=g+1;13}printf(\t\t);while(x!=vt[j]&&j=2)j++;if(j==2&&x!=vt[j]){printf(error\n);return;}if(action[y][j]==NULL){printf(error\n);return;}elsestrcpy(copy,action[y][j]);if(copy[0]=='S'){/*处理移进*/z=copy[1]-'0';top1=top1+1;top2=top2+1;a[top1]=z;b[top2]=x;top=top+1;i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}printf(\n);}if(copy[0]=='r'){/*处理归约*/i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}h=copy[1]-'0';14strcpy(copy1,LR[h]);while(copy1