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 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=，该语言是语言。
a. 3型语言，b. 2型语言，c. 1型语言，d. 0型语言。
10. 设有文法g：
i→i1 | i0 | ia | ic | a | b | c |
下面符号串中不是该文法的句子是。
a. ab0b. 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. b.
c. d.
15. 文法：g：s→xsx | y所识别的语言是。
a. xyxb. (xyxc. x*yx* d. xnyxn（n≥0）
一．答案：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；
按照组卷方案，至少15道小题）
1. 假设g是一个文法，是由终结符和非终结符组成的串，s是文法的开始符号，如果s=>*则称是。
2. 在赋值语句中，赋值号‘：=左右两边的变量名扮演着两种不同的角色，为了区分一个名字的这两种特征，我们把一个名字所代表的称为该名的左值，把一个名字的称为该名字的右值。
3. 对于文法g，仅含终结符号的句型称为。
4. 设有文法g[s]，其部分产生式：
e→e+t | t
t→t*f | f
f→(e) |a
则vnvt5. 由文法产生的集合是文法产生的语言。
6. chomsky语法定义的3型文法又可以分为。
7. 一个上下文文法g的四个组成部分分别是。
8. 已知语言：，其语法定义为：g=(，s，p)，其中p为。
9. 已知某语言的语法定义为：g=(,s, p )，且p: s→as | 则该语言为。
10. 已知某语言为*}，其语法定义为g=(，s，p)，其中p为。
11. 所谓最右推导是指。
12. 已知文法g(z):
e→et+|t
t→tf*|f
f→fp↑|p
a;s-|.q [八公山下p→e|i
试写出其识别的一个句子。
13. 文法g[s]：s→aa|a，a→as为___型文法，其确定的语言的为。
14. 在一棵语法树生长过程中的任何时刻就是一个句型。
15. 我们说g=(vt，vn，s，p)是一个0型文法，如果它的每一个产生式→是这样一种结构： 。
二．答案：1. 句型；2.
单元的地址（或者：单元、存储单元的地址），值（或者：单元的内容）3.
句子；4. vn=，vta}；5. 句子；6.
右线性文法和左线性文法；7. 开始符号，产生式集合，终结符集合，非终结符集合；8. s→ab；a→aab|；b→abb|；9.
；10. s→asa|bsb|；11. 任何一步都是对中的最右非终结符进行替换。
12. iii↑*+13. ；14.
所有那些没有后代的末端结点从左到右排列起来；15. ∈vn∪vt)*且至少含有一个非终结符，而∈(vn∪vt)*。
按照组卷方案，至少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=。（
8. 不存在任何正规文法能产生语言l=。（
9. 对于每一个左线性文法g1，都存在一个右线性文法g2，使得l(g1)=l(g2)。（
10. 正规文法产生的语言都可以用上下文无关文法来描述。（
11. 上下文无关文法比正规文法有更强的描述能力。（
12. 文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存在两个以上的文法来描述它。（
13. 二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切地给出该文法是否二义的答案。（
14. 说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标**。（
15. c语言是一个允许子程序嵌套定义的语言。（
三．答案：1. √2.
√3. √4. √5.
√6. ×7. √8.
√9. √10. √11.
√12. ×13. ×14.
√15. ×
按照组卷方案，至少3道小题）
1. 二义性文法；2. 推导和直接推导；3. 句型，句子和语言；4. 上下文无关文法；
5. 语法；6. 正规文法（左线性文法和右线性文法）；
四．答案：1. 如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是是二义性文法。
2. 设a→是一个产生式，且、(vtvn)*，若a=>，则称a直接推出；或者说，是a的一个直接推导。
编译原理第二章作业
1.pl 0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。pl 0 语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。数组 code 存放的只读目标程序，它在运行时不改变。运行时的数据区 s 是由解释程序定义的一维整型数组，解释执行时对数据空间 ...
编译原理答案第二章
第二章词法分析 2.1 完成下列选择题 1 词法分析器的输出结果是 c a.单词的种别编码 b.单词在符号表中的位置。c.单词的种别编码和自身值 d.单词自身值。2 正规式m1和m2等价是指 c a.m1和m2的状态数相等 b.m1和m2的有向边条数相等。c.m1和m2所识别的语言集相等 d.m1和...
编译原理第二章习题
第2章习题。1 文法g s 为 s ac ab a ab b bc 写出l g s 的全部元素。答案 s ac abc 或s ab abc 所以l g s 2 令文法g为 n d nd d 0 1 2 3 4 5 6 7 8 9 1 g的语言l g 是什么？2 给出句子0568的最左推导和最右推导。...