Exercices 1

Exercice 4 (Programmation)

L'exercice suivant vous permet de vous rappeler des principes de base de Java, afin d'expérimenter avec quelques fondements de la compilation (grammaires, arbres syntaxiques, interprétation, tables de symboles). Il est conseillé de prendre le temps pour le finir en tout cas, même si vous n'y parvenez pas pendant les heures de cours. Notez que des connaissances de base en Java sont indispensables pour le projet.

La grammaire suivante décrit un langage de commandes.

Stm --> Stm ";" Stm | id ":=" Exp | "print" Exp
Exp --> num | id | Exp Bop Exp
Bop --> "+" | "-" | "*" | "/"

Le fichier Ex1.java contient une représentation incomplète en java de cette grammaire, ainsi qu'un interprète également à compléter.

Compilez le programme (javac Ex1.java) et exécutez-le (java Ex1).
Ajoutez le code nécessaire à l'interprétation de "print 15 + 3 + 2002". (Voir aussi dans la méthode main.)
Complétez le reste du code. Il est conseillé de travailler exemple par exemple.

Que faudrait-il ajouter au programme pour ne plus devoir définir les arbres à la main?

Remarques

La création des arbres:

Les non-terminaux Stm et Exp sont représentés par des classes abstraites.
Chacune des règles de la grammaire est représentée par une sous-classe à une de ses classes abstraites. Ceci permettra plus tard de créteer des objets pour chaque instance de Stm ou Exp.
Les variables des objets représentent les symboles à droite de la flève. Donc, dans CmpStm on aura deux variables, par exemple.
Les constructeurs prennent comme arguments les sous-arbres et les assignent aux variables d'objet.

////////////////////////////////////////////////////////////
abstract class Stm {}

// Stm  -->  Stm ";" Stm   (CmpStm)
class CmpStm extends Stm {
	Stm stm1, stm2;
	CmpStm(Stm stm1, Stm stm2) {
		this.stm1 = stm1; this.stm2 = stm2; }
}

// Stm  -->  id "::=" Exp  (AssStm)
class AssStm extends Stm {
	String id; Exp exp;
	AssStm(String id, Exp exp) {
		this.id = id; this.exp = exp; }
}

// Stm  -->  "print" Exp   (PrtStm)
class PrtStm extends Stm {
	Exp exp;
	PrtStm(Exp exp) { this.exp = exp; }
}


////////////////////////////////////////////////////////////
abstract class Exp {}

// Exp  -->  num            (NumExp)
class NumExp extends Exp {
	int num;
	NumExp(int num) { this.num = num; }
}

// Exp  -->  id              (IdExp)
class IdExp extends Exp {
	String id;
	IdExp(String id) { this.id = id; }
}

// Exp  -->  Exp BinOp Exp    (OpExp)
class OpExp extends Exp {
	Exp exp1, exp2; int op;
	OpExp(Exp exp1, int op, Exp exp2) {
		this.exp1 = exp1; this.op = op; this.exp2 = exp2; }
}

L'interprétation des arbres:

Deux méthodes, une pour Stm, une pour Exp.
Les méthodes regardent de quelle instance (sous-type de Stm respectivement de Exp) stm respectivement exp est.
Un cast correspondant permet d'accéder d'une manière récursive aux variables des objets pour les interpréter.

	public void interprete(Stm stm) {

		if (stm instanceof CmpStm) {
			CmpStm cast = (CmpStm)stm;
			interprete(cast.stm1);
			interprete(cast.stm2);
			return;
		}

		if (stm instanceof AssStm) {
			AssStm cast = (AssStm)stm;
			int res = interprete(cast.exp);
			table = enter(cast.id, res, table);
			return;
		}

		if (stm instanceof PrtStm) {
			PrtStm cast = (PrtStm)stm;
			int res = interprete(cast.exp);
			System.out.println(res);
			return;
		}

		throw new Error("bad statement.");

	}

	public int interprete(Exp exp) {

		if (exp instanceof NumExp) {
			NumExp cast = (NumExp)exp;
			return cast.num;
		}

		if (exp instanceof IdExp) {
			IdExp cast = (IdExp)exp;
			return lookup(cast.id, table);
		}

		if (exp instanceof OpExp) {
			OpExp cast = (OpExp)exp;
			int res1 = interprete(cast.exp1);
			int res2 = interprete(cast.exp2);
			switch (cast.op) {
			case BinOp.Plus: return res1 + res2;
			case BinOp.Minus: return res1 - res2;
			case BinOp.Times: return res1 * res2;
			case BinOp.Div: return res1 / res2;
			default: throw new Error("unknown operator " + cast.op);
			}
		}

		throw new Error("bad expression.");

	}

Christine Röckl

Last modified: Thu Mar 14 16:08:30 CET 2002