《编译原理课程设计LR分析法》由会员分享，可在线阅读，更多相关《编译原理课程设计LR分析法（15页珍藏版）》请在金锄头文库上搜索。
1、关麻蔑工大拳课程设计说明书课程名称:编译原理课程设计题 目：LR（ 1）分析法院 系：= 专业班级：学 号：=- 学生姓名：=_ 指导教师：=2012年6月22日安徽理工大学课程设计(论文)任务书一院系教研室学号学生姓名专业(班级)信计09-1设计题目LR(1)分析法设计技术参数Windows xp操作系统 VC+6.0设计要求1. 掌SLR(1)分析法的基本原理2. 掌SLR(1)分析表的构造方法3. 掌握LR(1)驱动程序的构造方法工作量3kb的程序代码13页的课程设计说明书工作计划2012.6.14-2012.6.16 需求分析2012.6.16-2112.6.18 编写代码2012.6
2、.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)分析法一、系统简介及需求分析1.1设计目的及要求(1) 掌握LR(1)分析法的基本原理；(2) 掌握LR(1)分析表的构造方法；(3) 掌握L
3、R(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硬件设备内存容量2 GB硬盘容量320 GB硬盘描述7200转，
4、SATA流处理器个数322.2软件环境操作系统： WINDOWS XP开发平台：C语言开发软件：VC+ 6.0三、系统分析3.1 LR(1)分析法定义LR分析法是一种有效的自底向上的语法分析技术，它能适用于大部分上下 文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左山。可向右扫描输 入单词串，R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号 中的k是指在决定当前分析动作时向前看的符号个数。3.2 LR(1)分析方法的主要思想(1) 严格地进行最左归约(识别句柄并归约它)。(2) 将识别句柄的过程划分为由若干状态控制，每个状态控制识别出句柄的 一个符号。(3) 分
5、析栈：存放已识别的文法符号和状态，描述的是分析过程中的历史和展 望信息；(4) 由一个总控程序来控制整个识别过程。3.3 LR(1)分析器的工作过程(1) 将初始状态S0和输入串的左边界(#)分别进分析栈；(2) 根据状态栈栈顶和当前输入符号查动作表进行如下工作；移进:若动作表中对应“移进”，那么当前输入符号进符号栈，并据状态转换 表查得输入符号所对应的新的状态进状态栈，继续扫描，即下一个输入符号变成 当前得输入符号；归约:若动作表中对应“归约”，则按指定产生式进行归约，若产生式右部的 符号串长度为n，则符号栈栈顶的n个符号为句柄，所以符号栈栈顶n个符号出 栈，同时，状态栈顶的n个元素也出栈，
6、归约后的文法符号(非终结符)进符号栈， 并据状态转换表查归约后的文法符号所对应的新状态进状态栈；接受:若动作表中对应“acc”，则分析成功；出错:若动作表中对应空白，则报告错误信息。(3) 重复以上(2)的工作直到接受或出错为止。3.4 LR(1)的优点(1) LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的 结构。(2) LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进 -归约方法一样有效地实现。(3) LR方法能分析的文法类是预测分析法能分析的文法类的真超集。(4) LR分析器能及时察觉语法错误，快到自左向右扫描输入的最大可能。为了使一个文法是LR的，只要
7、保证当句柄出现在栈顶时，自左向右扫描的移进 -归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要 扫描整个栈就可以知道这一点，因为，如果这个识别句柄的有限自动机自底向上 读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态， 所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。3.5 LR分析器的组成(1) 总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同 的。(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分 析器不同时，分析表将不同，分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们
8、都可用二维数组表示。(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。3.6 LR分析器结构图(1) 在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况， 查分析表确定分析动作；分析表是LR分析器的核心，它跟文法有关，它包括动作表(Action)和状态转 换表(Goto)两部分，总控程序据分析表确定分析动作；(3)分析栈包括文法符号栈Xi和相应的状态栈Si两部分(状态是指能识别活前 缀的自动机状态)，LR分析器通过判断栈顶元素和输入符号查分析表确定下步分 析动作。3.7举例构造下面文法的LR(1)分析表(0)S S
9、(1) S aAd(2) S bAc(3) S aec(4) S bed(5) A e解：图3-22.根据项目集合得到分析表如下表3-1状态ACTIONGOTOabcde#SA0S2S311acc2S543S764S85S9r56S107r5S118r19r310r211r4四、测试运行4.1程序运行截图4.1.1输入字符串ABSD#图4-14.1.2输入字符串abbb#X图4-24.1.3 输入字符串 ababababab#图4-34.1.4 输入 i+i*i()i#图4-4五、总结经过这个实验的练习，通过对程序的分析，让我进一步了解LR （1）算法的 思想以及它的进一步程序实现，让我对它的
10、了解从简单的理论上升到程序实现的 级别，有理论上升到实际，让我更清楚它的用途。在对实验的分析的时候，也遇到很多的问题，刚开始根本想不到用程序怎么实 现这么繁杂的LR（1）文法，后来看了程序才知道，才转过来弯，通过对这个程 序的分析与揣摩，让自己对这方面文法的实现有了一定的头绪，对以后的的一些 文法的程序实现会有很大的帮助，通过练习我也感到理论仅留在理论是远远不行 的，用通过一定方式实现才有实用价值。通过本次课程设计，我加深了对预测分析LR（1）分析法的理解，同时体验 到了编译原理中一些算法的巧妙。由于LR（1）分析法程序是一个相当复杂的程 序，它需要利用到大量的编译原理，编程技巧和数据结构。由
11、于先前掌握的知识 不够牢固深刻使之在实验过程中出现了大量的问题。由于课前的充分准备，加上 同学和老师的帮助，最后顺利完成了实验。编译原理的在整个计算机体系课程中有着重要的地位，我现在才刚刚入门， 所以，我会在以后的课程和实验中继续努力，学好编译原理课程，为以后的学习 打下基础。参考文献1张素琴.吕映芝等.编译原理M.清华大学出版.2004年2王宏.李玉东.李罡.Visual C+实战演练M.人民邮电出版.2003年3月3胡元义等.编译原理实践教程M.西安电子科技大学出版社.2005年7月4胡伦骏.编译原理.M.电子工业出版社，20025高仲仪.编译原理及编译程序构造.M.北京航空航天大学出版社
12、.1990源代码#include#include/*ACTION 表*/char *action103=S3#,S4#,NULL,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#”;int goto1102=1,2,/*。丁。表 */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;/* 存放终结
13、符 */ char *LR4=E-S#,S-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(2009303506n);printf(请输入表达式n);doscanf(%c,&c1);ctop3=c1;top3=top3+1;while(c1!=#);printf(步骤状态栈 tt 符号栈 输入串 ttACTIONtGOTOn);doy=z;m=0;n=0;
