已知文法G2=(VT={a，'，'，(,)}，VN{S,L}，S，P)，其中P为， S→(L)|a L→L，S|S (a，(a，a))是L(G2[S])的句子，这个句子的最左推导是(28)A．B．C．D．

题目

已知文法G2=(VT={a，'，'，(,)}，VN{S,L}，S，P)，其中P为， S→(L)|a L→L，S|S (a，(a，a))是L(G2[S])的句子，这个句子的最左推导是(28)

A．

B．

C．

D．

参考答案和解析

正确答案：C
解析：设文法G=(VT，VN，S，P)，A→β∈P，γ，δ∈V*，则称γAδ直接推导出γβδ，表示成：γAδγβδ也称γβδ直接归约到γAδ。对于以上公式，若γ∈VT*，即A是γAδ中最左边的非终结符号，则称以上公式是一个最左推导。若Sa的每一步都是最左推导，则称Sa是一个最左推导，a称为一个左句型。对于以上公式，若δ∈VT*，即A是γAδ中最右边的非终结符号，则称以上公式是一个最右推导。若Sa的每一步都是最右推导，则称Sa是一个最右推导，a称为一个右句型。最右推导也称作规范推导，右句型也称作规范句型。对于句子(a，(a，a))，被选择答案中A是最右推导，C是最左推导，B和D的推导序列中，既有最左推导，又有最右推导。

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

文法G=(VT，VN，P,S)的类型由C中的(32)决定。若GO=({a，b}，{S，X，Y}，P,S)，P中的产生式及其序号如下：

1：S→XaaY

2：X→Dqb

3：Y→XbXla

则GO为(33)型文法，对应于(34)，由GO推导出句子aaaaa和baabbb时，所用产生式序号组成的序列分别为(35)和(36)。

A．VT

B．VN

C．P

D．S

正确答案：C

第2题：

假设某程序语言的文法如下：

S→a｜b｜(T)

T→TdS｜S

其中：VT={a，b，d，(，)}，VN{S，T}，S是开始符号。

考查该文法，称句型(Sd(T)db)是S的一个(33)，其中，(34)是句柄：(35)是素短语；(36)是该句型的直接短语；(37)是短语。

A．最左推导

B．最右推导

C．规范推导

D．推导

正确答案：D

第3题：

● 对给定文法G=（VN，VT， P，S），VT={a，Λ，(，)}，VN={S，T}，S是开始符号，

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．正规文法

正确答案：D,C
根据句子的定义，若从文法G的开始符号S能推导出的符号串成为文法的一个句型，仅含终结符的句型成为一个句子。很显然，备选答案D中含有非非终结符T，所以它不是文法的句子。
该文法是递归可枚举的，所以文法是0型文法，又文法所有产生式的右边长度大于或等于产生式左边长度，所以文法是1型文法，由于该文法的每个产生式的左边均是非终结符，所以该文法是2型文法；由于文法的两个产生式即不是右线性，也不是左线性，所以该文法不是正规型文法。

第4题：

已知文法G2=(VT={a，'，'，(,)}，VN={S，L)，S,P)，其中P为 S→(L)|a L→-L，s|s 与G2等价的不含左递归规则的文法是(29)。

A．G21=(VT={a，'，'，(,)}，VN={S，L}，S，P)，其中P为 S→(L)|a L→S，S|S

