not requiring any ex ante transformation of the CFG).
performance has been seen as a problem when parsing heavily ambiguous sentences, with both time and space requirements being worstcase cubic (O(N 3 )) in the sentence length N. Tomita (1986) described Shared Packed Parse Forests (SPPFs), a data structure that avoids redundancy when generating and storing parse trees for ambiguous token spans.