# S aZ21 bZ11 Z11 bZ11 ε Z21 aZ21 bZ11
9.解： (1)
产生式 first集 follow集
S→SaB
→bB {b} {b} {#,a,c} A→S →a {b} {a} {c}
B→Ac {a,b} {#,a,c}
(2)将S→SaB | bB改写为S→bBS’,S’→aBS’|ω,可验证，新文法是LL(1)的。
10.解：
1）为方便书写，记：<布尔表达式>为A，<布尔因子>为B，<布尔二次量>为C，<布尔初等量>为D，原文法可以简化为：
A→A∨B | B B→B∧C | CC→┐D | DD→(A) | true | false,
显然，文法含有左递归，消去后等价LL(1)文法为：
A→BA’ A’ →∨BA’|ω B→CB’,
B’ →∧CB’|ωC→┐D|DD→(A)| true|false
(2)略 证：若LL（1）文法G有形如B→aAAb的产生式，且AT+ε及AT*ag,根据FIRST集FOLLOW集的构造算法可知，FIRST(A)中一切非ε加到FOLLOW(A)中，则a∈FOLLOW(A)；又因为a∈FIRST(ag),所以两集合相交非空，因此，G不是LL(1)文法；与前提矛盾，假设不成立，得证。 解： (1) S A ( a ) b S = = A = < = < ( = = < < <
a > = < > < > > ) > > > > > b
> >
不是简单优先文法。 (2) S R T ( ) ∧ a , S
> = R
= T
> ( < = < < < < )
> > ∧
> > a
> > , < = < < <
是简单优先文法。 (3) S R ( a , ) S = <
< R
> > ( = < < a
> > , = < < )
> >
是简单优先文法。
首先消去无用产生式Z→E, Z→E+T S Z T # i ( ) S
Z = = T >