第二章 高级语言及其语法描述
本章要点
1. 程序语言的定义；
2. 高级程序语言一般结构和主要共同特征； 3. 正确理解上下文无关文法基本概念，包括：
文法的定义、推导、句型、句子、语言、语法树、二义性等； 4. Chomsky文法分类；
本章目标
掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。
本章重点
1. 语法，词法规则与语法规则； 2. 语义和语义规则； 3. 数据类型与操作；
4. 推导，最左推导和最右推导； 5. 语法分析树和二义性；
本章难点
1. 二义性文法； 2. Chomsky各个文法类；
作业题
一、单项选择题：
（按照组卷方案，至少15道小题）
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 7. 文法
S→(L)|a L→L，S|S 中，下面
是该文法中的终结符号。 b. 1
c. 2
d. 3
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型文法可由（ G ）识别。
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*
一．答案：1. c.；2. a.；3. b；4. c；5. d；6. d；7. b；8. d；9. d；10. a；11. b；12. c；13. b； 14. c；15. d；
）。
d. xnyxn（n≥0）
二、填空题：
（按照组卷方案，至少15道小题）
1. 假设G是一个文法，?是由终结符和非终结符组成的串，S是文法的开始符号，如果S=>*?，则称?是 。
2. 在赋值语句中，赋值号‘：=’左右两边的变量名扮演着两种不同的角色，为了区分一个名字的这两种特征，我们把一个名字所代表的 称为该名的左值，把一个名字的 称为该名字的右值。
3. 对于文法G，仅含终结符号的句型称为 。 4. 设有文法G[S]，其部分产生式: E→E+T | T T→T*F | F F→(E) | a
则VN ={ },VT={ }。 5. 由文法产生的 集合是文法产生的语言。 6. Chomsky语法定义的3型文法又可以分为 。
7. 一个上下文文法G的四个组成部分分别是： 。 8. 已知语言：{anbnambm|n，m≥0}，其语法定义为：G=({a，b}，{S，A，B}，S，P)，其中P为： 。