假设某程序语言的文法如下:
S→a|b|(T)
T→TdS|S
其中:Vt=(a,b,d,(,),Vn=S,T,S是开始符号。
考察该文法,称句型(Sd(T)db)是S的一个 (1) 。其中 (2) 是句柄: (3) 是素短语; (4) 是该句型的直接短语; (5) 是短语。
5()
A.(Sd(T)db)
B.d(T)
C.Td
D.Sd(T)d
参考答案:A
解析:
解答本题要搞清楚基本概念。
对于文法G[S],我们称αAβ直接推导出αγβ(也可以说αγβ是αAβ的直接推导),仅当A→γ是文法G的一个产生式,且α,β∈(VT∪VN)*,记做αAβ[*]αγβ。如果存在直接推导序列:α1[*]α2[*]…[*]αn,我们称该序列为a0到an的长度为n的推导,也称为a0可以推导出an,记做a0[*]an。如果n=0,即a0=an或a0[*]an,则记为a0[*]an。如果在每一步的直接推导中,都对最左边的非终结符应用相应的产生式的右部来代替,则称这种推导为最左推导。类似地,如果在每一步的直接推导中,都对最右边的非终结符应用相应的产生式的右部来代替,则称这种推导为最右推导。最右推导常被称为规范推导。
对于文法G,如果有S[*]aA δ且A[*]β,则称β是一个关于非终结符号A的、句型αβδ的短语。如果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。