1.将以下文法消除左递归，分析符号串 i*i+i 。
并分别求FIRST集、FOLLOW集，和SELECT集
E -> E+T | T
T -> T*F | F
F -> (E) | i
消除左递归：
E-->TE'
E'-->+TE' | ε
T-->FT'
T'-->*FT' | ε
F-->(E) | i
FIRST集
FIRST(TE')={ ( ( , i ) | T-->F-->{,T-->F-->i}
FIRST(+TE')={+}
FIRST(FT')={( ( , i ) | F-->{ , F-->I}
FIRST(*FT")={*}
FIRST(ε)={ε}
FIRST((E))={ ( }
FIRST(i)={i}
FOLLOW集
FOLLOW(E)={ ) }
FOLLOW(E')={#}
FOLLOW(T)={+}
FOLLOW(T')={#}
FOLLOW(F)={*}
SELECT集
SELECT(E-->TE')=FIRST(TE')={ ( ( , i ) }
SELECT(E'-->+TE' )=FIRST(+TE')={+}
SELECT(E'-->ε )=FOLLOW(E')={#}
SELECT(T-->FT' )=FIRST(FT')={( ( , i ) | F-->{ , F-->I}
SELECT(T'-->*FT' )=FIRST(*FT")={*}
SELECT(T'-->ε)=FOLLOW(T')={#}
SELECT(F-->(E) )=FIRST((E))={ ( }
SELECT(F-->i)=FIRST(i)={i}
分析i*i+i
2.P101练习7（2）（3）文法改写，并分别求FIRST集、FOLLOW集，和SELECT集
A → aABe|a
B → Bb|d
提取公因子
A-->aA'
A'-->ABe | ε
消除左递归
B-->bB' | d
B'-->*b | ε
FIRST集
FIRST(aA')={a}
FIRST(ABe)={a | A-->a}
FIRST(ε)={ε}
FIRST(bB')={b}
FIRST(d)={d}
FIRST(*b)={*}
FOLLOW集
FOLLOW(A)=FIRST(B)={b}
FOLLOW(A')={#}
FOLLOW(B)={e}
FOLLOW(B')={#}
SELECT集
SELECT(A-->aA')=FIRST(aA')={a}
SELECT(A'-->ABe)=FIRST(ABe)={a | A-->a}
SELECT(A'-->ε)=FOLLOW(A')={#}
SELECT(B-->bB' )=FIRST(bB')={b}
SELECT(B-->d)=FIRST(d)={d}
SELECT(B'-->*b)=FIRST(*b)={*}
SELECT(B'-->ε)=FOLLOW(B')={#}
S → Aa|b
A → SB
B → ab
带入S得
S-->SBa | b
B-->ab
消除左递归
S-->BaS' | b
S'-->*B | e
B-->ab
(待修改)
课堂练习：
求以下文法的FIRST集、FOLLOW集和SELECT集。
S->Ap
A->a |ε
A->cA
A->aA
FIRST集
FIRST(Ap)={(a,c,ε) | A-->a,A-->c,A-->ε}
FIRST(a)={a}
FIRST(ε)={ε}
FIRST(cA)={c}
FIRST(aA)={a}
FOLLOW集
FOLLOW(S)={#}
FOLLOW(A)={p}
SELECT集
SELECT(S->Ap)=FIRST(Ap)={(a,c,ε) | A-->a,A-->c,A-->ε}
SELECT(A->a)=FIRST(a)={a}
SELECT(A->ε)=FOLLOW(A)={p}
SELECT(A->cA)=FIRST(cA)={c}
SELECT(A->aA)=FIRST(aA)={a}
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
FIRST集
FIRST(Ap)={a}
FIRST(Bq)={b,d}
FIRST(a)={a}
FIRST(cA)={c}
FIRST(b)={b}
FIRST(dB)={d}
FOLLOW集
FOLLOW(S)={#}
FOLLOW(A)={p}
FOLLOW(B)={q}
SELECT集
SELECT(S->Ap)=FIRST(Ap)={a}
SELECT(S->Bq)=FIRST(b)={b} U FIRST(dB)={d}
SELECT(A->a)=FIRST(a)={a}
SELECT(A->cA)=FIRST(cA)={c}
SELECT(B->b)=FIRST(b)={b}
SELECT(B->dB)=FIRST(dB)={d}