Extended Context-free Grammars and Normal Form Algorithms

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 bounds for context-free grammars but do so in nontrivial ways. Specifically, we introduce a new representation scheme for extended contextfree grammars (the symbol-threaded expression forest), a new normal form for these grammars (dot normal form) and new regular expression algorithms. 1 Introduction in the 1960's, extended context-free grammars were introduced, using Backus--Naur form, as a useful abbreviatory notation that made context-free grammars easier to write. More recently, the Standardized General Markup Language (SGML) [13] used a similar ab...