AVERAGE STACK SIZE OF A DERIVATION TREE GENERATED BY A LINEAR CONTEXT-FREE GRAMMAR

被引：2

作者：

KEMP, R

机构：

[1] Universität des Saarlandes, Saarbrücken

来源：

INFORMATION AND CONTROL | 1979年 / 42卷 / 03期

关键词：

D O I：

10.1016/S0019-9958(79)90304-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let Gi = (VN, VT, P, Xi) be a linear context-free grammar with the nonterminals VN, the terminals VT, the start symbol Xi, and a special production system P ⊆ VN × (VNVN ∪ VT). The stack size Si(τ) of a derivation tree τ generated by Gi is the maximum number of nodes in the stack during postorder traversing of τ. We give an explicit formula for the average stack size {if354-1} of a derivation tree with n leaves that are labeled by terminals and show that {if354-2} has an asymptotic behavior of the form {if354-3}, where the functions F1(i)}(n) and F2(i)}(n) are quotients of trigonometric polynomials. © 1979 Academic Press, Inc.

引用

页码：354 / 365

页数：12