精品文档
第三章
1、L(G[S])={ abc }
2、L(G[N])={ n位整数或空字符串 | n>0 }
3、G[E]：E—>E+D | E-D | D
D—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
4、L(G[Z])={ anbn | n>0 }
5、(1) 考虑不包括“0”的情况
G[S]：S—>0S | ABC | 2 | 4| 6 | 8
A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B—>AB | 0B | ε C—>0 | 2 | 4 | 6 | 8
考虑包括“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)方法1：
G[S]：S—> ABC | 2 | 4 | 6 | 8
A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B—>AB | 0B | ε C—>0 | 2 | 4 | 6 | 8
方法2：
G[S]：S—>AB | C
B—> AB | 0B | C | 0
A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C—>2 | 4 | 6 | 8
6、设<表达式>为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 => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I
<表达式> 7、 <表达式>
* <表达式> <表达式>
+ <表达式> <表达式>
<表达式> i <表达式> + i * <表达式> <表达式>
i 精品文档
i
i
i
精品文档
8、是有二义性的，因为句子abc有两棵语法树（或称有两个最左推导或有两个最右推导）
最左推导1：S => Ac => abc 最左推导2：S => aB => abc 9、(1)
S
SS*
SS+a
aa
(2) 该文法描述了变量a和运算符+、*组成的逆波兰表达式
10、(1) 该文法描述了各种成对圆括号的语法结构
(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导： 最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()() 最左推导2：S => S(S)S => S(S)S(S)S => (S)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相对于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) 首先为了区别句子abbaa中的a和b，把它写成a1b1b2a2a3 该句子的短语有：a1b1b2a2a3，b1b2，a2a3，a1，a2，b1，b2，ε 直接短语有：a1，a2，b1，b2，ε 句柄：a1
14、(1) G[S]：S—>AB
A—>aAb |ε B—>aBb |ε
精品文档
精品文档
(2) G[S]：S—>1S0 | A A—>0A1 |ε (3) G[S]：S—>0S0 | aSa | a
16、(1) G[A]：A—>aA |ε
(2)G[A]：A—> aA | aB B—> bB | b (3)G[A]：A—>aA | B B—> bB | C C—>cC |ε
17、习题6、习题7和习题7中的文法所描述的语言都是由变量i、+、-、*、/、（和）组成算术表达式，因此它们之间是等价的。
第四章参考答案 第1题： (1) 0,1 1 1 0 1
S A B C
确定化： I0 I1 S –S A A A A AB B AB AC AB C AC A ABZ Z +ABZ AC AB
重新命名，令{AB}为B、{AC}为C、{ABZ}为Z 其中S为初态，Z为终态 0 1 –S A A A B B C B C A D +Z C B Z 精品文档
精品文档
(3)
a,b
a b
Z S A
a a
B b
确定化： Ia Ib 0 –S A 1 A AB AZ 2 AB AB ABZ 3 +AZ AB AZ 4 +ABZ AB ABZ
重新命名，以0、1、2、3、4代替{S},{A}, {AB},{AZ},{ABZ}得DFA 其中0为初态，3，4为终态 Ia Ib –0 1 1 2 3 2 2 4 +3 2 3 +4 2 4
第2题： I0 I1 A –X Z X B +Z XZ Y C +XZ XZ XY D Y XY E XY XYZ X F +XYZ XYZ XY
重新命名，以A、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ代替{X},{Z },{XZ },{ Y },{ XY },{XYZ}得DFA 其中A为初态，Ｂ，Ｃ，Ｆ为终态 –A 0 B 1 A 精品文档