Transformation d'une string en syntaxe abstraite

**funtix** · 14/02/2007, 20h26

Salut

A partir d'une expression algébrique contenue dans une string, je voudrais construire la syntaxe abstraite (AST).

Prenons un exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
let expr_s = "2 * var^2 + var - 1";;
 
(* Element de la syntaxe abstraite *)
type expr = 
  | Const of int
  | Var of string
  | Add of expr * expr
  | Mul of expr * expr
  | Exp of expr * int;;
 
(* La fameuse fonction qui prend en entrée une string est retourne l'AST *)
let String_to_Expr = ????
 
(* L'AST attendue est :   
Add( Add( Mul( Const 2, Exp( Var "var", 2)), Var "var"), Const -1)  
*)

Je debute en ocaml, y a quelques mois j'avais commencé a coder un programme qui donne la derivée d'une expression en m'inspirant de l'exemple du livre SICP. Et puis par manque de temps, j'ai laissé de coté ce projet. Je le reprend aujourd'hui et j'ai l'impression de repartir de zero par manque de pratique.

Avez vous une solution facile pour ce probleme?

Merci d'avance.

ps: je suis content de voir que les choses ont evolué sur le forum et que maintenant ocaml a le droit a sa propre section.

**gorgonite** · 14/02/2007, 20h55

perso, j'utiliserais ocamllex/ocamlyacc pour générer mon ast

**Strab** · 14/02/2007, 21h53

Voici un lien vers l'énoncé et le corrigé d'un TP que j'avais fait en prépa sur l'évaluation de formules simples, ça t'aidera peut-être : http://pauillac.inria.fr/~quercia/cd...s/formules.tgz

On avait aussi fait un évaluateur d'un mini-caml, mais je ne le retrouve pas et c'était semblable au lien précédent.

**funtix** · 14/02/2007, 23h28

En attendant vos reponse j'ai trouvé ca
C'est un exemple tres detaillé pour l'evaluation d'un programme en BASIC.

Pour ce qui est de ocamllex et ocamlyacc, c'est pas trop l'usine a gaz pour parser une string comme j'ai? Et puis mon but, c'est aussi d'apprendre le language et donc se casser un peu la tete sans utiliser des solutions toutes faites... Qu'en pensez vous?

Sinon je pense que le corrigé du TP parait pas mal pour commencer. Pour faire des trucs plus evolués je jeterais un coup d'oeil sur le lien precedemment cité.

**InOCamlWeTrust** · 15/02/2007, 10h15

Que dalle ! Vous vous plantez-là !

Il faut utiliser le module Genlex de la librairie standard. La doc se trouve ici :

http://caml.inria.fr/pub/docs/manual...ef/Genlex.html

ocamllex/ocamlyacc c'est bien, mais pour ce genre de trucs, utiliser ce petit module est bien plus simple.

Si tu veux réellement utiliser les arbres de syntaxe internes, il faut voir Camlp4, mais ça ne t'aidera pas beaucoup, je pense.

**Patriarch24** · 15/02/2007, 10h39

Il faut utiliser le module Genlex de la librairie standard

Absolument d'accord.

**gorgonite** · 15/02/2007, 11h17

Envoyé par InOCamlWeTrust

ocamllex/ocamlyacc c'est bien, mais pour ce genre de trucs, utiliser ce petit module est bien plus simple.

j'aurais du proposé menhir...

**Steki-kun** · 15/02/2007, 12h46

Envoyé par Patriarch24

Absolument d'accord.

+1 !

Cela dit c'est bien de savoir utiliser ocamlyacc et lex (non c est pas une usine a gaz d'abord

) mais Genlex permet de faire deja pas mal de trucs, c simple, c dans ton fichier .ml, etc. J'ai déjà refait caml light presqu'en entier rien qu'avec genlex

**InOCamlWeTrust** · 15/02/2007, 19h19

Genre tu as refait Caml Light ! Et pour l'analyse syntaxique, tu as fait comment ?

**funtix** · 15/02/2007, 21h01

Cool genlex

