Cours de Compilation, Master 1, 2004-2005

Tanguy Risset

2 mars 2005

1

Table des matie`res

1 Generalites 41.1 Biblio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Quest ce quun compilateur ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Un exemple simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 front-end . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.2 Creation de lenvironnement dexecution . . . . . . . . . . . . . . . . . . . . 61.3.3 Ameliorer le code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.4 La generation de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 assembleur Iloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Grammaires et expressions regulie`res 92.1 Quelques definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 De lexpression regulie`re a` lautomate minimal . . . . . . . . . . . . . . . . . . . . . 11

2.2.1 Des expressions regulie`res aux automates non deterministes . . . . . . . . . 112.2.2 Determinisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.3 Minimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Implementation de lanalyseur lexical . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3.1 Analyseur lexical a` base de table . . . . . . . . . . . . . . . . . . . . . . . . . 152.3.2 Analyseur lexical code directement . . . . . . . . . . . . . . . . . . . . . . . 16

2.4 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Analyse syntaxique 173.1 Grammaires hors contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Analyse syntaxique descendante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.1 Exemple danalyse descendante . . . . . . . . . . . . . . . . . . . . . . . . . 213.2.2 Elimination de la recursion a` gauche . . . . . . . . . . . . . . . . . . . . . . . 223.2.3 Elimination du bactrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2.4 Parser descendant recursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Parsing ascendant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3.1 Detection des reductions candidates . . . . . . . . . . . . . . . . . . . . . . . 273.3.2 Construction des tables LR(1) . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.4 Quelques conseils pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.5 Resume sur lanalyse lexicale/syntaxique . . . . . . . . . . . . . . . . . . . . . . . . 32

4 Analyse sensible au contexte 334.1 Introduction aux syste`mes de type . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.1 Composant dun syste`me de typage . . . . . . . . . . . . . . . . . . . . . . . 334.2 Les grammaires a` attributs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.3 Traduction ad-hoc dirigee par la syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . 364.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5 Representations Intermediaires 385.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.2 IR lineaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2.1 code trois adresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.3 Static Single Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.4 Nommage des valeurs et mode`le memoire . . . . . . . . . . . . . . . . . . . . . . . 415.5 La table des symboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6 Procedures 446.1 Abstraction du controle et espace des noms . . . . . . . . . . . . . . . . . . . . . . . 446.2 Enregistrement dactivation (AR) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.3 Communication des valeurs entre procedures . . . . . . . . . . . . . . . . . . . . . . 476.4 Adressabilite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.5 Edition de lien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2

6.6 Gestion memoire globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

7 Implementations de mecanismes specifiques 577.1 Stockage des valeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577.2 Expressions booleennes et relationnelles . . . . . . . . . . . . . . . . . . . . . . . . . 577.3 Operations de controle de flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597.4 Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617.5 Chanes de caracte`res . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627.6 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

8 Implementation des langages objet 658.1 Espace des noms dans les langages objets . . . . . . . . . . . . . . . . . . . . . . . . 658.2 Generation de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

9 Generation de code : selection dinstructions 709.1 Selection dinstruction par parcours darbre (BURS) . . . . . . . . . . . . . . . . . . . 719.2 Selection dinstruction par fenetrage . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

10 Introduction a` loptimisation : elimination de redondances 8010.1 Elimination dexpressions redondantes avec un AST . . . . . . . . . . . . . . . . . . 8010.2 Valeurs numerotees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8210.3 Au dela` dun bloc de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

11 Analyse flot de donnees 8911.1 Exemple des variables vivantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8911.2 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9111.3 Autres proble`mes data-flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

12 Static Single Assignment 9512.1 Passage en SSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

13 Quelques transformations de code 9713.1 Elimination de code mort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9713.2 Strength reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

14 Ordonnancement dinstructions 10414.1 List scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10614.2 Ordonnancement par region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10714.3 Ordonnancement de boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

15 Allocation de registres 11015.1 Allocation de registres locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11015.2 Allocation globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

A Operation de lassembleur lineaire Iloc 117

B Assembleur, editeur de liens, lexemple du Mips 119B.1 Assembleur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120B.2 Edition de lien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121B.3 Chargement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122B.4 Organisation de la memoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122B.5 Conventions pour lappel de procedure . . . . . . . . . . . . . . . . . . . . . . . . . 123B.6 Exceptions et Interruptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124B.7 Input/Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126B.8 Quelques commandes utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

3

1 Generalites

Page web du cours :http://perso.ens-lyon.fr/tanguy.risset/cours/compil2004.html

1.1 Biblio

La construction dun compilateur rassemble une grande diversite de processus. Certains etantune application directe de resultats theoriques puissants (comme la generation automatique dana-lyseurs lexicaux qui utilise la theorie des langages reguliers). Dautres se rattachent a` des proble`mesdifficiles, NP-Complet (ordonnancement dinstruction, allocation de registres). Ce qui est proba-blement le plus delicat dans la construction dun compilateur cest quil faut trouver un equilibreentre un code produit efficace et un temps de production de code raisonnable.

Il est tre`s important de realiser que le fait de matriser les techniques de construction duncompilateur sont une des raisons qui rendent les informaticiens indispensables. Un biologistepeut savoir bien programmer, mais lorsquil aura a` faire des traductions entre differents formats,il va utiliser des methodes ad-hoc. Linformaticien peut apporter enormement a` une equipe parla matrise de cet outil tre`s puissant quest le compilateur.

Le but de ce cours est de faire assimiler les techniques de bases de compilation pour

1. pouvoir rapidement ecrire un compilateur : utiliser les techniques et outils ayant fait leurspreuves.

2. avoir assimiles les notions qui permettent de comprendre les proble`mes et les solutions dansles compilateurs modernes.

Ce cours a ete prepare a` partir du livre de Keith D. Cooper et Linda Torczon de Rice Univer-sity : Engineering a Compiler [CT03]. Il est aussi issu du cours de compilation fait par YvesRobert jusquen 2003. Parmi les ouvrages importants qui peuvent completer ce cours je recom-mande . Dautre part, une bonne connaissance de larchitecture des processeurs peut etre utilesi lon decide dapprofondir un peu la compilation. La reference la plus accessible est le livre deHennessy et Patterson [HP98]

References

[ASU88] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers : Principles, Techniques andTools. Addison-Wesley, 1988. La bible, un peu depasse sur certains sujets, mais beaucoupnont pas change depuis.

[CT03] Keith D. Cooper and Linda Torczon. Engineering a Compiler. Morgan-Kaufmann, 2003.Le livre utilise pour ce cours, en cours de commande a` lENS.

[Muc] Steven S. Muchnick. Compiler Design Implementation. Morgan-Kaufmann. Tre`s completpour approfondir les optimisations.

[wA98] Andrew w. Appel. Modern Compiler implementation in Java. Cambridge University press,1998. Certaines parties tre`s bien expliquees

[GBJL00] D. Grune, H. Bal, J. H. Jacobs, and K. Langendoen. Modern Compiler Design. John Wiley& Sons, 2000. Globalement un peu moins bien (sauf pour certains points precis).

[HP98] J. Hennessy, D. Patterson Computer Organization and Design : The hardware software inter-face Morgan Kaufman 1998. Reference pour la description des architectures Risc.

1.2 Quest ce quun compilateur ?

Definition 1 Un compilateur est un programme qui prend en entree un programme executable et produiten sortie un autre programme executable.

4

Le langage du programme source est appele langage source, celui du programme cible estappele langage cible. Exemple de langage sources : Fortran, C, Java etc... Le langage cible peutetre un de ces langages ou un assembleur ou un code machine pour une machine precise.

Beaucoup de compilateurs ont le langage C comme langage cible car il existe des compilateursC sur pratiquement toutes les plate-formes. Un programme qui gene`re du postcript a` partir dunformat donnee (ascii, latex, jpg, etc.) est aussi un compilateur. En revanche, un programme quitransforme du postcript en des pixel sur un ecran est un interpreteur.

rsultats

InterpreteurCompilateursource cible

programmeprogramme programme

source

Exemple de langage interprete : Perl, Scheme, Mathematica, mapple.Les principes fondamentaux de la compilation sont :

1. Le compilateur doit conserver le sens du programme compile2. Le compilateur doit ameliorer le codeles proprietes importantes dun compilateur sont : code produit efficace (rapidite, memoire). informations retournees en cas derreurs, debboging rapidite de la compilationDans les annees 80, les compilateurs etaient tous de gros syste`mes monolithiques generant du

code assembleur le plus rapide possible directement a` partir dun programme entier. Aujourdhuidautres fonctions de cout entrent en jeux pour juger de la qualite dun compilateur : la taille decode et la consommation electrique ont une importance primordiale pour les syste`mes embarques(pour les applications multimedia recentes, la taille de code est quasiment le crite`re numero 1).

Le processus de compilation peut aussi etre decompose : comme le bytecode java qui estun programme semi-compile. Lediteur de liens, reliant le programme compile avec les librai-ries precompilees quil utilise peut eventuellement faire des optimisations. Le programme peutmeme etre ameliore a` lexecution avant detre execute grace a` des informations supplementairespresentes a` lexecution.

1.3 Un exemple simple

Considerons lexpression suivante pour laquelle nous voulons generer du code executable :

w w 2 x y zOn decompose aujourdhui un compilateur en 3 passes (front-end, middle-end, back-end) bienquil y ait beaucoup plus de trois passes en pratique. En plus des actions de chaque passe, ilest important de definir precisement les representations intermediaires (intermediate representation,IR) utilisees ainsi que linfrastructure du compilateur pour manipuler ces representions. Unerepresentation intuitive est la suivante :

Table des symbols, Arbres de syntaxe abstraite, Graphes, ensembles, IR, ...

Sca

nnin

g

Par

sing

C.S

.A

FrontEnd

All

oc.

Reg

.

Opt2

Opt3

MiddleEnd

Opt1

Sel

ecti

on

Ord

onnan

cem

ent

BackEnd

Compilateur

Infrastructure

5

On appelle cela un compilateur optimisant (optimizing compiler) par opposition aux premiercompilateurs qui ne comprenaient que deux passes (front-end, back end).

1.3.1 front-end

La premie`re tache du compilateur est de comprendre lexpression du langage source. Cela sefait en plusieurs etapes :

