itgle.com
北交《编译原理》精选试题与答案
●程序设计语言包括 (41) 等几个方面，它的基本成分包括 (42) 。Chomsky(乔姆斯基)提出了形式语言的分层理论，他定义了四类文法：短语结构文法、上下文有关文法、上下文无关文法和正则文法。一个文法可以用一个四元组G=(∑,V,S,P)表示，其中，∑是终结符的有限字符表，V是非终结符的有限字母表，S(∈V)是开始符号，P是生成式的有限非空集。在短语文法中，P中的生成式都是α→β的形式，其中a∈ (43) ，β∈(∑∪V)*。在上下文有关文法中，P中的生成式都是α1Aα2→α1βα2的形式，其中A∈ (44) ，β∈(∑∪V*),β≠ε。在上下文无关文法中，P中的生成式的左部∈ (45) 。
(41) A．语法、语义
B．语法、语用
C．语义、语用
D．语法、语义、语用
(42) A．数据、传输、运算
B．数据、运算、控制
C．数据、运算、控制、传输
D．顺序、分支、循环
(43)A．V+
B．(∑∪V)
C．(∑∪V)*
D．(∑∪V)*V(∑∪V)*
(44) A．V
B．V+
C．∑∪V
D．(∑∪V)*
(45) A．V
B．V+
C．∑∪V
D．(∑∪V)*
【解析】Chomsky提出了形式语言的分层理论，他定义了4类文法：短语结构文法、上下文有关文法、上下文无关文法和正则文法。一个文法G可以用一个四元组G=(VT，VN，S，P)来表示，其中VT是终结符的有限字符集，VN是非终结符的有限字母表，S∈VN是文法的开始符号，P是形如α→β的形式，如果P中的产生式都是α→β的形式，其中α∈(VT∪VN)*VN(VT∪VN)*，β∈(VT∪VN)*，则称该文法为短语文法；如果P中的产生式都是αAδ→αβδ的型式，其中A∈VN，α和δ∈(VT∪VN)*，β∈(VT∪VN)+，则称该文法是上下文有关文法；如果P中的产生式都是α→β的形式，其中A∈VN，B∈(VT∪VN)*，则称该文法为上下无关文法；如果P中的产生式都是A→α或A→αB的形式，其中A和B∈VN，α∈VT*，则称该文法为正则文法。
A. 短语文法
B. 上下文无关文法
C. 上下文有关文法
D. 正规文法
●根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与 (28) 等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 (29) 。从文法描述语言的能力来说， (30) 最强， (31) 最弱，由4类文法的定义可知： (32) 必是2型文法。
(28) A．线性有限自动机
B．非确定的下推自动机
C．图灵机
D．有限自动机
(29) A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
(30) A．1型文法
B．2型文法
C．3型文法
D．0型文法
(31) A．3型文法
B．2型文法
C．0型文法
D．1型文法
(32) A．1型文法
B．0型文法
C．3型文法
D．2型文法
【解析】乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。0型文法也称短语文法，0型文法的能力相当于图灵机(Turing)，或者说任何0型语言都是递归可枚举的。1型文法也称上下文有关方法，其能力相当于线形界限自动机。对非终结符进行替换时不必考虑上下文，并且一般不允许替换成空串ε。2型文法也称上下文无关文法，其能力相当于非确定的下推自动机。3型文法也称右线性文法，由于这种文法等价于正规式，所以也称正规文法。3型文法的能力相当于有限自动机。从文法描述语言的能力来说，0型文法最强，3型文法最弱。
语言的文法可以表示成一个四元组(VT，VN，S，P)。由3型文法的定义：一个文法G式3型文法，如果G是二型文法，并且G的每个产生式A→αB或A→α，其中α∈V*T，A，B∈VN，可知3型文法必是2型文法。
根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(67)。从文法描述语言的能力来说，(68)最强，(69)最弱，由四类文法的定义可知：(70)必是2型文法。
(40)
A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
E．有限自动机
Chomsky定义的四种形式语言文法中，2型语言可由()识别。
A、短语结构文法
B、前后文无关文法
C、前后文有关文法
D、正规文法
E、图灵机
F、有限自动机
G、下推自动机
下面哪个文法是左递归的( )。A.TF*TB.EaC.EET|TD.E(E)答案:C
文法 E(E)产生的语言是( )。A.空集B.（E）C.（）D.(E)答案:A
LR（1）文法都是( )。A.无二义性但可能是左递归B.无二义性且无左递归C.可能有二义性但无左递归D.可以既有二义性又有左递归答案:A
语义分析与中间代码产生所依循的是( )。A.语言的语义规则B.正规式C.有限自动机D.上下文无关文法答案:A
文法G的一棵语法树叶结点的自左至右排列是G的一个( )。A.素短语B.句柄C.句子D.句型答案:D
1型文法也称为( )。A.短语文法B.左性性文法C.右线性文法D.上下文有关文法答案:D
下面哪个文法具有二义性( )。A.EaB.EET|TC.E(E)D.AAA | (A) |答案:D
( )是指源程序中不符合语义规则的错误，这些错误一般在语义分析时能检测出来。A.语法错误B.语义错误C.短语错误D.短句错误答案:B
若一个文法是递归的，则它所产生的句子个数( )。A.根据具体情况而定B.是有限个的C.必定是无穷的D.不确定答案:A
.若文法G定义的语言是无限集，则文法必然是( )。A.递归文法B.正规文法C.二义性文法D.上下文无关文法答案:A
优化所依循的原则是( )。A.语言的语义规则B.程序的等价变换规则C.正规式D.上下文无关文法答案:B
有限自动机可以有( )个初始状态。A.多个B.两个C.三个D.一个答案:D
编译程序中语法分析器接收以( )为单位的输入。A.表达式B.句子C.单词D.产生式答案:C
最适合动态建立数据实体的内存分A.编译时预先分配B.栈式分配C.堆式分配D.以上三种均可答案:C
A.短语文法
B.正则文法
C.上下文有关文法
D.上下文无关文法
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(28)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(29)。从文法描述语言的能力来说，(30)最强，(31)最弱，由4类文法的定义可知：(32)必是2型文法。
A．线性有限自动机
B．非确定的下推自动机
C．图灵机
D．有限自动机
A.上下文有关文法
B.上下文无关文法
C.短语文法
D.句子文法
在形式语言中，若文法G的产生式集P为：
(1)Z→Bc(2)Z→Zc(3)B→Ab(4)B→Bb(5)A→Aa(6)A→a
则文法G是(27)文法，识别G的自动机为(28)。对于G来说，(29)为文法G可接受的字符串，(30)为文法G不可接受的字符串。
供选择的答案：
A．短语
B．上下文有关
C．上下文无关
D．正则
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，文法被分为4种类型，即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(1)等价，所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的有穷自动机必存在一个与之等价的(2)。从文法描述语言的能力来说，(3)最强，(4)最弱，由4类文法的定义可知(5)必是2型文法。
A．确定的有穷自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有穷自动机
E．有穷自动机