(* NOTE Ce fichier a été généré par la commande cat int_parser_02.ml expr_parser_01.ml expr_parser_02.ml expr_parser_03.ml > expr_parser.ml C'est la concaténation des exemples présentés en cours *) (* DEUX APPLICATIONS DU COURS SUR LES GRAMMAIRES AVEC ATTRIBUTS HÉRITÉS *) (* Quelques fonctions utiles sur les streams *) let (tail: 'a Stream.t -> 'a Stream.t) = fun stream -> begin Stream.junk stream ; stream end ;; let rec (list_of_stream: 'a Stream.t -> 'a list) = fun stream -> match Stream.peek stream with | None -> [] | Some a -> a :: (list_of_stream (tail stream)) ;; let rec (string_of_list: char list -> string) = fun cs -> match cs with | [] -> "" | c::cs -> (String.make 1 c) ^ (string_of_list cs) ;; (* APPLICATIONS 1 : GRAMMAIRE DES NOMBRES Nombre = Chiffre . Chiffre* d'où la grammaire Nombre -1-> Chiffre . Des_Chiffres Des_Chiffres -2-> epsilon | Chiffre . Des_Chiffres Chiffre -3-> '0' | '1' | ... | '9' *) (* VERSION 1 : reconnaissance uniquement *) print_string "\n\n (**** VERSION 1 = reconnaissance uniquement, avec des parsers : stream -> bool ****) \n\n" ;; (* Chiffre -3-> '0' | '1' | ... | '9' *) let (chiffre: char Stream.t -> bool) = parser | [< ' ('0'..'9') >] -> true ;; (* Des_Chiffres -2-> epsilon | Chiffre . Des_Chiffres *) let rec (des_chiffres: char Stream.t -> bool) = parser | [< b1 = chiffre ; b2 = des_chiffres >] -> b1 && b2 | [< >] -> true ;; (* Nombre -1-> Chiffre . Des_Chiffres *) let (nombre: char Stream.t -> bool) = parser | [< b1 = chiffre ; b2 = des_chiffres >] -> b1 && b2 (* /!\ Les parsers de ocaml sont paresseux. Si le résultat de l'un des parsers (l'entier retourné par chiffre) n'est pas utilisé, * le parser chiffre ne fait rien puisqu'il ferait le calcul pour rien. * Donc, le code suivant, * * | [< chiffre ; des_chiffres >] -> true * * qui n'utilise pas les résultats de chiffre et des_chiffres, est traduit en * * fun (stream : char Stream.t) -> true * * qui ne fait rien avec le stream et se contente de rendre true *) ;; let (parser_nombre: string -> bool) = fun ch -> begin print_string ("\n\"" ^ ch ^ "\"" ^ " : Nombre ?\n") ; let stream = Stream.of_string ch in let bool = try (nombre stream) with Stream.Failure -> false in begin print_string (string_of_list (list_of_stream stream)) ; bool end end ;; parser_nombre "" ;; parser_nombre "0" ;; parser_nombre "0001234.00" ;; (* VERSION 2 BOGUÉE : Même grammaire avec attributs synthétisés afin de retourner la valeur de l'entier lu sous forme de suite de caractères Chiffre { u } -3-> '0':char ..... ; { u = 0:int } | '1':char ..... ; { u = 1:int } ... | '9':char ..... ; { u = 9:int } Des_Chiffres { n' } -2-> epsilon ............................... ; { n' = ??? } | Chiffre { u } . Des_Chiffres { n } .... ; { n' = ??? } Nombre { n' } -1-> Chiffre { u } . Des_Chiffres { n } .......... ; { n' = ??? } *) print_string "\n\n (**** VERSION 2 (boguée) = retourne l'entier correspondant au stream lu, avec des parsers : stream -> int ****) \n\n" ;; let (chiffre_int: char Stream.t -> int) = parser | [< ' ('0') >] -> 0 | [< ' ('1') >] -> 1 | [< ' ('2') >] -> 2 | [< ' ('3') >] -> 3 | [< ' ('4') >] -> 4 | [< ' ('5') >] -> 5 | [< ' ('6') >] -> 6 | [< ' ('7') >] -> 7 | [< ' ('8') >] -> 8 | [< ' ('9') >] -> 9 ;; (* Des_Chiffres { n' } -2-> epsilon ............................. ; { n' = 0 } | Chiffre { u } . Des_Chiffres { n } .... ; { n' = 10 * u + n } *) let rec (des_chiffres_bug: char Stream.t -> int) = parser | [< u = chiffre_int ; n = des_chiffres_bug >] -> begin print_string (String.concat " " [ "\n 10 *" ; string_of_int u ; "+" ; string_of_int n ; ": "]) ; 10 * u + n end | [< >] -> 0 ;; (* Nombre { n' } -1-> Chiffre { u } . Des_Chiffres { n } .......... ; { n' = ??? } *) let (nombre_bug: char Stream.t -> int) = parser | [< u = chiffre_int ; n = des_chiffres_bug >] -> begin print_string (String.concat " " [ "\n10 *" ; string_of_int u ; "+" ; string_of_int n ; "\n"]) ; 10 * u + n end ;; let (parser_nombre_bug: string -> int option) = fun ch -> begin print_string ("\n\"" ^ ch ^ "\"" ^ " : Nombre ?\n") ; let stream = Stream.of_string ch in let n = try Some (nombre_bug stream) with Stream.Failure _ -> None in begin print_string (string_of_list (list_of_stream stream)) ; n end end ;; parser_nombre_bug "0" ;; parser_nombre_bug "1" ;; parser_nombre_bug "12" ;; parser_nombre_bug "123" ;; parser_nombre_bug "12340.00" ;; (* VERSION 3 (correcte): Même grammaire avec attributs hérités et synthétisés afin de retourner la valeur de l'entier lu sous forme de suite de caractères Chiffre { u } -3-> '0' ; { u = 0 } | '1' ; { u = 1 } ... | '9' ; { u = 9 } { i } Des_Chiffres { n' } -2-> epsilon .............................................. ; { n' = i } | Chiffre { u } . { 10 * i + u } Des_Chiffres { n } .... ; { n' = n } Nombre { n' } -1-> Chiffre { u } . { u } Des_Chiffres { n } .... ; { n' = n } *) print_string "\n\n (**** VERSION 3 (correcte) = retourne l'entier correspondant au stream lu, avec des parsers : int -> stream -> int ****) \n\n" ;; let rec (des_chiffres_int: int -> char Stream.t -> int) = fun i -> parser | [< u = chiffre_int ; n = (des_chiffres_int (10 * i + u)) >] -> n | [< >] -> i ;; (* Nombre { n' } -1-> Chiffre { u } . { u } Des_Chiffres { n } .... ; { n' = n } *) let (nombre_int: char Stream.t -> int) = parser | [< u = chiffre_int ; n = (des_chiffres_int u) >] -> n ;; let (parser_nombre_int: string -> int option) = fun ch -> begin print_string ("\n\"" ^ ch ^ "\"" ^ " : Nombre ?\n") ; let stream = Stream.of_string ch in let n = try Some (nombre_int stream) with Stream.Failure -> None in begin print_string (string_of_list (list_of_stream stream)) ; n end end ;; parser_nombre_int "0" ;; parser_nombre_int "1" ;; parser_nombre_int "12" ;; parser_nombre_int "123" ;; parser_nombre_int "123400" ;; parser_nombre_int "0001234.00" ;; (* APPLICATIONS 2 : GRAMMAIRES DES EXPRESSIONS ARITHMÉTIQUES Expr --> Nombre | Expr + Expr | ( Expr ) VERSION NON AMBIGUE Expr --> ' ' Expr | Nombre . Op_Expr | '(' . Expr . ')' . Op_Expr Op_Expr --> ' ' Op_expr | '+' . Expr | epsilon *) (* VERSION 1 : reconnaissance *) let rec (expr: char Stream.t -> bool) = parser | [< ' (' ') ; b = expr >] -> b | [< n = nombre_int ; b = op_expr >] -> b | [< ' ('(') ; b1 = expr ; ' (')') ; b2 = op_expr >] -> b1 && b2 and (op_expr: char Stream.t -> bool) = parser | [< ' (' ') ; b = op_expr >] -> b | [< ' ('+') ; b = expr >] -> b | [< >] -> true ;; let (parser_expr: string -> bool) = fun ch -> begin print_string ("\n\"" ^ ch ^ "\"" ^ " : Expr (version 1) ?\n") ; let stream = Stream.of_string ch in let bool = try expr stream with Stream.Failure _ -> false in begin print_string (string_of_list (list_of_stream stream)) ; bool end end ;; parser_expr "0 + 123" ;; parser_expr "(0 + (1 + 2) + (3 + 4) + (5))" ;; parser_expr "0 + 123 + 231" ;; parser_expr " + 213 + 231" ;; (* VERSION 2 : évaluation de l'expression pendant la reconnaissance Expr { n' } --> ' ' . Expr {n} ; { n' = .. } | Nombre {n1} . {..} Op_Expr {n} ; { n' = .. } | '(' . Expr {n1} . ')' . {..} Op_Expr {n} ; { n' = .. } { n1 } Op_Expr { n' } --> ' ' . {n1} Op_Expr {n} ; { n' = .. } | '+' . Expr {n2} ; { n' = ...... } | epsilon ; { n' = .. } *) let rec (expr: char Stream.t -> int) = parser | [< ' (' ') ; n = expr >] -> .. | [< n1 = nombre_int ; n = (op_expr n1) >] -> .. | [< ' ('(') ; n1 = expr ; ' (')') ; n = (op_expr n1) >] -> .. and (op_expr: int -> char Stream.t -> int) = fun n1 -> parser | [< ' (' ') ; n2 = (op_expr n1) >] -> .. | [< ' ('+') ; n2 = expr >] -> ....... | [< >] -> .. ;; let (parser_expr: string -> int option) = fun ch -> begin print_string ("\n\"" ^ ch ^ "\"" ^ " : Expr (version 3) ?\n") ; let stream = Stream.of_string ch in let n = try Some (expr stream) with Stream.Error _ -> None in begin print_string (string_of_list (list_of_stream stream)) ; n end end;; parser_expr "(0 + (1 + 2) + (3 + 4) + (5))" ;; parser_expr " + 213 + 231" ;; (* EXERCICE * ajoutez l'opérateur de multiplication à la grammaire *) (* VERSION 3 : construction d'une représentation ocaml de la structure de l'expression reconnue *) (* Représentation de al structure des expressions arithméthiques par un type caml *) type expr = | I of int | P of expr * expr (* GRAMMAIRE AVEC ATTRIBUTS HÉRITÉS ET SYNTHÉTISÉS Expr { e' } --> ' ' . Expr {e} .............................. ; { e' = .. } | Nombre {n} . {I(n)} Op_Expr {e} .............. ; { e' = .. } | '(' . Expr {e1} . ')' . {e1} Op_Expr {e } .... ; { e' = .. } { e1 } Op_Expr { e' } --> ' ' . {e1} Op_Expr {e} ............ ; { e'= .. } | '+' . Expr {e2} .................... ; { e' = ....... } | epsilon ............................ ; { e' = .... } *) let rec (expr: char Stream.t -> expr) = parser | [< ' (' ') ; e = expr >] -> .. | [< n = nombre_int ; e = op_expr (I n) >] -> .. | [< ' ('(') ; e1 = expr ; ' (')') ; e = op_expr e1 >] -> .. and (op_expr: expr -> char Stream.t -> expr) = fun e1 -> parser | [< ' (' ') ; e = op_expr e1 >] -> e | [< ' ('+') ; e2 = expr >] -> .. | [< ' ('*') ; e2 = expr >] -> .. | [< >] -> .. ;; let (parser_expr: string -> expr option) = fun ch -> begin print_string ("\n\"" ^ ch ^ "\"" ^ " : Expr (version 2) ?\n") ; let stream = Stream.of_string ch in let e = try Some (expr stream) with Stream.Error _ -> None in begin print_string (string_of_list (list_of_stream stream)) ; e end end ;; parser_expr "0 + 123 + 231" ;; parser_expr " + 123 + 231" ;; parser_expr "0 + 123 * 21" ;; parser_expr "(0 + (1 * 2) * (3 + 4) + (5))" ;; (* EXERCICE * ajoutez l'opérateur de multiplication à la grammaire, * représenté dans l'arbre par le constructeur * M of expr * expr *)