LooAst

Le projet LooAst vise l'implémentation de l'AST (Abstract Syntax Tree) d'un micro langage. Ce sujet de IsoLoo est volontairement simplifié à l'extrême : il s'agit d'exercer votre aptitude à implémenter élégamment en Eiffel, et tirant partie de ses fonctionnalités telles que la conception par contrat.

Le langage Loo

Voici un exemple du langage Loo :

let
  a := 42
in
  let
    b := if a = 0 then 42 else 51
    res := a + b
  in
    -- On n'a pas de test de différence en Loo,
    -- il faut donc écrire (a = b) = 0 pour
    -- tester si a /= b.
    if (a + b = 93) = 0 then
      res := -1  -- ceci n'est pas un opérateur unaire
                 -- mais bien l'entier `-1'.
    else
      res := 1
    res
  end
end

Lorsqu'on l'exécute, ce programme doit afficher

1

La syntaxe de Loo

Voici la grammaire du langage :

<program> ::= <expression>
<expression> ::= <integer>
               | <variable>
               | <variable> := <expression>
               | <expression> <op> <expression>
               | if <expression> then <expression> else <expression>
               | let <declaration>+ in <expression>+ end
<declaration> ::= <variable> := <expression>
<op> ::= + | - | * | /
       | < | =

Par convention d'écriture de grammaire, les parenthèses servent à grouper, le point d'interrogation signifie optionnel (i.e., 0 ou 1 fois), et le + représente la répétition 1 ou plusieurs fois.

Il ne sera pas demandé d'écrire d'analyseur syntaxique (ou /parser/) de Loo. Les programmes seront construits à l'intérieur de votre projet directement sous la forme d'arbre. Cela signifie en particulier qu'aucun programme mal formé syntaxiquement ne pourra être rencontré.

La syntaxe abstraite de Loo (LooAst)

L'exercice demandé est l'implémentation d'une hiérarchie de classes permettant de représenter un programme Loo. Ces classes sont très simplement définies par la grammaire.

Par exemple, en pseudo Eiffel :

class LOO_LET

inherit LOO_EXPRESSION
  redefine print, type, eval
 end

feature

  declarations : LINKED_LIST[LOO_DECLARATION]
  expressions  : LINKED_LIST[LOO_EXPRESSION]


  make (d: LINKED_LIST[LOO_DECLARATION],
        e: LINKED_LIST[LOO_EXPRESSION]) is ...

  -- Afficher cette expression ainsi :
  --  let
  --    declarations
  --  in
  --    expressions
  --  end
  display is ...

  -- Vérifier le typage, et calculer le type de cette
  -- expression.
  type (e: LOO_ENVIRONMENT) : LOO_TYPE is ...

  -- Évaluer et retourner la valeur de l'expression
  -- dans cet environnement (ou Void dans le cas des
  -- instructions).
  eval (e: LOO_ENVIRONMENT) : reference INTEGER is ...

end

Le typage de Loo

En Loo n'existe que deux types : le type Integer pour les expressions ayant une valeur entière, et le type Void pour les instructions qui, précisément, ne peuvent pas avoir de valeur.

Les règles sont les suivantes.

• programme

       <program> ::= <expression>
  

  L'expression doit être de type entier.
• entier littéral

       <expression> ::= <integer>
  

  L'expression résultante est de type entier.
• valeur de variable

       <expression> ::= <variable>
  

  Puisque les variables sont seulement de type entier, cette expression est de type entier. La variable doit avoir été définie.
• affectation

       <expression> ::= <variable> := <expression>
  

  La valeur affectée doit être entière. L'affectation est une instruction, donc de type Void.
• opérations binaires

       <expression> ::= <expression> <op> <expression>
  

  Elles nécessitent toutes que les parties droite et gauche soient entières, et retourne un entier.
