LR分析Word格式.doc
- 文档编号:3633331
- 上传时间:2023-05-02
- 格式:DOC
- 页数:11
- 大小:144KB
LR分析Word格式.doc
《LR分析Word格式.doc》由会员分享,可在线阅读,更多相关《LR分析Word格式.doc(11页珍藏版)》请在冰点文库上搜索。
5
1
R6
2
6
A
S7
R2
S8
R4
S9
7
10
8
11
9
R5
R1
R3
SN=移进并转移到状态NA=accept接受
RN=按第N条产生式进行规约-=error转移
(2)LR分析器总控程序框架如下:
push(0);
advance();
while(Action[tos][sym]!
=accept)
if(Action[tos][sym]==’-’)error();
elseif(Action[tos][sym]==SN){
push(N);
}
elseif(Action[tos][sym]==RN{
act(N);
pop(产生式N的右部的符号个数);
push(Goto[新tos][产生式N的左部符号]);
accept();
上述算法中的有关函数与符号的意义如下:
accept():
返回成功状态,LR分析器停止工作;
act(N):
执行利用产生式N的归约的动作,通常为产生代码;
advance():
丛输入流读下一单词到sym;
error():
出错处理;
pop(N):
从栈顶弹出N个符号(状态);
push(N):
把状态N压入状态栈;
sym:
当前输入的单词符号;
tos:
栈顶状态号。
(3)存放LR分析表的数据结构
①实现方法一:
用一个二维整数数组表示
数组元素为表示动作的整数。
数组的行下标为状态号,列下标用来表示终结符与非终结符的整数表示。
数组元素可作如下约定:
正整数:
表示移进动作,如S6用数6表示;
负整数:
表示归约动作,如R5用数-5表示;
0:
表示接受,通常为按产生式0归约;
状态号也用整数表示;
用不可能是状态号的较大的整数表示错误转移。
请将上述LALR
(1)分析表用这种表示方法,完成LR分析器的程序设计,并添加输出状态栈内容的功能。
用上述表达式文法G的一个句子作为输入,进行测试。
②实现方法二:
采用压缩表示法
动作Action表的每一行用一个数组表示,数组的第一个元素是本数组中存放的数偶个数,第二个元素到最后一个元素都以[终结符,动作]的数偶的形式存放。
再用一个以状态号为下标的下标数组,每个元素含一个指向数偶数组的指针。
若数组元素的值为NULL,则表示从此状态无转移弧发出。
若分析表有几行相同,则只需保存一行,其它元素则都指向存放这一行表的数组即可。
转移Goto表也按同样方式组织,只是这个行数组的数偶为[非终结符,下一状态号]。
每个行数组Yyan表示动作表Yy_action的一行,每个行数组Yygn表示转移表Yy_goto的一行。
假定上述表达式文法G中终结符及非终结符的整数值为:
终结符:
#ID+*()非终结符:
SETF
整数值:
012345整数值:
0123
Yy_action数组是以状态号为下标的下标数组,每个元素含有指向数组Yyan的指针;
下标数组Yy_goto的每个元素含有指向数组Yygn的指针。
表达式文法G的LALR
(1)分析表的具体压缩表示如下:
Yy_action
.
4,2
1,1
Yya000
5,-6
3,-6
2,-6
0,-6
Yya001
0,0
2,7
Yya003
5,-2
2,-2
0,-2
3,8
Yya004
5,-4
3,-4
2,-4
0,-4
Yya005
5,9
Yya006
5,-5
3,-5
2,-5
0,-5
Yya009
5,-1
2,-1
0,-1
Yya010
5,-3
2,-3
0,-3
Yya011
Yyg000
3,5
2,4
1,3
NULL
1,6
Yyg002
2,10
Yyg007
3,11
Yyg008
以上分析表用C语言程序描述如下:
/*
*Yy_action表
*/
intYya000[]={2,4,2,1,1};
intYya001[]={4,5,-6,3,-6,2,-6,0,-6};
intYya003[]={2,0,0,2,7};
intYya004[]={4,5,-2,2,-2,0,-2,3,8};
intYya005[]={4,5,-4,3,-4,2,-4,0,-4};
intYya006[]={2,5,9,2,7};
intYya009[]={4,5,-53,-5,2,-5,0,-5};
intYya010[]={4,5,-1,2,-1,0,-1,3,8};
intYya011[]={4,5,-3,3,-3,2,-3,0,-3};
intYy_action[]=
{
Yya000,Yya001,Yya000,Yya003,Yya004,Yya005,
Yya006,Yya000,Yya000,Yya009,Yya010,Yya011
};
*Yy_goto表
intYyg000[]={3,3,5,2,4,1,3};
intYyg002[]={3,3,5,2,4,1,6};
intYyg007[]={2,3,5,2,10};
intYyg008[]={1,3,11};
intYy_goto[]=
{
Yyg000,NULL,Yyg002,NULL,NULL,NULL,
NULL,Yyg007,Yyg008,NULL,NULL,NULL
};
*为了进行归约,使用一个Yy_lhs[]数组,其值为代表产生式左部符号的
*整数,数组的下标为产生式号
intYy_lhs[7]=
/*0*/0,
/*1*/1,
/*2*/1,
/*3*/2,
/*4*/2,
/*5*/3,
/*6*/3
*Yy_reduce[]数组元素的值为产生式右部符号的个数,
*以产生式号为数组的下标索引
intYy_reduce[]=
/*0*/1,
/*1*/3,
/*2*/1,
/*3*/3,
/*4*/1,
/*5*/3,
/*6*/1
根据以上数组结构,构造函数Yy_next(),其功能是在给定状态和输入符号下,求出应采取的动作或转向的下一状态。
intYy_next(table,cur_state,symbol)
int**table;
/*要查的表*/
intcur_state;
/*行号*/
intsymbol;
/*列号*/
int*p=table[cur_state];
inti;
if(p)
for(i=(int)*p++;
--i>
0;
p+=2)
if(symbol==p[0])
return(p[1]);
returnYYF;
/*出错指示*/
指针p指向Yyan数组或Yygn数组,由参数table的值而定。
如果table指向Yy_action,则p指向Yyan数组;
若table指向Yy_goto,则p指向Yygn数组据。
根据上述LALR
(1)分析表压缩表示方法,完成LR分析器的程序设计,并添加输出状态栈内容的功能。
4.程序源代码和运行结果:
#include<
iostream>
string>
iomanip>
usingnamespacestd;
char*cp;
/*指向给定的要分析
的表达式语言*/
inti=1;
//从第一步开始执行
structsta_stack
{intstas[50];
inttop1;
//状态栈的数据结构
sta_stackstack1;
//定义一个状态栈
structstr_stack
{stringstrs[50];
inttop2;
//符号栈的数据结构
str_stackstack2;
//定义一个符号栈
/*终结符用相应的整数代替*/
stringsymbol1[6]=
{"
#"
"
ID"
+"
*"
("
)"
/*非终结符也用相应的整数代替*/
stringsymbol2[4]=
S"
E"
T"
F"
/*Yy_action表*/
intYya009[]={4,5,-5,3,-5,2,-5,0,-5};
int*Yy_action[]=
{
Yya000,Yya001,Yya000,Yya003,Yya004,Yya005,
Yya006,Yya000,Yya000,Yya009,Yya010,Yya011
/*Yy_goto表*/
int*Yy_goto[]=
Yyg000,NULL,Yyg002,NULL,NULL,NULL,
NULL,Yyg007,Yyg008,NULL,NULL,NULL
/*为了进行归约,使用一个Yy_lhs[]数组,其值为代表
产生式左部符号的整数,数组的下标为产生式号*/
intYy_lhs[7]={0,1,1,2,2,3,3};
/*Yy_reduce[]数组元素的值为产生式右部符号的个数,
以产生式号为数组的下标索引*/
intYy_reduce[7]={1,3,1,3,1,3,1};
/*根据以上数组结构,构造函数Yy_next(),其功能是在给
定状态和输入符号下,求出应采取的动作或转向的下一状态。
intYy_next(int**table,intcur_state,intsymbol)
int*p=table[cur_state];
inti;
if(p)
for(i=(int)*p++;
i-->
0;
p+=2)
if(symbol==p[0])
return(p[1]);
return8000;
/*出错指示*/
/*将相应的状态和符号进行压栈*/
voidpush(intsta,stringstr)
{stack1.top1++;
stack1.stas[stack1.top1]=sta;
stack2.top2++;
stack2.strs[stack2.top2]=str;
/*从输入流读下一单词到sym*/
stringadvance()
{stringsym;
if(*cp=='
I'
&
*(cp+1)=='
D'
{sym="
;
/*cp=cp+2;
*/}
else
{sym=*cp;
/*cp=cp+1;
returnsym;
/*进行归约动作*/
intact(intYN)
{inttYN=-YN;
returnYy_lhs[tYN];
/*弹栈*/
voidpop(intn)
{stack1.top1-=n;
stack2.top2-=n;
voidoutput()//输出状态栈、符号栈以及未分析输入串
{intsumstrlen=0,i6;
intstasum=0,i7;
cout<
<
setw(3)<
setiosflags(ios:
:
right)<
i<
"
"
for(inti2=0;
i2<
=stack1.top1;
i2++)
{cout<
/*setw(8)<
left)<
*/stack1.stas[i2];
if(stack1.stas[i2]==10||stack1.stas[i2]==11)
i7=2;
elsei7=1;
stasum=stasum+i7;
setw(12-stasum)<
"
for(inti3=0;
i3<
=stack2.top2;
i3++)
stack2.strs[i3];
if(stack2.strs[i3]=="
i6=2;
elsei6=1;
sumstrlen=sumstrlen+i6;
}
setw(12-sumstrlen)<
//cout<
"
setw(8)<
setiosfla
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LR 分析