2.2.2 通过正式语法生成句子

图Fig 2.3中的语法,就是所谓的我们的t,d&h 短语结构语法(通常缩写为PS语法)。还有一个更紧凑的形式,左侧相同的,对应的右侧写在一起用竖线“|”隔开。这条竖线只是一种形式,就像箭头--->一样,可以读作“或其他”。右侧被竖线分隔开的,也被叫做备选项。这种更简洁的形式下,我们的语法变成了:

图1

带有下角标s的非终结符成为了起始符。(下角标决定了起始符,而不是规则)

现在让我们用这个语法来生成我们的初始例子,只使用根据上述规则的替换方式。我们得到了以下连续形式的句子

图2

中间形式(intermediate forms )被称为句子形式。如果一个句子形式不包含非终结符,那它则被称为一个句子并且属于生成的语言。从一行到下一行的过渡被称为生成步骤,而其规则被称为生成规则,原因很明显。

生成过程可以更加直观,通过使用“图标”在对应符号之间画一条连接线。一个就是一个节点集合,和一组连接起来的。一个节点可以认为是纸上的一个点,一条边是一条线,每条线连着两个点;一个点可能是多条线的结束点。图中的节点通常都是被“标记”的,也就是说它们都有名字,这样就可以很方便的在纸上画出写着它们名字的小圈来代替这些点。 如果这些边是有箭头的,那这个图就是有方向的;如果这些边只是线条,那这个图就是无方向的。几乎所有在解析技术中使用的图都是有方向的。

图标对应上述生成过程见图Fig 2.4。这种图被称为生成树或者句法树,描述了最终句子的句法结构(在给定的语法中)。我们看到的生成图通常是向下的,但偶尔我们也会看到一些星型结构,一般是由重写了一组符号导致。

在图中的一个循环就是一个路劲,从节点N顺着箭头一直在回到节点N。而生成树中是不允许有环的;如下所示。要得到一个环,我们就需要在生成树中有一个非终结符节点N,且N已经有了一个直接或间接指向N的子节点。但由于生成过程总会产生节点的副本,所以他布恩那个生成已经存在的节点。因此一个生成树是“非循环”的;有向无环树被称为dags

Fig 2.4

明显不可能让语法生成tom,dick,harry,任何试图生成多个人名的企图都会带来结束,而摆脱它(我们也必须摆脱,因为这是一个非终结符)的唯一办法就是把第3条规则吸收进来,而这会产生一个“和”。神奇的是,在一个只使用“可能被替换”的系统中我们成功的实施了“必须替换”这一概念;仔细看一下,我们就会发现,我们将“必须替换”分成了“可能替换”和“必须不能是一个非终结符”。

除了我们的标准例子,语法当然还会生成一些其他的句子;例如:

harry and tom harry tom, tom, tom and tom

以及其他更多的。一个决绝和鲁莽的尝试,生成没有“和”的不正确的形式将会让我们得到这样的句子形式,像

tom, dick, harry End

这样的,不是句子的句子形式,而其没有生成规则适用于它们。这种形式被称为死胡同。就像生成规则中的右箭头表明的一样,在相反的方向上规则可能就不适用了。

results matching ""

    No results matching ""