lr分析器实验报告

1、第 1 页 共 34 页lr分析器实验报告.1第一章 概述.21.1设计题目及内容.21.2设计环境.2第二章 设计的基本原理.32.1 LR 分析器的基本理.32.2 LR 分析器工作过程算法.3第 2 页 共 34 页第三章 程序设计.53.1 总体方案设计.53.2各模块设计.5第四章 程序测试和结论以及心得 . .7参考文献 .7附录 程序清单.8第一章 概述1 1 设计题目及内容设计题目： 根据 LR 分析表构造 LR 分析器 内容：已知文法 G: (1)E - E+T第3页共 34 页(2)E - T(3)T T*FT - F(5) F - (E)(6) F TLR 分析表:状态A

2、ction 表GOT(表abc#SAB0S21231accep t2S7353S7S484R1R1R1R15S66R3R3R3R37R4R4R4R48S9第4页共 34 页9R2R2R2R2注：sj 表示把下一状态 j 和现行输入符号 a 移进栈rj 表示按第 j 个产生式进行规约acc表示接受空格表示出错标志，报错根据以上文法和 LR 分析表，构造 LR 分析器，并要求输出 程。1. 2 设计环境硬件设备：一台 PC 机软件设备： Windows 2000/XP OS , VC+6.0实现语言：C 语言设计的基本原理2 1 基本原理LR 工作过第二章第 5 页 共 34 页1.LR 方法的基

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

4、” (ACTION 表，另一是“状态转换”(GOTO 表。他们 都是二维数组。 ACTION(s,a)规定了当状态 s 面临输入符号 a 时应采 取什么动作。GOTQs, X)规定了状态 s 面对文法符号 X(终结符或 非终结符)时下一状态是什么。显然，GOTO(s X)定义了一个以文法符号为字母表的 DFA。第 6 页 共 34 页每一项 ACTION(s，a) 所规定的动作不外是下述四种可能之一：(1)移进把(s, a)的下一个转态 s = GOTO(s, X)和 输入符号 a 推进栈，下一输入符号变成现行输入符号。(2)规约指用某一产生式 A-B进行规约。假若B的长度为 r，规约的动作是

5、 A,去除栈顶的 r 个项，使状态 Sm-r 变成栈 顶状态，然后把(Sm-r，A)的下一状态 s = GOTO(Sm-r,A)和文法 符号 A 推进栈。规约动作不改变现行输入符号。执行规约动作意味着B(= Xm-r+1Xn)已呈现于栈顶而且是一个相对于 A 的句柄。(3)接受宣布分析成功，停止分析器的工作。(4)报错发现源程序含有错误，调用出错处理程序。2 2 LR 分析器工作过程算法描述一个 LR 分析器的工作过程可看成是栈里的状态序列，已规约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为( s0,#, a1a2 an#)其中，s0 为分析器的初态；#为句子的左括号；a1a2

6、.an 为输入串；其后的为结束符(句子右括号)。分析过程每步的结果可表示 为(s0s1.sm, #X1X2.Xm ai, ai+1 .an#) 分析第 7 页 共 34 页器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定 的。即，执行 ACTION(sm，ai )所规定的动作。经执行每种可能的 动作之后，三元式的变化情形是：(1) 若 ACTION(sm，ai )为移进，且 s = GOT(O sm，ai )，则三元 式变成：(s0s1 sm s, #X1X2.Xm ai, ai+1 an#)(2)若 ACTION(sm ai ) = A-B,则按照产生式 A-B进行规约。 此时三元

7、式变为(s0s1.sm s, #X1X2.Xm A, ai ai+1 an#)此处 s = GOTO( Sm-r, A), r 为B的长度，B= Xm-r+1 .Xm。( 3) 若 ACTION(sm, ai )为“接受”,则三元式不再变化,变化过 程终止,宣布分析成功。(4) 若 ACTION(sm, ai )为“报错”,则三元式的变化过程终止, 报告错误。一个 LR 分析器的工作过程就是一步一步的变换三元式，直至执行“接受”或“报错”为止。第 8 页 共 34 页第 9 页 共 34 页第三章 程序设计3 1 总体设计方案第 10 页 共 34 页建模（1）分析表建模：构造一个 int 型

8、二维数组 table139, 用于存放 LR 分析表。 并初始化。作者这样规定：011 表示 状态 sj，其中 0 对应 s0, 1 对应 si 2126表示 规约 rj，其中 21 对应 r1 , 22 对应r2 12表示 “接受”-1表示 规约出错，报错（2）栈建模：建立一个 int 型状态栈，该栈为顺序栈。建立一个 char 型符号栈和一个 char 型输入串栈，该栈为顺序栈。（3）规约表达式建模：建立一个 rule 型结构，成员变量为 char 型非终结符和 int 型表 示规约第几条表达式。程序设计关键注意环节（ 1 ）在输入串（句子）输入的过程中，涉及到一个压栈的问题。但这样第 1

9、1 页 共 34 页是输入串压入的字符顺序刚好与原理中的字符串模型刚好相反， 需要先弹出的反而在栈底。 为了既要保证字符串输入， 又要让输入的 字符串存储顺序与输入的字符串相反。采取以下措施： 先将输入的字符串压入符号栈symbol 中，然后符号栈弹出的字 符再压入输入串栈 instr 中，这样实现了输入串的倒序存储。( 2 ) 状 态 栈 status_stack(status_p) 和 符 号 栈symbol_instr(symbol_p) 输出(遍历) 过程均采取自栈底到栈顶的顺 序，而输入串栈 symbol_instr(instr_p) 则是采取自栈顶到栈底的顺 序输出。32 各模块设

10、计栈设计构造一个 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)构造一个移进规约函数实现移进规约动作voidaction(status *status

11、_p,symbol_instr第 12 页 共 34 页*symbol_p,symbol_instr *instr_p)构造一个打印 LR 分析器的工作过程函数实现输出void print(status *status_p,symbol_instr*symbol_p,symbol_instr *instr_p)第 13 页 共 34 页流程图第 14 页共 34 页初始化状态栈，符号栈, 输入串栈_X_输入串各字符压栈求下一状态符号ii = goto_char(status_p,i nstr_p)规约动作：1.求出i对应规约规则右部 字符串长度x = ri-21.y2.在符号栈和状态栈中弹出x

12、个字符。然后将该规 约规则左部压入输入串 栈i = = 12 ?i0 & i=11.规约出错！异 常中止！*规约成功！退 出移进动作：1.将现状态i压 栈LR分析器设计流程图附录push(status_p,i)2.将当前输入串字符压入符号栈apop( in str_p)push(symbol_p,a)1f打印该步程工作过第 15 页 共 34 页程序源代码一：头文件 lr.h/LR 分析表#include#include/0-11 表示状态结点， 2126 表示规约标号，/-1 表示 error （出错）， 12 表示 acc （接受）int table107 = 2,-1,-1, -

13、1,1, -1, -1,-1, -1,-1,12,-1,-1,-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 rule第 16 页 共 34 页char x;int y;r6=E,3,E,1,T,3,T,1,F,3,F,1;/ 输入字符char index_char9=i,+,*,(,),#,

14、E,T,F;/ 获取 index_char9 中元素的位置int get_index_char(char 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;第 17 页 共 34 页int top;status;/ 初始化栈void init_stack(status *p)if( !p)printf(n 初始化状态栈出错 !n); p-top = -1;/ 压栈void p

15、ush(status *p,int x)if(p-top top+;p-stackp-top = x;else printf(n 状态栈溢出 !n);第 18 页 共 34 页/ 弹栈int pop(status *p)int x;if(p-top != 0)x = p-stackp-top;p-top-;return x;elseprin tf(n状态栈 1 空!n);return 0;/ 取栈顶元素int get_top(status *p)int x;if(p-top != -1)第 19 页 共 34 页x = p-stackp-top;return x;elseprintf(n状态栈

16、 2 空!n);return 0;/ 遍历栈元素void out_stack(status *p)int i;if(p-top 0)printf(n 状态栈 3 空!n);for(i=0; itop;i+)printf(%d,p-stacki);第 20 页 共 34 页三：头文件 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 初始化符号

17、栈出错 !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(symbol_instr *p)char x;if(p-top != -1)x = p-stackp-top;p-top-;return x;elseprintf(n 符号栈 1 空 !n);return 0;第 22 页 共 34 页/ 取栈顶元素char get_top(symbol_instr *p)char x;if(p-top != -1)

18、第 23 页 共 34 页x = p-stackp-top;return x;elseprintf(n 符号栈 2 空 !n);return 0;/ 自栈底到栈顶遍历栈元素void out_stack1(symbol_instr *p)int i;if(p-top 0)printf(n 符号栈 3 空!n);for(i=0; itop;i+)printf(%c,p-stacki);/ 自栈顶到栈底遍历栈元素void out_stack2(symbol_instr *p)第 24 页 共 34 页int i;if(p-top top;i=0;i-)printf(%c,p-stacki);四：主程

19、序：#includestatus_stack.h#includesymbol_instr_stack.h#includelr.h/打印 LR 分析器的工作过程void print(status *status_p,symbol_instry = get_top(status_p);第 25 页 共 34 页*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=21 & i=26)x = ri-21.y;for(j=0;jtop != 0)x = p