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

1、课程设计说明书 课程名称:编译原理课程设计 题 目: LR(1)分析法 院 系： 专业班级： 学 号： 学生姓名： 指导教师： 2012年 6 月 22 日安徽理工大学课程设计（论文）任务书 院系 教研室学 号 学生姓名 专业（班级）信计09-1 设计题目 LR（1）分析法设计技术参数 Windows xp操作系统 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 编写代码 2

2、012.6.19-2012.6.20 调试运行参考 资料1 张素琴.吕映芝等.编译原理M.清华大学出版.2004年2王宏.李玉东.李罡.Visual C+实战演练M.人民邮电出版.2003年3月3胡元义等.编译原理实践教程M.西安电子科技大学出版社.2005年7月4 胡伦骏.编译原理.M.电子工业出版社，20025 高仲仪.编译原理及编译程序构造>.M.北京航空航天大学出版社.1990 指导教师签字 教研室主任签字 2012年6 月22 日 学生姓名： 学号： 专业班级： 课程设计题目： LR(1)分析法 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩LR

3、(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、#)，如：a

4、bb#。输出过程如下：步骤 状态栈 符号栈 输入串ACTIONGOTO10#abb#S3. 图1-1二、设备与环境 2.1硬件设备 内存容量 2 GB 硬盘容量 320 GB 硬盘描述 7200转，SATA 流处理器个数 32 2.2软件环境 操作系统： WINDOWS XP 开发平台： C语言 开发软件: VC+ 6.03、 系统分析 3.1 LR(1)分析法定义LR分析法是一种有效的自底向上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右扫描输入单词串，R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号中的k

5、是指在决定当前分析动作时向前看的符号个数。 3.2 LR(1)分析方法的主要思想(1)严格地进行最左归约（识别句柄并归约它）。(2)将识别句柄的过程划分为由若干状态控制，每个状态控制识别出句柄的一个符号。(3)分析栈：存放已识别的文法符号和状态,描述的是分析过程中的历史和展望信息;(4)由一个总控程序来控制整个识别过程。 3.3 LR(1)分析器的工作过程(1) 将初始状态S0和输入串的左边界(#) 分别进分析栈；(2) 根据状态栈栈顶和当前输入符号查动作表进行如下工作;移进:若动作表中对应“移进”，那么当前输入符号进符号栈，并据状态转换表查得输入符号所对应的新的状态进状态栈，继续扫描，即下一

6、个输入符号变成当前得输入符号；归约:若动作表中对应“归约”，则按指定产生式进行归约，若产生式右部的符号串长度为n，则符号栈栈顶的n个符号为句柄，所以符号栈栈顶n个符号出栈，同时，状态栈顶的n个元素也出栈，归约后的文法符号(非终结符)进符号栈，并据状态转换表查归约后的文法符号所对应的新状态进状态栈；接受:若动作表中对应“acc”，则分析成功；出错:若动作表中对应空白，则报告错误信息。(3) 重复以上(2)的工作直到接受或出错为止。 3.4 LR(1)的优点 (1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。(2)LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和

7、其他移进-归约方法一样有效地实现。(3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。(4)LR分析器能及时察觉语法错误,快到自左向右扫描输入的最大可能。为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。 3.5 LR分析器的组成(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是

8、相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。 3.6 LR分析器结构图输入串a1a2aiai+1an#Sm。S1S0Xn。X1#输出总控程序Sp 分析表ACTION表GOTO 表 图3-1 图3-1(1)在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作；(2) 分析表是LR分析器的核心，它跟文

9、法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作；(3) 分析栈包括文法符号栈Xi和相应的状态栈Si两部分(状态是指能识别活前缀的自动机状态)，LR分析器通过判断栈顶元素和输入符号查分析表确定下步分析动作。3.7 举例构造下面文法的LR(1)分析表(0)S'® S(1)S® aAd(2)S® bAc(3)S® aec(4)S® bed(5) A® e解：S0: S'®.S, # S®.aAd, # S®.bAc, # S®.aec,

10、 # S®.bed, #S1: S'®S., #SaS2:S®a.Ad, # S®a.ec, #A®.e,dS4: S®aA.d, #S5: S®ae.c, #A®e.,dAeS8:S®aAd.,#dS9:S®aec., #cS3: S®b.Ac, # S®b.ed, #A®.e,cbAS6: S®bA.c, #S10: S®bAc., #cS7:S®be.d, #A®e.,ceS11;S®bed., #d1

11、. 求项目集合 图3-22. 根据项目集合得到分析表如下表3-1状态 ACTION GOTOabcde#SA0S2S311acc2S543S764S85S9r56S107r5S118r19r310r211r44、 测试运行4.1 程序运行截图4.1.1 输入字符串ABSD# 图4-1 4.1.2输入字符串abbb# 图4-2 4.1.3输入字符串ababababab# 图4-3 4.1.4 输入i+i*i()i# 图4-45、 总结 经过这个实验的练习，通过对程序的分析，让我进一步了解LR（1）算法的思想以及它的进一步程序实现，让我对它的了解从简单的理论上升到程序实现的级别，有理论上升到实际，

12、让我更清楚它的用途。 在对实验的分析的时候，也遇到很多的问题，刚开始根本想不到用程序怎么实现这么繁杂的LR（1）文法，后来看了程序才知道，才转过来弯，通过对这个程序的分析与揣摩，让自己对这方面文法的实现有了一定的头绪，对以后的的一些文法的程序实现会有很大的帮助，通过练习我也感到理论仅留在理论是远远不行的，用通过一定方式实现才有实用价值。 通过本次课程设计，我加深了对预测分析LR（1）分析法的理解，同时体验到了编译原理中一些算法的巧妙。由于LR（1）分析法程序是一个相当复杂的程序，它需要利用到大量的编译原理，编程技巧和数据结构。由于先前掌握的知识不够牢固深刻使之在实验过程中出现了大量的问题。由于

13、课前的充分准备，加上同学和老师的帮助，最后顺利完成了实验。 编译原理的在整个计算机体系课程中有着重要的地位，我现在才刚刚入门，所以，我会在以后的课程和实验中继续努力，学好编译原理课程，为以后的学习打下基础。参考文献1 张素琴.吕映芝等.编译原理M.清华大学出版.2004年2王宏.李玉东.李罡.Visual C+实战演练M.人民邮电出版.2003年3月3胡元义等.编译原理实践教程M.西安电子科技大学出版社.2005年7月4 胡伦骏.编译原理.M.电子工业出版社，20025 高仲仪.编译原理及编译程序构造>.M.北京航空航天大学出版社.1990源代码#include<stdio.h&g

14、t;#include<string.h>char *action103="S3#","S4#",NULL, /*ACTION表*/ NULL,NULL,"acc", "S6#","S7#",NULL, "S3#","S4#",NULL, "r3#","r3#",NULL, NULL,NULL,"r1#", "S6#","S7#",NULL, NU

15、LL,NULL,"r3#", "r2#","r2#",NULL, NULL,NULL,"r2#"int goto1102=1,2, /*QOTO表*/ 0,0, 0,5, 0,8, 0,0, 0,0, 0,9, 0,0, 0,0, 0,0;char vt3='a','b','#' /*存放非终结符*/char vn2='S','B' /*存放终结符*/char *LR4="E->S#","S->

16、BB#","B->aB#","B->b#"/*存放产生式*/int a10;char b10,c10,c1;int top1,top2,top3,top,m,n;void main()int g,h,i,j,k,l,p,y,z,count;char x,copy10,copy110;top1=0;top2=0;top3=0;top=0;a0=0;y=a0;b0='#'count=0;z=0;printf("-编译原理课程设计-n");printf("-许涛-n");printf

17、("-2009303506-n");printf("-请输入表达式-n");doscanf("%c",&c1);ctop3=c1;top3=top3+1;while(c1!='#');printf("步骤t状态栈tt符号栈tt输入串ttACTIONtGOTOn");doy=z;m=0;n=0; /*y,z指向状态栈栈顶*/g=top;j=0;k=0;x=ctop;count+;printf("%dt",count);while(m<=top1) /*输出状态栈*/p

18、rintf("%d",am); m=m+1;printf("tt");while(n<=top2) /*输出符号栈*/printf("%c",bn); n=n+1;printf("tt");while(g<=top3) /*输出输入串*/printf("%c",cg); g=g+1;printf("tt");while(x!=vtj&&j<=2) j+;if(j=2&&x!=vtj) printf("errorn"); return; if(actionyj=