编译原理试题集78677 下载本文

三.单项选择题

1. Chomsky把文法分成四种类型,0型、1型、2型和3型。3型文法也称为__________,2型文

法也称为_________ 。 a.上下文无关文法 b.上下文相关文法 c.正则文法 d.短语文法

2. 许多广为使用的语言,如Fortran、C、Pascal等,属于___________。 a. 强制式语言 b. 应用式语言 c. 基于规则的语言 d. 面向对象的语言

3. 设G是一个文法,S是开始符号。若S?*α,α∈(VT∪VN)*,则 称α是一个______ 。 a. 句子 b. 句型 c. 推导 d. 语言

4. 一个数据类型通常包括的三种要素中,没有下面的______。 a. 用于区别这种类型的数据对象的属性;b. 这种类型的数据对象可以具有的值; c. 对这种类型的数据对象的内存分配;d. 可以作用于这种类型的数据对象的操作;

5. Chomsky把文法分成四种类型,其中,______也称正规文法 a. 0型 b. 1型 c. 2型 d. 3型

6. 语言的词法规则一般用Chomsky的______ 型文法来描述: a. 0 b. 1 c. 2 d. 3

7. 文法 S→(L)|a L→L,S|S 中,下面 是该文法中的终结符号。 a. S b. , c. L d. |

8. 文法G所描述的语言是_______ 的集合。 a. 文法G的字母表?中的所有符号组成的符号串; b. 文法G的字母表?的闭包?*中的所有符号串; c. 文法G的识别符号推出的所有符号串; d. 文法G的识别符号推出的所有终结符号串;

9. 语言L={αcα | α∈(a|b)*},该语言是_____________语言。 a. 3型语言,b. 2型语言,c. 1型语言,d. 0型语言

10. 设有文法G: I→I1 | I0 | Ia | Ic | a | b | c | 下面符号串中不是该文法的句子是: a. ab0, b. a0c01, c. aaa, d. bc10

11. 给定文法A→bA|cc,下面的符号串中,是该文法句子的是________。 a. bcbc, b. bbbcc, c. bcbcc, d. bccbcc;

12. Chomsky定义的四种形式语言文法中,2型文法可由_______识别。 a. 图灵机;b. 确定性有限自动机;c. 下推自动机;d. 非确定性有限自动机;

13. 若文法G定义的语言是无限集,则文法必然是__________。 a. 上下文无关的 b. 递归的 c. 二义性的 d. 无二义性的

14. 文法 S→aaS|abc 定义的语言是_______。 a. {a2kbc|k>0} b. {akbc|k>0} c. {a2k-1bc|k>0} d. {akakbc|k>0}

15. 文法:G:S→xSx | y所识别的语言是________。 a. xyx b. (xyx)* c. x*yx* d. xnyxn(n≥0)

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

四.名词解释 1. 二义性文法;

2. 推导和直接推导;

3. 句型,句子和语言;

4. 上下文无关文法;

5. 语法;

6. 正规文法(左线性文法和右线性文法); 解答: 1. 2. 3. 4. 5. 6.

五.简答题

1. 作为描述程序语言的上下文无关文法,对它有哪些限制?

2. 什么是二义性文法?从输入串abab来说明下面文法二义吗? S→aSbS|bSaS|ε 该文法产生的语言是什么?

3. 文法 G[S]为: S→Ac|aB A→ab B→bc 该文法是否为二义的?为什么?

4. 已知文法G=({A,B,C},{a,b,c},P,A), P由以下产生式组成: A→abc A→aBbc Bb→bB Bc→Cbcc bC→Cb aC→aaB aC→aa 此文法所表示的语言是什么?

5. 已知文法G[Z]:

Z→0U|1V U→1Z|1 V→0Z|0 (1)请写出此文法描述的只含有4个符号的全部句子。 (2)G[Z]产生的语言是什么? (3)该文法在Chomsky文法分类中属于几型文法?

解答: 1. 2. 3. 4. 5.

六.应用题

1. 试分析下面给出的if-then-else语句的文法,它的提出原本是为了矫正dangling-else(e lse悬挂)文法的二义性: stmt → if expr then stmt | matched-stmt matched-stmt→ if expr then matched-stmt else stmt | other expr→e 考虑句子if e then if e then other else if e then other else other,试说明此文 法仍然是二义性的。

2. 考虑文法G[bexpr]: bexpr→bexpr or bterm | bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor| ( bexpr ) | true | false (a) 请指出此文法的终结符号、非终结符号和开始符号。 (b) 试对于句子not(true or false)构造一棵分析树。 (c) 试说明此文法所产生的语言是全体布尔表达式。

3. 已知文法G[S],其产生式为:S→(S)| ε? (a)L(G)是什么? (b)对于(a)的结果,请给出证明。

4. 试构造生成下列语言的上下文无关文法: (1) { anbnci | n≥1, i≥0 } (2) { w | w∈{a,b}+,且w中a的个数恰好比b多1 } (3) { w | w∈{a,b}+,且|a|≤|b|≤2|a| } (4) { w | w是不以0开始的奇数集 }