编译原理(第四版)胡元义第三章部分习题答案(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的最左推导和最右推导。

答&＃xff1a;
(1) G[N]的语言L(G[N])是非负整数。
(2)最左推导: N&＃61;>ND&＃61;>NDD&＃61;>NDDD&＃61;>DDDD&＃61;>0DDD&＃61;>01DD&＃61;>012D&＃61;>0127
N&＃61;>ND&＃61;>DD&＃61;>3D&＃61;>34
N&＃61;>ND&＃61;>NDD&＃61;>DDD&＃61;>5DD&＃61;>56D&＃61;>568
最右推导: N&＃61;>ND&＃61;>N7&＃61;>ND7&＃61;>N27&＃61;>ND27&＃61;>N127&＃61;>D127&＃61;>0127
N&＃61;>ND&＃61;>N4&＃61;>D4&＃61;>34
N&＃61;>ND&＃61;>N8&＃61;>ND8&＃61;>N68&＃61;>D68&＃61;>568

3.6 有文法G[S]:
S→aAcB I Bd
A→AaBIc
B→bScA Ib
(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄:
(2)写出句子acabcbbdcc的最左推导过程。
答&＃xff1a;
&＃xff08;1&＃xff09;根据aAaBcbbdcc语法树&＃xff0c;得知直接短语有3个: AaB、b和c&＃xff0c;而AaB为最左直接短语&＃xff0c;即为句柄。
根据aAcbBdcc语法树&＃xff0c; 直接短语有两个: Bd和c&＃xff0c;而Bd为最左直接短语&＃xff0c;即为句柄。

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

&＃xff08;2&＃xff09;短语: S、a、(a)、S,(a)、 (S,(a)); 直接短语:a、S; 句柄: S; 素短语&＃xff1a;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#的分析过程。
答&＃xff1a;
&＃xff08;1&＃xff09;
G’[A]:
A→aA’
A’→ABl I ε
B→dB ’
B’→bB’ | ε
(2)FIRST(A)&＃61;{a}
FIRST(A’)&＃61;{a,ε}
FIRST(B)&＃61;{d}
FIRST(B’)&＃61;{b,ε}
FOLLOW(A)&＃61;{#,d};
FOLLOW(B)&＃61;{l};
FOLLOW(A’)&＃61;{#,d};
FOLLOW(B’)&＃61;{l}。
分析表&＃xff1a;
&＃xff08;3&＃xff09;