5,优先关系表的构造
(1)FIRSTVT集
FIRSTVT(P)={a|P?a…,或 P?Qa…,a ?VT,Q ?VN}
?若 P?a… 或 P?Qa…,则 a?FIRSTVT(P);
?若 P?Q…,则 FIRSTVT(Q)?FIRSTVT(P);
直至 FIRSTVT(P)不再增大。
+ +
(2)LASTVT集
LASTVT(P)={a|P?...a,或 P?…aQ,a ?VT,Q ?VN}
?若 P?...a或 P?…aQ,则 a?LASTVT(P);
?若 P?...Q,则 LASTVT(Q)?LASTVT(P);
直至 LASTVT(P)不再增大。
+ +
例 G(E) E→E+T│T
T→T*F│F
F→(E) │i
E
T
F
FIRSTVT LASTVT
( i + *
( i
) i + *
) i *
) i
( i *
(3)构造优先关系表的算法
FOR 每条产生式 P?X1X2…X n DO
FOR i:=1 TO n-1 DO
BEGIN
IF Xi和 Xi+1均为终结符 THEN Xi= Xi+1;
IF i<=n-2 且 Xi和 Xi+2均为终结符 但 Xi?VN
THEN Xi=Xi+2;
IF Xi?VT,Xi+1?VN
THEN ?a?FIRSTVT(Xi+1) Xi<a;
IF Xi?VN,Xi+1?VT
THEN ?a?LASTVT(Xi) a>Xi+1
END;
例 G(E) E→E+T│T
T→T*F│F
F→(E) │i
E
T
F
FIRSTVT LASTVT
( i + *
( i
) i + *
) i *
) i
( i *
考察 E→E+T 中的 E和 +, +和 T
考察 T→T*F 中的 T和 *, *和 F
考察 F→(E) 中的 (和 E, (和 ), E和 )
+
+
*
*
i
i
(
(
)
)
$
$
>
>
>
<
>
<
<
<
<
>
>
>
<
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
=
=
算符优先关系表
二, LR分析法
1,LR(K) 分析法
自底向上的 LR分析法是指从左向右扫描
输入串,每次分析由分析栈中符号及向前
搜索 K个输入符号,以确定作为产生式右部
的短语 (句柄 )是否已在分析栈的栈顶形成,
从而决定应采取的动作 。 这种分析方法称
为 LR(K)分析法 。 一般只考虑 K?1的情况 。
其组成为,分析栈,控制程序,分析表,输入串
输入串
分析栈
驱动程序 输出
action goto
分析表
s0
,
,
,
sm-1
sm
a1 ai $,..,.,
2,分析栈
存放状态 ;初始时,置初始状态 s0;栈里的
每一状态概括了从分析开始到某一时刻
已进行的分析工作。
3,分析表
由 action[s,a]和 goto[s,x]两个子表组成。
(1)action[s,a]定义了在状态 s下,当前输入符号为
a时应采取的分析动作, 移进,归约,接受,出错。
(2)goto表是一个状态及非终结符的二维矩阵,
goto[s,x]定义了在状态 s下,面对文法符号 x时的
状态转换。
例 G0(E)
(1)E→E+T
(2)E→T
(3)T→T*F
(4)T→F
(5)F→(E)
(6)F→i
的 LR分析表如后
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
4,控制程序的工作
据 action[s,a]进行,
(1)若 action[s,a]=sj,则将状态 j推入栈顶,输入指针指向
下一输入符号 ;
(2)若 action[s,a]=rj,则按第 j个产生式 A??归约,设 |?|=t,
应在分析栈栈顶上托 t个状态出栈,呈现栈顶的状态设
为 si,则根据 si及归约后的非终结符 A,查 goto表,
goto[si,A]=j,则将状态 j下推入分析栈栈顶。
(3)若 action[s,a]=acc,则结束分析,输入串被接受。
(4)若 action[s,a]或 goto[s,A]不是上述情况,转出错处理
程序。
1
2
3
4
5
6
7
8
9
分析栈 符号栈 输入串 动作
$ (i+i*i)$ 移进
$,(,i +i*i)$
移进
0
0,4
0,4,5
$,( i+i*i)$
归约
0,4,3 $,(,F +i*i)$ 归约
0,4,2 $,(,T +i*i)$ 归约
0,4,8 $,(,E +i*i)$ 移进
0,4,8,6 $,(,E,+ i*i)$ 移进
0,4,8,6,5 $,(,E,+,i *i)$ 归约
0,4,8,6,3 $,(,E,+,F *i)$ 归约
例, (i+i*i)的分析过程
10
11
12
13
14
15
16
17
18
19
0,4,8,6,9 $,(,E,+,T *i)$ 移进
0,4,8,6,9,7 $,(,E,+,T,* i)$ 移进
0,4,8,6,9,7,5 $,(,E,+,T,*,i )$ 归约
0,4,8,6,9,7,10 $,(,E,+,T,*,F )$ 归约
0,4,8,6,9 $,(,E,+,T )$ 归约
0,4,8 $,(,E )$ 移进
0,4,8,11 $,(,E,) $ 归约
0,3 $,F $ 归约
0,2 $,T $ 归约
0,1 $,E $ 接受
(续表 )
1
2
3
4
5
6
7
8
9
分析栈 符号栈 输入串 动作
(i+i*i)$ 移进
+i*i)$
移进
0
0,4
0,4,5
i+i*i)$
归约
0,4,3 +i*i)$ 归约
0,4,2 +i*i)$ 归约
0,4,8 +i*i)$ 移进
0,4,8,6 i*i)$ 移进
0,4,8,6,5 *i)$ 归约
0,4,8,6,3 *i)$ 归约
例, (i+i*i)的分析过程
10
11
12
13
14
15
16
17
18
19
0,4,8,6,9 *i)$ 移进
0,4,8,6,9,7 i)$ 移进
0,4,8,6,9,7,5 )$ 归约
0,4,8,6,9,7,10 )$ 归约
0,4,8,6,9 )$ 归约
0,4,8 )$ 移进
0,4,8,11 $ 归约
0,3 $ 归约
0,2 $ 归约
0,1 $ 接受
(续表 )
E
E T +
F T
i
i
*
F
T
i
F
(i+i*i)
(F+i*i)
(T+i*i)
(E+i*i)
(E+F*i)
(E+T*i)
(E+T*F)
(E+T)
(E)
T
F
E
S’
E
( )
S’
5,几种 LR分析法及其比较
LR(0),SLR(1),LR(1),LALR(1)
三, 识别活前缀的 DFA
1,活前缀,规范句型的不含句柄之后任何符
号的一个前缀 。
亦即,若 A→ ??是文法的一个产生式,且有
S??A??????
则 ???的任何前缀都是规范句型 ????的活前缀 。
*
R R
(1)作为规范句型的活前缀,它不含句柄后的任何符号。
(2)活前缀与句柄之间的三种关系,
? 活前缀不含句柄的任何符号,此时期待从剩余输入串中
识别由 A→ ??的 ??能推导出的符号串 ;
? 活前缀只含句柄的真前缀,也即产生式 A→ ??中 ?已识
别于分析栈栈顶之上,期待从剩余输入串中识别由 ?所
能推导出的符号串 ;
? 活前缀已含句柄的全部符号,这表明产生式 A→ ??的右
部符号 ??已在分析栈栈顶之上,应将 ??归约为 A。
(3)句柄是一类活前缀的后缀,如果能识别一个文法的所有
活前缀,自然也就能识别这个文法的所有句柄了。
2,项目及分类
?项目,在产生式右部添加一个圆点
如 A→ ???,A→ ???,A→ ???
?归约项目,形如 A→ ??
?移进项目,形如 A→ ??a?,a?VT
?待约项目,形如 A→ ??B?,B?VN
?接受项目,形如 S→ ??,S为开始符
3,拓广文法
增加产生式 S’→S, 从而 S’→S ?成为唯
一的接受项目 。
4,NFA的构造
一个项目对应一个状态,S’→ ?S为唯一
初态, 其余均为终态 (活前缀识别态 )。
例如,文法 S’→E
E→E+T|T
T→T*F|F
F→(E)|i
这个文法的项目有,
1.S’→ ?E 8.E→T ? 15.F→ ?(E)
2.S’→E ? 9.T→ ?T*F 16.F→( ?E)
3.E→ ?E+T 10.T→T ?*F 17.F→(E ?)
4.E→E ?+T 11.T→T* ?F 18.F→(E) ?
5.E→E+ ?T 12.T→T*F ? 19.F→ ?i
6.E→E+T ? 13.T→ ?F 20.F→i ?
7.E→ ?T 14.T→F ?
2
4
1
3 5 6
7 8
9 10 11 20
13 18
12
14
15 16 17
19
E
?
?
E + T
T
?
?
? ?
T *
F
?
? i
F
?
?
( E )
识
别
活
前
缀
的
NFA
?
?
5,项目的有效性
(1)对于项目 A→ ???,如果有
S??A??????
则称 A→ ???对活前缀 ??有效。
意思是, 到达项目 A→ ???时,??已识别出,希望继
续识别从 ?推出的串。
*
R R
(2)若 A→ ??B?对活前缀 ??有效,则 B →? ?
对活前缀 ??也有效。
因为 S’??A????B??
则,设 ????’,有
S’??A????B?? ???B?’?????’
即 S’???B?’?????’
所以,B →? ?对 ??也有效。
*
R R
R
*
* *
R R R R
R R
*
(3)有效项目, 对活前缀 ??有效的项目的集
合称为对 ??的有效项目集。
(4)LR(0)项目集规范族, 文法 G的所有有效
项目集组成的集合。
6,closure(I)
设 I是文法 G的一个 LR(0)项目集,
(1)对 i?I,都有 i?closure(I);
(2)若 A???B??closure(I),且 B??为文法 G
的一个产生式,则 B??? ?closure(I)；
(3)重复 (2)直至 closure不再增大 。
7,go(I,X)
设 X?VT?VN
go(I,X)=closure({A??X??|A???X??I})
因为 A???X?对 ??有效
所以 S’??A????X??
故 A??X??对 ??X有效
*
R R
8,LR(0)项目集规范族的构造
begin
C:={closure({S’→ ?S})};
repeat
for C中每一项目集 I和文法符号 X do
if go(I,X)不空 且 go(I,X)?C then
把 go(I,X)加入 C中
until C不再增大
end;
例, 文法
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=goto(I0,E)
S’?E?,E?E?+T
I2=goto(I0,T)
E?T?,T?T?*F
I3=goto(I0,F)
T?F?
I4=goto(I0,( )
F?(?E),E??E+T,E??T,T??T*F,T??F,F??(E),F ??i
I5=goto(I0,i)
F ?i?
I6=goto(I1,+)
E?E+?T,T??T*F,T??F,F??(E),F ??i
I7=goto(I2,*)
T?T*?F,F??(E),F ??i
I8=goto(I4,E)
F?(E?),E?E?+T
I9=goto(I6,T)
E?E+T?,T?T?*F
I10=goto(I7,F)
T?T*F?
I11=goto(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)文法。
五, 关于二义文法
例 1,G(E) E→E+E|E*E|(E)|i
例 2,G(S) S→iSeS|iS|a
(1)FIRSTVT集
FIRSTVT(P)={a|P?a…,或 P?Qa…,a ?VT,Q ?VN}
?若 P?a… 或 P?Qa…,则 a?FIRSTVT(P);
?若 P?Q…,则 FIRSTVT(Q)?FIRSTVT(P);
直至 FIRSTVT(P)不再增大。
+ +
(2)LASTVT集
LASTVT(P)={a|P?...a,或 P?…aQ,a ?VT,Q ?VN}
?若 P?...a或 P?…aQ,则 a?LASTVT(P);
?若 P?...Q,则 LASTVT(Q)?LASTVT(P);
直至 LASTVT(P)不再增大。
+ +
例 G(E) E→E+T│T
T→T*F│F
F→(E) │i
E
T
F
FIRSTVT LASTVT
( i + *
( i
) i + *
) i *
) i
( i *
(3)构造优先关系表的算法
FOR 每条产生式 P?X1X2…X n DO
FOR i:=1 TO n-1 DO
BEGIN
IF Xi和 Xi+1均为终结符 THEN Xi= Xi+1;
IF i<=n-2 且 Xi和 Xi+2均为终结符 但 Xi?VN
THEN Xi=Xi+2;
IF Xi?VT,Xi+1?VN
THEN ?a?FIRSTVT(Xi+1) Xi<a;
IF Xi?VN,Xi+1?VT
THEN ?a?LASTVT(Xi) a>Xi+1
END;
例 G(E) E→E+T│T
T→T*F│F
F→(E) │i
E
T
F
FIRSTVT LASTVT
( i + *
( i
) i + *
) i *
) i
( i *
考察 E→E+T 中的 E和 +, +和 T
考察 T→T*F 中的 T和 *, *和 F
考察 F→(E) 中的 (和 E, (和 ), E和 )
+
+
*
*
i
i
(
(
)
)
$
$
>
>
>
<
>
<
<
<
<
>
>
>
<
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
=
=
算符优先关系表
二, LR分析法
1,LR(K) 分析法
自底向上的 LR分析法是指从左向右扫描
输入串,每次分析由分析栈中符号及向前
搜索 K个输入符号,以确定作为产生式右部
的短语 (句柄 )是否已在分析栈的栈顶形成,
从而决定应采取的动作 。 这种分析方法称
为 LR(K)分析法 。 一般只考虑 K?1的情况 。
其组成为,分析栈,控制程序,分析表,输入串
输入串
分析栈
驱动程序 输出
action goto
分析表
s0
,
,
,
sm-1
sm
a1 ai $,..,.,
2,分析栈
存放状态 ;初始时,置初始状态 s0;栈里的
每一状态概括了从分析开始到某一时刻
已进行的分析工作。
3,分析表
由 action[s,a]和 goto[s,x]两个子表组成。
(1)action[s,a]定义了在状态 s下,当前输入符号为
a时应采取的分析动作, 移进,归约,接受,出错。
(2)goto表是一个状态及非终结符的二维矩阵,
goto[s,x]定义了在状态 s下,面对文法符号 x时的
状态转换。
例 G0(E)
(1)E→E+T
(2)E→T
(3)T→T*F
(4)T→F
(5)F→(E)
(6)F→i
的 LR分析表如后
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
4,控制程序的工作
据 action[s,a]进行,
(1)若 action[s,a]=sj,则将状态 j推入栈顶,输入指针指向
下一输入符号 ;
(2)若 action[s,a]=rj,则按第 j个产生式 A??归约,设 |?|=t,
应在分析栈栈顶上托 t个状态出栈,呈现栈顶的状态设
为 si,则根据 si及归约后的非终结符 A,查 goto表,
goto[si,A]=j,则将状态 j下推入分析栈栈顶。
(3)若 action[s,a]=acc,则结束分析,输入串被接受。
(4)若 action[s,a]或 goto[s,A]不是上述情况,转出错处理
程序。
1
2
3
4
5
6
7
8
9
分析栈 符号栈 输入串 动作
$ (i+i*i)$ 移进
$,(,i +i*i)$
移进
0
0,4
0,4,5
$,( i+i*i)$
归约
0,4,3 $,(,F +i*i)$ 归约
0,4,2 $,(,T +i*i)$ 归约
0,4,8 $,(,E +i*i)$ 移进
0,4,8,6 $,(,E,+ i*i)$ 移进
0,4,8,6,5 $,(,E,+,i *i)$ 归约
0,4,8,6,3 $,(,E,+,F *i)$ 归约
例, (i+i*i)的分析过程
10
11
12
13
14
15
16
17
18
19
0,4,8,6,9 $,(,E,+,T *i)$ 移进
0,4,8,6,9,7 $,(,E,+,T,* i)$ 移进
0,4,8,6,9,7,5 $,(,E,+,T,*,i )$ 归约
0,4,8,6,9,7,10 $,(,E,+,T,*,F )$ 归约
0,4,8,6,9 $,(,E,+,T )$ 归约
0,4,8 $,(,E )$ 移进
0,4,8,11 $,(,E,) $ 归约
0,3 $,F $ 归约
0,2 $,T $ 归约
0,1 $,E $ 接受
(续表 )
1
2
3
4
5
6
7
8
9
分析栈 符号栈 输入串 动作
(i+i*i)$ 移进
+i*i)$
移进
0
0,4
0,4,5
i+i*i)$
归约
0,4,3 +i*i)$ 归约
0,4,2 +i*i)$ 归约
0,4,8 +i*i)$ 移进
0,4,8,6 i*i)$ 移进
0,4,8,6,5 *i)$ 归约
0,4,8,6,3 *i)$ 归约
例, (i+i*i)的分析过程
10
11
12
13
14
15
16
17
18
19
0,4,8,6,9 *i)$ 移进
0,4,8,6,9,7 i)$ 移进
0,4,8,6,9,7,5 )$ 归约
0,4,8,6,9,7,10 )$ 归约
0,4,8,6,9 )$ 归约
0,4,8 )$ 移进
0,4,8,11 $ 归约
0,3 $ 归约
0,2 $ 归约
0,1 $ 接受
(续表 )
E
E T +
F T
i
i
*
F
T
i
F
(i+i*i)
(F+i*i)
(T+i*i)
(E+i*i)
(E+F*i)
(E+T*i)
(E+T*F)
(E+T)
(E)
T
F
E
S’
E
( )
S’
5,几种 LR分析法及其比较
LR(0),SLR(1),LR(1),LALR(1)
三, 识别活前缀的 DFA
1,活前缀,规范句型的不含句柄之后任何符
号的一个前缀 。
亦即,若 A→ ??是文法的一个产生式,且有
S??A??????
则 ???的任何前缀都是规范句型 ????的活前缀 。
*
R R
(1)作为规范句型的活前缀,它不含句柄后的任何符号。
(2)活前缀与句柄之间的三种关系,
? 活前缀不含句柄的任何符号,此时期待从剩余输入串中
识别由 A→ ??的 ??能推导出的符号串 ;
? 活前缀只含句柄的真前缀,也即产生式 A→ ??中 ?已识
别于分析栈栈顶之上,期待从剩余输入串中识别由 ?所
能推导出的符号串 ;
? 活前缀已含句柄的全部符号,这表明产生式 A→ ??的右
部符号 ??已在分析栈栈顶之上,应将 ??归约为 A。
(3)句柄是一类活前缀的后缀,如果能识别一个文法的所有
活前缀,自然也就能识别这个文法的所有句柄了。
2,项目及分类
?项目,在产生式右部添加一个圆点
如 A→ ???,A→ ???,A→ ???
?归约项目,形如 A→ ??
?移进项目,形如 A→ ??a?,a?VT
?待约项目,形如 A→ ??B?,B?VN
?接受项目,形如 S→ ??,S为开始符
3,拓广文法
增加产生式 S’→S, 从而 S’→S ?成为唯
一的接受项目 。
4,NFA的构造
一个项目对应一个状态,S’→ ?S为唯一
初态, 其余均为终态 (活前缀识别态 )。
例如,文法 S’→E
E→E+T|T
T→T*F|F
F→(E)|i
这个文法的项目有,
1.S’→ ?E 8.E→T ? 15.F→ ?(E)
2.S’→E ? 9.T→ ?T*F 16.F→( ?E)
3.E→ ?E+T 10.T→T ?*F 17.F→(E ?)
4.E→E ?+T 11.T→T* ?F 18.F→(E) ?
5.E→E+ ?T 12.T→T*F ? 19.F→ ?i
6.E→E+T ? 13.T→ ?F 20.F→i ?
7.E→ ?T 14.T→F ?
2
4
1
3 5 6
7 8
9 10 11 20
13 18
12
14
15 16 17
19
E
?
?
E + T
T
?
?
? ?
T *
F
?
? i
F
?
?
( E )
识
别
活
前
缀
的
NFA
?
?
5,项目的有效性
(1)对于项目 A→ ???,如果有
S??A??????
则称 A→ ???对活前缀 ??有效。
意思是, 到达项目 A→ ???时,??已识别出,希望继
续识别从 ?推出的串。
*
R R
(2)若 A→ ??B?对活前缀 ??有效,则 B →? ?
对活前缀 ??也有效。
因为 S’??A????B??
则,设 ????’,有
S’??A????B?? ???B?’?????’
即 S’???B?’?????’
所以,B →? ?对 ??也有效。
*
R R
R
*
* *
R R R R
R R
*
(3)有效项目, 对活前缀 ??有效的项目的集
合称为对 ??的有效项目集。
(4)LR(0)项目集规范族, 文法 G的所有有效
项目集组成的集合。
6,closure(I)
设 I是文法 G的一个 LR(0)项目集,
(1)对 i?I,都有 i?closure(I);
(2)若 A???B??closure(I),且 B??为文法 G
的一个产生式,则 B??? ?closure(I)；
(3)重复 (2)直至 closure不再增大 。
7,go(I,X)
设 X?VT?VN
go(I,X)=closure({A??X??|A???X??I})
因为 A???X?对 ??有效
所以 S’??A????X??
故 A??X??对 ??X有效
*
R R
8,LR(0)项目集规范族的构造
begin
C:={closure({S’→ ?S})};
repeat
for C中每一项目集 I和文法符号 X do
if go(I,X)不空 且 go(I,X)?C then
把 go(I,X)加入 C中
until C不再增大
end;
例, 文法
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=goto(I0,E)
S’?E?,E?E?+T
I2=goto(I0,T)
E?T?,T?T?*F
I3=goto(I0,F)
T?F?
I4=goto(I0,( )
F?(?E),E??E+T,E??T,T??T*F,T??F,F??(E),F ??i
I5=goto(I0,i)
F ?i?
I6=goto(I1,+)
E?E+?T,T??T*F,T??F,F??(E),F ??i
I7=goto(I2,*)
T?T*?F,F??(E),F ??i
I8=goto(I4,E)
F?(E?),E?E?+T
I9=goto(I6,T)
E?E+T?,T?T?*F
I10=goto(I7,F)
T?T*F?
I11=goto(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)文法。
五, 关于二义文法
例 1,G(E) E→E+E|E*E|(E)|i
例 2,G(S) S→iSeS|iS|a
