假设某程序语言的文法如下:
S→a|b|(T)
T→TdS|S
其中:VT=a,b,d,(,),VNS,T,S是开始符号。
考查该文法,称句型(Sd(T)db)是S的一个 (33) ,其中, (34) 是句柄: (35) 是素短语; (36) 是该句型的直接短语; (37) 是短语。
(37)处填()。
A.[Sd(T)db]
B.d(T)
C.Td
D.Sd(T)d
参考答案:A
解析:
[分析]: 要正确解答本题需要清楚基本概念。
最左(右)推导:任何一步推导过程σ→β(σ,β都是句型)都是对σ中的最左(最右)非终结符进行替换,这种推导为最左 (最右)推导。在形式语言中,最右推导常被称为规范推导。按照最左推导和最右推导的规则,最终都不可能推出原来的句型。最后可以看出句型[Sd(T)db]是由一般推导推出的,步骤如下。
S→(T)→(TdS)→(Tdb)→[Td(T)db]→[Sd(T)db]
本题文法的推导树如图2-10所示。
[*]
所以,S是句型相对于规则T→S占的直接短语,也是最左直接短语(句柄)。(T)尽句型相对于规则S→(T)的直接短语,对于问题B,答案①是正确的。
素短语是一个短语,它至少包含一个终结符,并除自身外不包含其他的素短语。在问题C的备选答案中②③都满足条件,所以对于问题C,答案②③都正确。
b是句型Sd(T)db相对于S→b的直接短语,S是句型Sd(T)db相对于T→S的直接短语, (T)是句型Sd(T)db相对于S→(T)的直接短语,所以问题D的答案为②。
由推导树可知,无论如何无法从S推导出d(T),Td或Sd(T)d,所以问题E的答案是①。