资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 语法分析,5.6,对于如下文法，求其,First,集和,Follow,集。,S,aAB,S ,bA,S ,A ,aAb,A,B ,bB,B ,解：,First(aAB,)=a,First(bA,)=b,First(aAb,)=a,First(bB,)=b,Follow(S,)=#,Follow(A,)=#,b,Follow(B,)=#,5.7,设有文法,GS:,S,AB,AAaa|a,BBbb|b,(1),将此文法改造为,LL,（,1,）文法,;,(2),构造相应的,LL,（,1,）分析表。,解：（,1,）此文法是左递归文法，消除左递归后的,LL(1),文法为：,S,AB,AaA,A ,aaA,|,BbB,BbbB,|,(2),相应的,LL(1),分析表如下：,Select(S,AB,)=,First(AB,)=a,Select(A,aA,)=,First(aA,)=a,Select(A,aaA,)=,First(aaA,)=a,Select(,A, ,)=,Follow(A,)=b,Select(B,bB,)=,First(bB,)=b,Select(B,bbB,)=,First(bbB,)=b,Select(B, ,)=,Follow(B,)=#,a,b,#,S,BA/R,A,A/C,A,Aa,/C,/R,B,B/C,B,Bb,/C,/R,a,/C,b,/C,#,succ,5.8,对于文法,GS:,SSb,SAb,Sb,AAb,Aa,(1),构造一个与,GS,等价的,LL(1),文法,GS,。,(2),对于文法,GS,，构造,LL(1),分析表。,解,: (1),消除左递归,S,AbS|bS,SbS,|,AaA,AaA,|,(2),求,Select,集，构造相应的,LL(1),分析表,Select(S,AbS,)=,First(AbS,)=a,Select(S,bS,)=,First(bS,)=b,Select(S,bS,)=,First(bS,)=b,Select(,S,)=,Follow(S,)=#,Select(A,aA,)=,First(aA,)=a,Select(A,aA,)=,First(aA,)=a,Select(A,)=,Follow(A,)=b,分析表如下：,a,b,#,S,SbA,/R,S/C,S,S/C,/R,A,A/C,A,A/C,a,/C,b,/C,#,SUCC,5.9,设已知文法,GS:,SSaB|bB,AS|a,BAc,(1),将此文法改造为,LL(1),文法。,(2),构造其,Select,集。,(3),试为文法,GS,构造相应的,LL(1),分析表。,解,:,(1),此文法存在左递归现象，消除左递归后的,LL(1),文法为：,SbBS,SaBS,|,AS|a,BAc,(2),构造其,Select,集如下：,Select(S,bB,S,)=,First(bBS,)=b,Select(S,aBS,)=,First(aBS,)=a,Select(S,)=,Follow(S,)=#,Select(A,S,)=,First(S,)=,a,b,Select(A,a,)=,First(a,)=a,Select(B,Ac,)=,First(Ac,)=,a,b,(3),构造相应的,LL(1),分析表如下：,a,b,c,#,S,SB/C,S,SB/C,/R,A,/R,/R,B,cA,/R,cA,/R,c,/C,#,SUCC,5.10,设有表达文法,GE,：,E,E+T|E-T|T,TT*F|T/F|F,FF,P | P,P(E) | i,试为其构造,LL(1),分析表，并对输入串,i*,i,i-i/i,进,行分析。,解：此文法是左递归文法，消除左递归后的文法为：,E,TE,E,+TE|-TE|,TFT,T*FT|/FT|,FPF,F,PF |,P(E) | i,求各规则的,Select,集如下,:,1,Select(E,TE,)=,First(TE,)=(,i,2,Select(E,+TE,)=,First(+TE,)=+,3,Select(E,-TE,)=First(-TE)=-,4,Select(E,)=,Follow(E,)=),#,5,Select(T,FT,)=,First(FT,)=(,i,6,Select(T,*FT,)= First(*FT)=*,7,Select(T,/FT,)=First(/FT)=/,8,Select(T,)=,Follow(T,)=+,-,),#,9,Select(F,PF,)=,First(PF,)=(,i,10,Select(,F,PF,)=,First(,PF,)=,11,Select(F,)=,Follow(F,)=+,-,*,/,),#,12,Select(,P,(E,),)=,First(,(E,),)=,(,13,Select(,P,i,)=,First(,i,)=,i,LL,（,1,）分析表如下：,i,+,-,*,/,(,),#,E,ET/R,ET/R,E,ET/C,ET/C,/R,/R,T,TF/R,TF/R,T,/R,/R,TF/C,TF/C,/R,/R,F,FP/R,FP/R,F,/R,/R,/R,/R,/R,FP/C,/R,P,/C,)E/C,),/C,#,SUCC,对输入符号串,i*i,i-i/i,#,分析,分析栈 余留输入串 动作,#E i*i,i-i/i,#,ET/R,#ET i*i,i-i/i,#,TF/R,#ETF i*i,i-i/i,# FP/R,#ETFP i*i,i-i/i,#,/C,#ETF *i,i-i/i,#,/R,#ET *i,i-i/i,# TF/C,#ETF i,i-i/i,# FP/R,#ETFP i,i-i/i,#,/C,#ETF,i-i/i,# FP/C,#ETFP,i-i/i,#,/C,#ETF,-,i/i,#,/R,#ET,-,i/i,#,/R,#E,-,i/i,# ET/C,#ET,i/i,# TF/R,#ETF,i/i,#,FP/R,#ETFP,i/i,#,/C,#ETF,/i#,/R,#ET,/i# TF/C,#ETF,i#,F,P/R,#ETFP,i#,/C,#ETF,#,/R,#ET,#,/R,#E,#,/R,#,# SUCC,5.11,对下面的文法,GE,：,E,TE,E,+E|,TFT,TT|,FPF,F*F |,P(E) |,a|b,（,1,）计算这个文法的,select,集；,（,2,）证明这个文法是,LL(1),文法；,（,3,）构造文法,GE,的,LL(1),分析表；,（,4,）构造它的递归下降分析程序。,解：,(1),各规则的,Select,集如下：,1,Select(E,TE,) =,First(,TE,)=(,a,b,2,Select(E,+E,) =,First(,+E,)=+,3,Select(E,) =,Follow(E,)=#,),4,Select(,TFT,) =,First(,FT,)=(,a,b,5,Select(,TT,) =,First(,T,)=(,a,b,6,Select(,T,)=,Follow(,T,)=#,+,),7,Select(,FPF,) =,First(,PF,)=(,a,b,8,Select(,F,*F,) =First(,*F,)=*,9,Select(,F,) =,Follow(F,)=#,+,),(,a,b,10,Select(,P(E,),) =,First(,(E,),)=(,11,Select(,Pa,) =,First(,a,)=a,12,Select(,Pb,) =,First(,b,)=b,(2),证明：,因为：,select(E,+E,),select(E,) =,select(,TT,),select(,T,) =,select(,F,*F,),select(,F,),=,select(,P(E,),),select(,Pa,),select(,Pb,) =,即每个非终结符的不同规则具有不相交的,select,集，所以该文法是,LL,（,1,）文法,a,b,(,),+,*,#,E,ET/R,ET/R,ET/R,E,/R,E/C,/R,T,TF/R,TF/R,TF/R,T,T/R,T/R,T/R,/R,/R,/R,F,FP/R,FP/R,FP/R,F,/R,/R,/R,/R,/R,F/C,/R,P,/C,/C,)E/C,),/C,#,SUCC,5.13,设有文法,GS:,SaBc|bAB,AaAb|b,Bb,|,(1),构造其,LL(1),分析表,(2),分析符号串,baabbb,是否为该文法的句子。,解,: (1),各规则的,Select,集如下：,Select(S,aBc,) =,First(,aBc,)=a,Select(S,bAB,) =,First(,bAB,)=b,Select(,A,aAb,) =,First(aAb,)=a,Select(,A,b,) =,First(,b,)=b,Select(,B,b,) =,First(,b,)=b,Select(,B,) =,Follow(,B,)=#,c,a,b,c,#,S,cB,/C,BA/C,A,bA,/C,/C,B,/C,/R,/R,c,/C,b,/C,#,SUCC,LL(1),分析表如下：,(2),分析符号串,baabbb,分析栈,输入串,动作,#S,baabbb,#,BA/C,#BA,aabbb,#,bA,/C,#,BbA,abbb,#,bA,/C,#,BbbA,bbb,#,/C,#,Bbb,bb#,/C,#Bb,b#,/C,#B,#,c/R,#,#,SUCC,
展开阅读全文