• instruction et expression conditionnelles

       <expression> ::= if <expression> then <expression> else <expression>
  

  Derrière cette seule syntaxe se cachent deux opérations. Si les deux opérations (du then et du else) sont des instructions, alors le résultat est de type Void également ; ce cas s'apparente au if de Java, C, etc. Si par contre elles sont toutes les deux des expressions à valeur entières, alors le résultat est entier également ; ceci correspond à l'opérateur ? : de Java, C, etc.
  Bien entendu le test doit être de valeur entière.
  Tout autre cas est une erreur.
• introduction d'une portée

       <expression> ::= let <declaration>+ in <expression>+ end
  

  Aucune restriction sur les expressions (entre le in et le end). Le type de l'ensemble est celui de la dernière expression : il y a donc des expressions et des instructions de type let.
• déclarations

       <declaration> ::= <variable> := <expression>
  

  La variable ne doit pas avoir été définie dans la portée courante, et l'expression doit être de type entier.

La sémantique de Loo

• programme

       <program> ::= <expression>
  

  La valeur du programme (qui sera affichée) est la valeur de l'expression.
• entier littéral

       <expression> ::= <integer>
  

  La valeur de l'expression est celle de l'entier.
• valeur de variable

       <expression> ::= <variable>
  

  Retourne la valeur courante de la variable.
• affectation

       <expression> ::= <variable> := <expression>
  

  Met à jour la valeur courante de la variable.
• opérations binaires

       <expression> ::= <expression> <op> <expression>
  

  Pour l'arithmétique les sémantiques sont respectées, pour les comparaisons, le résultat est 0 pour le faux, et 1 pour le vrai.
• instruction et expression conditionnelles

       <expression> ::= if <expression> then <expression> else <expression>
  

  Si le test s'évalue à faux (0), alors le partie else est évaluée (et le cas échéant la valeur du if entier est celle-ci). Autrement, c'est la partie then qui est évaluée.
• introduction d'une portée

       <expression> ::= let <declaration>+ in <expression>+ end
  

  Dans le cas d'une expression, la valeur est celle de la dernière expression.
• déclarations

       <declaration> ::= <variable> := <expression>
  

  Initialise la valeur de la variable à celle de l'expression.

L'exercice demandé

Les fonctionnalités citées ci-dessus sont demandées dans l'ordre des sous-sections suivantes.

L'interface utilisateur

Il ne vous est pas demandé d'écrire un /analyseur syntaxique/ (/parser/ en anglais) ; en faire un est un exercice à part entière, qui relève plus de cours tels que THL ou GRANA que LOO. Par conséquent, l'utilisateur ne "tape pas" de programme Loo : ces programmes sont prédéfinis dans votre programme, et l'utilisateur ne fait qu'en choisir un.

Il est stipulé que dans votre rendu *il doit y avoir au moins dix programmes prédéfinis* : cinq corrects (qui affichent un résultat entier), et cinq incorrects (qui engendrent une exception). Ils doivent être réellement différents les uns des autres : ils doivent tester des aspects différents de votre compilateur.

