Compilation et langages - TP 2 - Analyse lexicale, analyse syntaxique

On va maintenant s'occuper de la partie avant du compilateur : vous allez utiliser les outils ocamllex et menhir pour créer des modules d'analyse lexicale et d'analyse syntaxique que vous pourrez facilement étendre dans les séquences suivantes.

Exercice préparatoire :
analyse ascendante et conflits

Considérons le mini-langage donné par la grammaire suivante :

      [p] ← ε
           | [i] ; [p]
      [i] ← {id} := [e]
      [e] ← {n}
           | {id} [e]
           | [e] + [e]
           | [e] * [e]

où les non terminaux [p], [i] et [e] désignent respectivement un programme, une instruction et une expression, où les terminaux {id} et {n} sont respectivement un identifiant formé d'une suite de caractères alphabétiques et un nombre entier, et où les symboles ;, :=, + et * sont des terminaux.

Effectuez l'analyse ascendante du programme suivant :

      x := f 1 + 8 * 7 + 1;

Énumérez les conflits rencontrés lors de cette analyse, et définissez des priorités pour les différentes règles et les différents terminaux pour obtenir un comportement comparable à celui de Caml.

Afficher la solution .

                          oooo$$$$$$$$$$$$oooo
                      oo$$$$$$$$$$$$$$$$$$$$$$$$o
                   oo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o         o$   $$ o$
   o $ oo        o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o       $$ $$ $$o$
oo $ $ "$      o$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$o       $$$o$$o$
"$$$$$$o$     o$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$o    $$$$$$$$
  $$$$$$$    $$$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$$$$$$$$$$$$$$
  $$$$$$$$$$$$$$$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$$$$$$  """$$$
   "$$$""""$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     "$$$
    $$$   o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     "$$$o
   o$$"   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$       $$$o
   $$$    $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$" "$$$$$$ooooo$$$$o
  o$$$oooo$$$$$  $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$   o$$$$$$$$$$$$$$$$$
  $$$$$$$$"$$$$   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     $$$$""""""""
 """"       $$$$    "$$$$$$$$$$$$$$$$$$$$$$$$$$$$"      o$$$
            "$$$o     """$$$$$$$$$$$$$$$$$$"$$"         $$$
              $$$o          "$$""$$$$$$""""           o$$$
               $$$$o                                o$$$"
                "$$$$o      o$$$$$$o"$$$$o        o$$$$
                  "$$$$$oo     ""$$$$o$$$$$o   o$$$$""
                     ""$$$$$oooo  "$$$o$$$$$$$$$"""
                        ""$$$$$$$oo $$$$$$$$$$
                                """"$$$$$$$$$$$
                                    $$$$$$$$$$$$
                                     $$$$$$$$$$"
                                      "$$$""""

Avouez, vous n'y croyiez pas.
Pour se consoler : un petit dessin.
Masquer.

Et pourtant !

Pour commencer, le programme est traduit en la suite de lexèmes suivante :

      {id} := {id} {n} + {n} * {n} + {n} ;

