Présentation

Vous allez devoir utiliser un outil de génération d’analyseurs syntaxiques. Les générateurs les plus utilisés sont ceux qui font partie de la famille de yacc (Yet Another Compiler Compiler), qui date des années 70. Pour OCaml, l’outil standard est ocamlyacc, mais nous utiliserons menhir, qui est plus agréable d’utilisation.

On peut voir la différence de style entre les deux, par exemple en regardant la façon de reconnaître une liste parenthésées d’expressions séparées par des virgules. Le code ocamlyacc est le suivant :

expression_list:
  | LPAREN expression_list_opt RPAREN { $2 }
;
expression_list_opt:
  | { [] }
  | comma_expression_list { $1 }
;
comma_expression_list:
  | expression { [$1] }
  | expression COMMA comma_expression_list { $1 :: $3 }

Le code menhir est plus concis et plus clair :

expression_list:
  | exp_list = delimited(LPAREN, separated_list(COMMA,expression), RPAREN) { exp_list }

Il s’agit d’écrire un analyseur syntaxique pour Pseudo-Pascal, donc de passer de la syntaxe concrète Pseudo-Pascal à la syntaxe abstraite donnée en cours. Cette dernière est la même que celle donnée dans le fichier d’interface LPP.mli que vous trouverez comme la semaine dernière dans l’archive pp.tar.gz à installer chez vous.

Pour vous permettre de vous concentrer sur le développement de votre parseur, on vous fournit notamment la liste des lexèmes dans tokens.mly, l’analyseur lexical dans lexer.mll et un début d’analyseur syntaxique dans parser.mly auquel il manque les règles de précédence des opérateurs, les instructions et les expressions (mais les conditions ont été traitées).

Voici quelques points sur menhir pour vous aider :

• par compatibilité avec ocamlyacc, on peut référencer les non-terminaux par $num où num est l’indice du non-terminal dans la production : dans la liste LPAREN expression_list_opt RPAREN, le mot-clé $2 fait référence à expression_list_opt.
• on préfère en général référencer un non-terminal par un nom explicitement donné dans la production, comme exp_list dans la production exp_list = ..., on prendra souvent le nom du non-terminal en question.
• par soucis de lisibilité, on peut ajouter des points-virgules, qui agissent comme des caractères blancs, par exemple:

  document:
    | head = head ; body = body ; tail = tail { ... }
  

• on utilisera si possible la librairie standard de menhir, qui définit les règles paramétriques les plus courantes. Elles sont détaillées dans le manuel de menhir, figure 3, voici leur équivalent sous forme d’expressions régulières :

  Règle de menhir option(X)  preceded(opening,X)  delimited(opening,X,closing)  list(X)  nonempty_list(X)  separated_list(sep,X)  separated_nonempty_list(sep,X)       Expression régulière X | є  opening X  opening X closing  X*  X+  X (sep X)* | є  X (sep X)*

• on peut déclarer qu’un non-terminal est %inline, ce qui a le même effet qu’expanser toutes les productions de ce non-terminal dans toutes les productions qui l’incluent. C’est recommandé pour les opérateurs arithmétiques en particulier, de façon à avoir une grammaire plus lisible (en factorisant les opérateurs) tout en gardant les règles de priorité des opérateurs (définies avec %left, %right ou %nonassoc).

Compilation et exécution

La compilation s’effectue encore une fois à l’aide du Makefile.

# make
...
menhir --ocamlc ``ocamlc.opt'' --infer -v --base parser tokens.mly parser.mly
File ``tokens.mly'', line 7, characters 30-33:
Warning: the token AND is unused.
...
ocamlopt.opt -o compilo   integer.cmx misc.cmx ...

Comme la semaine dernière, vous pouvez tester votre parseur en lui faisant parser du Pseudo-Pascal puis l’imprimer sur l’entrée standard :

# ./compilo -dpp test/zero.p

