工学
单选题3型文法是（）是语法分析使用的文法。A 短语文法B 上下文有关文法C 上下文无关文法D 正规文法
题目
短语文法
上下文有关文法
上下文无关文法
正规文法
参考答案和解析
相似问题和答案
第1题：
假设某程序语言的文法如下：
S→SaT|T
T→TbR|R
R→PdR|P
P→fSg|e
其中Vr＝{a，b，d，e，f，g}；Vn＝{S，T，R，P}；S是开始符号，那么，此文法是(43)文法。这种文法的语法分析通常采用优先矩阵。优先矩阵给出了该文法中各个终结符之间的优先关系(大于、小于、等于和无关系)。在上述文法中，某些终结符之间的优先关系如下：b{(44)}a；f{(45)}g；a{(46)}a；d{(47)}d。
A．五则文法
B．算符文法
C．二义文法
D．属性文法
第2题：
此题为判断题(对，错)。
第3题：
●根据乔姆斯基于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型文法。
第4题：
在Chomsky定义的4种形式语言文法中，0型文法又称为(51)文法；1型文法又称为(52)文法；2型语言可由(53)识别。
A．短语结构文法
B．上下文无关文法
C．上下文有关文法
D．正规文法
第5题：
A.短语文法
B.正则文法
C.上下文有关文法
D.上下文无关文法
第6题：
此题为判断题(对，错)。
第7题：
此题为判断题(对，错)。
第8题：
● 对给定文法G=（VN，VT， P，S），VT={a，Λ，(，)}，VN={S，T}，S是开始符号，
P:
S→a|Λ|(T)
T→T,S|S
则（1）不是它的句子。该文法是（2）型文法。
（1）A. (a,(a,a)) B. (((a,a), Λ,(a)),a) C. ((a,a), Λ) D. ((a,a),(T))
（2）A．0型文法 B．1型文法 C．2型文法 D．正规文法
根据句子的定义，若从文法G的开始符号S能推导出的符号串成为文法的一个句型，仅含终结符的句型成为一个句子。很显然，备选答案D中含有非非终结符T，所以它不是文法的句子。
该文法是递归可枚举的，所以文法是0型文法，又文法所有产生式的右边长度大于或等于产生式左边长度，所以文法是1型文法，由于该文法的每个产生式的左边均是非终结符，所以该文法是2型文法；由于文法的两个产生式即不是右线性，也不是左线性，所以该文法不是正规型文法。
第9题：
语法分析方法大体上可分成自顶向下和自底向上两种。自底向上分析法，是从输入符号串开始逐步进行(38)，直至(38)成文法的起始符号。自顶向下分析法，则是从文法的起始符号开始反复使用产生式进行(39)，直至(40)出输入符号串。算符优先文法是一种自底向上分析方法，其特点是文法的产生式中(41)。自顶向下的分析方法，通常要求文法的产生式(41)，如(42)文法就是一种可以自顶向下分析的文法。
A．递归
B．综合
C．回归
D．推导
E．归约
第10题：
假设某程序语言的文法如下：
S→SaT｜T
T→TbR｜R
T→PdR｜P P→fSg｜e
其中：VT={a，b，d，e，f，g}，VN{S，T，R，P}，S是开始符号。那么，此方法是(38 方法。这种文法的语法分析通常采用优先矩阵，优先矩阵给出了该文法中各个终结符之间的优先关系 (大于，小于，等于，无关系)。在上述文法中，某些终结符之间的优先关系如下：
b(39)a：f(40)g；a(41)a；d(42)d。
A．正规文法
B．算符文法
C．二义文法
D．属性文法