Master M1 - SLPC - TP à rendre le 8 novembre 2013.
L'objectif de ce travail est d'implémenter un interpréteur pour le
langage While
(vu en cours).
- Le comportement de cet interpréteur est défini par la
sémantique opérationnelle du langage.
- Il doit calculer et afficher le contenu de la mémoire et de
l'environnement à chaque pas d'exécution du programme.
- Il peut s'implémenter par un parcours de l’arbre abstrait
(AST) du programme.
- Vous considérerez une liaison statique pour les procédures, et
une liaison dynamique ou une liaison statique (au choix) pour
les variables.
Vous pouvez implémenter votre interpréteur en C, C++, Java, ADA ou
OCaml. Nous fournissons la partie analyse syntaxique et construction
de l'AST dans le cas d'une implémentation en C, mais notez
qu'utiliser OCaml
peut également grandement faciliter la programmation
...
Quelques
contraintes pratiques :
- vous devez travailler en binôme
- vous devez rendre votre travail par mail à votre enseignant
de TD, le
vendredi 8 novembre, sous forme d'une archive contenant
:
- vos fichiers sources
- un mini manuel utilisateur : comment compiler, exécuter,
quelles sont les limites, ...
- un jeux d'essais de programmes While sur lesquels
votre interpréteur fonctionne
Quelques
ressources fournies
(si vous choisissez une implémentation en C !)
- le code source d'un analyseur While
- main.c: programme principal, lance
l'analyse sur un fichier d'entrée
- tree.c: construction et affichage de
l'AST
- type.h: définition des types et
constantes globales
- while.l: analyseur lexical, en flex
- while.y: analyseur syntaxique, en yacc
- Makefile: pour compiler l'analyseur
- exemples de programmes While syntaxiquement corrects
- ex1.w: un exemple très simple
- ex2.w: un exemple avec (presque) toutes
les constructions du langage
- ex3.w: un exemple pour illustrer la
sémantique des liens statiques
L'ensemble de ces fichiers est disponible dans l'archive suivante :
WhileParser.tgz.
Comment
utiliser ces ressources :
- compiler l'analyseur : make
- exécuter l'analyseur :
./while ex1.w
analyse le fichier ex1.w et affiche son AST
ou
./while
analyse
la séquence lue sur stdin (terminée par ^D), et affiche son AST.
Le
langage while
Grammaire
concrète
(les symboles terminaux sont en gras, un identifier
est une séquence de lettres ou chiffres débutant par une lettre, un
integer est une séquence de
chiffres).
Notez que cette syntaxe concrète est légèrement différente de celle
utilisée en cours et TD).
program ::= bloc
bloc ::= declare
declaration_list begin
instruction_list end
declaration_list ::= declaration | declaration_list ; declaration
declaration ::= var identifier | proc identifier (formal_param_list) is bloc
instruction_list ::= instruction | instruction_list ; instruction
instruction ::= identifier
:= e | while b do instruction od| if b then
instruction else
instruction | call identifier
(effective_param_list)
formal_param_list ::= epsilon | identifier | identifier
, formal_param_list
effective_param_list ::= epsilon | e | e ,
effective_param_list
e ::= e + t | t
t ::= t * f | f
f::= ( e )| identifier | integer
b ::= b /\ bb | bb
bb ::= e < e | e = e | ^ bb | (b)
Arbre Abstrait (AST)
La structure de l'AST peut être déduite du code de la fonction
print_tree() du fichier
tree.c
On suppose que les programmes sont bien typés (pas de vérification
de types effectuées par l'analyseur).