Syntax tree

Syntax tree

Post by gmonc » Sun, 04 Apr 2004 03:21:44


Hi. I'm trying to build an automata from a regular expression, using
the algorithm given in "Regular Expressions into Finita Automata" from
Anne Bruggermann-Klein.

Somewhere in the paper says:

"Let n be the size of E. We begin by converting E into a syntax tree.
The external nodes are labeled with <empty> <epsilon> and the
occurrences of symbols, and the internal nodes are labeled with one of
the operatores +,., or *. Since the regular expressions are generated
by an LL(1) grammar, this can be donde in time O(n). Each node of the
syntax tree corresponds to a subexpression Ev of E".

There's someting here I cannot understand: if you construct and LL(1)
grammar for the language of regular expressions, you don't get a
syntax tree like the one mentioned there, but another where (as
symbols like * or + are part of the strings) all symbols of the
expression are leaves. As the algorith work assuming the
tree-structure mentioned, I cannot go on. Am I missing something? Do I
have to convert from one form to another?

thanks for your help
gmonce