A.(Sd(T)db)B.d(T)C.TdD.Sd(T)d

Question

A．(Sd(T)db)

B．d(T)

C．Td

D．Sd(T)d

Answer 1

正确答案：A
解析：解答本题要搞清楚基本概念。要检查由符号串x是否是文法G的一个句型或者句子，就要检查是否存在一个由S到a的x的推导。推导树的每一个结点和终结符或者非终结符相关联。和终结符关联的结点是叶结点，而与非终结符相关联的结点可以是叶结点，也可以是非叶结点，树的根结点为文法的开始符号S。已知符号串x在文法G中的一个推导，就可以构造相应的推导树。将x中的每一步产生式的应用表达从所替代的非终结符号生长出新的树杈，且子结点自左向右逐个和产生式的右部符号相关联。因此，每棵推导树的终端结点自左至右所构成的字符串应该是文法G的一个句型，如果所有的终端结点都是与终结符关联的，则该字符串是文法G的一个句子，此时该推导树是完全推导树。题中的句型(Sd(T)db)的第一步肯定是由S→(T)→(TdS)得出的。按照最左推导的规则(TdS)→(TdSdS)→(SdSdS)，最终不可能推出原来的句型。按照最右推导的规则(TdS)→(Tdb)→(Td(T)db)，最终不可能推出原先的句型。最后可以看出句型(Sd(T)db)是由一般推导推出的，步骤如下：S→(T)→(TdS)→(Tdb)→(Td(T)db)→(Sd(T)db)此文法推导树如图6-7示。所以，S是句型相对于规则T→S的直接短语，也是最左直接短语(句柄)。(T)是句型相对于规则S→(T)的直接短语，对于问题(34)，答案A是正确的。素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他的素短语。备选答案中只有B满足条件，所以，问题(35)的正确答案为B。b是句型Sd(T)db相对于规则S→b的直接短语，S是句型Sd(T)曲相对于规则T→S的直接短语，(T)是句型Sd(T)曲相对于规则S→(T)的直接短语，所以问题(36)的答案为B。由推导树可知，无-论如何，无法由S推导出d(T)，Td或Sd(T)d，所以问题(37)的正确答案为A。