编译原理（第2版）课后习题答案详解 (9)

附加题

问题 1：

给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0

答案：

R = (01 | 10) ( 01 | 10 )*

问题 2：

已知文法 G[A]，写出它定义的语言描述 G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC

答案:

G[A]定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同.

问题 3：

给出语言描述，构造文法.

构造一文法,其定义的语言是由算符+, *, (,)和运算对象 a 构成的算术表达式的集合.

答案一：

G[E] E→E+T|T T→T* F|F F→(E)|a

答案二：

G[E] E→E+E|E* E|(E)|a

问题 4：

已知文法 G[S]:

S→dAB

A→aA|a

B→ε|bB

相应的正规式是什么？G[S]能否改写成为等价的正规文法？

答案：

正规式是 daa*b*；

相应的正规文法为(由自动机化简来)：

G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b

也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε

问题 5：

已知文法 G：

E→E+T|E-T|T

T→T*F|T/F|F

F→(E)|i

试给出下述表达式的推导及语法树

(1) i; (2) i*i+i (3) i+i*i (4) i+(i+i)

答案：

(1)E=>T=>F=>i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i

(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)

(2) (3) (4)

E + T i T F i F i E E + T E + T i T F F ( E ) i T F i F