第五章课外训练答案

1试构造与下列文法G[S]等价的无左递归文法。G[S]:S→Sa|Nb|cN→Sd|Ne|f解：将非终结符按SN的循序排列S→Sa|Nb|c存在直接左递归，消除左递归为：S-NbS’|cS’S’-aS’|εN→Sd|Ne|f中Sd中S的顺序在N之前需用S的右部代替S，则N-〉（NbS’|cS’）d|Ne|f整理为：N-〉NbS’d|Ne|cS’d|f存在直接左递归，消除左递归为：N-cS’dN’|fN’N’-bS’dN’|eN’|ε等价的无左递归文法为：SNbS’|cS’S’aS’|NcS’dN’|fN’N’eN’|bS’dN’|2：文法G的规则集为;P→begind:XendX→d:X|sYY→:sY|e做出该文法LL(1)分析表。LL(1)分析表为：begind:endse#P→begind:XendX→d:X→sYY→:sY→e3设有以下文法：G[S]:S→eEfGh|gE→FSG|hF→SEc|cG|εG→Sh|ε（1）求出该文法每一个非终结符的FOLLOW集。#hfchegFollow(S)Follow(E)Follow(G)Follow(F)First(S)First(G)First(E)egegc根据关系图：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)文法吗？为什么？不是F→SEc|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)文法G[S]并说明其理由。文法为：S-〉ABA-〉1A0|1a0B-〉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设有文法：G[S]:S→aBc|bABA→aAb|bB→b|ε这道题是B→ε不是B→e特此改正构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子。分析表为：abc#S→aBc→bABA→aAb→bB→b→ε→ε分析栈余留符号串产生式#Sbaabbb#S-bAB#BAbbaabbb##BAaabbb#A→aAb#BbAaaabbb##BbAabbb#A→aAb#BbbAaabbb##BbbAbbb#A-b#Bbbbbbb##Bbbbb##Bbb##B#B→ε##分析成功6将G[V]改造为LL(1)文法G[V]:V→N|N[E]E→V|V+EN→i提取公共左因子：V→NV’V’→ε|[E]E→VE’E’→ε|+EN→i7有文法G[S]:S→BAA→BS|dB→aA|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）=Φ对于非终结符BFIRST（aA）∩FIRST（bS）∩FIRST（c）=Φ该文法为LL(1)文法（2）构造LL(1)分析表。abcd#S-〉BA-〉BA-〉BAA→BS→BS→BS→dB→aA→bS→c（3）写出句子adccd的分析过程分析栈余留符号串产生式#Sadccd#S-BA#ABadccd#B-aA#AAaadccd##AAdccd#A-d#Addccd##Accd#A-BS#SBccd#B-c#Scccd##Scd#S-BA#ABcd#B-c#Accd##Ad#A-d#dd###分析成功8考虑下面文法G1:S→a|∧|(T)T→T,S|S(1)消去G1的左递归。然后对每一个非终结符，写出不带回溯的递归子程序。T→ST’T’→,ST’|ε改写后的文法G’为：S→a|∧|(T)T→ST’T’→,ST’|ε对每个非终结符S、T、T’的递归子程序为：procedureT;beginS;T’end;procdureT’beginifSYM=’,’thenbeginadvance;S;T’endend;procedureS;beginifSYM=’a’orSYM=’^’thenadvanceelseifSYM=’(’thenadvanceelseerrorendelseerrorend;递归过程中的advance是一个将输入指针移向下一个输入符号的子程序，SYM则代表输入指针当前所指的输入符号，error为出错诊断处理程序(2)经改写后的文法是否是LL(1)文法？给出它的预测分析表。a∧,()#S→a→∧→(T)T→ST’→ST’→ST’T’→,ST’→ε9下面文法中那些是LL(1)文法，说明理由。（1）1、S→Abc2、A→a|ε3、B→b|ε是LL(1)文法（2）S→AbA→a|B|εB→b|ε不是(3)S→ABBAA→a|εB→b|ε不是（4）S→aSe|BB→bBe|CC→cCe|d是