Analyser une structure arborescente avec menhir [Résolu]

[sulu45]

Bonjour,

J'essaye de réaliser un "parser" pour le langage utilisé par TaskJuggler (un outil de gestion de projets). Le langage permet de décrire les tâches, les ressources, les délais...

Et il y a notamment le concept de scénarios qui permet en résumé de décrire des variations autour d'un projet. On aura par exemple un scénario où le projet aura un retard de plusieurs jours et un autre où certaines ressources seront plus rares.

Le langage permet d'avoir une arborescence de scénarios sous la forme suivante :

Code :

1
2
3
4
5
6
7
8
9
10
11
  scenario sc1 "Scénario1" {
    scenario sc1.1 "Scénario1.1" {
      scenario sc1.1.1 "Scénario1.1.1" {
      }
    }
    scenario sc1.2 "Scénario1.2" {
      scenario sc1.2.1 "Scénario1.2.1" {
      }
    }
  }

Donc j'ai tout d'abord créé une structure d'arbre de scénarios mais maintenant je ne vois pas comment analyser le code TaskJuggler avec menhir pour remplir mon arbre ??

Quelqu'un aurait-il un exemple simple de "parser" en menhir ou en ocamlyacc pour ce type de structure ?

Merci.
Stéphane.

[Cacophrene]

Bonjour,

