Efficiently building a parse tree from a regular expression

摘要

We show in this paper that parsing with regular expressions in- stead of context-free grammars, when it is possible, is desirable. We present efficient algorithms for performing different tasks that concern parsing: pro- ducing the external representation and the internal representation of parse trees; producing all possible parse trees or a single one. Each of our al- gorithms 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.