三.单项选择题
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）请写出此文法描述的只含有４个符号的全部句子。 （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开始的奇数集 }