24 # # E`
二、考虑下面文法G
S T
a
^(T) S
T,S
⑴消除文法的左递归。
⑵经改写后的文法是否是LL(1)的?给出它的预测分析表。 解答:
⑴经考察该文法S终结符号,所以只有T法,改写后的文法是:
S T
T`
aST` ,ST`
^(T)
a
^
(T)的各侯选式的首字符都是S是直接左递归。根据改写算
T,S
⑵证明改写后的文法是否是LL(1)的.
①证明S
a
^(T)各侯选式的FIRST是否两两相交。
FIRST(^)=FIRST(()=FIRST(()=
FIRST(a)
FIRST(a)FIRST(^)
②证明T`否相交。
,ST`
的FIRST(T`)和FOLLOW(T`)是
求FIRST(T`)={,,
FOLLOW(T`)={
} }
FIRST(T`)? FOLLOW(T`)={,,
该文法是LL(1)的。
⑶构造预测分析表
}?{ }=?
a , ^ ( ) #
S S T T
a SST` T
^ SST` T
(T) ST`
T` T`,ST` T`
二、下面的文法G
E E` T
T`F F`
P
TE` +EFT` TPF` *F`(E)
^
a
b
⑴计算这个文法的每个非终结符的FIRST和FOLLOW。 ⑵证明这个文法是LL(1)的 ⑶构造它的预测分析表。 解答:
⑴求非终结符的FIRST和FOLLOW。 求非终结符的FIRST:
因为E`因为F`因为P
+E*F`(E)
,所以FIRST(E`)={+, ,所以FIRST(F`)={*, ^
a
b,
。
}。 }。
所以FIRST(P)={(, ^, a, b 因为F因为T因为E因为T`
PF`,所以FIRST(F)= FIRST(P)。 FT`,所以FIRST(T)={FIRST(F)。 TE`,所以FIRST(E)= FIRST(T)。 T
,
{
}
。
所以FIRST(T`)= FIRST(T)
={(, ^, a, b ,求非终结符的FOLLOW: 因为E
TE`的E是文法的开始符号,FOLLOW(E)={#},
FIRST())\\{
}={#,)}
又因为P(E),所以FOLLOW(E)={#}
因为E因为E
TE`,所以FOLLOW(E`)=FOLLOW(E) TE`,并且E`≠
,
所以FOLLOW(T)=FIRST(E`)\\{}, 又因为E`
,
FOLLOW(E)={+}
{#,}}={+,
所以FOLLOW(T)={+}#,
}. 因为T#,
}. 因为T
FT`,并且T`≠
FT`,所以FOLLOW(T`)=FOLLOW(T)={+,
,
所以FOLLOW(F)=FIRST(T`)\\{},又因为T`所以FOLLOW(F)={(,^,a,b ={(,^,a,b 因为F
PF`,
{+,#,
,
FOLLOW(T)
}={(,^,a,b ,+,#,
所以FOLLOW(F`)=FOLLOW(F)={(,^,a,b ,+,#,
. 因为F
PF`,并且F`≠
,
,
所以FOLLOW(P)=FIRST(F`)\\{},又因为F`所以FOLLOW(P)={*
={*}
FOLLOW(F) {(,^,a,b,+,),#
,#
.
={*,(,^,a,b ,+,⑵证明这个文法是LL(1)的 ①证明P
(E)
^
a
b各侯选式的FIRST是否两两相交。 FIRST(^)=FIRST(a)=FIRST(b)=
*F`
非终结符号的
FIRST((E))
FIRST((E))FIRST((E))
FIRST(^)
FIRST(^)FIRST(a)
②证明E`
+E
FIRST(a)=FIRST(b)=FIRST(b)=,T`
T
,F`
FIRST和FOLLOW是否相交。
FIRST(E`)? FOLLOW(E`)={+,
}?{#,
}=?
FIRST(T`)? FOLLOW(T`) ={(, ^, a, b ,
?{+,#, }=?
FIRST(F`)? FOLLOW(F`) ={*,
}?{(,^,a,b ,+,#,
=?
该文法是LL(1)的。
⑶构造预测分析表
+ * ( ) a b ^ # E TE` TE` TE` TE` E` +E`
T FT` FT` FT` FT` T`
T
T T T
F PF` PF` PF` PF` F`
*F`
P (E) a b ^
语法分析-自上而下分析
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)