课外训练答案.docVIP

1试构造与下列文法G[S]等价的无左递归文法。 G[S]: S→Sa|Nb|c N →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 →begin d : X end X →d : X | sY Y→: sY | ( 做出该文法LL(1)分析表。 LL(1)分析表为： begin d : end s e # P →begin d : X end X →d : X →sY Y →: sY →e 3 设有以下文法： G[S]: S→eEfGh | g E→FSG | h F→SEc | cG | ε G→Sh |ε （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)文法吗？为什么？ 不是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-〉AB A-〉1A0|1a0 B-〉1B0|a 提取公共左因子为： 〉1A’ A’-A0|a0 改造后的文法为： S-〉AB 〉1A’ A’-A0|a0 〉1B0|a 判断文法是LL（1）文法的充要条件是：对每一个非终结符的任何两个不同产生式 〉α|β，则下述条件成立： 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 | bAB A→aAb | b B→b | ε 这道题是B→ε不是B→e特此改正 构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子。 分析表为： a b c # S →aBc →bAB A →aAb →b B →b →ε →ε 分析栈 余留符号串 产生式 #S baabbb# S- bAB #BAb baabbb# #BA aabbb# A →aAb #BbAa aabbb# #BbA abbb# A →aAb #Bbb