下载文档原格式
第4章语法分析习题答案1．判断（1）由于递归下降分析法比较简单，因此它要求文法不必是LL(1)文法。
(× )LL(1)文法。
(× )（3）任何LL(1)文法都是无二义性的。
(√)（4）存在一种算法，能判定任何上下文无关文法是否是LL(1) 文法。
(√)(× )（6）每一个SLR(1)文法都是LR(1)文法。
(√)（7）任何一个LR(1)文法，反之亦然。
(× )（8）由于LALR是在LR(1)基础上的改进方法，所以LALR(× )（9）所有LR分析器的总控程序都是一样的，只是分析表各有不同。
(√)（10）算符优先分析法很难完全避免将错误的句子得到正确的归约。
(√)2．文法G[E]：E→E+T|TT→T*F|FF→(E)|i试给出句型(E+F)*i的短语、简单短语、句柄和最左素短语。
答案：画出语法树，得到：短语: (E+F)*i ，(E+F) ，E+F ，F ，i简单短语: F ，i句柄: F最左素短语: E+F3．文法G[S]：S→SdT | TT→T<G | GG→(S) | a试给出句型(SdG)<a的短语、简单短语、句柄和最左素短语。
答案：画出语法树，得到：短语：(SdG)<a 、（SdG） 、SdG 、G 、a简单(直接)短语：G 、a句柄：G最左素短语：SdG4．对文法G[S]提取公共左因子进行改写，判断改写后的文法是否为LL(1)文法。
S→if E then S else SS→if E then SS→otherE→b答案：提取公共左因子；文法改写为：S→if E then S S'|otherS'→else S|E→bLL(1)文法判定：① 文法无左递归② First(S)={if,other}, First(S')={else, }First(E)={b}Follow(S)= Follow(S')={else,#}Follow(E)={then}First(if E then S S')∩First(other)=First(else S)∩First( )=③First(S')∩Follow(S')={else}不为空集故此文法不是LL(1)文法。
第五章习题5-1设有文法G[S] ：S→A/A→aA∣ AS∣/(1)找出部分符号序偶间的简单优先关系。
(2)验证 G[S] 不是简单优先文法。
5-2对于算符文法G[S] ：S→E E→ E-T∣ T T→T*F∣F F→ -P∣P P→ (E)∣i(1)找出部分终结符号序偶间的算符优先关系。
(2)验证 G[S] 不是算符优先文法。
5-3 设有文法G′[E] ：E→E E→E+T |T1T →T T→T*F|F F→(E)|i11111其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i ）进行简单优先分析的过程。
题图 5-3 文法 G′ [E] 的简单优先矩阵5-4设有文法G[E]：E→E+T|TT→T*F|FF→(E)|i其相应的算符优先矩阵如题图5-4 所示。
试给出对符号串（i+i ）进行算符优先分析的过程。
(i*+)#(○○○○○＜＜＜＜＝i○○○○＞＞＞＞○○○○○○*＜＜＞＞＞＞○○○○○○+＜＜＜＞＞＞○○○○)＞＞＞＞○○○○#＜＜＜＜题图 5-4文法 G[E] 的算符优先矩阵5-5对于下列的文法，试分别构造识别其全部可归前缀的DFA和 LR(0) 分析表，并判断哪些是LR(0) 文法。
(1)S →aSb∣ aSc∣ ab(2)S →aSSb∣ aSSS∣c(3)S →AA→Ab∣ a5-6下列文法是否是SLR(1)文法？若是，构造相应的SLR(1) 分析表，若不是，则阐明其理由。
(1) S →Sab∣ bR R→S∣a(2) S →aSAB∣ BA A→aA∣ B B→ b(3) S →aA∣bB A→cAd∣εB→cBdd∣ε5-7对如下的文法分别构造LR(0) 及 SLR(1) 分析表，并比较两者的异同。
S→cAd∣ b A→ASc∣a5-8对于文法G[S]:S→A A→BA∣εB→ aB∣ b(1)构造 LR(1) 分析表；(2)给出用LR(1)分析表对输入符号串abab 的分析过程。
第四章 词法分析1．构造下列正规式相应的DFA ：(1) 1(0|1)*101(2) 1(1010*| 1(010)*1)*0 (3) a((a|b)*|ab *a)*b (4) b((ab)*| bb)*ab 解：(1)1(0|1)*101对应的NFA 为下表由子集法将NFA 转换为DFA ：(2)1(1010*| 1(010)*1)*0对应的NFA 为 10,1下表由子集法将NFA转换为DFA：(3)a((a|b)*|ab *a)*b (略) (4)b((ab)*| bb)*ab (略)2．已知NFA=（{x,y,z},{0,1},M,{x},{z}）其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)=φ,M(z,1)={y},构造相应的DFA 。
解：根据题意有NFA 图如下下表由子集法将NFA 转换为DFA ：0，1下面将该DFA最小化：(1)首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}(2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。
由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。
有P21={C,F},P22={B}。
(3)区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。
(4)由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。
(5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。
所以最小化的DFA如下：3.将图确定化：1101111解：下表由子集法将NFA 转换为DFA ：4.把图的(a)和(b)分别确定化和最小化：(a) (b)解： (a):下表由子集法将NFA 转换为DFA ：0，1a可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B 等价，可将DFA 最小化，即：删除B ，将原来引向B 的引线引向与其等价的状态A ，有图(a2)。
第4章习题解答：1，2，3，4 解答略！5. 解答：(1)× (2)√ (3)× (4)√ (5)√ (6)√(7)×(8)×6. 解答：(1)A：④ B：③ C：③ D：④ E：②(2)A：④ B：④ C：③ D：③ E：②7.解答：(1) 消除给定文法中的左递归，并提取公因子：bexpr→bterm {or bterm }bterm→bfactor {and bfactor}bfactor→not bfactor | (bexpr) | true |false(2) 用类C语言写出其递归分析程序:void bexpr();{bterm();WHILE(lookahead =='or') { match ('or');bterm();}}void bterm();{bfactor();WHILE(lookahead =='and'){ match ('and');bfactor();}} void bfactor();{if (llokahead=='not') then {match ('not');bfactor();}else if(lookahead=='(') then {match (‘(');bexpr();match(')');}else if(lookahead =='true')then match ('true) else if (lookahead=='false')then match ('false');else error;}8. 解答：消除所给文法的左递归，得G'：S →(L)|aL → SL'L'→ ,SL' |实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G'有：First(S) = { ( , a ) Follow(S) = { ) , , , #}First(L) = { ( , a ) Follow(L) = { ) }First(L') = { ,} Follow(L') = { ) }按以上结果，构造预测分析表M如下：文法G'是LL(1)的，因为它的LL(1)分析表不含多重定义入口。
第4章练习P72作业布置：P723，7，9，11提示1：判断两个正规式是否相等，应判断两个正规式所产生的正规集是否一样。
完成此项任务需要经过四个阶段：第一，画出正规式的NFA；第二，由NFA变换到DFA；第三，将DFA最小化；第四，画出最小化DFA的有限自动机。
如果要判断的正规式的最小化DFA的有限自动机是一样的，则正规式等价；反之，则不等价。
提示2：构造正规表达式的最小化的DFA方法是：首先，按规则将正规表达式用NFA表示；其次，使用ε-closure(Move())将NFA转变为DFA；最后使用子集法将DFA最小化。
对于这类题目要多做练习，熟能生巧。
3.将下图确定化：解：下表由子集法将NFA 转换为DFA ：7、给文法G[S]： S →aA|bQ A →aA|bB|bB →bD|aQ0，10，1Q →aQ|bD|b D →bB|aA E →aB|bFF →bD|aE|b构造相应的最小的DFA 。
解：由于从S 出发任何输入串都不能到达状态E 和F ，所以，状态E ，F 为多余的状态，不予考虑。
这样，可以写出文法G[S]对应的NFA M ：NFA M={k, Σ, f, S, Z}K={S, A, B, Q, D, Z} S={S} Z={Z} F(S, a)=A f(S, b)=Q F(A, a)=A f(A, b)=B f(A,b)=ZF(B, b)=D f(B, a)=QF(Q, a)=Q f(Q, b)=D f(Q,b)=Z F(D, b)=B f(D, a)=A NFA M 的状态转换图为：下表由子集法将NFA 转换为DFA ：a由上表可知：(1)因为C、D是DFA的终态，其他是非终态，可将状态集分成两个子集：P1={S, A, B, E, F}，P2={C, D}。
(2)因为{A, B}b={C, D}为终态，{S, E, F}b={B, E, F}为非终态，所以P1可划分为：P11={S, E, F}，P12={A, B}。
第四章语义分析和中间代码生成4.1 完成下列选择题：(1) 四元式之间的联系是通过实现的。
a. 指示器b. 临时变量c. 符号表d. 程序变量(2) 间接三元式表示法的优点为。
a. 采用间接码表，便于优化处理b. 节省存储空间，不便于表的修改c. 便于优化处理，节省存储空间d. 节省存储空间，不便于优化处理(3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。
a. ┐AB∨∧CD∨b. A┐B∨CD∨∧c. AB∨┐CD∨∧d. A┐B∨∧CD∨(4) 有一语法制导翻译如下所示：S→bAb {print″1″}A→(B {print″2″}A→a {print″3″}B→Aa) {print″4″}若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。
a. 32224441 b. 34242421c. 12424243d. 34442212【解答】(1) b (2) a (3) b (4) b4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。
【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。
也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。
用语法制导翻译(SDTS)生成中间代码的要点如下：(1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。
(2) 注意地址返填问题。
(3) 不要遗漏必要的处理，如无条件跳转等。
例如下面的程序段：if (i>0) a=i+e-b*d; else a=0;在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。
此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。
第四章1.设字母表∑={0，1}，给出∑上的正规式r=(0|10)*，请完成以下任务：1) 构造NFA M`，使得L（M`）=L（r）；2) 将NFA M`确定化、最小化，得到最简DFA M，使得L（M）=L（M`）。
解：1）M`③2) 1令T0=-closure(1)={1,2,4}, T0未被标记，加入到子集族C中2 标记T0，Move(T0,0)={2},-closure(Move(T0,0))={2,4}=T1,T1未被标记，加入到子集族C中Move(T0,1)={3},-closure(Move(T0,1))={3}=T2,T2未被标记，加入到子集族C中3 标记T1，Move(T1,0)={2},-closure(Move(T1,0))={2,4}=T1,Move(T1,1)={3},-closure(Move(T1,1))={3}=T2,4标记T2，Move(T2,0)={2},-closure(Move(T2,0))={2,4}=T1,Move(T2,1)=,-closure(Move(T2,1))=,化简后为：2.已知正规文法G1(S为开始符号)G1: S→0A|1BA→1S|1B→0S|01）该文法产生语言是什么？请用正规式表示；2）构造最简的确定有限自动机DFA，并画出状态转换图。
解：1)S=0A|1BS=(0(1S|1))|(1(0S|0))S=(01(S|))|(10(S|))S=(01|10)(S|)S=(01|10)(01|10)*2)NFA为：②③④ɛɛ①ɛ 1 0 ɛ⑤⑥⑦ɛNFA转化为DFA：1令T0=-closure(1)={1,2,5}, T0未被标记，加入到子集族C中2 标记T0，Move(T0,0)={3},-closure(Move(T0,0))={3}=T1,T1未被标记，加入到子集族C中Move(T0,1)={6},-closure(Move(T0,1))={6}=T2,T2未被标记，加入到子集族C中3 标记T1，Move(T1,0)=,-closure(Move(T1,0))=,Move(T1,1)={4},-closure(Move(T1,1))={4,8,9,10,13,17}=T3,T3未被标记，加入到子集族C中4标记T2，Move(T2,0)={7},-closure(Move(T2,0))={ 4,8,9,10,13,17}=T4,T4未被标记，加入到子集族C中Move(T2,1)=,-closure(Move(T2,1))=,5标记T3，Move(T3,0)={11},-closure(Move(T3,0))={11}=T5,T5未被标记，加入到子集族C中Move(T3,1)={14},-closure(Move(T3,1))={14}=T6,T6未被标记，加入到子集族C中6标记T4，Move(T4,0)={11},-closure(Move(T4,0))={11}=T5,Move(T4,1)={14},-closure(Move(T4,1))={14}=T6,7标记T5，Move(T5,0)=,-closure(Move(T5,0))=,Move(T5,1)={12},-closure(Move(T5,1))={9,10,12,13,16,17}=T7,T7未被标记，加入到子集族C中8标记T6，Move(T6,0)={15},-closure(Move(T6,0))={ 9,10,13,15,16,17}=T8,T8未被标记，加入到子集族C中Move(T6,1)=,-closure(Move(T6,1))=,9标记T7，Move(T7,0)={11},-closure(Move(T7,0))={11}=T5,Move(T7,1)={14},-closure(Move(T7,1))={14}=T6,10标记T8，Move(T8,0)={11},-closure(Move(T8,0))={11}=T5,Move(T8,1)={14},-closure(Move(T8,1))={14}=T6,则DFA为：②①1化简后为：②①13.将R=a(a|d)*转换成相应的正规文法。
第四章习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a*(1)给出这个串的一个最左推导S -> S S *-> S S + S *-> a S + S *-> a a + S *-> aa + a*(3)给出这个串的一棵语法分析树习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。
它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆：rexpr→ rexpr + rterm | rtermrterm→rterm rfactor | rfactorrfactor→ rfactor * | rprimaryrprimary→a | b1)对这个文法提取公因子2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？3)提取公因子之后，原文法中消除左递归4)得到的文法适用于自顶向下的语法分析吗？解1)提取左公因子之后的文法变为rexpr→ rexpr + rterm | rtermrterm→rterm rfactor | rfactorrfactor→ rfactor * | rprimaryrprimary→a | b2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法3)消除左递归后的文法rexpr -> rterm rexpr’rexpr’-> + rterm rexpr’|εrterm-> rfactor rterm’rterm’-> rfactor rterm’|εrfactor-> rprimay rfactor’rfactor’-> *rfactor’|εrprimary-> a | b4)该文法无左递归，适合于自顶向下的语法分析习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。
可能要先对文法进行提取左公因子或消除左递归(3)S->S(S)S|ε(5)S->(L)|a L->L,S|S解(3)①消除该文法的左递归后得到文法S->S’S’->(S)SS’|ε②计算FIRST和FOLLOW集合FIRST(S)={(,ε} FOLLOW(S)={),$}FIRST(S’)={(,ε} FOLLOW(S’)={),$}③构建预测分析表(5)①消除该文法的左递归得到文法S->(L)|aL->SL’L’->,SL’|ε②计算FIRST与FOLLOW集合FIRST(S)={(,a} FOLLOW(S)={ ),, ,$}FIRST(L)={(,a} FOLLOW(L)={ ) }FIRST(L’)={,,ε} FOLLOW(L’)={ ) }③构建预测分析表习题4.4.4 计算练习4.2.2的文法的FIRST和FOLLOW集合3)S→S(S)S|ε5)S→(L)|a,L→L,S|S解：3)FIRST(S)={ ε,( } FOLLOW(S)={ (,),$ }5)FIRST(S)={ (,a } FOLLOW(S)={ ),,,$ }FIRST(L)={ (,a } FOLLOW(L)={ ),, }习题4.6.2为练习4.2.1中的增广文法构造SLR项集，计算这些项集的GOTO函数，给出这个文法的语法分析表。
编译原理第4章答案第四章词法分析1．构造下列正规式相应的DFA ：(1) 1(0|1)* 101 (2) 1(1010* | 1(010)* 1)* 0 (3) a((a|b)*|ab *a)* b (4) b((ab)* | bb)*ab 解：(1)1(0|1)*101对应的NFA 为(2)1(1010* | 1(010)* 1)* 0对应的NFA 为下表由⼦集法将NFA 转换为DFA ：0 0,1(3)a((a|b)*|ab*a)* b (略)(4)b((ab)* | bb)* ab (略)2．已知NFA=（{x,y,z},{0,1},M,{x},{z}）其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)=φ,M(z,1)={y},构造相应的DFA。
解：根据题意有NFA图如下0，1 下表由⼦集法将NFA转换为DFA：下⾯将该DFA最⼩化：(1)⾸先将它的状态集分成两个⼦集：P1={A,D,E},P2={B,C,F}(2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。
由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,⽽D，E不等价（见下步），从⽽B与C，F可以区分。
有P21={C,F},P22={B}。
(3)区分P1:由于A，E输⼊0到终态，⽽D输⼊0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。
(4)由于F(A,0)=B,F(E,0)=F,⽽B，F不等价，所以A，E可以区分。
(5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。
所以最⼩化的DFA如下：3.将图4.16确定化：图4.16解：下表由⼦集法将NFA转换为DFA：14.把图4.17的(a)和(b)分别确定化和最⼩化：(a) (b)解： (a):下表由⼦集法将NFA 转换为DFA ：可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B 等价，可将DFA 最⼩化，即：删除B ，将原来引向B 的引线引向与其等价的状态A ，有图(a2)。
蒋⽴源编译原理第三版第四章习题与答案第4章习题14-1 消除下列⽂法的左递归性。
(1) S→SA|A A→SB|B|(S)|( ) B→[S]|[ ](2) S→AS|b A→SA|a(3) S→(T)|a|ε T→S|T,S4-2 对于如下⽂法，求各候选式的FIRST集和各⾮终结符号的FOLLOW集。
S→aAB|bA|ε A→aAb|ε B→bB|ε4-3 验证下列⽂法是否为LL(1)⽂法。
(1) S→AB|CDa A→ab|c B→dE|εC→eC|ε D→fD|f E→dE|ε(2) S→aABbCD|ε A→ASd|ε B→SAc|eC|εC→Sf|Cg|ε D→aBD|ε4-4 对于如下的⽂法G[S]：S→Sb|Ab|bA→Aa|a(1) 构造⼀个与G等价的LL(1)⽂法G′[S]；(2) 对于G′[S]，构造相应的LL(1)分析表；(3) 利⽤LL(1)分析法判断符号串aabb是否是⽂法G[S]的合法句⼦。
4-5 设已给⽂法S→SaB|bB A→S|a B→Ac(1) 构造⼀个与G等价的LL(1)⽂法G′[S]；(2) 对于G′[S]，构造相应的LL(1)分析表；(3) 利⽤LL(1)分析法判断符号串bacabc是否是⽂法G[S]的合法句⼦。
第4章习题答案4-1 解：(1) ⽂法G[S]中的S，A都是间接左递归的⾮终结符号。
将A产⽣式的右部代⼊产⽣式S→A中，得到与原⽂法等价的⽂法G′[S]：S→SA|SB|B|(S)|( )A→SB|B|(S)|( )B→[S]|[ ]⽂法G′[S]中的S是直接左递归的⾮终结符号，则消除S产⽣式的直接递归性后，我们便得到了与原⽂法等价且⽆任何左递归性的⽂法G"[S]：S→BS′|(S)S′|( )S′A→SB|B|(S)|( )B→[S]|[ ](2) ⽂法G[S]中的S，A都是间接左递归的⾮终结符号。
将A产⽣式代⼊产⽣式S→AS中，得到与原⽂法等价的⽂法G′[S]：S→SAS|aS|bA→SA|a⽂法G′[S]中的S是直接左递归的⾮终结符号，则消除S产⽣式的直接递归性后，我们便得到了与原⽂法等价且⽆任何左递归性的⽂法G"[S]：S→aSS′|bS′S′→ASS′|εA→SA|a(3) ⽂法G[S]中的T是直接左递归的⾮终结符号。
编译原理第4章测试卷编译原理2014—2015学年第二学期第四单元测试试卷（闭卷考试）时间：45分钟满分：100分姓名班级出题人班级软件12-4题目一二三四五总分得分一、选择题（5*2分）（每题1分，共10分）1. 下列文法中，_______是LL(1)文法。
A. S→aSb|abB. S→ab|SabC. S→aS|bD. S→aS|a2. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于分析法。
A. 自左至右B. 自顶向下C. 自底向上D. 自右向左3. 自上而下分析面临的四个问题中，不包括。
A. 需消除左递归；B. 存在回朔；C. 虚假匹配；D. 寻找可归约串4. 语法分析器接收以________为单位的输入，并产生有关信息供以后各阶段使用。
A. 表达式；B. 产生式； C 单词；D. 语句；5. 自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号（根结点）出发，________。
A. 为输入串寻找最右推导；B. 为输入串寻找最左直接子树；C. 为输入串建立最右直接子树；D. 为输入串寻找最左推导；二、简答题（2*10分）（每题10分，共20分）6. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？7. 为什么要消除回溯？三、分析题（4题共70分）8.设有文法G[S]：S→ABA→bB|AaB→Sb|a试消除该文法的左递归。
（15分）9.已知文法G[E]：G[E]：E→E+T|TT→T*F|FF→i|(E)请按递归子程序法为其构造语法分析程序。
（20分）10．文法G[M]是否是LL(1)文法，说明理由。
（15分）G[M]：M→TBT→Ba|εB→Db|eT|εD→d|ε11. 已知文法G[S]：S → uBDzB → Br | wD → EFE → y | ?F → x | ?(1) 求每个非终结符的FIRST和Follow集。
(2) 构造这个文法的LL(1)分析表(3) 说明这个文法不是LL(1)的;(3) 尽可能少地修改此文法,使其成为能产生相同语言的LL(1)文法.（20分）第四章答案1-5B D DC D6. 答：词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子。
