消除左递归
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')=First(T)=Fisrt(F)={ ( , i }
First(+TE')={+}
First(ε)={ε}
First(FT')=First(F)={ ( , i }
First(*FT')={*}
First((E))={ ( }
First(i)={i}
FOLLOW集：
Follow(E)={ ) }
Follow(E')={#}
Follow(T)={E'}
Follow(T')={#}
Follow(F)={T'}
E-> TE'
E'-> +TE' |ε
T-> FT'
T'-> *FT' |ε
F-> (E) | i
SELLECT集：
Sellect(E->TE')=First(TE')={ ( , i }
Sellect(E'-> +TE')=First(+TE')={+}
Sellect(E'-> ε)=First(ε)-{ε} U Follow(E')=Follow(E')={#}
Sellect(T-> FT')=First{FT'}={ ( , i }
Sellect(T'-> *FT')=First(*FT')={*}
Sellect(T'->ε)=First(ε)-{ε} U Follow(T')=Follow(T')={#}
Sellect{F-> (E)}=First((E))={ ( }
Sellect(F-> i)=First(i)={i}
i*i+i
------------------------------------------------------------------------------------------------------------------------------
2.P101练习7（2）（3）文法改写，并分别求FIRST集、FOLLOW集，和SELECT集
(2)A-> aABe | a
B-> Bb | d
A->ax
x->ABe
B-> dB'
B'-> bB' |ε
FIRST集：
First(ax)={a}
First{ABe}={A}={A}
First(dB')={d}
First(bB')={b}
First(ε)={ε}
FOLLOW集：
Follow(A)={B}
Follow(x)={#}
Folliw(B)={#}
Follow(B')={#}
A->ax
x->ABe
B-> dB'
B'-> bB' |ε
SELLECT集：
Sellect(A->ax)=First(ax)={a}
Sellect(x->ABe)=First(ABe)={A}
Sellect(B-> dB')=First(dB')={d}
Sellect(B'-> bB')=First(bB')={}
Sellect(B'-> ε)=First(ε)-{ε} U Follow(B')=Follow(B')={#}
(3)S->Aa | b
A-> SB
B-> ab
将A->SB 代入 S->Aa | b 得：
S-> SBa | b
消除左递归：
S->bS'
S'->BaS' |ε
B-> ab
FIRST集：
First(bS')={b}
First(BsS')={B}
First(ε)={ε}
First(ab)={a}
FOLLOW集：
Follow(S)={#}
Follow(S')={#}
Follow(B)={a}
SELLECT集：
Sellect(S->bS')=First(bS')={b}
Sellect(S'->BaS')=First(BaS')={B}
Sellect(S'-> ε)=First(ε)={ε}
Sellect(B-> ab)=First(ab)={a}
------------------------------------------------------------------------------------------------------------------------------
课堂练习：
求以下文法的FIRST集、FOLLOW集和SELECT集。
S->Ap
A->a |ε
A->cA
A->aA
FIRST集：
Ap=>ap
=>p
=>cAp
=>aAp
First(A)={c,a,ε}
First(Ap)={c,a,p}
First(a)={a}
First(ε)={ε}
First(cA)={c}
First(aA)={a}
FOLLOW集：
Follow(S)={#}
Follow(A)={p}
SELLECT集：
Sellect(S->Ap)= First(Ap)= {c,a,p}
Sellect(A->a)= First(a)={a}
Sellect(A->ε)= First{ε}-{ε} U Follow(A)= Follow(A) ={p}
Sellect(A->cA)= First(cA)= {c}
Sellect(A->aA)= First{aA}= {a}
------------------------------------------------------------------------------------------------------------------------------
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
FIRST集：
Ap=>ap
=>cAp
First(Ap)={a,c}
Bq=>bq
=>dBq
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}
SELLECT集：
Sellect(S->Ap)=First(Ap)={a,c}
Sellect(S->Bq)=First(Bq)={b,d}
Sellect(A->a)=First{a}={a}
Sellect(A->cA)=First{cA}={c}
Sellect(B->b)=First{b}={b}
Sellect(b->dB)=First(dB)={d}
优质内容筛选与推荐>>1、关于数组的一些常用函数
2、程序员求职面试三部曲之一：选择合适的工作单位
3、Redis两种持久化方式(RDB&AOF)
4、Android数据存储方式
5、mockito模拟静态方法