蒋立源-《编译原理》-西北工业大学出版社-第3版课后答案

第3章习题3-1 试构造一右线性文法,使得它与如下得文法等价S→AB A→UT U→aU|a D→bT|b B→cB|c 并根据所得得右线性文法,构造出相应得状态转换图。

3-2 对于如题图3-2所示得状态转换图(1) 写出相应得右线性文法;(2) 指出它接受得最短输入串;(3) 任意列出它接受得另外4个输入串;(4) 任意列出它拒绝接受得4个输入串。

3-3 对于如下得状态转换矩阵:(1) 分别画出相应得状态转换图;(2) 写出相应得3型文法;(3) 用自然语言描述它们所识别得输入串得特征。

3-4 将如下得NFA确定化与最小化:3-5 将如题图3-5所示得具有ε动作得NFA确定化。

题图3-5 具有ε动作得NFA3-6 设有文法G[S]:S→aA A→aA|bB B→bB|cC|c C→cC|c 试用正规式描述它所产生得语言。

3-7 分别构造与如下正规式相应得NFA。

(1) ((0* |1)(1* 0))*(2) b|a(aa*b)*b3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应得DFA。

第3章习题答案3-1 解:根据文法知其产生得语言就是:L[G]={a m b n c i| m,n,i≧1}可以构造与原文法等价得右线性文法:S→aA A→aA|bB B→bB|cC|c C→cC|c 其状态转换图如下:3-2 解:(1) 其对应得右线性文法就是G[A]:A →0D B→0A|1C C→0A|1F|1D→0B|1C E→0B|1C F→1A|0E|0(2) 最短输入串为011(3) 任意接受得四个输入串为:0110,0011,000011,00110(4) 任意拒绝接受得输入串为:0111,1011,1100,10013-3 解:(1) 相应得状态转换图为:(2) 相应得3型文法为:(ⅰ) S→aA|bS A→aA|bB|b B→aB|bB|a|b(ⅱ) S→aA|bB|a A→bA|aC|a|b B→aB|bC|b C→aC|bC|a|b(ⅲ) S→aA|bB|b A→aB|bA|a B→aB|bB|a|b(ⅳ) S→bS|aA A→aC|bB|a B→aB|bC|b C→aC|bC|a|b(3) 用自然语言描述得输入串得特征为:(ⅰ) 以任意个(包括0个)b开头,中间有任意个(大于1)a,跟一个b,还可以有一个由a,b组成得任意字符串。

编译原理3答案【篇一：编译原理试题及答案3】填空题：1、编译方式与解释方式的根本区别在于（是否生成目标代码）。

2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。

3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。

4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。

5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。

6、ll(k)分析法中，第一个l的含义是（从左到右进行分析），第二个l的含义是（每次进行最左推导），“k”的含义是（向输入串中查看k个输入符号）。

7、ll(1)分析法中，第一个l的含义是（从左到右进行分析），第二个l的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。

8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。

9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。

10、lr(0)分析法的名字中，“l”的含义是（从左到右进行分析），“r”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。

11、lr(1)分析法的名字中，“l”的含义是（从左到右进行分析），“r”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。

12、slr(1)分析法的名字中，“s”的含义是（简单的），“l”的含义是（从左到右进行分析），“r”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。

13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。

编译原理第三版课后习题答案编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。

而《编译原理》第三版是目前被广泛采用的教材之一。

在学习过程中，课后习题是巩固知识、提高能力的重要环节。

本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。

第一章：引论习题1.1：编译器和解释器有什么区别？答案：编译器将整个源程序转换为目标代码，然后一次性执行目标代码；而解释器则逐行解释源程序，并即时执行。

习题1.2：编译器的主要任务是什么？答案：编译器的主要任务是将高级程序语言转换为目标代码，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等过程。

第二章：词法分析习题2.1：什么是词法分析？答案：词法分析是将源程序中的字符序列划分为有意义的词素（token）序列的过程。

习题2.2：请给出识别下列词素的正则表达式：（1）整数：[0-9]+（2）浮点数：[0-9]+\.[0-9]+（3）标识符：[a-zA-Z_][a-zA-Z_0-9]*第三章：语法分析习题3.1：什么是语法分析？答案：语法分析是将词法分析得到的词素序列转换为语法树的过程。

