LR(0)分析表构造.pdf

该【LR(0)分析表构造 】是由【花开花落】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【LR(0)分析表构造 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
.
编译原理实验报告
实验名称自动生成LR(0)分析表
实验时间2013、12、10
院系计算机科学与电子技术系
班级2011级计算机软件
学号JV******JV******JV******
姓名段国顺葛立冬黄磊
.:.
.
一、实验目的
输入:任意的压缩了的上下文无关文法。
输出:相应的LR(0)分析表。
二、实验原理
对于LR文法,我们可以自动构造相应的LR分析表。为了构造LR分析表,
我们需要定义一个重要概念——文法的规范句型“活前缀”。
这种句柄之后不含任何符号的前缀称为活前缀。
在LR分析工作过程中的任何时候,栈里的文法符号(自栈底而上)XX…
12
X应该构成活前缀,把输入串的剩余部分配上之后即应成为规范句型(如果整
m
个输入串确实构成一个句子)。因此,只要输入串的已扫描部分保持可归约成一
个活前缀,那就意味着所扫描过的部分没有错误。
对于一个文法G,我们可以构造一个有限自动机,它能识别G的所有活前
缀,然后把这个自动机转变成LR分析表,按照该LR分析表进行LR分析,就
能保证在分析的过程中,如果分析的句子是正确的,栈里的文法符号(自栈底而
上)始终构成活前缀。
假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)
不存在下述情况:(1)既含移进项目又含归约项目;(2)含有多个归约项目,则
称G是一个LR(0)文法。该自动机的状态集合即为该文法的LR(0)项目集
规范族。
构造识别文法活前缀DFA有3种方法:
(1)根据形式定义求出活前缀的正则表达式,然后由此正则表达式构造NFA
再确定为DFA;
(2)求出文法的所有项目,按一定规则构造识别活前缀的NFA再确定化为
DFA;
(3)使用闭包函数(CLOSURE)和转向函数(GO(I,X))构造文法G’的LR(0)
的项目集规范族,再由转换函数建立状态之间的连接关系来得到识别活前缀的
DFA。
符号串的前缀是指该符号串的任意首部,包括空串ε。例如,对于符号串abc,
其前缀有ε,a,ab,abc。如果输入串没有错误的话,一个规范句型的活前缀是
该句型的一个前缀,但它不含句柄之后的任何符号。之所以称为活前缀,是因为
在该前缀后联接尚未输入的符号串可以构成一个规范句型。
活前缀与句柄的关系如下:
(1)活前缀已含有句柄的全部符号,表明产生式A→β的右部β已出现在
栈顶。
(2)活前缀只含句柄的一部分符号,表明A→ββ的右部子串β已出现
121
在栈顶,期待从输入串中看到β推出的符号。
2
(3)活前缀不含有句柄的任何符号,此时期望A→β的右部所推出的符号
串。
在文法G的每个产生式的右部(候选式)的任何位置上添加一个圆点,所构
成的每个产生式称为LR(0)项目。如产生式Axyz有如下项目:A.xyz,
A,A,Axyz.。为刻划分析过程中的文法的每一个产生式的右部
.:.
.
符号已有多大一部分被识别(出现在栈顶),可以用这种标有圆点的产生式来确
定。
(1)A→→β的右部β已出现在栈顶。
(2)A→→ββ的右部子串β已出现在栈顶,期待从输入串
12121
中看到β推出的符号。
2
(3)A→.β刻划没有句柄的任何符号在栈顶,此时期望A→β的右部所推出
的符号串。
(4)对于A→ε的LR(0)项目只有A→.。
设文法G=(V,V,S,P)是一个上下文无关文法,若存在一个规范推导
TN
*
SaAwab1b2w(其中A®b1b2ÎP),则称项目A®b1•b2对活前缀g=ab1是有效的,
rmrm
即LR(0)有效项目。
从直观意义上讲,一个LR(0)项目指明了在分析过程中的某一步我们看到产
生式的多大部分被识别,LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分
界线,圆点左边为已进入分析栈的部分,右边是当前输入或继续扫描的符号串。
不同的LR(0)项目,反映了分析栈顶的不同情况。我们根据LR(0)项目的作
用不同,将其分为四类:
(1)归约项目:
表现形式:A→a.
这类LR(0)项目表示句柄a恰好包含在栈中,即当前栈顶的部分内容构成了
所期望的句柄,应按A→a进行归约。
(2)接受项目:
表现形式:S→a.
其中S是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目,表
示分析栈中内容恰好为a,用S→a进行归约,则整个分析成功。
(3)移进项目:
表现形式:A→(bV)
T
这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀,为构成恰好有句
柄的活前级,需将b移进分析栈。
(4)待约项目:
表现形式:A→(BV)
N
这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀,为构成恰好有句
柄的活前缀,应把当前输入字符串中的相应内容先归约到B。
在给出LR(0)项目的定义和分类之后,我们从这些LR(0)项目出发,来构造
能识别文法所有前缀的有限自动机。其步骤是:首先构造能识别文法所有活前缀
的非确定的有限自动机,再将其确定化和最小化,最终得到所需的确定的有限自
动机。
由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机
的方法:
(1)规定含有文法开始符号的产生式(设S→A)的第一个LR(0)项目(即
S→.A)为NFA的惟一初态。
(2)令所有LR(0)项目分别对应NFA的一个状态且LR(0)项目为归约项目
的对应状态为终态。
.:.
.
(3)若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆
点只相差一个位置,即:
若i为X→XX·…X·X…X,j为X→XX…X·X…X,则从状态
12i-1in12ii+1n
i引一条标记为X的弧到状态j。
i
(4)若状态i为待约项目(设X→α·Aβ),则从状态i引ε弧到所有A
→·r的状态。
为了使“接受”状态易于识别,我们通常将文法G进行拓广。
假定文法G是一个以S为开始符号的文法,我们构造一个G,它包含了整
个G,但它引进了一个不出现在G中的非终结符S,并加进一个新产生式S→S,
以S→SG为开始符号。那么,我们称G是G的拓广文法。
这样,便会有一个仅含项目S→S的状态,这就是惟一的“接受”态。
如果I是文法G'的一个项目集,定义和构造I的闭包CLOSURE(I)如下:
(1)I的项目都在CLOSURE(I)中。
(2)若A→.B属于CLOSURE(I),则每一形如B→.的项目也属于
CLOSURE(I)。
(3)重复(2)直到CLOSURE(I)不再扩大。
定义转换函数如下:
GO(I,X)=CLOSURE(J)
其中:I为包含某一项目集的状态,X为一文法符号,J={A→X.|A→.X
∈I}。
圆点不在产生式右部最左边的项目称为核,惟一的例外是S′→.S,因此用
GOTO(I,X)状态转换函数得到的J为转向后状态闭包项目集的核。
使用闭包函数(CLOSURE)和转换函数(GO(I,X))构造文法G’的LR(0)的项
目集规范族,步骤如下:
(1)置项目S′→.S为初态集的核,然后对核求闭包CLOSURE({S′→.S})
得到初态的闭包项目集。
(2)对初态集或其他所构造的项目集应用转换函数GO(I,X)=CLOSURE(J)
求出新状态J的闭包项目集。
(3)重复(2)直到不出现新的项目集为止。
计算LR(0)项目集规范族C={I,I,...In}的算法伪代码如下:
01
Procedureitemsets(G’);
BeginC:={CLOSURE({S’.S})}
Repeat
ForC中每一项目集I和每一文法符号X
DoifGO(I,X)非空且不属于C
Then把GO(I,X)放入C中
UntilC不再增大
.:.
.
End;
一个项目集可能包含多种项目,若移进和归约项目同时存在,则称移进-归约
冲突,若
归约和归约项目同时存在,则称归约-归约冲突。下面看一个具体的例子:
我们希望能根据识别文法的活前缀的DFA建立LR分析器,因此,需要研
究这个我们说项目A→,其条件是存在规范推导
121
SA。一般而言,同一项目可能对几个活前缀都是有效的(当一个
12
项目出现在几个不同的集合中时便是这种情形)。若归约项目A→
1
是有效的,则它告诉我们应把符号串归约为A,即把活前缀变成αA。
111
若移进项目A→是有效的,则它告诉我们,句柄尚未形成,
121
因此,下一步动作应是移进。但是,可能存在这样的情形,对同一活前缀,存在
若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同,互相冲突。
这种冲突通过向前多看几个输入符号,或许能够获得解决。
对于每个活前缀,我们可以构造它的有效项目集。实际上,一个活前缀γ的
有效项目集正是从上述的DFA的初态出发,经读出γ后而到达的那个项目集(状
态)。换言之,在任何时候,分析栈中的活前缀XX…X的有效项目集正是栈
12m
顶状态S所代表的那个集合。这是LR分析理论的一条基本定理。实际上,栈
m
顶的项目集(状态)体现了栈里的一切有用信息——历史。
前面我们已经对LR(0)文法进行了定义,下面我们来看一下LR(0)分析
表是如何构造的。
对于LR(0)文法,我们可以直接从它的项目集规范族C和活前缀识别自
动机的状态转换函数GO构造出LR分析表。下面是构造LR(0)分析表的算法。
假定C={I,I,…,In},令每个项目集I的下标k为分析器的一个状态,因此,
01k
G'的LR(0)分析表含有状态0,1,…,n。令那个含有项目S'→.S的I的下标k
k
为初态。ACTION子表和GOTO子表可按如下方法构造:
(1)若项目A→(I,a)=I,a为终结符,则置ACTION[k,
kkj
a]为“把状态j和符号a移进栈”,简记为“s”;
j
(2)若项目A→,那么,对任何终结符a,置ACTION[k,a]为“用
k
产生式A→α进行规约”,简记为“r”;其中,假定A→α为文法G'的第j个产
j
生式;
(3)若项目S'→,则置ACTION[k,#]为“接受”,简记为“acc”;
k
(4)若GO(I,A)=I,A为非终结符,则置GOTO[k,A]=j;
kj
(5)分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。
按上述算法构造的含有ACTION和GOTO两部分的分析表,如果每个入口不
含多重定义,则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一
个LR(0)文法,LR(0)文法是无二义的。
DFA的每个项目集(状态)中的项目的不同作用。
三、实验内容
(1)建立一个项目集classProjectSet/
(2)建立stringactionTable[MAX_PRO_SET_NUM+1][MAX_VT_NUM];//ACTION表
.:.
.
stringgotoTable[MAX_PRO_SET_NUM+1][MAX_VT_NUM];//GOTO表
(3)输出分析表voidinput()
四、实验代码与结果
#include<iostream>
#include<string>
#include<fstream>
usingnamespacestd;
#defineMAX_PRO_NUM50
#defineMAX_PRO_SET_NUM20
#defineMAX_P_NUM20
#defineMAX_VT_NUM27
stringvn;//非终结符集
stringvt;//终结符集,包括#
structProject
{//项目的数据结构
charleft;
stringinputed;
stringuninputed;
booloperator==(Projectcmp)
{
if(left==&&inputed==&&uninputed==)
returntrue;
else
returnfalse;
}
};
structGo
{
/*
*GO映射的数据结构
*go[i][j].input=a
*go[i][j].nextProjectSet=2
*表示第i状态的第j条箭弧受a激发到达第2状态
*/
charinput;
intnextProjectSet;
}go[MAX_PRO_SET_NUM][MAX_PRO_NUM];
intgoLength[MAX_PRO_SET_NUM]={0};//goLength[i]是第i状态共有多少条箭弧
structPSet//产生式集合
{
charleft;//产生式左部
stringright;//产生式右部
.:.
.
booloperator==(Projectt)//判断项目是否是由该产生式得到的
{
stringtemp;
if(left!=)
returnfalse;
else
{
if(=="null")
temp=;
elseif(=="null")
temp=;
else
temp=+;
}
if(right==temp)
returntrue;
returnfalse;
}
}pSet[MAX_P_NUM];
intpSetLength=0;//产生式个数
classProjectSet;
structDFA//识别活前缀的DFA的项目集集合
{
ProjectSet*state[MAX_PRO_SET_NUM];
intstateLength;
}aDFA;
classProjectSet//项目集
{
private:
intprojectNum;
Projectpro[MAX_PRO_NUM];
intproLength;
intinclude[MAX_P_NUM];
public:
ProjectSet(Projectin)//由一个项目构造项目集闭包
{
projectNum=;
proLength=1;
for(inti=0;i<MAX_P_NUM;i++)
include[i]=0;
pro[0].left=;
.:.
.
pro[0].inputed=;
pro[0].uninputed=;
for(intj=0;j<proLength;j++)
{
charvn=pro[j].uninputed[0];
if(pro[j].uninputed=="null"||vn>='a'&&vn<='z')
continue;
for(inti=0;i<pSetLength;i++)
{
if(pSet[i].left==vn&&include[i]==0)
{
include[i]=1;
pro[proLength].left=pSet[i].left;
pro[proLength].inputed="null";
pro[proLength].uninputed=pSet[i].right;
proLength++;
}
}
}
}
intgetProjectNum()
{
returnprojectNum;
}
intgetProLength()
{
returnproLength;
}
ProjectgetPro(inti)
{
returnpro[i];
}
};
stringactionTable[MAX_PRO_SET_NUM+1][MAX_VT_NUM];//ACTION表
stringgotoTable[MAX_PRO_SET_NUM+1][MAX_VT_NUM];//GOTO表
voidinput();
.:.
.
intgetActionIndex(chart);
intgetGotoIndex(chart);
stringintToString(intt);
voiddisplay()//显示LR(0)分析表
{
cout<<"\t\t\tACTION\t\t\t\tGOTO"<<endl;
cout<<endl;
for(inti=0;i<+1;i++)
{
if(i>0)
cout<<i-1<<"\t";
else
cout<<"\t";
for(unsignedj=0;j<();j++)
cout<<actionTable[i][j]<<'\t';
for(j=0;j<();j++)
cout<<gotoTable[i][j]<<'\t';
cout<<endl;
}
}
intmain()
{
input();
for(inti=0;i<MAX_PRO_SET_NUM;i++)
[i]=NULL;
=0;
Projectstart;
=pSet[0].left;
="null";
=pSet[0].right;
[0]=newProjectSet(start);
++;
intcurrState=0;//当前分析的项目集
do{
for(inti=0;i<[currState]->getProLength();i++)
{
stringtemp=[currState]->getPro(i).uninputed;
if(temp=="null")//归约项目
continue;
else
.:.
.
{
go[currState][goLength[currState]].input=temp[0];//当前状态currState的第
goLength[currState]条箭弧受uninputed[0]激发
go[currState][goLength[currState]].nextProjectSet=;//默认
到达一个新建的状态
ProjectaProject,t=[currState]->getPro(i);
=;
if(=="null")
=[0];
else
=+[0];
if(()==1)
="null";
else
=(1,());
boolflag=false;
if(aProject==[currState]->getPro(0))//状态到达自身置一条到
达自身的箭弧
{
go[currState][goLength[currState]].nextProjectSet=
[currState]->getProjectNum();
goLength[currState]++;
continue;
}
else
{
for(intiter=0;iter<;iter++)
{
if(aProject==[iter]->getPro(0))//与其他某一状态吻合
置一跳到达该状态的箭弧
{
go[currState][goLength[currState]].nextProjectSet=iter;
goLength[currState]++;
flag=true;
break;
}
}
}
if(flag==false)//均不满足时新建一个状态
{
go[currState][goLength[currState]].nextProjectSet=;
[]=newProjectSet(aProject);
.:.
.
++;
goLength[currState]++;
}
}
}
currState++;
}while(currState!=);//当前分析的项目集是项目集集合的最后一个项目
集时退出循环
/*
*以上,识别活前缀的DFA构造完毕
*以下,构造LR(0)分析表
*/
//ACTION表和GOTO表初始化
for(i=0;i<();i++)
{
actionTable[0][i]=vt[i];
}
for(i=0;i<();i++)
gotoTable[0][i]=vn[i];
//以状态号顺序填表
for(i=0;i<;i++)
{
Projectt=[i]->getPro(0);
if(=="null")//是归约项目
{
if(=='Z'&&[0]==vn[0]&&()==1)//接受状态
Z->S.
{
actionTable[i+1][()-1]="acc";
continue;
}
for(intiter=0;iter<pSetLength;iter++)//扫描产生式以确定用哪一条产生式归
约
{
if(pSet[iter]==[i]->getPro(0))
{
for(unsignedk=0;k<();k++)
{
actionTable[i+1][k]="r"+intToString(iter);
}
.:.
.
}
}
continue;
}
for(intj=0;j<goLength[i];j++)
{
if(go[i][j].input>='a'&&go[i][j].input<='z')//终结符移进
{
intindex=getActionIndex(go[i][j].input);
actionTable[i+1][index]="S"+intToString(go[i][j].nextProjectSet);
}
elseif(go[i][j].input>='A'&&go[i][j].input<='Z')//非终结符跳转
{
intindex=getGotoIndex(go[i][j].input);
gotoTable[i+1][index]=intToString(go[i][j].nextProjectSet);
}
}
}
display();
getchar();
return0;
}
voidinput()
{
charline[20];
charfile[20];
cout<<"请输入文法导入文件的文件名:";
cin>>file;
getchar();
strcat(file,".txt");
ifstreammyFile(file);
inti=0;
(line,28);
vn=line;
(line,28);
vt=line;
(line,20);
while(line[0]!='\0')
{
.:.
.
pSet[i].left=line[0];
charsub[20];
intk=3;
while(line[k]!='\0')
{
sub[k-3]=line[k];
k++;
}
sub[k-3]='\0';
pSet[i].right=string(sub);
pSet[++i].left='\0';
pSetLength++;
(line,20);
}
}
intgetActionIndex(chart)//给出一个终结符返回该终结符在ACTION表中是第几列
{
for(unsignedi=0;i<();i++)
if(actionTable[0][i][0]==t)
returni;
return-1;
}
intgetGotoIndex(chart)//给出一个非终结符返回该非终结符在GOTO表中是第几列
{
for(unsignedi=0;i<();i++)
if(gotoTable[0][i][0]==t)
returni;
return-1;
}
stringintToString(intt)//整型转换成字符串类型
{
stringtemp;
while(t)
{
chararray[2]={'\0'};
array[0]=t%10+48;
temp+=string(array);
t/=10;
}
.:.
.
五、实验心得
在实验的过程中,我遇到的问题很多,主要是关键字的数组声明,最后在我
们的一致商量中我们选择了结构体用起来还比较方便。
总之,我喜欢这样的实验,每一次都让自己能够彻底的投入,然后获得的是
充实和兴奋,同时在每一次的试验中我也感受到了自己的知识欠缺,比如这次,
我基本上又