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%