[antlr-interest] Need help with treewalking
Subhobroto Sinha
subhobrotosinha at rediffmail.com
Tue Jun 28 11:19:13 PDT 2005
Hi
This will just take a few minutes for you pros.
First of all, please get the ANTLR grammar at http://www.geocities.com/subhobrotosinha/novel.txt
The driver (C++) is available at http://www.geocities.com/subhobrotosinha/noveldriver.txt
For now, it just builds an AST for ANY arithmetic expression (C like : +,-,*,/ and () only)
Now, I just want to emit simple instructions in english which would calculate such an expression.
I think that I will be able to do what I want, if I implement an external stack/LIFO - I don't have a problem with that.
But something tells me that ANTLR TreeParser is much more powerful for that - specially after
I went through Michael Barnett's treebuilding tut.
I think that that tut is wildy incomplete - if he had indeed completed the part
on "How to write tree parser rules that explore the abstract syntax trees in a different order than the default left-to-right depth-first traversal."
then maybe, that would have made my day. Too bad - he didn't write it. Did anyone ?
So I want to take a pure ANTLR approach to the problem - I wanna write my TreeParser to do exactly what I want it to.
For example, I want to feed my program this :
START MAIN
MODULE PE0
a = ((b * c) + d) / ((e + f) * g);
END MODULE
END MAIN
Abstract Syntax Tree : (AST is generated correctly)
( MAIN START ( PE0 MODULE ( = a ( / ( + ( * b c ) d ) ( * ( + e f ) g ) ) ) END MODULE ) END MAIN )
Here's the output currently generated :
;start of program 'MAIN'
;start of module 'PE0'
;got assignment
;got indentifier 'a'
;got division
;got addition
;got multiplication
;got indentifier 'b'
;got indentifier 'c'
; multiply them
;got indentifier 'd'
; add them
;got multiplication
;got addition
;got indentifier 'e'
;got indentifier 'f'
; add them
;got indentifier 'g'
; multiply them
; divide them
;assign it to 'a'
;end of module 'PE0'
;end of program 'MAIN'
and this what I want to get : (It's what SHOULD be, instead of what is being currently generated)
;start of program 'MAIN'
;start of module 'PE0'
;got assignment
;got indentifier 'a'
;got division
;got addition
;got multiplication
;got indentifier 'b'
;got indentifier 'c'
; multiply 'b' and 'c'
; store the result a temp register, say 'R0' [Note : I think in this such cases, temp registers should be used - am I correct ? BTW - DON'T use the stack to store temps - there's no stack on the target machine - it's kinda RISC. period.]
;got indentifier 'd'
; add 'd' to the temp register 'R0'
;got multiplication
;got addition
;got indentifier 'e'
;got indentifier 'f'
; add 'e' and 'f'
; store the result a temp register, say 'R1'
;got indentifier 'g'
; multiply 'g' with the temp register 'R1'
; divide 'R0' by 'R1'
; store the result a temp register, say 'R2'
;assign 'R2' to 'a'
;end of module 'PE0'
;end of program 'MAIN'
So you see what I want to do ?
My alter self tells me to get on with implementing an external stack, and then operate on the top two operands once we get a binary op (kinda postfix eval. like)
However, I really wanna know ANTLR well, and I feel if you pros just gave me a head start, then I could understand a little about treewalking.
The current docs are way too much complicated for me (it would have been much better if Terr. explained the theory with a few diagrams), but if I get to grasp about TreeParser, then I indent to write a "Dummies guide to treewalking" ;)
Note that I am NOT interested in evaluating the expression, but in generating the instructions to do so..
BTW - simplified treewalking tuts are very much welcome.
You got me - I WANNA know about treewalking as much as possible, and I won't leave you guys until I do that ;)
Subhobroto Sinha
http://www.geocities.com/subhobrotosinha
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20050628/4d58eee1/attachment-0001.html
More information about the antlr-interest
mailing list