(** Correction du D.S. du lundi 2 avril *) (** exercice 2 *) (* ESC-v : remonte d'une page (hauteur courante) dans le buffer courant CTRL-x CTRL-s : sauvegarde le buffer courant CTRL-x o : (attention : CTRL-x CTRL-o ne fait rien) passe d'une fenêtre d'édition à une autre notes : - CTRL-o insère un retour chariot *) (** exercice 3 *) (* Remonter en haut du fichier : ESC-< ou CTRL-début Sauver : CTRL-x CTRL-s Interpréter la fonction courante : CTRL-x CTRL-e ou CTRL-c CTRL-e Indenter le dubber entier : ESC-q ou CTRL-c CTRL-q notes : - ESC-q indente l'ensemble d'une fonction (et une seule, pas le buffer entier) - TAB indente une ligne *) (** exercice 4 *) (* CTRL-x ( CTRL-x o ESC-> CTRL-x o CTRL-x ) *) (** exercice 5 *) (* notes : - on a supposé que les indices allaient de 0 à n-1 où n est la taille de la liste - failwith consiste en une levée de l'exception prédéfinie Failure of string. - Une optimisation est possible (f5_) : si n est strictement négatif on peut éviter de parcourir toute la liste inutilement. Par contre tester si l'on dépasse la taille de la liste (par exemple avec List.length) n'est pas une bonne idée car ce test demande un parcours entier de la liste. *) exception Notfound of string let rec f5 n l = match l with | e::l -> if n = 0 then e else f5 (n - 1) l | [] -> raise (Notfound "there is not so many elements in the list") let f5_ n l = if n >= 0 then f5 n l else raise (Notfound "positive index expected") (** exercice 6 *) (* notes : - passer par une fonction auxiliaire max (qui est même prédéfinie) - la fonction prédéfinie max n'utilise pas des couples ! - attention aux if (a < b ... ) then ... else if (b < a ...) then ... else c. Le cas a = b > c donne c en max, ce qui est faux. - lire l'énoncé : sans la flèche, c'est sans la flèche *) let g a b c = let max x y = if x > y then x else y in max a (max b c) let f = g 34 (** exercice 7 *) (* notes: - attention au typage des opérateurs :: et @ - losque vous utilisez List.map vous ne faites pas une déclaration récursive (pas de mot clé rec) *) let rec f7 f l = match l with | e::l' -> (e, f e)::(f7 f l') | [] -> [] let f7_ f l = List.map (fun e -> (e, f e)) l (** exercice 8 *) (* notes - l'énoncé considère qu'il n'y a pas d'arbre binaire vide - () est la valeur "unit". unit est le type "unit" contenant un unique valeur : () - pour l'utilsiation d'un module M de signature S, on peut soit utiliser open M soit utiliser la qualification des méthodes par M. *) module type S = sig type t type ab = Node of ab * ab | Leaf val to_seq : string -> t val print : t -> unit val parse : t -> ab end let _ = M.parse (M.to_seq "tototitii") (** exercice 9 *) (* - l'énoncé suppose que les entrées respectent la grammaire G : on peut donc se borner à compter le nombre de lexèmes TEnt - l'énoncé ne spécifie pas sous qu'elle forme est donnée une entrée. On suppose qu'il s'agit d'un flot de tokens - On peut rendre l'analyse récursive terminale à l'aide d'un accumulateur - Trois versions équivalentes sont proposées. *) #load "camlp4o.cma" exception SyntaxError type token = TEnt of int | Tp | TVirgule | TParenG | TParenD let parseur f = let rec parseur_aux f = match f with parser | [< 'TEnt(_) >] -> 1 + parseur_aux f | [< '_ >] -> parseur_aux f | [<>] -> 0 in parseur_aux f let parseur = let rec parseur_aux = parser | [< 'TEnt(_) ; n' = parseur_aux >] -> 1 + n' | [< '_ ; n' = parseur_aux >] -> n' | [<>] -> 0 in parseur_aux let parseur = let rec parseur_aux = parser | [< 'TEnt(_) ; s >] -> 1 + parseur_aux s | [< '_ ; s >] -> parseur_aux s | [<>] -> 0 in parseur_aux let _ = parseur [< 'Tp ; 'TParenG ; 'TParenD >] let _ = parseur [< 'Tp ; 'TParenG ; 'TEnt(1) ; 'TParenD >] let _ = parseur [< 'Tp ; 'TParenG ; 'TEnt(1) ; 'TVirgule ; 'TEnt(2) ; 'TVirgule ; 'TEnt(3) ; 'TParenD >] let _ = parseur [< 'Tp ; 'TParenG ; 'TEnt(1) ; 'TVirgule ; 'TEnt(2) ; 'TParenD >]