L'analyse ascendante avec les priorités de Caml se déroule comme suit :

    <|>  {id} := {id} {n} + {n} * {n} + {n} ;   |   shift
{id}     <|>  := {id} {n} + {n} * {n} + {n} ;   |   shift
{id} :=     <|>  {id} {n} + {n} * {n} + {n} ;   |   shift
{id} := {id}     <|>  {n} + {n} * {n} + {n} ;   |   shift
{id} := {id} {n}     <|>  + {n} * {n} + {n} ;   |   shift
{id} := {id} [e]     <|>  + {n} * {n} + {n} ;   |   reduce [e] ← {n}
{id} := [e]          <|>  + {n} * {n} + {n} ;   | (1)  reduce [e] ← {id} [e]
{id} := [e] +          <|>  {n} * {n} + {n} ;   |   shift
{id} := [e] + {n}          <|>  * {n} + {n} ;   |   shift
{id} := [e] + [e]          <|>  * {n} + {n} ;   |   reduce [e] ← {n}
{id} := [e] + [e] *          <|>  {n} + {n} ;   | (2)  shift
{id} := [e] + [e] * {n}          <|>  + {n} ;   |   shift
{id} := [e] + [e] * [e]          <|>  + {n} ;   |   reduce [e] ← {n}
{id} := [e] + [e]                <|>  + {n} ;   | (3)  reduce [e] ← [e] * [e]
{id} := [e]                      <|>  + {n} ;   | (4)  reduce [e] ← [e] + [e]
{id} := [e] +                      <|>  {n} ;   |   shift
{id} := [e] + {n}                      <|>  ;   |   shift
{id} := [e] + [e]                      <|>  ;   |   reduce [e] ← {n}
{id} := [e]                            <|>  ;   |   reduce [e] ← [e] + [e]
[i]                                    <|>  ;   |   reduce [i] ← {id} := [e]
[i] ;                                    <|>    |   shift
[i] ; [p]                                <|>    |   reduce [p] ← ε
[p]                                      <|>    |   reduce [p] ← [i] ; [p]

Cette version correspond au parenthésage

      x := ((f 1) + (8*7)) + 1;

Conflits rencontrés :

(1) Conflit entre shift + et reduce [e] ← {id} [e].
Le choix fait est de privilégier la règle d'application, avec donc l'application plus prioritaire que le symbole +. Dans le cas contraire, le parenthésage aurait pu être
```
  x := f ((1 + (8*7)) + 1)
```
(mais cela dépend aussi de la comparaison de priorités entre application et *).
(2) Conflit entre shift * et reduce [e] ← [e] + [e].
Le choix fait est de privilégier le symbole *, qu'on déclare donc plus prioritaire que le symbole +. Donc le cas contraire, le parenthésage aurait été
```
  x := ((f 1)+8) * (7+1)
```
(3) Conflit entre shift + et reduce [e] ← [e] * [e].
Ce conflit est réglé par le choix précédent de privilégier le symbole * par rapport au symbole +.
(4) Conflit entre shift + et reduce [e] ← [e] + [e].
Ici, les deux actions possibles concernent le même symbole +. Le choix fait est de privilégier la réduction par rapport au décalage, on déclare donc le symbole + associatif à gauche. Dans le cas contraire, le parenthésage aurait été
```
  x := (f 1) + ((8*7) + 1)
```

Finalement, on peut utiliser les déclarations de priorité et d'associativité suivantes :

      %left PLUS
      %left MULT
      %right APP

où PLUS et MULT désignent les symboles + et *, et où APP est un symbole factice utilisé pour indiquer la priorité de la règle [e] ← {id} [e] %prec APP.

Masquer.

Syntaxe du langage `A6000`

Lexèmes

Les lexèmes du langage A6000 sont les suivants :

{n}, {b} : constantes entières et booléennes
{id} : identifiants (chaînes de caractères alphabétiques minuscules)
(, ), ;, :=, +, -, *, ==, !=, <, ≤, &&, ||
main, integer, boolean, var, while, if, then, else
EOF : fin de fichier

Grammaire

Les symboles terminaux de la grammaire sont les lexèmes.
Les symboles non terminaux sont :

[main] : le programme
[var_decls] : une séquence de déclarations de variables
[instructions] : une séquence d'instructions
[instruction] : une instruction
[expression] : une expression
[location] : une variable
[binop] : un opérateur binaire
[type] : un type

Les règles de la grammaire sont :

              [main]  ←  main ( integer id ) ( [var_decls] [instructions] ) EOF

      [instructions]  ←  { [instruction] ; }*
       [instruction]  ←  [location] := [expression]
                      |  while [expression] ( [instructions] )
                      |  if [expression] then ( [instructions] )
	                                 else ( [instructions] )
                      |  print ( [expression] )

         [var_decls]  ←  { var [typ] {id} ; }*
              [type]  ←  integer | boolean
        [expression]  ←  {n}
	              |  {b}
                      |  [expression] [binop] [expression]
          [location]  ←  {id}
             [binop]  ←  + | - | * | == | != | < | <= | && | ||

