about me

projects

MPEG & DVD

doc

leisure

Samuel Hocevar
École Centrale - option SEM
11 novembre 2001


                      Rapport de BE compilateur
             ============================================
              DTC - deterministic transformable compiler



0 - introduction
================

   J'ai choisi le langage Scheme pour réaliser ce compilateur parce que
les structures de données telles que les listes et les arbres existent à
la base dans le langage, et des opérations telles que le rééquilibrage
d'arbres ou le retournement de listes sont triviales à implémenter.

   De plus, puisque la technique à employer est la descente récursive,
un langage fonctionnel me paraissait tout à fait adapté pour implémenter
des récursions.


   Ce document est en ligne à l'adresse http://sam.zoy.org/software/dtc
où une version plus récente se trouvera éventuellement si j'ai eu un peu
de temps pour travailler dessus.


  0 - introduction

  1 - la grammaire
   1.1 - correction de la grammaire
   1.2 - choix d'une représentation générique en Scheme
   1.3 - l'exemple de notre grammaire
   1.4 - écriture d'outils travaillant sur la grammaire

  2 - le lexer (analyseur lexical)
   2.1 - écriture d'un automate non-déterministe à partir de la grammaire
   2.2 - déterminisation de l'automate
   2.3 - écriture du lexer à partir de l'automate déterministe
   2.4 - exemple de code lexé

  3 - le parser (analyseur syntaxique)
   3.1 - écriture d'un parser à partir de la grammaire
   3.2 - exemples de fonction de parsage
   3.3 - exemple de code parsé

  4 - optimisations de l'arbre syntaxique
   4.1 - simplification de l'arbre
   4.2 - exemple d'arbre simplifié
   4.3 - optimisation de l'arbre
   4.4 - exemple d'arbre optimisé

  5 - génération de code
   5.1 - principe
   5.2 - optimisations durant la compilation
   5.3 - optimisations peep-hole
   5.4 - exemple de code généré

  6 - essais réalisés pour le BE
   6.1 - essais sur du code invalide
   6.2 - exemple de l'énoncé
   6.3 - exercices
   6.4 - performances

  7 - conclusion
   7.1 - intéret de DTC
   7.2 - exemple d'extension de DTC

===============================================================================


1 - la grammaire
================

   Les fonctions présentées dans cette partie sont contenues dans le
fichier "include/grammar.scm".


1.1 - correction de la grammaire
--------------------------------

   Il apparait tout de suite que l'on ne pourra pas directement générer
un parser en descente récursive à partir de la grammaire, à cause de la
production suivante dont les ensembles de têtes des règles ne sont pas
disjoints :

   <var> ::= <ident> | <ident> [ <indices> ]

   Je la transforme donc en les deux règles suivantes (ø représentant le
mot vide) :

   <var>   ::= <ident> <index>
   <index> ::= [ <indices> ] | ø


   Après cette modification, la grammaire ne pose plus aucun problème
pour la réalisation de l'analyseur syntaxique en descente récursive.


1.2 - choix d'une représentation générique en Scheme
----------------------------------------------------

   Une grammaire est un ensemble de productions, il m'a donc paru normal
de représenter une grammaire par une liste de productions :

(define grammar (list production1 production2 ... productionX))

   Une production est un ensemble de règles associées à un métanom, j'ai
donc choisi une représentation en liste dont le premier élément est un
métanom et le reste une liste de règles :

