Help needed with a precedence climbing parser

BlitzMax Forums/BlitzMax Programming/Help needed with a precedence climbing parser

AnthonyB(Posted 2010) [#1]
Hello everyone,

I am working on a precedence climbing recursive descent parser for expressions, based on this: http://www.cs.vu.nl/~eliens/documents/libero/lrintr6.htm

I mainly do it since I'm learning how the algorithm works, so that I can put it to use in a scripting language. But for some reason the precedence doesn't quite work. Could someone take a look at the code and help me?

Here's the code:



This is a direct port of the psuedo-code from the essay I linked to. This is not intended to be the actual parser for my scripting language, but rather a test version, to learn how it works, and to have as a template when I implement it into my real parser. I wrote it really really fast, just to try it out, but now I have been sitting with it for hours and hours on end and I cannot for the life of me figure out what's wrong.

Any help would be appreciated! :)

Regards,
Anthony


AnthonyB(Posted 2010) [#2]
Noone? :) I thought there would at least be SOMEONE who had any idea of how these things worked.


Czar Flavius(Posted 2010) [#3]
I have no idea what a "precedence climbing recursive descent parser for expressions" is, unfortunately, but we've been studying Reverse Polish Notation, which is a way of representing mathematical expressions in a way that is easy for a computer to store and process. You could adapt it, possibly, to other kinds of expression?

Here's the Wiki article: http://en.wikipedia.org/wiki/Reverse_polish_notation
Here's how to convert: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

"Interpreters of Reverse Polish notation are often stack-based; that is, operands are pushed onto a stack, and when an operation is performed, its operands are popped from a stack and its result pushed back on. Stacks, and therefore RPN, have the advantage of being easy to implement and very fast."

If you think this can suit your need, I can explain further. :)


AnthonyB(Posted 2010) [#4]
Thanks for the reply. Precedence climbing is explained in the article I linked to.

I have glanced at Reverse Polish Notation (RPN) before, but precedence climbing is supposed to be even faster, so I never payed much attention to it. And the fact that GCC uses Precedence Climbing for arithmetic expressions just made it even more appealing. But I guess I have to use RPN either way, since neither I, or anyone else seems to be able to grasp what's wrong with the code I posted.

Could you ellaborate further on RPN? I don't need this for evaluating expressions per se, but rather to build an Abstract Syntax Tree from it. This is one reason why I haven't been using RPN. It seems time consuming to first convert an expression to RPN, and THEN to an abstract syntax tree. Or is there a fast way to accomplish this?

Thanks,
Anthony


Warpy(Posted 2010) [#5]
I'm getting round to looking at it, Anthony, give me some time!
Well, I've done a shunting yard algorithm before, I'll see how similar this is.


Warpy(Posted 2010) [#6]
ok, so you never set the precedence of any tokens, that's probably your first error.

EDIT: that fixed, you just had the precedences the wrong way round. Changing the multiplication to 2 and addition to 1 worked.


AnthonyB(Posted 2010) [#7]
Warpy, I tried that, but it still doesn't work. I get this output:

Created leaf node from token: '9'.
Created leaf node from token: '10'.
Created leaf node from token: '6'.
Created leaf node from token: '3'.
Created binary operator node from token: '+' with left operand: '6' and right operand '3'.
Created binary operator node from token: '*' with left operand: '10' and right operand '+'.
Created binary operator node from token: '+' with left operand: '9' and right operand '*'.

But I should get this output (except maybe the order they are created in might be different when it works, but they should be assigned like this):

Created leaf node from token: '9'.
Created leaf node from token: '10'.
Created leaf node from token: '6'.
Created leaf node from token: '3'.
Created binary operator node from token: '+' with left operand: '*' and right operand '3'.
Created binary operator node from token: '*' with left operand: '10' and right operand '6'.
Created binary operator node from token: '+' with left operand: '9' and right operand '*'.


Warpy(Posted 2010) [#8]
That's odd. Here's my code:

All I changed was the precedences and Token.Create. Did you set the associativity field as well?


AnthonyB(Posted 2010) [#9]
Ahhhhhhhhhhhhhhhhhhhhhhhh... Why the hell didn't I see that? :D Thanks!

EDIT: Buuuuuuuuuuuuut... there's still one problem. This solves the precedence issue, but now the operators of the same precedence don't work as expected.

This is the output I get now, when I changed the code:

Created leaf node from token: '9'.
Created leaf node from token: '10'.
Created leaf node from token: '6'.
Created binary operator node from token: '*' with left operand: '10' and right operand '6'.
Created leaf node from token: '3'.
Created binary operator node from token: '+' with left operand: '*' and right operand '3'.
Created binary operator node from token: '+' with left operand: '9' and right operand '+'.

But the last '+' operator should have * as it's right operand, not +.


AnthonyB(Posted 2010) [#10]
Although, when looking closer at it, maybe it does work? It yields the same result, when evaluating the tree, as the output I expected it to have.


Warpy(Posted 2010) [#11]
you might like this for printing out your parsed tree:



AnthonyB(Posted 2010) [#12]
Thanks Warpy! That saved me a bunch of time :)