Génération et auto-génération d’analyseurs syntaxiques

Proposé par Benjamin Werner
 
***

Une page de suivie sera fournie, qui sera complétée au fur et à mesure des questions.

 

Il s’agit de programmer une version simplifiée du programme yacc (yet another compiler’s compiler). Il s’agit d’un utilitaire d’analyse syntaxique. Une originalité du sujet est que ce programme génère lui-même des programmes.

1  Principes

Comme cela sera traité lors de l’amphi 14 du cours, un analyseur syntaxique, ou parseur est un programme qui:

La forme de la structure attendue est donnée par une grammaire.

2  Génération de parseurs

Un générateur de parseurs est un programme qui va fabriquer un autre programme. Pour cela, il va prendre en entrée une grammaire annotée, c’est-à-dire, en première approximation:

A partir de cette grammaire annotée, le générateur fabriquera le parseur. C’est-à-dire qu’il fabriquera un fichier contenant le code source du programme qui implémente la grammaire annotée.

3  Exemple explicatif: la calculette simple

Voici une grammaire annotée pour une calculette 4 opérations simple. J’ai repris volontairement l’exemple de l’amphi 5:

expr ::= 
   prod '+ expr  -> { $1 + $3 }
 | prod '- expr  -> { $1 - $3 }
 | prod          -> { $1 }
;;

prod ::= 
   fun '* prod   -> { $1 * $3 }
 | fun '/ prod   -> { $1 / $3 }
 | fun           -> { $1 }
;;

fun ::=
   int          -> { $1 }
 | '( expr ')   -> { $2 }
;;

On appelle expr, prod et fun les ées de la grammaire. Elles sont composées respectivement de 3, 3 et 2 règles séparées par le signe "|".

Dans chaque règle, on trouve à gauche du "->" la description de la syntaxe correspondante. À droite on trouve entre accolades un petit bout de programme java qui décrit ce qu’il faut faire avec l’expression parsée. Ces bouts de programme sont les actions de la grammaire. Dans ces actions, $1 désigne la première composante de la règle de grammaire, $2 la deuxième, etc…

Je fournirai un début d’analyseur syntaxique pour la calculette. C’est-à-dire que ce programme, une fois achevé, prendra en entrée une chaine de caractères (comme (” 1+2*2 ") et rendra le résultat (dans ce cas, 5). Ce début de programme donnera une bonne idée du fonctionnement de l’analyseur.

Le premier travail sera de terminer ce programme.

4  Générateur de parseurs

Le deuxième travail demandé est donc d’écrire un générateur de parseurs. C’est-à-dire un programme qui à partir d’une grammaire annotée engendrera un programme java exécutable correspondant à cette grammaire (par exemple fournira le programme de la question 1 à partir de la grammaire ci-dessus.

Précisions techniques

  1. Dans la syntaxe des grammaires annotées, on propose d’encadrer les bouts de programmes java entre accolades. Cela interdit, a priori d’utiliser des accolades dans ces programmes. Pour contourner cet obstacle, on peut décider, dans ces programmes, de remplacer } par }}, }} par }}}, etc.
  2. En pratique une grammaire annotée sera complétée par deux autres morceaux de programmes java, un prélude et un épilogue qui dans le programme final seront ajoutés respectivement au début et à la fin. Par exemple, dans le cas de la calculette, on ajoutera vraisemblablement une conclusion qui demandera à l’utilisateur de taper une expression, appellera le parseur et affichera le résultat.
  3. Je rappellerai au besoin, sur l’url de suivi, les primitives pour lire et écrire des fichiers, ou pour manipuler les chaînes de caractères.
  4. On se contentera de traiter des grammaires pouvant être traitées par analyse descendante. La structure du programme engendré sera ainsi raisonnablement simple.

Grammaire des grammaires

Pour construire le programme demandé, il est utile de remarquer que ce programme demandé effectue lui-même une analyse syntaxique; plus précisément il analyse la description d’une grammaire. En d’autres termes: il existe une grammaire des descriptions de grammaire.

Il est fortement recommandé de construire cette grammaire des grammaires sur papier avant de commencer l’écriture du programme. Ce n’est pas très difficile et vous simplifiera la tâche. Surtout, ce travail est de toute façon nécessaire pour la question suivante.

5  Autogénération

Appelons Zacc le programme écrit dans la question précédente. Ce programme écrit est donc un programme qui analyse une grammaire pour fabriquer un (autre) programme d’analyse syntaxique. Il s’agit ensuite de réussir à ce que ce programme s’engendre lui-même !

Pour cela il suffit de:

  1. Donner la grammaire des grammaires.
  2. Annoter celle-ci avec les morceaux de programmes correspondant à Zacc.
  3. Passer cette grammaire annotée en argument à Zacc.

Si votre programme Zacc est correct, il doit alors produire un programme Zacc’ à peu près identique à Zacc et surtout équivalent. C’est-à-dire que Zacc’, si on lui passe la même grammaire annotée rendra une nouvelle copie de lui même en résultat.

Remarque

La possibilité pour un programme de s’engendrer lui-même est habituelle en compilation. Par exemple, un compilateur (C, java, caml…) sera souvent lui-même écrit en C, java ou caml. En anglais on appelle cela le bootstrap, puisque tout se passe comme si on pouvait décoller en tirer sur la languette de ses propres bottes !

En pratique, dans le cas des compilateurs, la première version doit, bien sûr, avoir été écrite dans un autre langage.

Par ailleurs, le bootstrap est, comme dans ce sujet, une bonne manière de vérifier la correction du programme écrit.

6  Références

Yacc.

Un exemple en français ici.

This document was translated from LATEX by HEVEA.