[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