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
分析符号串 i*i+i 为:
FIRST 集:
- FIRST(TE')={ (, i }
- FIRST(+TE')={
- +
- }
FIRST(ε)={ε}
- FIRST(FT')={ (, i }
- FIRST(*FT')={
- *
- }
- 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'->ε)=FIRST(ε)-{
- ε
- }UFOLLOW(E')=FOLLOW(E')={
- ),#
- }
- SELECT(T->FT')=FIRST(FT')={
- (,i
- }
- SELECT(T'->*FT')=FIRST(*FT')={*}
- SELECT(T'->ε)=FIRST(ε)-{
- ε
- }UFOLLOW(T')=FOLLOW(T')={
- +,),#
- }
- SELECT(F->(E))=FIRST((E))={
- (
- }
- SELECT(F->i)=FIRST(i)={
- i
- }
2.P101 练习 7(2)(3) 文法改写, 并分别求 FIRST 集, FOLLOW 集, 和 SELECT 集
答: 107 页练习 7(2)
- A->aABe | a
- B->Bb | d
文法改写:
A->aA'A'->ABe | ε
B->dB'B'->bB' | ε
FIRST 集:
- FIRST(aA')={
- a
- }
- FIRST(ABe)={
- a
- }
FIRST(ε)={ε}
- FIRST(dB')={d}
- FIRST(bB')={
- b
- }
FOLLOW 集:
- FOLLOW(A)={
- d,#
- }
- FOLLOW(A')={d,#}
- FOLLOW(B)={e}
- FOLLOW(B')={
- e
- }
SELECT 集:
- SELECT(A->aA')=FIRST(aA')={
- a
- }
- SELECT(A'->ABe)=FIRST(ABe)={a}
- SELECT(A'->ε)=FIRST(ε)-{
- ε
- }UFOLLOW(A')=FOLLOW(A')={
- d,#
- }
- SELECT(B->dB')=FIRST(dB')={
- d
- }
- SELECT(B'->bB')=FIRST(bB')={b}
- SELECT(B'->ε)=FIRST(ε)-{
- ε
- }UFOLLOW(B')=FOLLOW(B')={
- e
- }
答: 107 页练习 7 (3)
- S->Aa | b
- A->SB
- B->ab
文法改写:
S->bS'S'->BaS' | ε
B->ab
FIRST 集:
- FIRST(bS')={b}
- FIRST(BaS')={
- a
- }
FIRST(ε)={ε}
FIRST(ab)={a}
FOLLOW 集:
- FOLLOW(S)={
- #
- }
- FOLLOW(S')={
- #
- }
- FOLLOW(B)={
- a
- }
SELECT 集:
- SELECT(S->bS')=FIRST(bS')={
- b
- }
- SELECT(S'->BaS')=FIRST(BaS')={a}
- SELECT(S'->ε)=FIRST(ε)-{
- ε
- }UFOLLOW(S')=FOLLOW(S')={
- #
- }
- SELECT(B->ab)=FIRST(ab)={
- a
- }
课堂练习:
求以下文法的 FIRST 集, FOLLOW 集和 SELECT 集.
S->Ap
A->a |ε
A->cA
A->aA
答:
FIRST 集:
- FIRST(Ap)={
- a,c,p
- }
- FIRST(a)={
- a
- }
FIRST(ε)={ε}
- FIRST(cA)={
- c
- }
- FIRST(aA)={
- a
- }
FOLLOW 集:
- FOLLOW(S)={
- #
- }
- FOLLOW(A)={
- p
- }
SELECT 集:
- SELECT(S->Ap)=FIRST(Ap)={
- a,c,p
- }
- SELECT(A->a)=FIRST(a)={
- a
- }
SELECT(A->ε)=FIRST(ε)-{ε}UFOLLOW(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,c
- }
- 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,c
- }
- SELECT(S->Bp)=FIRST(Bq)={
- b,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
- }
来源: http://www.bubuko.com/infodetail-3289498.html