Par contre, par curiosité j'ai voulu voir comment c'etait implementé... et j'ai rien compris.
J'ai du mal avec toutes ces fonctions imbriquées les une dans les autres avec 'in' 'and' etc... a voir les sous blocs... Quand on voit ca, je trouve pas que ocaml soit particulierement lisible. J'imagine que c'est de l'entrainement...

Genlex repose sur les streams a premiere vue, et je n'ai pas encore abordé ce point. Mais je vais essayer de comprendre comment fonctionne ce module.

[EDIT] Je ne comprends pas l'utilisation du constructeur Some (que je ne connaissais pas avant ce soir).

Pourquoi ne pas faire tout simplement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
  match Stream.peek strm__ with
       ' ' | '\010' | '\013' | '\009' | '\026' | '\012' ->
        Stream.junk strm__; next_token strm__
    | 'A'..'Z' | 'a'..'z' | '_' | '\192'..'\255' as c ->
        Stream.junk strm__;
        let s = strm__ in reset_buffer (); store c; ident s

Au lieu de,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
match Stream.peek strm__ with
      Some (' ' | '\010' | '\013' | '\009' | '\026' | '\012') ->
        Stream.junk strm__; next_token strm__
    | Some ('A'..'Z' | 'a'..'z' | '_' | '\192'..'\255' as c) ->
        Stream.junk strm__;
        let s = strm__ in reset_buffer (); store c; ident s

Il me semble que c'est possible?

**Patriarch24** · 16/02/2007, 12h02

En général, on utilise un type inductif pour unifier des données, en particulier pour les types de retour des fonctions.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
type result = Some of int | None;;

Cela est particulièrement utile pour éviter les fonctions partielles :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
let fact n = 
   let rec aux var (Some acc) = 
       if(var = 0) 
         then (Some acc)
       else aux (var-1) (Some (acc*var))
   in
      if (n<0)
        then None
      else aux n (Some 1);;
 
fact : int->result

qui calcule la factorielle quel que soit le nombre en entrée (pas d'exceptions). Je suppose que l'utilisation de Some ici est due à la définition du type associé.

**InOCamlWeTrust** · 19/02/2007, 23h16

Plus généralement, on se sert du type 'a option pour marquer le fait qu'une valeur peut être présente ou non dans un type.

En ce moment, je m'en sers beaucoup dans des arbres de syntaxe, ou certaines parties de syntaxe peuvent être absentes, comme par exemple des constructions optionnelles ou des mots-clef optionnels (ou autres...).

Pour ce qui est de la fonction plus haut.

Autre chose : les constructeurs Some et None font partie du module Pervasives, celle qui est ouverte par défaut, et ils sont regroupés sous le nom de type 'a option... donc pas la peine de les redéfinir.

**Patriarch24** · 21/02/2007, 16h45

Autre chose : les constructeurs Some et None font partie du module Pervasives, celle qui est ouverte par défaut, et ils sont regroupés sous le nom de type 'a option... donc pas la peine de les redéfinir.

effectivement, j'aurais dû le préciser. D'ailleurs, je me demande pourquoi j'ai nommé mon type result... (à vouloir répondre trop vite...)

**zekabyle** · 23/02/2007, 17h09

où peut-on télécharger Menhir pour windows?

**gorgonite** · 23/02/2007, 17h19

Envoyé par zekabyle

où peut-on télécharger Menhir pour windows?

déjà que menhir pour linux via godi plante à la compil...

**LLB** · 23/02/2007, 19h15

Je l'avais installé sous Linux, via Godi, et ça marche parfaitement.

où peut-on télécharger Menhir pour windows?

Je ne sais pas. A priori, il n'y a que les sources de disponibles... tu peux t'amuser à les compiler.

http://cristal.inria.fr/~fpottier/menhir/

**Steki-kun** · 23/02/2007, 22h06

Envoyé par LLB

Je l'avais installé sous Linux, via Godi, et ça marche parfaitement.

Je ne sais pas. A priori, il n'y a que les sources de disponibles... tu peux t'amuser à les compiler.

http://cristal.inria.fr/~fpottier/menhir/

Je confirme je l'ai compilé y'a pas si longtemps que ça il marche très bien. A noter que tu as besoin d'ocaml > 3.9.