Ceci n'est qu'un ** exemple ** de corrige : 
  - la plupart des questions admettent differentes reponses possibles
  - il y a donc beaucoup d'autres solutions correctes ...


Partie 1 
========

Q1. 
	AB est un lexeme incorrect.

Q2. 
    Une solution consiste a reconnaitre les sequences de caracteres 
    consitituees de lettres minuscules, puis de "filtrer" parmi 
    ces sequences celles qui correspondent aux mots-cles.


    Fragment de code :

		selon etat   

            cas INIT :
                  si CC dans 'a'..'z' alors
 					etat <- CHAINE 
					lexeme_courant.chaine <- CC
					lexeme_courant.nature <- IDF 
					Avancer
                  sinon 
					...
				  fsi

			cas CHAINE : 
				  si CC dans 'a'..'z' alors
					lexeme_courant.chaine <- leceme_courant.chaine & CC
					Avancer 
				  sinon 
					Etat <- FIN
				  fsi

			cas FIN :
				  si lexeme_courant.nature = IDF alors 
					si  lexeme_courant.chaine = "si" alors
						lexeme_courant.chaine <- SI 
					sinonsi lexeme_courant.chaine = "alors" alors
						lexeme_courant.chaine <- ALORS
					etc.
 		 fselon


Partie 2 
========= 

Q3. 

	"soit x dans 2" est syntaxiquement incorrect

Q4.
	(voir feuille jointe)

Q5.

  type Ast is private;

   type TypeAst is (OPERATION, VALEUR, IDF, SI_ALORS_SINON, SOIT_DANS);
   type TypeOperateur is (PLUS, MUL, MOINS, INF, SUP, EGAL, ...);

private

   type NoeudAst;
   type Ast is access NoeudAst;

   type NoeudAst is record
      nature : TypeAst;
      operateur : TypeOperateur;
      gauche, milieu, droite : Ast;
      valeur : Integer;    -- pour les entiers
      valeurbool : Integer;    -- pour les booleens
	  nom : chaine;   -- pour les idfs 
   end record;

Q6.

	Rec_Pgm (A: out Ast) = 
		Rec_Exp (A) ; 
		si LC.nature /= FSEQ alors Erreur fsi

	Rec_Exp (A : out Ast) = 
     lexique
		Ag, Am, Ad : Ast 
		nom_idf : chaineconstruire_soit_dans( nom_idf, Am, Ad) 
	  debut 
		selon LC.nature 

			cas SOIT : 
				Avancer ;
				si LC.nature = IDF alors 
					nom_idf <- LC.chaine ; Avancer 
				sinon 
					Erreur 
				fsi 
				si LC.nature = EGAL alors 
					Avancer 
				sinon 
					Erreur 
				fsi 
				Rec_Exp (Am) 
				si LC.nature = DANS alors 
					Avancer 
				sinon 
					Erreur 
				fsi 
				si LC.nature = PARO alors 
					Avancer 
				sinon 
					Erreur 
				fsi 
				Rec_Exp (Ad) 
				si LC.nature = PARF alors 
					Avancer 
				sinon 
					Erreur 
				fsi 
				A <- construire_soit_dans( nom_idf, Am, Ad) 
				
 
			cas SI : 
				Avancer ;
				Rec_Exp_bool (Ag) 
				si LC.nature = ALORS alors 
					Avancer 
				sinon 
					Erreur 
				fsi 
				Rec_Exp (Am) 
				si LC.nature = SINON alors 
					Avancer 
				sinon 
					Erreur 
				fsi 
				Rec_Exp (Ad) 
				A <- construire_si_alors_sinon( Ag, Am, Ad) 

			cas PARO : 
				Avancer ;
				Rec_Exp_Arith (A) 
				si LC.nature = PARF alors 
					Avancer 
				sinon 
					Erreur 
				fsi 
		fin


construire_soit_dans( nom_idf, Am, Ad)  renvoie un Ast de nature SOIT_DANS
et avec pour fils gauche, milieu et droit respectifs : 
	- l'Ast de nature IDF et de nom nom_idf  
	- l'Ast Am
	- l'Ast Ad

construire_si_alors_sinon(Ag, Am, Ad)  renvoie un Ast de nature SI_ALORS_SINON
et avec pour fils gauche, milieu et droit respectifs les Ast Ag, Am et Ad. 
 

Partie 3
=========

Q7. 

type cellule ; 

type cellule is record
	valeur : integer ;
	suiv = access cellule ;
end record ;

type pile_val is access cellule ;  -- pile de valeurs entieres

type tab_symb is array ('a' .. 'z') of pile_val ;
   -- la table des symboles est un tableau de piles de valeurs entieres, 
   --   indexe par les nom des identificateurs

TS : tab_symb ; -- TS est la table des synboles

procedure initialiser ; 
  -- initialise toutes les cases du tableau TS a Nil (pile vide)

procedure empiler_val (x : in character ; v : in integer) ;
  -- empile la nouvelle valeur v dans TS(x) 

procedure depiler_val (x : in character) ;
  -- depile la valeur en sommet de TS(x)

function valeur_idf (x : in character) is integer ;
  -- renvoie la valeur en sommet de TS(x)

Q8.

function valeur (A : Ast ) : integer is
begin
	case A.TypeAst is
   		when OPERATION =>
			return evaluer(A) ;
			-- comme dans le projet 

		when VALEUR  =>
			return A.valeur ;
			-- comme dans le projet 

		when IDF  =>
			return val_idf (A.valeur) ;

		when SI_ALORS_SINON  =>
			b = valeur_bool (A) ;  -- comme dans le projet
			if b then 
				return evaluer (A.milieu)
			else 
				return evaluer (A.droite)
			end if ;

		when SOIT_DANS =>
			v = evaluer (A.milieu) ;
			empiler_val (A.gauche, v) ;
			v = evaluer (A.droite) ;
			depiler_val (A.gauche) ;
			return v ;
	end case ;
			
		
end 

Partie 4
=========


Q9.

On etend le type TypeAst :
   type TypeAst is (..., FUNC, CALL);


On ajoute les champs param et nom_param a la structure NoeudAst :

   type NoeudAst is record
      nature : TypeAst;
      operateur : TypeOperateur;
      gauche, milieu, droite : Ast;
      valeur : Integer;    -- pour les entiers
      valeurbool : Integer;    -- pour les booleens
      nom : chaine;   -- pour les idfs ou pour les fonctions
      param : Ast;  -- parametre  effectif pour un appel de fonction
      nom_param : chaine;  -- nom du parametre  formel pour une declaration de fonction
  end record ;

Q10.

On note TF la table des fonctions et on ajoute 1 nouveau cas a la fonction valeur

	when CALL =>
		v = evaluer (A.nom_param) ; -- evaluation du parametre effectif
		substituer (A.param, v, TF(A.nom) ; 
		return evaluer TF(A.nom)

La procedure substituer (x, v, A) remplace toutes les occurrences libres du nom x 
par la valeur v dans l'arbre A.

Q11. 

[la reponse a cette question depend des reponses aux questions precedentes, elle peut donc varier !]

Cette solution ne permet pas de traiter des fonctions recursives, car l'Ast de la fonction 
est modifie des l'appel principal par la procedure "substituer". Il n'est donc plus 
possible de traiter convenablement les prochains appels recursifs eventuels.

Pour y remedier il faudrait empiler les valeurs courantes des parametres a chaque appel 
(sans modifier "definitivement" l'Ast de la fonction).