问题 单项选择题

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

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的答案是①。

选择题
单项选择题