已知文法G2=(VT={a，'，'，(，)}，VN={S,L)，S,P)，其中P为，S→(L)|aL→L,S|S(a,a)是L(G2)的句子，这个句子的分析树是(28)。A．B．C．D．
题目
已知文法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．
相似考题
参考答案和解析
解析：根据推导构造分析树，已知文法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称作句法(语法)分析，上面这种分析过程称为自项向下分析。
更多“ 已知文法G2=(VT={a，'，'，(，)}，VN={S,L)，S,P)，其中P为，S→(L)|aL→L,S|S(a,a)是L(G2)的句子，这个句子的分析树是(28)。A．B．C．D． ”相关问题
-
第1题：
已知文法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'|ε -
第2题：
设语言L={w|w∈{a,b}+且w中a和b的个数相等}，产生语言L的上下文无关文法是(28)。
A．Ga=(VT={a,b}，VN={S，A，B}，S,P)，其中P为， S→a|aA|bSS A→aB|bS B→b|bA|aBB
B．Gb=(VT={a,b}，VN={S,A,B}，S,P)，其中P为， S→b|bB|aSS B→aS|bA A→a|aB|bAA
C．Gc=(VT={a,b}，VN{S,A,B}，S,P)，其中P为， S→aB|bA A→a|aS|bAA B→b|bS|aBB
D．Gd=(VT={a,b}，VN={S，A，B}，S,P)，其中P为， S→aB|bA|s A→aS|bAA B→bS|aBB
正确答案：C
解析：字母表{a,b}上的任何非空串，从其所含a和b的个数来划分，分成下面3个集合：①a和b的个数相等：②a比b的个数多，但仅要a比b的个数多1个的那些子串；③b比a的个数多，但仅要b比a的个数多1个的那些子串。通过上面的分析，根据用文法规则产生句子的原理，设3个非终结符号，不妨称做S、A、B，它们的产生式分别完成：①用S的产生式推导出a和b的个数相等的串；②用A的产生式推导出a比b的个数多1个的串；③用B的产生式推导出b比a的个数多1个的串。根据3个非终结符号S、A、B的含义，显然，关于S的产生式应该是S→aB|bA。对于A产生的串，若第1个字符是a，则剩下的是a和b的个数相等的串：若第1个字符是b，则跟随b的是a比b的个数多2个的串，这个串是两个a比b的个数多1个的子串。根据上述分析，写出关于A的产生式A→a|aS|bAA。可以通过和A类似的分析，写出关于B的产生式B→b|bS|aBB。可以用归纳法证明上面所写的文法是正确的。现在，我们很清楚被选答案中的4个文法所描述的语言，它们分别是：L(Ga)={w|w∈{a,b}+且w中a比b的个数多一个}L(Gb)={w|w∈{a,b}+且w中b比a的个数多一个}L(Gc)={w|w∈{a,b}+且w中a和b的个数相等}L(Gd)={w|w∈{a,b}+且w中a和b的个数相等} -
第3题：
己知文法G2=(VT＝{a，'，'，(，)}，VN={S，L}，S，P)，其中P为， S→(L)|a L→L，S|S 右句型(L，(L，S))的句柄是(28)。
A．(L，(L，S))
B．(L，S)
C．L,S
D．S
正确答案：C
解析：在自底向上分析的过程中，按最右推导的逆过程构造出最右推导，称为规范归约。关键是每步找出被归约的右句型的“可归约串”，称为“句柄”。请读者仔细领会句柄的定义。右句型(最右推导推导出的句型)γ的句柄是一个产生式A→β以及γ中的一个位置，根据这个位置可找到β，用A代替β得到最右推导的前一个右句型。即如果有下面的最右推导：SaAwaβw那么，在a后A→β是aβw的句柄。句柄右边的w仅含终结符号。有的教课书上，句柄的定义借助于短语、直接短语的定义给出：设G＝(VT,VN，S，P)足一个文法，若SaAγaβγ则在句型aβγ中，β是相对于非终结符号A的短语。又若SaAγaβγ则在句型αβγ中，β是相对于非终结符号A的直接短语，最左边的直接短语称为句柄。根据句型(L，(L,S))的最右推导：S(L,(L))(L，(L，S))(此步最右推导使用规则S→L，S)因此，(L，(L,S)中的L,S是句型(L，(L,S))的句柄。 -
第4题：
已知G4=(VT{a，'，'，(，)}，VN={S，L，L'}，S,P)，其中P为， S→(L)｜a｜ε L→SL' L'→,SL'｜ε FIRST(SL')是(29)。
A．{','，ε}
B．{(，a}
C．{(，a，',')
D．{(，a，',' ，ε)
正确答案：D
解析：FIRST(α)的定义如下：FIRST(α)={a｜αa…，a∈VT}，若αs，则规定ε∈FIRST(α)。从上面定义可以看出，FLRST(α)是从α推导出来的终结符号集合。从SL'推导出的终结符号集合首先包括从S推导出来的终结符号。因为S的规则是S→(L)｜a｜ε，因此，从S推导出来的终结符号有‘(’和‘a’。又因为Sε，因此，FIRST(SL')中也包括从L'推导出来的终结符号。根据L'→，SL'｜ε，从L'推导出来的终结符号是'，'。最后，SL'ε，则ε∈FIRST(SL')。 -
第5题：
已知文法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的推导序列中，既有最左推导，又有最右推导。