B．G22=(VT＜a，'，'，(,)}，VN={S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' L'→SL'|ε

C．G23=(VT{a，'，'，(,)}，VN={S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' U→,SL'|ε

D．G24=(VT=(a，'，'，(,)}，VN=＜S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' L→SL'|S

正确答案：C
解析：采用自顶向下的预测分析法首先是等价改写给定的文法，消除文法的左递归和提取产生式的公共左因子。消除直接左递归的方法如下：若A→Aα|β，其中α，β∈(VT∪VN)*，β不以A开始，则关于A的这种形式的产生式可改写成A→βA'A'→αA'|ε一般而言，假设A的产生式为A→Aα1|Aα2|…|Aαn|β1|β2|…|βm其中αI(i=1，2，…，n)不等于ε，βj(j=1，2，…，m)不以A开始，那么上述产生式可改成A→β1A'|β2A'|…|βmA'A'→α1A'|α2A'|…|αnA'|ε消除文法G2中规则的左递归后，其规则变成S→(L)|aL→SL'L'→，SL'|ε

第5题：

已知文法G2=(VT={a,b}，VN={S，A}，S,P)，其中P为， S→Sb｜Ab A→aSb｜ε 该文法生成的语言是(28)。

A．{ambn｜n＞m≥0}

B．{ambn｜m＞n≥0}

C．{ambn｜n≥m≥1}

D．{ambn｜m≥n≥1}

正确答案：A
解析：根据文法G2的产生式A→aSb｜ε，用A的产生式推导出终结符号串，如果仅用A→ε，则产生{ε}；如果先用若干次A→aSb推导，再用A→ε，则推导过程如下：因此，由A生成的终结符号集合是{ambm｜m＞0}。从S出发使用产生式S→Sb｜Ab进行推导，或者。最后，L(G2)={ambm｜m0}连接{bk｜k＞0}={ambm+k｜m+k＞m0}={ambn｜n＞m0}。

第6题：

设已给文法 G=(VN,VT,P,S) ,其中:VN={S}VT={a1,a2,…,an,∨,∧,~,[,]}P={S→ai∣ i=1,2,…,n}∪{S→~S,S→[S∨S],S→[S∧S]}此文法所产生的语言是()。

A.以终结符 a1,a2,…,an 为运算对象的布尔表达式串

B.以∨,∧,~为运算符，以[、]为分隔符的布尔表达式串

C.以终结符 a1,a2,…,an 为运算对象，以∨,∧,~为运算符，以[、]为分隔符的布尔表达式串

D.以[、]为分隔符的布尔表达式串

正确答案:C

第7题：

已知G4=(VT{a，'，'，(，)}，VN={S,L，L'}，S,P)，其中P为， S→(L)|a|ξ L→SL' L'→，SL'|ξ FOLLOW(S)是(29)。

A．{'，'，ξ，}}

B．{'，'#，}}

C．{a，'，'ξ，}}

D．{a，'，'，#}

正确答案：B
解析：终结符A的FOLLOW集合定义如下：FOLLOW(A)={a|S…Aa…，a∈VT，A∈VN}，若S…A，则规定#∈FOLLOW(A)，约定#为句子结束标记。给定一个文法，求FOLLOW(A)的算法如下：①对于文法的开始符号S，置#于FOLLOW(S)中；②若A→αBβ∈P，则把FIRST(β)中的所有非∈—元素都加至FOLLOW(B)中；③若A→αB∈P，或A→αBβ∈P而βξ，则把FOLLOW(A)加至FOLLOW(B)中。重复使用上述3条规则，直到每个FOLLOW集合不再增大为止。非形式地说，一个非终结符的FOLLOW集合，就是从文法开始符号可以推导出的所有含A句型中紧跟在A之后的所有终结符号。首先，因为S是开始符号，所以，置#于FOLLOW(S)中。根据L→SL'，把FIRST(L')中的所有非ξ一元素都加至FOLLOW(S)中，即把','加至FOLLOW(S)中。又根据L→SL'和L'ξ，把FOLLOW(L)加至FOLLOW(S)中，即把')'加至FOLLOW(S)中。最后，FOLLOW(S)为{#，','，)}。

第8题：

已知文法G2=(VT={a，'，'，(，)}，VN={S,L)，S,P)，其中P为，

S→(L)|a

L→L,S|S

(a,a)是L(G2)的句子，这个句子的分析树是(28)。

A．

B．

C．

D．

正确答案：B
解析：根据推导构造分析树，已知文法G[S]，对于w，若w∈L(G)，则存在一个推导序列Sw。分析树的构造步骤如下所述。首先，设置以开始符号S为标识的根结点，然后，对进行的每一步推导，根据使用的产生式，生成一个子树，直至推导结束。设推导使用的产生式为A→x1x2…xn，则生成以A为根结点，从左至右标识为x1，x2，…，xn的子结点的一棵子树。例如，对于本题的文法G2和句子(a,a)，其推导和构造分析树的过程如下：S(L)(L,S)(S,S)(a,S)(a,a)S→(L)L→L,SL→SS→aS→a上面构造树的过程是从树根开始，每进行一步推导，就生出某一子树的子结点，直至推导结束。这种画树过程是从树根到树叶。对于一个w，我们把构造Sw称作句法(语法)分析，上面这种分析过程称为自项向下分析。

第9题：

已知文法G1＝(VT＝{a,b,d}，VN＝{S，A，B}，S,P)，其中P为： S→dAB A→aA|a B→bB|ε 该文法属于(28)文法。

A．0型

B．上下文有关

C．上下文无关

D．正规

正确答案：C
解析：乔姆斯基(Chomsky)把文法分成4种类型，即0型、1型、2型和3型，由此产生的语言分别称为0型、1型、2型和3型语言。这几类文法的差别在于对产生式的形式施加不同的限制，如下表所示。0型文法也称短语文法，1型文法也称上下文有关文法，2型文法也称上下文无关文法，2型文法的识别器模型是下推自动机。3型文法也称线性文法(或称正规文法)，其识别器模型是有限状态自动机。文法G1的所有产生式形式都是A→β，其中A∈VN，β∈V*，且第1条规则S→dAB是非线性的，因此文法G1属于2型文法，又称上下文无关文法。

第10题：

假设某程序语言的文法如下：

S→a|b|(T)

T→TdS|S

其中，VT={a，b，d，(，))；VN={S，T}，S是开始符号。考察该文法，句型(Sd(T)db)是S的一个(28)。

其中(29)是最左素短语，(30)是该句型的直接短语。

(74)