Forum Programmation.autre [OCaml] Quel stratégie pour transformer un arbre en grammaire ?

Posté par  (site web personnel) .
Étiquettes : aucune
2
22
août
2009
Bonjour, je réalise un utilitaire qui transforme du Java en Lisaac.
Je dispose d'un source java sous forme XML (grâce à un petit programme nommé Java2Xml), que j'importe en Ocaml avec Xml-Light.

Mon xml en caml est représenté avec le type :
type xmls = Elem of (string * (string * string) list * xmls list);;
(c'est celui de Xml Light, mais simplifié car je n'ai jamais de PCData avec l'xml que je traite)

J'ai donc créé une grammaire java sous forme de type Ocaml afin de pouvoir transformer l'arbre XML en grammaire définie en Caml pour pouvoir réaliser quelques transformations.

Voici un morceau de ma grammaire permettant de représenter une propriété (une variable) définie dans une classe :

(* Champ (propriété) défini dans la classe *)
type field = { name_f : string ; type_field : type_def ; transient_f : bool; volatile_f : string; static_f :
bool; final_f : bool; visibility_f : visibility ; litteral_def_f : litteral_def ; lit_expre : expre }
(* TODO : définir valeur littérale *)
and (* DEFINITION D'UN TYPE *)
type_def = { name_t : string; primitive_t : bool ; dimensions : int }
and (* LITTERAUX : entiers, float, chaines, caractères *)
litteral_def = LiteralChar of char
| LiteralNombre of literal_number
| LiteralChain of string
| LiteralBool of bool
| LiteralCaractere of char
| LiteralNull
and visibility = Public | Private | Protected


Voici un exemple d'arbre xml que j'aimerai traiter :

[field name="ANGLE_360" visibility="public" final="true" static="true"]
    [type primitive="true" name="int"/]
    [literal-number kind="integer" value="1920"/]
[/field]
[field name="VIEWPLANE_DISTANCE" visibility="public" final="true"]
    [type primitive="true" name="int"/]
    [paren]
        [binary-expr op="/"]
            [var-ref name="SCREEN_WIDTH"/]
            [literal-number kind="integer" value="64"/]
        [/binary-expr]
    [/paren]
[/field]


Evidemment, vous aurez compris, je veux faire une fonction qui me prend ce bout d'arbre en entré, et me renvoi un type field en sorti avec toutes les infos qui vont bien dedans.

Après 10 ans sans avoir fait de caml (et de toutes façons jamais à ce niveau là), j'avoue que je me casse la tête sur le comment faire...
En particulier, ce qui me bloque est de savoir comment je "ramasse" des informations qui peuvent se trouver sur 3 ou plus niveau de profondeur en une seule structure de données : mon type field est composé d'informations se trouvant dans la balise field, mais aussi dans son fils la balise type, ainsi que dans sa balise fille litteral.
J'imagine que je dois donner mon type field aux fonctions qui vont traiter les élément fils de "field", mais j'ai du mal à trouver une manière concrète de l'écrire

J'ai donc plusieurs idées :

Stratégie 1 : je traite une première fois le xml afin de le simplifier. Par exemple mon exemple là haut pourrait devenir :

[field name="ANGLE_360" visibility="public" final="true" static="true" type_primitive="true" type_name="int" literal_kind="integer" literal_value="1920" /]
[field name="VIEWPLANE_DISTANCE" visibility="public" final="true" type_primitive="true" type_name="int"]
    [paren]
        [binary-expr op="/"]
            [var-ref name="SCREEN_WIDTH"/]
            [literal-number kind="integer" value="64"/]
        [/binary-expr]
    [/paren]
[/field]

ce qui ferait un xml qui colle mieux à ma structure et où les élement fils correspondraient uniquement à mes sous type dans mon enregistrement

Stratégie 2 :

Je ne touche pas à l'arbre Xml et quand je tombe sur un field, j'appel les fonction filtrant les balises type et litteral, auxquels je donne à manger mon type field que j'ai commencé à remplir avec les informations trouvée dans la balise field.
Le problème, c'est que comme j'ai une liste de fils, je suis tenté d'appliquer une fonction List.map à la liste qui me renverrait donc... une liste de type field que je devrait unir en un seul..
Mais j'ai du mal à le formaliser.

Quel stratégie vous semble la meilleur ?

Merci !

  • # Problème de point de vue

    Posté par  . Évalué à 4.

    Bon déjà les deux commentaires évident :
    - essaie de respecter la règle des 80 colonnes, ton type "field" est pas lisible
    - tu as regardé les outils déjà existant qui parsent directement Java -> Ocaml ? Ça existe sûrement, pas mal de gens font de l'analyse statique de Java en OCaml, après leur AST est peut-être pas exactement comme le tien, mais ça me semblerait la méthode la moins fatiguante pour toi


    Sinon, bah tu n'as pas le bon point de vue : pour toi on donne le "field en cours de construction" aux sous-fonctions qui vont explorer les fils de ton noeud XML pour rajouter les infos. Ça suppose des effets de bords et des trucs pas nets. Il vaut mieux faire l'inverse : ta fonction qui parse les fields _appelle_ les sous-fonctions (c'est elle qui dirige le flot de contrôle, pas les fils), récupère tous les résultats d'un coup et s'en sert pour construire l'enregistrement, en une seule fois.

    Entre nous je pense pas que l'approche XML soit la plus simple pour ton truc. Dans 90% tu as des arbres qui ont "un seul enfant de tel type", en XML tu as une liste d'enfants tous types mélangés, tu dois filtrer sur l'attribut et gérer le cas où il n'y en a aucun/plusieurs, c'est pas très pratique. Tu tiens vraiment à ton frontend XML ?


    PS : pourquoi il me fait chier en quotant les guillements, le moteur qui affiche la prévisualisation ? Quand je fais "sans HTML" c'est pire, il pourrit mes accents en plus.

    • [^] # Re: Problème de point de vue

      Posté par  (site web personnel) . Évalué à 2.

      tu as regardé les outils déjà existant qui parsent directement Java -> Ocaml ? Ça existe sûrement, pas mal de gens font de l'analyse statique de Java en OCaml, après leur AST est peut-être pas exactement comme le tien, mais ça me semblerait la méthode la moins fatiguante pour toi
      J'ai regardé et c'est imbitable. Fjavac par exemple http://www.cis.upenn.edu/~stevez/stse-work/javac/index.html
      En plus, il y a de gros problèmes de compatibilité Java 1.5
      Cela dit, j'en ai trouvé un nouveau, mais très vieux ( http://www.cs.cmu.edu/~ecc/joust.tar.gz ) et je vais regarder ça, ou au moins m'en inspirer.

      J'ai tourné le problème dans tous les sens, et le fait que je dois construire ma grammaire avec cette méthode me permet de comprendre ce que je fais

      Sinon, bah tu n'as pas le bon point de vue : pour toi on donne le "field en cours de construction" aux sous-fonctions qui vont explorer les fils de ton noeud XML pour rajouter les infos. Ça suppose des effets de bords et des trucs pas nets. Il vaut mieux faire l'inverse : ta fonction qui parse les fields _appelle_ les sous-fonctions (c'est elle qui dirige le flot de contrôle, pas les fils), récupère tous les résultats d'un coup et s'en sert pour construire l'enregistrement, en une seule fois.

      Donc en gros, j'aurai un truc du genre

      Elem ( "field" , infos, fils) ->
      { name_f=cle(infos,"name") ; type_field=match_type fils ; ...}

      ?
      ie., je colle mes fonction d'exploration de l'arbre dans chaque élément que je veux remplir ? Là ce serait match_type fils qui irait chercher les infos en bas ?
      C'est ça que tu veux dire ?

      Entre nous je pense pas que l'approche XML soit la plus simple pour ton truc. Dans 90% tu as des arbres qui ont "un seul enfant de tel type", en XML tu as une liste d'enfants tous types mélangés, tu dois filtrer sur l'attribut et gérer le cas où il n'y en a aucun/plusieurs, c'est pas très pratique. Tu tiens vraiment à ton frontend XML ?

      Les autres approches sont pas simples non plus, javac est imbitable, et joost est trop vieux...
      Au moins le xml, je peux le manipuler, et de toutes façon, il ressemble à une grammaire java, donc il a une cohérence...

      M'enfin je vais qd même reregarder, mais, entre deux lignes, j'ai reregardé fjavac, et j'y comprend rien, je sais pas où commencer, c'est trop gros, je trouve pas la syntaxe abstraite, etc....

      En tout cas, merci beaucoup pour ta réponse :-)

      « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

      • [^] # Re: Problème de point de vue

        Posté par  . Évalué à 2.

        Je pense que c'est à peu près "ça que je veux dire", même si ton truc est un peu ambigu donc je suis pas certain. Par contre si ton code pour récupérer le résultat pour chaque champ est un peu gros, t'as intérêt stylistiquement à déclarer des variables locales avant, un truc du genre

        Elem ("field", infos, fils) ->
        let name_f = parse_name(infos) in
        let type_field = parse_type(fils) in
        ...
        { name_f = name_f; type_field = type_field; .. }

        C'est la même chose, bien sûr. Et bien sûr t'es pas obligé de déclarer une fonction séparée pour par exemple parse_name si sa définition est très simple, c'était juste pour dire de pas forcément tout mettre dans le tuple.

  • # Parsing

    Posté par  (site web personnel) . Évalué à 3.

    Salut.

    Bon, en fait, tu veux simplement écrire un "bête" analyseur grammatical (un "parser").
    Pour cela, de bons indices ici: http://caml.inria.fr/pub/docs/oreilly-book/html.bak/book-ora(...)

    Sinon, à la main (cf mon code plus bas)

    Ensuite, petite remarque : pour améliorer l'abstraction du code, je te conseille de remplacer les "string" par des types créés à l'occasion
    type tag = string
    type xmls = Elem of (tag * (string * string) list * xmls list);;
    Et ainsi de suite.


    type tag = string
    type key = string
    type value = string

    type xmls = Elem of (tag * ((key * value) option)) * ((xmls list) option)

    type field = {
    tag : key;
    key : key option;
    value : value option;
    children : field list option;
    }

    (*




    *)
    let monXMLS = Elem (
    ("foo", Some ("bar","qux")),
    Some [
    Elem( ("jour", Some ("heure","midi")), None);
    Elem( ("nuit", None), None)])


    let rec parse xmls = match xmls with
    | Elem((t,kvOpt),lOpt) -> parseElem t kvOpt lOpt

    and parseElem t kvOpt lOpt =
    let (k,v) = match kvOpt with
    | Some (k,v) -> (Some k, Some v)
    | None -> (None, None)
    in let l = match lOpt with
    | Some l -> Some (List.map parse l) (* appel récursif d'abord, avant de créer le parent *)
    | None -> None in
    {
    tag = t;
    key = k;
    value = v;
    children = l;
    };;

    parse monXMLS;;



    Une autre solution consiste à utiliser ocamllex et ocamlyacc directement (et encore, tu dois pouvoir utiliser yacc avec tes propres données, sans passer par un lexeur).

    • [^] # Re: Parsing

      Posté par  (site web personnel) . Évalué à 3.

      Il y avait en commentaire, qui fut avalé par templeet, le code suivant:
      <foo bar="qux">
        <jour heure="midi"/>
        <nuit/>
      </foo>

      Et le résultat est
      # - : field =
      {tag = "foo"; key = Some "bar"; value = Some "qux";
       children =
        Some
         [{tag = "jour"; key = Some "heure"; value = Some "midi"; children = None};
           tag = "nuit"; key = None; value = None; children = None}]}

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.