Efficiently building a parse tree from a regular expression |
| |
Authors: | Danny Dubé Marc Feeley |
| |
Affiliation: | (1) Université de Montréal C.P. 6128, succ. centre-ville, Montréal Canada H3C 3J7 (e-mail: {dube,feeley}@IRO.UMontreal.CA), CA |
| |
Abstract: | We show in this paper that parsing with regular expressions instead of context-free grammars, when it is possible, is desirable.
We present efficient algorithms for performing different tasks that concern parsing: producing the external representation
and the internal representation of parse trees; producing all possible parse trees or a single one. Each of our algorithms
to produce a parse tree from an input string has an optimal time complexity, linear with the length of the string. Moreover,
ambiguous regular expressions can be used.
Received: 21 October 1997 / 30 May 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|