:: Enseignements :: ESIPE :: E4INFO :: 2011-2012 :: Génération de code ::
[LOGO]

Interpréteur simplePS

Ce projet consiste à réaliser, à l'aide du générateur d'analyseur lexical et syntaxique Tatoo, un interpréteur pour un langage PostScript simplifié.

Le langage PostScript

Introduction

PostScript est un langage de programmation créé en 1982 destiné à la description graphique de pages 2D. Il est destiné à l'origine à être interprété par des imprimantes. Toutefois celui-ci est néanmoins un langage Turing complet capable d'exécuter tout algorithme (avec notamment avec des structures conditionnelles et de boucle). A l'instar de la machine virtuelle Java, PostScript utilise un modèle de calcul à pile : pour chaque opération, on empile les opérandes puis on appelle l'opérateur qui dépile ces opérandes et empile le résultat. La pile de calculs peut accueillir des objets de différents types : des nombres (on se limitera ici aux entiers), des chaînes de caractères mais également des noms symboliques ainsi que des procédures (sorte de macros délimitées par des accolades dont l'exécution est différée).

Il existe trois versions de PostScript (niveau 1, niveau 2 et niveau 3), chaque version apportant des fonctionnalités supplémentaires (notamment sur le support des images bitmap et des fontes). On se limitera à PostScript niveau 1 avec l'implantation d'un nombre limité d'opérateurs (les courageux peuvent toujours lire la spécification complète de 774 pages).

Quelques exemples

Un 1er exemple : le traditionnel 'Hello World'

On souhaite écrire un 'Hello World' sur une page 
%!PS
/Times 30 selectfont	% choix de la fonte
100 200 moveto		% on se déplace sur la page au coordonnées x=100,y=200 (x=0,y=0 est au base à gauche de la page)
(Hello world !) show	% affiche le texte
showpage		% affiche la page
On pourra tester cet exemple avec l'interpréteur PostScript GhostScript (commande gs, normalement disponible sur toutes les distributions Linux). D'après la spécification PostScript, une unité de coordonnée correspond à 1/72ème de pouce (environ 0,35 mm).

Un 2ème exemple traditionnel : le calcul des nombres de Fibonacci

Nous définissons une fonction de calcul récursive (pas vraiment optimale) des nombres de Fibonacci : 

%!PS
/fib { 
	dup 1 gt { % si n > 1
		1 sub dup % la pile contient (n-1) et (n-1)
		fib % on appelle fib(n-1)
		exch % on échange les opérandes, la pile contient [fib(n-1), n-1]
		1 sub % on calcule (n-1) - 1
		fib % on appelle fib(n-2)
		% la pile contient maintenant [fib(n-1), fib(n-2)]
		add % on calcule la somme
	} 
	{ % si n <= 1
		pop
		1 % empile 1
	} ifelse
} def

/n 15 def
/printint { 20 string cvs print } def

(The ) print
n printint % Print n
(-nth Fibonacci number is ) print
n fib printint
On constate qu'il est possible de définir une fonction par la structure /nomfonction { } def ; on emploie également la structure {} {} ifelse qui est execute une des deux procédures entre accolades en fonction de la valeur en haut de pile (calculée par dup 1 gt).

La grammaire du langage

Un programme simplePS est une succession d'opérandes feuille et d'opérateurs. Les caractères d'espacement (tabulations, retours à la ligne...) sont ignorés ainsi que les commentaires commençant par un caractère % et se terminant par une fin de ligne.

Une opérande feuille peut être une constante entière, une constante chaîne de caractères (entre parenthèses, cf Hello world) ou un nom de variable symbolique (obligatoirement préfixé par un / pour le distinguer d'un opérateur).

Un opérateur est un identificateur libre (ne commençant ni par un chiffre ni par un /). Celui-ci peut être un opérateur prédéfini dans Operators ou alors une macro créé dans le programme courant. Un opérateur a un effet sur l'environnement courant (dépilement d'éléments de pile, empilement d'éléments, mise à jour du dictionnaire de variables, action de dessin).

On implante également des structures de contrôles utilisant des séquences d'instructions (procédures) :
  • { procédure } if : exécute la procédure si le sommet de la pile contient true
  • { procedure1 } { procedure2 } ifelse : exécute procedure1 si le sommet de la pile est true, false sinon
  • { procedure } loop : exécute procedure un nombre indéfini de fois
On notera que if, ifelse et loop sont de vrais opérateurs en SimplePS ; on essaiera toutefois de les définir explicitement dans la grammaire en tant que mots-réservés. On définira également un opérateur exit permettant de sortir d'une boucle (car attendre éternellement la fin d'exécution d'une boucle c'est long --- surtout vers la fin ---).

Les opérateurs prédéfinis

Voici les différents opérateurs prédéfinis du langage. Leur implantation vous est déjà fournie avec la classe DefaultOperators. Il n'est pas nécessaire de les définir explicitement dans le lexique (ils seront recherchés en premier lieu lorsqu'un opérateur sera rencontré).

