Discussion :

[Fractal LLG]

Bonjour

Je suis en classe prépa scientifique et ce genre de programme m'intéresse tout particulièrement.
Pensez-vous que la création d'un interpréteur de formules mathématiques avec la description précise de toutes les étapes (analyse lexicale, rajout de parenthèses pour tenir compte des priorités des opérations, analyse syntaxique puis calcul) pourrait constituer un bon sujet de TIPE d'info pour les ENS?
Est-ce trop facile, trop difficile, trop banal, trop pauvre?

Merci de vos réponses

Fractal

[millie]

Bonjour

Je suis en classe prépa scientifique et ce genre de programme m'intéresse tout particulièrement.
Pensez-vous que la création d'un interpréteur de formules mathématiques avec la description précise de toutes les étapes (analyse lexicale, rajout de parenthèses pour tenir compte des priorités des opérations, analyse syntaxique puis calcul) pourrait constituer un bon sujet de TIPE d'info pour les ENS?
Est-ce trop facile, trop difficile, trop banal, trop pauvre?

Merci de vos réponses

Fractal

Alors, si tu traites l'analyse lexicale, l'analyse syntaxique de manière générale, ça peut être assez difficile (l'analyse syntaxique en soit sans analyseur syntaxique tout fait comme yacc est casse gueule) et donc intéressant.
Si tu traites plus rapidement l'analyse syntaxique, je te conseille de tenter de partir sur un petit compilateur simple (qui est plus difficile qu'un intérpréteur en général car il y a l'analyse sémantique).

Par exemple un compilateur d'expression mathématique vers un langage 3 adresses (type assembleur sans registre) pourrait ressembler à :

Entrée :

Code :

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

(3*3+2)*4

Sortie:

Code :

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

1
2
3
4
5
6
u1 = 3;
u2 = 3;
u1 = u1 * u2;
u2= 2;
u1 = u1+u2
...

(avec gestion maligne ou non des variables)


Maintenant, je crois que les TIPE, c'est 15min de présentation ? Même avec ça, ça peut vite passer

Il est possible que je bouge ces messages, je préviendrais ce qui ont participé.

[Fractal LLG]

Alors, si tu traites l'analyse lexicale, l'analyse syntaxique de manière générale, ça peut être assez difficile (l'analyse syntaxique en soit sans analyseur syntaxique tout fait comme yacc est casse gueule) et donc intéressant.

À priori, l'analyse syntaxique m'intéresse aussi, j'ai envie de comprendre l'intégralité de la démarche qui d'une expression mathématique sous forme de chaîne de caractères emmène à son évaluation numérique

Si tu traites plus rapidement l'analyse syntaxique, je te conseille de tenter de partir sur un petit compilateur simple (qui est plus difficile qu'un intérpréteur en général car il y a l'analyse sémantique).

En quoi consiste l'analyse sémantique?
Et quel est l'avantage du compilateur d'expressions mathématiques si un interpréteur fait la même chose avec une phase en moins?

Maintenant, je crois que les TIPE, c'est 15min de présentation ? Même avec ça, ça peut vite passer

Aux ENS il n'y a pas de présentation : quelques jours avant l'épreuve, on rend une fiche récapitulant ce sur quoi on a travaillé et s'en suit un entretien avec le jury d'environ trois quarts d'heure.
Il s'agit en fait plutôt d'un oral sur un sujet choisi et préparé à l'avance spécialement par le candidat.
Mais bon, c'est pas plus mal d'avoir un truc concret à présenter

Merci

Fractal

[millie]

Déjà, tu peux lire les liens dans Théorie des langages ici : http://general.developpez.com/cours/#generalite (tout ce qui est théorie des langages pures, tu peux sauter, tu peux aller directement à tout ce qui est Théorie de la compilation).

Si t'as un peu de sous ou un accès à une bibliothèque, je te conseille de prendre le livre là : http://general.developpez.com/livres...ue#L2100058878 qui est bien foutu

EDIT : Ce qui est intéressant avec l'analyse sémantique, c'est la partie Gestion de contexte des variables (qu'on ne voit pas dans mon exemple) mais qu'on voit dans un truc du style :

Code :

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

1
2
3
4
5
6
int i = 0;
int k = 20;
for(int j=0; j<k; j++) {
  int i = 2; //différent de l'autre mais même nom
}

Si tu veux un truc plus complexe mais abordable, tu peux faire une compilateur trois adresses d'un langage type C sans fonction, sans structure mais juste avec des types simples (int, char) et les boucles for, while et les if
en compilant vers des trucs qui ressemblent à :

Code :

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

1
2
3
4
5
6
7
8
9
10
v1=0;
v2=20;
label2:
if(v1<v2) goto label1;
v3 = 2

v1 += 1
goto label2
label1:

[Fractal LLG]

Oki, merci beaucoup
Je vais aller voir les liens que tu m'as passé et peut-être que Compilateurs est au CDI de mon lycée ^^
Je vais déjà essayer de voir ce que je peux faire pour un interpréteur de formules mathématiques et si ça marche bien j'irais sans doute farfouiller du côté d'un mini-compilateur

Fractal

[Steki-kun]

De mon temps il n'y avait rien sur les compilos dans ce CDI ! (oui parce que vu ton pseudo, pas très dur de deviner ledit lycée ^^) J'espère que ça a changé, bon courage pour tt le reste en tout cas

[Jean-Marc.Bourguet]

(l'analyse syntaxique en soit sans analyseur syntaxique tout fait comme yacc est casse gueule)

Pas sur que je sois d'accord avec la phrase dans sa generalite. Mais j'ai deja ecrit plus haut ce que je pensais des generateurs...

Si t'as un peu de sous ou un accès à une bibliothèque, je te conseille de prendre le livre là : http://general.developpez.com/livres...ue#L2100058878 qui est bien foutu

S'il s'agit bien de la traduction de "Modern Compiler Design", je confirme que l'original est bien fait (je ne peux rien dire sur la traduction). C'est entre autre l'introduction la plus accessible que je connaisse a la compilation des langages functionnels et logiques.

Dans un tout autre genre, la deuxieme edition de Parsing Techniques qui vient de sortir est excellente. Mais le genre est "bouquin de reference", pas d'introduction. Je le deconseille a Fractal LLG, meme si le sous-titre est "A Practical Guide".

[gorgonite]

Aux ENS il n'y a pas de présentation : quelques jours avant l'épreuve, on rend une fiche récapitulant ce sur quoi on a travaillé et s'en suit un entretien avec le jury d'environ trois quarts d'heure.
Il s'agit en fait plutôt d'un oral sur un sujet choisi et préparé à l'avance spécialement par le candidat.
Mais bon, c'est pas plus mal d'avoir un truc concret à présenter

Ayant passé cet oral dans ma jeunesse, je pense que tu as toutes tes chances avec un sujet comme celui-ci. Mais saches qu'il est fort probable qu'ils mettront un jury assez compétent et qu'ils ne te poseront pas de questions sur ce qu'il y a dans ton rapport... ça m'avait un peu déboussolé, et j'ai été content d'avoir une grosse partie en réserve que je n'avais pas mis car je n'avais pas fini de la formaliser

Pas sur que je sois d'accord avec la phrase dans sa generalite. Mais j'ai deja ecrit plus haut ce que je pensais des generateurs...

j'ai beaucoup de mal à comprendre ce que tout le monde reproche à lex/yacc
ce sont d'excellents outils, et si l'on accepte de "salir" un peu son code, on arrive à parser des langages assez complexes

S'il s'agit bien de la traduction de "Modern Compiler Design", je confirme que l'original est bien fait (je ne peux rien dire sur la traduction). C'est entre autre l'introduction la plus accessible que je connaisse a la compilation des langages functionnels et logiques.

je l'ai survolé et approfondi quelques chapitres, et je n'ai pas été enchanté par la version traduite...

au passage, selon moi le dragon book (version anglaise ) peut convenir à un élève de prépa qui n'a pas de difficultés en info

[Steki-kun]

Ayant passé cet oral dans ma jeunesse, je pense que tu as toutes tes chances avec un sujet comme celui-ci. Mais saches qu'il est fort probable qu'ils mettront un jury assez compétent et qu'ils ne te poseront pas de questions sur ce qu'il y a dans ton rapport... ça m'avait un peu déboussolé, et j'ai été content d'avoir une grosse partie en réserve que je n'avais pas mis car je n'avais pas fini de la formaliser

Je me permets d'appuyer sur ce point soulevé par Gorgonite : la présentation de TIPE aux ENS n'a rien à voir avec celle des Mines, il te faudra absolument en avoir "en réserve" et, dans le cas où ton TIPE s'oriente vers un truc plutôt pratique, t'être abondamment renseigné sur la théorie sous-jacente. Les examinateurs partent du principe que ce qui est dans ton rapport, tu le connais, et ils préfèrent utiliser les 45min pour te questionner sur ce qui manque dans ton rapport :-)

[Fractal LLG]

Merci à tous pour vos réponses

Je suis allé voir au CDI et effectivement il n'y a rien du tout

Ceci dit, j'ai fini la version 0.9 de mon interpréteur de formules mathématiques (il marche, mais est juste pas optimisé et c'est un peu le fouillis par endroits dans le code)
Si vous voulez y jeter un coup d'oeil (c'est écrit en Caml Light) :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
(* Interpréteur d'expressions mathématiques *)

(* Définitions des types, fonctions d'affichage et autres fonctions diverses *)

type Lexeme = (* Comprend les lexèmes, les listes de lexèmes ainsi qu'un symbole particulier Nil qui sert lors de la reconnaissance des parenthèses *)
  | Nil
  | Num of float
  | Symb of char
  | List of Lexeme list;;
  
type Expr = 
  | Nb of float
  | Add of Expr * Expr
  | Sub of Expr * Expr
  | Mul of Expr * Expr
  | Div of Expr * Expr
  | Neg of Expr
  | Sin of Expr
  | Cos of Expr;;
  
let rec print = function (* Affiche une liste de Lexeme *)
  |[] -> ()
  |h::t -> match h with
             | Nil -> print t
             | Num i -> (print_float i; print_string " "; print t)
             | Symb c -> (print_char c; print_string " "; print t)
             | List l -> (print_char `[`; print l; print_char `]`; print_string " "; print t)
  ;;
  
let rec print_expr expr = match expr with (* Affiche une expression *)
  | Nb n -> print_float n
  | Add(a,b) -> (print_char `(`; print_expr a; print_char `+`; print_expr b; print_char `)`)
  | Sub(a,b) -> (print_char `(`; print_expr a; print_char `-`; print_expr b; print_char `)`)
  | Mul(a,b) -> (print_char `(`; print_expr a; print_char `*`; print_expr b; print_char `)`)
  | Div(a,b) -> (print_char `(`; print_expr a; print_char `/`; print_expr b; print_char `)`)
  | Neg a -> (print_char `(`; print_char `-`; print_expr a; print_char `)`)
  | Sin a -> (print_string "(sin"; print_expr a; print_char `)`)
  | Cos a -> (print_string "(cos"; print_expr a; print_char `)`)
  ;;

let rec add lexlist lex = match lexlist with (* Étant donnés une liste de Lexeme et un Lexeme, rajoute ce dernier à la fin de la liste et le plus profondément, ie si la fin de la liste est aussi une liste, on le rajoute à la fin de celle-ci et ainsi de suite, mais en considérant que les listes se terminant par Nil sont pleines *)
  | [] -> [lex]
  | Nil::_ -> lexlist
  | (Num _)::_ | (Symb _)::_ -> lex::lexlist
  | (List [])::t -> (List [lex])::t
  | (List l)::t when hd(l) = Nil -> lex::(List l)::t
  | (List l)::t -> (List (add l lex))::t;;
  
let rec purge liste = match liste with (* Supprime tous les Nil d'une liste de lexèmes (y compris ceux dans les sous-listes) *)
  | [] -> []
  | h::t -> match h with
              |Nil -> purge t
              |Num _ | Symb _ -> h::(purge t)
              |List l -> (List (purge l))::(purge t)
  ;;
 
let rec miroir lexlist = match lexlist with (* Renvoi un miroir de la liste de lexèmes, y compris des sous-listes *)
  | [] -> []
  | h::t -> match h with
              |Nil |Num _ |Symb _ -> (miroir t) @ [h]
              |List l -> (miroir t) @ [List (miroir l)]
  ;;

(* Analyseur lexical : il rentre une chaîne de caractères, il ressort une liste de Lexeme ne contenant pas de Nil ni de List *)

let is_num c = let c' = int_of_char c in (47 < c') && (c' < 58);;

let valeur c = float_of_int( (int_of_char c) - 48 );;

let is_symb c = (c = `+`) || (c = `-`) || (c = `*`) || (c = `/`) || (c = `(`) || (c = `)`) ;;

let lex str = 
  let sortie = ref [] and
      num_now = ref false and (* true si on est entrain de lire un nombre *)
      num = ref 0. and (* si num_now = true, le nombre qu'on est entrain de lire *)
      is_flott = ref false and (* true si on est entrain de lire un flottant *)
      eps = ref 18.57 in
  for i = 0 to (string_length str) - 1 do
    let c = str.[i] in
    
    if is_symb c then 
      if !num_now then (sortie := (Symb c)::(Num !num)::!sortie; num_now := false)
      else sortie := (Symb c)::!sortie
    else if is_num c then
      if !num_now then (if !is_flott then (num := !num +. (valeur c) *. !eps; eps := !eps /. 10.) else num := 10. *. !num +. (valeur c))
      else (num_now := true; num := valeur c)
    else if c = `.` then 
      if !num_now && (not !is_flott) then (is_flott := true; eps := 0.1) else failwith "Erreur de syntaxe"
    else if !num_now then (sortie := (Num !num)::!sortie; num_now := false; is_flott := false)
    else if c = `s` then
      if (string_length str) > (i + 2) && str.[i+1] = `i` && str.[i+2] = `n` then (sortie := (Symb `s`)::!sortie; str.[i+1] <- ` `; str.[i+2] <- ` `) else failwith "Erreur de syntaxe"
    else if c = `c` then
      if (string_length str) > (i + 2) && str.[i+1] = `o` && str.[i+2] = `s` then (sortie := (Symb `c`)::!sortie; str.[i+1] <- ` `; str.[i+2] <- ` `) else (print_int i; print_string str; failwith "Erreur de syntaxe")
    else if c!=` ` then failwith("Erreur de syntaxe !");
  done;
  if !num_now then sortie := ((Num !num):: !sortie);
  rev !sortie;;


(* Prédécoupage selon les parenthèses : on remplace tout couple de parenthèses par la liste des lexèmes situés entre, il rentre une liste de Lexeme ne contenant pas de Nil ni de List, et ressort une liste de Lexeme ne contenant pas de Symb `(` ni de Symb`)` même dans les sous listes *)
  
let decoup liste = 
  let rec decoupage fait sefait reste = match reste with
    | [] -> (sefait)@fait
    | h::t when h = Symb `(` -> (decoupage fait (add sefait (List [])) t)
    | h::t when h = Symb `)` -> if sefait = [] then failwith "Erreur de syntaxe" else 
                                 (match (hd sefait) with
                                 | Nil -> failwith "Erreur de syntaxe"
                                 | Num _ | Symb _ -> decoupage ((List (sefait))::fait) [] t
                                 | List l -> decoupage fait (add sefait Nil) t;)
    | h::t -> (decoupage fait (add sefait h) t);
  in (decoupage [] [] liste);;

(* Résolution des opérateurs unaires : si U est un opérateur unaire (moins négatif, sin ou cos) on parenthèse (Ux) (avec une sous liste)*)

let rec unaires lexlist = match lexlist with
  | [] -> []
  | [Num _] -> lexlist
  | [Symb _] -> failwith "Erreur de syntaxe"
  | [List l] -> [List (unaires l)]
  | [Symb _; _] -> [List lexlist]
  | (Symb c)::h::t when c = `-` || c = `c` || c = `s` -> (unaires ((List [Symb c; h])::t))
  | a::b::t -> a::b::(unaires t)
  | _ -> failwith "Erreur de syntaxe";;

(* Convertisseur en expression : la liste de lexèmes est normalisée : toute sous-liste est de la forme 
   - un truc calculable (nombre ou sous-liste)
ou - un opérateur unaire + un truc calculable
ou - une liste de trucs calculables et d'opérateurs binaires cbcbcbcb...c
   et on le convertit en expression*)

let prior c = if (c = `+`) || (c = `-`) then 1 else 2;; (* si (prior c) = 2, c'est que c = `*` ou `/` *)
let rec priority liste = match liste with
  |[] | [_] -> 3
  |[a;b] -> failwith "Erreur de syntaxe"
  |t::(Symb o)::q -> if (priority q) = 3 then (prior o) else (max (prior o) (priority q))
  |_ -> failwith "Erreur de syntaxe";;

let rec syntax liste = match liste with
  | [] | [Symb _] -> failwith "Erreur de syntaxe"
  | [Num n] -> Nb n
  | [List l] -> syntax l
  | [Symb `-`; n] -> Neg (syntax [n])
  | [Symb `c`; n] -> Cos (syntax [n])
  | [Symb `s`; n] -> Sin (syntax [n])
  | avant::(Symb c)::apres -> if (prior c) < priority apres then (match c with
                                | `+` -> Add ((syntax [avant]),(syntax apres))
                                | `-` -> Sub ((syntax [avant]),(syntax apres))
                                | `*` -> Mul ((syntax [avant]),(syntax apres))
                                | `/` -> Div ((syntax [avant]),(syntax apres))
                                | _ -> failwith "Erreur de syntaxe")
                              else syntax ((List [avant; Symb c; hd apres])::(tl apres));
  | _ -> failwith "Erreur de syntaxe";;

(* Évaluateur : il rentre une expression et il ressort sa valeur calculée *)

let rec calc expr = match expr with
  | Nb n -> n
  | Add(a,b) -> (calc a) +. (calc b)
  | Sub(a,b) -> (calc a) -. (calc b)
  | Mul(a,b) -> (calc a) *. (calc b)
  | Div(a,b) -> let cb = calc b in (if cb = 0. then (failwith "Division par zéro !") else (calc a) /. (calc b))
  | Neg a -> -.(calc a)
  | Sin a -> sin (calc a)
  | Cos a -> cos (calc a)
;;

(* Fonction finale d'évaluation d'une chaîne de caractères *)

let eval str = 
  let lexlist = lex str in
  (*print lexlist;
  print_newline();
  print_newline();
  print (miroir (purge (decoup lexlist)));
  print_newline();
  print_newline();
  print_expr (syntax (unaires (miroir (purge (decoup lexlist)))));
  print_newline();
  print_newline();*)
  print_float (calc (syntax (unaires (miroir (purge (decoup lexlist))))));
  print_newline();;

eval "(1+ (2) * 3 + cos(3 + 2)/sin(1))";;

Il y a 4 étapes :
Analyse lexicale : on sépare les nombres et les sin cos
Détection des parenthèses : on utilise le parenthésage présent dans l'expression pour faire de l'expression presque un arbre
Rajout des parenthèses manquantes : on transforme l'arbre en arbre binaire en se servant de la priorité des opérateurs
Calcul : on calcule l'expression

J'ai pas le temps de l'améliorer maintenant (j'ai TP d'info ) mais j'aurai peut-être le temps ce soir.

Fractal

[gorgonite]

Je suis allé voir au CDI et effectivement il n'y a rien du tout

voici un cours que j'ai reçu il y a quelques temps déjà, et qui devrait te donner toutes les bases nécessaires à la réalisation de ton projet
http://quincy.inria.fr/data/courses/itlp/

il y a bien sûr plein d'autres cours du même niveau, mais je pense que celui-ci te suffira

Ceci dit, j'ai fini la version 0.9 de mon interpréteur de formules mathématiques (il marche, mais est juste pas optimisé et c'est un peu le fouillis par endroits dans le code)
Si vous voulez y jeter un coup d'oeil (c'est écrit en Caml Light) :

J'essayerais de le regarder ce weekend

En revanche, je pense qu'il serait préférable que tu passes à OCaml pour ton TIPE... ce choix ne te sera reproché par personne (même pas aux tetraconcours )

Il y a 4 étapes :
Analyse lexicale : on sépare les nombres et les sin cos
Détection des parenthèses : on utilise le parenthésage présent dans l'expression pour faire de l'expression presque un arbre
Rajout des parenthèses manquantes : on transforme l'arbre en arbre binaire en se servant de la priorité des opérateurs
Calcul : on calcule l'expression

j'ai une remarque sur les parenthèses, je ne pense pas qu'il faille y attacher une importance particulière... il faut juste que tu définisses bien la sémantique de ton langage

[Jedai]

Je me permets d'appuyer sur ce point soulevé par Gorgonite : la présentation de TIPE aux ENS n'a rien à voir avec celle des Mines, il te faudra absolument en avoir "en réserve" et, dans le cas où ton TIPE s'oriente vers un truc plutôt pratique, t'être abondamment renseigné sur la théorie sous-jacente. Les examinateurs partent du principe que ce qui est dans ton rapport, tu le connais, et ils préfèrent utiliser les 45min pour te questionner sur ce qui manque dans ton rapport :-)

Je confirme (en tant que survivant de LLG) ! Pour ma part j'avais fait un petit TIPE sur la reconnaissance de langage naturel. Ma partie pratique était une implémentation d'un trie en Perl, avec reconnaissance des conjugaisons, pluriels et féminin de façon un peu avancé (et un mini-shell pour manipuler le tout) mais bon, c'était complètement un rush de dernière minute, du coup quand les examinateurs m'ont posé certaines questions sur les fondements théoriques de mon code, j'ai fait le mort...
C'était même pas des trucs très forts, simplement réaliser ce que j'avais fait et les analogies avec le programme d'info de Prépa. Donc réfléchis un peu à la théorie avant la présentation.

--
Jedaï

[Fractal LLG]

En revanche, je pense qu'il serait préférable que tu passes à OCaml pour ton TIPE... ce choix ne te sera reproché par personne (même pas aux tetraconcours )

Voui, je compte bien le faire en OCaml plutôt, mais c'est juste que je viens de passer sous Linux et j'ai pas encore installé le compilateur OCaml
D'ailleurs pourquoi est-ce qu'on apprend le Caml light en cours d'info vu que tout le monde trouve qu'il est complètement inutile et qu'il vaut mieux faire du OCaml?

j'ai une remarque sur les parenthèses, je ne pense pas qu'il faille y attacher une importance particulière... il faut juste que tu définisses bien la sémantique de ton langage

En fait j'utilise pas de méthode d'analyse syntaxique précise, je l'ai fait à ma façon et ça utilise du coup très fortement le fait que la grammaire en question soit très simple, et pour ma méthode il me semble que la gestion des parenthèses est assez importante.
N'ayant jusqu'à présent aucune connaissance en théorie des language, grammaires, etc. je me suis contenté de la grammaire naturelle des expressions mathématiques qui est complètement ambiguë, donc j'ai fait mon programme en conséquence, il ne serait pas adaptable directement pour une autre grammaire.

En ce qui concerne le TIPE au tétraconcours, a priori si je ne suis pas pris à l'ENS je préfère aller en fac plutôt qu'en école d'ingénieurs, donc je ne passerai peut-être même pas le TIPE du tétraconcours.
On verra l'an prochain (je suis en sup).

Fractal

[gorgonite]

D'ailleurs pourquoi est-ce qu'on apprend le Caml light en cours d'info vu que tout le monde trouve qu'il est complètement inutile et qu'il vaut mieux faire du OCaml?

parce qu'une personne ne comprenant pas forcemment grand chose à l'informatique a décidé de bloquer toute évolution dans ce domaine au niveau prépa par peur de voir émerger une filière MI

N'ayant jusqu'à présent aucune connaissance en théorie des language, grammaires, etc. je me suis contenté de la grammaire naturelle des expressions mathématiques qui est complètement ambiguë, donc j'ai fait mon programme en conséquence, il ne serait pas adaptable directement pour une autre grammaire.

donc tu pourras corriger cela après avoir lu mon lien

En ce qui concerne le TIPE au tétraconcours, a priori si je ne suis pas pris à l'ENS je préfère aller en fac plutôt qu'en école d'ingénieurs, donc je ne passerai peut-être même pas le TIPE du tétraconcours.
On verra l'an prochain (je suis en sup).

saches qu'il y a moyen de faire de la recherche même en école d'ingénieurs, et un master en cumul de ta 3A
au moins, ça te permet de voir la pratique et la théorie... alors que souvent dans les universités tu ne verras presque que de la théorie

[Jean-Marc.Bourguet]

j'ai beaucoup de mal à comprendre ce que tout le monde reproche à lex/yacc
ce sont d'excellents outils, et si l'on accepte de "salir" un peu son code, on arrive à parser des langages assez complexes

Tout le monde, j'en sais rien. Ma position est simple.

lex: ça fait bien son boulot. Il est peut-être possible de faire plus efficace à la main, mais je ne suis pas sûr que ça en vaille la peine ni que ce soit si évident que cela.

yacc et les générateurs de parseur... Je ne leur reproche rien. Je reproche simplement à certains de les considérer systématiquement comme l'unique solution envisageable (voir la surprise quand j'ai donné du code n'utilisant pas un générateur sur le défi) et de les pousser vers des zones où je ne pense pas qu'ils soient adaptés.
- Les générateurs automatiques sont à mon avis les premiers responsables de la qualité abyssimale des messages d'erreurs (voir le compilateur Ada de GNU pour ce qu'il est possible de faire quand on fait attention à cela).
- Dans les cas "simples" (qui ne le sont pas toujours pour les générateurs), ils sont plus compliqués à utiliser que d'écrire un parseur à la main. En théorie, ils ont l'avantage très fort de garantir que la grammaire est bien celle parsée, en pratique il faut modifier la grammaire pour arriver à la faire avaler par le générateur et pour arriver à avoir une gestion d'erreur correcte.
- Dans les cas compliqués, les modifications de grammaire, les astuces et hacks divers qu'il faut employer deviennent réhidibitoires et gènent fortement la maintenance et bloque l'évolutivité.
Je les trouve donc utile:
- dans une zone médiane, où il n'est pas trop simple d'écrire à la main mais où ils ne s'effondrent pas sous la complexité des moyens nécessaires pour contourner leurs limitations.
* d'autant plus que la grammaire est controllée et donc la version de référence peut être contraintes à respecter les limitations du générateur utilisé
* d'autant plus que la grammaire est volatile (ce pour autant qu'il n'y ait pas déjà trop de choses à faire pour l'adapter au générateur, car alors la volatilité de la grammaire est un inconvénient). Un cas particulier de ce genre, c'est quand les grammaires elles-mêmes sont générées automatiquement.

Note: j'ai une expérience industrielle avec des parseurs générés et écrits à la main mais elle commence à se faire vieille et je manque d'expérience pratique industrielle avec les générateurs récents. Je crains qu'ils aient progressés en généralité au détriment de la qualité la gestion d'erreur.

[Fractal LLG]

Euh, bon, en fait attendez peut-être que j'aie posté une nouvelle version de mon interpréteur, parce que je viens de m'apercevoir que çui-ci ne sait pas calculer (-1+2)*3 donc ya peut-être d'autres bugs cachés.
En plus l'analyseur lexical est en itératif alors que c'est beaucoup plus beau, plus court et plus compréhensible en récursif.

Merci à tous pour vos réponses en tous cas

Fractal

[InOCamlWeTrust]

Tu n'auras pas le temps de faire quelque chose de substantiel pour les ENS. C'est mon humble avis, si tu n'as pas encore commencé et si tu n'as aucune base, ce qui, je crois, est le cas.

Un bon sujet serait : "Une méthode générique pour introduire des messages d'erreur et d'avertissement dans un analyseur syntaxique". C'est le point faible de TOUS les analyseurs. C'est d'ailleurs ce qui, à mon sens, fait toute la valeur ajoutée d'un compilateur C propriétaire comme celui de Sun, comparé au GCC (que j'adore, mais qui est un poil limite à ce niveau). Avec un tel sujet, tu as d'ailleurs l'avantage de la nouveauté parce qu'aucun académicien ne veut se casser le cul à trouver une solution potable (fractale ou pas, homéomorphe ou non, réductible ou lambda-réductible ou non, topologiquement acceptable ou non).

[gorgonite]

Un bon sujet serait : "Une méthode générique pour introduire des messages d'erreur et d'avertissement dans un analyseur syntaxique". (...) Avec un tel sujet, tu as d'ailleurs l'avantage de la nouveauté parce qu'aucun académicien ne veut se casser le cul à trouver une solution potable (fractale ou pas, homéomorphe ou non, réductible ou lambda-réductible ou non, topologiquement acceptable ou non).

j'ai l'impression que tu as oublié que le TIPE n'est pas un stage de master de recherche... rappelles-toi de notre prépa, et des sujets assez pitoyables que certains proposaient, et qui leur a rapporté quand même une bonne note le jour du tetraconcours ^^

franchement, parmi ce qui préparaient les ENS dans notre lycée (situé à une station de métro de LLG ), personne n'a réellement fait quelque chose de nouveau, on faisait surtout une application de travaux existant, et une tentative d'explication du phénomène avec des connaissances théoriques ne dépassant pas le niveau prépa...
mais il est vrai qu'on est pas monté au-dessus de 15/20 pour le TIPE ENS

[Jean-Marc.Bourguet]

Un bon sujet serait : "Une méthode générique pour introduire des messages d'erreur et d'avertissement dans un analyseur syntaxique". C'est le point faible de TOUS les analyseurs.

Qu'est-ce que j'écrivais?

j'ai l'impression que tu as oublié que le TIPE n'est pas un stage de master de recherche...

J'ai du mal avec la structure académique française. Je trouve en tout cas que c'est un sujet de thèse de doctorat.

Il y a 22 pages sur le sujet dans Parsing techniques (qui en fait plus de 600). Et ce n'est pas traité plus en profondeur que dans le Crafting a compiler de Fisher et LeBlanc qui est presque 20 ans plus vieux. Mais j'ai pas été voir ce qu'il y a dans la bibliographie de l'ouvrage (la bibliographie fait 227 pages, à la page 113 de celle-ci commence la liste des 147 références sur le traitement d'erreur qu'elle contient).

[gorgonite]

J'ai du mal avec la structure académique française. Je trouve en tout cas que c'est un sujet de thèse de doctorat.

disons que le stage de master de recherche est le préambule d'une thèse... le sujet de doctorat sera certainement plus spécialisé