Analyse syntaxique

Voici le cours correspondant. La solution se trouve dans le fichier parser.mly.

Présentation

Nous utilisons aujourd’hui un générateur d’analyseurs syntaxiques, c’est-à-dire un outil qui, à partir d’une grammaire, produit le code d’un analyseur syntaxique. (Notons qu’il s’agit d’une forme de compilation!)

Les générateurs les plus utilisés sont basés sur le formalisme LR et descendent de yacc, le premier outil du genre, développé dans les années 70. Dans le monde d’Objective Caml, l’outil standard est ocamlyacc. Nous utiliserons de préférence menhir, qui est plus agréable d’utilisation.

L’objectif de ce TD est d’écrire un analyseur syntaxique pour Pseudo-Pascal, qui doit permettre de passer de la syntaxe concrète à la syntaxe abstraite. La syntaxe abstraite de Pseudo-Pascal est résumée par cette fiche et est définie formellement dans le fichier LPP.mli.

Les langages LPP (défini par LPP.mli) et et PP (défini par PP.mli) sont en fait identiques – il s’agit dans les deux cas de Pseudo-Pascal – à ceci près que dans LPP, les arbres abstraits sont annotés par des positions en provenance du code source, tandis que dans PP, ces positions ont été supprimées. La chaîne de compilation est la suivante: l’analyseur syntaxique produit des arbres au sens de LPP; le typeur (implémenté dans typechecking.ml) analyse des arbres de LPP, et utilise les positions pour afficher de bons messages d’erreur si besoin; puis les positions sont supprimées (lpp2pp.ml), car elles ne sont pas utiles dans la suite. L’interprète que nous avons écrit la semaine dernière utilisait des arbres PP. L’analyseur syntaxique que nous écrivons aujourd’hui doit produire des arbres LPP.

Progression

Comme d’habitude, il vous faut télécharger l’archive td3.tar.gz. La compilation se fait à l’aide de la commande make.

L’analyseur lexical vous est fourni (lexer.mll), ainsi qu’un analyseur syntaxique incomplet, situé dans le fichier parser.mly. Il y manque:

  1. la définition de la syntaxe des expressions – les seules expressions reconnues pour le moment sont les constantes entières;
  2. la définition de la syntaxe des instructions – les seules instructions reconnues pour le moment sont les instructions d’affectation à une variable;
  3. des déclarations de précédence des opérateurs.

Vous pouvez vérifier que le petit compilateur accepte un programme qui n’utilise que les constructions reconnues par cet analyseur incomplet, comme zero.p:

program var x : integer; begin x := 0 end.

Le petit compilateur accepte ce fichier et ne signale aucune erreur de syntaxe: 

# ./compilo test/zero.p

Vous pouvez passer l’option -dpp au petit compilateur pour lui demander d’afficher le programme Pseudo-Pascal après l’avoir analysé (c’est-à-dire que le petit compilateur effectue d’abord la traduction de la syntaxe concrète vers la syntaxe abstraite, puis la traduction inverse, et affiche le résultat). On doit alors obtenir un programme identique au programme source, modulo l’indentation, le parenthésage, etc. qui peuvent être différents. 

# ./compilo -dpp test/zero.p
program

var 
  x : integer; 
  
begin
  x := 0
end.

Vous pourrez vérifier expérimentalement que l’analyseur syntaxique qui vous est fourni est bel et bien incomplet: 

# ./compilo test/trivial.p
File "test/trivial.p", line 4, characters 4-11:
Syntax error.

Ici, il n’a pas reconnu l’appel de procédure writeln(10).

L’objectif est de compléter l’analyseur syntaxique.

Il vous faut compléter la grammaire des définitions et des instructions. Au fur et à mesure que vous ajouterez des constructions syntaxiques, vous verrez apparaître des conflits, qui seront signalés par Menhir. Vous devrez comprendre ces conflits et les résoudre (les éliminer) à l’aide de déclarations de précédence.

Lorsque vous compilerez l’analyseur syntaxique incomplet qui vous est fourni, vous constaterez que Menhir affiche des avertissements: certains lexèmes (tokens) et certaines productions ne sont jamais utilisés. C’est normal: l’analyseur est incomplet et contient effectivement des morceaux qui ne sont pas (encore) utilisés.

Un premier critère de réussite est fourni par la commande make test. Pour chaque programme Pseudo-Pascal dans le sous-répertoire test/, on vérifie que ce programme est accepté par votre analyseur syntaxique.

Un second critère de réussite est fourni par la commande make dpp. Pour chaque programme Pseudo-Pascal dans le sous-répertoire test/, on vérifie que la fonction ./compilo -dpp est involutive. En d’autres termes, si on effectue l’analyse syntaxique puis l’affichage du programme, on doit obtenir un texte qui peut à nouveau être analysé puis affiché à l’identique. On vérifie ainsi que l’analyseur syntaxique et l’afficheur sont d’accord entre eux: par exemple, si l’analyseur syntaxique pense que + est associatif à gauche alors que l’afficheur pense qu’il est associatif à droite, ce test échouera pour une entrée de la forme x+(y+z).

