Pretty Printing a tree data structure in 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.

Print the tree *sideways*, root node first, with childen indented. See LISP S-expressions for the canonical ways to represent/print trees. Done right this will take you 1-2 hours. — Ira Baxter, Jun 19 '12 at 16:56
@Sean It doesn't necessarily need to be ascii, I just did that as a simple example — Hunter McMillen, Jun 19 '12 at 17:17
Here's an example of a tree prettyprinted "sideways": http://stackoverflow.com/a/10749970/120163 — Ira Baxter, Jun 19 '12 at 17:30

score 3 · Accepted Answer · answered Jun 19 '12 at 15:05

3

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!

answered Jun 19 '12 at 15:05

Sergio Tulentsev

226,338
43
373
367

1

[How does `git` do it?](http://www.kernel.org/pub/software/scm/git/docs/git-log.html) – Matheus Moreira Jun 19 '12 at 16:13
Thank you, I have never heard of this but it looks really promising. – Hunter McMillen Jun 19 '12 at 17:17
Any ideas as to how I could go about passing this data between classes? Each of the nodes in the above tree represents a class in my compiler, should I just return an array from each of those nodes and gather them into a hash somehow? – Hunter McMillen Jun 19 '12 at 17:21

score 3 · Answer 2 · edited Oct 03 '12 at 08:08

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

Thank you, I will definitely look into this – Hunter McMillen Jun 19 '12 at 18:19 — Hunter McMillen, Jun 19 '12 at 18:19

Pretty Printing a tree data structure in Ruby

2 Answers2