Samuel Hocevar École Centrale - option SEM 11 novembre 2001 Rapport de TP compilateur =========================== 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 triviaux à 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. Plan ==== 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 3 - le parser (analyseur syntaxique) 3.1 - écriture d'un parser à partir de la grammaire 3.2 - exemples 4 - optimisations de l'arbre syntaxique 5 - génération de code 6 - optimisations peep-hole =============================================================================== 1 - la grammaire ================ Les fonctions présentées dans cette partie sont contenues dans le fichier "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 : ::= | [ ] Je la transforme donc en les deux règles suivantes (ø représentant le mot vide) : ::= ::= [ ] | ø 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) : ::= A | B { C } | ø 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 "grammar-tp.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 "automaton.scm" et "lexer.scm". 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 de la grammaire. On exploitera les fonctions get-grammar-metanames et get-grammar-lexems citées précédemment afin de créer la fonction make-nondeterministic-automaton. La première étape consiste à créer deux cellules de l'automate par métanom, l'une s'appelant "debut_metanom" et l'autre "fin_metanom", et on note "fin_metanom" comme étant un état final. On rajoute de plus des transitions en boucle sur les caractères espace, tabulation et retour à la ligne : "debut_metanom" _ "debut_metanom" "fin_metanom" _ "fin_metanom" La deuxième étape consiste à créer N+1 cellules dans l'automate par 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 que les transitions en boucle sur les caractères d'espacement. Dans notre exemple toujours : "lexem-FOO-" _ "lexem-FOO-" "lexem-FOO-" F "lexem-FOO-F" "lexem-FOO-F" O "lexem-FOO-FO" "lexem-FOO-FO" O "lexem-FOO-FOO" "lexem-FOO-FOO" _ "lexem-FOO-FOO" La troisième et dernière étape est la plus complexe, et consiste à créer des zéro-transitions à partir des règles d'adjacence que l'on pourra déceler dans la grammaire. Je ne m'étendrai pas trop sur le sujet. Le seul point délicat étant les répétitions, que l'on règle sans problème par explosion combinatoire en remplaçant une règle contenant une boucle par deux (ou plus) règles n'en contenant pas. Par exemple : ::= { } Sera analysé comme deux productions : ::= ::= Le reste est relativement trivial, par exemple la production : ::= WOK Conduira aux zéro-transitions suivantes : "debut_foo" ø "debut_bar" "fin_bar" ø "lexem-WOK-" "lexem-WOK-" ø "debut_quux" "fin_quux" ø "fin_foo" Je ne l'ai pas démontré, et ça nécessiterait sans doute beaucoup de temps, mais l'automate résultant reconnait sans problème un fichier écrit dans le langage défini par la grammaire. 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 un 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 TP : - automate non-déterministe: 132 cellules, 543 transitions, 60 états finaux - automate déterminisisé: 33 cellules, 293 transitions, 31 é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 le nombre de zéro-transitions). 2.3 - écriture du lexer à partir de l'automate déterministe ----------------------------------------------------------- (todo) =============================================================================== 3 - le parser (analyseur syntaxique) ==================================== Le code présenté dans cette partie se trouve dans le fichier "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. Voici comment l'on construit les parsers: ::= "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 parse-foo (lambda (s0) (if (reco s0 '("X" "Y" "Z")) (cons (list 'foo (cadr s0)) (cddr s0)) (error s0 "foo")))) ::= "wok" ---------------------------- (define parse-foo (lambda (s0) (let ((s1 (parse-foo s0))) (if (car s1) (if (reco s1 '("wok")) (let ((s2 (parse-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"))))) ::= | "X" ------------------------------------ (define parse-foo (lambda (s0) (cond ((reco s0 tete-bar) (let ((s1 (parse-bar s0))) (if (car s1) (cons (list 'foo (car s1)) (cdr s1)) (error s0 "bar")))) ((reco s0 '("X")) (let ((s1 (parse-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"))))) sans \tab et \newline: Stats: 132 states, 304 transitions, 60 end cells Stats: 59 states, 1116 transitions, 48 end cells