(define production (cons 'metaname (list rule1 rule2 ... ruleX)))

   Une règle est une liste d'items pouvant être des métanoms, des
lexèmes ou des répétitions d'autres règles. La règle composée du mot
vide est tout simplement la liste vide :

(define rule (list item1 item2 ... itemX))

   On représente un métanom par un objet Scheme de type symbole et un
lexème par un objet de type string.

   Reste le problème des répétitions. J'ai choisi de les représenter un
peu comme les productions, mais en remplaçant le métanom par le type de
répétition (* pour n>=1 et + pour n>=0), ce qui laisse la possibilité
d'étendre le système ultérieurement :

(define repeat (cons 'type (list rule1 rule2 ... ruleX)))

   Par exemple la production suivante (ø représentant le mot vide) :

<foo> ::= A <bar> | B <quux> { C <wok> } | ø

   Sera traduite ainsi :

(define production
  '(foo
     ("A" bar)
     ("B" quux (* ("C" wok)))
     ()))


1.3 - représentation de notre grammaire
---------------------------------------

   Notre grammaire a la représentation suivante (elle est aussi dans le
fichier "lang/be/language.scm" puisque le compilateur l'utilise) :

(define *grammar*
  '((prog        (inst_affect (* (";" inst_affect)) $))
    (inst_affect (var ":=" expr))
    (var         (ident index))
    (index       ("[" indices "]")
                 ())
    (ident       ("a") ("b") ("c") ("d") ("e") ("f") ("g") ("h") ("i")
                 ("j") ("k") ("l") ("m") ("n") ("o") ("p") ("q") ("r")
                 ("s") ("t") ("u") ("v") ("w") ("x") ("y") ("z"))
    (indices     (expr (* ("," expr))))
    (expr        (expr_simple)
                 ("SI" expr oper_comp expr "ALORS" expr "SINON" expr))
    (oper_comp   ("#") ("=") ("<") (">") ("<=") (">="))
    (expr_simple (tete_expr (* (oper_add terme))))
    (tete_expr   (terme)
                 ("+" terme)
                 ("-" terme))
    (oper_add    ("+") ("-"))
    (terme       (fact (* (oper_mul fact))))
    (oper_mul    ("*") ("/"))
    (fact        ("(" expr ")")
                 (var))))


1.4 - écriture d'outils travaillant sur la grammaire
----------------------------------------------------

 get-grammar-metanames
 - - - - - - - - - - -

   Cette fonction renvoie la liste des métanoms définis dans la
grammaire, qui sera utilisée par le générateur d'automate fini.

(get-grammar-metanames *grammar*)
 ==> (prog inst_affect var index ident indices expr oper_comp expr_simple
      tete_expr oper_add terme oper_mul fact)


 get-grammar-lexems
 - - - - - - - - - -

   Cette fonction renvoie la liste des lexèmes intervenant dans la
grammaire, qui sera utilisée par le générateur d'automate fini.

(get-grammar-lexems *grammar*)
 ==> (";" ":=" "[" "]" "a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m"
      "n" "o" "p" "q" "r" "s" "t" "u" "v" "w" "x" "y" "z" "," "SI" "ALORS"
      "SINON" "#" "=" "<" ">" "<=" ">=" "+" "-" "*" "/" "(" ")")


 get-symbol-tete
 - - - - - - - -

   Cette fonction renvoie l'ensemble de tête d'une production donnée,
qui sera utilisée par le générateur de parser.

(get-symbol-tete 'oper_comp *grammar*)
 ==> ("#" "=" "<" ">" "<=" ">=")

(get-symbol-tete 'fact *grammar*)
 ==> ("(" "a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o" "p" "q"
     "r" "s" "t" "u" "v" "w" "x" "y" "z")


===============================================================================


2 - le lexer (analyseur lexical)
================================

   Les fichiers contenant le code présenté dans cette partie sont
"include/automaton.scm" et "include/lexer.scm".

   Il est clair que je me suis volontairement compliqué la vie pour la
génération du lexer, vue la simplicité du langage, mais le travail de
déterminisation d'automate m'intéressait.


2.1 - écriture d'un automate non-déterministe à partir de la grammaire
----------------------------------------------------------------------

   L'écriture de cet automate n'est pas excessivement complexe et repose
sur une simple étude des lexèmes de la grammaire. On exploitera la
fonction get-grammar-lexems vue précédemment afin de créer la fonction
make-nondeterministic-automaton.


   La première étape consiste à créer deux cellules de l'automate, l'une
s'appelant "start" et l'autre "end", la première étant l'état initial et
la deuxième étant un état final. On rajoute de plus des transitions sur
les caractères espace, tabulation et retour à la ligne allant de "start"
à "end".

   La deuxième étape consiste à créer N+1 cellules dans l'automate pour
chaque lexème, où N est la longueur du lexème, et on note la N+1e comme
étant un état final. On aura par exemple pour le lexème "FOO", les
cellules suivants :

    "lexem-FOO-", "lexem-FOO-F", "lexem-FOO-FO" et "lexem-FOO-FOO"

   Puis on ajoute les transitions évidentes sur les cellules des
lexèmes, ainsi qu'une zéro-transition provenant de la cellule de départ,
et j'en profite pour rajouter "lexem-FOO-FOO" à la liste des états
finaux.

            "start" ø "lexem-FOO-"
       "lexem-FOO-" F "lexem-FOO-F"
      "lexem-FOO-F" O "lexem-FOO-FO"
     "lexem-FOO-FO" O "lexem-FOO-FOO"


2.2 - déterminisation de l'automate
-----------------------------------

   Cette partie est plutôt délicate à gérer si on ne veut pas trop
perdre en performances. La déterminisation d'un automate à n cellules
et p transitions requiert dans le cas général beaucoup de mémoire
puisque l'automate résultant peut avoir jusqu'à 2^n cellules et p*2^n
transitions, et la complexité globale de l'algorithme est en n! si mes
souvenirs sont bons.

   Je ferai un petit abus de langage en parlant d'automate déterministe
car il ne l'est pas vraiment, en effet je ne crée pas de cellule
"poubelle" pour envoyer toutes les transitions ne correspondant à aucune
transition de l'automate originel, pour économiser un peu de mémoire.


   Je vais déterminiser l'automate de proche en proche. Cette technique
est particulièrement adaptée à notre problème car on a en fait très peu
de transitions (la plupart sont des zéro-transitions).

   La méthode est simple : on part d'un automate vide, on lui ajoute une
cellule de départ (qui est l'extension de l'ensemble des cellules de
départ de l'automate original), et pour chaque mot de l'alphabet reconnu
par le premier automate, si elle correspond à une transition possible
dans le nouvel automate, on rajoute cette transition dans l'automate,
et si la nouvelle cellule n'y était pas encore, on la rajoute aussi
et on reparcourt tout l'alphabet pour cette nouvelle cellule avant de
continuer la cellule en cours.


   Ci-après une explication plus complète de l'algorithme, que j'ai
surtout placée ici à titre personnel pour me souvenir du code si un jour
je décide d'y toucher à nouveau.

  - On écrit metacell-extension, qui à partir d'une liste de cellules du
    premier automate renvoie la liste des cellules directement accessibles via
    une zéro-transition à partir de l'une des cellules de la liste. Cette
    fonction sera utilisée pour trouver la cellule de départ de l'automate
    déterminisé.

  - On écrit metacell-target, qui à partir d'une liste de cellules du premier
    automate et d'un caractère renvoie la liste des cellules directement
    accessibles via la lecture du caractère. Il est nécessaire de le combiner
    à gauche et/ou à droite avec metacell-extension pour avoir les cellules
    accessibles en tenant compte des zéro-transitions.

  - On part avec les variables suivantes :
     · xda, automate vide ;
     · mc, (metacell-extension start) où start est l'ensemble des cellules de
       départ de l'automate non-déterministe ;
     · alph, l'alphabet reconnu par l'automate non-déterministe.

    * récursion, profondeur 1 :

    - On ajoute mc à xda, on appelle la récursion de profondeur 2.

      * récursion, profondeur 2 :

      - Si alph est vide, on renvoie xda.
      - On calcule newmc, (metacell-extension (metacell-target mc (car alph))),
        pour savoir s'il y aura une transition valide partant de mc dans
        l'automate déterminisé portant la lettre (car alph).
      - Si newmc est vide, on recommence la récursion de profondeur 2 avec
        alph valant cette fois (cdr alph).
      - Si newmc n'est pas vide, on rajoute la transition (mc (car alph) newmc)
        à l'automate xda car on est sûr qu'elle n'existait pas avant.
      - On regarde si newmc est une cellule connue de xda.
      - Si newmc était déjà une cellule de xda, pas la peine de rechercher ses
        suivants, ce sera fait par une autre branche de la récursion, on
        continue donc la récursion de profondeur 2 avec alph valant cette
        fois (cdr alph).
      - Si newmc n'est pas une cellule de xda, on appelle la récursion de
        profondeur 1 avec mc valant newmc et alph valant de nouveau
        l'alphabet total, histoire d'ajouter newmc et toutes les transitions
        partant de newmc, et on continue la récursion de profondeur 2 avec
        le nouveau xda ainsi créé et alph valant (cdr alph).


   Quelques chiffres au sujet de l'automate créé avec la grammaire de
notre BE :

  - automate non-déterministe: 106 cellules, 107 transitions, 47 états finaux
  - automate déterminisisé: 56 cellules, 55 transitions, 47 états finaux

   On constate que la déterminisation n'augmente pas dramatiquement la
taille de l'automate, et même qu'elle a tendance à le réduire (ce qui
est compréhensible vu la simplicité du langage reconnu).


2.3 - écriture du lexer à partir de l'automate déterministe
-----------------------------------------------------------

   Mon but était de générer un lexer à partir de l'automate (tant
qu'à faire de la programmation fonctionnelle, autant pousser le vice
jusqu'au bout), mais je n'ai pas eu le temps de le faire, je me suis
donc contenté d'écrire un lexer qui interprète l'automate. On perd un
peu en performances, mais celles-ci restent largement honorables. Le
lexer se trouve dans "include/lexer.scm".


2.4 - exemple de code lexé
--------------------------

   À partir du fichier contenant le code suivant :

    a := b +  c* d

   Le lexer renvoie la liste de lexèmes suivante :

    ("a" ":=" "b" "+" "c" "*" "d")


===============================================================================


3 - le parser (analyseur syntaxique)
====================================

   Le code présenté dans cette partie se trouve dans le fichier
"include/parser.scm".


3.1 - écriture d'un parser à partir de la grammaire
---------------------------------------------------

   Un parser prend pour argument une paire (X . Y), X est ignoré, et Y
contient le source à parser. La valeur de retour est une paire (X . Y)
avec X l'objet que l'on a demandé à parser, et Y le source restant à
parser. En cas d'erreur, X est mis à #f.

   On va donc construire un parser élémentaire pour chaque métanom de la
grammaire, qui vont récursivement s'appeler l'un l'autre, et retourner
les productions qu'ils ont reconnues.


   C'est ici que la puissance de Scheme est remarquable : le procédé de
récursion fait que les données résultantes seront agencées en arbre,
sans qu'il y ait à passer par une structure de données intermédiaire ou
à créer de lourdes macros de gestion d'arbre.


3.2 - exemples de fonction de parsage
-------------------------------------

   Voici quelques exemples de parsers élémentaires, les fonctions rs_**
demandées dans l'énoncé. Ce ne sont que des exemples très simples, le
code autogénéré par DTC est beaucoup plus gros.

   Ils exploitent la fonction reco qui reconnait un caractère dans le
source, ainsi que la fonction chop qui supprime le caractère courant du
source, toutes deux définies dans "parser.scm".


<foo> ::= X | Y | Z
- - - - - - - - - -

   Ces productions ne contiennent que des règles contenant un terminal,
on renvoie donc un parser très simple qui se contente de vérifier si le
premier lexème du source se trouve dans la liste des terminaux.

(define rs_foo (lambda (s0)
  (if (reco s0 '("X" "Y" "Z"))
    (cons (list 'foo (cadr s0)) (cddr s0))
    (error s0 "foo"))))


<foo> ::= <bar> wok <quux>
- - - - - - - - - - - - - -

(define rs_foo (lambda (s0)
  (let ((s1 (rs_foo s0)))
    (if (car s1)
      (if (reco s1 '("wok"))
        (let ((s2 (rs_quux (chop s1))))
          (if (car s2)
            (cons (list 'foo (car s1) "wok" (car s2)) (cdr s2))
            (error (chop s1) "quux")))
        (error s1 "wok"))
      (error s0 "bar")))))


<foo> ::= <bar> | X <quux>
- - - - - - - - - - - - - -

(define rs_foo (lambda (s0)
  (cond
    ((reco s0 tete-bar)
     (let ((s1 (rs_bar s0)))
       (if (car s1)
         (cons (list 'foo (car s1)) (cdr s1))
         (error s0 "bar"))))
    ((reco s0 '("X"))
     (let ((s1 (rs_quux (chop s0))))
       (if (car s1)
         (cons (list 'foo "X" (car (chop s0))) (cdr (chop s0)))
         (error (chop s0) "X quux"))))
    (else
     (error s0 "foo")))))


3.3 - exemple de code parsé
---------------------------

   Toujours en prenant l'exemple de 2.4, le fichier contenant :

    a := b +  c* d

   L'arbre syntaxique généré par le parser est le suivant :

    (prog
      (inst_affect
         (var (ident "a") (index))
         ":="
         (expr
           (expr_simple
             (tete_expr
               (terme
                 (fact
                   (var
                     (ident "b")
                     (index)))
                 ()))
             ((oper_add "+")
              (terme
                (fact
                  (var
                  (ident "d")
                  (index)))
                ((oper_mul "*")
                 (fact
                   (var
                     (ident "c")
                     (index)))))))))
      ()
      $)


===============================================================================


4 - optimisations de l'arbre syntaxique
=======================================

   C'est à partir de ce moment que le code devient spécifique au langage
et où on ne peut plus se limiter à l'étude de la grammaire pour traiter
les données.


4.1 - simplification de l'arbre
-------------------------------

   On a remarqué dans 3.3 que l'arbre généré était très riche, ce qui
est à la fois intéressant et ennuyeux. Par exemple la valeur de la
variable 'a' apparaissant dans une addition sera représentée de la façon
suivante :

    (terme
      (fact
        (var
          (ident "a")
          (index)))
      ())))))

   Il serait tout de même plus efficace de remplacer cette structure
simplement par :

    (var "a")

   Nous allons donc descendre l'arbre récursivement pour transformer
tout ce qu'il est possible de simplifier sans perdre trop d'information,
on crée donc la fonction simplify-tree qui va agir sur un arbre
syntaxique et renvoyer un nouvel arbre plus simple. Les fonctions
réalisant ce travail se trouvent dans le fichier "lang/be/optim.scm".


4.2 - exemple d'arbre simplifié
-------------------------------

   Toujours d'après l'exemple vu en 2.4 et en 3.3, l'arbre simplifié est
le suivant :

    (prog
      (var_affect
        (var "a")
        (+
          (var "b")
          (*
            (var "c")
            (var "d")))))


4.3 - optimisation de l'arbre
-----------------------------

   Toujours dans le fichier "lang/be/optim.scm", on écrit la fonction
optimize-tree qui s'occupe de faire certaines opérations élémentaires
d'optimisation sur l'arbre simplifié.

   L'optimisation la plus évidente est l'inversion de deux branches d'un
arbre lorsque l'on a affaire à un opérateur binaire commutatif, afin
de faire apparaitre des feuilles du côté droit de l'arbre. C'est en
fait la seule optimisation de ce type que je fais pour le moment, car
le rééquilibrage profond de l'arbre est assez complexe et je n'ai pas
encore trouvé de méthode très efficace.


   Les autres optimisations que je fais sont les suivantes :

    -(X-Y) ==> (Y-X)
    -(-X)  ==> X
    -X+Y   ==> Y-X
    X+(-Y) ==> X-Y
    -X-Y   ==> -(X+Y)
    X-(-Y) ==> X+Y


4.2 - exemple d'arbre optimisé
------------------------------

   Toujours d'après le même exemple, on a l'arbre optimisé suivant :

    (prog
      (var_affect
        (var "a")
        (+
          (*
            (var "d")
            (var "c"))
          (var "b"))))


===============================================================================


5 - génération de code
======================


5.1 - principe
--------------

   Avec l'arbre syntaxique simplifié et la puissance de parcours d'arbre
qu'on peut implémenter simplement en Scheme, la génération de code est
presque une formalité.

   On crée donc la fonction generate-pseudocode qui générera le
code source en langage de pseudo-assemblage (afin de permettre les
optimisations peep-hole ultérieures). On crée ensuite la fonction
récursive format-pseudocode qui se charge d'aplatir la liste
d'instructions et d'en faire une chaîne de caractères. On écrit aussi
une version output-pseudocode qui réalise la même chose mais écrit dans
la sortie standard plutôt que de créer une chaîne de caractères.

   Les fonctions de génération de code se trouvent dans "lang/be/codegen.scm".


5.2 - optimisations durant la compilation
-----------------------------------------


Gestion des garages temporaires
- - - - - - - - - - - - - - - -

   Elle se fait trivialement avec un indice de garage temporaire, que
l'on incrémente durant l'utilisation de la variable en question, et dont
la valeur est donc passée récursivement à chaque sous-branche. On est
donc sûr qu'en sortant d'une branche le compteur de garages aura la même
valeur qu'en y entrant.


Opérations binaires
- - - - - - - - - -

   Il est possible d'optimiser à la compilation l'ordre dans lequel on
fait les calculs arithmétiques du type (op X Y) :

   - si Y est une variable, on calcule X dans l'accumulateur et la seule
   instruction supplémentaire est "op Y".

   - si Y est un tableau, on calcule son adresse, on la stocke dans un
   garage temporaire (comme w0), puis on calcule X dans l'accumulateur
   et enfin on fait "op @w0".

   - si Y est une expression complexe, on la calcule, on stocke son
   résultat dans un garage temporaire (comme w0), puis on calcule X dans
   l'accumulateur et enfin on fait "op w0".

   Le compilateur ne fera pas le travail d'inversion, car ce n'est pas
son rôle. Il convient à l'optimiseur d'arbre de s'arranger pour que Y
soit le plus souvent une variable.


5.3 - optimisations peep-hole
-----------------------------

   Je n'ai rien fait à ce sujet, car je n'ai pas trouvé dans les
exemples de cas où l'allocation de registres devenait inefficace, mais
si vous trouvez un exemple où le compilateur est pris à défaut, je suis
prêt à y travailler.


5.4 - exemple de code généré
----------------------------

   Toujours d'après l'exemple vu en 2.4, 3.3, 4.2 et 4.4, le code généré
pour l'expression a:=b+c*d est le suivant :

        LDA d
        MUL c
        ADD b
        STA a

   On obtient quelque chose d'extrêmement simple, ce qui est plutôt
rassurant, et me permettra d'aller me coucher l'esprit serein.


===============================================================================


6 - essais réalisés pour le BE
==============================

   L'exécutable du compilateur s'appelle "dtc". Il prend comme argument
le nom du fichier à compiler, et choisit l'entrée standard si aucun
fichier n'est spécifié. Un argument obligatoire est "-l <lang>" pour
spécifier le langage à utiliser (le langage du BE est "be"). Un argument
optionnel est "-v" si l'on veut plus d'information sur la compilation,
que l'on peut même spécifier une deuxième fois.

   J'ai mis #!/usr/bin/scm en tête de fichier car c'est mon interpréteur
Scheme préféré, mais par exemple /usr/bin/guile fonctionnerait tout
autant, bien que celui-ci soit légèrement plus lent.

   On peut donc lancer dtc de différentes manières :

     ./dtc -l be
     scm dtc -l be
     guile -s dtc -l be

6.1 - essais sur du code invalide
---------------------------------

   On se propose de voir le comportement de DTC lorsqu'il est mis en
présence d'un code invalide. Par exemple, une erreur comme l'utilisation
du caractère « ^ » :

    a := d + c ^ g

   Donne ce comportement de DTC :

~/dtc% echo "a := d + c ^ g" | ./dtc -v -l be
dtc: This is DTC v0.2, the deterministic transformable compiler
dtc: Copyright 2001 Samuel Hocevar <sam@zoy.org>
dtc: This is free software with ABSOLUTELY NO WARRANTY
dtc: loading language processor from "lang/be/language.scm"
dtc: creating non-deterministic automaton
dtc: determinizing automaton
dtc: simplifying automaton
dtc: lexing file "/dev/stdin"
dtc error: lexer stuck before « ^ »
dtc fatal error: lexer barfed
~/dtc%

   On remarque que l'erreur est assez pauvre en renseignements. Je vais
voir ce que je peux faire pour améliorer la détection d'erreur à ce
niveau.


   Par contre, si l'erreur n'est pas décelable directement par le lexer,
par exemple une parenthèse mal placée :

    a := b + (c *) d

   On obtient l'erreur suivante, un peu plus précise :

~/dtc% echo "a := b + (c *) d" | ./dtc -v -l be
dtc: This is DTC v0.2, the deterministic transformable compiler
dtc: Copyright 2001 Samuel Hocevar <sam@zoy.org>
dtc: This is free software with ABSOLUTELY NO WARRANTY
dtc: loading language processor from "lang/be/language.scm"
dtc: creating non-deterministic automaton
dtc: determinizing automaton
dtc: simplifying automaton
dtc: lexing file "/dev/stdin"
dtc: creating parser
dtc: parsing lexems
dtc error: parser stuck before « ) d EOF », expecting « <fact> »
dtc error: parser stuck before « ) d EOF », expecting « <fact> »
dtc error: parser stuck before « d EOF », expecting « EOF »
dtc error: parser stuck before « d EOF », expecting « <$> »
dtc fatal error: parser barfed
~/dtc%


6.2 - exemple de l'énoncé
-------------------------

   Pour le source donné en exemple dans l'énoncé, à savoir :

    c[y*(SI b>-a ALORS d SINON e-x-y), f, g[h]]:=i/(j*(k-g[-m]))

   DTC renvoie la sortie suivante :

~/dtc% ./dtc -v -l be doc/examples/example.be
dtc: This is DTC v0.2, the deterministic transformable compiler
dtc: Copyright 2001 Samuel Hocevar <sam@zoy.org>
dtc: This is free software with ABSOLUTELY NO WARRANTY
dtc: loading language processor from "lang/be/language.scm"
dtc: creating non-deterministic automaton
dtc: determinizing automaton
dtc: simplifying automaton
dtc: lexing file "/dev/stdin"
dtc: creating parser
dtc: parsing lexems
dtc: simplifying code tree
dtc: optimizing code tree
dtc: generating pseudocode
dtc: formating code
        LDA a
        NEG
        CMP b
        BGE $0
        LDA d
        BRA $1
$0:
        LDA e
        SUB x
        SUB y
$1:
        MUL y
        STA w0
        PSH w0
        PSH f
        PSH h
        PEA g
        PSH #1
        JSR ADELEM
        STA w0
        PSH @w0
        PEA c
        PSH #3
        JSR ADELEM
        STA w0
        LDA m
        NEG
        STA w1
        PSH w1
        PEA g
        PSH #1
        JSR ADELEM
        STA w1
        LDA k
        SUB @w1
        MUL j
        STA w1
        LDA i
        DIV w1
        STA @w0

dtc: successful
~/dtc%


   Il s'agit exactement du code donné en exemple, je pense donc que le
compilateur n'est pas trop mauvais.


6.3 - exercices
---------------

   Voici pour chacun des exercices le code généré :


    a := (b-d+e)*((-f+h)/(-(m-n))); a :=SI a<d ALORS g[a] SINON d*a

        LDA n
        SUB m
        STA w0
        LDA h
        SUB f
        DIV w0
        STA w0
        LDA b
        SUB d
        ADD e
        MUL w0
        STA a

        LDA d
        CMP a
        BLE $0
        PSH a
        PEA g
        PSH #1
        JSR ADELEM
        STA w0
        LDA @w0
        BRA $1
$0:
        LDA a
        MUL d
$1:
        STA a

   Ici le compilateur n'a pas vu qu'on pouvait remplacer "LDA a MUL d" à
la fin par "MUL a" puisque d était déjà dans l'accumulateur. Je ne vois
guère qu'une méthode peephole pour déceler ce genre de subtilités, mais
c'est une optimisation plutôt complexe à trouver à mon avis.


    c[p + (SI b > -a ALORS d SINON e)+x, f, g[h]]:=i/(j*(j-g[-m]))

        LDA a
        NEG
        CMP b
        BGE $0
        LDA d
        BRA $1
$0:
        LDA e
$1:
        ADD p
        ADD x
        STA w0
        PSH w0
        PSH f
        PSH h
        PEA g
        PSH #1
        JSR ADELEM
        STA w0
        PSH @w0
        PEA c
        PSH #3
        JSR ADELEM
        STA w0
        LDA m
        NEG
        STA w1
        PSH w1
        PEA g
        PSH #1
        JSR ADELEM
        STA w1
        LDA j
        SUB @w1
        MUL j
        STA w1
        LDA i
        DIV w1
        STA @w0

   Ici à première vue le code est parfait. Je ne vois pas trop comment
l'on pourrait l'améliorer, mais je n'ai pas réfléchi à toutes les
méthodes d'optimisation.


   e:=a-(SI SI -k = l ALORS z SINON a> e ALORS a SINON SI f+e#-d-e-y
   ALORS -a+g[i/j/k] SINON d)-e

        LDA k
        NEG
        CMP l
        BEQ $0
        LDA z
        BRA $1
$0:
        LDA a
$1:
        CMP e
        BLE $2
        LDA a
        BRA $3
$2:
        LDA d
        ADD e
        NEG
        SUB y
        STA w0
        LDA e
        ADD f
        CMP w0
        BNE $4
        LDA i
        DIV j
        DIV k
        STA w0
        PSH w0
        PEA g
        PSH #1
        JSR ADELEM
        STA w0
        LDA @w0
        SUB a
        BRA $5
$4:
        LDA d
$5:
$3:
        STA w0
        LDA a
        SUB w0
        SUB e
        STA e

   Ici aussi, le code me semble convenable, sans opérations inutiles ni
gaspillage de garages temporaires.


6.4 - performances
------------------

   Les performances sont à mon avis raisonnables, compte tenu que
l'automate fini et le parser sont recalculés à chaque fois alors que
dans un compilateur en production on les stockerait plutôt dans des
fichiers.

   Sur mon ordinateur, un PIII à 600MHz sous GNU/Linux, avec l'inter-
préteur Scheme scm (http://www-swiss.ai.mit.edu/~jaffer/SCM.html), les
temps de compilation sont les suivants :

    - 60 caractères :      0.71s (40 lignes d'assembleur)
    - 1000 caractères :    0.78s (500 lignes d'assembleur)
    - 7000 caractères :    1.28s (3600 lignes d'assembleur)
    - 35000 caractères :   4.28s (18000 lignes d'assembleur)
    - 100000 caractères : 12.53s (58000 lignes d'assembleur)

   Le temps de compilation est donc globalement proportionnel à la
taille du fichier à compiler, bien que cela dépende un peu du contenu
exact des fichiers à compiler ; les arbres syntaxiques ne seront pas les
mêmes suivant le type de calcul à effectuer. La consommation mémoire
peut atteindre 18 Mo dans le cas d'un fichier de 100000 caractères.


   Guile (http://www.gnu.org/software/guile/guile.html), l'interpréteur
Scheme du projet GNU, est quant à lui à peu près deux fois plus lent,
mais sa consommation mémoire est légèrement plus faible.


   En comparaison, le compilateur gcc (version 0.2.96), sur la même
machine et pour un code en langage C de complexité équivalente, a les
performances suivantes avec le flag -S (pour ne générer que le code
assembleur) :

    - 7000 caractères :    0.41s (5000 lignes d'assembleur)
    - 35000 caractères :   2.05s (28000 lignes d'assembleur)
    - 100000 caractères :  6.56s (80000 lignes d'assembleur)

   Et avec le flag -O6 (optimisations les plus poussées) :

    - 7000 caractères :    1.38s (4000 lignes d'assembleur)
    - 35000 caractères :  11.12s (20000 lignes d'assembleur)
    - 100000 caractères : 76.79s (58000 lignes d'assembleur)

   On constate donc que même s'il effectue très peu d'optimisations, DTC
offre des performances honorables par rapport à un compilateur moyen. Je
pense qu'il est possible de gagner énormément en performances en rendant
le lexer autonome (ie, le générer à partir de l'automate, au lieu de lui
faire évaluer l'automate). En effet, à première vue 3/4 du temps de la
compilation est passé dans le lexer.


===============================================================================


7 - conclusion
==============


7.1 - intéret de DTC
--------------------

   L'intéret de DTC repose essentiellement dans sa modularité (il
est possible de n'en utiliser que le parser, ou d'utiliser un autre
optimiseur) et surtout dans sa relative indépendance de la grammaire, du
moins pour tout ce qui est analyse lexicale et syntaxique.

   Il est tout à fait possible de réaliser par exemple un interpréteur
d'expressions algébriques basé sur DTC, en remplaçant la phase de
simplification de l'arbre par une évaluation numérique de ses feuilles,
et c'est d'ailleurs l'exemple que nous allons voir en 7.2.


7.2 - exemple d'extension de DTC
--------------------------------

   Dans le répertoire "lang/calc" j'ai écrit le fichier "language.scm",
nécessaire pour compiler un simple langage de calcul numérique, dont la
grammaire est très fortement inspirée de celle du langage du BE :

    <expr>      ::=  <tete_expr> { <oper_add> <terme> }
    <tete_expr> ::=  <terme> | + <terme> | - <terme>
    <oper_add>  ::=  + | -
    <terme>     ::=  <fact> { <oper_mul> <fact> }
    <oper_mul>  ::=  * | /
    <fact>      ::=  ( <expr> ) | <number>
    <number>    ::=  <digit> { <digit> }
    <digit>     ::=  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   D'où la grammaire dans notre représentation Scheme :

(define *grammar*
  '((expr        (tete_expr (* (oper_add terme))))
    (tete_expr   (terme)
                 ("+" terme)
                 ("-" terme))
    (oper_add    ("+") ("-"))
    (terme       (fact (* (oper_mul fact))))
    (oper_mul    ("*") ("/"))
    (fact        ("(" expr ")")
                 (number))
    (number      (digit (* (digit))))
    (digit       ("0") ("1") ("2") ("3") ("4")
                 ("5") ("6") ("7") ("8") ("9"))))


   La subtilité ici est que l'on va utiliser l'interpréteur Scheme
lui-même pour effectuer le calcul. Ainsi le fichier suivant :

     3 * (-((((-( 11)))))) - 9 * 6 + (1000 + 3 * (-3 * (-5)))

   Va être transformé (après passage dans simplify-tree) en l'arbre :

     (+
       (-
         (*
           3
           (-
             (- 11)))
         (* 9 6))
       (+
         1000
         (*
           3
           (-
             (*
               3
               (- 5))))))

   Le lecteur connaissant Scheme reconnaîtra là une expression Scheme
évaluable. Ainsi la fonction d'optimisation de l'arbre simplifié pourra
être la fonction identité, "generate-pseudocode" sera la fonction "eval"
et "format-pseudocode" sera la fonction "number->string". On obtient
donc un évaluateur d'expressions arithmétiques :

~/dtc% echo '(12*12*12+12+12+12)/(3+4+5+6+7+8+9)' | ./dtc -l calc
42
~/dtc%