HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
|Title: ||Normal form algorithms for extended context-free grammars|
|Authors: ||Albert, Jürgen|
|Keywords: ||Context-free grammars|
|Issue Date: ||14-Jan-2000 |
|Citation: ||Theoretical Computer Science 267, (2001), 35-47.|
|Series/Report no.: ||HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2000-01|
|Abstract: ||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.|
|Appears in Collections:||CSE TCSC Research Reports|
Files in This Item:
All items in this Repository are protected by copyright, with all rights reserved.