Programmation Fonctionnelle, TP8

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP8 : Combinateurs de parsing.

Guyslain Naves

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.

Le module a récupéré se trouve sur ces pages, selon la version du compilateur :

Son interface est donnée sur cette page.

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

  1. #directory "chemin/du/repertoire/contenant/le/fichier/cmo";;
  2. #load "parse.cmo";;
  3. open Parser.Infix (* pour utiliser les opérateurs infixes *)

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

conversion liste - chaîne de caractères

Écrire deux fonctions, permettant de transformer une liste de caractères en chaînes de caractères, et inversement.

  1. val string_of_list : char list -> string (* utiliser String.concat *)
  2. val list_of_string : string -> char list

Lecture de caractères, d'entiers

  1. Écrire un parseur lisant le premier caractère d'une liste de caractères en utilisant Parse.read_this.

    1. val read_char : (char,char) Parse.t

  2. É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.

    1. val read_and_check_char : (char -> bool) -> (char,char) Parse.t

  3. Écrire une fonction testant si un caractère est un chiffre :

    1. val is_figure : char -> bool

  4. Écrire une fonction retournant l'entier correspond à un chiffre (en utilisant int_of_char) :

    1. val value_of_figure : char -> int

  5. Utiliser Parse.read_strict_sequence, Parse.keep_highest_score et -!- 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.

    1. val read_int : (int,char) Parse.t

Expressions arithmétiques

On définit les expressions arithmétiques ainsi :

  1. type operator =
  2. | Plus
  3. | Times
  4. | Quotient
  5. | Minus

  7. type expression =
  8. | Operation of expression * operator * expression
  9. | Literal of int
  10. | Variable of string

Du coup, le langage à parser sera composé de 4 sortes de lexèmes :

  1. les opérateurs,
  2. les entiers,
  3. les variables, constitués de uniquement de lettres,
  4. les parenthèses ouvrantes et fermantes

Définir un type token pour les lèxemes.

Lecture d'une variable

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.

  1. val read_variable : (char,string) Parse.t

Lecture des opérateurs, des espaces

Écrire un parseur lisant autant de caractères d'espacement que possible (éventuellement aucun). Puis écrire une fonction lisant un des quatre opérateurs.

  1. val read_spaces : (char,char list) Parse.t
  2. val read_operator : (char, operator) Parse.t =

Lexeur

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.

  1. val read_token : (char,token) Parse.t
  2. val scan_token : (char, token list) Parse.t
  3. val lexer : char list -> token list

Parseur d'expressions arithmétiques

Coder maintenant le parseur.

Pour cela, notons qu'il n'est pas possible d'utiliser une grammaire récursive à gauche, puisque cela ferait boucler le processus de parsage. On utilise donc la grammaire suivante :

  1. expr_simple :=
  2. | '(' expr ')'
  3. | Variable
  4. | Literal

  6. expr_factor :=
  7. | expr_simple '*' expr_factor
  8. | expr_simple '/' expr_factor
  9. | expr_simple

  11. expr :=
  12. | expr_factor '+' expr
  13. | expr_factor '-' expr
  14. | expr_factor

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

  1. let rec read_simple : (token,expression) Parse.t =
  2. ...
  3. and read_factor : (token,expression) Parse.t =
  4. ...
  5. and read_expression : (token,expression) Parse.t =
  6. ...

Le module Parse

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