Pretty Printing a tree data structure in Ruby

abstract-syntax-tree expression-trees ruby

Question

I'm developing a compiler, and as part of it, I create a tree that reflects the source program that is input. I want to provide this in a tree-like format so that I can show the program's structure to anybody who is interested.

At the moment, the tree is just printed on a single line like follows:

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

I'd prefer something along these lines:

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

How are trees often represented in Ruby as I haven't actually dealt with them?

We would appreciate any assistance.

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

Accepted Answer

It takes a lot of math to produce this type of beautiful printing. In addition, it's not apparent what ought to happen if the tree expands over the boundaries of the console window. I am not aware of any libraries that will do this now. I use the awesome_print method.

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

require 'awesome_print'

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

Look at all the alternatives it offers!

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

Popular Answer

You should investigate the Graph gem. It is excellent and very easy to use. You have a ton of options for customizing your tree, including the nodes' shapes, colors, and more. I was astounded when I first learned about it at Rubyconf the previous year.

It is as easy as

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

Of course you'd want to input the edges programmatically:)

A connect to a pdf of the lecture that will provide further details is provided below:

If you're interested, you may see a video of the discussion on Confreaks.

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