LR分析实验报告

1、学号:E 专业:计算机科学与技术二班 姓名:杨雨露实验日期:2012/5/25 教师签字: 成绩:编译原理课程实验报告Word上实验四:LR分析 目 录引言.1第一章 概述.2 1.1设计题目及内容.2 1.2设计环境.2第二章 设计的基本原理.3 2.1 LR分析器的基本理.3 2.2 LR分析器工作过程算法.3 第三章 程序设计.5 3.1总体方案设计.5 3.2各模块设计.5 第四章 程序测试和结论以及心得. .7参考文献. 7 附录 程序清单.8第一章 概述11设计题目及内容设计题目：根据LR分析表构造LR分析器内容：已知文法G：(1)EE+T (2) ET (3) TT*F (4)

2、TF (5) F(E) (6) FILR分析表：状态Action表GOTO表 a b c # S A B0S21231accept2S7353S7S484R1R1R1R15S66R3R3R3R37R4R4R4R48S99R2R2R2R2注：sj表示把下一状态j和现行输入符号a移进栈rj表示按第j个产生式进行规约acc表示接受空格表示出错标志，报错根据以上文法和LR分析表，构造LR分析器，并要求输出LR工作过程。12设计环境硬件设备：一台PC机软件设备：Windows 2000/XP OS ，VC+6.0 实现语言：C语言第二章 设计的基本原理21 基本原理1.LR方法的基本思想： 在规范规约的

3、过程中，一方面记住已移进和规约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据记载的“历史”和“展望”以及“现实”的输入符号等三个方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。2LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。3LR分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。4为清晰说明LR分析器实现原理和模型： LR分析器的核心部分是一张分析表。这张分析表包括两个部分，一是“动作”（ACTION）表，另一是“状态转换”（GOTO）

4、表。他们都是二维数组。ACTION(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)和文法符

5、号A推进栈。规约动作不改变现行输入符号。执行规约动作意味着（= Xm-r+1Xm）已呈现于栈顶而且是一个相对于A的句柄。（3）接受宣布分析成功，停止分析器的工作。（4）报错发现源程序含有错误，调用出错处理程序。22 LR分析器工作过程算法描述一个LR分析器的工作过程可看成是栈里的状态序列，已规约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为 （s0, #, a1a2an#）其中，s0为分析器的初态；为句子的左括号；a1a2an为输入串；其后的为结束符（句子右括号）。分析过程每步的结果可表示为（s0s1sm， #X1X2Xm ai, ai+1an#）分析器的下一步动作是由栈顶状态s

6、m和现行输入符号ai所唯一决定的。即，执行ACTION（sm，ai）所规定的动作。经执行每种可能的动作之后，三元式的变化情形是：（1） 若ACTION（sm，ai）为移进，且s = GOTO（sm，ai），则三元式变成： （s0s1sm s， #X1X2Xm ai, ai+1an#）（2） 若ACTION（sm，ai）= A,则按照产生式A进行规约。此时三元式变为 （s0s1sm s， #X1X2Xm A, ai ai+1an#） 此处s = GOTO（Sm-r，A），r为的长度， = Xm-r+1Xm。（3） 若ACTION（sm，ai）为“接受”，则三元式不再变化，变化过程终止，宣布分析成

7、功。（4） 若ACTION（sm，ai）为“报错”，则三元式的变化过程终止，报告错误。一个LR分析器的工作过程就是一步一步的变换三元式，直至执行“接受”或“报错”为止。 第三章 程序设计31总体设计方案建模（1）分析表建模： 构造一个int 型二维数组table139,用于存放LR分析表。并初始化。作者这样规定：011 表示 状态sj，其中0对应s0，1对应s12126表示 规约rj，其中21对应r1，22对应r212表示 “接受”-1表示 规约出错，报错（2）栈建模： 建立一个int 型状态栈，该栈为顺序栈。 建立一个char型符号栈和一个char型输入串栈，该栈为顺序栈。（3）规约表达式建

8、模： 建立一个rule型结构，成员变量为char型非终结符和int型表示规约第几条表达式。程序设计关键注意环节（1）在输入串(句子)输入的过程中，涉及到一个压栈的问题。但是输入串压入的字符顺序刚好与原理中的字符串模型刚好相反，这样需要先弹出的反而在栈底。为了既要保证字符串输入，又要让输入的字符串存储顺序与输入的字符串相反。采取以下措施： 先将输入的字符串压入符号栈symbol中，然后符号栈弹出的字符再压入输入串栈instr中，这样实现了输入串的倒序存储。（2）状态栈status_stack(status_p)和符号栈symbol_instr(symbol_p)输出（遍历）过程均采取自栈底到栈顶

