Re: Parsing implicit operators with recursive descent?

Johann 'Myrkraverk' Oskarsson wrote:


> Is it possible to parse implicit operators, like the regular
> expression concatenation operator, with a recursive descent parser?


> That is, to be explicit, is it possible to make a recursive descent
> parser that produces (*) the following parse tree on this input "aab":
>
> @
> / \
> @ b
> / \
> a a


It's completely trivial for hand-written recursive descent. Here's
pseudocode:


parseConcat:
    result = parseElement()
    while notEof() do
        result = makeConcat(result, parseElement())
    return result


.... assuming parseElement() handles items in the concatenation at the
right level of precedence. The loop is useful to avoid redundant
recursion in long sequences; also, using an explicit vector or similar,
rather than a parse tree, might be wise considering a pathologically
deep tree. And of course, the exit condition of the loop would need to
be changed for things like parentheses used for precedence (i.e. check
for closing parenthesis), but this should give you a hint as to the
right direction.


-- Barry


--
http://barrkel.blogspot.com/

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