编译原理(第四版)胡元义第三章习题答案

2 设文法G[N]为
G[N]:N→D IND
D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(1) 文法G[N]所描述的语言L(G)具有何种特性?
(2) 分别为句子0127、34和568提供最左推导与最右推导过程。

**答：
(1) 文法G[N]所生成的语言L(G[N])表示的是非负整数集合。
(2) 最左推导: N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
N=>ND=>DD=>3D=>34
N=>ND=>NDD=>DDD=>5DD=>56D=>568
最右推导: N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127
N=>ND=>N4 => D4 =>34
N => ND => N8 => ND8 => N68 => D68 =>568

3.6 考虑文法G[S]:
S→aAcB I Bd
A→AaBIc
B→bScA Ib
(1) 尝试确定句型aAaBcbbdcc与aAcbBdcc的句柄；
(2) 描述句子acabcbbdcc的最左推导路径。

**答：
（1）依据句型aAaBcbbdcc对应的语法树分析，其直接短语共有三个，分别为AaB、b以及c，其中位于左侧的直接短语即为句