Normal form algorithms for extended context-free grammars

We investigate the complexity of a variety of normal-form transformations f or extended context-free grammars, where by extended we mean that the set o f right-hand sides for each nonterminal in such a grammar is a regular set. The study is motivated by the implementation project GraMa which will prov ide a C++ toolkit for the symbolic manipulation of context-free objects jus t as Grail does for regular objects. Our results generalize known complexit y bounds for context-free grammars but do so in nontrivial ways. Specifical ly, we introduce a new representation scheme for extended context-free gram mars (the symbol-threaded expression forest), a new normal form for these g rammars (dot normal form) and new regular expression algorithms. (C) 2001 E lsevier Science B.V. All rights reserved.