2.2.2 通过形式语法生成句子

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

带有下角标_s的非终结符成为了起始符。（下角标决定了起始符，而不是规则）

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

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

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

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

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

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

除了我们的标准例子，语法当然还会生成一些其他的句子；例如：

harry and tom harry tom, tom, tom and tom

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

tom, dick, harry End

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