本书为《编译原理》第二版的答案解析书籍，内容完整无缺，详细解答了教材中的各类习题和问题，适合深入学习编译原理的学生使用。
第三章
L(G[S]) = {abc}
L(G[N]) = { n位整数或空字符串 | n>0 }
G[E]：
E → E+D | E-D | D
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
L(G[Z]) = {anbn|n > 0}
(1) 考虑不包括0的情况
G[S]：
S → ASB
A → BCB
C → DCD
D → a|b
考虑包含“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) 方法一：
G[S]:
S→ ABC
A→ BCB
B→ DCD
C→ a|b
方法二：
G[S] :
S → AB | C
B → AB | 0B | C
A → 1|2|3|4|5|6|7|8|9
C → 0 | 2 | 4 | 6 | 8
设<表达式>为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→E-T→E*T→E/F→F*F→i*i
= >i*I
是有二义性的，因为句子abc有两棵语法树（或称有两个最左推导或有两个最右推导）。
最左推导1：S => Ac => abc
最左推导2：S → aB → abc
(1) 该文法描述了变量a和运算符+、*组成的逆波兰表达式。
(10)(1) 描述的是各种成对圆括号的语法结构。
(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导：
最左推导1：S → S(S)S→ ()S → ()()
最左推导2：S → S(S)S→ S(S)(S)
= > (S) (S) => ()(())=>()
= > ()()
(11)(1) 因为从文法的开始符E出发可推导出 E+T*F，推导过程如下：
E → E + T→E + T * F
所以E+T*F是句型。 从子树和短语之间的关系可知：
E+T*F 是相对于E 的短语；
T*F 是相对于T的 短语，也是简单短语 和 句柄。
(13)(1) 最左推导：S → ABS→ aBS→ aSBBS
= >aBBS => abBS=> abbS=>abbAa=abbaa
(2) S—>ABS | Aa|ε
A—>a
B—>SBB | b
(3) G[S]：
S → 0S0 | aSa | a
或者:
S→1S0|A
A→0A1|
(16)(1)G[A]:
A →aA|
(2)G[A]:
A →aA|bB
B → bB |
(3) G[A]：
A → aA | BC
C → cC |
(17)
习题6、习题7和习题8中的文法所描述的语言都是由变量i、+、-、*、/组成算术表达式，因此它们之间是等价的。
5星
