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)={ T }
FIRST(+TE')={ + }
FIRST(FT')={ F }
FIRST(*FT')={ * }
FIRST((E))={ ( }
FOLLOW集:
FOLLOW(E)={ ) }
FOLLOW(E')={ # }
FOLLOW(T)={ E' }
FOLLOW(T')={ # }
FOLLOW(F)={ T' }
SELECT集:
SELECT(E→TE')=FIRST(TE')={T}
SELECT(E'→+TE')=FIRST(+TE')={+}
SELECT(E'→ε)=(FIRST(ε)-{ε})∪FOLLOW(E')={)}
SELECT(T→FT')=FIRST(FT')={F}
SELECT(T'→*FT')=FIRST(*FT')={*}
SELECT(T'→ε)=(FIRST(ε)-{ε})∪FOLLOW(T')={#}
SELECT(F→(E))=FIRST((E))={(}
SELECT(F→i)=FIRST(i)={i}
分析符号串 i*i+i:
2.P101练习7(2)(3)文法改写,并分别求FIRST集、FOLLOW集,和SELECT集。
(2)A->aABe | a
B->Bb | d
提取左公因子:
A->aA'
A'->ABe | ε
消除左递归:
B->dB'
B'->bB' | ε
FITST集:
FIRST(aA')={a}
FIRST(ABe)={A}
FIRST(ε)={ε}
FIRST(dB')={d}
FIRST(bB')={b}
FOLLOW集:
FOLLOW(A)={Be}
FOLLOW(A')={#}
FOLLOW(B)={e}
FOLLOW(B')={#}
SELECT集:
SELECT(A→aA')=FIRST(aA')={a}
SELECT(A'→ABe)=FIRST(ABe)={A}
SELECT(A'→ε)=(FIRST(ε)-{ε})∪FOLLOW(A')={#}
SELECT(B→dB')=FIRST(dB')={d}
SELECT(B'→bB')=FIRST(bB')={b}
SELECT(B'→ε)=(FIRST(ε)-{ε})∪FOLLOW(B')={#}
(3)S->Aa | b
A->SB
B->ab
代入式子:
S->SBa | b
消除左递归:
S'->bS'
S'->BaS' | ε
B->ab
FIRST集:
FIRST(SBa)={S}
FIRST(b)={b}
FIRST(bS')={b}
FIRST(BaS)={B}
FIRST(ε)={ε}
FIRST(ab)={ab}
FOLLOW集:
FOLLOW(S)={B}
FOLLOW(S')={#}
FOLLOW(B)={a}
SELECT集:
SELECT(S→SBa)=FIRST(SBa)={S}
SELECT(S→b)=FIRST(b)={b}
SELECT(S→bS')=FIRST(bS')={b}
SELECT(S'→BaS')=FIRST(BaS')={B}
SELECT(S'→ε)=(FIRST(ε)-{ε})∪FOLLOW(S')={#}
SELECT(B→ab)=FIRST(ab)={a}
课堂练习:
求以下文法的FIRST集、FOLLOW集和SELECT集。
S->Ap
A->a |ε
A->cA
A->aA
FIRST集:
FIRST(a)={a}
FIRST(ε)={ε}
FIRST(cA)={c}
FIRST(aA)={a}
FIRST(Ap)={a,c,p}FOLLOW集:
FOLLOW(S)={#}
FOLLOW(A)= {p}
SELECT集:
SELECT(S→Ap)=FIEST(Ap)={A}
SELECT(A→a)=FIRST(a)={a}
SELECT(A→ε)=(FIRST(ε)-{ε})∪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(a)={a}
FIRST(cA)={c}
FIRST(b)={b}
FIRST(dB)={d}
FIRST(Ap)={a,c}
FIRST(Bq)={b,d}
FOLLOW集:
FOLLOW(S)={#}
FOLLOW(A)={p}
FOLLOW(B)={q}
SELECT集:
SELECT(S→Ap)=FIEST(Ap)={A}
SELECT(S→Bq)=FIRST(a)={a}
SELECT(A→a)=FIRST(a)={a}
SELECT(A→cA)=FIRST(cA)={c}
SELECT(B→b)=FIRST(b)={b}
SELECT(B→dB)=FIRST(dB)={d}