Need to build a tree buttom-up (parse tree) 
Author Message
 Need to build a tree buttom-up (parse tree)

Hello out there,
continuing my adventures with "Parsing C" :) I need to build a parse
tree. Now these trees are built "buttom-up": for an expression like
        8 + 7 * 5
one would build a tree like
  +
  /\
8  *
    /\
  7  5
that is, starting at the simplest components and building up more
complex structures.

Now I would love to use struct::tree from tcllib, but I don't see a
way to use it in this context. Seems to me, there you start out with a
root node - thus building the tree "top-down".
Q 1) Is there a way to use struct::tree for what I need here?
Q 2) if { !$Q1 } {any other way?}
Thanks for any pointers
Helmut Giese



Mon, 18 Dec 2006 01:35:16 GMT  
 Need to build a tree buttom-up (parse tree)

Quote:

> Hello out there,
> continuing my adventures with "Parsing C" :) I need to build a parse
> tree. Now these trees are built "buttom-up": for an expression like
>    8 + 7 * 5
> one would build a tree like
>   +
>   /\
> 8  *
>     /\
>   7  5
> that is, starting at the simplest components and building up more
> complex structures.

> Now I would love to use struct::tree from tcllib, but I don't see a
> way to use it in this context. Seems to me, there you start out with a
> root node - thus building the tree "top-down".
> Q 1) Is there a way to use struct::tree for what I need here?
> Q 2) if { !$Q1 } {any other way?}
> Thanks for any pointers
> Helmut Giese

you could use the splice method to insert nodes above your current
nodes to build it from leaf nodes up, but are you sure thats the order
you are getting you tokens? many times parsers tend to define expressions
in a way that you build in more of an in-order type way (i.e. sytax is
often defined recursively & you match that way too)

Bruce



Mon, 18 Dec 2006 04:52:07 GMT  
 Need to build a tree buttom-up (parse tree)

Quote:
> continuing my adventures with "Parsing C" :) I need to build a parse
> tree. [...]

Can the article "http://en.wikipedia.org/wiki/OpenC_Plus_Plus" show
you more opportunities?


Mon, 18 Dec 2006 17:45:16 GMT  
 Need to build a tree buttom-up (parse tree)
On Wed, 30 Jun 2004 15:52:07 -0500, Bruce Hartweg

Quote:

>you could use the splice method to insert nodes above your current
>nodes to build it from leaf nodes up,

Hi Bruce,
I noticed the splice command, but I was unsure whether it was useful
in my context.
Quote:
> but are you sure thats the order
>you are getting you tokens?

No, I'm not sure (yet) - I'm just starting. Have to get the Dragon
book (and find some time to browse over it) - it's been a long time.

However, in the mean time I found the tree package by Evan Rempel (URL
http://web.uvic.ca/~erempel/tcl). Seems like a perfect fit for my
needs - but then I'm not sure I already know my true needs. Well,
we'll see. Thanks for your advice
Helmut Giese



Mon, 18 Dec 2006 17:57:42 GMT  
 Need to build a tree buttom-up (parse tree)


Quote:
>> continuing my adventures with "Parsing C" :) I need to build a parse
>> tree. [...]

>Can the article "http://en.wikipedia.org/wiki/OpenC_Plus_Plus" show
>you more opportunities?

Thanks for the info. Currently I'll stick to the approach to do the
grunt work myself. But it definitively is interesting to know that
there is a C++ parser available.
Best regards
Helmut Giese


Mon, 18 Dec 2006 21:06:08 GMT  
 Need to build a tree buttom-up (parse tree)
If your problem is drawing such a tree, then your best bet is the TkTree
(C++) extension.
See for example:
http://www.ellogon.org/content_images/Screenshots/EllogonParseViewer.png

(The code for the viewer is publically available :-))

George


Quote:
> Hello out there,
> continuing my adventures with "Parsing C" :) I need to build a parse
> tree. Now these trees are built "buttom-up": for an expression like
> 8 + 7 * 5
> one would build a tree like
>   +
>   /\
> 8  *
>     /\
>   7  5
> that is, starting at the simplest components and building up more
> complex structures.

> Now I would love to use struct::tree from tcllib, but I don't see a
> way to use it in this context. Seems to me, there you start out with a
> root node - thus building the tree "top-down".
> Q 1) Is there a way to use struct::tree for what I need here?
> Q 2) if { !$Q1 } {any other way?}
> Thanks for any pointers
> Helmut Giese



Mon, 18 Dec 2006 23:06:40 GMT  
 Need to build a tree buttom-up (parse tree)

Quote:

> Hello out there,
> continuing my adventures with "Parsing C" :) I need to build a parse
> tree.

Have you already built a parser for your language?  That would be your
first step.


Tue, 19 Dec 2006 00:25:33 GMT  
 Need to build a tree buttom-up (parse tree)
