编译原理first集合

本文格式为Word版，下载可任意编辑——编译原理first集合Firstfollow

1.对以下文法G(S)：

S—>D(R)R—>R;P|PP—>S|ID—>i

①计算文法G中每个非终结符的FIRSTVT集和LASTVT集。②构造文法G的算符优先关系矩阵。解：（1）FIRSTVT(S)={(,i}，FIRSTVT(D)={i}，FIRSTVT(R)={;,(,i}，FIRSTVT(P)={i,(}，LASTVT(S)={)}，LASTVT(D)={i}，LASTVT(R)={;,),i}，LASTVT(P)={i,)}

（2）算符优先矩阵，如表A-5所示。

表A-5优先矩阵

();i#(????????)B??????;????????i??????#??B2.设有文法G（S）：

S—>aBc|bABA—>aAb|bB—>b|ε

①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。②构造LL(1)分析表，并分析符号串baabbb是否是。

解：（1）FIRST(aBc)={a},FIRST(bAB)={b}FIRST(aAb)={a},A→b:FIRST(A→b)={b},B→b:FIRST(b)={b},FIRST(ε)={ε}

FOLLOW(A)={b,#},FOOLOW(B)={c,#}

SELECT(S→aBc)={a},SELECT(S→bAB)={b},SELECT(A→aAb)={a},SELECT(A→b)={b},SELECT(B→b)={b},SELECT(B→?)={c,#}

因此，所得的LL(1)分析表如表A-4所示。

表A-4LL(1)分析表输输入符号入abc#VNSS→aBcS→bABAA→aAbA→bBB→bB→?B→?

（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。

步骤符号栈输入串所用的产生式1#Sbaabbb#S?bAB2#BAbbaabbb#3#BAaabbb#A?aAb4#BbAaaabbb#5#BbAabbb#A?aAb6#BbbAaabbb#7#BbbAbbb#A?b8#Bbbb9#Bbb10#Bb11#B12#bbb#bb#b###B?ε成功

图A-16识别串baabbb的过程

3、设文法G(S)：(12分)

S?SiA|AA?A?B|BB?)A*|(1．构造各非终结符的FIRSTVT和LASTVT集合；2．构造优先关系表和优先函数。(12分)答：(6分)

FIRSTVT(S)={i，+，)，(}FIRSTVT(A)={+，)，(}FIRSTVT(B)={)，(}

LASTVT(S)={i，+，*，(}LASTVT(A)={+，*，(}LASTVT(B)={*，(}

优先关系表:(3分)

i+()*

优先函数:(3分)

i+()*i>>>>+>(>>fg2164661661

4、对表达式文法G：

E→E+T|TT→T*F|FF→(E)|I

（1）造各非终结符的FIRSTVT和LASTVT集合；（2）构造文法的算符优先关系表。（15）ETF

算符优先关系表+*I（）#+>>>>>>=>#>>>>=FIRSTVT*，+，（，i*，（，i（，iLASTVT*，+，），i*，），i），i五、设有文法G[A]：

A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAf|c

(1)计算该文法的每一个非终结符的FIRST集和FOLLOW集；(2)试判断该文法是否为LL（1）文法。（15）ABCDEFIRSTA,b,c,d,gbA,c,dDC,gFOLLOWA,c,dC,d,gA,b,c,g是LL（1）文法。

三、对文法G(S)：S→a|^|(T)；T→T，S|S

答：(1)

FIRSTVT(S)?{a,^,(}FIRSTVT(T)?{,,a,^,(}LASTVT(S)?{a,^,)}LASTVT(T)?{,,a,^,)}a^(),#a>=>>>>#>>>=(2)是算符优先文法，由于任何两个终结符之间至多只有一种优先关系。（2分）(3)给出输入串(a,a)#的算符优先分析过程。

步骤12345678910

栈##(#(a#(N#(N,#(N,a#(N,N#(N#(N)#N当前输入字符(A,,A)）)##剩余输入串动作a,a#,a)#a)#a)#)#####)归约(=)移进)>#归约接受3、对于文法G(S):S?bMbM?(L|aL?Ma）

答：1）S?bMb?b(Lb?b(Ma)b2）短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)

13.设文法G（S）：S→T|S∨TT→U|T∧UU→i|-U

（1）计算FIRSTVT和LASTVT；（2）构造优先关系表。

.(1)FIRSTVT(S)={∨,∧,i,-}FIRSTVT(T)={∧,i,-}FIRSTVT(U)={i,-}

LASTVT(S)={∨,∧,i,-}

LASTVT(T)={∧,i,-}

b(SMbTLMa)LASTVT(U)={i,-}

(2)

iS∨.>.>.>∧.>.>-+(9、文法G：S→b|∧(T)T→T,S|S

则FIRSTVT(T)。a.{b,∧,(}b.{b,∧,)}

().>.>=.>.c.{b,∧,(,，}d.{b,∧,),，}

由T→T,…和T→(…得FIRSTVT(T))={(,，)}；

由T→S得FIRSTVT(S)?FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即FIRSTVT(T)={b,∧,(,，}；因此选c。

STT’aS→aT→ST’^S→^T→ST’(S→(T)'T→ST’)T’→ε,T’→,ST’#

3.设文法G（S）：S→(T)|aT→T+S|S

(1）计算FIRSTVT和LASTVT；（2）构造优先关系表。(1)FIRSTVT(S)={a,(}FIRSTVT(T)={+,aa,(}LASTVT(S)={a,)}

LASTVT(T)={+,a,)}

(2)a+a.>+(9、文法G：S→b|∧(T)T→T,S|S

则FIRSTVT(T)。a.{b,∧,(}b.{b,∧,)}

(