# 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 >