Hi George,
Quote:
>If your problem is drawing such a tree, then your best bet is the TkTree
>(C++) extension.

no, my problem is _building_ the data structures, but I think I'm on
my way now.
Quote:
>See for example:
>http://www.ellogon.org/content_images/Screenshots/EllogonParseViewer.png

Looks impressive.
Have a nice weekend
Helmut Giese


Tue, 19 Dec 2006 18:05:17 GMT  
 Need to build a tree buttom-up (parse tree)


Quote:

>> Hello out there,
>> continuing my adventures with "Parsing C" :) I need to build a parse
>> tree.

>Have you already built a parser for your language?  That would be your
>first step.

Why, sure - that is, I only needed to adapt the one I found on the
wiki. See my message "Added a missing piece" from June 30.
Best regards
Helmut Giese


Tue, 19 Dec 2006 18:12:16 GMT  
 Need to build a tree buttom-up (parse tree)

Quote:




>>>Hello out there,
>>>continuing my adventures with "Parsing C" :) I need to build a parse
>>>tree.

>>Have you already built a parser for your language?  That would be your
>>first step.

> Why, sure - that is, I only needed to adapt the one I found on the
> wiki. See my message "Added a missing piece" from June 30.
> Best regards
> Helmut Giese

That means you are keeping a stack of parser states.  Parsing is a
sequence of shifts and reductions.

Now instead of or in addition to keeping that stack, you keep a stack of
subtrees of the growing parse tree.   At each shift, a leaf node is
created, and the subtree consisting of that node is pushed on the stack.
  At each reduction, zero or more subtrees are popped from the stack,
and their roots become the children of a newly-created node, yielding a
new subtree.  When a correct input is used up, the stack contains a
single item: the finished parse tree.

You will have to find and modify and augment the code that manages the
parser stack.



Thu, 21 Dec 2006 01:52:56 GMT  
 Need to build a tree buttom-up (parse tree)

Quote:
> Why, sure - that is, I only needed to adapt the one I found on the
> wiki. See my message "Added a missing piece" from June 30.

(insert cheap plug)

If a parser generator would aid you, ala yacc, try out my program
"taccle":

http://mini.net/tcl/taccle

--



Thu, 21 Dec 2006 07:44:42 GMT  
 Need to build a tree buttom-up (parse tree)


        [snip]
Quote:
>That means you are keeping a stack of parser states.  Parsing is a
>sequence of shifts and reductions.

>Now instead of or in addition to keeping that stack, you keep a stack of
>subtrees of the growing parse tree.   At each shift, a leaf node is
>created, and the subtree consisting of that node is pushed on the stack.
>  At each reduction, zero or more subtrees are popped from the stack,
>and their roots become the children of a newly-created node, yielding a
>new subtree.  When a correct input is used up, the stack contains a
>single item: the finished parse tree.

Hi Matt,
while what you say is true, it looks like way too much work :) - I'm
not a parser specialist, nor do I intend to become one.

Quote:
>You will have to find and modify and augment the code that manages the
>parser stack.

I am quite happy with Yeti and the way it works. I'll leave it as it
is and won't fiddle around with it.
I just needed a way to build my tree, and since I found the tree
package by Evan Rempel (URL
http://web.uvic.ca/~erempel/tcl), which is designed araound a
different concept from tcllib's struct::tree, I'm well on my way.
Thanks for your input and best regards
Helmut Giese


Thu, 21 Dec 2006 23:34:22 GMT  
 Need to build a tree buttom-up (parse tree)

Quote:


>> Why, sure - that is, I only needed to adapt the one I found on the
>> wiki. See my message "Added a missing piece" from June 30.

>(insert cheap plug)

>If a parser generator would aid you, ala yacc, try out my program
>"taccle":

>http://mini.net/tcl/taccle

Hi Jason,
thanks for the link. I am using Yeti, which is also a Yacc-like parser
generator.
Best regards
Helmut Giese


Thu, 21 Dec 2006 23:36:08 GMT  
 
 [ 13 post ] 

 Relevant Pages 

1. Need help in Tree building routine - Problem stated clearly

2. Self-Adjusting Binary Search Trees (Splay Trees)

3. Self-Adjusting Binary Search Trees (Splay Trees)

4. TREE browse .. Ultra Tree Template - Att Marius

5. cast iron tree stand for Christmas tree

6. Alternate solution to tree -> tree problem

7. B plus trees and b star trees

8. Searching for B-tree/B*-tree package...

9. BLT Tree -vs- BWidget Tree

10. AVL Tree,Binary Tree,Sorting..

11. ANNOUNCE: tree-3.3 - tree widget for Tk-3.3b3

12. searching trees (AVL, 2-3-4 and red-black trees)

 

 
Powered by phpBB® Forum Software