3.1.1 解析树的大小

一个有n标记的字符串的解析树由属于终结符的n个节点，在加上大量属于非终结符的节点组成。令人惊讶的是，不能有多于C_Gn的属于非终结符的节点，在n标记节点的一个解析树中，*C_G*是由语法决定的一个常量，证明语法没有循环。这意味着，任何解析树的大小都是线性的，根据输入的长度。

表明确实需要用一系列步骤来完成。我们首先证明对语法来说所有右侧都是长度2；这就导致了二叉树，树上每个节点要么有两个子节点要么就是叶子（没有子节点的节点）。二叉树有着显著的特点，所有的给定树叶数量的二叉树都有同样数量的节点，而不在乎它们的形状。下面我们看右侧长度>2的语法，接着有单元规则的语法，最后是可为空规则的语法。

正如我们说的，长度为n的输入字符串包含n标记的节点。当解析树尚不存在时，这些节点是没有父节点的叶子。现在我们来构建一棵二叉树来给每个叶子一个父节点，父节点都标记了来自语法的非终结符。第一个父节点P₁我们添加的，减少了2个没有父节点的叶子，但是现在P₁自身成为了没有父节点的节点；所以我们现在有n+1个节点，其中n-2+1 = n-1个节点没有父节点了。同样的事情发生在添加的第二个父节点P₂上，不论P₁是否是其子节点；所以现在我们有n+2个节点，其中n-2个没有父节点。j步之后，我们就有了n+j个节点，其中n-j个没有父节点，并且在n-1步之后，我们就有2n-1个节点，其中1个没有父节点。那没有父节点的1个节点就是根节点，然后解析树就完成了。所以我们看到，当所有右侧长度是2时，对于输入长度是n的解析树，包含2n-1个节点，其线性在n。

如果有的右侧的长度>2，那可能只需要更少的父节点来构造这颗树。所以整棵树的大小可能会小于2n-1，并且肯定会小于2n。

如果语法包含单元规则 - A → B形式的规则 - 那么添加父节点会减少无父节点数这点就不对了：当一个无父节点的节点B通过规则A → B获得了一个父节点A，它就不再是无父节点的节点了，但是A又成为了无父节点的节点，并且更糟的是，节点数却增加了一个。并且可能有必要重复这个过程，就是说使用规则Z → A，等等。但是最终端元规则的链必定会走到尽头，比如P（所以我们有了P →Q···Z → A → B），或者语法中就有一个环。这意味着P获得了一个有多个子节点的父节点，然后无父节点的节点数减少了（或者P就是根节点）。所以单元规则能做的最糟糕的事情就是“延长”每一个节点通过构造因子C_u，因此解析树的大小会小于2C_un。

如果语法包含形式A → ε这样的规则，只有数量有限的ε能在输入的相邻标记中被识别，或者语法中就又有一个环了。所以可为空规则能做的最糟糕的事情就是“延长”输入通过构造一个因子C_n，在两个标志之间被识别的ε的最大数目，还有解析树的大小都小于2C_nC_un，其线性大小是n。

另一方面，如果语法允许包含循环，以上两个过程就将会在解析树中引入无限延伸的节点，那树的大小就是任何大小了。