Sablecc et évaluation d'expressions

Exercice 1 - Grammaire simplifiée d'évaluateur d'expression

Voici un exemple d'utilisation d'un petit évaluateur d'expressions très simples. Les lignes sont saisies, puis chacune d'elle est « évaluée » et son résultat est affiché.

Par exemple, si les lignes suivantes sont saisies :

a=2+3
b=a+2
c=3*a
d=3+2*3
a=4
b

5
7
15
9
4
6

Les expressions utilisées dans cet exemple permettent de réaliser des opérations arithmétiques simples (+, -, *, /) et des affectations (=) ; dans tous les cas, le résultat de l'expression est affiché.

L'outil sablecc permet de produire, à partir d'une grammaire comme celle donnée ci-dessous, de générer un analyseur lexical (lexer) et un analyseur synatxique (parser). On peut spécifier le package de destination de toutes les classes générées par sablecc au début de la grammaire.

Package fr.umlv.sableccexample;

Tokens
 number = ['0'..'9']+;
 plus =    '+'; 
 minus =   '-';
 mult =    '*';
 div =     '/';
 l_par =    '(';
 r_par =    ')';
 blank =   (' ' | 10 | 13 | 9)+;

Ignored Tokens
 blank;

Productions
 expr = 
	{term}   term |
	{plus}   expr plus term |
	{minus}  expr minus term 
	;
 term = 
	{factor}  factor |
	{mult}    term mult factor |
	{div}	  term div factor
	;
 factor =
	{number}   number |
	{paren}    l_par expr r_par 
	;

1. Cette grammaire ne permet pas d'utiliser des variables, ne décrit pas l'affectation et est limitée à une seule ligne d'évaluation. Modifier cette grammaire afin qu'elle accepte l'exemple du haut de page.
2. Afin de vérifier qu'elle est correcte, lancer sablecc sur cette grammaire. Il est important de bien supprimer les anciens fichiers générés lorsqu'on relance une nouvelle fois sablecc.

Exercice 2 - Arbres des expressions

Avant d'utiliser les classes générées par sablecc, nous allons préciser les types de la hiérarchie dont nous aurons besoin pour représenter les expressions. Récupérer les classes Expr.java et Operations.java.

La classe Expr définit le type général de toute expression. Outre le type énuméré des opérateurs, la classe Operations définit des méthodes statiques permettant de construire chaque type d'expressions. En réalité, elle permet de construire des opérateurs binaires et des nombres, mais pas de variables ni d'affectations.

1. Après avoir réfléchi d'une part à la notion de « portée»  (scope) et à la façon de l'implémenter et d'autre part à la manière d'associer un nom de variable à l'« arbre»  d'expression qu'il représente, compléter la classe Operations avec des méthodes variable() et assign() permettant de construire les expressions correspondantes. Vous aurez probablement besoin d'ajouter une nouvelle classe.
2. Avec ces classes complétées, construisez « à la main»  des objets de type Expr représentant chacune des lignes du premier exemple du haut de cette page, et évaluez les.

Exercice 3 - Construction et utilisation de l'AST

1. Supprimez tous les fichiers déjà générés par sablecc.
2. Récupérez le fichier example.grammar, et relancer sablecc avec cette version. Des fichiers java sont générés dans quatre packages.
   • lexer contient les classes chargées de l'analyse lexicale, en particulier la classe Lexer ;
   • node contient les classes représentant les différents nœuds de l'AST (Abstract Syntax Tree), déclinés suivant les productions de la grammaire. En particulier, les types dont le nom commence par T représentent les terminaux (e.g. TPlus pour le caractère « +» ), ceux dont le nom commence par P représentent les productions de la grammaire (e.g. PExpr pour les productions « expr» ), déclinées suivant les différentes alternatives, dont les noms commencent par A (e.g. ATermExpr, APlusExpr, AMinusExpr, qui sont des sous-types de PExpr). Le type Start représente la racine de l'arbre (axiome de la grammaire). Tous ces types sont des sous-types de Node ;
   • analysis fournit des types correspondant à des sortes de « visiteurs»  utilisés pour parcourir l'AST. Une implantation qui ne fait rien de l'interface Analysis est fournie par la classe AnalysisAdapter et deux classes de visites de l'AST (par défaut) en profondeur d'abord sont données ;
   • parser contient les classes chargées de l'analyse syntaxique, en particulier la classe Parser qui offre une méthode parse() construisant l'AST.
3. Récupérez le fichier Main.java, et compléter la classe SimpleInterpret.java qui permet de réaliser l'évaluation souhaitée.