《编译原理课程设计 lr分析----张小蒙》由会员分享，可在线阅读，更多相关《编译原理课程设计 lr分析----张小蒙（24页珍藏版）》请在金锄头文库上搜索。
1、课课 程程 设设 计计课程名称编译技术课程设计题目名称根据 LR 分析表构造 LR分析器专业班级2013 级软件工程学生姓名张小蒙 吴松琴 李伟 孙萌 程起 杨伟平 张红伟学 号指导教师邹青青二一六年 五 月 二十八 日蚌埠学院计算机科学与技术系课程设计任务书课 程编译技术课程设计班级2013 级软件工程指导教师邹青青题 目根据 LR 分析表构造 LR 分析器完成时 间2016 年 5 月 23 日 至 2015 年 6 月 17 日主要内容1LR 方法的基本思想过程。2LR 分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。3LR 分析器的每一步工作是由栈顶状态和现行输入符号所唯
2、一决定的。4为清晰说明 LR 分析器实现原理和模型：设计报告要求设计报告要求1封面 2课程设计任务书 3. 分工协作说明 4. 成绩评定表 5课程设计报告 系统总体方案 设计思路和主要步骤 各功能模块和流程图 设计代码 心得体会和参考资料 说明：学生完成课程设计后，提交软件及课程设计电子和纸质版，要求报告 文字通畅、字迹工整，文字不少于 3000 字，并按要求装订成册。星期 周次一二三四五六日上机时间安排第 14 周 至 第 17 周5-6 节1-2 节版面要求版面要求1.题目用黑体三号，段后距 18 磅（或 1 行），居中对齐； 2.标题用黑体四号，段前、段后距 6 磅（或 0.3 行）；
3、3.正文用小四号宋体，行距为 1.25 倍行距； 4.标题按“一”、“”、“1”、“”顺序编号。指导时 间地点上机时间，多媒体技术实验室（A503）分工协作说明分工协作说明课题名称课题名称学生姓名学生姓名学号学号所做的工作所做的工作张小蒙总体架构，模块指导吴松琴总体设计方案，综合文档修改李伟模块测试孙萌模块测试程起模块测试根据LR分析表构造LR分析器张红伟模块测试杨伟平资料整理、打印蚌埠学院计算机科学与技术系课程设计成绩评定表蚌埠学院计算机科学与技术系课程设计成绩评定表项目权重分值具体要求得分文献阅读与调查论证0.20100能独立查阅文献和从事其它调研活动；有收集、加工各种信息的能力设计质量0
4、.30100设计合理、功能齐备，程序运行正常，实验数据准确可靠；有较强的实际动手能力论文撰写质量0.20100设计说明书完全符合规范化要求，用 A4 复印纸打印成文学习态度0.20100学习态度认真，科学作风严谨，严格按要求开展各项工作，按期完成任务学术水平与创新0.10100设计有创意，有一定的学术水平或实用价值总分评语：等级： 指导教师： 年 月 日目录1 设计题目及内容11.1 设计题目.11.2 内容.11.3 设计环境.22 设计的基本原理.32.1 基本原理.32.2 LR 分析器工作过程算法描述43 程序设计.53.1 总体设计方案.53.1.1 建模.53.1.2 程序设计关键
5、注意环节53.1.3 LR 分析器的组成 53.1.4 分析器结构图.63.2 各模块设计73.2.1 栈设计.73.2.2 LR 分析器工作过程算法设计.73.3 流程图84 测试运行.94.1 测试一94.2 测试二94.3 测试三105 心得体会.116 参考文献.11附录1211 设计题目及内容1.1 设计题目根据 LR 分析表构造 LR 分析器1.2 内容已知文法 G：(1)EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) FILR 分析表：ACTION(动作)GOTO(转换)状态I + * ( ) # E T F0S5S41231S6Acc2R2S7R2R23
6、R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R52注：sj 表示把下一状态 j 和现行输入符号 a 移进栈rj 表示按第 j 个产生式进行规约acc表示接受空格表示出错标志，报错根据以上文法和 LR 分析表，构造 LR 分析器，并要求输出 LR 工作过程。1.3 设计环境硬件设备：一台 PC 机软件设备：Windows 2000/XP OS ，VC+6.0 实现语言：C 语言32 设计的基本原理2.1 基本原理1.LR 方法的基本思想在规范规约的过程中，一方面记住已移进和规约出的整个符号串，即记
7、住“历史” ，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望” 。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据记载的“历史”和“展望”以及“现实”的输入符号等三个方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。2LR 分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。3LR 分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。4为清晰说明 LR 分析器实现原理和模型：LR 分析器的核心部分是一张分析表。这张分析表包括两个部分，一是“动作” （ACTION）表，另一是“状态转换” （GOTO）表。他们都是二维数组。ACTION
8、(s,a)规定了当状态 s 面临输入符号 a 时应采取什么动作。GOTO（s，X）规定了状态 s 面对文法符号 X（终结符或非终结符）时下一状态是什么。显然，GOTO(s，X)定义了一个以文法符号为字母表的 DFA。每一项 ACTION(s，a)所规定的动作不外是下述四种可能之一：（1）移进：把（s，a）的下一个转态 s = GOTO(s，X)和输入符号 a 推进栈，下一输入符号变成现行输入符号。（2）规约：指用某一产生式 A 进行规约。假若 的长度为 r，规约的动作是 A，去除栈顶的 r 个项，使状态 Sm-r 变成栈顶状态，然后把（Sm-r，A）的下一状态 s = GOTO(Sm-r,A)
9、和文法符号 A 推进栈。规约动作不改变现行输入符号。执行规约动作意味着 （= Xm-r+1Xm）已呈现于栈顶而且是一个相对于 A 的句柄。（3）接受：宣布分析成功，停止分析器的工作。（4）报错：发现源程序含有错误，调用出错处理程序。42.2 LR 分析器工作过程算法描述一个 LR 分析器的工作过程可看成是栈里的状态序列，已规约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为（s0, #, a1a2an#）其中，s0 为分析器的初态；为句子的左括号；a1a2an 为输入串；其后的为结束符（句子右括号） 。分析过程每步的结果可表示为（s0s1sm， #X1X2Xm ai, ai+1an
10、#）分析器的下一步动作是由栈顶状态 sm 和现行输入符号 ai 所唯一决定的。即，执行 ACTION（sm，ai）所规定的动作。经执行每种可能的动作之后，三元式的变化情形是：若 ACTION（sm，ai）为移进，且 s = GOTO（sm，ai） ，则三元式变成：（s0s1sm s， #X1X2Xm ai, ai+1an#）若 ACTION（sm，ai）= A,则按照产生式 A 进行规约。此时三元式变为（s0s1sm s， #X1X2Xm A, ai ai+1an#）此处 s = GOTO（Sm-r，A） ，r 为 的长度， = Xm-r+1Xm。若 ACTION（sm，ai）为“接受” ，则
11、三元式不再变化，变化过程终止，宣布分析成功。若 ACTION（sm，ai）为“报错” ，则三元式的变化过程终止，报告错误。一个 LR 分析器的工作过程就是一步一步的变换三元式，直至执行“接受”或“报错”为止。53 程序设计3.1 总体设计方案3.1.1 建模（1）分析表建模：构造一个 int 型二维数组 table139,用于存放 LR 分析表。并初始化。作者这样规定：011 表示 状态 sj，其中 0 对应 s0，1 对应 s12126 表示 规约 rj，其中 21 对应 r1，22 对应 r212表示 “接受”-1表示 规约出错，报错（2）栈建模：建立一个 int 型状态栈，该栈为顺序栈。
12、建立一个 char 型符号栈和一个 char 型输入串栈，该栈为顺序栈。（3）规约表达式建模：建立一个 rule 型结构，成员变量为 char 型非终结符和 int 型表示规约第几条表达式。3.1.2 程序设计关键注意环节在输入串(句子)输入的过程中，涉及到一个压栈的问题。但是输入串压入的字符顺序刚好与原理中的字符串模型刚好相反，这样需要先弹出的反而在栈底。为了既要保证字符串输入，又要让输入的字符串存储顺序与输入的字符串相反。采取以下措施：先将输入的字符串压入符号栈 symbol 中，然后符号栈弹出的字符再压入输入串栈 instr 中，这样实现了输入串的倒序存储。状态栈 status_stac
13、k(status_p)和符号栈 symbol_instr(symbol_p)输出（遍历）过程均采取自栈底到栈顶的顺序，而输入串栈 symbol_instr(instr_p)则是采取自栈顶到栈底的顺序输出。3.1.3 LR 分析器的组成 (1)总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。 (2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR6分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。 (3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈
14、顶状态和当前输入符号所决定。3.1.4 分析器结构图(1)在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作； (2) 分析表是 LR 分析器的核心，它跟文法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作； (3) 分析栈包括文法符号栈 Xi和相应的状态栈 Si两部分(状态是指能识别活前缀的自动机状态)，LR 分析器通过判断栈顶元素和输入符号查分析表确定下步分析动作。图 3-1 分析器结构图73.2 各模块设计3.2.1 栈设计构造一个 int 型“状态栈”status 和一个 char 型“符号输入串栈” s
15、ymbol_instr。该栈包括初始化该栈 init_status()，压栈 push()，弹栈 pop()，取栈顶元素 get_top()，自栈底到栈顶遍历元素 out_stack1()和自栈顶到栈底遍历元素 out_stack2()。3.2.2 LR 分析器工作过程算法设计构造一个状态转换函数实现状态转换int goto_char(status *status_p,symbol_instr *instr_p) 构造一个移进规约函数实现移进规约动作voidaction(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p)
16、 构造一个打印 LR 分析器的工作过程函数实现输出void print(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p)83.3 流程图图 3-2 LR 分析器设计流程图94 测试运行4.1 测试一输入表达式 i*i+i 并且个符号之间不能有空格，以#字符结束，结果如下：图 4-1 测试图一4.2 测试二输入表达式 i+i*i 并且个符号之间不能有空格，以#字符结束，结果如下10图 4-2 测试图二4.3 测试三输入表达式 i+(i+i)*i+i*i 并且个符号之间不能有空格，以#字符结束， 测试结果如下：图 4-3 测试图三115 心得体会经过这个实验的练习，通过对程序的分析，让我进一步了解 L
