.
'. 第二章 练习
2.1 考虑文法G[S],其产生式如下:
S→(L)|a
L→L，S|S
(1) 试指出此文法的终结符号、非终结符号。
解答：终结符号为：{(,),a,,,} 非终结符号为：{S,L} 开始符号为：S
(2)给出下列各句子的分析树：
①(a,a) ②(a,(a，a)) ③(a，((a，a)，(a，a)))
.
'.
(3)构造下列各句子的一个最左推导：
①(a,a)
S (L) .
'. (L,S)
(S,S)
(a,S) .
'. (a,a)
②(a,(a，a))
S (L)
(L,S) .
'. (S,S)
(a,S)
(a,(L) .
'. (a,(L,S))
(a,(S,S))
(a,(a,S)) .
'. (a,(a,a))
③(a，((a，a)，(a，a)))
S (L)
(L,S) .
'. (S,S)
(a,S)
(a,(L)) .
'. (a,(L,S))
(a,(S,S))
(a,((L),S)) .
'. (a,((L,S),S))
(a,((S,S),S))
(a,((a,S),S)) .
'. (a,((a,a),S))
(a,((a,a),(L)))
(a,((a,a),(L,S))) .
'. (a,((a,a),(S,S)))
(a,((a,a),(a,S)))
(a,((a,a),(a,a)))
(4)构造下列各句子的一个最右推导： .
'. ①(a,a)
S (L)
(L,S)
(L,a) .
'. (S,a)
(a,a)
②(a,(a，a))
S (L) .
'. (L,S)
(L,(L))
(L,(L,S)) .
'. (L,(L,a))
编译原理第三版课后习题答案
编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。而《编译原理》第三版是目前被广泛采用的教材之一。在学习过程中，课后习题是巩固知识、提高能力的重要环节。本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。
第一章：引论
习题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 -> aAb
A -> 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：什么是中间代码？
1 第二章 高级语言及其语法描述
4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：
（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。
（2） 优先顺序为↑，+，*，同级优先采用右结合。
解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16
（2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=4
6．令文法G6为 N→D|ND
D→0|1|2|3|4|5|6|7|8|9
（1） G6 的语言L（G6）是什么？
（2） 给出句子0127、34和568的最左推导和最右推导。
解：（1）L（G6）=｛a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝
（2）N ＝＞ND＝＞ NDD＝＞ NDDD＝＞ DDDD＝＞ 0DDD＝＞ 01DD＝＞ 012D＝＞ 0127
N＝＞ ND＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127
N＝＞ ND＝＞ DD＝＞ 3D＝＞ 34
N＝＞ ND＝＞ N4＝＞ D4 ＝＞34
N＝＞ ND＝＞ NDD＝＞ DDD＝＞ 5DD＝＞ 56D＝＞ 568
N＝＞ ND＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 568
7．写一个文法，使其语言是奇数集，且每个奇数不以0开头。
解：A→SN, S→+|-|∑, N→D|MD
D→1|3|5|7|9, M→MB|1|2|3|4|5|6|7|8|9 B→0|1|2|3|4|5|6|7|8|9
8. 文法：
ETETETTFTFTFFEi|||*|/()|
最左推导:
EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii********()*()*()*()*()*()*()
第三章
1、L(G[S])={ abc }
2、L(G[N])={ n位整数或空字符串| n>0 }
3、G[E]：E—>E+D | E-D | D
D—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
4、L(G[Z])={ anbn | n>0 }
5、(1) 考虑不包括“0”的情况
G[S]：S—>0S | ABC | 2 | 4| 6 | 8
A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
B—>AB | 0B | ε
C—>0 | 2 | 4 | 6 | 8
考虑包括“0”的情况：
G[S]：S—>AB | C
B—>AB | C
A—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
C—>0 | 2 | 4 | 6 | 8
(2)方法1：
G[S]：S—> ABC | 2 | 4 | 6 | 8
A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
B—>AB | 0B | ε
C—>0 | 2 | 4 | 6 | 8
方法2：
G[S]：S—>AB | C
B—> AB | 0B | C | 0
A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
C—>2 | 4 | 6 | 8
6、设为E，为T，为F，注：推导过程不能省略，以下均为最左推导
(1) E => T => F => i
(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i
(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I
7、
*
+ i i i
