Compilation
Master M1 Informatique 2004-2005


TD-TP d'initiation à l'outil Lex




Le but de ce TD est de vous familiariser avec l'outil ocamllex, la version Ocaml de l'outil Unix standard lex. Cet outil construit automatiquement un automate déterministe à actions, prenant en entrée un flot de caractères, à partir d'un ensemble de règles de la forme expression régulière Þ action. L'outil lex est naturellement utilisé pour écrire les analyseurs lexicaux précédant les analyseurs syntaxiques, mais peut être également utilisé pour écrire tout type de filtre qui analyse son entrée sur la base d'expressions régulières. Dans ce TD, nous allons mettre en pratique cette utilisation de lex.

1  Utilisation d'ocamllex

Les fichiers ocamllex portent le suffixe .mll et suivent la syntaxe suivante : 
    { 
      code Ocaml
    } 
    let ident = regexp
    let ident = regexp
    :
    rule ident = parse
      regexp { code Ocaml }
    | regexp { code Ocaml }
    :
    and ident = parse
      regexp { code Ocaml }
    | regexp { code Ocaml }
    :
    {
      code Ocaml
    }
Les déclarations let permettent de donner des noms à des expressions régulières, qui pourront être réutilisés dans les membres gauches des règles. Les expressions régulières suivent la syntaxe donnée figure 1.
regexp ::= ident
  | 'caractère'
  | "chaîne"
  | regexp regexp
  | regexp | regexp
  | regexp ?
  | regexp +
  | regexp *
  | ( regexp )
  | [ caractères ]
  | [^ caractères ]
  | eof
  | _
  | regexp as ident
caractères ::= ('caractère' | 'caractère'-'caractère')+

Figure 1: Syntaxe des expressions régulières

La compilation d'un fichier foo.mll est réalisée par la commande ocamllex foo.mll, qui produit le fichier foo.ml. Ce fichier définit pour chaque entrée f du fichier lex une fonction f : Lexing.lexbuf ® t où t est le type commun à toutes les actions de l'entrée f. Le type Lexing.lexbuf est le type des buffers lexicaux. Le module Lexing fournit divers moyens de construire de tels buffers à partir de chaînes de caractères, de fichiers, etc. Nous vous renvoyons au manuel en ce qui concerne le module Lexing.

Dans une action, il est possible de récupérer la chaîne reconnue avec Lexing.lexeme lexbuf. De manière plus précise, il est possible de récupérer la portion de cette chaîne correspondant à une sous-expression de l'expression régulière en nommant celle-ci à l'aide de la construction as (voir figure 1). Le nom correspondant est alors une variable Ocaml que l'on peut utiliser dans l'action (de type char, string, ou char option ou string option selon les cas).

2  Application : cpp

Nous nous proposons ici d'utiliser ocamllex pour écrire un petit préprocesseur (inspiré du préprocesseur C cpp mais bien plus simple). Un tel préprocesseur permet de définir des macros et de faire de la compilation conditionnelle. Notre programme acceptera un fichier sur sa ligne de commande et produira alors la version préprocessée de ce fichier sur la sortie standard. On pourra utiliser le canevas ocamllex suivant (où ... désigne les endroits à compléter) : 
{ 
  open Lexing
  open Printf
  ...
}
...
rule scan = parse
...
{
  let usage () = eprintf "usage: cpp file\n"; exit 1

  let main () =
    if Array.length Sys.argv <> 2 then usage ();
    let c = open_in Sys.argv.(1) in
    let lb = from_channel c in
    scan lb;
    close_in c

  let _ = Printexc.catch main ()
}
Pour le confort de ce TP, on pourra aussi utiliser le Makefile minimal suivant : 
cpp: cpp.ml
        ocamlopt -o cpp cpp.ml

cpp.ml: cpp.mll
        ocamllex cpp.mll
Après compilation, on pourra tester sur un source quelconque test.c avec la commande ./cpp test.c.

2.1  Macros

La première tâche du préprocesseur est de permettre la définition de macros et leur expansion. Une macro est définie par une ligne de la forme 
#define nom valeur
Une telle commande définie la macro nom dont la valeur valeur est le texte qui s'étend entre le nom de la macro et la fin de la ligne, les espaces avant et après ce texte étant ignorés. La valeur peut être absente et auquel cas la macro est considérée comme définie avec pour valeur la chaîne vide.

Dès qu'une macro est définie, toute occurrence d'un identificateur de ce nom apparaissant par la suite est remplacée par la valeur de cette macro. Ainsi l'application de préprocesseur au texte 
#define PI 3.141592
const float c = PI;
#define R 6378
float DT = 2 * PI * R;
donne le texte suivant 
const float c = 3.141592;
float DT = 2 * 3.141592 * 6378;
Programmez la définition et l'expansion des macros. On pourra supposer que les définitions de macros commencent toujours au début de la ligne.

2.2  Compilation conditionnelle

La seconde tâche du préprocesseur est de permettre la compilation conditionnelle : selon qu'une macro est ou non définie, une partie du source sera ou non prise en compte. La définition de macro est testée avec une ligne de la forme #ifdef nom. Le texte concerné par ce test s'étend jusqu'à une ligne de la forme #endif. Si la macro nom est définie le texte englobé est considéré (et le préprocesseur s'applique à ce texte) ; sinon, ce texte est ignoré. À l'instar d'une conditionnelle dans un langage de programmation, une commande #else permet de considérer le cas où la macro n'est pas définie. Note : les définitions de macros se trouvant dans une portion de texte ignorée sont ignorées.

Ainsi on peut écrire 
#define A
#ifdef A
dans le cas où A est définie
#else
dans le cas contraire
#endif
et l'application du préprocesseur donne le résultat suivant : 
dans le cas où  est définie
(Notez l'expansion de A).

Programmez les commandes du préprocesseur #ifdef, #else et #endif. On pourra supposer que ces commandes sont toujours bien formées (un #endif ferme toujours un #ifdef, pas de #else en dehors d'un #ifdef, etc.)

Attention : les #ifdef peuvent être imbriqués.

2.3  Commentaires et chaînes de caractères

Pour des raisons évidentes, le préprocesseur C ne s'applique pas à l'intérieur des commentaires et des chaînes de caractères. Ajoutez ce comportement à votre préprocesseur.

Les conventions lexicales du C sont les suivantes : On pourra supposer les commentaires et les chaînes toujours bien formés.
This document was translated from LATEX by HEVEA.