3. 对于文法G，仅含终结符号的句型称为_________________________。
4. 设有文法G[S]，其部分产生式: S－>S;T S－>T T－>if E then S T－>V:=E T－>A 则VN ={ },VT={ }。
5. 由文法产生的_______________________集合是文法产生的语言。
6. Chomsky语法定义的3型文法又可以分为__________________________________。
7. 一个上下文文法G的四个组成部分分别是：________________________________________ _。
8. 已知语言：{anbnambm|n，m≥0}，其
语法定义为：G=({a，b}，{S，A，B}，S，P)，其中P为： ________________________________________________________ 。
9. 已知某语言的语法定义为：G=({1，0}，{S，A}，S，P)，且P：S→1A0|A|ε?；A→0A1| ε，则该语言为________________________________。
10. 已知某语言为{?wcwR|?∈{a，b}*}，其语法定义为G=({a，b，c}，{S}，S， P)， 其中P为：_________________________________ 。
11. 所谓最右推导是指_________________________________________________________。
12. 已知文法G(Z): E→ET+|T T→TF*|F F→FP↑|P P→E|i 试写出其识别的一个句子：_____________________。
13. 文法G[S]：S→aA|a， A→aS为_______ 型文法，其确定的语言的为：_______ 。
14. 在一棵语法树生长过___________________________________________ _________ 就是一个句型。
程
中
的
任
何
时
刻
，
15. 我们说G=(VT，VN，S，P)是一个0型文法，如果它的每一个产生 式α→β是这样一种结构：
_________________________________________________________________ 。
解答: 1. 句型；
2. 单元的地址（或者：单元、存储单元的地址），值（或者：单元的内容） 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
二.判断题
1. 一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。 （ ）
2. 可能有两个不同的文法G和G“，期中一个是二义的而另一个是无二义的，但是却有L(G) ＝L(G“)。（ ）
3. 变量既持有左值又持有右值，而常数和带有算符的表达式一般认为只持有右值。（ ）
4. 文法G: S→bA A→aA|a 定义的语言是所有以b开头的后跟至少一个a的字符串的集合。（ ）
5. 设有文法G： S→S*S | S+S | (S) | a
该文法是二义的。( )
6. 正则文法一定不是二义的。（ ）
7. 上下文无关文法可以产生语言L={ anbnci | i>=1, n>=1 }。（ ）
8. 不存在任何正规文法能产生语言L={anbn | n>=1}。（ ）
9. 对于每一个左线性文法G1，都存在一个右线性文法G2，使得L(G
（ ） 1)=L(G2)。
10. 正规文法产生的语言都可以用上下文无关文法来描述。（ ）
11. 上下文无关文法比正规文法有更强的描述能力。（ ）
12. 文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存 在两个以上的文法来描述它。（ ）
13. 二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切 地给出该文法是否二义的答案。（ ）
14. 说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名 字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。（ ）
15. C语言是一个允许子程序嵌套定义的语言。（ ）
解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 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 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. 二义性文法；
