编译原理课后习题答案解析+清华大学出版社第二版

=><

表达式

>

＋

<

因子< /p>

>*i

<

表

达式

>

<

表

达式

>

+

<

项

>

<

项

>

<

因

子

>

<

因

子

>

（

<

表

达式

>

)

i

<

表

达式

>

+

<

项

>

<

项

>

<

因

子

>

<

因

子

>

i

i

<

表

达式

>

<

表

达式

>

+

<

项

>

<

项

>

<

项

>

*

<

因

子

>

<

因

子

>

<

因

子

>

i

i

i

=><

表 达式

>

＋

i*i

=><

项

>

＋

i*i

=><

因子

>

＋

i*i

=>i

＋

i*i

第

7

题

证明下述文法

G[

< br>〈表达式〉

]

是

二义的。

〈表达式〉∷

=a|(

〈表达式〉

)|

〈表达式〉< /p>

〈运算符〉

〈表达式〉

〈运算符〉∷

=+|-|*|/

答案：可为句子

a+a*a

构造两个不同的最右推导

:

最右

推导

1

〈表达式〉

〈表达式〉

〈运算符〉

〈 表达式〉

〈表达式〉

〈运算符〉

a

〈表达式〉

* a

〈表达式〉

〈运 算符〉

〈表达式〉

* a

〈表达式〉

〈运算符〉

a * a

〈表达式〉

+ a * a

a + a * a

最右推导

2

〈表达式〉

〈运算符〉

〈表达式〉

符〉

〈表达式〉

〈运算符〉

〈表达式〉

〈表达式〉

〈运 算符〉

〈表达式〉

〈运算符〉

a

〈表达式〉< /p>

〈运算符〉

〈表达式〉

* a

〈表达式〉

〈运算符〉

a * a

〈表达式〉

+ a * a

a + a * a

第

8

题

文法

G[S]

为：

S

→

Ac|aB

A

→

ab

B

→

bc

该文法是否为二义的为什么

〈表达式〉

〈运算

答案：

对于串

abc

(1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。

或者：

对输入字符串

abc

，能构造两棵不 同的语法树，所以它是二义

的。

第

9

题

考虑下面上下文无关文法：

S

→

SS*|SS+|a

(1)

表明通过此文法如何生成串

< /p>

aa+a*

，并为该串构造

语法树。

(2)G[S]

的语言是什么

答案：

(1)

此文法生成串

aa+a*

的最右推导如下

S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

(2)

该文法生成的语言是：

*

和

+

的后缀表达式 ，即逆波兰式。

第

10

题

文法

S

→

S(S)S|ε

(1)

生成的语言是什么

(2)

该文法是二义的吗说明理由。

S

S

+

a

S

S

S

a

B

A

c

a

b

c

b

S

S

*

a

a

答案：

（１）

嵌套的括号

（２）

是二义的，因为对于（）

（）可以构造两棵不同的语法树。

第

11

题

令文法

G[E]

为：

E→T|E+T|E

-T

T→F|T*F|T/F

F→(E)|i

证明

E+T*F

是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

答案：

此句型对应语法树如右，故为此文法一个句型。

或者：因为存在推导序列

: E=>E+T=>E+T*F

，所以

E+T*F

句型

此句型相对于

E

的短语有

:E+T*F

；相对于

T

的

短语

有

T*F

直接短语为：

T*F

句柄为：

T*F

第

13

题

一个上下文无关文法生成句子

abbaa

的推导树如下：

(1)

给出串

abbaa

最左推导、最右推导。

(2)

该文法的产生式集合

P

可能有哪些元

素

(3)

找出该句子的所有短语、直接 短语、句

a

答案：

(1)

串

abbaa

最左推导

:

S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa =>abbaa

最右推导：

S=>ABS=>ABAa=>ABaa=>ASBBaa= >ASBbaa=>ASbbaa=>Abbaa=>abbaa

a

S

ε

B

b

B

A

b

a

A

B

S

S

柄。

(2)

产生式有：S→ABS |Aa|ε A→a B→SBB|b 可能元素

有：ε aa ab abbaa aaabbaa ……

(3)

该句子的短语有：

a

是

相对

A

的短语

ε

是

相对

S

的短语

b

是相

对

B

的短语

εbb 是

相对

B

的短语

aa

是

相对

S

的短语

aεbbaa 是相对

S

的

短语

直接短语有：a ε b

句柄是：

a

第

14

题

给出生成下述语言的上下文无关文法：

（

1

）

{ a

b

a

b

| n

，

m>=0}

（

2

）

{ 1

0

1

0

| n

，

m>=0}

< br>（

3

）

{WaWr|W

属于

{0|a}*

，

Wr

表示

W

的逆

}

答案：

（１）

S→AA

A→aAb|ε

（２）

S→1S0|A

A→0A1|ε

（３）

S→0S0|1S1|ε

第

16

题

给出生成下述语言的三型文

法：

n

m

m

n

n

n

m

m

(1){an|n >=0 }

(2) { a

b

|n,m>=1 }

(3){a

b

c

|n,m,k>=0 }

答案：

(1) S→aS|ε

(2)

S→aA

A→aA|B

B→bB|b

(3)

A→aA|B

B→bB|C

C→cC|ε

第

17

题

习题７和习题

11

中的文法等价吗

答案：

等价。

第

18

题

解释下列术语和概念：

（１）

字母表

（２）

（３）

（１）

字母表：是一个非空有穷集合。

（２）

串：符号的有穷序列。字：字母表中的元素。句子：如果

Z x , x

串、字和句子

语言、语法和语义

答案：

n

m

k

n

m

+

∈V *T 则称

x

是文法

G

的一个句子。

（３）语言：它是由句子组成

的集合， 是由一组记号所构成的集合。程序设计的语言就是所

< br>有该语

言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构 成

的一切基本符号串组成的集合。

语法：表示构成语言句子的各个记 号之间的组合规律。程序的结构或形式。

< br>语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。

附加题

问题

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*

；

< br>相应的正规文法为

(

由自动机化简来

)

：

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

< br>(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)

E

E

E + T

T

T

*

F

F i

i

E + T

T

F

F

i

i

i

E

E + T

T

F

i

F

(

E )

E

+

T

T

F

(4)

i

F

i

T

F

F

i

(1)

问题

6

：

已知文法

G[E]:

E

→

ET+|T

T

→

TF* | F

F

→

F^ | a

< br>试证：

FF^^*

是文法的句型，指出该句型的短语、简 单短语和句

柄

.

答案：

该句型对应的语法树如下：

该句型相对

于

E

的短语有

FF^^*

相对于

T

的短语有

FF^^*,F

相对于

F

的短语有

F^;F^^

简单

短语有

F;F^

句柄为

F.

问题

7

：

适当变换文法，找到下列文法所定义语言的一个无二义的文法：

S

→

SaS

?