Re: Parsing implicit operators with recursive descent?

> Is it possible to parse implicit operators, like the regular
> expression concatenation operator, with a recursive descent parser?
of course, why would not it be possible?


simple rules such as:
RE = terminal | terminal RE
while make you trees for 'aab' such as


(a . (a . (b)))


where parentheses make a single RE match, '.' is the implicit operator and
each a or b represent a match from 'terminal'.


the 'tree' will probably more look like a list though, it can be important
to note as tree handling in such degenerated case can lead to O(n^2)
treatments while balanced trees may behave in O(n log n)


it _may_ be a reason for the preprocessing (i.e. placing wisely the implicit
operators by pre-balancing their insertions). at least it was the case for
one of the RE engine I did.


(did you have a look at boost::regexp?)


Armel

Return to the comp.compilers page.
Search the comp.compilers archives again.