Parseur GraphViz avec Treetop

Cela faisait un bout de temps que je n'avais pas touché à Ruby/GraphViz. En fait, il traine en version 0.9 depuis plus d'un an, faute de temps. Et bien cela va changer. En effet, j'ai enfin trouvé quelques heures pour ajouter l'élément essentiel qui lui permettra de passer enfin en version 1.0 : un parseur DOT.

Avec la version actuelle, il est facile de créer des graphes. Mais il est impossible de modifier un graphe en partant d'un fichier graphviz existant. Pourtant, c'est une fonctionnalité qui me semble relativement importante.

Pour faire ce parseur, je me suis appuyé sur Treetop. Cette librairie est un moteur de PEG pour Ruby, similaire ou célèbre peg/leg¹.

Treetop

Le principe d'un PEG est on ne peut plus simple. Il s'agit tout simplement de rassembler des règles dans une grammaire, chaque règle utilisant des expressions rationnelles. Ainsi si vous voulez décrire une règle de capture pour un nombre entier, vous décrirez ceci avec Treetop :

grammar MyGrammar
  rule integer
    [1-9] [0-9]*
  end
end

Pour utiliser cette grammaire dans un programme Ruby, vous ferez cela :

require 'rubygems'
require 'treetop'

Treetop.load "my_grammar.treetop" 

puts MyGrammarParser.new.parse( "123")
# => #<Treetop::Runtime::SyntaxNode:0x1017d0238>

puts MyGrammarParser.new.parse("Hello")
# => nil

L'ensemble des règles forme un arbre. Avec Treetop, le traitement nécessaire à chaque branche peut être fait de différentes façons. La solution la plus simple, quoique pas forcement la plus jolie, consiste à ajouter, au niveau des règles, les méthodes nécessaires. Dans l'exemple précédent nous pouvons modifier la grammaire de la façon suivante :

grammar MyGrammar
  rule integer
    [1-9] [0-9]* {
      def value
        puts "J'ai trouvé la valeur #{text_value}"
      end
    }
  end
end

Ainsi, un appel du type MyGrammarParser.new.parse("123").value affichera le message J'ai trouvé la valeur 123.

Dans cette démonstration nous utilisons text_value. Il s'agit d'une méthode de la classe Treetop::Runtime::SyntaxNode. En effet, vous avez déjà remarqué que chaque branche de l'arbre est une instance de cette classe. text_value donne le texte capturé. Il existe trois autres méthodes à connaitre dans la classe Treetop::Runtime::SyntaxNode :

• terminal? retourne vrai si nous sommes sur un noeud terminal.
• nonterminal? retourne vrai si nous sommes sur un noeud non terminal.
• elements donne les noeuds capturés par la séquence, uniquement sur un noeud non terminal. Par exemple, dans le cas de la règle integer décrite ci-dessus, elements renvoie un tableau dont le premier élément correspond à la valeur capturée par [1-9] et le second la valeur capturée par [0-9]*.

L'autre méthode pour traiter les branches consiste à définir des classes héritant de Treetop::Runtime::SyntaxNode et à préciser, au niveau des règles, la classe à utiliser. Nous pouvons ainsi transformer notre exemple de la façon suivante :

grammar MyGrammar
  rule integer
    [1-9] [0-9]* <MyInteger>
  end
end

Puis,

require 'rubygems'
require 'treetop'

Treetop.load "my_grammar.treetop" 

class MyInteger < Treetop::Runtime::SyntaxNode
  def value
    puts "J'ai trouvé la valeur #{text_value}"
  end
end

MyGrammarParser.new.parse("123").value
# => j'ai trouvé la valeur 123

Voici un exemple un peu plus complet qui vous montrera comment, en seulement quelques lignes, nous pouvons développer une calculatrice en notation polonaise inverse.

grammar Rpn
  rule expression
    space (number / operator)* space <Expression>
  end

  rule operator
    (!number .) space <Operator>
  end
  
  rule number
    (float / integer) space <Number>
  end

  rule integer
    "0" <MyInteger> / [1-9] [0-9]* <MyInteger>
  end

  rule float
    integer "." [0-9]+ <MyFloat>
  end
  
  rule space
    [\ \t]*
  end
end

require 'rubygems'
require 'treetop'

Treetop.load "rpn.treetop" 
class Expression < Treetop::Runtime::SyntaxNode
  def eval( stack )
    elements[1].elements.each do |e|
      e.eval( stack )
    end
  end
end

class Number < Treetop::Runtime::SyntaxNode
  def eval( stack )
    elements[0].eval( stack )
  end
end

class Operator < Treetop::Runtime::SyntaxNode
  def eval( stack )
    one = stack.pop
    two = stack.pop
    stack << two.send( elements[0].text_value, one)
  end
end

class MyInteger < Treetop::Runtime::SyntaxNode
  def eval( stack )
    stack << text_value.to_i
  end
end

class MyFloat < Treetop::Runtime::SyntaxNode
  def eval( stack )
    stack << text_value.to_f
    p stack
  end
end

stack = []
r = RpnParser.new.parse(ARGV.join(" ")).eval( stack )

print "Stack : "
p stack

Ruby/GraphViz

Et Ruby/GraphViz dans tout cela ? Et bien si vous regardez dans mes derniers commits, vous verrez que j'ai ajouté un parseur DOT, et qu'il est donc possible de modifier un graphe créé à partir d'un fichier GraphViz.

Si nous partons du code suivant :

digraph G {
  Hello->World

}

Nous obtenons le graphe suivant :

Si maintenant nous utilisons le code suivant pour traiter ce fichier :

require 'graphviz'

GraphViz.parse( "hello.dot", :path => "/usr/local/bin" ) { |g|
  g.get_node("Hello") { |n|
    n[:label] = "Bonjour"
  }
  g.get_node("World") { |n|
    n[:label] = "Le Monde"
  }
}.output(:output => "png", :file => "hello.png")

Nous obtenons ceci :

Cool non ?

En pratique, si vous récupérer les sources sur Github, vous verrez que non seulement il y a abondances de trace lors de l'utilisation de ce parseur, mais qu'en plus il comporte beaucoup de limites. Ceci est dû au fait que je me suis appuyé sur une version simplifiée de la grammaire du langage DOT qui oblige l'utilisation du point-virgule (;) comme séparateur d'instruction et de la virgule (,) comme séparateur de propriétés. Enfin, DOT autorise les chaines HTML entre bra (<) et ket (>), ce que je n'ai pas pris en compte. Bref, il existe des limites que je dois lever avant une diffusion.

¹ le lecteur notera l'excellente version réentrante développée initialement par _why