习题3.2：请给出下列文法的FIRST集和FOLLOW集：S -> aAbA -> cA | ε答案：FIRST(S) = {a}FIRST(A) = {c, ε}FOLLOW(S) = {$}FOLLOW(A) = {b}第四章：语义分析习题4.1：什么是语义分析？答案：语义分析是对源程序进行静态和动态语义检查的过程。

习题4.2：请给出下列文法的语义动作：S -> if E then S1 else S2答案：1. 计算E的值2. 如果E的值为真，则执行S1；否则执行S2。

第五章：中间代码生成习题5.1：什么是中间代码？答案：中间代码是一种介于源代码和目标代码之间的表示形式，它将源代码转换为一种更容易进行优化和转换的形式。

目录P36-62P36-72P36-82P36-93P36-103P36-113P64–74P64–85P64–125 P64–147 P81–18P81–29P81–312 P133–112 P133–212 P133–314 P134–515 P164–518 P164–719 P217–119 P217–319 P218–420 P218–521 P218–621 P218–722 P219–1222 P270–924P36-6(1)L G ()1是0~9组成的数字串(2)最左推导:N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334556568最右推导:N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434886868568P36-7G(S)O N O D N S O AO A AD N→→→→→1357924680|||||||||||P36-8文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/P36-9句子iiiei 有两个语法树：S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒P36-10/**************)(|)(|S T TTS S →→***************/P36-11/*************** L1:ε||cC C ab aAb A AC S →→→ L2:bcbBc B aA A AB S ||→→→εL3:εε||aBb B aAb A AB S →→→ L4:AB B A A B A S |01|10|→→→ε ***************/第三章习题参考答案P64–7(1)101101(|)*确定化：最小化：{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,01234560123451350123451246012345601234135012345601231010==== 3012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}=====P64–8(1)01)0|1(*(2))5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*(3)******)110|0(01|)110|0(10P64–12(a)确定化：给状态编号：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123a ba b ====a(b)已经确定化了,进行最小化最小化：{{,}, {,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}10243535353524 b a baP64–14(2):(|εε给状态编号：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101====第四章P81–1(1) 按照T,S 的顺序消除左递归ε|,)(||^)(T S T TS T T a S S G '→''→→' 递归子程序： procedure S; beginif sym='a' or sym='^' then abvance else if sym='('then beginadvance;T;if sym=')' then advance;else error;endelse errorend;procedure T;beginS;'Tend;procedure 'T;beginif sym=','then beginadvance;S;'Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST('T)={,,ε}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW('T)={)}预测分析表是LL(1)文法P81–2文法：|^||)(|*||b a E P F F F P F T T T F T E E E T E →'→''→→''→+→''→εεε(1)FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεεFIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ 所以,该文法式LL(1)文法.(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' endelse errorendprocedure E';beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' endelse errorendprocedure T';beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advance else error endelse errorend;P81–3/***************(1) 是，满足三个条件。

目录P36-6 (2)P36-7 (2)P36-8 (2)P36-9 (3)P36-10 (3)P36-11 (3)P64–7 (4)P64–8 (5)P64–12 (5)P64–14 (7)P81–1 (8)P81–2 (9)P81–3 (12)P133–1 (12)P133–2 (12)P133–3 (14)P134–5 (15)P164–5 (19)P164–7 (19)P217–1 (19)P217–3 (20)P218–4 (20)P218–5 (21)P218–6 (22)P218–7 (22)P219–12 (22)P270–9 (24)P36-6(1)L G ()1是0~9组成的数字串(2)最左推导:N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334556568最右推导:N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434886868568P36-7G(S)O N O D N S O AO A AD N→→→→→1357924680|||||||||||P36-8文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiE EFT+T F FTiii*i+i+ii-i-ii+i*i*****************/P36-9句子iiiei 有两个语法树：S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒P36-10/**************)(|)(|S T TTS S →→***************/P36-11/*************** L1:ε||cC C ab aAb A AC S →→→ L2:bcbBc B aA A AB S ||→→→εL3:εε||aBb B aAb A AB S →→→ L4:AB B A A B A S |01|10|→→→ε ***************/第三章习题参考答案P64–7(1)101101(|)*1 ε ε 1 0 11 确定化：0 1 {X} φ {1,2,3} φ φ φ {1,2,3} {2,3} {2,3,4} {2,3} {2,3} {2,3,4} {2,3,4} {2,3,5} {2,3,4} {2,3,5} {2,3} {2,3,4,Y} {2,3,4,Y}{2,3,5}{2,3,4,}1 00 0 1 1 00 1 0 1 1 1 最小化：X 1 2 3 4 Y5 X Y60 12 35 4{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,012345601234513501234512460123456012341350123456012310100==== 3012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}===== 010 0 1 00 1 0 1 1 1P64–8(1)01)0|1(*(2))5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*(3)******)110|0(01|)110|0(10P64–12(a)aa,b a确定化：a b {0} {0,1} {1} {0,1} {0,1} {1} {1}{0}φ5 01 2 4 3 01φφ φ给状态编号：a b 0 1 2 1 1 2 2 0 3 333aaa b b bba最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123a ba b ====a ab bab (b)b b aa b aa bb aa a已经确定化了,进行最小化0 1 2 3 01 2 02 3 14 5最小化：{{,}, {,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}10243535353524 b a bb b aa baP64–14(1) 01 0 (2):(|)*0100 1 ε ε确定化：0 1 {X,1,Y}{1,Y}{2}1 2 01YX YX 2 1{1,Y} {1,Y} {2} {2} {1,Y} φ φφ φ 给状态编号：0 1 0 1 2 1 1 2 2 1 3 3330 1 01 1 10 最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101====1 1 1 0第四章P81–1(1) 按照T,S 的顺序消除左递归ε|,)(||^)(T S T TS T T a S S G '→''→→' 递归子程序： procedure S; beginif sym='a' or sym='^' then abvance else if sym='('0 2 13 01 3then begin advance;T;if sym=')' then advance; else error; end else error end;procedure T; begin S;'T end;procedure 'T ; beginif sym=',' then begin advance; S;'T end end; 其中:sym:是输入串指针IP 所指的符号 advance:是把IP 调至下一个输入符号 error:是出错诊察程序 (2)FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST('T )={,,ε} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW('T )={)} 预测分析表a^() , # S S a →S →^S T →()TT ST →' T ST →' T ST →''T'→T ε '→'T ST ,是LL(1)文法P81–2文法：|^||)(|*||b a E P F F F P F T T T F T E E E T E →'→''→→''→+→''→εεε(1)FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεεFIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. (3)+ * ()ab^#EE TE →' E TE →' E TE →' E TE →'E' '→+E E'→E ε '→E εTT F T →' T F T →' T F T →' T F T →'T''→T ε'→T T '→T ε '→T T '→T T '→T T '→T εFF P F →'F P F →' F P F →' F P F →'F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F εPP E →() P a → P b → P →^(4)procedure E; beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' end else error endprocedure E'; beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T; beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' end else error endprocedure T'; beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then error endprocedure F; beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' end else error endprocedure F'; beginif sym='*'then begin advance; F' end endprocedure P; beginif sym='a' or sym='b' or sym='^' then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advance else error endelse errorend;P81–3/***************(1) 是，满足三个条件。

《编译原理》课后习题答案第一章1.解：源程序是指以某种程序设计语言所编写的程序。

目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。

翻译程序是将某种语言翻译成另一种语言的程序的统称。

编译程序与解释程序均为翻译程序，但二者工作方法不同。

解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。

即边解释边执行，翻译所得的指令序列并不保存。

编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。

即先翻译、后执行。

2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。

3.解：C语言的关键字有：auto break case char const continuedefault do double else enum extern float for goto if int longregister return short signed sizeof static struct switch typedef union unsigned void volatile while。

上述关键字在C语言中均为保留字。

4.解：C语言中括号有三种：{}，[]，（）。

其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。

C语言中无END关键字。

逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。

5.略第二章1.（1）答：26*26=676（2）答：26*10=260（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658个2.构造产生下列语言的文法（1）{anbn|n≥0}解：对应文法为G(S) = ({S},{a,b},{ S→ε| aSb },S)（2）{anbmcp|n,m,p≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)（3）{an # bn|n≥0}∪{cn # dn|n≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c,d,#}, {S→X, S→Y,X→aXb|#,Y →cYd|# },S)（4）{w#wr# | w?{0,1}*,wr是w的逆序排列}解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)（5）任何不是以0打头的所有奇整数所组成的集合解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, Jà1|3|5|7|9},S)（6）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为 S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B3.描述语言特点（1）S→10S0S→aAA→bAA→a解：本文法构成的语言集为：L(G)={(10)nabma0n|n, m≥0}。

编译原理_第三版_课后答案编译原理课后题答案第二章P36-6(1)是0~9组成的数字串⑵最左推导：N= ND= NDD= NDDD = DDDD = ODDD = O1DD= 012D= 0127N= ND 二DD 二3D二34N= ND 二NDD = DDD = 5DD = 56D二568最右推导：N 二ND 二N7二ND7二N27二ND27二N127二D127二0127 N = ND = N4= D4= 34N= ND 二N8= ND8二N68二D68二568P36-7G(S)编译原理第三版课后答案O > 1|3|5|7|9N > 2|4|6|8|0D 、0|NS > 0|A0A > AD|NP36-8文法:E T T E +T|E —TT t F T* F|T/ FF > (E)|i最左推导：E = E T= T T=F T = i T = i T * F = i F * F = i i * F = i i*iE = T= T*F 二 F * F = i* F 二i *( E)二i*( E T)二i *( T T)二i *( F T) =i *( i T)二i*(i F)= i*( i i)最右推导:E= E T= E T*F= E T*i= E F*i= E i*i= T i*i= F i*i= i i*iE= T= F*T= F * F= F*( E)= F *( E T)= F *( E F)= F *( E i)=F*( T i)= F*( F i)= F*( i i)= i*(i i)/********************************P36-11*****************P36-9句子iiiei 有两个语法树:S 二 iSeS 二 iSei 二 iiSei = iiiei S= iS = iiSeS = iiSei = iiieiP36-10/**************S > TS |T T > (S)|()***************ii+i+ii-i-iii+i*i***************P36-11L1:S > ACA r aAb | abC r cC | ；L2:S > ABA》aA| ；B r bBc|bcL3:S > ABA—：aAb | ；B = aBb | ；L4:S > A| BA—；0A1| ；B-1B0| A***************/第三章习题参考答案P64 - 7(1)编译原理第三版课后答案1(01)*101(1)1101确定化:1001111最小化:{0,1,2,3,4,5},{6}{0,123,4,5}。

蒋立源编译原理第三版第四章-习题与答案(总15页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第五章习题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→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i其相应的简单优先矩阵如题图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）进行算符优先分析的过程。

题图5-4 文法G[E]的算符优先矩阵5-5 对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。

(1) S→aSb∣aSc∣ab(2) S→aSSb∣aSSS∣c(3) S→A A→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的分析过程。

5-9 对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。

第二章 高级语言及其语法描述6．（1）L （G 6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导：N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687．【答案】Ｇ：S →ABC | AC | CA →1|2|3|4|5|6|7|8|9B →BB|0|1|2|3|4|5|6|7|8|9C →1|3|5|7|98．（1）最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=> i*(i+i) 最右推导：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i) (2)9．证明：该文法存在一个句子iiiei 有两棵不同语法分析树，如下所示，因此该文法是二义的。

第4章习题14-1 消除以下文法的左递归性。

(1) S→SA|AA→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|fE→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′S′→AS′|BS′|ε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是直接左递归的非终结符号。

第3章习题3-1 试构造一右线性文法，使得它与如下的文法等价S→AB A→UT U→aU|a D→bT|b B→cB|c 并根据所得的右线性文法，构造出相应的状态转换图。

3-2 对于如题图3-2所示的状态转换图(1) 写出相应的右线性文法；(2) 指出它接受的最短输入串；(3) 任意列出它接受的另外4个输入串；(4) 任意列出它拒绝接受的4个输入串。

3-3 对于如下的状态转换矩阵：(1) 分别画出相应的状态转换图；(2) 写出相应的3型文法；(3) 用自然语言描述它们所识别的输入串的特征。

3-4 将如下的NFA确定化和最小化：3-5 将如题图3-5所示的具有ε动作的NFA确定化。

题图3-5 具有ε动作的NFA3-6 设有文法G[S]：S→aA A→aA|bB B→bB|cC|c C→cC|c 试用正规式描述它所产生的语言。

3-7 分别构造与如下正规式相应的NFA。

(1) ((0* |1)(1* 0))*(2) b|a(aa*b)*b3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。

第3章习题答案3-1 解：根据文法知其产生的语言是:L[G]={a m b n c i| m,n,i≧1}可以构造与原文法等价的右线性文法:S→aA A→aA|bB B→bB|cC|c C→cC|c 其状态转换图如下:3-2 解:(1) 其对应的右线性文法是G[A]:A →0D B→0A|1C C→0A|1F|1D→0B|1C E→0B|1C F→1A|0E|0(2) 最短输入串为011(3) 任意接受的四个输入串为：0110,0011,000011,00110(4) 任意拒绝接受的输入串为：0111，1011，1100，10013-3 解:(1) 相应的状态转换图为：(2) 相应的3型文法为：(ⅰ) S→aA|bS A→aA|bB|b B→aB|bB|a|b(ⅱ) S→aA|bB|a A→bA|aC|a|b B→aB|bC|b C→aC|bC|a|b(ⅲ) S→aA|bB|b A→aB|bA|a B→aB|bB|a|b(ⅳ) S→bS|aA A→aC|bB|a B→aB|bC|b C→aC|bC|a|b(3) 用自然语言描述的输入串的特征为：(ⅰ) 以任意个(包括0个)b开头，中间有任意个（大于1）a，跟一个b，还可以有一个由a,b组成的任意字符串。

编译原理第三版课后答案1. 词法分析。

1.1 什么是词法分析？它的作用是什么？词法分析是编译过程中的第一个阶段，它的主要作用是将源代码中的字符序列转换成单词（Token）序列，同时识别出每个单词的种类（标识符、关键字、常数、运算符等）。

词法分析的结果将作为语法分析的输入，为后续的语义分析和代码生成提供基础。

1.2 词法分析的主要步骤有哪些？词法分析的主要步骤包括扫描、识别和归类。

首先，词法分析器会从源代码中逐个读取字符，并将它们组合成单词。

然后，词法分析器会根据事先定义好的词法规则，识别出每个单词的种类，并将其归类为相应的Token。

1.3 请简要介绍一下有限自动机（DFA）在词法分析中的应用。

有限自动机（DFA）是词法分析中常用的一种工具，它可以根据事先定义好的状态转移规则，对输入的字符序列进行逐个扫描，并最终确定每个单词的种类。

DFA具有高效、简洁的特点，能够快速地识别出单词，并将其转换成Token序列。

2. 语法分析。

2.1 什么是语法分析？它的作用是什么？语法分析是编译过程中的第二个阶段，它的主要作用是将词法分析得到的Token序列转换成抽象语法树（AST），同时检查源代码中是否存在语法错误。

语法分析的结果将为后续的语义分析和代码生成提供基础。

2.2 语法分析的主要步骤有哪些？语法分析的主要步骤包括识别、分析和构建。

首先，语法分析器会从词法分析得到的Token序列中逐个读取Token，并根据语法规则进行识别和分析。

然后，语法分析器会根据语法规则构建抽象语法树，以表示源代码的结构和语法关系。

2.3 请简要介绍一下递归下降分析法在语法分析中的应用。

递归下降分析法是语法分析中常用的一种方法，它通过递归地调用自身来分析源代码的语法结构。

递归下降分析法具有简单、直观的特点，能够方便地根据语法规则构建抽象语法树，并且易于与语法规则进行对应。

3. 语义分析。

3.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→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i其相应得简单优先矩阵如题图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)进行算符优先分析得过程。

题图5-4 文法G[E]得算符优先矩阵5-5 对于下列得文法,试分别构造识别其全部可归前缀得DFA与LR(0)分析表,并判断哪些就是LR(0)文法。

(1) S→aSb∣aSc∣ab(2) S→aSSb∣aSSS∣c(3) S→A A→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得分析过程。

5-9 对于如下得文法,构造LR(1)项目集族,并判断它们就是否为LR(1)文法。

(1) S→A A→AB∣ε B→aB∣b(2) S→aSa∣a第4章习题答案25-1 解:(1) 由文法得产生式与如答案图5-1(a)所示得句型A／／a／得语法树,可得G中得部分优先关系如答案图5-1(b)所示。