HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/735
Title: Normal form algorithms for extended context-free grammars
Authors: Albert, Jürgen
Giammarresi, Dora
Wood, Derick
Keywords: Context-free grammars
C++
Grail
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.
URI: http://hdl.handle.net/1783.1/735
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200001.pdf253KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.