9、的顺序，而输入串栈 symbol_instr(instr_p)则是采取自栈顶到栈底的顺序输出。32各模块设计栈设计构造一个int型“状态栈”status和一个char型“符号输入串栈” symbol_instr。该栈包括初始化该栈init_status()，压栈push()，弹栈pop()，取栈顶元素get_top()，自栈底到栈顶遍历元素out_stack1()和自栈顶到栈底遍历元素out_stack2()。LR分析器工作过程算法设计构造一个状态转换函数实现状态转换int goto_char(status *status_p,symbol_instr *instr_p)构造一个移进规约函数实

10、现移进规约动作voidaction(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p)构造一个打印LR分析器的工作过程函数实现输出void print(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p)流程图 初始化状态栈，符号栈，输入串栈输入串各字符压栈 求下一状态符号ii = goto_char(status_p,instr_p)规约出错！异常中止！i = = -1 ?规约成功！退出i = = 12 ?规约动作：1 求出i对应规约规则右部字符串

11、长度x = ri-21.y2 在符号栈和状态栈中弹出x个字符。然后将该规约规则左部压入输入串栈i0 & i=11 移进动作：1 将现状态i压栈push(status_p,i)2 将当前输入串字符压入符号栈a = pop(instr_p)push(symbol_p,a)打印该步工作过程 LR分析器设计流程图 附录 程序源代码一：头文件 lr.h/LR分析表#include#include/0-11表示状态结点，2126表示规约标号，/-1表示error（出错），12表示acc（接受）int table107 = 2,-1,-1, -1,1, -1, -1,-1, -1,-1,12,-1,-1,-

12、1,-1,7,-1,-1,-1,3,5,-1,7,4,-1,-1,-1,8, 21,21,21,21,-1, -1,-1,6,-1,-1,-1,-1,-1,-1,23,23,23,23,-1,-1,-1,24,24,24,24,-1,-1,-1,-1,9,-1,-1,-1,-1,-1,22,22,22,22,-1,-1,-1/规约规则struct rulechar x;int y;r6=E,3,E,1,T,3,T,1,F,3,F,1;/输入字符char index_char9=i,+,*,(,),#,E,T,F;/获取index_char9中元素的位置int get_index_char(ch

13、ar i)for(int j=0;j9;j+)if(index_charj = i)return j;return -1;二：头文件 status_stack.h#include#include#define MAX 20typedef structint stackMAX;int top;status;/初始化栈void init_stack(status *p)if( !p)printf(n初始化状态栈出错!n);p-top = -1;/压栈void push(status *p,int x)if(p-top top+;p-stackp-top = x;else printf(n状态栈溢出

14、!n);/弹栈int pop(status *p)int x;if(p-top != 0)x = p-stackp-top;p-top-;return x;else printf(n状态栈1空!n);return 0;/取栈顶元素int get_top(status *p)int x;if(p-top != -1)x = p-stackp-top;return x;else printf(n状态栈2空!n);return 0;/遍历栈元素void out_stack(status *p)int i;if(p-top 0)printf(n状态栈3空!n);for(i=0; itop;i+)pri

15、ntf(%d,p-stacki);三：头文件 symbol_instr_stack.h#include#include#define MAX 20typedef structchar stackMAX;int top;symbol_instr;/初始化栈void init_stack(symbol_instr *p)if( !p)printf(n初始化符号栈出错!n);p-top = -1;/压栈void push(symbol_instr *p,char x)if(p-top top+;p-stackp-top = x;else printf(n符号栈溢出!n);/弹栈char pop(sy

16、mbol_instr *p)char x;if(p-top != -1)x = p-stackp-top;p-top-;return x;else printf(n符号栈1空!n);return 0;/取栈顶元素char get_top(symbol_instr *p)char x;if(p-top != -1)x = p-stackp-top;return x;else printf(n符号栈2空!n);return 0;/自栈底到栈顶遍历栈元素void out_stack1(symbol_instr *p)int i;if(p-top 0)printf(n符号栈3空!n);for(i=0;

17、 itop;i+)printf(%c,p-stacki);/自栈顶到栈底遍历栈元素void out_stack2(symbol_instr *p)int i;if(p-top top;i=0;i-)printf(%c,p-stacki);四：主程序：#includestatus_stack.h#includesymbol_instr_stack.h#includelr.h/打印LR分析器的工作过程void print(status *status_p,symbol_instr *symbol_p,symbol_instr *instr_p)int i;out_stack(status_p);for(i=0;itop;i+)printf( );out_stack1(symbol_p);for(i=0;i=0 & i