SELECT ( H ->ξ ) = FOLLOW ( H ) = { f , # , o } SELECT ( K-> d M L ) = { d }
SELECT ( K->ξ ) = FOLLOW ( K ) = { e , # , o } SELECT ( L-> e H f ) = { e }
SELECT ( M->K ) = ( FIRST( K ) –{ξ} ) ∪ FOLLOW ( M ) = {d， e , # , o } SELECT ( M -> b L M )= { b } 构造LL( 1 ) 分析表 S H K L M a -> a b -> M H -> b L M e -> M H ->L S o ->ξ -> e H f ->K d -> M H -> d M L ->K f ->ξ o -> M H ->ξ ->ξ ->K # -> M H ->ξ ->ξ ->K
4 . 文法含有左公因式，变为
S->C $ { b, a } C-> b A { b } C-> a B { a }
A -> b A A { b } A-> a A’ { a }
A’-> ξ { $ , a, b }
A’-> C { a , b } B->a B B { a } B -> b B’ { b }
B’->ξ { $ , a , b }
B’-> C { a, b }
5. <程序> --- S <语句表>――A <语句>――B <无条件语句>――C <条件语句>――D <如果语句>――E <如果子句> --F
S->begin A end S->begin A end { begin } A-> B A-> B A’ { a , if } A-> A ; B A’-> ; B A’ { ; } A’->ξ { end } B-> C B-> C { a } B-> D B-> D { if } C-> a C-> a { a } D-> E D-> E D’ { if } D-> E else B D’-> else B { else }
D’->ξ {; , end }
E-> FC E-> FC { if }
F-> if b then F-> if b then { if } 非终结符是否为空
S－否 A－否 A’－是 B－否 C－否 D－否 D’－是 E－否 F－否
11
FIRST(S) = { begin }
FIRST(A) = FIRST(B) ∪ FIRST(A’) ∪ {ξ} = {a , if , ; , ξ} FIRST(A’) ={ ; , ξ}
FIRST(B) = FIRST(C) ∪ FIRST(D) ={ a , if } FIRST(C) = {a}
FIRST(D) = FIRST（E）= { if } FIRSR(D’) = {else , ξ}
FIRST(E) = FIRST(F) = { if } FIRST(F) = { if }
FOLLOW(S) = {# } FOLLOW(A) = {end} FOLLOW(A’) = { end } FOLLOW(B) = {; , end }
FOLLOW (C) = {; , end , else } FOLLOW(D) = {; , end } FOLLOW( D’ ) = { ; , end } FOLLOW(E) = { else , ; end } FOLLOW(F) = { a }
S A A’ B C D D’ E F if then else begin end a b ; S A A’ B C D D’ E F if -> B A’ -> D -> E D’ ->FC ->if b then then else begin end ->ξ ->ξ a -> B A’ -> C -> a b ; # ->begin A end -> ; B A’ ->ξ -> else B D’ 6. 1.
(1) S -> A | B (2) A -> aA|a (3)B -> bB |b 提取 （2），（3）左公因子 (1) S -> A | B (2) A -> aA’ (3) A’-> A|ξ (4) B -> bB’
12
(5) B’-> B |ξ 2.
(1) S->AB (2) A->Ba|ξ (3) B->Db|D (4) D-> d|ξ
提取（3）左公因子 (1) S->AB (2) A->Ba|ξ (3) B->DB’ (4) B’->b|ξ (5) D-> d|ξ 3.
(1) S->aAaB | bAbB (2) A-> S| db (3) B->bB|a 4
(1) S->i|(E)
(2) E->E+S|E-S|S 提取（2）左公因子 (1) S->i|(E) (2) E->SE’
(3) E’->+SE’|-SE’ |ξ 5
(1) S->SaA | bB (2) A->aB|c (3) B->Bb|d
消除（1）(3)直接左递归 (1) S->bBS’ (2) S’->aAS’|ξ (3) A->aB | c (4) B -> dB’ (5) B’->bB’|ξ 6.
(1) M->MaH | H (2) H->b(M) | (M) |b
消除（1）直接左递归，提取（2）左公因子 (1) M-> HM’
(2) M’-> aHM’ |ξ (3) H->bH’ | ( M ) (4) H’->(M) |ξ
7. (1)
13
1) A->baB 2) A->ξ 3) B->Abb 4) B->a 将1）、2)式代入3）式 1) A->baB 2) A->ξ 3) B->baBbb 4) B->bb 5) B->a 提取3）、4）式左公因子 1) A->baB 2) A->ξ 3) B->bB’
4) B’->aBbb | b 5) B->a (3)
1) S->Aa 2) S->b 3) A->SB 4) B->ab
将3）式代入1）式 1) S->SBa 2) S->b 3) A->SB 4) B->ab
消除1）式直接左递归 1) S->bS’
2) S’->BaS’ |ξ 3) S->b 4) A->SB 5) B->ab
删除多余产生式4） 1) S->bS’
2) S’->BaS’ |ξ 3) S->b 4) B->ab
（5）
1) S->Ab 2) S->Ba 3) A->aA 4) A->a 5) B->a
提取3） 4）左公因子
14
1) S->Ab 2) S->Ba 3) A->aA’ 4) A’-> A |ξ 5) B->a
将3）代入1） 5）代入2 1) S->aA’b 2) S->aa 3) A->aA’ 4) A’-> A |ξ 5) B->a
提取1） 2） 左公因子 1) S-> aS’ 2) S’->A’b | a 3) A->aA’ 4) A’-> A |ξ 5) B->a
删除多余产生式5） 1) S-> aS’ 2) S’->A’b | a 3) A->aA’ 4) A’-> A |ξ A A’ S’ S 将3）代入4） 1) S-> aS’ 2) S’->A’b | a 3) A->aA ’ 4) A’-> aA’ |ξ 将4）代入2） 1) S-> aS’ 2) S’->aA’b 3) S’->a 4) S’->b 5) A->aA ’ 6) A’-> aA’ |ξ
对2）3)提取左公因子 1) S->aS’ 2) S’->aS’’ 3) S’’->A’b|ξ 4) S’->b 5) A->aA ’ 6) A’-> aA’ |ξ 删除多余产生式5） 1) S->aS’ 2) S’->aS’’ 3) S’’->A’b|ξ
15