编译原理教程课后习题答案——第三章

第三章语法分析3.1完成下列选择题：(1)文法G：S→xSx|y所识别的语言是。a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*(2)如果文法G是无二义的，则它的任何句子α。a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同(3)采用自上而下分析，必须。a.消除左递a.必有ac归b.消除右递归c.消除回溯d.提取公共左因子(4)设a、b、c是文法的终结符，且满足优先关系ab和bc，则。b.必有cac.必有bad.a～c都不一定成立(5)在规范归约中，用来刻画可归约串。a.直接短语b.句柄c.最左素短语d.素短语(6)若a为终结符，则A→α·aβ为项目。a.归约b.移进c.接受d.待约(7)若项目集Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是。a.LALR文法b.LR(0)文法c.LR(1)文法d.SLR(1)文法(8)同心集合并有可能产生新的冲突。a.归约b.“移进”/“移进”c.“移进”/“归约”d.“归约”/“归约”【解答】(1)c(2)a(3)c(4)d(5)b(6)b(7)d(8)d3.2令文法G[N]为G[N]:N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G[N]的语言L(G[N])是什么?(2)给出句子0127、34和568的最左推导和最右推导。【解答】(1)G[N]的语言L(G[N])是非负整数。(2)最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。【解答】由文法G[S]：S→aSb|Sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。图3-1句子aabbbb对应的两棵不同语法树因此，文法G[S]为二义文法(对句子abbb也可画出两棵不同语法树)。3.4已知文法G[S]为S→SaS|ε，试证明文法G[S]为二义文法。【解答】由文法G[S]：S→SaS|ε，句子aa的语法树如图3-2所示。图3-2句子aa对应的两棵不同的语法树由图3-2可知，文法G[S]为二义文法。3.5按指定类型，给出语言的文法。(1)L={aibj|j＞i≥0}的上下文无关文法；(2)字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；(3)由相同个数a和b组成句子的无二义文法。【解答】(1)由L={aibj|j＞i≥0}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→b型的产生式，用以保证b的个数多于a的个数。因此，所求上下文无关文法G[S]为G[S]：S→aSb|Sb|b(2)为了构造字母表Σ={a,b}上同时只有奇数个a和奇数个b的所有串集合的正规式，我们画出如图3-3所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B；而由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发经过奇数个a到达终态C。由图3-3可直接得到正规文法G[S]如下：G[S]：S→aA|bBA→aS|bC|bB→bS|aC|aC→bA|aB|ε图3-3习题3.5的DFASaSbaSbSbbaSbSbSaSbbSSSaSSaSSSaSSa(a)(b)SCABaabbbbaa(3)我们用一个非终结符A代表一个a(即有A→a)，用一个非终结符B代表一个b(即有B→b)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个B，出现一个b时则相应出现一个A。假定已推导出bA，如果下一步要推导出连续两个b时，则应有bAbbAA。也即为了保证b和A的个数一致，应有A→bAA；同理有B→aBB。此外，为了保证递归地推出所要求的ab串，应有S→aBS和S→bAS。由此得到无二义文法G[S]为G[S]：S→aBS|bAS|εA→bAA|aB→aBB|b3.6有文法G[S]:S→aAcB|BdA→AaB|cB→bScA|b(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)写出句子acabcbbdcc的最左推导过程。【解答】(1)分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3-4的(a)、(b)所示。图3-4习题3.6的语法树(a)aAaBcbbdcc;(b)aAcbBdcc对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足A→AaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足A→C右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。(2)句子acabcbbdcc的最左推导如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc3.7对于文法G[S]:S→(L)|aS|aL→L,S|S(1)画出句型(S,(a))的语法树；(2)写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。【解答】(1)句型(S,(a))的语法树如图3-5所示。图3-5句型(S,(a))的语法树AaBbScABAcaSBdbbScABAcaSBdc(a)(b)c(L)SL,SS(L)Sa(2)由图3-5可知：短语：S、a、(a)、S,(a)、(S,(a))；直接短语：a、S；句柄：S；素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即：#⋖(⋖，⋖(⋖a⋗)⋗)⋗#因此，素短语为a。3.8下述文法描述了C语言整数变量的声明语句：G[D]:D→TLT→int|long|shortL→id|L,id(1)改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2)分别用上述文法G[D]和改造后的文法G[D′]为输入序列inta,b,c构造分析树。【解答】(1)消除左递归后，文法G[D′]如下：D→TLT→int|long|shortL→idL图3-6两种文法为inta,b,c构造的分析树(a)文法G(D)；(b)文法G′(D)3.9考虑文法G[S]:S→(T)|a+S|aT→T,S|S消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。【解答】消除文法G[S]的左递归：S→(T)|a+S|aT→ST′T′→,ST′|ε提取公共左因子：S→(T)|aS′S′→+S|εT→ST′T′→,ST′|ε改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：voidmatch(tokent){if(lookahead==t)lookahead=nexttoken;elseerror();}voidS(){L,cLDTintL,ba,bLDTintaL′L′,cL′(a)(b)if(lookahead==′a′)match(′a′);elseif(lookahead==′(′){match(′(′);T();voidS′(){if(lookahead==′+′){match(′+′);S();}}voidT(){S();T′();}voidT′(){if(lookahead==′,′){match(′,′);S();T′();}}3.10已知文法G[A]:A→aABl|aB→Bb|d(1)试给出与G[A]等价的LL(1)文法G[A′]；(2)构造G[A′]的LL(1)分析表；(3)给出输入串aadl#的分析过程。【解答】(1)文法G[A]存在左递归和回溯，故其不是LL(1)文法。要将G[A]改造为LL(1)文法，首先要消除文法的左递归，即将形如P→Pα|β的产生式改造为P→βP′P→αP′|ε来消除左递归。由此，将产生式B→Bb|d改造为B→dB′B′→bB′|ε其次，应通过提取公共左因子的方法来消除G[A]中的回溯，即将产生式A→aABl|a改造为A→aA′A′→ABl|ε最后得到改造后的文法为G[A′]：A→aA′A′→ABl|εB→dB′B′→bB′|ε求得：FIRST(A)={a}FIRST(A′)={a,ε}FIRST(B)={d}FIRST(B′)={b,ε}对文法开始符号A，有FOLLOW(A)={#}。由A′→ABl得FIRST(B)\{ε}FOLLOW(A)，即FOLLOW(A)={#,d}；由A′→ABl得FIRST(′l′)FOLLOW(B)，即FOLLOW(B)={l}；由A→aA′得FOLLOW(A)FOLLOW(A′)，即FOLLOW(A′)={#,d}；由B→dB′得FOLLOW(B)FOLLOW(B′)，即FOLLOW(B′)={l}。对A′→ABl来说，FIRST(A)∩FOLLOW(A′)={a}∩{#,d}=Φ，所以文法G′[A]为所求等价的LL(1)文法。(2)构造预测分析表的方法如下：①对文法G[A′]的每个产生式A→α执行②、③步。②对每个终结符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α为含有首字符a的候选式或为唯一的候选式。③若ε∈FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A→ε加入到M[A,b]中。把所有无定义的M[A,a]标记上“出错”。由此得到G[A′]的预测分析表，见表3-1。表3-1预测分析表(3)输入串aadl的分析过程见表3-2。表3-2输入串aadl的分析过程abld#AA→aA′A′A′→ABlA′→εA′→εBB→dB′B′B′→bB′B′→ε符号栈当前输入符号输入串说明#Aaadl#弹出栈顶符号A并将A→aA′产生式右部反序压栈#A′aaadl#匹配，弹出栈顶符号a并读出下一个输入符号a#A′adl#弹出栈顶符号A′并将A′→ABl产生式右部反序压栈#lBAadl#弹出栈顶符号A并将A→aA′产生式右部反序压栈#lBA′aadl#匹配，弹出栈顶符号a并读出下一个输入符号d#lBA′dl#由A′→ε仅弹出栈顶符号A′#lBdl#弹出栈顶符号B并将B→dB′产生式右部反序压栈#lB′ddl#匹配，弹出栈顶符号d并读出下一个输入符号l#lB′l#由B′→ε仅弹出栈顶符号B′#ll#匹配，弹出栈顶符号l并读出下一个输入符号###匹配，分析成功3.11将下述文法改造为LL(1)文法：G[V]:V→N|N[E]E→V|V+EN→i【解答】LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而文法G[V]中含有回溯，所以先消除回溯，得到文法G[V′]：G[V′]：V→NV′V′→ε|[E]E→VE′E′→ε|+EN→i一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A→α|β有下面的条件成立：(1)FIRST(α)∩FIRST(β)=Φ；(2)假若βε，则有FIRST(α)∩FOLLOW(A)=Φ。即求出G[V′]的FIRSTVT和LASTVT集如下：FIRST(N)=FIRST(V)=FIRST(E)={i}FIRST(V′)={[,ε}FIRST(E′)={+,ε}FOLLOW(V)={#}由V′→…E]得FIRST(′)′)FOLLOW(E)，即FOLLOW(E)={]}；由V→NV′得FIRST(V′)\{ε}FOLLOW(N)，即FOLLOW(N)=