Ces deux critères ne garantissent pas que votre analyseur syntaxique est correct: par exemple, un analyseur syntaxique trivial, qui accepte tout et construit un arbre de syntaxe correspondant au programme vide, vérifierait ces deux critères!

Un troisième critère de réussite est fourni par la commande make reftest. Pour chaque programme Pseudo-Pascal dans le sous-répertoire test/, on vérifie que le comportement de ce programme, obtenu via ./compilo -ipp, est identique au comportement attendu, qui a été obtenu à l’aide du petit compilateur de référence (dont l’analyseur syntaxique est supposé correct) et stocké dans un fichier .out.

À propos de Menhir

Non-terminaux paramétrés

L’une des caractéristiques qui distinguent Menhir est la possibilité de définir des symboles non-terminaux paramétrés. Un langage de programmation moderne, comme Objective Caml, Haskell ou Java, permet de définir une fois pour toutes un type des listes, paramétré par le type des éléments. De même, Menhir permet de définir une fois pour toutes la syntaxe des listes, paramétrée par la syntaxe des éléments. Bien sûr, diverses variantes sont possibles, selon que l’on veut autoriser ou non la liste vide, selon que les éléments de la liste sont délimités par des séparateurs, des terminateurs, etc.

La librairie standard de Menhir définit un certain nombre de non-terminaux paramétrés, qui sont souvent utiles. Ces définitions sont décrites dans le manuel, figure 3. On les trouve également dans le fichier standard.mly. Bien sûr, rien ne vous empêche de définir vos propres symboles non-terminaux paramétrés.

Pour donner un exemple de l’utilité des non-terminaux paramétrés, supposons que l’on souhaite reconnaître une liste d’expressions séparées par des virgules, potentiellement vide, et délimitée par des parenthèses. (Dans le cas de Pseudo-Pascal, cela correspond à la liste des arguments effectifs d’un appel de fonction.) En l’absence de non-terminaux paramétrés, on devrait effectuer une définition en trois étages – voici par exemple ce que l’on devrait écrire si l’on utilisait ocamlyacc: 

delimited_comma_separated_expression_list:
| LPAREN comma_separated_expression_list RPAREN
    { $2 }

comma_separated_expression_list:
|
    { [] }
| nonempty_comma_separated_expression_list
    { $1 }

nonempty_comma_separated_expression_list:
| expression
    { [$1] }
| expression COMMA nonempty_comma_separated_expression_list
    { $1 :: $3 }

Si l’on utilise Menhir, les notions d’objet délimité et de liste avec séparateurs sont déjà définies dans la librairie standard (consultez leur définition dans standard.mly), ce qui permet d’utiliser directement le symbole non-terminal delimited(LPAREN, separated_list(COMMA, expression), RPAREN), sans devoir effectuer aucune définition auxiliaire.

Si X est un non-terminal, Menhir permet d’écrire X?, X*, et X+. Ces notations sont considérées comme des abréviations pour option(X), list(X), et nonempty_list(X), respectivement. Les symboles non-terminaux paramétrés permettent ainsi de considérer ces notations comme de simples cas particuliers d’un mécanisme beaucoup plus général.

Conflits

Un second atout de Menhir est sa capacité à expliquer les conflits (shift/reduce et reduce/reduce) sous une forme relativement lisible.

Lorsque Menhir signale un ou plusieurs conflits, vous devez consulter le fichier parser.conflicts. Celui-ci justifie chaque conflit en expliquant en quoi ce conflit correspond à une ambiguïté de la grammaire. Plus précisément, pour chaque conflit, Menhir construit une phrase (composée de symboles terminaux et non-terminaux) qui peut être interprétée de deux façons différentes – cette phrase est (un préfixe de) la frange de deux arbres d’analyse syntaxique distincts. Ceci prouve que la grammaire n’est pas LR(1), et (souvent) lorsque cela se produit, la grammaire est effectivement ambiguë.

Vous pouvez également consulter le fichier parser.automaton. Moins lisible, celui contient la description de l’automate LR qui a été engendré, et indique quels états contiennent des conflits.

En général, il existe deux façons de résoudre un conflit. L’une est de donner des directives de précédence (%left, %right, %nonassoc, %prec) bien senties. Ce mécanisme offre l’avantage de ne demander aucune modification de la grammaire, mais peut être difficile d’emploi, et doit être utilisé avec parcimonie. L’autre est de modifier la grammaire pour éviter le conflit. Lorsque l’on utilise Menhir, l’emploi judicieux de la directive %inline permet d’effectuer certaines modifications de la grammaire de façon transparente, et permet d’éliminer certains conflits sans difficulté.

Dans le TD d’aujourd’hui, la plupart des conflits pourront être résolus à l’aide de directive de précédence. Cependant, la directive %inline a été utilisée pour définir le symbole non-terminal binop. À titre d’exercice, vous pourrez vérifier que ceci permet d’éviter certains conflits – supprimer la directive fait ré-apparaître ces conflits – et vous pourrez tenter d’expliquer pourquoi.

Ce document a été traduit de LATEX par HEVEA