1. Analyse syntaxique : permet de verifier que lexpression est bien une phrase du langagesource syntaxiquement correcte, on dit aussi quelle est bien formee. Cela necessite donc unedefinition formelle du langage source. Exemple en francais : Le lion mange de la viande estsyntaxiquement correcte et le lion viande nest pas syntaxiquement correcte. En pratique,lanalyse cette phase est divisee en deux traitements : lanalyse lexicale ou scanning (repererles cesures de mots, la ponctuation) et lanalyse syntaxique ou parsing (verifier les re`gles degrammaire pour lexemple du francais).

2. Analyse semantique : permet de verifier que lexpression a un sens dans le langage source(on peut dire aussi analyse sensible au contexte, context sensitive analysis, CSC en anglais).Cela necessite une semantique precise pour le langage source. Exemple en Francais : le liondort de la viande est syntaxiquement correcte (sujet, verbe, complement dobjet) mais na pasde sens defini. Ici, on peut etre amene a` se demander si les variables w, x, y et z ont etedeclarees, et si on leur a affecte des valeurs precedemment.

Ces traitements sont regroupe dans ce qui est appele le front-end du compilateur. Ces deux trai-tements sont largement automatises aujourdhui grace a` lapplication des resultats de la theoriedes langages. On dispose doutils permettant de generer les analyzeurs lexicauxs et syntaxiquesa` partir de la description du langage source sous forme de grammaire.

1.3.2 Creation de lenvironnement dexecution

Le langage source est generalement une abstraction permettant dexprimer un calcul dans unformalisme relativement intuitif pour letre humain. Par exemple, il contient des noms symbo-liques : x, y, z, w qui represente plus que des valeurs : des cases memoire qui peuvent prendreplusieurs valeurs successivement.

Le compilateur doit detruire cette abstraction, faire un choix pour implementer la structureet les actions designees et maintenir la coherence avec les actions qui suivent. Ici, par exemple lecompilateur peut choisir dallouer quatre cases memoire consecutives pour les quatre variablesw, x, y, z :

0 w x y z ,

ou il peut decider de conserver ces variables dans des registres par une serie daffection :

r1 w; r2 x; r3 y; r4 zDans tous les cas, le compilateur doit assurer la coherence de ces choix tout au long du processusde traduction.

En plus des noms le compilateur doit creer et maintenir des mecanismes pour les procedures,les parame`tres, les portees lexicales les operations de controle du flot. On appelle cela choisir laforme du code.

Ce point precis est assez important : cest parce que lon a etudie le processus de compilationvers une architecture cible dun type tre`s precis : type architecture de Von Neumann sequentielleavec un processeur programmable (muni de plusieurs unites) et une memoire (eventuellementhierarchisee) que lon a pu automatiser cette descente dans le niveau dabstraction. Aujourdhui,il nexiste toujours par de paralleliseur satisfaisant pour une machine paralle`le donnee (cestdailleurs une des raisons pour laquelle les constructeurs ne fabriquent quasiment plus de ma-chines paralle`les) car le raffinement efficace de labstraction pour ces architectures est beaucoupplus delicat (les communications posent un enorme proble`me de performance). De meme onne sait pas compiler efficacement un circuit integre a` partir dune specification de haut niveaucar pour beaucoup dabstraction faites par les langages de haut niveau les choix a` faire pour

6

limplementation sont tre`s difficiles. Par exemple lintroduction du temps a` partir dune specificationfonctionnelle (ordonnancement), la parallelisation etc.

1.3.3 Ameliorer le code

Le compilateur peut tre`s souvent tirer partie du contexte dans lequel se trouve une expressionpour optimiser son implementation. Par exemple, si lexpression a` compiler se trouve a` linterieurdune boucle dans laquelle la sous expression 2 x y est invariante, le compilateur aura intereta` introduire une variable temporaire pour sortir le calcul de cette expression de la boucle :

w

loadAI rarp, @w r1 // load wadd r1, r1 r1 // r1 w 2loadAI rarp, @x r2 // load xmult r1, r2 r1 // r1 (w2) xloadAI rarp, @y r2 // load ymult r1, r2 r1 // rw (w2) x yloadAI rarp, @z r2 // load zmult r1, r2 r1 // r1 (w2) x y zstoreAI r1 rarp, @w // ecriture de w

1.4 assembleur Iloc

Un compilateur est etroitement lie a` lassembleur quil va generer (au moins pour les phasesdu back-end). Il existe autant dassembleur que de type de processeurs, cependant on peut degagerdes principes communs. Pour illustrer le cours on utilisera le langage assembleur Iloc proposedans [CT03]. ILOC est un code lineaire assembleur pour une machine RISC. Cest une versionsimplifiee de la representation intermediare utilisee dans le MSCP (Massively Scalar CompilerProject),developpe a` luniversite de Rice. Iloc est detaille en Annexe A (page 117). Des exemplesdassembleur reel (Pentium et MIPS) sont visibles en pages 130 et 131.

ILOC na quun type de nombre : les entiers (pas de double, flottant etc.). La machine abstraitesur laquelle ILOC sexecute posse`de un nombre illimite de registres. Cest un code trois adresses.Il supporte simplement les modes dadressage elementaires :

adressage direct.load r1 r2 : charger dans r2 le contenu de la case dont ladresse est contenue dans r1,

chargement.loadI 2 r2 : charger dans r2 la valeur 2.

adressage indirect Address-Immediate.loadAI r1, 2 r2 : charger dans r2 le contenu de la case dont ladresse est contenu der1+2.

adressage indirect indexe Adress-Offset.loadAO r1, r2 r3 : charger dans r3 le contenu de la case dont ladresse est contenu der1+contenu de r2.1

Chaque instruction ILOC peut etre precedee dun label qui peut etre reference par les ins-tructions de branchement (jump,cbr). Le registre r0 designe par defaut lenregistrement dactivation(activation record : AR) de la procedure courante. Les decalage en memoire par rapport a` cet ARsont notes : @x. Il y a deux types dinstruction de controle du flot pour illustrer deux manie`resdimplementer cela au niveau de la generation de code.

1demander le nom des differents adressage en francais

8

2 Grammaires et expressions regulie`res

2.1 Quelques definitions

Nous allons survoler quelques definitions importantes (langage regulier, grammaire, auto-mate etc.). Ces notions sont utilisees dans beaucoup de domaines de linformatique, elles sontapprofondies dans le cours de Marianne Delorme (automates).

automates finis On cherche a` reconnatre un langage cest a` dire a` indiquer si la phrase que lona lu appartient bien syntaxiquement au langage ou pas. Commencons par la tache simple quiconsiste a` reconnatre quelques mots particuliers. Par exemple, nous souhaitons reconnatre lemot fee. La manie`re la plus naturelle est de lire les lettres les unes apre`s les autres et daccepterle mot une fois que lon a bien lu fee. On passe alors par quatre etats : lorsquon a rien lu,lorsquon a lu f, lorsquon a lu fe puis lorsquon a lu fee. On peut representer cela par le dia-gramme :

S3s0f e e

S1 S2

Sur ce dessin, letat initial est s0, s3 est letat final signifiant quon a reconnut le mot fee. Si onest en train de lire un autre mot, une des transitions ne pourra pas seffectuer, on rejettera le mot.Le diagramme ci-dessus est la representation dun automate fini qui reconnat le mot fee. Si lonveut reconnatre deux mots, par exemple fee et feu, on peut utiliser lautomate suivant :

u

e

S3s0f e

S1 S2

S4

Plus formellement, on peut definir la notion dautomate fini :

Definition 2 Un automate fini deterministe est donne par (S,, , s0, SF ) ou : S est un ensemble fini detats ; est un alphabet fini ; : S S est la fonction de transition ; s0 est letat initial ; SF est lensemble des etats finaux

Dans notre exemple de lautomate reconnaissant fee, on a S = {s0, s1, s2, s3}, = {f, e} (outout lalphabet) = {(s0, f) s1, (s1, e) s2, (s2, e) s3}. Il y a en fait un etat implicitederreur (se) vers lequel vont toutes les transitions qui ne sont pas definies.

Un automate accepte une chane de caracte`re si et seulement si en demarrant de s0, les ca-racte`res successifs de la chane entranent une succession de transitions qui ame`ne lautomatedans un etat final. Si la chane x est composee des caracte`res x1x2 . . . xn, on doit avoir :

((. . . ((s0, x1), x2), x3) . . . , xn1), xn) SFPar definition, on peut avoir des circuits dans le diagramme de transition dun automate, cest

a` dire que lon peut reconnatre des mots de longueur arbitraire, par exemple, lautomate suivant

9

reconnat nimporte quel entier :

0

S1

19

09

s0

S2

Les automates que nous avons vus jusqua` present sont tous deterministes, cest a` dire que lors-quils sont dans un etat particulier si et quils lisent un caracte`re ci la donnee sj = (si, ci) definitexactement letat suivant. Nous allons avoir besoin dautomates indeterministes, cest a` dire dau-tomates qui, etant dans un etat si et lisant un caracte`re ci pourront atteindre plusieurs etats : sj1 ,ou sj2 , . . ., ou sj3 . Il y deux manie`res de representer cela sur les diagrammes de transition : soiton autorise les -transitions, cest a` dire des transitions du type : (si, ) = sj ou` est la chanevide (i.e. lautomate peut changer detat sans lire de caracte`re), soit on utilise plusieurs transitionsetiquetees par un meme caracte`re a` partir dun meme etat (cest a` dire que devient une fonctionde S 2S , qui retourne un ensemble detats). En pratique, on fait les deux.

Nous avons alors besoin dune nouvelle definition du fonctionnement dun automate (ou de lanotion daccepter). Un automate non deterministe (S,, , s0, SF ) accepte une chane de caracte`rex0x1 . . . xn si et seulement si il existe un chemin dans le diagramme de transition qui demarre a`s0, et finit a` sk SF et tel que les etiquettes des arcs epellent toute la chane (sachant que les arcsetiquetes par ne comptent pas).

Par exemple : lautomate suivant reconnat un mot dun nombre quelconque (eventuellementnul) de a ou un mot dun nombre quelconque strictement positif de a suivi dun b.

bs0 S1

a

S3S2a

On peut demontrer que les automates deterministes et non deterministes sont equivalents enterme de langage reconnus (on verra sur un exemple comment determiniser un automate).

expressions regulie`res Une expression regulie`re est une formule close permettant de designerun ensemble de chanes de caracte`res construites a` partir dun alphabet (eventuellement aug-mente de la chane vide ). On appelle cet ensemble de chane de caracte`re un langage.

Une expression regulie`re est construite a` partir des lettres de lalphabet (un lettre dans uneexpression regulie`re designe lensemble reduit a` la chane de caracte`re egale au caracte`re en ques-tion) et des trois operations de base sur les ensembles de chanes de caracte`res :

lunion de deux ensembles, notee R | S est {s | s R ou s S}. la concatenation de deux ensembles R et S notee RS est {rs | r R et s S}. On note Ri

pour RRR . . . R i fois. la fermeture transitive (ou etoile, ou fermeture de kleene) dun ensemble de chanes de

caracte`res R notee R est i=0Ri. Cest donc lunion des concatenation de R avec lui memezero fois (cest a` dire la chane vide ) ou plus.

Le langage (ou ensemble) represente par une expression regulie`re r est note L(r). On utiliseaussi les parenthe`ses dans les expressions regulie`res pour exprimer la precedence (priorite deprecedence : fermeture > concatenation > union). Enfin, on utilise des raccourcis de notation : parexemple [0..4] equivaut a` 0|1|2|3|4, cest a` dire lensemble constitue des cinq chanes {0, 1, 2, 3, 4}.

On utilise ce formalisme pour specifier les langages de programmation que nous allons com-piler. Par exemple, les identificateurs dans beaucoup de langages actuels sont definis commecommencant par une lettre suivi de lettres ou de chiffres. On peut decrire cet ensemble de chanespar lexpression regulie`re : [a..z]([a..z]|[0..9]).

Pour les entiers : 0 | [1..9][0..9]Pour les reels (+ | | )(0 | [1..9][0..9])(.[0..9] | )E(+ | | )(0 | [1..9][0..9])Lensemble des langages qui peuvent etre exprimes par des expressions regulie`res est appele

10

lensemble des langages reguliers. Ces langages ont de bonnes proprietes qui les rendent en particu-lier aptes a` etre reconnus par des analyseurs generes automatiquement. Une propriete importanteest que ces langages sont clos par les operations dunion, concatenation et fermeture de kleene cequi permet de construire des analyseurs incrementalement. On peut montrer (on va le voir sur unexemple) que les langages reguliers sont exactement les langages qui peuvent etre reconnus parun automate fini.

2.2 De lexpression regulie`re a` lautomate minimal

La theorie des langages reguliers permet de generer automatique un analyseur syntaxique a`partir dune expression regulie`re. Le schema global est le suivant :

code pour analyseur

Expressions

Rgulires

Automates

finis

dterministes

Automates

finis

nondterministes

Construction de Kleene

Construction

de Thompson

Determinisation

Minimization

2.2.1 Des expressions regulie`res aux automates non deterministes

Pour etre capable de construire un automate qui reconnaisse un langage regulier quelconque,il suffit davoir un mecanisme qui reconnat chaque lettre, puis un mecanisme qui reconnat laconcatenation, lunion et la fermeture de langages reconnus.

Nous allons illustrer ce processus sur un exemple simple, il est elementaire a` generaliser.Considerons le langage designe par lexpression regulie`re : a(b | c) . Le parenthesage indiquelordre dans lequel on doit decomposer lexpression ; il faut reconnatre dans lordre : les langagesb et c puis (b | c) puis (b|c) puis a puis a(b|c).

11

NFA pour (b|c)*

s0 S1a b c

NFA pour b|c

s2b

c

s3

s4 s5

s6 s7

s2b

c

s3

s4 s5

S6s6 s9

s8

NFA pour a(b|c)*

s0 s1a

s2 s3 s4 S1

s2b

c

s3

s4 s5

S6s6 s9

s8

Notons que ce langage particulier aurait ete reconnu par un automate beaucoup plus simple :

c

s0 S1a

b

La suite du processus permettra de simplifier lautomate obtenu jusqua` obtenir lautomate ci-dessus.

2.2.2 Determinisation

On veut maintenant obtenir un automate deterministe (D,, D, d0, DF ) a` partir dun auto-mate non-deterministe (N,, N , n0, NF ). La clef est de deriver D et D. reste le meme. Lal-gorithme utilise est appele la construction de sous-ensembles (subset construction). Lidee cest queles etats du nouvel automate sont des ensembles detats de lancien automate. Un nouvel etatqi = {n1, . . . , nk} contient precisement lensemble des anciens etats pouvant etre atteints en lisantun caracte`re particulier depuis un etat qj . Lalgorithme utilise pour construire le nouvel automateest le suivant :

q0 -fermeture(n0)initialiser Q avec q0WorkList q0Tant que (WorkList 6= )

choisir qi dans WorkList

12

pour chaque caracte`re c q -fermeture((qi, c))D[qi, c] qsi q / Q alors ajouter q a` WorkList ;

ajouter q a` Q ;

L-fermeture dun ensemble detats ajoute a` cet ensemble detat tous les etats pouvant etreatteint par des -transitions a` partir des etats de lensemble. Loperateur(qi, c) calcule lensembledes etats atteignables en lisant c depuis les etats nij de qi : si qi = {ni1, . . . , nik} alors (qi, c) =ni

jqiN (n

ij , c)

Appliquons cet algorithme sur lautomate non-deterministe obtenu (on a renomme les etats).

n8

a

a

a

n0 n1 n2 n3

n4 n5

n9

n6 n7

1. l-fermeture de n0 donne letat q0 = {n0}.2. la premie`re iteration de la boucle while calcule :

(q0, a) = {n1} ; -fermeture({n1})={n1, n2, n3, n4, n6, n9} = q1 (q0, b) = (q0, c) =

3. la deuxie`me iteration de la boucle while calcule : (q1, a) = (q1, b) = {n5} ; -fermeture({n5})={n5, n8, n9, n3, n4, n6} = q2 (q1, c) = {n7} ; -fermeture({n7})={n7, n8, n9, n3, n4, n6} = q3

4. les iterations suivantes retomberont sur les memes etats q2 et q3, lalgorithme sarrete en 4iterations et produit lautomate suivant :

.

q3

a

b

a

c

b

c bq0 q1

q2

c

On peut montrer que cette methode pour obtenir des automates deterministes reconnaissantune expression regulie`re produit des automates avec beaucoup detats (Q peut avoir 2|N | etats)mais naugmente pas le nombre de transitions necessaires pour reconnatre un mot.

remarque : algorithme de point fixe Lalgorithme que nous venons de voir est un bon exempledalgorithmes de point fixe qui sont tre`s largement utilises en informatique. La caracteristique detels algorithmes est quils appliquent une fonction monotone (f(x) x) a` une collection den-sembles choisis dans un domaine ayant une certaine structure. Ces algorithmes terminent lorsqueles iterations suivantes de la fonction ne modifient plus le resultat, on parle de point fixe atteint.

13

La terminaison de tels algorithmes depend des proprietes du domaine choisi. Dans notreexemple, on sait que chaque qi Q est aussi dans 2N , donc ils sont en nombre fini. Le corps de laboucle while est monotone car lensemble Q ne peut que grossir. Donc forcement, au bout dunmoment, Q sarretera de grossir. Lorsque Q ne grossit plus, lagorithme sarrete en |Q| iterationsau maximum, donc lalgorithme presente sarrete bien.

On calcule l-fermeture par un autre algorithme point fixe.

2.2.3 Minimisation

Le grand nombre detats de lautomate resultant de la determinisation est un proble`me pourlimplementation. La minimisation permet de regrouper les etats equivalents, cest a` dire qui ontle meme comportement sur les memes entrees. Lalgorithme de minimisation construit une parti-tion de lensemble D des etats de lautomate deterministe, chaque etat etant dans le meme sous-ensemble a le meme comportement sur les memes entrees. Lalgorithme est le suivant :

P {DF , D DF }tant que (P change)

T pour chaque ensemble p P

T T Partition(p)P T

Partition(p)pour chaque c

si c separe p en {p1, . . . , pk}alors Return({p1, . . . , pk})

Return(p)

La procedure Partition decoupe lensemble p en mettant ensemble les etats pi de p qui arriventdans le meme ensemble. Par exemple, le schema ci-dessous presente deux cas de figure. Sur lagauche, on a un automate dans lequel le caracte`re c ne separe pas la partition p1 car toutes lestransitions etiquetees par c arrive sur des etats qui sont dans la meme partition (dx, dy, dz sontdans p2). Sur la droite, c separe p1 en p1 = {{di}, {dj , dk}} car les transitions etiquetees par cpartant de di narrivent pas dans la meme partition que celles partant de dj et dk.

p2

di

dj

dk

dx

dy

dz

c

c

c

p1

p3

di

dj

dk

dx

dy

dz

c

c

c

p1 p2

Appliquons cet algorithme sur lexemple, lalgorithme demarre avec la partie elementaireseparant les etats finaux des non finaux :

14

p2

a

b

c

b

c bq0 q1

q2

c

q3

p1

Lalgorithme est incapable de separer p2, il termine donc immediatement et on obtient alors lau-tomate recherche :

c

s0 S1a

b

On peut aussi construire lexpression regulie`re qui correspond a` un automate donne (cest laconstruction de kleene), cest ce qui prouve lequivalence entre langages reconnus par des auto-mates et expressions regulie`res. Cela est etudie dans le cours de Marianne Delorme.

2.3 Implementation de lanalyseur lexical

Il sagit maintenant de produire une implementation de lautomate genere lors de la produc-tion precedente. Il y a essentiellement deux types dimplementation, les analyseurs bases sur destables et les analyseurs codes directement .

2.3.1 Analyseur lexical a` base de table

Lanalyseur utilise un programme squelette commun a` tous les analyseurs lexicaux et unetable dans laquelle est stockee la fonction de transition. Pour notre exemple cela donne :

char prochain caracte`restate s0tant que (char 6= EOF )

state (state, char)char prochain caracte`re

si (state SF )alors acceptersinon rejeter

a b c autress0 s1 s1 s1 s1

15

2.3.2 Analyseur lexical code directement

Le type danalyseur precedent passe beaucoup de temps a` tester et manipuler la variabledetat, on peut eviter cela en codant directement letat dans letat du programme :

s0 : char prochain caracte`resi (char = a)

alors goto s1sinon goto se

s1 : char prochain caracte`resi (char = b|char = c)

alors goto s1sinon si (char = EOF )

alors acceptersinon goto se

se : rejeter

Ce type dimplementation devient rapidement difficile a` gerer manuellement, mais il peut etregenere automatiquement et sera en general plus rapide que lanalyseur a` base de table.

2.4 Pour aller plus loin

Un analyseur lexical peut faire un peu plus que reconnatre une phrase du langage, il peutpreparer le terrain pour lanalyse syntaxique. En particulier, il peut reconnatre les mots clefs dulangage. Pour cela il y a deux possibilites, soit on introduit une suite explicite detats reconnaissantchaque mot clef, soit on reconnat les identificateurs et on les comparera a` une table des symbolescontenant les mots cles du langage.

En general, lanalyseur lexical va generer une sequence de mots elementaires ou token (separantidentificateurs, valeurs, mots clefs, structure de controle, etc.) qui sera utilisee pour lanalyse syn-taxique.

On peut choisir de realiser des actions dans chaque etat de lanalyseur (pas seulement lorsquelon a fini de lire la chane). Par exemple si on essaie de reconnatre un entier, on peut calculer auvol sa valeur pour la produire de`s que lentier est reconnu.

Le developpement des techniques presentees ici a entrane des definitions de langage coherentesavec les contraintes des expressions regulie`res. Mais les langages anciens ont certaines caracteristiquesqui les rendent delicat a` analyser. Par exemple, en Fortran 77, les espaces ne sont pas significatifs,donc unentier, un entier, u n e n t i e r representent la meme chane. Les identifi-cateurs sont limites a` 6 carcte`res, et le compilateur doit utiliser cela pour identifier les structuresdu programme ; les mots cles ne sont pas reserves. Par exempleFORMAT(4H)=(3)est linstruction FORMAT car 4H est un prefixe qui designe )=(3 comme une chane de caracte`re.Alors queFORMAT(4 )=(3)est lassignation a` lelement numero 4 du tableau FORMAT.

Ces difficultes ont amene les developpeurs a` produire des analyseurs lexicaux a` deux passes.

16

3 Analyse syntaxique

Dans ce cours nous allons etudier comment produire des analyseurs syntaxique pour les lan-gages definis par des grammaires hors contexte. Il existe de nombreuses methodes pour parser (i.e.analyser syntaxiquement) de tels langage, nous verrons une methode recursive descendante (topdown recursive descent parsing) qui est la methode la plus pratique lorsquon code le parser a` lamain. Le meme principe est utilise pour les parser LL(1). Nous verrons aussi une technique as-cendante (bottom-up LR(1) parsing) basee sur des tables aussi appelee shift reduce parsing.

3.1 Grammaires hors contexte

Pour decrire la syntaxe dun langage de programmation, on utilise une grammaire. Une gram-maire est un ensemble de re`gles decrivant comment former des phrases.

Definition 3 Une grammaire hors contexte (context free grammar, CFG) est un quadrupletG = (T,NT, S, P )ou` :

T est lensemble des symboles terminaux du langage. Les symboles terminaux correspondent auxmots decouvert par lanalyseur lexical. On representera les terminaux soulignes pour les identifier.

NT est lensemble des symboles non-terminaux du langage. Ces symboles napparaissent pas dansle langage mais dans les re`gles de la grammaire definissant le langage, ils permettent dexprimer lastructure des re`gles grammaticales.

S NT est appele lelement de depart de G (ou axiome de G). Le langage que G decrit (noteL(G)) correspond a` lensemble des phrases qui peuvent etre derivees a` partir de S par les re`gles de lagrammaire.

P est un ensemble de production (ou re`gles de reecriture) de la forme N 12 . . . n aveci T NT . Cest a` dire que chaque element de P associe un non terminal a` une suite de terminauxet non terminaux. Le fait que les parties gauches des re`gles ne contiennent quun seul non terminaldonne la propriete hors contexte a` la grammaire.

Exemple : une liste delement

T = {elem}, NT = {List}, S = List, P ={

List elem ListList elem

}On peut facilement voir quune suite finie dun nombre quelconque de elem correspond a` une

phrase du langage decrit par cette grammaire. Par exemple, elem elem correspond a` lapplicationde la premie`re re`gle puis de la deuxie`me en partant de S :

List elem List elem elemExemple : des parenthe`ses et crochets correctement equilibres en alternance, on pourra utiliser

les re`gles suivants :

P ={

Paren ( Croch )| ( )

Croch [ Paren ]| [ ]

}On peut eventuellement rajouter un non terminal Start pour commencer indifferemment par

des crochets ou par des parenthe`ses :

Start Parent| Croch

Considerons la grammaire suivante :

1. Expr Expr Op nombre2. nombre3. Op +4. 5. 6.

17

En appliquant la sequence de re`gles : 1, 5, 1, 4, 2 on arrive a` deriver la phrase : nombre nombre nombre :

Re`gle PhraseExpr

1 Expr Op number5 Expr number1 Expr Op number number4 Expr number number2 number number number

On peut representer graphiquement cette derivation par un arbre que lon nomme arbre de derivation(ou arbre syntaxique, arbre de syntaxe, parse tree).

Expr

Op

number

Expr number

Expr Op

*

number

Lors de cette derivation, nous avons toujours decide dutiliser une re`gle derivant du non terminalle plus a` droite de la phrase (derivation la plus a` droite, rightmost derivation). On aurait pu arrivera` la meme phrase en choisissant systematiquement le non-terminal le plus a` gauche par exemple(derivation la plus a` gauche), cela donne lordre dapplication des re`gles : 1, 1, 2 ,4 , 5

Re`gle PhraseExpr

1 Expr Op number1 Expr Op number Op number2 number Op number Op number4 number number Op number5 number number number

Si lon dessine larbre de derivation correspondant on sapercoit que cest le meme arbre que celuidessine precedemment. En general, ce nest pas toujours le cas. Cette propriete est appelee lanon-ambigute. Une grammaire est ambigue sil existe une phrase de L(G) qui posse`de plusieursarbres de derivation.

Lexemple classique de grammaire ambigue est le if-then-else

1 Instruction if Expr then Instruction else Instruction2 | if Expr then Instruction3 | Assignation4 | AutreInstructions....

Avec cette grammaire, le code

if Expr1 then if Expr2 then Ass1 else Ass2

peut etre compris de deux manie`res :

if Expr1then if Expr2

then Ass1else Ass2

if Expr1then if Expr2

then Ass1else Ass2

Bien sur, les sens des deux interpretations sont differents. Pour enlever cette ambigute, ondoit faire un choix pour la resoudre (par exemple que chaque else se rapporte au if non ferme

18

le plus proche dans limbrication), et on doit modifier la grammaire pour faire apparatre cettere`gle de priorite, par exemple de la facon suivante :

1 Instruction AvecElse2 | DernierElse3 AvecElse if Expr then AvecElse else AvecElse4 | Assignation5 | AutreInstructions....6 DernierElse if Expr then Instruction7 | if Expr then AvecElse else DernierElse8 | AutreInstructions....

On voit donc une relation entre la structure grammaticale et le sens dune phrase. Il existe dautressituations pour lesquelles la structure de la grammaire va influencer sur la manie`re avec la-quelle on comprend la phrase. Par exemple, pour la priorite des operateurs, la grammaire donneeprecedemment pour les expressions arithmetiques simples ne permet pas dencoder dans larbrede derivation lordre correct devaluation de lexpression : si lon parcourt larbre dun manie`re na-turelle par exemple par un parcours en profondeur, on evaluera lexpression (nombrenombre)nombre alors que lon voudrait evaluer nombre (nombre nombre).

Pour permettre que larbre de derivation refle`te la precedence des operateurs, il faut restruc-turer la grammaire, par exemple de la facon suivante :

1. Expr Expr +Term2. Expr Term3. Term4. T erm Term number5. Term number6. number

On fera de meme pour introduire les precendences superieures pour les parenthe`ses, les indicesde tableaux, les conversions de type (type-cast) etc. Dans la suite on utilisera la grammaire ci-dessous (grammaire dexpressions classiques)

La grammaire dexpressions arithmetiques classiques :

1. Expr Expr + Term2. Expr Term3. Term4. T erm Term Factor5. Term Factor6. Factor7. Factor ( Expr )8. number9. identifier

Jusqua` present nous avons devine les re`gles a` utiliser pour deriver une phrase. Le travaildu parser est de construire larbre de derivation a` partir dune phrase du langage composee doncuniquement de terminaux. En fait, le parser prend en entree une phrase allegee par lanalysesyntaxique cest a` dire une sequence de mots (token) avec leur categorie syntaxique attachee. Parexemple si le code source est x 2 y, lentree du parser sera quelque chose comme :

identificateur, x nombre, 2 identificateur, y

On voudrait produire larbre suivant grace a` la grammaire des expressions arithmetiques clas-siques.

19

Factor

Term

Factor

Term

Expr

Expr

Factor

Term

*

Les parseurs descendants (top down parsers) vont partir de laxiome et a` chaque etape choisirdappliquer une re`gle pour lun des non terminals presents sur la frontie`re de larbre. Les parsersascendants (bottom up parsers) vont partir des feuilles et tenter de reconstruire larbre a` partir dubas.

Les grammaires hors contexte decrivent plus de langages que les expressions regulie`res (ce-lui des parenthe`ses equilibrees ne peut etre exprime en expression regulie`re, les prioritees entreoperateurs peuvent etre exprimees dans la structure des grammaires hors contexte). La classe desgrammaires regulie`res decrit exactement les meme langages. Une grammaire est dite regulie`re (ougrammaire lineaire a` gauche) si toutes les productions sont de la forme : soit A a soit A aBavec A,B NT et a T . Les langages reguliers sont un sous ensemble strict de lensemble deslangages reconnus par les grammaires hors contexte.

On peut legitimement se demander pourquoi on nutilise pas uniquement le parsing pouranalyser un programme source. As-ton besoin de lanalyse lexicale ? La raison est que les analy-seurs bases sur des automates finis sont tre`s efficaces, le temps danalyse est proportionnel a` lalongueur de la chane dentree et les constantes multiplicatives sont tre`s petites (un analyseur syn-taxique serait beaucoup plus long). Mais surtout, en reconnaissant les structures lexicales de base,les analyseurs lexicaux reduisent fortement la complexite des grammaires necessaires a` specifierla syntaxe du langage (suppression des commentaires, detection des identificateurs, des valeursetc.).

3.2 Analyse syntaxique descendante

Le principe de lanalyse syntaxique descendante est le suivant : on commence avec laxiome dela grammaire et on developpe systematiquement larbre de derivation jusquaux feuilles (termi-naux) en choisissant systematiquement de deriver le non-terminal le plus a` gauche sur la frontie`rede larbre. Quand on arrive aux terminaux, on verifie quils correspondent aux mots qui sont dansla phrase ; si cest OK, on continue, sinon, il faut revenir en arrie`re (bactracker) et choisir une autrere`gle dans le processus de derivation. Larbre de derivation au cours de lalgorithme ressembledonc a` cela :

20

Frontire

t1 t2 t3

NT1 NT2 NT3 NT4 NT5

Axiome

.......

NTn

Prochain non terminal dvelopp

On va voir que ce qui rend ce processus viable est quil existe un large sous ensemble degrammaires hors contexte pour lesquelles, on naura jamais besoin de bactracker. On utilise unpointeur sur la chane a` lire qui ne peut quavancer (on na pas acce`s a` nimporte quel endroit dela chane nimporte quand).

3.2.1 Exemple danalyse descendante

Considerons que lon ait a parser lexpression x2y que lon veut parser avec la grammairedes expressions arithmetiques classiques. On va utiliser les notation precedentes pour la succes-sion de re`gles permettant la derivation en ajoutant un signe : dans la colonne des numeros dere`gle pour indiquer que lon avance le pointeur de lecture. La fle`che verticale indiquera la positiondu pointeur de lecture. Si lon applique betement la methode expliquee ci-dessus, on va pouvoirtomber sur ce type de derivation :

Re`gle Phrase EntreeExpr x 2 y

1 Expr + Term x 2 y1 Expr + Term + Term x 2 y1 Expr + Term ... x 2 y1 ... x 2 y

En fait la grammaire telle quelle est definie pose un proble`me intrinse`que car elle est recursivea` gauche. Ignorons pour linstant ce proble`me et supposons que le parser ait effectue la derivationsuivante :

Re`gle Phrase EntreeExpr x 2 y

3 Term x 2 y6 Factor x 2 y9 identifier x 2 y identifier x 2 y

Ici, on ne boucle pas mais on na pas reconnu la phrase entie`re, on en a reconnu une partie, mais onna plus de non terminal a` remplacer, on ne sait pas si lon a fait un mauvais choix a` un moment ousi la phrase nest pas valide. Dans le doute, on backtrack et, en supposant que lon puisse essayer

21

toutes les possibilites, on arrivera finalement a` la derivation suivante :

Re`gle Phrase EntreeExpr x 2 y

2 Expr Term x 2 y3 Term Term x 2 y6 Factor Term x 2 y9 identifier Term x 2 y identifier Term x 2 y identifier Term x 2 y4 identifier Term Factor x 2 y6 identifier Factor Factor x 2 y8 identifier number Factor x 2 y identifier number Factor x 2 y identifier number Factor x 2 y9 identifier number identifier x 2 y identifier number identifier x 2 y

3.2.2 Elimination de la recursion a` gauche

La recursivite a` gauche pose un proble`me pour ce type de parser car le bactrack ne peutarriver que lorsquon arrive sur un non terminal en premie`re position dans la phrase partielleen cours de reconnaissance. On peut transformer mecaniquement des grammaires pour enlevertoute recursivite a` gauche en autorisant les re`gles du type A .

A A

A BB B

Lorsque la recursivite est indirecte, on deroule les re`gles jusqua` ce que lon rencontre une

recursivite directe et on utilise le meme processus :

A B B A

A A

B A

A CC C

B A

Du fait de la nature finie de la grammaire, on sait que le processus de deroulage va sarreter.La grammaire des expressions arithmetiques classique peut etre reecrite en variante recursive a`droite :

1. Expr Term Expr2. Expr + Term Expr3. Term Expr4. 5. T erm Factor Term6. T erm Factor Term7. Factor Term8. 9. Factor ( Expr )10. number11. identifier

3.2.3 Elimination du bactrack

On va montrer comment on peut, pour des grammaires recursives a` droite, systematiquementeliminer le bactrack. En fait, le bactrack arrive lorsque lalgorithme choisi une mauvaise re`gle a`

22

appliquer. Si lalgorithme choisissait systematiquement la bonne re`gle, il ny aurait jamais besoinde bactracker.

Lidee est que lorsque le parser choisit une re`gle pour remplacer le non terminal le plus a`gauche sur la frontie`re, il va etre capable de connatre lensemble des terminaux qui arriverontfinalement a` cette place. En regardant le premier mot non accepte sur la phrase dentree, le par-ser va alors pouvoir choisir la re`gle qui convient. On peut montrer que pour les grammairesrecursives a` droite, la lecture dun seul mot en avant permet de decider quelle re`gle appliquer. Dela` vient le terme LL(1) : Left-to-right scanning, Leftmost derivation, use 1 symbol lookahead .

Voyons comment cela marche en reconnaissant lexpression x2y avec la version recursivea` droite de la grammaire dexpressions arithmetiques classiques :

Re`gle Phrase EntreeExpr x 2 y

1 Term Expr x 2 y5 Factor Term Expr x 2 y11 id Term Expr x 2 y id Term Expr x 2 y8 id Expr x 2 y3 id Term Expr x 2 y id Term Expr x 2 y5 id Factor Term Expr x 2 y10 id num Term Expr x 2 y id num Term Expr x 2 y6 id num Factor Term Expr x 2 y id num Factor Term Expr x 2 y11 id num id Term Expr x 2 y id num id Term Expr x 2 y 8 id num id Expr x 2 y 4 id num id x 2 y

Les deux premie`res derivations sont imposees. Nous voyons que la troisie`me derivation (appli-cation de la re`gle 11) est imposee par le fait que le mot arrivant nest ni une parenthe`se ni unnombre. De meme on est oblige dappliquer la re`gle 8 (Term ) car sinon on devrait trouversoit un soit un . On continue jusqua` reconnaissance de la phrase entie`re.

On va formaliser cela en introduisant les ensembles First et Follow.

Definition 4 Soit First() lensemble des symboles terminaux qui peuvent apparatre comme premiersymbole dans une phrase derivee du symbole

First est defini pour les symboles terminaux et non terminaux. Considerons les re`gles pourExpr :

2. Expr + Term Expr3. Term Expr4.

Pour les deux premie`res,il ny a pas dambiguites, par contre, pour lepsilon transition, le seulsymbole derive est , on met alors dans lensemble First on a donc : First(Expr) = {+,, }.

Si un ensemble First(A) contient , on ne sait pas quel non terminal sera recontre lorsque ceA aura ete developpe. Dans ce cas, le parser doit connatre ce qui peut apparatre immediatementa` la droite de la chaine vide produite, ici, immediatement a` la droite de Expr.

Definition 5 Etant donne un symbole non terminal A, on definit Follow(A) comme lensemble des sym-boles terminaux qui peuvent apparatre immediatement apre`s un A dans une phrase valide du langage.

Dans notre grammaire, on voit que rien ne peut apparatre apre`s Expr a` part une parenthe`sefermante : Follow(Expr) = {eof, )}. Voici les algorithmes pour calculer les ensembles First etFollow :

23

pour chaque TFirst()

pour chaque A NTFirst(A)

tant que (les ensembles First changent)Pour chaque p P ou p a` la forme A 12 . . . k

First(A) First(A) (First(1) {})i 1tant que ( First(i) et i k 1)

First(A) First(A) (First(i+1) {})i i+ 1

si i = k et First(k)alors First(A) First(A) {}

pour chaque A NTFollow(A)

tant que (les ensembles Follow changent)Pour chaque p P ou p a` la forme A 12 . . . k

si k NT alors Follow(k) Follow(k) Follow(A)Traqueur Follow(A)Pour i k jusqua` 2

si First(i) alorssi i1 NT alors Follow(i1) Follow(i1) (First(i) {}) Traqueur

sinonsi i1 NT alors Follow(i1) Follow(i1) First(i)Traqueur First(i)

Ces algorithmes sont formules comme des calculs de point fixe, on peut montrer quils convergent.Les ensembleFirst etFollow pour les non terminaux de la grammaire dexpressions arithmetiquesclassiques (variante recursive a` droite) sont :

symbole F irst FollowExpr {(, number, identifier} {)}Expr {+,, } {)}Term {(, number, identifier} {+,}Term {,, } {+,}Factor {(, number, identifier} {,,+,}

On peut maintenant formuler la condition a` laquelle une grammaire permet deviter les bac-track dans un parsing descendant. Notons First+() lensemble First() si / First() etFirst() Follow() si First(). La condition que doit verifier la grammaire est que pourtout non-terminalA qui est en partie de gauche plusieurs re`gles :A 1 | 2 | . . . n on doit avoirla propriete suivante. Par extension First+(ABCD) designe First+(A) et dans le cas particulierou` un des i est egal a` , on rajoute lintersection avec des First+(i) avec Follow(A).

First+(i) First+(j) = , i, j 1 i < j n

Pour que lon ait cette propriete, etant donnee une grammaire recursive a` droite, on va la fac-toriser a` gauche, cest a` dire que lorsquon aura plusieurs productions pour le meme non-terminalqui ont le meme prefixe, on va introduire un nouveau non-terminal pour tous les suffixes sui-vant ce prefixe, ce qui permettra de choisir une et une seule re`gle lorsquon veut demarrer par ceprefixe. Par exemple, si on a les re`gles :

A 1 | 2 | . . . | n | 1 | . . . | k

24

on les remplacera par :A B | 1 | . . . | kB 1 | 2 | . . . | n

La factorisation a` gauche permet de convertir certaines grammaires necessitant du bactrack endes grammaires ne necessitant pas de bactrack (ou grammaires predictives, ou grammaire LL(1)).Cependant toutes les grammaires hors contexte ne peuvent pas etre transformees en grammairesne necessitant pas de bactrack. Savoir si une grammaire LL(1) equivalente existe pour une gram-maire hors contexte arbitraire est indecidable.

3.2.4 Parser descendant recursif

On a maintenant tous les outils pour construire un parser recursif descendant a` la main. On vaecrire un ensemble de procedures mutuellement recursives, une pour chaque non-terminal dansla grammaire. La procedure pour le non terminal A doit reconnatre une instance de A pour celaelle doit reconnatre les differents non-terminaux apparaissant en partie droite dune productionde A. Par exemple, si A posse`de les productions suivantes :

A a1 1 | 1 2 |

avec a1 T , 1, 1, 2 NT alors le code de la procedure pour A aura la forme suivante :

trouverA()si (motCourant = a1) alors

motCourant = prochainMot() ;return (trouver1()) /* A a1 1 choisi */

sinon si (motCourant First+(1)) alorsreturn (trouver1() trouver2()) /* A 1 2 choisi */

sinon si (motCourant Follow(A))alors return True /* A choisi */sinon return False /* erreur */

Par exemple, voici le parser recursif descendant pour la grammaire des expressions arithmetiques(variante recursive a` droite) :

25

Main()/* But Expr */motCourant = prochainMot() ;si (Expr() motCourant == eof )

alors return Truesinon return False

Expr()/* Expr Term Expr */si (Term() == False)

alors return Falsesinon return EPrime()

EPrime()/* Expr + Term Expr *//* Expr Term Expr */si (motCourant == +)

(motCourant == ) alorsmotCourant = prochainMot()si (Term() == False)

alors retrun Falsesinon return EPrime()

/* Expr */return True

Term()/* Term Factor Term */si (Factor() == False)

alors return Falsesinon return TPrime()

EPrime()/* Term Factor Term *//* Term Factor Term */si (motCourant == )

(motCourant == ) alorsmotCourant = prochainMot()si (Factor() == False)

alors retrun Falsesinon return TPrime()

/* Term */return True

Factor()/* Factor ( Expr ) */si (motCourant == () alors

motCourant = prochainMot()si (Expr() == False)

alors retrun Falsesinon si (motCourant 6=))

alors return Falsesinon/* Factor number *//* Factor identifier */

si (motCourant() 6= number)(motCourant() 6= identifier)

alors return FalsemotCourant = prochainMot()return True

On peut aussi imaginer une implementation a` base de table indiquant, pour chaque non termi-nal, la re`gle a` appliquer en fonction du mot rencontre. Ce type de parseur presentent les avantagesdetre facilement codes manuellement, ils sont compacts et efficaces. Ils gene`rent en particulier undebogging tre`s efficace pour les entrees non conformes.

3.3 Parsing ascendant

On va voir maintenant lapproche inverse : on construit des feuilles au fur et a` mesure quonrencontre des mots, et lorsque lon peut reduire les feuilles en utilisant une re`gle (i.e. ajouter unparent commun a` plusieurs noeuds contigus correspondant a` une partie gauche de re`gle), on lefait. Si la construction est bloquee avant darriver a` une racine unique etiquetee par laxiome, leparsing echoue. Larbre de derivation est donc construit par le bas et la frontie`re est maintenantdirigee vers le haut :

26

Frontire

t1 t2 t3

NT1 NT2NT3

NT4

NT5 NT6

NT7

t4 t5 t6

Du fait que les reductions de re`gles ont lieu a` partir de la gauche (dans lordre de lecture de laphrase), et que larbre est construit a` lenvers, par les feuilles, larbre de derivation decouvert parce parseur sera un arbre de derivation la plus a` droite. On va considerer les parser LR(1). Cesparseurs lisent de gauche a` droite et construisent (a` lenvers) une derivation la plus a` droite enregardant au plus un symbole sur lentree, dou leur nom : Left-to -right scan, Reverse-rightmostderivation with 1 symbol lookahead. On appelle aussi cela du shift-reduce parsing.

On introduit la notation suivante : A , k indique que sur la frontiere, a` la position k,il y une possibilite de reduction avec la re`gle A . On appelle cela une reduction candidate(handle en anglais). Limplementation du parser va utiliser une pile. Le parser fonctionne de lamanie`re suivante : il empile la frontie`re, reduit les reductions candidates a` partir du sommet depile (depile les parties droites et empile la partie gauche de la re`gle selectionnee). Quand celanest plus possible, il demande le prochain mot et lempile puis recommence. Le sommet de lapile correspond a` la partie la plus a` droite de la frontie`re. Lalgorithme generique pour le shift-reduce parsing est le suivant :

push InvalidmotCourant prochainMot()tant que (motCourant 6= eof ou la pile ne contient pas exactement Expr au dessus de Invalid)

si une reduction candidate A , k est au sommet de pilealors /* reduire par A */

pop || symbolspush A

sinon si (motCourant 6= eof )alors/* shift : decalage dun sur lentree */

push motCourantmotCourant prochainMot()

sinon /* pas de reduction candidate pas dinput */error

Ici les bonnes reductions candidates ont ete trouvees par un oracle. Une detection efficace desbonnes reductions candidates a` realiser est la clef dun parsing LR(1) efficace. Une fois que lon acela, le reste est trivial.

3.3.1 Detection des reductions candidates

On va introduire une nouvelle notation pour les reductions candidates : A . Le pointnoir (, dot en anglais) represente le sommet de la pile. La notation A signifie, la pile esttelle que lon peut reduire avec la re`gle A a` partir du sommet de pile (on na plus besoin deladresse dans la frontie`re puisquon choisi de reduire toujours a` partir du sommet de pile). Dansle meme ordre didee, la notation A va representer letat dans lequel jai empile , sijamais jempile encore alors la re`gle A sera une reduction candidate et je pourrai reduire.

27

On dit alors que lon a une reduction potentielle (elle nest pas encore candidate puisquon a pas lutout ce dont on aurait besoin pour faire la reduction).

On peut construire un nombre fini de tel dotted item (reduction candidate ou potentielle) pourune grammaire donnee. Un ensemble de reductions candidates ou potentielles represente doncun etat du parser (i.e. un ensemble de possibilites daction a` realiser en fonction de ce qui estlu). Les parseurs LR(1) sont en fait des automates dont les etats sont constitues densemble dereductions potentielles ou candidates. On a vu quon pouvait implementer ces automates a` partirdune table repesentant la fonction de transition, les outils permettant la construction de cettetable sont tre`s largement utilises aujourdhui pour la construction de parser.

La grosse difficulte va etre de construire deux tables (Action et Goto) qui vont indiquer lactiona` realiser a` chaque etape. Ces tables contiennent la connaissance precompilee des reductionspotentielles et candidates pouvant se presenter en fonction de ce quon lit et de letat dans lequelon se trouve. Lalgorithme pour le parser LR(1) est le suivant :

push Invalidpush s0motCourant prochainMot()tant que (True)

s sommet de pilesi Action[s,motCourant]= shiftalors push motCourant

push Goto[s,motCourant]motCourant prochainMot()

sinon si Action[s,motCourant]= reduce A alors pop 2 || symboles

s sommet de pilepush Apush Goto[s,A]

sinon si Action[s,motCourant]= accept alors Acceptsinon Erreur

On voit que, au lieu de la phrase vague : si une reduction candidate A est au sommet depile on a une action indiquee par la table action, et au lieu dempiler uniquement la frontie`re, onempile aussi letat courant.

3.3.2 Construction des tables LR(1)

Pour construire les tables Action et Goto, le parseur construit un automate permettant de re-connatre les reductions potentielles et candidates et deduit de cet automate les tables. Cet au-tomate utilise des ensembles ditem LR(1) (voir definition ci-apre`s) comme etats, lensemble desetats est appele la collection canonique densemble ditem LR(1) : CC = {cc0, cc1, . . . , ccn}. Chacun deces ensembles va correspondre a` un etat si de lautomate dans lalgorithme ci-dessus.

Definition 6 Un item LR(1) est une paire : [A , a] ou` A est une reduction potentielleou candidate, indique ou est le sommet de pile et a T est un terminal (on rajoute toujours le terminalEOF pour signifier la fin du fichier).

Ces itemLR(1) decrivent les configurations dans lesquelles peut se trouver le parser ; ils decriventles reductions potentielles compatibles avec ce qui a ete lu, a est le prochain caracte`re a` lire, unefois que lon aura reduit par cette reduction potentielle. Reprenons lexemple de la grammaire deliste :

1. But List2. List elem List3. | elem

28

elle produit les items LR(1) suivants :

[But List, eof ] [List elem List, eof ][But List , eof ] [List elem List, eof ][List elem, eof ] [List elem List , eof ][List elem , eof ] [List elem List, elem][List elem, elem] [List elem List, elem][List elem , elem] [List elem List , elem]

On suppose, comme cest le cas ici que lon a une unique re`gle indiquant le but a` realiser pourreconnatre une phrase du langage. Litem [But List, eof ] sert a` initaliser letat initial cc0du parseur. On va rajouter a cela les item qui peuvent etre rencontres pour realiser cet item : onutilise pour cela la procedure closure :

closure(s)tant que (s change)

pour chaque item [A C, a] spour chaque production C P

pour chaque b First(a)s s {[C , b]}

Voici lexplication en francais : si [A C, a] s alors une completion possible du contextedeja` lu est de trouver une chane qui se reduit a` C suivi de a. Si cette reduction (par exempleC ) a lieu, on va donc recontrer puis un element de First(a) juste apre`s donc on passeraforcement par un des item ajoutes dans la procedure closure.

Dans notre exemple, on a initalement [But List, eof ] dans cc0, le passage par la procedureclosure() ajoute deux items : [List elem List, eof ] et [But elem, eof ], comme les prece`dent uniquement des non terminaux, cela ne gene`re pas plus ditem :

cc0 = closure(s0) = {[But List, eof ], [List elem List, eof ], [But elem, eof ]}

Table Goto On construit une table qui prevoit letat que le parseur devrait prendre sil etait dansun certain etat s = cci et quil lisait un symbole x.

goto(s, x)moved pour chaque item i s

si i est [ x, a] alorsmoved moved {[ x , a]}

return closure(moved)

Sur notre exemple, goto(cc0, elem) donne dabord : les deux items : {[List elem List, eof ], [List elem , eof ]} puis la fermeture rajoute :

cc2 = goto(cc0, elem) ={

[List elem List, eof ] , [List elem , eof ] ,[List elem List, eof ] , [List elem, eof ]

}On a aussi

cc1 = goto(cc0, List) = {[But List , eof ]}et

cc3 = goto(cc2, List) = {[List elem List, eof ]et enfin : goto(cc2, elem) = cc2.

29

Collection canonique densemble ditem LR(1)

cc0 closure(s0)CC cc0tant que (CC change)

pour chaque ccj CC non marquemarquer ccjpour chaque x suivant un dans un item de ccj

temp goto(ccj , x)si temp / CC

alors CC CC {temp}enregistrer la transition de ccj a` temp sur x

Lensemble CC des etats generes ainsi que les transitions enregistrees donnent directement latable Goto (on utilise que les transitions sur les non-terminaux pour la table Goto). Pour la tableAction, on regarde les etats generes. Il y a plusieurs cas :

1. Un item de la forme [A c, a] indique le fait de rencontrer le terminal c serait une etapevalide pour la reconnaissance du non terminal A. Laction a` generer est un shift sur c dansletat courant. Le prochain etat est letat genere avec la table Goto ( et peuvent etre ).

2. Un item de la forme [A , a] indique que le parser a reconnu ; si le symbole a` lire est aalors litem est une reduction candidate, on gene`re donc un reduce A sur a dans letatcourant.

3. Litem [But S , eof ] est unique ; il gene`re une acceptation.Notez quon ignore les item ou` le prece`de un non-terminal. En fait, le fait que lon ait execute laprocedure closure assure que les items qui permettent de reduire ce non-terminal sont presentsdans le meme etat. On recupe`re donc les deux tables :

Table Actionetat eof elem

cc0 shift cc2cc1 acceptcc2 reduce List elem shift cc2cc3 reduce List elem List

Table Gotoetat List eof elem

cc0 cc1 cc2cc1cc2 cc3 cc2cc3

Si une grammaire nest pas LR(1) (si elle est ambigue, par exemple) alors cette propriete vaapparatre lors de la construction des tables. On va se retrouver avec un conflit shift reduce :un item contient a` la fois [A c, a] et [B , c]. Il peut aussi contenir un conflit reducereduce : [A , a] et [B , a]. La meilleure methode pour determiner si une grammaire estLR(1) est de lancer le parseur LR(1) dessus.

3.4 Quelques conseils pratiques

Bien que les parseurs soient maintenant essentiellement generes automatiquement, un certainnombre de choix sont laisses au programmeur.

Gestion derreur Le parseur est largement utilise pour debugger les erreurs de syntaxe, il doitdonc en detecter le maximum dun seul coup. Pour linstant on a toujours suppose que le parseursarretait lorsquil rencontrait une erreur. Si lon desire continuer le parsing, il faut un mecanismequi permette de remettre le parseur dans un etat a` partir duquel il peut continuer le parsing. Unemanie`re de realiser cela est de reperer des mots de synchronisation qui permettent de synchroni-ser lentree lue avec letat interne du parseur. Lorsque le parseur rencontre des erreurs, il oublieles mots jusqua` ce quil rencontre un mot de synchronisation. Par exemple, dans beaucoup delangage a` la Algol le point-virgule est un separateur qui peut etre utilise comme mot de syn-chronisation.

30

Pour les parseurs descendants, ca ne pose pas de proble`me. Pour les parseurLR(1), on cherchedans la pile le dernier Goto[s, Statement] (i.e. celui qui a provoque lerreur), on depile, avale lescaracte`res jusquau debut du prochain Statement et empile un nouveau Goto[s, Statement]. Onpeut indiquer aux generateurs de parseurs comment se synchroniser avec les re`gles de recou-vrement derreurs (on indique dans les parties droites de re`gles ou` et comment ils peuvent seresynchroniser).

Ambiguite sensible au contexte On utilise souvent les parenthe`ses pour representer a` la foisles acce`s aux tableaux et les appels de fonctions. Une grammaire permettant cela sera forcementambigue. Dans un parser descendant on peut tester le type de lidentificateur precedant les pa-renthe`se. Pour les parseurs LR(1) on peut introduire un non terminal commun pour les deuxusages (et tester le type de lidentificateur) ou reserver des identificateurs differents pour les ta-bleaux et le fonctions.

recursion a` droite ou a` gauche Les parsersLR(1) autorisent les grammaires recursives a` gauche.On a donc le choix entre grammaires recursives a` droite et a` gauche. Pour decrire le langage, plu-sieurs facteurs entrent en ligne de compte :

la taille de la pile. En general la recursion a` gauche entrane des piles de taille inferieure.La recursion a` gauche va reduire plus rapidement et limiter la taille de la pile (a` lextreme :une liste de taille l peut entraner une pile de taille 2 en recursif a` gauche et l en recursif a`droite).

Associativite. La recursion a` gauche ou a` droite de la grammaire va imposer lordre danslequel lassociativite va etre faite (les grammaires recursives a` gauche produisent de las-sociativite a` gauche si on a List List elem on produit un AST qui descend a` gauche etdonc : ((elem1 elem2) elem3) . . .. Meme pour des operateurs theoriquement associatifs cetordre peut changer les valeurs a` lexecution. On peut eventuellement modifier lassociativitepar defaut dans le parseur en manipulant explicitement lAST

optimisations La forme de la grammaire a un impact direct sur les performances de son analysesyntaxique (bien que la complexite asymptotique ne change pas). On peut reecrire la grammairepour reduire la hauteur de larbre de syntaxe. Si lon reprend la grammaire des expressions clas-siques et que lon deroule le non-terminal Factor dans lexpression de Term on obtient 9 par-ties droites possibles pour Term mais on reduit la hauteur generale de tout arbre dexpressionarithmetique de 1. En parsing LR(1) sur lexpression x 2 y, cela elimine trois reductions sur6 (le nombre de shift reste inchange). En general on peut eliminer toutes les productions in-utiles, cest a` dire ne comportant quun seul symbole en partie droite. En revanche la grammaireresultante est moins lisible et comme on va le voir plus loin, les actions que pourra realiser leparseur seront moins faciles a` controler. Cette transformation peut aussi augmenter la taille destables generees (ici CC passe de 32 ensembles a` 46 ensembles), le parseur resultant execute moinsde reductions mais manipule des tables plus grandes.

On peut aussi regrouper des non terminaux dans des categories (par exemple, + et ) et nemettre quune seule re`gle pour tous, la differenciation etant fate en testant explicitement la valeurdu symbole a` posteriori.

De gros efforts sont faits pour reduire les tables des parseurs LR(1). Lorsque les lignes ou lescolonnes des tables sont identiques, le concepteur du parseur peut les combiner et renommer leslignes des tables en consequence (une ligne peut alors representer plusieurs etats). pour la gram-maire des expressions simple, cela produit une reduction de taille de 28% . On peut aussi choisirde combiner deux lignes dont le comportement ne diffe`re que pour les erreurs, on acceptera peut-etre alors des codes incorrects.

On peut aussi decider dimplementer le contenu de Action et Goto directement en code plutotque dans une table. chaque etat devient alors un gros case. Cela devient difficile a` lire mais peutetre tre`s efficace

Enfin, il existe dautres algorithmes de construction de parseur qui produisent des tables pluspetites que la construction LR(1) classique. Lalgorithme SLR(1) (Simple LR(1)) impose a` lagrammaire que le symbole a` lire en avant ne soit pas necessaire pour effectuer une reduction par

31

le bas. Les item sont alors de la forme A sans le symbole cense suivre apre`s . Lal-gorithme est similaire a` LR(1) mais il utilise lensemble Follow entier (independant du contexte)pour choisir entre shift et reduction plutot que la restriction de cet ensemble au contexte danslequel on se trouve.

Lalgorithme LALR(1) (Lookahead LR(1)) rassemble certains item qui ne diffe`rent que parle symbole lu en avant (item ayant le meme core, le meme item SLR). Cela produit une collec-tion canonique semblable a` celle de la construction LR(1) mais plus compacte. Une grammaireLR(1) peut ne pas etre LALR(1) (on peut montrer que tout langage ayant une grammaire LR(1)a aussi une grammaire SLR(1) et une grammaire LALR(1)). Malgre la moindre expressivite,les parseurs LALR(1) sont extremement populaires du fait de leur efficacite (Bison/Y acc en estun). En fait pour une grammaire de langage quelconque il tre`s probable que la transformationLR(1) LALR(1) de lautomate donne un automate sans conflit.

3.5 Resume sur lanalyse lexicale/syntaxique

Lanalyse lexicale transforme un flot de caracte`res en un flot de token. Lanalyse syntaxiquetransforme un flot de token en arbre syntaxique.

Un token est generalement une classe et une chane de caracte`re (son nom) (on peut quel-quefois rajouter des informations sur sa position dans la chane).

Les analyseurs lexicaux peuvent etre generes a` partir des automates detats finis, eux-memesgeneres a` partir des expressions regulie`res decrivant des langages.

Lanalyseur lexical fait un traitement lorsquil rencontre un identificateur (en general il lereference dans une table des symboles).

Lanalyse syntaxique peut se faire de manie`re descendante ou ascendante (se referant a` lamanie`re avec laquelle on construit larbre syntaxique.

Les parseurs descendants ecrits a` la main consistent en un ensemble de procedures mutuel-lement recursives structurees comme la grammaire.

Pour ecrire ces parseurs, il faut avoir calcule les ensembles First et Follow. Les grammairesacceptees par ces parseurs sont dits LL(1).

Les grammaires recursives a` gauche ne sont pasLL(1), on peut derecursiver une grammairerecursive a` gauche.

Les parseurs ascendants manipulent des item : a` la base cest une re`gle avec un point (dot)symbolisant lendroit jusquauquel on a reconnu (eventuellement associe a` un ou plusieurssymboles representant ce que lon rencontrera apre`s avoir fini de reconnatre la re`gle enquestion).

Les parseurs ascendants essayent didentifier successivement les reductions candidates (handle).Il y de nombreuses techniques pour trouver les reductions candidates. Les parseurs LR(1)utilisent des ensembles ditem LR(1).

Un ensemble ditem represente un etat dans lequel peut se trouver le parseur LR(1) a` unmoment donne. Formellement, les etats de lautomate a` partir duquel est construit le par-seur LR(1) sont des ensembles ditem.

En parsing LR(0) tout item de la forme [N ] gene`re une reduction. En parsing SLR(1)un item [N ] gene`re une reduction si et seulement si le prochain symbole a` lireappartient a` Follow(N). En parsing LR(1) un item [N , A] gene`re une reduction si leprochain symbole a` lire est dans lensemble A, un petit ensemble de terminaux. En LR(1) Aest limite a` un symbole. En LALR(1) cest un ensemble de symbole (dans Follow(N)). Enpratique une grammaire LR(1) a de tre`s fortes chances detre LALR(1).

Concernant les classes de grammaires, on a les relations : RG LL(1) LR(1) CFG.Lambigute entrane le fait que la grammaire nest pas LR(1), mais ce nest pas le seul cas.Etant donnee une grammaire, on ne sait pas dire si on peut trouver une autre grammaireequivalente LR(1). La methode la plus simple pour savoir si une grammaire est LR(1) estde construire le parseur et de voir sil y a des reductions.

32

4 Analyse sensible au contexte

On a vu que lon pouvait introduire certaines informations semantiques dans la phase de par-sing. Mais cela ne suffit pas, on a besoin de plus dinformation que lon ne peut pas coder avecune grammaire hors contexte, on va avoir besoin dinformation contextuelle. Par exemple, lors-quon rencontre un identificateur, est-ce une fonction ou une variable ; si cest une variable, queltype de valeur est stockee dans cette variable ; si cest une fonction, combien et quel type dargu-ment a-t-elle ? Toutes ces informations sont disponibles dans le programme mais pas forcementa` lendroit ou` lon rencontre lidentificateur. En plus de reconnatre si le programme est bien unephrase du langage, le parseur va construire un contexte qui va lui permettre davoir acce`s a` cesinformations en temps voulu.

4.1 Introduction aux syste`mes de type

La plupart des langages propose un syste`me de type cest a` dire un ensemble de proprietesassociees a` chaque valeur. La theorie des types a genere enormement de recherches et de nou-veaux concepts de programmation que nous ne mentionneront pas ici. Le but dun syste`me detypage est de specifier le comportement du programme plus precisement quavec une simplegrammaire hors contexte. Le syste`me de type cree un deuxie`me vocabulaire pour decrire la formeet le comportement des programmes valides. Il est essentiellement utile pour :

la surete a` lexecution : il permet de detecter a` la compilation beaucoup plus de programmesmal formes.

augmenter lexpressivite : il permet dexprimer au moins plus naturellement certains concepts(par exemple par la surcharge doperateurs elementaires comme laddition).

generer un meilleur code : il permet denlever des tests a` lexecution puisque le resultat estconnu a` la compilation (exemple : comment stocker une variable quand on ne connait passon type).

4.1.1 Composant dun syste`me de typage

En general tous les langages ont un syste`me de type base sur :

Des types de base En general les nombres : entiers de differentes tailles, reels (flottants), ca-racte`res et booleens (quelquefois les chane de caracte`res).

Des constructeurs de types A` partir de ces types de base, on peut construire des structures dedonnees plus complexes pour representer les graphes, arbres, tableaux, listes, piles, etc. Parmi lesplus frequents on trouve : les tableaux avec des implementations diverses (ordre de linearisation,contraintes sur les bornes) et eventuellement des operations associees. Les chanes de caracte`ressont quelquefois implementees comme des tableaux de caracte`res. Le produit cartesien de type :type1 type2 (souvent appele structure) permett dassocier plusieurs objets de type arbitraire,les unions permettent de rassembler plusieurs types en un seul. Les ensembles enumeres sontsouvent autorises et enfin les pointeurs permettent davoir une certaine liberte quant a` la mani-pulation de la memoire.

Equivalence de types On peut decider que deux types sont dits equivalents lorsquils ont lememe nom (difficile a` gerer pour les gros programmes) ou lorsquils ont la meme structure (peutreduire les erreurs detectees par le syste`me de typage).

Des re`gles dinference Les re`gles dinference specifient pour chaque operateur les relationsentre le type des operandes et le type du resultat. Elles permettent daffecter un type a` toutesles expressions du langage et de detecter des erreurs de type.

33

Inference de type pour toutes les expressions Souvent les langages imposent une re`gle dedeclaration de type avant utilisation. Dans ce cas, linference et la detection derreur de type peutse faire a` la compilation. Sinon (ou pour les constantes par exemple) le type est choisi lorsquonrencontre lexpression, le mecanisme mis en place est plus complexe. Le syste`me doit forcementcontenir des re`gles pour lanalyse interprocedurale et definir des signatures (types des argumentset resultats) pour chaque fonction.

Remarque : Dans le cas des langages fortement types, linference de type se fait relativementbien. Il existe des situations plus difficiles. Par exemple, dans certains langages les declarationssont optionnelles, mais le typage doit etre consistant quand meme (le type ne change pas duneutilisation a` lautre). On introduit des algorithmes dunification pour trouver le type le plus largecompatible avec lutilisation qui est faite des variables. Dautres langages permettent le change-ment dynamique de types.

4.2 Les grammaires a` attributs

Les grammaires a` attributs ont ete proposees pour resoudre certains proble`mes de transmis-sion dinformation dans larbre de syntaxe. La grammaire hors contexte du langage est fourniepar le concepteur du langage ainsi que la semantique associee. Le concepteur du compilateurintroduit alors un ensemble dattributs pour les terminaux et non terminaux du langage et unensemble de re`gles associees aux re`gles de la grammaire qui permet de calculer ces attributs.

Considerons la grammaire SBN = (T,NT, S, P ) suivante representant les nombres binairessignes :

T = {+,, 0, 1} NT = {Number, Sign, List, Bit} S = {Number} P =

Number Sign ListSign +

| List List Bit

| BitBit 0

| 1

On va annoter cette grammaire avec des attributs permettant de calculer la valeur du nombrebinaire signe qui est represente :

Symbole AttributNumber valeurSign negatifList position, valeurBit position, valeur

On va ensuite definir les re`gles pour definir les attributs de chaque symbole. Ces re`gles sontassociees aux re`gles de la grammaire :

1. Number Sign List List.position 0si Sign.negatif

alors Number.valeur List.valeursinon Number.valeur List.valeur

2. Sign + Sign.negatif false3. Sign Sign.negatif true4. List Bit Bit.position List.position

List.valeur Bit.valeur5. List0 List1 Bit List1.position List0.position+ 1

Bit.position List0.positionList0.valeur List1.valeur +Bit.valeur

6. Bit 0 Bit.valeur 07. Bit 1 Bit.valeur 2Bit.position

34

Par exemple, pour la chane 101, on va construire larbre suivant :

val:4

Number

List

List

ListSign

Bit

Bit

Bit

1 0 1

neg: true

val:5

pos:0

val:5

pos:0

val:1

pos:1

val:0

pos:1

val:4

pos:2

val:4

pos:2

On peut representer les dependences entre les attributs :

val:4

Number

List

List

ListSign

Bit

Bit

Bit

1 0 1

neg: true

val:5

pos:0

val:5

pos:0

val:1

pos:1

val:0

pos:1

val:4

pos:2

val:4

pos:2

Pour construire cet arbre, on a execute un parseur qui a cree une instance des attributs pourchaque noeud et on a ensuite execute un evaluateur qui a calcule les valeurs de chaque attribut.

Les re`gles sur les attributs induisent des dependances implicites. Selon la direction des dependancesentre les attributs, on parle dattributs synthetises (lorsque le flot des valeurs va de bas en haut)ou herites (lorsque le flot des valeurs va de haut en bas, ou lorsque les valeurs viennent de luimeme ou de ses fre`res). Il faut quil ny ait pas de circuits dans un tel graphe de dependance.Pour les grammaires non circulaires, il existe des generateurs devaluateurs, qui etant donneeune grammaire a` attributs, vont generer un evaluateur pour les attributs. On a une certaine li-berte pour lordre devaluation du moment quil respecte les dependances. On peut utiliser des

35

methodes dynamiques (qui maintiennent une liste dattributs prets a` etre evalue), des methodessystematiques (parcours systematique de larbre jusqua` convergence), des methodes basees surles re`gles (on analyse statiquement lordre dans lequel peuvent etre executees les re`gles, voire oncree une methode dediee a` certains attributs).

Limitations des grammaires a` attributs Pour certaines informations qui se transmettent deproche en proche dans un seul sens, les grammaires a` attributs sont bien adaptees. En revanchebeaucoup de proble`mes pratiques apparaissent lorsquon veut transmettre dautre type dinfor-mations.

Information non locale. Si lon veut transmettre une information non locale par des attributs(e.g. le type dune variable stockee dans une table) , on doit ajouter des re`gles pour tous lesnon terminaux afin de transporter cette information jusqua` lendroit ou` elle est utile.

Place memoire. Sur des exemples realistes, levaluation produit un tre`s grand nombre dat-tributs. Le caracte`re fonctionnel de la transmission des attributs peut entraner une placeutilisee trop grande, or on ne sait pas a` priori quand est ce que lon va pouvoir desallouercette memoire.

Utilisation de larbre de parsing. Les attributs sont instancies sur les noeuds de larbre deparsing (i.e. larbre representant exactement la derivation dans la grammaire). Comme on vale voir, peu de compilateurs utilisent veritablement larbre syntaxique ; on utilise en generalun arbre de syntaxe abstrait (abstract syntax tree, AST) qui est une simplification de larbresyntaxique. Il peut arriver quon utilise pas du tout de representation sous forme darbre, lecout de la gestion additionnelle dun arbre doit etre evalue.

Acce`s aux informations. Les informations recuperees par les attributs sont dissemineesdans larbre. Lacce`s aux informations ne se fait pas en temps constant. Ce proble`me peutetre resolu par lutilisation de variables globales stockant les attributs. Dans ce cas, lesdependances entre attributs ne sont plus explicites mais par les acce`s aux cases du tableau(le paradigme nest plus fonctionnel)

Pour toutes ces raisons, les grammaires a` attributs nont pas eu le succe`s quont eu les grammaireshors contexte pour la definition de compilateurs. Elles restent neanmoins un moyen relativementpropre et efficace de calculer certaines valeurs lorsque la structure du calcul sy prete bien.

4.3 Traduction ad-hoc dirigee par la syntaxe

Lidee sous-jacente aux grammaires a` attributs est de specifier une sequence dactions associeeaux re`gles. Ce principe est maintenant implemente dans tous les compilateurs mais sous uneforme moins systematique que dans la theorie des grammaires a` attributs. Il ny aura quun seulattribut par noeud (qui peut etre considere comme la valeur associee au noeud) et cet attribut serasystematiquement synthetise (calcule de bas en haut). Les actions sont specifiees par le concepteurdu compilateur et peuvent etre des actions complexes referencant des variables globales (table dessymbole par exemple).

Le concepteur du compilateur ajou