Callcc/Guyslain/Teaching/ProgFonc/TP2014/TP8-2014

Version & licenses
Creative Commons License
  1. {`author "Guyslain Naves"}
  2. {`date "Mars 2014"}
  3. {`windowtitle "Programmation Fonctionnelle, TP8"}
  4. {`frametitle "Programmation Fonctionnelle, TP8 : Combinateurs de parsing."}
  5. {`menu "progfonc"}


  6. Ce TP porte sur l'utilisation de fonctionnelles pour la reconnaissance de grammaires. Dans un premier temps, on utilisera un module compilé fourni qui donne les fonctionnelles pour construire une grammaire reconnaissant les expressions arithmétiques. Dans un second temps on recodera nous-même ce module.

  7. Le module a récupéré se trouve sur ces pages, selon la version du compilateur :
  8. - Ocaml 3.11.2 : {link af://guyslain/teaching/ParCo/3.11.2/parse.cmo parse.cmo} et
  9. {link af://guyslain/teaching/ParCo/3.11.2/parse.cmi parse.cmi}
  10. - Ocaml 3.12.1 : {link af://guyslain/teaching/ParCo/3.12.1/parse.cmo parse.cmo} et
  11. {link af://guyslain/teaching/ParCo/3.12.1/parse.cmi parse.cmi}
  12. - Ocaml 4.00.0 : {link af://guyslain/teaching/ParCo/4.00.0/parse.cmo parse.cmo} et
  13. {link af://guyslain/teaching/ParCo/4.00.0/parse.cmi parse.cmi}
  14. - Ocaml 4.00.1 : {link af://guyslain/teaching/ParCo/4.00.1/parse.cmo parse.cmo} et
  15. {link af://guyslain/teaching/ParCo/4.00.1/parse.cmi parse.cmi}

  16. Son interface est donnée {link af://callcc/Guyslain/Teaching/ProgFonc/Code/parse_mli sur cette page.}

  17. Pour utiliser ce module dans le toplevel, évaluer les lignes suivantes :

  18. {code {`language "ocaml"} {:
  19. #directory "chemin/du/repertoire/contenant/le/fichier/cmo";;
  20. #load "parse.cmo";;
  21. open Parser.Infix (* pour utiliser les opérateurs infixes *)
  22. :}}

  23. Vous pouvez voir l'interface du module en le renommant : le toplevel listera alors son contenu.

  24. {section 3 conversion liste - chaîne de caractères}

  25. Écrire deux fonctions, permettant de transformer une liste de caractères en chaînes de caractères, et inversement.
  26. {code {`language "ocaml"} {:
  27. val string_of_list : char list -> string (* utiliser String.concat *)
  28. val list_of_string : string -> char list
  29. :}}


  30. {section 3 Lecture de caractères, d'entiers}

  31. + {subframe
  32. Écrire un parseur lisant le premier caractère d'une liste de caractères en utilisant {verb {:Parse.read_this:}}.
  33. {code {`language "ocaml"} {:val read_char : (char,char) Parse.t:}}
  34. }
  35. + {subframe
  36. Écrire un parseur lisant le premier caractère d'une liste de caractères, si celui-ci vérifie un prédicat passé en argument.
  37. {code {`language "ocaml"} {:val read_and_check_char : (char -> bool) -> (char,char) Parse.t:}}
  38. }
  39. + {subframe
  40. Écrire une fonction testant si un caractère est un chiffre :
  41. {code {`language "ocaml"} {:val is_figure : char -> bool:}}
  42. }
  43. + {subframe
  44. Écrire une fonction retournant l'entier correspond à un chiffre (en utilisant {verb {:int_of_char:}}) :
  45. {code {`language "ocaml"} {:val value_of_figure : char -> int:}}
  46. }
  47. + {subframe
  48. Utiliser {verb {:Parse.read_strict_sequence:}}, {verb {:Parse.keep_highest_score:}} et {verb{:-!-:}} pour écrire un parseur qui lit une liste de caractères, ne retourne rien si le premier caractère n'est pas un chiffre, sinon lit autant de chiffres que possible et retourne l'entier correspondant.
  49. {code {`language "ocaml"} {:val read_int : (int,char) Parse.t:}}
  50. }

  51. {section 3 Expressions arithmétiques}

  52. On définit les expressions arithmétiques ainsi :
  53. {code {`language "ocaml"} {:
  54. type operator =
  55. | Plus
  56. | Times
  57. | Quotient
  58. | Minus

  59. type expression =
  60. | Operation of expression * operator * expression
  61. | Literal of int
  62. | Variable of string
  63. :}}

  64. Du coup, le langage à parser sera composé de 4 sortes de lexèmes :
  65. + les opérateurs,
  66. + les entiers,
  67. + les variables, constitués de uniquement de lettres,
  68. + les parenthèses ouvrantes et fermantes

  69. Définir un type {verb {:token:}} pour les lèxemes.

  70. {section 3 Lecture d'une variable}

  71. En vous inspirant de la lecture des entiers, coder un parseur pouvant lire une variable. Essayer de factoriser au mieux le code des deux fonctions.
  72. {code {`language "ocaml"} {:
  73. val read_variable : (char,string) Parse.t
  74. :}}

  75. {section 3 Lecture des opérateurs, des espaces}

  76. Écrire un parseur lisant autant de caractères d'espacement que possible (éventuellement aucun). Puis écrire une fonction lisant un des quatre opérateurs.
  77. {code {`language "ocaml"} {:
  78. val read_spaces : (char,char list) Parse.t
  79. val read_operator : (char, operator) Parse.t =
  80. :}}


  81. {section 3 Lexeur}

  82. On peut maintenant écrire le lexeur, qui transforme une liste de caractères en liste de lexèmes. Pour cela, on répète la lecture de caractères d'espacement suivi de la lecture d'une des sortes de lexème.
  83. {code {`language "ocaml"} {:
  84. val read_token : (char,token) Parse.t
  85. val scan_token : (char, token list) Parse.t
  86. val lexer : char list -> token list
  87. :}}


  88. {section 3 Parseur d'expressions arithmétiques}

  89. Coder maintenant le parseur.

  90. Pour cela, notons qu'il n'est pas possible d'utiliser une grammaire
  91. récursive à gauche, puisque cela ferait boucler le processus de
  92. parsage. On utilise donc la grammaire suivante :
  93. {code {:
  94. expr_simple :=
  95. | '(' expr ')'
  96. | Variable
  97. | Literal

  98. expr_factor :=
  99. | expr_simple '*' expr_factor
  100. | expr_simple '/' expr_factor
  101. | expr_simple

  102. expr :=
  103. | expr_factor '+' expr
  104. | expr_factor '-' expr
  105. | expr_factor
  106. :}}

  107. Nous aurons donc besoin de trois fonctions, une par non-terminal de la
  108. grammaire, définies de façon mutuellement récursive.

  109. {code {`language "ocaml"} {:
  110. let rec read_simple : (token,expression) Parse.t =
  111. ...
  112. and read_factor : (token,expression) Parse.t =
  113. ...
  114. and read_expression : (token,expression) Parse.t =
  115. ...
  116. :}}


  117. {section 3 Le module {verb {:Parse:}}}

  118. La suite du TP consiste à coder vous-même le module {verb
  119. {:Parse:}}. Cette partie ne sera pas noté dans le cadre de ce TP, mais
  120. dans le cadre du projet.