Re: Parsing expressions directly into an abstract syntax tree

Russell Shaw <rjshaw@netspace.net.au>
8 Jan 2006 11:37:54 -0500

          From comp.compilers

Related articles
Parsing expressions directly into an abstract syntax tree travis_nixon@yahoo.com (Travis Nixon) (2006-01-07)
Re: Parsing expressions directly into an abstract syntax tree rjshaw@netspace.net.au (Russell Shaw) (2006-01-08)
Re: Parsing expressions directly into an abstract syntax tree ncannasse@motion-twin.com (Nicolas Cannasse) (2006-01-09)
| List of all articles for this month |

From: Russell Shaw <rjshaw@netspace.net.au>
Newsgroups: comp.compilers
Date: 8 Jan 2006 11:37:54 -0500
Organization: Compilers Central
References: 06-01-011
Keywords: parse, AST
Posted-Date: 08 Jan 2006 11:37:54 EST

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.


Post a followup to this message

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