Re: Parsing expressions directly into an abstract syntax tree

Nicolas Cannasse <ncannasse@motion-twin.com>
9 Jan 2006 23:48:04 -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: Nicolas Cannasse <ncannasse@motion-twin.com>
Newsgroups: comp.compilers
Date: 9 Jan 2006 23:48:04 -0500
Organization: Guest of ProXad - France
References: 06-01-011
Keywords: parse, LL(1)

> (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?


It's LL(1).


But what you're doing is rewriting the tree in order to take into
account operator priority. You would not have to do that if your syntax
was suitable to be directly parsed with LL(1). For instance in terms of
lisp syntax :


(+ a (* b (++ c))


Or with operators in the middle :


(a + (b * (c ++))


Please notice that parenthesis are required and forgeting them will be a
syntax error. In that case the syntax directly represent the LL(1)
parsable tree, so no need to do some rewriting. However deducing the
priority without parenthesis require a little more work.


I'm using same "trick" as you for the Neko compiler (see
http://nekovm.org) and I guess it's a good way of doing it.


function rec make_binop(op,e,e2) {
        match e2 {
        | EBinop (_op,_e,_e2) when priority _op <= priority op ->
var _e = make_binop op e _e;
EBinop(_op,_e,_e2)
        | _ ->
EBinop(op,e,e2)
        }
}


Nicolas


Post a followup to this message

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