《编译原理》单元测试第二章试题

编译原理

2014—2015学年第二学期第二单元测试试卷

（闭卷考试） 时间：45分钟 满分：100分

姓名 班级 出题人 刘兵 班级 02

题目 一 二 三 四 五 总分 得分 一、选择题（5*2分）（每题1分，共10分）

1．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. 短语文法 B．正则文法 C． 上下文有关文法 D．上下文无关文法 2．文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是 _____ A. L(G[N])={bi│i≥0} B. L(G[N])={b2i│i≥0} C. L(G[N])={b2i+1│i≥0} D. L(G[N])={b2i+1│i≥1}

3．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符 号，一个开始符号，以及一组_______

A. 句子 B. 句型 C. 单词 D. 产生式 4．一个句型中的最左______称为该句型的句柄。 可选项有：

A. 短语 B. 简单短语 C. 素短语 D. 终结符号

5．文法G[E]：E→T∣E＋T T→F∣T﹡F F→a∣（E） 该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的______ 。

①（E＋T） ②E＋T ③F ④ F﹡(E＋T) 可选项有：

A) ①和③ B) ②和③ C) ③和④ D) ③

二、简答题（2*10分）（每题10分，共20分）

1．解释语言、语法和语义的概念。

2. 文法 S→S(S)S|ε

(1) 生成的语言是什么？

(2) 该文法是二义的吗？说明理由。

三、分析题（4题共70分）

1．

文法 G[S]为： S→Ac|aB A→ab B→bc

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

2．考虑下面上下文无关文法： S→SS*|SS+|a

(1)表明通过此文法如何生成串 aa+a* (2)G[S]的语言是什么？

3．令文法 G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i

证明 E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

4. 给出生成下述语言的三型文法： (1){an|n >=0 } (2) { anbm|n,m>=1 } (3){anbmck|n,m,k>=0 }

编译原理

2014—2015学年第二学期第二单元测试答案

答案

一

1.B 2.C 3.D 4.B 5.B 二

1. 语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所

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

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 2.

（１） 嵌套的括号

（２） 是二义的，因为对于（）（）可以构造两棵不同的语法树。 三 .1.

对于串 abc

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

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

(1)此文法生成串 aa+a*的最右推导如下 S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 3. 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所 以 E+T*F 句型

此句型相对于 E 的短语有:E+T*F；相对于 T 的短语 有 T*F

直接短语为：T*F 句柄为：T*F

4. (1) S→aS|ε (2) S→aA A→aA|B B→bB|b (3)

A→aA|B B→bB|C C→cC|ε