Que trouve-t-on à l'intérieur des accolades d'un scénario interne (je veux dire, sans scénario imbriqué à l'intérieur) ? Avec ocamlyacc, tu peux utiliser quelque chose comme ceci (attention, c'est juste une ébauche, le code n'est pas fonctionnel). J'ai noté MyTree.tree la structure arborescente qui représente un scénario :

Code :

1
2
3
4
5
6
7
8
9
10
%token <string> NAME
%token <string> TEXT
%token SCENARIO
%token LBRACE RBRACE
%type <MyTree.tree> expr

expr: 
  | ...
  | SCENARIO NAME TEXT LBRACE expr RBRACE { MyTree.Scenario ($2, $3, $5) }

Mais peut-être que si c'est une imbrication simple avec quelques mots-clefs, tu n'as pas vraiment besoin de passer par lex/yacc. Tu as essayé de voir si tu t'en sors avec le module Genlex ?

Cordialement,
Cacophrène

[sulu45]

Bonjour,

Merci pour ta réponse.

Je n'ai pas essayé avec Genlex parce que je souhaite justement utiliser concrètement un outil du type yacc. Et le langage proposé par TaskJuggler me paraît suffisamment complexe pour justifier l'utilisation de ce type d'outil.

Dans un scénario on peut seulement avoir un autre scénario et/ou un seul attribut "active" qui est un booléen :

Code :

1
2
3
4
5
6
7
  scenario plan "Planned Scenario" {
    scenario actual "Actual Scenario"
    scenario test "Test Scenario" {
      active no
    }
  }

En utilisant ce que je pense être l'équivalent de ton exemple avec menhir :

Code :

1
2
3
4
5
6
7
8
9
10
scenario:
| SCENARIO id=ID name=string opt=option(delimited(LEFT_CURLY, scenario, RIGHT_CURLY))
    { 
      let node = OCTJ_Scenario.make ~id:id ~name:name in
      let tree = OCTJ_NTree_Structure.make node in
      match opt with
      | None -> tree
      | Some child -> OCTJ_NTree_Structure.add_child tree child
    }

il arrive bien à analyser ce type de code :

Code :

1
2
3
4
5
6
7
8
  scenario sc1 "Plan 1" { 
    scenario sc11 "Plan 11, sub scenario in sc1" {
      scenario sc111 "Plan 111, sub scenario in sc11" {
        scenario sc1111 "Plan 1111, sub scenario in sc111"
      }
    }
  }

mais pas celui-ci :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
  scenario sc1 "Plan 1" { 
    scenario sc11 "Plan 11, sub scenario in sc1" {
      scenario sc111 "Plan 111, sub scenario in sc11" {
        scenario sc1111 "Plan 1111, sub scenario in sc111"
      }
    }
    scenario sc12 "Plan 12, sub scenario in sc1" {
      scenario sc121 "Plan 121, sub scenario in sc12" {
        scenario sc1211 "Plan 1211, sub scenario in sc121"
      }
    }
  }

Autrement dit il n'accepte pas un autre scénario de même niveau (ce qui est légal avec TaskJuggler).

J'ai essayé ceci :

Code :

1
2
3
scenario:
| SCENARIO id=ID name=string opt=option(delimited(LEFT_CURLY, scenario, RIGHT_CURLY)) suite=option(scenario)

mais menhir indique un conflit. Comment je peux lui indiquer qu'il peut y avoir une suite de scénarios dans un même niveau ?

Merci.
Stéphane.

[gasche]

Une solution (pas testée) est de dire qu'un scénario est soit une imbrication de scénario comme tu fais, soit une liste de scénarios ("au même niveau"):

Code :

1
2
3
scenario:
| SCENARIO id=ID name=string opt=option(delimited(LEFT_CURLY, scenario, RIGHT_CURLY)) { ... }
| children = list(scenario) { ... }

[sulu45]

Menhir produit alors l'erreur suivante :

Code :

1
2
3
4
5
Error: the grammar is ambiguous.
The following items participate in an epsilon-cycle:
scenario -> . list(scenario) 
list(scenario) -> . scenario list(scenario)

Mais c'est en effet quasiment la solution, apparemment il suffit d'utiliser :

Code :

1
2
3
scenario:
| SCENARIO id=ID name=string opt=option(delimited(LEFT_CURLY, list(scenario), RIGHT_CURLY))

Et là tout fonctionne ! Merci beaucoup pour votre aide.

[Cacophrene]

Bonjour,

Je note que le problème évoqué dans cette discussion est marqué comme résolu : c'est très bien.
Quoi qu'il en soit, je voudrais revenir un peu sur cette histoire de module Genlex et ajouter mon grain de sel à la discussion.

Envoyé par sulu45

Je n'ai pas essayé avec Genlex parce que je souhaite justement utiliser concrètement un outil du type yacc. Et le langage proposé par TaskJuggler me paraît suffisamment complexe pour justifier l'utilisation de ce type d'outil.

La première partie de la phrase ne me pose aucun problème : c'est bien d'apprendre à utiliser des outils comme yacc/menhir, je n'ai rien à redire là-dessus. Du coup mon message ne change rien à l'intérêt et/ou à la pertinence de cette discussion. J'ajoute que nous n'avons pas souvent des codes en menhir ici, alors il faut en profiter !

Cependant, pour d'éventuels futurs lecteurs du forum : sans connaître particulièrement TaskJuggler, je constate que le « langage » présenté ici est plutôt simple et ne justifie donc pas vraiment, à lui seul, le recours à un outil de type yacc/menhir. En fait, je ne vois pas de grammaire complexe à mettre en œuvre qui nécessite des outils élaborés comme yacc/menhir.

Rapidement, le code suivant (niveau brouillon) devrait venir à bout de tous les exemples donnés ici dès lors que le nom du scénario suit les conventions lexicales de caml (par exemple, sc111 est valide mais pas sc1.1.1) :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
open Genlex

type scenario =
  | Active of bool
  | Scenario of string * string * scenario list
 
let tokenize = Genlex.make_lexer ["scenario"; "active"; "{"; "}"]

let rec parse_scenario = parser
  | [< 'Kwd "active"; 'Ident x >] -> [Active (x = "yes")]
  | [< 'Kwd "scenario"; 'Ident x; 'String s; 'Kwd "{";
    rem = parse_scenario; 'Kwd "}"; succ = parse_scenario >] ->
    Scenario (x, s, rem) :: succ
  | [< _ >] -> []
   
let parse_file fname =
  let ich = open_in fname in
  let res = parse_scenario (tokenize (Stream.of_channel ich)) in
  close_in ich;
  res

Pour tester : ocaml -I +camlp4 dynlink.cma camlp4of.cma

Attention, ce code nécessite obligatoirement la présence d'une paire d'accolades après scenario, même quand celui-ci est vide. On pourrait développer pour lever cette contrainte, mais ça n'apporterait rien de plus à l'exemple (sauf d'inutiles complications).

Cordialement,
Cacophrène