Please use this identifier to cite or link to this item:

Normal form algorithms for extended context-free grammars

Authors Albert, Jürgen
Giammarresi, Dora
Wood, Derick
Issue Date 2000-01-14
Source Theoretical Computer Science, v.267, 2001, P. 35-47.
Summary We investigate the complexity of a variety of normal-form transformations for extended context-free grammars, where by extended we mean that the set of 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 provide a C++ toolkit for the symbolic manipulation of context-free objects just as Grail does for regular objects. Our results generalize known complexity bounds for context-free grammars but do so in nontrivial ways. Specifically, we introduce a new representation scheme for extended context-free grammars (the symbol-threaded expression forest), a new normal form for these grammars (dot normal form) and new regular expression algorithms.
Language English
Format Technical report
Files in this item:
File Description Size Format
200001.pdf 253.16 kB Adobe PDF