Re: Parsing expressions directly into an abstract syntax tree

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

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