Re: Parsing expressions directly into an abstract syntax tree

Travis Nixon wrote:
> I have been working out an algorithm to parse expressions directly
> into an abstract syntax tree, in a way that allows you to give the
> parser arbitrary prefix, postfix, and infix operators, specifying the
> precedence and associativity for each operator. The parsing itself is
> done from left-to-right, with one lookahead token, and very little
> recursion. (recursion only happens when encountering a parenthesized
> sub-expression, and even that could be done away with fairly easily)
>
> As far as I can tell, what I've got so far is something very similar
> to operator precedence bottom-up parsing, but either they're not quite
> the same, or they really are the same, and I just don't really have a
> full understanding of what it is I'm actually doing. (Which is not at
> all outside the realm of possibility)
>
> :)


...


> (cur = op, next = value[subexp], setright)
> [*]
> / \
> a SE
> |
> +
> / \
> b c
>
>
> So...after all that...
>
> What in the world is this method of expression parsing called?


Looks like LL(1) parsing, but because of the simple recursive
tree structure of expressions, you have practically all the
context you need when you have each token, saving having to
do the typical switch-to-a-new-rule-context of parsing a
complex grammar.

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