Normal form algorithms for extended context-free grammars

被引：15

作者：

Albert, J

Giammarresi, D

Wood, D ^{[1
]}

机构：

[1] Hong Kong Univ Sci & Technol, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China

[2] Univ Wurzburg, Lerhstuhl Informat 2, D-97074 Wurzburg, Germany

[3] Univ Ca Foscari Venezia, Dipartimento Matemat Applicata & Informat, I-30173 Venice, Italy

来源：

THEORETICAL COMPUTER SCIENCE | 2001年 / 267卷 / 1-2期

关键词：

complexity; efficient algorithms; extended context-free grammars; grammatical representations; normal forms; symbolic manipulation;

D O I：

10.1016/S0304-3975(00)00294-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：35 / 47

页数：13

共 26 条

[1]

Aho Alfred V., 1972, The theory of parsing, translation, and compiling

[2]

BARNES KR, 1972, THESIS MCMASTER U HA

[3] DERIVATIVES OF REGULAR EXPRESSIONS [J].

BRZOZOWSKI, JA .

JOURNAL OF THE ACM, 1964, 11 (04) :481-&

[4]

CAMERON HA, 2000, IN PRESS STRUCTURAL

[5]

COHEN DJ, 1970, COMPUT SURV, V2, P65

[6]

CONNOLLY D, 1997, W3C WEB PAGE XML

[7] AN EASY PROOF OF GREIBACH NORMAL-FORM [J].

EHRENFEUCHT, A ;

ROZENBERG, G .

INFORMATION AND CONTROL, 1984, 63 (03) :190-199

[8] DAGWOOD - A SYSTEM FOR MANIPULATING POLYNOMIALS GIVEN BY STRAIGHT-LINE PROGRAMS [J].

FREEMAN, TS ;

IMIRZIAN, GM ;

KALTOFEN, E ;

YAGATI, L .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1988, 14 (03) :218-240

[9]

GIAMMARRESI D, 1998, P 6 IT C THEOR COMP

[10] A NEW NORMAL-FORM THEOREM FOR CONTEXT-FREE PHRASE STRUCTURE GRAMMARS [J].

GREIBACH, SA .

JOURNAL OF THE ACM, 1965, 12 (01) :42-&

← 1 2 3 →