Vous pouvez vérifier que le compilateur complet fait lui le travail attendu :

# cd ..
# wget <URL-ci-dessus>
# tar xvzf petit.tar.gz && (cd petit && make)
# ../petit/compilo -dpp test/zero.p
program

var
  x : integer;

begin
  x := 0
end.

Conflits

En cas de conflit, vous devez aller regarder le fichier parser.conflicts, qui exprime les conflits en terme de grammaire. Le fichier parser.automaton contient l’automate sous-jacent, avec les conflits exprimés en terme d’état, comme c’est le cas en général avec les générateurs d’analyseurs syntaxiques du style de yacc.

On vous suggère notamment :

• d’utiliser autant que possible les règles paramétriques définies dans la librairie standard de menhir.
• d’utiliser de préférences les priorités des terminaux pour résoudre les conflits shift-reduce.

Non-terminaux et productions

Les productions concernant les expressions et les instructions sont à compléter. Les grammaires des types, des conditions, des blocs, des procédures, des fonctions et des programmes vous sont donnés. On vous conseil d’avancer progressivement et de tester régulièrement votre parseur. Laissez vous guider par les tests dans le répertoire test, en commençant par trivial{,2,3}.p.

Le cas de readln

Le traitement de readln est un peut spécial en Pseudo-Pascal, en effet comme en pascal on écrit readln(x) où x est une variable, ou readln(a[i]) où a et i sont des expressions. Car contrairement à Pascal, Pseudo-Pascal ne peut passer les paramètres par références. À vous de trouver une astuce pour traiter les deux cas d’utilisation cités précédemment.

Actions sémantiques

Les actions sémantiques construisent l’arbre de syntaxe abstraite du programme reconnu. Il faudra alors :

• mettre des constructions de l’arbre de syntaxe abstraite dans les actions du parseur.
• utiliser $startpos(X) et $endpos(X) pour donner les positions de début et de fin du terminal ou non-terminal X. En effet, la spécification est de construire un arbre de type LPP.program au lieu de PP.program, qui est le type de l’arbre pour lequel vous avez écrit un interprète la semaine dernière. Le language LPP est le même que le langage PP, avec des localisations pour pouvoir donner des messages d’erreur utiles. Cependant la production located, bien utilisée vous économisera la plupart des constructions de positions.

Vous pouvez à tout moment soit lancer des tests à la main pour commencer, soit utiliser l’entrée test du Makefile à l’aide de la commande make test : pour chaque fichier Pseudo-Pascal, on compare alors le résultat de l’exécution du programme originel avec le résultat obtenu en exécutant votre analyseur, en imprimant l’AST (Arbre de Syntaxe Abstraite), et en exécutant le programme imprimé.

Vous pouvez aussi vérifier que votre parseur est ré-entrant avec make dpp, c’est-à-dire que si vous prenez en entrée le programme que vous venez d’imprimez, vous obtenez la même sortie. Mais il est plus facile pour un parseur incorrect de passer ce test (essayez avec le parseur vide donné initialement).

Bonus

Voici quelques extensions syntaxique que vous pouvez implémenter en bonus.

Boucles for

Ajoutez le support des boucles for en utilisant la boucle while.

Par exemple for i := e1 to e2 do bloc;.

Tableaux avec initialisation

On veux pouvoir allouer un tableau et l’initialiser en même temps, voici un example arr := new array of integer [| 1, 2 + 3, f(x) |];.

Affectations simultanées

Cette extension permet d’affecter plusieurs variables en même temps, y compris de permuter le contenue de plusieurs variables.

Par exemple (v1, v2, v3) := (v2, v3, v1);

Affectation par bloc

Cette extension permet de transférer par blocs les éléments d’un tableau vers un autre, on pourra utiliser la construction des boucles for pour désucrer cette extension.

Par exemple arr1[i .. i+10] := arr2[0 .. 10];

Ce document a été traduit de L^AT_EX par H^EV^EA