实验三 LR(1) 分析法
实验学时： 4
实验类型：验证
实验要求：必修
一、实验目的
构造 LR(1) 分析程序，利用它进行语法分析，判断给出的符号串 是否为该文法识别的句子，了解 LR (K)分析方法是严格的从左向右 扫描，和自底向上的语法分析方法。
二、实验内容
对下列文法，用LR( 1)分析法对任意输入的符号串进行分析：(产 生式有误，进行修改 )
( 1 ) E- E+T
( 2) E- E — T( E->T)
( 3) T- T*F
( 4) T- T/F (T->F)
( 5) F- (E)
( 6) F- i
三、实验目的
1、 编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。
2、 如果遇到错误的表达式，应输出错误提示信息。
3、程序输入/输出实例:
输入一以#结束的符号串(包括+—*/ () i#):在此位置输入符号串
输出过程如下：
步骤 状态栈 符号栈 剩余输入串 动作
1 0 # i+i*i#
移进
i+i*i的LR分析过程
步骤
状态栈
符号栈
输入串
动作说明
1
0
#
i+i*i#
ACTION[0,i]=S 5,状态 5 入栈
2
05
#i
+i*i#
r6： F— i 归约,GOTO(0,F)=3入
栈
3
03
#F
+i*i#
r4： T— F 归约,GOTO(0,T)=3 入
栈
4
02
#T
+i*i#
「2： E— T 归约,GOTO(0,E)=1 入
栈
5
01
#E
+i*i#
ACTION[1,+]=S6,状态 6 入栈
6
016
#E+
i*i#
ACTION[6,i]=S 5,状态 5 入栈
7
0165
#E+i
*i#
「6： F— i 归约,GOTO(6,F)=3 入
栈
8
0163
#E+F
*i#
r4： T— F 归约,GOTO(6,T)=9 入
栈
9
0169
#E+T
*i#
ACTION[9,*]=S7,状态 7 入栈
10
01697
#E+T*
i#
ACTION[7,i]=S 5,状态 5 入栈
11
016975
#E+T*i
#
r6：F — i 归约,GOTO(7,F)=10
入栈
12
0169710
#E+T*F
#
r3： T — T*F 归约,GOTO(6,T)=9
入栈
13
0169
#E+T
#
r 1：E — E+T,GOTO(0,E)=1 入栈
14
01
#E
#
Acc :分析成功
实验报告正文的内容：
描述LR(1)语法分析程序的设计思想：
定义项目的一般形式是［A — ? , a ?…a］，这样的一个项目 称为一个LR(k)项目。项目中的a?…a称为它的向前搜索符串
(或展望串)，令K=1,即为LR(1)语法分析程序。在此，重新定义
CLOSURE( I 的算法：
项目集I的闭包CLOSURED构造方法：
I的任何项目都属于 CLOSURE(I)
若项目［A — ?B , a］属于CLOSURE(I) B— 是一个产
生式，那么，对于FIRST( a)中的每个终结符b,如果［B —?
b］原来不在CLOSURE(I中，则把它加进去。
重复执行步骤2,直至CLOSURE(不再增大为止。
GO()的算法保持与LR语法分析程序一样，通过以下方法构造文 法分析表：
动作ACTION和状态转换GOT构造如下：
若项目［A — ?a , b］属于 I k 且 GO(Ik, a) = I j, a 为终 结符，则置 ACTION［k, a］为 “sj ”。
若项目［A — ?, a］属于 Ik,则置 ACTION［k, a］为 “rj ”；
其中假定A— 为文法G的第j个产生式。
若项目[S —S?,#]属于 Ik,则置 ACTION[k, #]为 “ acc”。
若 GO(Ik, A) = I j,则置 GOTO[k, A]=j。
分析表中凡不能用规则1至4填入信息的空白栏均填上“出 错标志”。
当具体面对输入串时，通过查表进行分析该进行何种动作。
程序结构描述：函数调用格式、参数含义、返回值描述、函数功 能均在程序源代码出注释出来，在此不再赘述，详细含义请参照 源代码cpp文件。
详细的算法描述(程序执行流程图)：
总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都 是相同的。
分析表或分析函数，不同的文法分析表将不同，同一个文法采用
的LR分析器不同时，分析表将不同，分析表又可以分为动作表
(ACTION和状态转换(GOTO表两个部分，它们都可用二维数组表 示。
分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
LR分析器由三个部分组成:
LR分析器结构:
转换表用GOTO[, X]=j表示，规定当栈顶状态为i，遇到当前 文法符号为X时应转向状态j , X为终结符或非终结符。
ACTION[i, a]规定了栈顶状态为i时遇到输入符号a应执行。
动作有四种可能：
(1)移进：
action[i ，a]= Sj :状态j移入到状态栈，把a移入到文法符号
栈，其中i,j表示状态号。
⑵归约：
action[i ，a]=rk :当在栈顶形成句柄时，则归约为相应的非终
结符A,即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则 从状态栈和文法符号栈中自顶向下去掉 R个符号，即栈指针SP减去 R,并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修 改指针后的栈顶状态。
⑶接受acc:
当归约到文法符号栈中只剩文法的开始符号 S时，并且输入符号 串已结束即当前输入符是# ,则为分析成功。
报错:
当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报
错，说明输入端不是该文法能接受的符号串
把誦叱分别镶入 符号戟和状态找； 使址菌进列下一个 字符-
分别从栈顶弹岀同个 符号，令x是当斎挨顶 状恋把已和她国曲 先启键入挨中,誓出产 生式A->0.
第
出暑处理
四、实验要求
本程序原本的设计思想与实验二相仿，但由于此种设计思想会 导致程序灵活性大大降低，故对设计思想进行优化，在此，不 在对原程序设计思想进行阐述，仅对改良后的程序设计思想进 行阐述。
该文法的LR(1)分析表:
算术表达式文法的LR分析表
状
态
ACTION
GOTO
i
+
*
(
)
#
E
T
F
0
S
S4
1
2
3
1
Sb
acc
2
「2
S
「2
「2
3
r4
「4
「4
「4
4
S5
S4
8
2
3
5
「6
「6
「6
「6
6
S5
S4
9
3
7
S
s
10
8
Sb
S11
9
r1
S7
r 1
r 1
10
「3
r 3
r 3
r 3
11
「5
r 5
r 5
r 5
本程序根据给出的LR(1)文法分析表，构造string 类的
actio n[12] [6]二｛"S5","0","0","S4","0","0",
cl
#E
解 Ki
oa AF
32 ttT
ai uf
316 itE*
UlbS tth+i
3163 ttE+F
3169 1tE*T
31697 #E *T"
ISlb97b ?E+l*i WE+I*F
31G9 ttE+r
血Rd〉吩'^fy K XX KXKJt KM kMKJtKMHHKMKXKMKM
p-XE>
P->1
E ? mb 理 upt bi: xe it mt at Pt?t at xj< ■ x
T->F
f亠”咄
53
T 巳' stj cy^PFT 痢译游莹 E? ebug^fciH 1. exe
B 1 2 a
2;3 4u ￡ ￥859 1111
同I
諭人字符串
状态栈持号栈 吐 X a
14 31
杲否维续労析
務％段奮分析
*i*it +i*i* +i*il +i*dl ±*itt *ifl *ifl *iH
Iff n tt M a
动作说明
ACTION（a.il^SS.状态 5入栈 M 土 P-'zL 归约，CoT0<erF>=3 M; r4：T-汕归约，GotD<0,T>^A： r2：E->TiH约* Gorn<0,E>^L Af fltniohiri,
fiClIONtt, rb:F->i归
M：T->fE^? GoIaC6,T>^Xtl flC7lON[?,*]=G7,|^
昭：F-〉i片约，GorcC7,F）=llJ/ r3：T-M*F归约.GDTa<6.T>=9 rl =E-3E*T归纹I, GoTo<B,E>-1 0 分崭成功
*】=K「狀态咅几核 约,CaTc<6,F>^AtS
}
}
H "DWtucypPT舗涌原②Debug冋肚比儁事
本奈析文法产生式为
￡->E+T
E >T
r-M*^
T->P
P-XE>
卩一》丄
比 <丄)吩入彳斤H ?:M J< U K K tx It 理 K H X 比?X 直 ML!M hk It jc ml
輸入字符爭
Cl>
歩囁
状态栈
椅号挨
i
a
tt
34
tt<
B4b
U<i
343
tt<F
B42
tt<T
348
#<E
94811
tt<E>
33
ttF
32
ttT
is
31
ME
床否継续労析段或邂
密进q如下分析
±>fl
>■
>t
>t
A
A
M
41
:M Jt-jtE-覽耳诅JW Mr光-■ JfrJl捕机MrM擡 址民■: 动作说明
nC7I0Kt4, rb:F-〉i归 m=t->f0|5； ra 汨-yrjg药， AClIONia,>]-GliR 状态丄 1■入楞 rh：F-XEJ归约，Sot旗kLF〉=H入桟 r4：T->FB§, GorD<0RT>=2人桂 1'2 TE->Tlji3约，GorD<B,E>-lX： ^
乂】=K4”；犬态4九戋 状态&入栈 约，Gotn<l,F>-3^\ Gorn<4,T>=2A GDtn<4J1LE>=8/
同 S3
状态栈
符号栈
U<T tt<E
KE) HP
MT GE
942
EM8
M811
&3
&2
Ul
I?入字符串
Ci>*O
龍烹
±)*<>B >*<>1 >*<>? >*<>t >*<>1 *<># *<># *C Ait
<>W
也:E」〉T归约，入枝 ftC7IOH[9,>l=Sll,状态“入栈 f5：F-XE>归约"GoTo<0-F>-3X4^ MTi〉F r2 : E-XT
IV
星香继续分析/血继缠
动作说明 —\蛀
fiC7 IOKtftAl弋乙吠态竝入啖 fiCTI0Nt4,l)=SS^ 态 5 入楞 r6：F-》i归约,GoIo<4,F;=3A ft r4：T->F归约.00?0<4-1>=2入】号 诅汨-yri口约，GorD<4,E>-BAfJl AG7lOHta,> 1-Sll,3|^^li 入栈 rb :F-XE>lJ3釣.Golo<U,F>=3X-tS r4：T-M归药.Gorij<0RT>=2人栈 fiCliONt2,?)=G?,H;态”找 AG7IDR：7,< Z*,：￥态小
J 34 U<
345 tt<i
343 tt<F
* 342 M<T
6 34S U<￡
I? k!4?ll ft<E>
B 33 ttF
9 盟 ttT
LB 32 ■? ttT"
S1F1*O1*
皋告绅纯弈析畀或翩
GoTa<0 如“<叫”逹入* Guru<0,E>-￡Af 分祈加J
回
S3
r
en gth()-3;
for(i nt j=O;j<N;j++){t(O)v<")二";
(Productio n[i-1].at(0));t(0)=='S'){
actio n[i][t].erase(0,1);
_str()),s);_str())
将 action[i][t] 转换为整型
，将action[i][t].insert(0,"S");t(0)=='r'){
，将
action[i][t].erase(0,1);_str()),s);_str())
action[i][t] 转换为整型
action[i][t].insert(0,"r");// 将 r 添加回
action[i][t]
}
}
else if(action[i][t]=="0"){
cout<<"\tError"<<endl;
break;
}
else if(action[i][t]=="acc"){
Output(s);
cout<<"acc"<<"\t 分析成功 "<<endl;
break;
}
}
else if(flag==false)
break;
int main(){string s;cout<<"************************LR(1)分析
int main(){
string s;
cout<<"
***********************
*LR(1)
分析
<<endl;
cout<<" 本分析文法产生式为 "<<endl;
for(int j=0;j<6;j++)
cout<<Production[j]<<endl;
cout<<"************************LR(1)分析
cout<<"
***********************
*LR(1)
分析
<<endl;*************************H
<<endl;
char T;
do{
cout<<" 输入字符串 "<<endl;
cin>>s;// 输入要分析的字符串
cout<<"************************现进行如下分析
cout<<"
************************
现进行如下分析
<<endl;*************************H
<<endl;
coutvv"步骤"vv"\t"vv" 状态栈"vv"\t"vv" 符号栈"vv"\t"vv" 剩 余输入串 "<<"\t"<<" 动作说明 "<<endl;
Analyse(s);
count=0;// 记录当前进行处理的输入字符串字符位置
line=1;// 记录处理的步骤数
stacktd="#";
StatusNumber=1;
}
}
}
}
while(!()){
();
}
while(!()){
();
}
cout<<" 是否继续分析 ,Y 或 y 继续 "<<endl; cin>>T;
}while(T=='y'||T=='Y');
return 0;
推荐访问:实验报告 实验 代码 报告 LR(1)实验报告(附代码)