编译原理(第2版)课后习题答案详解 下载本文

第 16 题

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

(1){an|n >=0 }

(2) { anbm|n,m>=1 }

(3){anbmck|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 题

习题7和习题 11 中的文法等价吗?

答案:

等价。

第 18 题

解释下列术语和概念:

(1) 字母表

(2) 串、字和句子 (3) 语言、语法和语义

答案:

(1)字母表:是一个非空有穷集合。

(2)串:符号的有穷序列。

字:字母表中的元素。

句子:如果 Z x , x ∈V *T 则称 x 是文法 G 的一个句子。

+

(3)语言:它是由句子组成的集合,是由一组记号所构成的集合。程序设计的语言就是所

有该语言的程序的全体。语言可以看成在一个基本符号集上定义的,按一定规 则构成的一切基本符号串组成的集合。

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

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

附加题

问题 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: