编译原理-编译原理第五章

第五章

2.对下面的文法G：

EfTE

E->+E|e

TfFT

TTT|£

F9PF

F9*叫£

P->(E)|aIbI*

⑴计郛这个文法的每个非终结符的FIRST集和FOLLOW集，

(2)证明这个方法是LL(1)的。

(3)构造它的预测分析表。

(4)构造它的递归下降分析程序。

解：

(1)计算这个文法的每个非终结符的FIRST集和FOLLOW英。

FIRST集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,*};

FIRST(£)=(1,c)

FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,1;

E1RST(T)=FIRST(T)U{2}={(,a,b/，e};

FIRST(F)=FTRST(P)={(,a,b/};

FIRST(F/)=FIRST(P)={*,e};

FIRST(P)={(,a,b/};

FOLLOW集合有：

FOLLOW(E)={),#};

FOLLOW(E)=FOLLOW(E)=1),0};

FOLLOW(T)=FIRST(E)UFOLLOW(E)={+,),#}；〃不包含e

FOLLOW(T)=FOLLOW(T)=FIRST(E)UFOLLOW(E)={+,),#};

FOLLOW(F)=FIRST(T)UFOLLOW(T)={(,a,b/，+,),#};//不包含e

FOLLOW(Fj=FOLLOW(F)=FIRST(T)UFOLLOW(T)={(,a,b「,+,),#};

FOLLOW(P)=FIRST(F/)UFOLLOW(F)={*,(,a,bj,+,),#};//不包含£

(2)证明这个方法是LL(1)的。

各产生式的SELECT集合有：

SELECT(ETTE)=FIRST(T)={(,a,b/};

SELECT(E、9+E)={+};

SELECT(E->£)=FOLLOW(E)={),#}

SELECT(T-^FT)=FIRST(F)={(,a,b,"}；

SELECT(T^T)=FIRST(T)={(,a,b/};

SELECT(T->e)=FOLLOW(T)={+,),#};

SELECT(FTPF)=FIRST(P)={(,a,b,.};

SELECT(FT*F)={*};

SELECT(FTs)=FOLLOW(F)={(,a,bj,+,),#};

SELECT(P9(E))={(}

SELECT(P->a)={a}

SELECT(P->b)={b}

SELECT(PT')=「}

可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。

(3)构造它的预测分析表。

文法G[E]的预测分析表如下:

*

+*()ab

EfTE今TETTETTE

E’9+E今£->£

T9FT今FT今FT今FT，

T)£IT今£TTTT9T今£

FfPF今PFTPFTPF

F'€9*F"->£)£->£今€->£->£

PT(E)->alb4

(4)构造它的递归下降分析程序。

对每个非终结符写出不带回溯的递归子程序如下：

charCH;〃存放当前的输入符号

voidP_E()〃非线结符E的子程序

{

if(IsIn(CH,FIRSTTEP))//FIRSTTEP为TTTE的右部的FIRST集合,产生式ETTE

(

P_T();

P_EP();

)

elseERR;

)

voidP_EP()〃非终结符E的子程序

(

if(CH=r+')〃产生式ET+E

(

READ(CH);

P_E();

)

else〃产生式E->£

(

if(lsln(CH,FOLLOW一EP))//FOLLOWEP为E的FOLLOW集合

return;

elseERR;

)

)

voidP_T()〃非终结符T的子程序

{

if(IsIn(CH,FIRST_FTP))//FIRST_TEP为T9FT的右部的FIRST集合，产生式TIFT

(

P_F()；

P_TP();

)

elseERR;

)

voidP_TP()〃非终结符T的子程序

if(Isln(CH,FIRSTT))//FIRSTT为产生式T>T的右部的FIRST集合,产生式TTT

P_T();

)

else〃产生式T)£

(

if(IsIn(CH,FOLLOW_TP))//FOLLOW_TP为T的FOLLOW集合

return;

elseERR;

)

)

voidP_F。//非终结符F的子程序

{

if(IsIn(CH,FIRST.PFP))//FIRST_PFP为FTP—的右部的FIRST集合，产生式F9PF

(

P_P()；

P_FP();

)

elseERR;

)

voidP_FP()〃非终结符F的子程序

(

if(CH==,*')〃产生式F3*F

{

READ(Cl!);

P_FP()；

)

else〃产生式F今£

{

if(lsln(CH,FOLLOW_FP))//FOLLOW_FP为F的FOLLOW集合

return;

elseERR;

)

)

voidP_PO〃非终结符P的子程序

{

if(CH==,(')

(

READ(CH);

P_E();

if(CH==,)')READCII(CH)：

else

ERR;

)

elseif(CH=='a')READ(CH);

elseif(CH==,b')READ(CH);

,

PISPir(CH==r)READ(QI)：

elseERR;

)

4证明下述文法不是LL(I)的。

S->C$C->bA|aBA->a|aC|bAAB->b|bC|aBB你能否构造一等价的文法，使其是LL

(1)的，并给出判断过程。

【解】SELECT(A->a)nSELECT(A->aC)^<I>,WffiLL(1)文法的判定条件：

(1)文法不含左递归

(2)对于文法U的任意两个不同的规则有：SelectiU-*o)ASelect(U-*尸中一个

文法若满足以上条件，称该文法G为LL(1)文法。得出该文法不是LL(1)文法。该文法

含公共因子，消除后的文法为：

s->c$

C->bA|aB

A->aA'|bAA

A'

B->bB'|