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

3.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语法树，得知直接短语有3个: AaB、b和c，而AaB为最左直接短语，即为句柄。
根据aAcbBdcc语法树， 直接短语有两个: Bd和c，而Bd为最左直接短语，即为句柄。

3.7 对于文法G[S]:
S→(L) l aS l a
L→L,S I S
(1)画出句型(S,(a))的语法树;
(2)写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。
答：
(1)

（2）短语: S、a、(a)、S,(a)、 (S,(a)); 直接短语:a、S; 句柄: S; 素短语：a

3.10已知文法 G[A]:
A -> aABI l a
B→Bb l d
(1)试给出与G[A]等价的LL(1)文法G’[A];
(2) 构造G[A’]的LL(1)分析表;
(3)给出输入串aadl#的分析过程。
答：
（1）
G’[A]:
A→aA’
A’→ABl I ε
B→dB ’
B’→bB’ | ε
(2)FIRST(A)={a}
FIRST(A’)={a,ε}
FIRST(B)={d}
FIRST(B’)={b,ε}
FOLLOW(A)={#,d};
FOLLOW(B)={l};
FOLLOW(A’)={#,d};
FOLLOW(B’)={l}。
分析表：
（3）