SLR1文法分析实验报告Word文件下载.docx
《SLR1文法分析实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《SLR1文法分析实验报告Word文件下载.docx（40页珍藏版）》请在冰点文库上搜索。
Closure&
make_item
（）
dfs（const
x）
make_first
append（conststring&
stri
conststring
str2
）
_check（constvector<
int
>
id,conststringstr
make_follow
'
make_set
make_V（）
make_cmp
（vector
<
WF>
cmpi
inti,charch）
make_go（）
make_table
print（stringsi
string
s2,strings3,
string
s4
s6,
strings7
stringget_steps
（int
x）
stringget_stk
T>
stk）
};
strings5,
stringget_shift
（WF&
temp）
voidanalyse（stringsrc）
2.2算法思想
SLF文法构造分析表的主要思想：
许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决。
解决冲突的方法是分析所有含A和B的句型，考察集合FOLLOW（A和FOLLOW（B）如果这两
个集合不相交，而且也不包含b，那么当状态I面临输入符号a时，我们可以使用如下策略：
若a=b,则移进。
若a€FOLLOW（A）,则用产生式A^a进行归约;
若a€FOLLOW（B,则用产生式B^a进行归约;
此外，报错*SLR的基本算法：
假定LR（0规范族的一个项目集I中含有m个移进项目
A1Ta?
a131,A2fa?
a2B2,…，Am^a?
am3m;
同时含有n个归约项目
B1^a?
B2fa?
•••,B3^a
如果集合{a1,…,am},FOLLOW（B1,…，FOLLOW（Bn两两不相交（包括不得有两个FOLLOW
集合有#）,则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1个集合中
的哪个集合而活的解决：
若a是某个ai,i=1,2,…,m,则移进。
若a€FOLLOW（Bi）i=1,2,…,m，则用产生式Bfa进行归约;
此外，报错
这种冲突的解决方法叫做SLR（1解决办法。
SLF语法分析表的构造方法：
首先把G拓广为G'
对G'
构造LR（O项目集规范族C和活前缀识别自动机的状态转换函
数GO。
函数ACTION和GOTO可按如下方法构造：
若项目A~a?
bB属于Ik,GO（lk,a）=lj,a为终结符，置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”；
若项目A^a?
属于Ik,那么，对任何非终结符a,a€FOLLOW（A）,置ACTION[k,a]为“用产
生式A^a进行归约”，简记为“rj”；
其中，假定A^a为文法G'
的第j个产生式
若项目S'
tS?
属于Ik,则置ACTION[k,#]为可“接受”，简记为“acc”；
若GO（Ik,A）=lj,A为非终结符，则置GOTO[k,A]=j;
分析表中凡不能用规则1至4填入信息的空白格均填上“出错标志”。
语法分析器的初始状态是包含S'
t?
S的项目集合的状态
SLR解决的冲突只是移进-规约冲突和规约-规约冲突
3主要功能模块流程图
3.1主函数功能流程图
图3.1程序主要流程
4系统测试
7
S->
E
沌十T
K->
E+T"
TE->
T
T->
T+F
T*F
F
F-》㈤
F->
（E）
1
图4.1输入
Ir«
*7\n4X
$Eback:
Oid:
O
E$back:
0id：
l
E->
$E+TbackILid:
2
卜沌$+Tback:
Lid:
3
£
->
E+$Tbackilid:
4
E+T$back:
5
$Tback:
2id:
T$back:
r->
$rr*Fback:
3id:
B
Fback:
3id;
9
T~back:
10
W$back:
ll
$Fback:
4id:
12
K$back:
13
$（E）back:
5id:
14
（$E）back:
15
tejiback:
5id：
10
^>
CE）$back:
5id:
17
$iback:
6id:
18
F—>
i$back:
19
图4.2项目表
FIRST®
={（ni}
FIRST（F）二{（,il
FIRSTCS）-{（,il
FIRST（T）-[Gil
图4.3FIRST集
牡*芈牢宋来农芈舸ki«
k*Hi*ROLLO叩集啡=1=来*芈*半壮來芈來芈琳未朮
FOLLOV®
）-优），十}
FOLLOW（F>
=
FOLLOW（S）={ft}
FOLLOV（T）=怕,），叽十}
图4.4FOLLOW集
cl^^ure-lO
$E-^T
ST
$（E）
F-〉$i
$E
T-〉$F
t->
$T*r
cLosure-Il
e->
je+tE->
JT
$i
（?
E）
T-）JF
$T+F
E$+T
E$
closure-13
T-）F$
closure-14
E-〉T$
T-〉T$*F
closure-I5
i$
closure-IO
E$-HT
F-XEJ）
■?
Losure-I7
E+$T
F->
S（E）
F_〉$i
JF
$T*F
closure-18
$（E）
F-》$i
T+$F
cLosure-19
F-〉（E）$
closur2-110
E-）E+T$
T$+F
closure-ill
T*F$
图4.5CLOSURE表
EDGE
io—c—it
IO-E—12
10—F-—13
It>
-T—14
10—1—15
IL—C—Il
it—r—13
IL—T—14
11—1—15
11—I—16
12—---17
14—^—18
I&
--h—17
16—）—19
IT—C—Il
IT—13
17—1—15
17—T—no
19—C—T1
13—1—15
is—r—in
no—*—ia
图4.6EDGE表
片町去•
I
J
*1
1卩
15
-
n
厂
13
551
si
6
S5
a；
ac-c
JU
IN
茁
斗
H2
SH
K2
R2
HO
K&
RC
b
阳
Si
11
8S
R5
昉
Et5
ID
R1
El
Etl
H3
舲1
R3
图4.7LR（0）表
StkOE
IuL_S'
心
-.-U&
rar.ioji
.；
Livy-Gt：
）ck
ftCTlDi
CCTO
shift
Io
SI
|乳
UiJHA
bl
的
■
Iflfti
vi>
+jB
Ted-uee^F->
iJ
15
R6
iw
*i>
+iff
rectueE（T一J
1013
■t
*1>
+lir
ill
her-
）*iff
丄抽
=5
1«
Cr*i
蓝■du"
（卩一》
|Q14^
Jll
：
htr*F
"
田內仃一江*沪
lUJ31；
叮
|i!
（T
rBchice（E~>
T）
1014
V2
+itf
low
I-J
1畑
+1F
redlU£
!
ir（F->
{tl）
|O1«
IffF
+if
radsu^r
|03
V1
IfT
•”iU
TRI^JCF1；
卫一>
h4
砒
?
-4
Ike
-if
sM£
t
|02
E7
_h
ifl
loir
注
HhG
IT
二BjqhlQU（f~>
i）
iazra
kb
juz*f
q
IO2T3
Ri
1」
ItfF*T
«
匸日ckiE旧+T）
10271o
Fl
血
H
Accept
iCC
图4.8文法分析步骤
5结论
LR分析法是一种自下而上进行规范归约的语法分析方法。
这里L是指从左到右扫描输入符号串。
R是指构造最右推倒的逆工程。
这种分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。
附录程序源码清单
#inelude<
iostream>
cstdio>
#include《algorithm〉
estring>
eetype>
veetor>
string>
queue>
map>
set>
#include<
sstream>
#defineMAX507
〃#defineDEBUG
usingnamespacestd;
#pragmawarning（disable:
4996）
{
public:
stringleft,right;
intback;
intid;
WF（chars1[],chars2[],intx,inty）
left=s1;
right=s2;
back=x;
id=y;
WF（conststring
1&
s1
s2,intx
inty）
left
=s1;
right
=s2;
back
=x;
}
（const
if（left==a.
left）
return
a.right
a.left
（left
==a.left
）&
（right=
=a.right）;
print（）
printf
（"
%s->
%s\n"
left.c_str（）,
right.c_str
（））；
public
vector
element;
%-15s%-15s\n"
"
str.c_
str（））；
for（inti=0;
ivelement.size（）;
i++）
element[i].print（）;
returnfalse
booloperator==（constClosure&
a）const{
if（a.element.size（）!
=element.size（））
for（inti=0;
i<
a.element.size（）;
i++）if（element[i]==a.element[i]）continueelsereturnfalse;
returntrue;
structContent
inttype;
intnum;
stringout;
Content（）{type=-1;
Content（inta,intb）
:
type（a）,num（b）{}
vector<
wf;
map<
vector
dic;
VN_set
bool>
vis;
stringstart
="
S"
Closure>
collection
items
charCH='
$'
;
intgo[MAX][MAX];
intto[MAX];
char>
V;
boolused[MAX];
Contentaction[MAX][MAX];
intGoto[MAX][MAX];
mapvstring,set<
first
follow
voidmake
item（）
memset
（to，-1,sizeof
（-1））;
for（int
i=0;
wf.
size
（）;
i++）
VNset
[wf[i].left
].
push_back（i）;
for（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
#ifdefDEBUG
puts（"
项目表——
items.size（）
.size
printf（"
%sback:
%did:
%d\n"
items[i].left
items[i].right.c_str（）,items[i].back,items[i].
（）））;
"
）;
；
_str（）,
id）;
break
puts（”
#endif
voiddfs（conststring&
if（vis[x]）return;
vis[x]=1;
int>
id=VN_set[x];
i<
id.size（）;
i
++）
left
=wf[id[i]].
right
for
（intj
j
.length
j++）
if（isupper
（right
[j]））
dfs
.substr
（j,1））;
set
char
temp
=first
[right
.substr（j,1）];
iteratorit
=temp
.begin（）;
flag
=true;
（;
it
=temp.
end（）;
it++）
if（*it=
='
~'
）flag
=false;
first
[left
].insert
（*it
if（flag）break
first[left].insert
（right[j]）;
else
printf（"
FIRST（%s）={"
it->
first.c_str
set<
temp=it
second;
iteratorit1
=temp.begin（
boolflag=false;
for（;
it1!
=temp.end
（）；
it1++）
puts
}"
）；
voidmake_first（）
append
（const
str1
const
str2）
vchar
from
=follow
[str1
];
to=follow
[str2];
=from
=
from.
e
升级会员 