编译原理LR(1)分析法课程设计.doc-资料库

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第1页.png

第1页 / 共13页

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第2页.png

第2页 / 共13页

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第3页.png

第3页 / 共13页

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第4页.png

第4页 / 共13页

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第5页.png

第5页 / 共13页

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第6页.png

第6页 / 共13页

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第7页.png

第7页 / 共13页

b5fcd32d-7c3e-482c-b83a-7dd505c09520.doc.pdf-第8页.png

第8页 / 共13页

课程设计说明书课程名称:＿编译原理课程设计＿题目: LR(1)分析法院系：专业班级：＿学号：＿＿＿＿＿学生姓名：＿＿＿指导教师：＿＿＿ 2012 年 6 月 22 日

安徽理工大学课程设计（论文）任务书院系学生姓名教研室专业（班级） 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 编写代码 2012.6.19---2012.6.20 调试运行 [1] 张素琴.吕映芝等.《编译原理》[M.]清华大学出版.2004 年 [2]王宏.李玉东.李罡.《Visual C++实战演练》[M.]人民邮电出版.2003 年 3 月 [3]胡元义等.《编译原理实践教程》[M.]西安电子科技大学出版社.2005 年 7 月 [4] 胡伦骏.《编译原理》.[M.]电子工业出版社，2002 [5] 高仲仪.《编译原理及编译程序构造>.[M.]北京航空航天大学出版社.1990 指导教师签字教研室主任签字 2012 年 6 月 22 日 2

安徽理工大学课程设计（论文）成绩学生姓名：学号：专业班级：课程设计题目： LR(1)分析法指导教师评语：成绩：指导教师：年月日 3

LR(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#。输出过程如下：步骤 1 状态栈 0 ... ... # ... 符号栈输入串 ACTION GOTO S3 ... ... abb# ... 图 1-1 二、设备与环境 2.1 硬件设备内存容量 2 GB 硬盘容量 320 GB 硬盘描述 7200 转，SATA 流处理器个数 32 4

2.2 软件环境操作系统： WINDOWS XP 开发平台： C 语言开发软件: 三、系统分析 VC++ 6.0 3.1 LR(1)分析法定义 LR 分析法是一种有效的自底向上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫 LR(k)分析方法，其中 L 是指自左(Left)向右扫描输入单词串，R 是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号中的 k 是指在决定当前分析动作时向前看的符号个数。 3.2 LR(1)分析方法的主要思想 (1)严格地进行最左归约（识别句柄并归约它）。 (2)将识别句柄的过程划分为由若干状态控制，每个状态控制识别出句柄的一个符号。 (3)分析栈：存放已识别的文法符号和状态,描述的是分析过程中的历史和展望信息; (4)由一个总控程序来控制整个识别过程。 3.3 LR(1)分析器的工作过程 (1) 将初始状态 S0 和输入串的左边界(#) 分别进分析栈； (2) 根据状态栈栈顶和当前输入符号查动作表进行如下工作; 移进:若动作表中对应“移进”，那么当前输入符号进符号栈，并据状态转换表查得输入符号所对应的新的状态进状态栈，继续扫描，即下一个输入符号变成当前得输入符号；归约:若动作表中对应“归约”，则按指定产生式进行归约，若产生式右部的符号串长度为 n，则符号栈栈顶的 n 个符号为句柄，所以符号栈栈顶 n 个符号出栈，同时，状态栈顶的 n 个元素也出栈，归约后的文法符号(非终结符)进符号栈，并据状态转换表查归约后的文法符号所对应的新状态进状态栈；接受:若动作表中对应“acc”，则分析成功；出错:若动作表中对应空白，则报告错误信息。 (3) 重复以上(2)的工作直到接受或出错为止。 3.4 LR(1)的优点 (1)LR 分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的 5

结构。 (2)LR 分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进 -归约方法一样有效地实现。 (3)LR 方法能分析的文法类是预测分析法能分析的文法类的真超集。 (4)LR 分析器能及时察觉语法错误,快到自左向右扫描输入的最大可能。为了使一个文法是 LR 的，只要保证当句柄出现在栈顶时，自左向右扫描的移进 -归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR 分析器必须要扫描整个栈就可以知道这一点，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR 分析器可以从栈顶的状态确定它需要从栈中了解的一切。 3.5 LR 分析器的组成 (1)总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。 (2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR 分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。 (3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。 3.6 LR 分析器结构图 S p Sm 。。。 S1 S0 Xn 。。。 X1 # 输入串 a1a2…aiai+1…an# 总控程序输出 ACTION 表图 3-1 GOTO 表分析表图 3-1 6

(1)在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作； (2) 分析表是 LR 分析器的核心，它跟文法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作； (3) 分析栈包括文法符号栈 X[i]和相应的状态栈 S[i]两部分(状态是指能识别活前缀的自动机状态)，LR 分析器通过判断栈顶元素和输入符号查分析表确定下步分析动作。 3.7 举例 S aAd bAc aec bed e 构造下面文法的 LR(1)分析表 (0)S' (1)S (2)S (3)S (4)S (5)A 解： 1.求项目集合 a S0: S' .S, # S .aAd, # S .bAc, # S .aec, # S .bed, # S S1: S' S., # b S3: S b.Ac, # S b.ed, # S2:S a.Ad, # S a.ec, # A .e,d A e A A .e,c e S4: S aA.d, # d S5: S ae.c, # A e.,d c S8:S aAd.,# S9:S aec., # S6: S bA.c, # c S10: S bAc., # S7:S be.d, # A e.,c d S11; S bed., # 图 3-2 7

GOTO A S 1 4 6 2.根据项目集合得到分析表如下表 3-1 ACTION c d e # a S2 b S3 S8 r5 S11 S9 S10 r5 acc S5 S7 r1 r3 r2 r4 状态 0 1 2 3 4 5 6 7 8 9 10 11 四、测试运行 4.1 程序运行截图 4.1.1 输入字符串 ABSD# 图 4-1 8

资料库

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

相关推荐

课程资源

热门标签

最新资料