Je suggère que votre classe maîtresse (lancée par l'exécution) aient plusieurs méthodes de création de programmes, par exemple :

  correct_bin : LOO_EXP is
  do
    Result := create {LOO_BIN}.make ("*",
                                     create {LOO_INT}.make (6),
                                     create {LOO_INT}.make (7))
  end

  undeclared_variable : LOO_EXP is
  do
     Result := create {LOO_VAR}.make ("toto")
  end

Le corps de la routine de création, après avoir demandé le numéro du programme voulu, effectue:

inspect num
  when 1 then exp := correct_bin
  when 2 then exp := undeclared_var
  ...
end

Il s'agira ensuite d'exécuter les opérations suivantes.

Affichage, display

Il s'agit simplement de réécrire l'AST sous forme humaine. Auparavant nous avions suggéré d'utiliser le nom print, ce qui est impossible : il est frozen dans ANY. Cependant si vous voulez faire les choses "bien", cherchez print_on.

Évaluation, eval

Implémenter une évaluation. Il faut prendre garde à :

• gérer correctement les environnements
• vérifier par contrats que le typage est correct
• vérifier par contrats que les déclarations sont correctes (on ne définit pas deux fois un nom dans un même étage de déclaration)

Tout programme incorrect doit donner lieu à un viol de contrat. Voici quelques exemples incorrects en syntaxe Loo :

a + b

let
  a := 1
  a := 1
in
  a + a
end

let
  a := 0
  b := 0
in
  a := b := 1
  a
end

Dans ce dernier cas le problème est lié au typage : b : 1= est une instruction qui n'a pas de valeur. Une affectation nécessite que l'expression ait une valeur, i.e., soit typé comme un entier.

Les comparaisons, = et <, renvoient des entiers : 0 (faux) et 1 (vrai).

Contrôle de type : type

Vérifier le typage de l'arbre avant de l'évaluer. Si les règles ne sont pas vérifiées, faire un joli message d'erreur. En aucune situation il ne doit être possible de voir à nouveau un contrat violé.

L'environnement

Une partie significative de cet exercice consiste en la conception d'un environnement, ou encore /table des symboles/. Cette structure se comporte comme un tableau associatif auquel sont adjointes des opérations de gestion de portées. Cette structure est indépendante des types des clefs et des valeurs, elle est /générique/. Il est donc expressément demandé d'implémenter cette structure d'une façon générique, même si, en effet, votre programme utilisera exclusivement des clefs chaînes de caractères et des valeurs entières.

Sa signature est par conséquent :

class LOO_ENVIRONMENT[KEY->HASHABLE, VALUE]

feature

  -- Entrée dans une nouvelle portée, prête à
  -- masquer temporairement les variables précédentes.
  push is ...

  -- Sortie de la dernière portée.
  pop is ...

  insert (k: KEY, v: VALUE)
  -- k doit exister auparavant.
  set (k:KEY, v: VALUE)
  has (k: KEY) : BOOLEAN
  -- k doit exister dans l'environnement.
  get (k: KEY) : VALUE

end

Le rôle de l'environnement est compréhensible dans l'exemple ci-dessous :

let
  a := 1
in
  let
    a := 2
  in
    a
  end
  a
end

dont le résultat est 1 et non pas 2.

Vous pouvez (devriez) introduire une classe (non générique) pour le cas utilisé par votre propre programme :

class LOO_VARIABLES
  inherit LOO_ENVIRONMENT[STRING, INTEGER] end
end

Règles d'évaluation du projet

Les règles pour le rendu sont décrites dans IsoLoo. La date est le 16 février 12h.

Le contrat est (avec les coûts) :

• D: -2: Rendu correct, selon la norme (delivery)
• R: un fichier texte ou HTML est livré, et décrit (README) :
  • RC: -1: comment compiler votre application
  • RR: -1: comment la faire fonctionner (run)
  • RD: -2: quels sont les grands axes de votre modélisation (design)
  • RH: -2: votre hiérarchie (UML est bien sûr le bienvenu)
• H: -2 la hiérarchie est correcte (utilisation judicieuse de classes abstraites etc.)
• G: -2: l'environnement est implémenté de façon générique
• T: -2: il y a au moins 10 tests (5 ok; 5 ko) réellement différents
• Y: +4: vous avez implémenté type, l'optionnel contrôle de types
• C: -4: les contrats Eiffel sont largement utilisés (préconditions etc.) et il n'est jamais possible de faire échouer votre programme d'une façon inattendue.
• Q: le code doit être de bonne qualité :
  • QR: -1: lisible et compréhensible (readable)
  • GM: -1: pas de méthodes monstres
  • QC: -1: des commentaires bien placés
  • QD: -2: pas de duplication de code
  • QE: -2: pas d'erreur d'encapsulation (les détails d'implémentation d'une classe ne regarde pas les autres)

La qualité des commentaires et des contrats sera en particulier évaluée grâce à l'outil short.

to top