11.将以下文法消除左递归,分析符号串 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->I | (E)
FIRST(TE')={I,(}
FIRST(+TE')={+}
FIRST(ε)={ε}
FIRST(FT')={I,(}
FIRST(*FT')={*}
FIRST(I)={I}
FIRST((E))={(}
FOLLOW(E)={)}
FOLLOW(E')={#}
FOLLOW(T)={E'}
FOLLOW(T')={#}
FOLLOW(F)={T'}
SELECT(TE')={I,(}
SELECT(+TE')={+}
SELECT(ε)={#}
SELECT(FT')={I,(}
SELECT(*FT')={*}
SELECT(I)={I}
SELECT(F)={(}
2.P101练习7(2)(3)文法改写,并分别求FIRST集、FOLLOW集,和SELECT集
(2)
A->aA'
A'->ABe | ε
B->dB'
B'->bB' | ε
FIRST( aA')={a}
FIRST( ABe)={a}
FIRST( ε)={ε}
FIRST(dB')={d}
FIRST(bB')={b}
FOLLOW(A)={d}
FOLLOW(A')={#}
FOLLOW(B)={e}
FOLLOW(B')={#}
SELECT( A->aA')={a}
SELECT( A'->ABe)={a}
SELECT( A'->ε)={#}
SELECT(B->dB')={d}
SELECT(B'->bB')={b}
SELECT(B'->ε)={#}
(3)
S->bS'
S'->BaS' | ε
B->ab
FIRST(bS')={b}
FIRST(BaS')={a}
FIRST(ε)={ε}
FIRST(ab)={a}
FOLLOW(S)={#}
FOLLOW(S')={#}
FOLLOW(B)={a}
SELECT(S->bS')={b}
SELECT(S'->BaS')={a}
SELECT(S'->ε)={#}
SELECT(B->ab)={a}
课堂练习:
求以下文法的FIRST集、FOLLOW集和SELECT集。
(1)
S->Ap
A->a |ε
A->cA
A->aA
FIRST(Ap)={a,c,p}
FIRST(a)={a}
FIRST(ε)={ε}
FIRST(cA)={c}
FIRST(aA)={a}
FOLLOW(S)={#}
FOLLOW(A)={p}
SELECT(S->Ap)={a,c,p}
SELECT(A->a)={a}
SELECT(A->ε)={p}
SELECT(A->cA)={c}
SELECT(A->aA)={a}
(2)
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
FIRST(Ap)={a,c}
FIRST(Bq)={b,d}
FIRST(a)={a}
FIRST(c)={c}
FIRST(b)={b}
FIRST(dB)={b}
FOLLOW(S)={#}
FOLLOW(A)={p}
FOLLOW(B)={q}
SELECT(S->Ap)={a,c}
SELECT(S->Bq)={b,d}
SELECT(A->a)={a}
SELECT(A->cA)={c}
SELECT(B->b)={b}
SELECT(B->dB)={d}