例, 文法
S’→E
E→E+T│T
T→T*F│F
F→(E)│i
I0=closure({S’→ ?S})
S’??E,E??E+T,E??T,T??T*F,T??F,F??(E),F ??i
I1=go(I0,E)
S’?E?,E?E?+T 移进 -归约冲突
I2=go(I0,T)
E?T?,T?T?*F 移进 -归约冲突
I3=go(I0,F)
T?F?
I4=go(I0,( )
F?(?E),E??E+T,E??T,T??T*F,T??F,F??(E),F ??i
I5=go(I0,i)
F ?i?
I6=go(I1,+)
E?E+?T,T??T*F,T??F,F??(E),F ??i
I7=go(I2,*)
T?T*?F,F??(E),F ??i
I8=go(I4,E)
F?(E?),E?E?+T
I9=go(I6,T)
E?E+T?,T?T?*F 移进 -归约冲突
I10=go(I7,F)
T?T*F?
I11=go(I8,) )
F?(E)?
四, SLR分析表的构造
1,SLR方法
当某个项目集形如
I={X???b?,A???,B???}时,出现了移进 -归
约冲突和归约 -归约冲突,可用如下方法解决,该
方法称为 SLR方法 。
a是当前输入符号,
当 {b}?FOLLOW(A) ? FOLLOW(B)=Φ时
(1)a=b,则移进输入符 a;
(2)a?FOLLOW(A),则用 A→α 归约 ;
(3)a?FOLLOW(B),则用 B→α 归约 ;
(4)此外出错。
2,SLR分析表的构造
(1)C={I0,I1,…,I n},Ii对应状态 i,
I0=closure({S’??S})为唯一初态 ;
(2)对每个 Ii,
? 若 A???a??Ii,且 go(Ii,a)=Ij,则 action[i,a]=sj;
? 若 A????Ii,A??为第 j个产生式,
则 ?b?FOLLOW(A),action[i,b]=rj;
? 若 S’?S??Ii,则 action[i,$]=acc;
(3)若 go(Ii,A)=Ij,则 goto[i,A]=j;
(4)凡不能用规则 (2),(3)登记的表项均为“错误”。
若由该方法构造的分析表,不含多重入
口,则该分析表称为 SLR分析表,相应文法
G称为 SLR(1)文法。
LR分析表
状
态
0
1
2
3
4
5
6
7
8
9
10
11
action goto
i + * ( ) $ E T F
s5 s4 1 2 3
s6 acc
r2 s7 r2 r2
r4 r4 r4 r4
s5 s4 8 2 3
r6 r6 r6 r6
s5 s4 9 3
s5 s4 10
s6 s11
r1 s7 r1 r1
r3 r3 r3 r3
r5 r5 r5 r5
五, 关于二义文法
例 1,G(E) E→E+E|E*E|(E)|i
拓广文法,
(0)S’→E
(1)E→E+E
(2)E→E*E
(3)E→(E)
(4)E→i
I0=closure({S’→ ?E})
S’??E,E??E+E,E??E*E,E??(E),E ??i
I1=go(I0,E)
S’?E?,E?E?+E,E?E?*E 移进 -归约冲突
I2=go(I0,( )
E?(?E),E??E+E,E??E*E,E??(E),E ??i
I3=go(I0,i)
E?i?
I4=go(I1,+)
E?E+?E,E??E+E,E??E*E,E??(E),E ??i
I5=go(I1,*)
E?E*?E,E??E+E,E??E*E,E??(E),E ??i
I6=go(I2,E)
E?(E?),E?E?+E,E?E?*E
I7=go(I4,E)
E?E+E?,E?E?+E,E?E?*E 移进 -归约冲突
I8=go(I5,E)
E?E*E?,E?E?+E,E?E?*E 移进 -归约冲突
I9=go(I6,) )
E?(E)?
例 2,G(S) S→iSeS|iS|a
拓广文法,
(0)S’→S
(1)S→iSeS
(2)S→iS
(3)S→i
I0=closure({S’→ ?S})
S’??S,S??iSeS,S??iS,S??a
I1=go(I0,S)
S’?S?
I2=go(I0,i)
S?i?SeS,S?i?S,S??iSeS,S??iS,S??a
I3=go(I0,a)
S?a?
I4=go(I2,S)
S?iS?eS,S?iS? 移进 -归约冲突
I5=go(I4,e)
S?iSe?S,S??iSeS,S??iS,S??a
I6=go(I5,S)
S?iSeS?
第四节 LEX和 YACC简介
一, LEX
LEX是一个描述词法分析器的语言,一
个词法分析器的 LEX程序由一组正规式
以及与每个正规式相应的一个动作组成。
1,LEX编译系统的组成
LEX编译程序 LEX源程序 词法分析器 L
词法分析器 L 输入串 单词符号串
2,语言 LEX的一般描述
一个 LEX源程序主要包括两部分, 辅
助定义式、识别规则。
?辅助定义式
D1?R1
D2?R2
……
Dn?Rn
其中,每个 Ri是一个正规式,Di是代表这个正规式
的简名,而且在 Ri中只允许出现字母表 ?中的字
符和前面已定义的简名 D1,D2,…,D i-1。
?识别规则
P1 {A1}
P2 {A2}
… …
Pm {Am}
其中,每个 Pi是一个正规式,称为词形。 Pi是
??{D1,D2,…,D n}上的一个正规式 ; 每个 Ai是一
小段程序代码,在识别出词形为 Pi的单词之后,
词法分析器所应采取的动作。
二, YACC
输入 YACC LALR(1)分析表
其中,输入为, 文法、优先级、结合性等
输入串 控制程序 分析表 输出
第五章习题 (必做题 ),
5-5,5-8(a),5-12(a)(b),5-13