第6章 属性文法和语法制导翻译
7. 下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：
试设计求的属性文法，其中，已知B的综合属性c, 给出由B产生的二进位的结果值。例如，输入时，=，其中第一个二进位的值是4，最后一个二进位的值是。
【答案】
产生式 语义规则
S→L1. L2 { := + *2－ }
S→L { := }
L→L1B { :=*2+;
L. length:= +1 }
L→B { :=;
L. length:= 1 }
B→0
{ := 0 }
B→1 { :=1 }
11. 设下列文法生成变量的类型说明：
(1) 构造一下翻译模式，把每个标识符的类型存入符号表；参考例。
【答案】
产生式 语义规则
L→ id L1 { := + *2－ }
L→, id L1 { := } S→∣L
L→LB∣B
L→ id L
L→, id L∣:T L→ :T { :=*2+;
L. length:= +1 }
T→ integer { :=;
L. length:= 1 }
T→ real { := 0 }
第7章 语义分析和中间代码产生
1. 给出下面表达式的逆波兰表示（后缀式）：
【答案】
原式 后缀式
(1) a*(-b+c) ab-c+*
(2) a+b*(c+d/e) abcde/+*+
(3) –a+b*(-c+d) a-bc-d+*+
(4) not A or not (C or not D) A not C D not or not or
(5) (A and B) or (not C or D) A B and C not D or or
(6) (A or B) and (C or not D and
E) A B or C D not E and or and
(7) if (x+y)*z=0
then (a+b)↑c
第2章 形式语言基础
2.2 设有文法G[N]: N -> D | ND
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(1) G[N]定义的语言是什么?
(2) 给出句子0123和268的最左推导和最右推导。
解答：
(1) L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={| 为可带前导0的正整数}
(2)
0123的最左推导：N ND NDD NDDD DDDD 0DDD 01DD 012D 0123
0123的最右推导：N ND N3 ND3 N23 ND23 N123 D123 0123
268的最左推导：N ND NDD DDD 2DDD 26D 268
268的最右推导：N ND N8 ND8 N68 D68 268
2.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。
解答：
首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。
N -> 1 | 3 | 5 | 7 | 9 | BN
B -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B0
第 2 章 习题
2-1 设有字母表 A1 ={a,b,c, ⋯,z} ，A2 ={0,1, ⋯,9} ，试回答下 列问题：
（1） 字母表 A1上长度为 2 的符号串有多少个？
（2） 集合 A1A2 含有多少个元素？
（3） 列出集合 A1（A 1∪A2） *中的全部长度不大于 3 的符号串。
2- 2 试分别构造产生下列语言的文法：
（1）{a nbn|n ≥0}；
（2）{a nbmcp|n,m,p ≥0}；
（3）{a n#bn|n ≥ 0} ∪{c n#dn|n ≥0}；
（ 4）{w#wr # | w ∈{0,1} *,wr 是 w的逆序排列 } ；
（ 5）任何不是以 0 打头的所有奇整数所组成的集合；
（6）所有由偶数个 0 和偶数个 1 所组成的符号串的集合。
2- 3 试描述由下列文法所产生的语言的特点：
1） S→10S0 S →aA A →bA A →a 2） S→SS S →1A0 A →1A0 A →ε 3） S→1A S →B0 A →1A A →C
B→ B0 B → C C →1C0 C →ε
（ 4）S→aSS S →a
2- 4 试证明文法
S →AB|DC A →aA|a B →bBc|bc C → cC|c D →
aDb|ab 矚慫润厲钐瘗睞枥庑赖。 为二义性文法。 2- 5 对于下列的文法
S→AB|c A → bA|a B →aSb|c
试给出句子 bbaacb 的最右推导，并指出各步直接推导所得句型的句 柄；指出句子的全部短语。
2- 6 化简下列各个文法
(1) S →aABS|bCACd A → bAB|cSA|cCC B →bAB|cSB C → cS|c
聞創沟燴鐺險爱氇谴净。
(2) S → aAB|E A →dDA|e B → bE|f
C→cAB|dSD|a D → eA E →fA|g
(3) S → ac|bA A →cBC B →SA C → bC|d
编译原理第三版课后习题答案
编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。而《编译原理》第三版是目前被广泛采用的教材之一。在学习过程中，课后习题是巩固知识、提高能力的重要环节。本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。
第一章：引论
习题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：什么是中间代码？
