+ Répondre à la discussion
Affichage des résultats 1 à 6 sur 6
  1. #1
    Invité de passage
    Inscrit en
    septembre 2008
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : septembre 2008
    Messages : 8
    Points : 1
    Points
    1

    Par défaut Analyser une structure arborescente avec menhir

    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.

  2. #2
    Membre Expert
    Avatar de Cacophrene
    Inscrit en
    janvier 2009
    Messages
    533
    Détails du profil
    Informations forums :
    Inscription : janvier 2009
    Messages : 533
    Points : 1 031
    Points
    1 031

    Par défaut

    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

  3. #3
    Invité de passage
    Inscrit en
    septembre 2008
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : septembre 2008
    Messages : 8
    Points : 1
    Points
    1

    Par défaut

    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.

  4. #4
    Membre Expert
    Inscrit en
    avril 2007
    Messages
    831
    Détails du profil
    Informations forums :
    Inscription : avril 2007
    Messages : 831
    Points : 1 130
    Points
    1 130

    Par défaut

    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) { ... }

  5. #5
    Invité de passage
    Inscrit en
    septembre 2008
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : septembre 2008
    Messages : 8
    Points : 1
    Points
    1

    Par défaut

    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.

  6. #6
    Membre Expert
    Avatar de Cacophrene
    Inscrit en
    janvier 2009
    Messages
    533
    Détails du profil
    Informations forums :
    Inscription : janvier 2009
    Messages : 533
    Points : 1 031
    Points
    1 031

    Par défaut

    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.

    Citation 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

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •