SLR1文法分析实验报告.docx
《SLR1文法分析实验报告.docx》由会员分享，可在线阅读，更多相关《SLR1文法分析实验报告.docx（36页珍藏版）》请在冰点文库上搜索。
SLR1文法分析实验报告
SLR
（1）文法分析实验报告
《编译原理》课程设计报告
—SLR
（1）分析的实现
学院计算机科学与技术
专业计算机科学与技术
学号
学生姓名
指导教师姓名
2015年12月26日
对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称这种分析方法为简单的LR
（1）分析法，用SLR
（1）表示。
2算法的基本思想
2.1主要功能函数
classWF
{
WF（chars1[],chars2[],intx,inty）
WF（conststring&s1,conststring&s2,intx,inty）
booloperator<（constWF&a）const
booloperator==（constWF&a）const
voidprint（）
};
classClosure
{
voidprint（stringstr）
booloperator==（constClosure&a）const
};
voidmake_item（）
voiddfs（conststring&x）
voidmake_first（）
voidappend（conststring&str1,conststring&str2）
bool_check（constvector&id,conststringstr）
voidmake_follow（）
voidmake_set（）
voidmake_V（）
voidmake_cmp（vector&cmp1,inti,charch）
voidmake_go（）
voidmake_table（）
voidprint（strings1,strings2,strings3,strings4,strings5,strings6,strings7）
stringget_steps（intx）
stringget_stk（vectorstk）
stringget_shift（WF&temp）
voidanalyse（stringsrc）
2.2算法思想
SLR文法构造分析表的主要思想：
许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决。
解决冲突的方法：
解决冲突的方法是分析所有含A和B的句型，考察集合FOLLOW（A）和FOLLOW（B），如果这两个集合不相交，而且也不包含b，那么当状态I面临输入符号a时，我们可以使用如下策略：
若a=b，则移进。
若a∈FOLLOW（A），则用产生式A→α进行归约；
若a∈FOLLOW（B），则用产生式B→α进行归约；
此外，报错*SLR的基本算法：
假定LR（0）规范族的一个项目集I中含有m个移进项目
A1→α•a1β1，A2→α•a2β2，…，Am→α•amβm；
同时含有n个归约项目
B1→α•，B2→α•，…，B3→α•，
如果集合{a1,…,am}，FOLLOW（B1），…，FOLLOW（Bn）两两不相交（包括不得有两个FOLLOW集合有#），则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1个集合中的哪个集合而活的解决：
若a是某个ai，i=1,2,…,m，则移进。
若a∈FOLLOW（Bi），i=1,2,…,m，则用产生式Bi→α进行归约；
此外，报错
这种冲突的解决方法叫做SLR
（1）解决办法。
SLR语法分析表的构造方法：
首先把G拓广为G’，对G’构造LR（0）项目集规范族C和活前缀识别自动机的状态转换函数GO。
函数ACTION和GOTO可按如下方法构造：
若项目A→α•bβ属于Ik，GO（Ik,a）=Ij,a为终结符，置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”；
若项目A→α•属于Ik，那么，对任何非终结符a，a∈FOLLOW（A），置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”；其中，假定A→α为文法G’的第j个产生式
若项目S’→S•属于Ik，则置ACTION[k,#]为可“接受”，简记为“acc”；
若GO（Ik,A）=Ij，A为非终结符，则置GOTO[k,A]=j；
分析表中凡不能用规则1至4填入信息的空白格均填上“出错标志”。
语法分析器的初始状态是包含S’→•S的项目集合的状态
SLR解决的冲突只是移进-规约冲突和规约-规约冲突
3主要功能模块流程图
3.1主函数功能流程图
退出程序，并告知用户分析结果
图3.1程序主要流程
4系统测试
图4.1输入
图4.2项目表
图4.3FIRST集
图4.4FOLLOW集
图4.5CLOSURE表
图4.6EDGE表
图4.7LR（0）表
图4.8文法分析步骤
5结论
LR分析法是一种自下而上进行规范归约的语法分析方法。
这里L是指从左到右扫描输入符号串。
R是指构造最右推倒的逆工程。
这种分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。
附录程序源码清单
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#defineMAX507
//#defineDEBUG
usingnamespacestd;
#pragmawarning（disable:
4996）
classWF
{
public:
stringleft,right;
intback;
intid;
WF（chars1[],chars2[],intx,inty）
{
left=s1;
right=s2;
back=x;
id=y;
}
WF（conststring&s1,conststring&s2,intx,inty）
{
left=s1;
right=s2;
back=x;
id=y;
}
booloperator<（constWF&a）const
{
if（left==a.left）
returnrightreturnleft}
booloperator==（constWF&a）const
{
return（left==a.left）&&（right==a.right）;
}
voidprint（）
{
printf（"%s->%s\n",left.c_str（）,right.c_str（））;
}
};
classClosure
{
public:
vectorelement;
voidprint（stringstr）
{
printf（"%-15s%-15s\n","",str.c_str（））;
for（inti=0;ielement[i].print（）;
}
booloperator==（constClosure&a）const
{
if（a.element.size（）!
=element.size（））returnfalse;
for（inti=0;iif（element[i]==a.element[i]）continue;
elsereturnfalse;
returntrue;
}
};
structContent
{
inttype;
intnum;
stringout;
Content（）{type=-1;}
Content（inta,intb）
:
type（a）,num（b）{}
};
vectorwf;
map>dic;
map>VN_set;
mapvis;
stringstart="S";
vectorcollection;
vectoritems;
charCH='$';
intgo[MAX][MAX];
intto[MAX];
vectorV;
boolused[MAX];
Contentaction[MAX][MAX];
intGoto[MAX][MAX];
map>first;
map>follow;
voidmake_item（）
{
memset（to,-1,sizeof（-1））;
for（inti=0;iVN_set[wf[i].left].push_back（i）;
for（inti=0;ifor（intj=0;j<=wf[i].right.length（）;j++）
{
stringtemp=wf[i].right;
temp.insert（temp.begin（）+j,CH）;
dic[wf[i].left].push_back（items.size（））;
if（j）
to[items.size（）-1]=items.size（）;
items.push_back（WF（wf[i].left,temp,i,items.size（）））;
}
#ifdefDEBUG
puts（"-------------------------项目表-------------------------"）;
for（inti=0;iprintf（"%s->%sback:
%did:
%d\n",items[i].left.c_str（）,items[i].right.c_str（）,items[i].back,items[i].id）;
puts（"--------------------------------------------------------"）;
#endif
}
voiddfs（conststring&x）
{
if（vis[x]）return;
vis[x]=1;
vector&id=VN_set[x];
for（inti=0;i{
string&left=wf[id[i]].left;
string&right=wf[id[i]].right;
for（intj=0;jif（isupper（right[j]））
{
dfs（right.substr（j,1））;
set&temp=first[right.substr（j,1）];
set:
:
iteratorit=temp.begin（）;
boolflag=true;
for（;it!
=temp.end（）;it++）
{
if（*it=='~'）flag=false;
first[left].insert（*it）;
}
if（flag）break;
}
else
{
first[left].insert（right[j]）;
break;
}
}
}
voidmake_first（）
{
vis.clear（）;
map>:
:
iteratorit2=dic.begin（）;
for（;it2!
=dic.end（）;it2++）
if（vis[it2->first]）continue;
elsedfs（it2->first）;
#ifdefDEBUG
puts（"****************FIRST集***************************"）;
map>:
:
iteratorit=first.begin（）;
for（;it!
=first.end（）;it++）
{
printf（"FIRST（%s）={",it->first.c_str（））;
set&temp=it->second;
set:
:
iteratorit1=temp.begin（）;
boolflag=false;
for（;it1!
=temp.end（）;it1++）
{
if（flag）printf（","）;
printf（"%c",*it1）;
flag=true;
}
puts（"}"）;
}
#endif
}
voidappend（conststring&str1,conststring&str2）
{
set&from=follow[str1];
set&to=follow[str2];
set:
:
iteratorit=from.begin（）;
for（;it!
=from.end（）;it++）
to.insert（*it）;
}
bool_check（constvector&id,conststringstr）
{
for（inti=0;i{
intx=id[i];
if（wf[x].right==str）returntrue;
}
returnfalse;
}
voidmake_follow（）
{
while（true）
{
boolgoon=false;
map>:
:
iteratorit2=VN_set.begin（）;
for（;it2!
=VN_set.end（）;it2++）
{
vector&id=it2->second;
for（inti=0;i{
boolflag=true;
WF&tt=wf[id[i]];
string&left=tt.left;
conststring&right=tt.right;
for（intj=right.length（）-1;j>=0;j--）
if（isupper（right[j]））
{
if（flag）
{
inttx=follow[right.substr（j,1）].size（）;
append（left,right.substr（j,1））;
inttx1=follow[right.substr（j,1）].size（）;
if（tx1>tx）goon=true;
if（_check（id,"~"））
flag=false;
}
for（intk=j+1;kif（isupper（right[k]））
{
stringidd=right.substr（k,1）;
set&from=first[idd];
set&to=follow[right.substr（j,1）];
set:
:
iteratorit1=from.begin（）;
inttx=follow[right.substr（j,1）].size（）;
for（;it1!
=from.end（）;it1++）
if（*it1!
='~'）
to.insert（*it1）;
inttx1=follow[right.substr（j,1）].size（）;
if（tx1>tx）goon=true;
if（_check（id,"~"））
break;
}
else
{
inttx=follow[right.substr（j,1）].size（）;
follow[right.substr（j,1）].insert（right[k]）;
inttx1=follow[right.substr（j,1）].size（）;
if（tx1>tx）goon=true;
break;
}
}
elseflag=false;
}
}
if（!
goon）break;
}
#ifdefDEBUG
puts（"***************FOLLOW集*******************"）;
map>:
:
iteratorit=follow.begin（）;
for（;it!
=follow.end（）;it++）
{
printf（"FOLLOW（%s）={",it->first.c_str（））;
set&temp=it->second;
temp.insert（'#'）;
set:
:
iteratorit1=temp.begin（）;
boolflag=false;
for（;it1!
=temp.end（）;it1++）
{
if（flag）printf（","）;
printf（"%c",*it1）;
flag=true;
}
puts（"}"）;
}
#endif
}
voidmake_set（）
{
boolhas[MAX];
for（inti=0;iif（items[i].left[0]=='S'&&items[i].right[0]==CH）
{
Closuretemp;
string&str=items[i].right;
vector&element=temp.element;
element.push_back（items[i]）;
size_tx=0;
for（x=0;xif（str[x]==CH）
break;
memset（has,0,sizeof（has））;
has[i]=1;
if（x!
=str.length（）-1）
{
queueq;
q.push（str.substr（x+1,1））;
while（!
q.empty（））
{
stringu=q.front（）;
q.pop（）;
vector&id=dic[u];
for（size_tj=0;j{
inttx=id[j];
if（items[tx].right[0]==CH）
{
if（has[tx]）continue;
has[tx]=1;
if（isupper（items[tx].right[1]））
q.push（items[tx].right.substr（1,1））;
element.push_back（items[tx]）;
}
}
}
}
collection.push_back（temp）;
}
for（size_ti=0;i{
maptemp;
for（size_tj=0;j{
stringstr=collection[i].element[j].right;
size_tx=0;
for（;xif（str[x]==CH）break;
if（x==str.length（）-1）
continue;
inty=str[x+1];
intii;
str.erase（str.begin（）+x）;
str.insert（str.begin（）+x+1,CH）;
WFcmp=WF（collection[i].element[j].left,str,-1,-1）;
for（size_tk=0;kif（items[k]==cmp）
{
ii=k;
break;
}
memset（has,0,sizeof（has））;
vector&element=temp[y].element;
element.push_back（items[ii]）;
has[ii]=1;
x++;
if（x!
=str.length（）-1）
{
queueq;
q.push（str.substr（x+1,1））;
while（!
q.empty（））
{
stringu=q.fr
升级会员 