第五章课外训练答案.doc

1试构造与下列文法GS等价的无左递归文法。 GS: SSa|Nb|c N Sd|Ne|f 解：将非终结符按SN的循序排列 SSa|Nb|c 存在直接左递归，消除左递归为：S-NbS|cSS-aS|N Sd|Ne|f中Sd中S的顺序在N之前需用S的右部代替S，则N-（NbS|cS） d|Ne|f整理为：N-NbSd| Ne|cSd|f存在直接左递归，消除左递归为： N- cSdN|fN N-bSdN|eN|等价的无左递归文法为：S NbS |cS S aS|e N cSdN |fN N eN |bSdN | e 2：文法G的规则集为; P begin d : X end X d : X | sY Y: sY | e做出该文法LL(1)分析表。 LL(1)分析表为：begind:endse#Pbegin d : X endXd : XsYY: sYe3 设有以下文法：GS: SeEfGh | g EFSG | h FSEc | cG | GSh |（1） 求出该文法每一个非终结符的FOLLOW集。 # h f c h e g Follow(S) Follow(E) Follow(G) Follow(F) First(S) First(G) First(E) e g e g c 根据关系图：Follow(S)=#,h,e,g,c,f Follow(E)=f,c Follow(G)=f,c,h,e,g Follow(F)=e,g（2） 它是LL(1)文法吗？为什么？不是FSEc | cG | First(SEc)=e,g 因为 F，而Follow(F)=e,g First(SEc) Follow(F)=e,g，不为空集，所以不是LL(1)文法4：给出语言L=1na0n1ma0m|n0, m=0 的LL(1)文法GS并说明其理由。 文法为：S-AB A-1A0|1a0 B-1B0|a 提取公共左因子为：A- 1A A-A0|a0 改造后的文法为： S-ABA- 1A A-A0|a0B- 1B0|a 判断文法是LL（1）文法的充要条件是：对每一个非终结符的任何两个不同产生式A- |，则下述条件成立： FIRST（）FIRST（）= * 若=,则FIRST（）FOLLOW（A）=由于文法不存在形如A-的产生式，所以无需求非终结符的FOLLOW集。FIRST（A）=FIRST（S）=1 FIRST（A）= FIRST（B）=1,a 对非终结符A和B有FIRST（A0）FIRST（a0）=FIRST（1B0）FIRST（a）=文法是LL(1)文法。该文法为LL(1)文法，因为左部相同，右部的符号串的First集为空集5 设有文法：GS: SaBc | bAB AaAb | b Bb | 这道题是B不是Be特此改正构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子。 分析表为：abc#SaBcbABAaAbbBb分析栈 余留符号串 产生式 #S baabbb# S- bAB#BAb baabbb#BA aabbb# A aAb#BbAa aabbb#BbA abbb# A aAb#BbbAa abbb#BbbA bbb# A-b#Bbbb bbb#Bbb bb#Bb b#B # B # # 分析成功6将GV改造为LL(1)文法 GV : VN | NE EV | V+E Ni提取公共左因子：VNVV | E EVEE | +E Ni7有文法GS: S BA ABS | d BaA | bS | c （1）证明文法为LL(1)文法。 判断文法是LL（1）文法的充要条件是：对每一个非终结符的任何两个不同产生式A-|，则下述条件成立： FIRST（）FIRST（）= * 若=,则FIRST（）FOLLOW（A）=因为无A-的产生式，所以无需求非终结符的FOLLOW集。FIRST（S）=a,b,c FIRST（B）=a,b,c FIRST（A）=a,b,c,d对于非终结符A： FIRST（BS）FIRST（d）=对于非终结符B FIRST（aA）FIRST（bS）FIRST（c） = 该文法为LL(1)文法 （2）构造LL(1)分析表。 abcd#S-BA-BA-BAABSBSBSdBaAbSc （3）写出句子adccd的分析过程分析栈 余留符号串 产生式#S adccd# S-BA#AB adccd# B-aA#AAa adccd#AA dccd# A-d#Ad dccd# #A ccd# A-BS#SB ccd# B-c#Sc ccd#S cd# S-BA#AB cd# B-c#Ac cd#A d# A-d#d d# # 分析成功 8 考虑下面文法G1:Sa| (T)TT, S | S(1) 消去G1的左递归。然后对每一个非终结符，写出不带回溯的递归子程序。 T STT, ST |改写后的文法G为： Sa| (T)T STT, ST |对每个非终结符S、T、T的递归子程序为：procedure T; begin S;Tend;procdure Tbegin if SYM=,then begin advance; S;Tendend;procedure S; begin if SYM=aor SYM=then advanceelse if SYM=(then advance else errorendelse errorend;递归过程中的advance是一个将输入指针移向下一个输入符号的子程序，SYM则代表输入指针当前所指的输入符号，error为出错诊断处理程序(2) 经改写后的文法是否是LL(1)文法？给出它的预测分析表。a,()#Sa (T)TSTSTSTT, ST9下面文法中那些是