Les opérateurs de pile

Les opérateurs de dictionnaires

On choisit d'implanter qu'un seul opérateur pour manipuler le dictionnaire des variables locales. Il s'agit de l'opérateur def. L'élément d'indice n-1 de la pile est le nom de la variable (préfixé par /), l'élément d'indice n est sa valeur.

Les opérateurs mathématiques

Les opérateurs de comparaison

Les autres opérateurs (pour dessiner notamment)

Consignes

Dans un premier temps, on définira le fichier EBNF de description du lexique et de la grammaire. Il faut y déclarer les mots-clés des opérateurs structurels du langage (if, ifelse, loop, exit notamment), un élément identificateur pour les opérateurs prédéfinis et les variables créées ainsi que les constantes (entiers, chaînes de caractères). On définira des règles de grammaire adaptées pour supporter le langage. Il n'y a pas de problématique de priorité d'opérateurs à gérer, la notation utilisée étant postfixe (et non infixe).

Dans un deuxième temps, on s'attaque à la réalisation de l'interpréteur. Celui-ci est basé sur le (désormais bien connu) design-pattern de visiteur. Il utilise un environnement contenant :
  • le dictionnaire de variables
  • la pile d'opérandes utilisée pour l'exécution
  • le chemin de tracé courant avec les coordonnées courantes sur la page
  • une instance d'Operators. Une implantation vous est déjà fournie réalisant le dessin sur un Graphics d'une image bitmap (que l'on pourra ensuite admirer avec son visualisateur d'images favori).

Vous pouvez tester votre interpréteur sur les exemples inclus dans l'archive fournie. Cette archive contient également un squelette de code pour l'interpréteur ainsi qu'une classe DefaultOperators (le code fourni n'est qu'indicatif et pourra changer en fonction de la grammaire employée). On notera qu'il n'est pas nécessaire de définir l'ensemble des opérateurs comme mots-clés, ceux-ci étant "capturés" par le lexème 'identificateur' ; il faut ensuite récupérer l'opérateur correspondant à l'identificateur. Il peut s'agir d'un opérateur prédéfini dans Operators (récupéré par introspection) ou alors d'un opérateur (variable) ajouté dans le dictionnaire (par def). Une variable est un opérateur dans le sens où elle empile un objet correspondant à sa valeur ou elle exécute une procédure. Le fichier build.xml fourni requiert que le répertoire de Tatoo soit spécifié dans la variable d'environnement TATOO_HOME.

Un TP noté sera consécutif à ce projet : il consistera à réimplanter en temps limité certaines fonctionnalités existantes du langage SimplePS (ainsi que de nouvelles extensions surprises) et à répondre à quelques questions. Il aura lieu le mardi 28 août 2012 de 8h30 à 10h30 en salle 1b14. Il est conseillé de s'entraîner sur le projet et d'en rendre une version fonctionnelle à chilowi at univ-mlv.fr le 26 août au plus tard : lors du TP noté vous aurez (uniquement) à votre disposition l'archive que vous aurez préalablement rendue.

Quelques références utiles pour conclure

© Université de Marne-la-Vallée