où { e }* signifie "e répété 0 fois ou plus".

Travail à effectuer

Les fichiers SourceLexer.mll et SourceParser.mly implémentent déjà une partie de cette syntaxe. Vous devez les compléter pour reconnaître l'ensemble de la syntaxe concrète d'A6000 et la traduire en syntaxe abstraite SourceAst (qui contient un arbre de syntaxe et une table des symboles).

Pour mémoire, la répartition des différents éléments est la suivante :

Déclaration des lexèmes : SourceParser.mly
Reconnaissance des lexèmes : SourceLexer.mll
Reconnaissance de la grammaire : SourceParser.mly
Génération de l'AST : SourceParser.mly

Extensions

Voici la première série d'extensions que vous pouvez intégrer à votre compilateur.
Remarque : celle concernant les messages d'erreur est susceptible de vous être utile un jour ou l'autre.

1. Sucre syntaxique : une boucle `for`

Ajoutez une boucle for à la syntaxe concrète d'A6000, sous forme de sucre syntaxique.

Vous ne devez pas modifier SourceAst ni aucune des étapes subséquentes du compilateur. Votre analyseur syntaxique doit traduire la boucle en utilisant d'autres éléments déjà présents dans la syntaxe abstraite.

2. Aider son prochain : messages d'erreur (RECOMMANDÉ)

2.1. Erreurs de syntaxe

Faites en sorte qu'en cas d'erreur de syntaxe, une indication soit donnée à l'utilisateur quant à la nature et/ou la position de cette erreur.

L'information minimale utile est la ligne à laquelle l'erreur a été rencontrée. Vous devez donc d'une manière ou l'autre tenir le compte des lignes du programme (le mécanisme de localisation interne au module Lexing de Caml ne le fait pas directement).

2.2. Erreurs de typage

Étendez votre système de signalisation des erreurs pour qu'il indique également la position des erreurs de typage.

Vous aurez besoin d'adapter légèrement la syntaxe abstraite SourceAst afin qu'elle intègre des informations sur les positions des différents éléments. Comme ces informations supplémentaires ne seront plus utiles à partir de l'étape UntypedAst, vous pourrez profiter de la transformation SourcetoUntyped pour les oublier.

3. Pré-processeur : des macros utilisateur

Un pré-processeur est un programme qui agit avant le programme principal du compilateur. Il prend en entrée un fichier source [file].a6m et produit un nouveau fichier source [file].pp.a6m sur lequel travaillera le compilateur.

Cette phase peut être utilisée pour expanser les macros utilisateur.

3.1. Macros constantes

On veut donner la possibilité à l'utilisateur de définir des macros à l'aide directives comme

      #DEFINE <macro_name> <text>

puis d'utiliser plus tard #<macro_name> à la place de <text>.

Utilisez ocamllex pour créer un module Preprocessor qui ouvre le fichier source, lit les définitions de macros, et crée un nouveau fichier source dans lequel chaque utilisation de macro #<macro_name> est remplacée par le texte correspondant.

Modifiez le module Main pour ajouter cette phase en amont du compilateur, éventuellement liée à une nouvelle option -pp.

3.2. Macros avec arguments

Enrichissez votre pré-processeur pour permettre aux macros de recevoir des arguments.

Une définition aura par exemple la forme :

      #DEFINE <macro_name>{n} <text>

où n est le nombre d'arguments de la macro, et où le texte <text> peut faire référence au i-ème argument avec la notation #i. Une macro à n arguments s'utilise alors comme :

      #<macro_name>{<arg_1>}...{<arg_n>}

Conseil : dans un premier temps, limitez-vous aux macros à un argument.

Compilation et langages TP 2 - Analyse lexicale, analyse syntaxique

Exercice préparatoire : analyse ascendante et conflits

Syntaxe du langage A6000