lr分析器实验报告.docx
《lr分析器实验报告.docx》由会员分享,可在线阅读,更多相关《lr分析器实验报告.docx(18页珍藏版)》请在冰点文库上搜索。
lr分析器实验报告
lr分析器实验报告
引言..............................................................1
第一章概述....................................................2
1.1设计题目及内容.............................................2
1.2设计环境...................................................2
第二章设计的基本原理..........................................3
2.1LR分析器的基本理..........................................3
2.2LR分析器工作过程算法......................................3
第三章程序设计................................................5
3.1总体方案设计..............................................5
3.2各模块设计.................................................5
第四章程序测试和结论以及心得..................................7
参考文献..........................................................7
附录程序清单................................................8
第一章概述
1.1设计题目及内容
设计题目:
根据LR分析表构造LR分析器
内容:
已知文法G:
(1)E→E+T
(2)E→T
(3)T→T*F
(4)T→F
(5)F→(E)
(6)F→I
LR分析表:
状态
Action表
GOTO表
a
b
c
#
S
A
B
0
S2
1
2
3
1
accept
2
S7
3
5
3
S7
S4
8
4
R1
R1
R1
R1
5
S6
6
R3
R3
R3
R3
7
R4
R4
R4
R4
8
S9
9
R2
R2
R2
R2
注:
sj表示把下一状态j和现行输入符号a移进栈
rj表示按第j个产生式进行规约
acc表示接受
空格表示出错标志,报错
根据以上文法和LR分析表,构造LR分析器,并要求输出LR工作过程。
1.2设计环境
硬件设备:
一台PC机
软件设备:
Windows2000/XPOS,VC++6.0
实现语言:
C语言
第二章设计的基本原理
2.1基本原理
1.LR方法的基本思想:
在规范规约的过程中,一方面记住已移进和规约出的整个符号串,即记住“历史”,另一方面根据所用的产生式推测未来可能碰到的输入符号,即对未来进行“展望”。
当一串貌似句柄的符号串呈现于分析栈的顶端时,我们希望能够根据记载的“历史”和“展望”以及“现实”的输入符号等三个方面的材料,来确定栈顶的符号串是否构成相对某一产生式的句柄。
2.LR分析器实质上是一个带先进后出存储器(栈)的确定有限状态自动机。
3.LR分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。
4.为清晰说明LR分析器实现原理和模型:
LR分析器的核心部分是一张分析表。
这张分析表包括两个部分,一是“动作”(ACTION)表,另一是“状态转换”(GOTO)表。
他们都是二维数组。
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)和文法符号A推进栈。
规约动作不改变现行输入符号。
执行规约动作意味着β(=Xm-r+1…Xm)已呈现于栈顶而且是一个相对于A的句柄。
(3)接受宣布分析成功,停止分析器的工作。
(4)报错发现源程序含有错误,调用出错处理程序。
2.2LR分析器工作过程算法描述
一个LR分析器的工作过程可看成是栈里的状态序列,已规约串和输入串所构成的三元式的变化过程。
分析开始时的初始三元式为
(s0,#,a1a2……an#)
其中,s0为分析器的初态;#为句子的左括号;a1a2……an为输入串;其后的#为结束符(句子右括号)。
分析过程每步的结果可表示为
(s0s1……sm,#X1X2……Xmai,ai+1……an#)
分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的。
即,执行ACTION(sm,ai)所规定的动作。
经执行每种可能的动作之后,三元式的变化情形是:
(1)若ACTION(sm,ai)为移进,且s=GOTO(sm,ai),则三元式变成:
(s0s1……sms,#X1X2……Xmai,ai+1……an#)
(2)若ACTION(sm,ai)={A→β},则按照产生式A→β进行规约。
此时三元式变为
(s0s1……sms,#X1X2……XmA,aiai+1……an#)
此处s=GOTO(Sm-r,A),r为β的长度,β=Xm-r+1……Xm。
(3)若ACTION(sm,ai)为“接受”,则三元式不再变化,变化过程终止,宣布分析成功。
(4)若ACTION(sm,ai)为“报错”,则三元式的变化过程终止,报告错误。
一个LR分析器的工作过程就是一步一步的变换三元式,直至执行“接受”或“报错”为止。
第三章程序设计
3.1总体设计方案
建模
(1)分析表建模:
构造一个int型二维数组table[13][9],用于存放LR分析表。
并初始化。
作者这样规定:
0~11表示状态sj,其中0对应s0,1对应s1……
21~26表示规约rj,其中21对应r1,22对应r2……
12表示“接受”
-1表示规约出错,报错
(2)栈建模:
建立一个int型状态栈,该栈为顺序栈。
建立一个char型符号栈和一个char型输入串栈,该栈为顺序栈。
(3)规约表达式建模:
建立一个rule型结构,成员变量为char型非终结符和int型表示规约第几条表达式。
程序设计关键注意环节
(1)在输入串(句子)输入的过程中,涉及到一个压栈的问题。
但是输入串压入的字符顺序刚好与原理中的字符串模型刚好相反,这样需要先弹出的反而在栈底。
为了既要保证字符串输入,又要让输入的字符串存储顺序与输入的字符串相反。
采取以下措施:
先将输入的字符串压入符号栈symbol中,然后符号栈弹出的字符再压入输入串栈instr中,这样实现了输入串的倒序存储。
(2)状态栈status_stack(status_p)和符号栈symbol_instr(symbol_p)输出(遍历)过程均采取自栈底到栈顶的顺序,而输入串栈symbol_instr(instr_p)则是采取自栈顶到栈底的顺序输出。
3.2各模块设计
栈设计
构造一个int型“状态栈”status和一个char型“符号-输入串栈”symbol_instr。
该栈包括初始化该栈init_status(),压栈push(),弹栈pop(),取栈顶元素get_top(),自栈底到栈顶遍历元素out_stack1()和自栈顶到栈底遍历元素out_stack2()。
LR分析器工作过程算法设计
构造一个状态转换函数实现状态转换
intgoto_char(status*status_p,symbol_instr*instr_p)
构造一个移进--规约函数实现移进规约动作
voidaction(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)
构造一个打印LR分析器的工作过程函数实现输出
voidprint(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)
流程图
LR分析器设计流程图
附录
程序源代码
一:
头文件lr.h
//LR分析表
#include
#include
//0--11表示状态结点,21--26表示规约标号,
//-1表示error(出错),12表示acc(接受)
inttable[10][7]={{2,-1,-1,-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}}
//规约规则
structrule{
charx;
inty;
}r[6]={{'E',3},{'E',1},{'T',3},{'T',1},{'F',3},{'F',1}};
//输入字符
charindex_char[9]={'i','+','*','(',')','#','E','T','F'};//
//获取index_char[9]中元素的位置
intget_index_char(chari)
{
for(intj=0;j<9;j++)
{
if(index_char[j]==i)
returnj;
}
return-1;
}
二:
头文件status_stack.h
#include
#include
#defineMAX20
typedefstruct{
intstack[MAX];
inttop;
}status;
//初始化栈
voidinit_stack(status*p)
{
if(!
p)
printf("\n初始化状态栈出错!
\n");
p->top=-1;
}
//压栈
voidpush(status*p,intx)
{
if(p->top{
p->top++;
p->stack[p->top]=x;
}
elseprintf("\n状态栈溢出!
\n");
}
//弹栈
intpop(status*p)
{
intx;
if(p->top!
=0)
{
x=p->stack[p->top];
p->top--;
returnx;
}
else
{
printf("\n状态栈1空!
\n");
return0;
}
}
//取栈顶元素
intget_top(status*p)
{
intx;
if(p->top!
=-1)
{
x=p->stack[p->top];
returnx;
}
else
{
printf("\n状态栈2空!
\n");
return0;
}
}
//遍历栈元素
voidout_stack(status*p)
{
inti;
if(p->top<0)
printf("\n状态栈3空!
\n");
for(i=0;i<=p->top;i++)
{
printf("%d",p->stack[i]);
}
}
三:
头文件symbol_instr_stack..h
#include
#include
#defineMAX20
typedefstruct{
charstack[MAX];
inttop;
}symbol_instr;
//初始化栈
voidinit_stack(symbol_instr*p)
{
if(!
p)
printf("\n初始化符号栈出错!
\n");
p->top=-1;
}
//压栈
voidpush(symbol_instr*p,charx)
{
if(p->top{
p->top++;
p->stack[p->top]=x;
}
elseprintf("\n符号栈溢出!
\n");
}
//弹栈
charpop(symbol_instr*p)
{
charx;
if(p->top!
=-1)
{
x=p->stack[p->top];
p->top--;
returnx;
}
else
{
printf("\n符号栈1空!
\n");
return0;
}
}
//取栈顶元素
charget_top(symbol_instr*p)
{
charx;
if(p->top!
=-1)
{
x=p->stack[p->top];
returnx;
}
else
{
printf("\n符号栈2空!
\n");
return0;
}
}
//自栈底到栈顶遍历栈元素
voidout_stack1(symbol_instr*p)
{
inti;
if(p->top<0)
printf("\n符号栈3空!
\n");
for(i=0;i<=p->top;i++)
{
printf("%c",p->stack[i]);
}
}
//自栈顶到栈底遍历栈元素
voidout_stack2(symbol_instr*p)
{
inti;
if(p->top<0)
printf("\n符号栈4空!
\n");
for(i=p->top;i>=0;i--)
{
printf("%c",p->stack[i]);
}
}
四:
主程序:
#include"status_stack.h"
#include"symbol_instr_stack.h"
#include"lr.h"
//打印LR分析器的工作过程
voidprint(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)
{
inti;
out_stack(status_p);
for(i=0;i<20-status_p->top;i++)
printf("");
out_stack1(symbol_p);
for(i=0;i<20;i++)
printf("");
out_stack2(instr_p);
printf("\n");
}
//状态转换函数
intgoto_char(status*status_p,symbol_instr*instr_p)
{
charx;
inty,z;
x=get_top(instr_p);
y=get_top(status_p);
z=get_index_char(x);
returntable[y][z];
}
//移进--规约函数
voidaction(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)
{
inti,j,x;
chara;
i=goto_char(status_p,instr_p);
//规约出错
if(i==-1)
printf("\n===============规约出错!
================\n");
//规约成功
if(i==12)
printf("\n===============规约成功!
================\n");
//移进动作
if(i>=0&&i<=11)
{
push(status_p,i);
a=pop(instr_p);
push(symbol_p,a);
print(status_p,symbol_p,instr_p);
action(status_p,symbol_p,instr_p);
}
//规约动作
if(i>=21&&i<=26)
{
x=r[i-21].y;
for(j=0;j{
pop(status_p);
pop(symbol_p);
}
push(instr_p,r[i-21].x);
action(status_p,symbol_p,instr_p);
}
}
intmain()
{
charx;
//分配空间
status*status_p;
symbol_instr*symbol_p,*instr_p;
status_p=(status*)malloc(sizeof(status));
symbol_p=(symbol_instr*)malloc(sizeof(symbol_instr));
instr_p=(symbol_instr*)malloc(sizeof(symbol_instr));
//初始化各栈
init_stack(status_p);
init_stack(symbol_p);
init_stack(instr_p);
//压进栈初始元素
push(status_p,0);//
push(symbol_p,'#');//
//输入表达式
printf("\n请输入要规约的输入串,各字符之间不能有空格,以'#'字符结束!
\n");
printf("===========Expression=");
//先将输入串压进符号栈
do{
scanf("%c",&x);
push(symbol_p,x);
}while(x!
='#');
//然后由符号栈弹出,压进输入栈