3.1.1 解析树的大小

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

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

正如我们说的,长度为n的输入字符串包含n标记的节点。当解析树尚不存在时,这些节点是没有父节点的叶子。现在我们来构建一棵二叉树来给每个叶子一个父节点,父节点都标记了来自语法的非终结符。第一个父节点P1我们添加的,减少了2个没有父节点的叶子,但是现在P1自身成为了没有父节点的节点;所以我们现在有n+1个节点,其中n-2+1 = n-1个节点没有父节点了。同样的事情发生在添加的第二个父节点P2上,不论P1是否是其子节点;所以现在我们有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就是根节点)。所以单元规则能做的最糟糕的事情就是“延长”每一个节点通过构造因子Cu,因此解析树的大小会小于2Cun

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

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

results matching ""

    No results matching ""