Pretty Printing a tree data structure in Ruby

abstract-syntax-tree expression-trees ruby

Question

I am working on a building a compiler and within that I generate a tree that represents the source program that is passed in. I want to display this is a tree like fashion so I can display the structure of the program to anyone interested.

Right now I just have the tree printing on a single line like this:

ProgramNode -> 'Math' BlockNode -> DeclarationNode -> ConstantDeclarationNode -> const ConstantListNode -> [m := 7, ConstantANode -> [n := StringLiteralNode -> ""TEST"" ]] ; 

What I would like is something like this:

   ProgramNode 
    /     \
'Math' BlockNode
           |
    DeclarationNode
           |
    ConstantDeclarationNode ------------------------------
        /      \                                         |
     const ConstantListNode                              |
             /  |  \      \                              |
             m  :=  7    ConstantANode                   |
                            /  |    \                    |
                           n   :=  StringLiteralNode     |
                                      /    |   \         |
                                      "   TEST  "        ;

I haven't really worked with trees in Ruby, how are they usually represented?

Any help would be appreciated.

1
7
6/19/2012 2:51:57 PM

Accepted Answer

This kind of pretty printing requires quite a bit of math. Besides, it's unclear what should happen if the tree grows too wide for the console window. I don't know of any existing libraries that'll do this. I personally use awesome_print.

tree = {'ConstantDeclarationNode' => ['const',
                                      'ConstantListNode' => ['m', ':=', '7']]}

require 'awesome_print'

ap tree
# >> {
# >>     "ConstantDeclarationNode" => [
# >>         [0] "const",
# >>         [1] {
# >>             "ConstantListNode" => [
# >>                 [0] "m",
# >>                 [1] ":=",
# >>                 [2] "7"
# >>             ]
# >>         }
# >>     ]
# >> }

It has tons of options, check it out!

3
6/19/2012 3:05:27 PM

Popular Answer

You need to check out the Graph gem. It is amazing and remarkably simple to work with. You can choose the direction of your tree and the shape of the nodes, as well as colors and so much more. I first found out about it at Rubyconf last year and was blown away.

It is as simple as:

digraph do
  edge "Programnode", "Blocknode"
  edge "Programnode", "Math"
  edge "Blocknode", "DeclarationNode"
end

Obviously you would want to programmatically enter the edges :)

Here is a link to a pdf of the talk which will give more information on it:

There is also a video of the talk on Confreaks if you are interested.

Cheers, Sean



Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow