Compilation Cours - Theorie des Langages (PDF)

Universite de Bretagne Occidentale IUP Ingenierie INFORMATIQUE Deuxi
eme annee COMPILATION THEORIE DES LANGAGES Derniere r
evision: 29 janvier 2003 Table des matieres 1 Introduction...

Universite de Bretagne Occidentale IUP Ingenierie INFORMATIQUE Deuxi
eme annee COMPILATION THEORIE DES LANGAGES Derniere r
evision: 29 janvier 2003 Table des matieres 1 Introduction 3 1.1 Qu'est ce que la compilation? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 1.2 Pourquoi ce cours? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.3 Bibliographie succinte : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 2 Structure d'un compilateur 6 2.1 Phases d'analyse : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 2.1.1 Analyse lexicale : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 2.1.2 Analyse syntaxique : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 2.1.3 Analyse s
emantique : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 2.2 Phases de production : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.2.1 G
en
eration de code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.2.2 Optimisation de code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.3 Phases paralleles : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.3.1 Gestion de la table des symboles : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.3.2 Gestion des erreurs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2.4 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 3 Analyse lexicale 9 3.1 Unit
es lexicales et lexemes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 3.1.1 Expressions r
egulieres : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 3.2 Mise en uvre d'un analyseur lexical : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 3.2.1 Sp
ecication des unit
es lexicales : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 3.2.2 Attributs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 3.2.3 Analyseur lexical : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 3.3 Erreurs lexicales : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13 4 L'outil (f)lex 15 4.1 Structure du chier de sp
ecications (f)lex : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15 4.2 Les expressions r
egulieres (f)lex : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 4.3 Variables et fonctions pr
ed
enies : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 4.4 Options de compilation ex : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 4.5 Exemples de chier.l : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 5 Analyse syntaxique 18 5.1 Grammaires et Arbres de d
erivation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 5.1.1 Grammaires : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 5.1.2 Arbre de d
erivation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 5.2 Mise en oeuvre d'un analyseur syntaxique : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 5.3 Analyse descendante : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21 5.3.1 Exemples : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21 5.3.2 Table d'analyse LL(1) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 22 5.3.3 Analyseur syntaxique : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 5.3.4 Grammaire LL(1) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 5.3.5 R
ecursivit
e a gauche : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 5.3.6 Grammaire propre : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 27 5.3.7 Factorisation a gauche : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 27 5.3.8 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28 5.4 Analyse ascendante : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 28 5.5 Erreurs syntaxiques : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 5.5.1 R
ecup
eration en mode panique : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 1  5.5.2 R
ecup
eration au niveau du syntagme : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 5.5.3 Productions d'erreur : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 5.5.4 Correction globale : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 6 L'outil yacc/bison 36 6.1 Structure du chier de sp
ecications bison : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36 6.2 Attributs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 6.3 Communication avec l'analyseur lexical: yylval : : : : : : : : : : : : : : : : : : : : : : : : : : : 37 6.4 Variables, fonctions et actions pr
ed
enies : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 6.5 Conits shift-reduce et reduce-reduce : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 6.5.1 Associativit
e et priorit
e des symboles terminaux : : : : : : : : : : : : : : : : : : : : : : : 38 6.6 R
ecup
eration des erreurs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 39 6.7 Exemples de chier.y : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 39 7 Theorie des langages : les automates 41 7.1 Classication des grammaires : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41 7.1.1 Les langages contextuels : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41 7.1.2 Les langages r
eguliers : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42 7.1.3 Les reconnaisseurs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 43 7.2 Automates a
etats nis : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 43 7.2.1 Construction d'un AEF a partir d'une E.R. : : : : : : : : : : : : : : : : : : : : : : : : : : 44 7.2.2 Automates nis d
eterministes (AFD) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 45 7.2.3 Minimisation d'un AFD : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48 7.2.4 Calcul d'une E.R. d
ecrite par un A.E.F. : : : : : : : : : : : : : : : : : : : : : : : : : : : : 48 7.3 Les automates a piles : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 49 8 Analyse semantique 51 8.1 D
enition dirig
ee par la syntaxe : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 51 8.1.1 Sch
ema de traduction dirig
e par la syntaxe : : : : : : : : : : : : : : : : : : : : : : : : : : 53 8.1.2 Graphe de d
ependances : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 53 8.1.3 Evaluation des attributs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 8.2 Port
ee des identicateurs : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 57 8.3 Contr^ole de type : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58 8.3.1 Surcharge d'op
erateurs et de fonctions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 59 8.3.2 Fonctions polymorphes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 59 8.4 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 59 9 Generation de code 62 9.1 Environnement d'ex
ecution : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 62 9.1.1 Organisation de la m
emoire a l'ex
ecution : : : : : : : : : : : : : : : : : : : : : : : : : : : 62 9.1.2 Allocation dynamique: gestion du tas : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 63 9.2 Code interm
ediaire : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 9.2.1 Caract
eristiques communes aux machines cibles : : : : : : : : : : : : : : : : : : : : : : : : 64 9.2.2 Code a 3 adresses simpli
e : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 9.2.3 Production de code a 3 adresses : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 65 9.3 Optimisation de code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 69 9.3.1 Optimisations ind
ependantes de la machine cible : : : : : : : : : : : : : : : : : : : : : : : 69 9.3.2 Optimisations d
ependantes de la machine cible : : : : : : : : : : : : : : : : : : : : : : : : 69 9.3.3 Graphe de ot de contr^ole : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 69 9.3.4 Elimination des sous-expressions communes : : : : : : : : : : : : : : : : : : : : : : : : : : 70 9.3.5 Propagation des copies : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 74 9.3.6 Calculs invariants dans les boucles : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 74 9.3.7 Interpr
etation abstraite : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75 9.4 G
en
eration de code : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75 Index 76 2 Chapitre 1 Introduction 1.1 Qu'est ce que la compilation? Tout programmeur utilise jour apres jour un outil essentiel a la r
ealisation de programmes informatiques: le compilateur. Un compilateur est un logiciel particulier qui traduit un programme
ecrit dans un langage de haut niveau (par le programmeur) en instructions ex
ecutables (par un ordinateur). C'est donc l'instrument fondamental a la base de tout r
ealisation informatique. algorithme editeur de texte programme source compilateur erreurs de compilation editeur de liens erreurs d’edition de liens programme cible resultats donnees processeur erreurs d’execution Fig. 1.1 - Cha^
ne de developpement d'un programme Tout programme
ecrit dans un langage de haut niveau (dans lequel il est fait abstraction (sauf pour quelques instructions) de la structure et des d
etails du calculateur sur lequel les programmes sont destin
es a ^etre ex
ecut
es) ne peut ^etre
ex
ecut
e par un ordinateur que s'il est traduit en instructions ex
ecutables par l'ordinateur (langage machine, instructions
el
ementaires directement ex
ecutables par le processeur). Remarque : Une autre phase importante qui intervient apres la compilation pour obtenir un programme ex
ecu- table est la phase d'editions de liens. Un
editeur de lien r
esout entre autres les r
ef
erences a des appels de routines dont le code est conserv
e dans des librairies. En g
en
eral, un compilateur comprend une partie
editeur de lien. Nous ne parlerons pas de cette
etape dans ce cours. En outre, sur les systemes modernes, l'
edition des liens est faite a l'execution du programme! (le programme est plus petit, et les mises a jour sont plus faciles) Autre remarque: on ne parlera pas non plus de la pr
ecompilation (cf pr
eprocesseur C) Attention, il ne faut pas confondre les compilateurs et les interpreteurs ! Un compilateur est un programme (de traduction automatique d'un programme
ecrit dans un langage source en un programme
ecrit dans un langage cible). Le chier r
esultant de cette compilation est directement ex
ecu- 3  programme source erreurs donnees interpreteur resultats Fig. 1.2 - Interpreteur table une fois pour toutes. Exemples de langages compil
es: Pascal, C, C++, ADA, Fortran, Cobol Au lieu de produire un programme cible comme dans le cas d'un compilateur, un interprete execute lui m^eme au fur et a mesure les op
erations sp
eci
ees par le programme source. Il analyse une instruction apres l'autre puis l'ex
ecute imm
ediatement. A l'inverse d'un compilateur, il travaille simultan
ement sur le programme et sur les donn
ees. L'interpr
eteur doit ^etre pr
esent sur le systeme a chaque fois que le programme est ex
ecut
e, ce qui n'est pas le cas avec un compilateur. G
en
eralement les interpr
eteurs sont assez petits, mais le programme est plus lent qu'avec un langage compil
e. Autre inconv
enient : on ne peut pas cacher le code (et donc garder des secrets de fabrication), toute personne ayant acces au programme peut le consulter et le modier comme il le veut. Par contre, les langages interpr
et
es sont souvent plus simples a utiliser et tolerent plus d'erreurs de codage que les langages compil
es. Exemples de langages interpr
et
es : BASIC, scheme, CaML, Tcl, LISP, Perl, Prolog Il existe des langages qui sont a mi-chemin de l'interpr
etation et de la compilation. On les appelle langages P-code ou langages intermediaires. Le code source est traduit (compil
e) dans une forme binaire compacte (du pseudo-code ou p-code) qui n'est pas encore du code machine. Lorsque l'on ex
ecute le programme, ce P-code est interpr
et
e. Par exemple en Java, le source est compil
e pour obtenir un chier (.class) "byte code" qui sera interpr
et
e par une machine virtuelle. Autre langage p-code : Python. Les interpr
eteurs de p-code peuvent ^etre relativement petits et rapides, si bien que le p-code peut s'ex
ecuter presque aussi rapidement que du binaire compil
e 1. En outre les langages p-code peuvent garder la exibilit
e et la puissance des langages interpr
et
es. On ne garde que les avantages !! 1.2 Pourquoi ce cours? Il est
evident qu'il n'est pas n
ecessaire de comprendre comment est
ecrit un compilateur pour savoir comment l'utiliser. De m^eme, un informaticien a peu de chances d'^etre impliqu
e dans la r
ealisation ou m^eme la mainte- nance d'un compilateur pour un langage de programmation majeur. Alors pourquoi ce cours? 1) La "compilation" n'est pas limit
ee a la traduction d'un programme informatique
ecrit dans un langage de haut niveau en un programme directement ex
ecutable par une machine, cela peut aussi ^etre : la traduction d'un langage de programmation de haut niveau vers un autre langage de programmation de haut niveau. Par exemple une traduction de Pascal vers C, ou de Java vers C++, ou de : : : Lorsque le langage cible est aussi un langage de haut niveau, on parle plut^ot de traducteur. Autre di
erence entre traducteur et compilateur: dans un traducteur, il n'y a pas de perte d'informations (on garde les commen- taires, par exemple), alors que dans un compilateur il y a perte d'informations. la traduction d'un langage de programmation de bas niveau vers un autre langage de programmation de haut niveau. Par exemple pour retrouver le code C a partir d'un code compil
e (piratage, r
ecup
eration de vieux logi- ciels, : : :) la traduction d'un langage quelconque vers une autre langage quelconque (ie pas forcemment de program- mation): word vers html, pdf vers ps, : : : Ce genre de travail peut tres bien ^etre con
e a un ing
enieur ma^tre de nos jours. 2) Le but de ce cours est de pr
esenter les principes de base inh
erents a la r
ealisation de compilateurs. Les id
ees et techniques d
evelopp
ees dans ce domaine sont si generales et fondamentales qu'un informaticien (et m^eme un scientique non informaticien) les utilisera tres souvent au cours de sa carriere : traitement de donn
ees, moteurs de recherche, outils sed ou awk, etc. Nous verrons - les principes de base inh
erents a la r
ealisation de compilateurs: analyse lexicale, analyse syntaxique, analyse s
emantique, g
en
eration de code, 1 mais presque seulement : ::: 4  - les outils fondamentaux utilis
es pour eectuer ces analyses : fondements de base de la th
eorie des langages (grammaires, automates, : : :), m
ethodes algorithmiques d'analyse, : : : 3) En outre, comprendre comment est
ecrit un compilateur permet de mieux comprendre les "contraintes" impos
ees par les di
erents langages lorsque l'on
ecrit un programme dans un langage de haut niveau. 1.3 Bibliographie succinte Ce cours s'inspire des livres suivants A. Aho, R. Sethi, J. Ullman, Compilateurs: principes, techniques et outils, InterEditions 1991. N. Silverio, Realiser un compilateur, Eyrolles 1995. R.Wilhelm, D. Maurer, Les compilateurs: theorie, construction, generation, Masson 1994. J. Levine, T. Masson, D. Brown, lex & yacc, E
ditions O'Reilly International Thomson 1995. 5 Chapitre 2 Structure d'un compilateur La compilation se d
ecompose en deux phases : une phase d'analyse, qui va reconna^tre les variables, les instructions, les op
erateurs et
elaborer la structure syntaxique du programme ainsi que certaines propri
et
es s
emantiques une phase de synthese et de production qui devra produire le code cible. 2.1 Phases d'analyse 2.1.1 Analyse lexicale (appel
ee aussi Analyse lineaire) Il s'agit de reconna^tre les "types" des "mots" lus. Pour cela, les caracteres sont regroup
es en unites lexicales (token). L'analyse lexicale se charge de
eliminer les caracteres superus (commentaires, espaces, passages a la ligne, : : :) identier et traiter les parties du texte qui ne font pas partie a proprement parler du programme mais sont des directives pour le compilateur identier les symboles qui repr
esentent des identicateurs, des constantes r
eelles, entieres, cha^nes de caracteres, des op
erateurs (aectation, addition, : : :), des s
eparateurs (parentheses, points virgules, : : :) 1 , les mots clefs du langage, : : : C'est cela que l'on appelle des unites lexicales. Par exemple, a partir du morceau de C suivant : if (i< lettre = A ; Z ja ; z chire = 0 ; 9 >: sep = IDENT = (lettre j sep)( lettre j chire j sep) Remarque IMPORTANTE : toutes les unit
es lexicales ne peuvent pas ^etre exprim
ees par des d
enitions r
egulieres. Par exemple une unit
e lexicale correspondant au modele "toute suite de a et de b de la forme anbn avec n
0 " ne peut pas ^etre exprim
ee par des d
enitions r
egulieres, car ce n'est pas un langage r
egulier (mais c'est un langage que l'on appelle hors contexte, on verra plus tard qu'on peut s'en sortir avec les langages hors contexte et heureusement). Autre exemple : il n'est pas possible d'exprimer sous forme d'ER les systemes de parentheses bien form
es, ie les mots (), (())(), ()(()()(())) : : :. Ce n'est pas non plus un langage r
egulier (donc les commentaires a la Pascal ne forment pas un langage r
egulier). 3.2.2 Attributs Pour ce qui est des symboles =

, l'analyseur syntaxique a juste besoin de savoir que cela corres- pond a l'unit
e lexicale OPREL (op
erateur relationnel). C'est seulement lors de la g
en
eration de code que l'on aura besoin de distinguer < de >= (par exemple). Pour ce qui est des identicateurs, l'analyseur syntaxique a juste besoin de savoir que c'est l'unit
e lexicale IDENT. Mais le g
en
erateur de code, lui, aura besoin de l'adresse de la variable correspondant a cet identicateur. L'ana- lyseur s
emantique aura aussi besoin du type de la variable pour v
erier que les expressions sont s
emantiquement correctes. Cette information suppl
ementaire, inutile pour l'analyseur syntaxique mais utile pour les autres phases du com- pilateur, est appel
ee attribut. 3.2.3 Analyseur lexical R
ecapitulons : le r^ole d'un analyseur lexical est la reconnaissance des unit
es lexicales. Une unit
e lexicale peut (la plupart du temps) ^etre exprim
ee sous forme de d
enitions r
egulieres. 11 Dans la th
eorie des langages, on d
enit des automates qui sont des machines th
eoriques permettant la re- connaissance de mots (voir chapitre 7). Ces machines ne marchent que pour certains types de langages. En particulier : Theoreme 3.9 Un langage regulier est reconnu par un automate ni. Contentons nous pour l'instant de donner un exemple d'automate: Le langage r
egulier d
ecrit par l'ER (abbcjbacc)+c(cjbb) est reconnu par l'automate: a b 1 2 c a b c c 0 3 6 7 b b 4 5 c b 8 a b qui s'
ecrit
egalement
etat a b c 0 1 4 1 2 2 3 3 6 4 5 5 3 6 1 4 7 7 8 7 8 7 Bon, un langage r
egulier (et donc une ER) peut ^etre reconnu par un automate. Donc pour
ecrire un analyseur lexical de notre programme source, il "sut" (: : :) d'
ecrire un programme simulant l'automate. Lorsqu'une unit
e lexicale est reconnue, elle envoy
ee a l'analyseur syntaxique, qui la traite, puis repasse la main a l'analyseur lexical qui lit l'unit
e lexicale suivante dans le programme source. Et ainsi de suite, jusqu'a tomber sur une erreur ou jusqu'a ce que le programme source soit trait
e en entier (et alors on est content). Exemple de morceau d'analyseur lexical pour le langage Pascal (en C) : c = getchar() switch (c) { case ':' : c=getchar() if (c== '=') { unite_lex = AFFECTATION c= getchar() } else unite_lex = DEUX_POINTS break case ' avec VT = f il, elle, parle, est, devient, court, reste, sympa, vite g VN = f PHRASE, PRONOM, VERBE, COMPLEMENT, VERBETAT, VERBACTION g S = PHRASE P = f PHRASE ! PRONOM VERBE COMPLEMENT PRONOM ! il j elle VERBE ! VERBETAT j VERBACTION VERBETAT ! est j devient j reste VERBACTION ! parle j court COMPLEMENT ! sympa j vite g Conventions: l'emploi de lettres capitales est r
eserv
e pour d
enoter des symboles non-terminaux. Les lettres minuscules du d
ebut de l'alphabet sont utilis
ees pour repr
esenter des symboles terminaux. Les lettres minuscules de la n de l'alphabet (t, : : :, z) sont utilis
ees pour indiquer une cha^ne de symboles terminaux. Les lettres grecques d
enotent des cha^nes compos
ees de symboles terminaux et non terminaux. 5.1.2 Arbre de derivation S On appelle derivation l'application d'une ou plusieurs regles a partir d'un mot de (VT VN )+. On notera ! une d
erivation obtenue par application d'une seule regle de production, et ! une d
erivation obte- nue par l'application de n regles de production, ou n
0. Exemples: sur la grammaire de l'exemple 1 S !" S ! aSb aSb ! aaSbb S ! ab S ! aaabbb S ! aaSbb sur la grammaire de l'exemple 2 PHRASE ! SUJET VERBE COMPLEMENT ! elle VERBETAT sympa PHRASE ! il parle vite PHRASE ! elle court sympa Remarque : il est possible de g
en
erer des phrases syntaxiquement correctes mais qui n'ont pas de sens. C'est l'analyse s
emantique qui permettra d'
eliminer ce probleme. Denition 5.3 Etant donnee une grammaire G, on note L(G) le langage genere par G et deni par fw 2 (VT ) tq S ! wg (c'est a dire tous les mots composes uniquement de symboles terminaux (de lettres de l'alphabet) que l'on peut former a partir de S ). L'exemple 1 nous donne L(G) = fanbn
n
0g Denition 5.4 On appelle arbre de derivation (ou arbre syntaxique) tout arbre tel que la racine est l'axiome 19  les feuilles sont des unites lexicales ou " les noeuds sont des symboles non-terminaux les ls d'un noeud  sont 0
: : :
n si et seulement si  ! 0 : : :n est une production  Sla!grammaire Exemple : Soit aTb jc ayant S pour axiome et pour regles de production P = T ! cSS jS Un arbre de d
erivation pour le mot accacbb est : S a T b c S S c a T b S c S ! aT b ! acSSb ! accSb ! accaTbb ! accaSbb ! accacbb (d
erivations gauches) ou S ! aTb ! acSSb ! acSaT bb ! acSaSbb ! acSacbb ! accacbb (d
erivations droites) Ces deux suites dierentes de d
erivations donnent le m^eme arbre de d
erivation. Denition 5.5 Une grammaire est dite ambigue s'il existe un mot de L(G) ayant plusieurs arbres syntaxiques. Remarque : la grammaire pr
ec
edente n'est pas ambigue. 8> instr ! < instr ! if (expr ) if (expr ) instr else instr instr Exemple : Soit G donn
ee par > instr : ! ::: expr ! : : : Cette grammaire est ambigue car le mot m = if (x > 10 ) if (y < 0) a = 1 else a = 0 possede deux arbres syntaxiques di
erents : instr instr if ( expr ) instr if ( expr ) instr else instr x>10 if ( expr ) instr else instr x>10 if ( expr ) instr a=0 y10) if (y< E ! +T E j ; T E j" 0 0 0 0 >> TT !!FTFT j=FT j" 0 avec le mot w = 3  4 + 10  (5 + 11)=34 + 12 : F ! (E)j nb 0 0 0 Pf... Alors la on ne voit plus rien du tout !! Conclusion: ce qui serait pratique, ca serait d'avoir une table qui nous dit: quand je lis tel caractere et que j'en suis a d
eriver tel symbole non-terminal, alors j'applique telle regle et je ne me pose pas de questions. C a existe, et ca s'appelle une table d'analyse. 5.3.2 Table d'analyse LL(1) Pour construire une table d'analyse, on a besoin des ensembles PREMIER et SUIVANT Calcul de PREMIER Pour toute cha^ne  compos
ee de symboles terminaux et non-terminaux, on cherche PREMIER() : l'ensemble de tous les terminaux qui peuvent commencer une cha^ne qui se d
erive de  C'est a dire que l'on cherche toutes les lettres a telles qu'il existe une d
erivation  ! a (
etant une cha^ne quelconque compos
ee de symboles terminaux et non-terminaux). 8: Exemple < S ! Ba : BP !! dS cP jbP jP j" S ! a, donc a 2 PREMIER(S) S ! cPa, donc c 2 PREMIER(S) S ! bPa, donc b 2 PREMIER(S) S ! dSa, donc d 2 PREMIER(S) Il n'y a pas de d
erivation S ! " Donc PREMIER(S)= fa
b
c
dg B ! dS, donc d 2 PREMIER(B) aB ! a, donc PREMIER(aB)= fag BSb ! ab, donc a 2 PREMIER(BS) Algorithme de construction des ensembles PREMIER : 1. Si X est un non-terminal et X ! Y1 Y2 : : :Yn est une production de la grammaire (avec Yi symbole terminal ou non-terminal) alors ajouter les
el
ements de PREMIER(Y1 ) sauf " dans PREMIER(X) s'il existe j (j 2 f2
: : :
ng) tel que pour tout i = 1
: : :
j ; 1 on a " 2PREMIER(Yi ), alors ajouter les
el
ements de PREMIER(Yj ) sauf " dans PREMIER(X) si pour tout i = 1
: : :
n " 2PREMIER(Yi), alors ajouter " dans PREMIER(X) 2. Si X est un non-terminal et X ! " est une production, ajouter " dans PREMIER(X) 3. Si X est un terminal, PREMIER(X) = fX g. Recommencer jusqu'a ce qu'on n'ajoute rien de nouveau dans les ensembles PREMIER. 8> 1E: ! T E0 Exemple >< E0 ! +T E0j ; T E0j" >> TT 0!!FTFT0 0j=FT 0j" : F ! (E)j nb PREMIER(E) = PREMIER(T ) = f(
nbg PREMIER(E 0 ) = f+
;
"g PREMIER(T ) = PREMIER(F ) = f(
nbg PREMIER(T 0 ) = f
=
"g PREMIER(F) = f(
nbg Exemple 8> 2S: ! ABCe < A ! aAj" >: B ! bBjcBj" C ! dejdajdA 22  PREMIER(S) = fa
b
c
dg PREMIER(A) = fa
"g PREMIER(B) = fb
c
"g PREMIER(C) = fdg Calcul de SUIVANT Pour tout non-terminal A, on cherche SUIVANT(A) : l'ensemble de tous les symboles terminaux a qui peuvent appara^tre imm
ediatement a droite de A dans une d
erivation: S ! Aa 8: Exemple < S ! ScjBa : BP !! dSBPajbPbjP j" a
b
c
2SUIVANT(S) car il y a les d
erivations S ! Sc, S ! dSa et S ! bdSba d 2SUIVANT(B) car S ! BdSaa Algorithme de construction des ensembles SUIVANT : 1. Ajouter un marqueur de n de cha^ne (symbole $ par exemple) a SUIVANT(S) (ou S est l'axiome de d
epart de la grammaire) 2. Pour chaque production A ! B ou B est un non-terminal, alors ajouter le contenu de PREMIER() a SUIVANT(B), sauf " 3. Pour chaque production A ! B, alors ajouter SUIVANT(A) a SUIVANT(B) 4. Pour chaque production A ! B avec " 2PREMIER(), ajouter SUIVANT(A) a SUIVANT(B) Recommencer a partir de l'
etape 3 jusqu'a ce qu'on n'ajoute rien de nouveau dans les ensembles SUIVANT. 8> 1E: ! T E0 Exemple >< E0 ! +T E0j ; T E0j" >> TT 0!!FTFT0 0j=FT 0j" : F ! (E)j nb SUIVANT(E) = f $
) g SUIVANT(E 0 ) = f $
) g SUIVANT(T) = f +
;
)
$ g SUIVANT(T 0 ) = f +
;
)
$ g SUIVANT(F) = f 
=
)
+
;
$ g Exemple 8< S ! aSbjcdjSAe 2 : : AB !! aAdB bb j" PREMIER SUIVANT S ac $bae A a" ed B b ed Construction de la table d'analyse LL Une table d'analyse est un tableau M a deux dimensions qui indique pour chaque symbole non-terminal A et chaque symbole terminal a ou symbole $ la regle de production a appliquer. Pour chaque production A !  faire 1. pour tout a 2PREMIER() (et a 6= "), rajouter la production A !  dans la case M%A
a] 2. si " 2PREMIER(), alors pour chaque b 2SUIVANT(A) ajouter A !  dans M%A
b] Chaque case M%A
a] vide est une erreur de syntaxe Avec notre exemple (grammaire ETF), on obtient la table gure 5.1 5.3.3 Analyseur syntaxique Maintenant qu'on a la table, comment l'utiliser pour d
eterminer si un mot m donn
e est tel que S ! m? On utilise une pile. 23  nb + ;  = ( ) $ E E ! TE 0 E ! TE 0 E0 E 0 ! +TE 0 E 0 ! ;TE 0 E0 ! " E0 ! " T T ! FT 0 T ! FT 0 T0 T0 ! " T0 ! " T 0 ! FT 0 T 0 ! =F T 0 T0 ! " T0 ! " F F ! nb F ! (E) Fig. 5.1 - Table LL de la grammaire ETF Algorithme: donn
ees : mot m termin
e par $, table d'analyse M initialisation de la pile : S et un pointeur ps sur la 1ere lettre de m $ repeter Soit X le symbole en sommet de pile Soit a la lettre point
ee par ps Si X est un non terminal alors Si M%X
a] = X ! Y1 : : :Yn alors enlever X de la pile mettre Yn puis Yn;1 puis : : :puis Y1 dans la pile
emettre en sortie la production X ! Y1 : : :Yn sinon (case vide dans la table) ERREUR nsi Sinon Si X =$ alors Si a = $ alors ACCEPTER Sinon ERREUR nsi Sinon Si X = a alors enlever X de la pile avancer ps sinon ERREUR nsi nsi nsi jusqu'a ERREUR ou ACCEPTER$ Sur l'exemple E
E 0
T
T 0
F, soit le mot m = 3 + 4  5 PILE Entr
ee Sortie $E 3 + 4  5$ E ! TE 0 $ E 0T 3 + 4  5$ T ! FT 0 $ E 0T 0 F 3 + 4  5$ F ! nb $ E 0T 0 3 3 + 4  5$ $ E 0T 0 +4  5$ T0 ! " $ E0 +4  5$ E 0 ! +TE 0 $ E 0T+ +4  5$ $ E 0T 4  5$ T ! FT 0 $ E 0T 0 F 4  5$ F ! nb $ E 0T 0 4 4  5$ $ E 0T 0 5$ T 0 ! FT 0 $ E 0T 0 F  5$ $ E 0T 0 F 5$ F ! nb $ E 0T 0 5 5$ $ E 0T 0 $ T0 ! " $ E0 $ E0 ! " $ $ ACCEPTER (analyse syntaxique r
eussie) 24  E T E’ F T’ + T E’ 3 F T’ 4 * F T’ 5 Fig. 5.2 - Arbre syntaxique pour 3 + 4  5 On obtient donc l'arbre syntaxique de la gure 5.2. Si l'on essaye d'analyser maintenant le mot m = (7 + 3)5 PILE Entr
ee Sortie $E (7 + 3)5$ E ! TE 0 $ E 0T (7 + 3)5$ T ! FT 0 $ET F 0 0 (7 + 3)5$ F ! (E) $ E 0T 0 )E( (7 + 3)5$ $ E 0T 0 )E 7 + 3)5$ E ! TE 0 $ E T )E T 0 0 0 7 + 3)5$ T ! FT 0 $ E T )E T F 7 + 3)5$ F ! 7 0 0 0 0 $ E 0T 0 )E 0 T 07 7 + 3)5$ $ E 0T 0 )E 0 T 0 +3)5$ T 0 ! " $ E T )E 0 0 0 +3)5$ E 0 ! * T E' $ E T )E T + 0 0 0 +3)5$ $ E 0T 0 )E 0 T 3)5$ T ! FT 0 $ E T )E T F 0 0 0 0 3)5$ F ! 3 $ E 0T 0 )E 0 T 03 3)5$ $ E 0T 0 )E 0 T 0 )5$ T 0 ! " $ E T )E 0 0 0 )5$ E 0 ! " $ET ) 0 0 )5$ $ E 0T 0 5$ ERREUR !! Donc ce mot n'appartient pas au langage g
en
er
e par cette grammaire. 5.3.4 Grammaire LL(1) L'algorithme pr
ec
edent ne peut pas ^etre appliqu
e a toutes les grammaires. En eet, si la table d'analyse comporte des entr
ees multiples (plusieurs productions pour une m^eme case M%A
a]), on ne pourra pas faire une telle analyse descendante car on ne pourra pas savoir quelle production appliquer. Denition 5.6 On appelle grammaire LL(1) une grammaire pour laquelle la table d'analyse decrite prece- demment n'a aucune case denie de facon multiple. Le terme "LL(1)" signie que l'on parcourt l'entr
ee de gauche a droite (L pour Left to right scanning), que l'on utilise les d
erivations gauches (L pour Leftmost derivation), et qu'un seul symbole de pr
e-vision est n
ecessaire a chaque
etape n
ecessitant la prise d'une d
ecision d'action d'analyse (1).  S !nous Par exemple, aAb avons d
eja vu la grammaire A ! cdjc Nous avons PREMIER(S) = fag, PREMIER(A) = fcg, SUIVANT(S) = f$g et SUIVANT(A) = fbg, ce qui donne la table d'analyse 25  a c b d $ S S ! aAb A A ! cd A!c Il y a deux r
eductions pour la case M%A
c], donc ce n'est pas une grammaire LL(1). On ne peut pas utiliser cette m
ethode d'analyse. En eet, on l'a d
eja remarqu
e, pour pouvoir choisir entre la production A ! cd et la produc- tion A ! c, il faut lire la lettre qui suit celle que l'on pointe (donc deux symboles de pr
e-vision sont n
ecessaires) 1. Autre exemple : S ! aT bbbb n'est pas LL(1) T ! Tbj" Theoreme 5.7 Une grammaire ambigue ou recursive a gauche ou non factorisee a gauche n'est pas LL(1) "Ambigue", on a d
eja vu, on sait ce que ca veut dire. Voyons les autres termes. 5.3.5 Recursivite a
gauche Denition 5.8 Une grammaire est immediatement recursive a gauche si elle contient un non-terminal A tel qu'il existe une production A ! A ou  est une cha^
ne quelconque. 8: Exemple < S ! ScAjB : AB !! Aa j" Bbjdje Cette grammaire contient plusieurs r
ecursivit
es a gauche imm
ediates. Eliminitation de la recursivite a gauche immediate: Remplacer toute regle de la forme A ! Aj par A ! A0 A0 ! A0 j" Theoreme 5.9 La grammaire ainsi obtenue reconnait le m^eme langage que la grammaire initiale. 8> S ! BS Sur l'exemple, on obtient : >>< S0 ! cAS 0 0 j" A!A 0 >> A0 ! aA00j" 0 >: BB0!!dBbB0jjeB" Cette grammaire reconnait le m^eme langage que la premiere. Par exemple, le mot dbbcaa s'obtient a partir de la premiere grammaire par les d
erivations S ! ScA ! BcA ! BbcA ! BbbcA ! dbbcA ! dbbcAc ! dbbcAaa ! dbbcaa. Il s'obtient a partir de la deuxieme grammaire par S ! BS 0 ! dB 0S 0 ! dbB 0S 0 ! dbbB 0 S 0 ! dbbS 0 ! dbbcAS 0 ! dbbcA0S 0 ! dbbcaA0S 0 ! dbbcaaA0S 0 ! dbbcaaS 0 ! dbbcaa. Remarque : ici on peut se passer de A'. C'est a dire en fait que S ! Sj" est
equivalent a S ! S j" (qui, elle, n'est pas imm
ediatement r
ecursive a gauche, mais a droite, ce qui n'a rien a voir). Denition 5.10 Une grammaire est recursive a gauche si elle contient un non-terminal A tel qu'il existe une derivation A ! + A ou  est une cha^
ne quelconque.  S ! Aajb Exemple : A ! AcjSdjc Le non-terminal S est r
ecursif a gauche car S ! Aa ! Sda (mais il n'est pas imm
ediatement r
ecursif a gauche). 1 en fait, c'est une grammaire LL(2) : 26 Eliminitation de la recursivite a gauche pour toute grammaire sans regle A ! ": Ordonner les non-terminaux A1
A2
: : :
An Pour i=1 a n faire pour j=1 a i-1 faire remplacer chaque production de la forme Ai ! Aj  ou Aj ! 1 j : : : jp par Ai ! 1 j : : : jp  n pour
eliminer les r
ecursivit
es a gauche imm
ediates des productions Ai n pour Theoreme 5.11 La grammaire ainsi obtenue reconnait le m^eme langage que la grammaire initiale. Sur l'exemple: On ordonne S
A i = 1 pas de r
ecursivit
e imm
ediate dans S ! Aajb i = 2 et j = 1 on obtient A ! AcjAadjbdj" on
elimine la rec. imm
ediate: A ! bdA0jcA0 A0 ! cA0 jadA0j" Bref, on8 a obtenu la grammaire: < S ! Aajb0 0 : AA0!!bdA jA cA0 jadA0j"  S !exemple Autre SajTScjd : T ! TbT j" 8On obtient la grammaire: >< S0! TScS0 0 jdS0 S ! aS j" >: T 0! T 0 0 T ! bTT j" Or on a S ! TScS 0 ! T 0 ScS 0 ! ScS 0 damned une r
ecursivit
e a gauche !!!! Eh oui, l'algo ne marche pas toujours lorsque la grammaire possede une regle A ! " ! 5.3.6 Grammaire propre Denition 5.12 Une grammaire est dite propre si elle ne contient aucune production A ! " Comment rendre une grammaire propre? En rajoutant une production dans laquelle le A est remplac
e par ", ceci pour chaque A appara^ssant en partie droite d'une production, et pour chaque A d'un A ! ". 8< S ! aTb Exemple : jaU 8< S ! aT bjabjaU : TU !! bTaTA aU jb j" devient : TU !! bTaT aU jb AjbaTAjbTaAjbaA 5.3.7 Factorisation a
gauche L'id
ee de base est que pour d
evelopper un non-terminal A quand il n'est pas
evident de choisir l'alternative a utiliser (ie quelle production prendre), on doit r
e
ecrire les productions de A de facon a dierer la d
ecision jusqu'a ce que susamment de texte ait
et
e lu pour faire le bon choix. 8> S ! bacdAbdjbacdBcca >< A ! aD Exemple : > B ! cE >: C ! : : : E ! ::: Au d
epart, pour savoir s'il faut choisir S ! bacdAbd ou S ! bacdBcca, il faut avoir lu la 5ieme lettre du mot (un a ou un c). On ne peut donc pas des le d
epart savoir quelle production prendre. Ce qui est incompatible avec une grammaire LL(1). (Remarque: mais pas avec une grammaire LL(5), mais ce n'est pas notre probleme.) Factorisation a gauche : 27  Pour chaque non-terminal A trouver le plus long pr
exe  commun a deux de ses alternatives ou plus Si  6= , remplacer A ! 1 j : : : jnj 1 j : : : j p (ou les i ne commencent pas par ) par A ! A0j 1 j : : : j p A0 ! 1 j : : : jn 8< S ! aEbSjusqu'a Recommencer ne plus en trouver. jaEbSeB ja Exemple : : E ! bcB jbca B ! ba 8> S ! aEbSS0 ja >< S0 ! eBj0" Factoris
ee a gauche, cette grammaire devient : E ! bcE >>: E0 ! Bja B ! ba 5.3.8 Conclusion Si notre grammaire est LL(1), l'analyse syntaxique peut se faire par l'analyse descendante vue ci-dessus. Mais comment savoir que notre grammaire est LL(1)? 2 Etant donn
ee une grammaire 1. la rendre non ambigue. Il n'y a pas de m
ethodes. Une grammaire ambigue est une grammaire qui a
et
e mal concue. 2.
eliminer la r
ecursivit
e a gauche si n
ecessaire 3. la factoriser a gauche si n
ecessaire 4. construire la table d'analyse Il ne reste plus qu'a esp
erer que ca soit LL(1). Sinon, il faut concevoir une autre m
ethode pour l'analyse syn- taxique 3. Exemple : grammaire des expressions arithm
etiques avec les op
erateurs + ; = et  E ! E + E jE ; E jE  E jE=oE j(E)jnb Mais elle est ambigue. Pour lever l'ambigut
e, on considere les priorit
es classiques des op
erateurs et on obtient 8< E !non la grammaire ambigue : E + T j E ; T jT : TF !! T(E) jFnbjT=F jF Apres 8 suppression de la r
ecursivit
e a gauche, on obtient < E0! T E0 0 0 T 0 ! FT 0j=FT 0j" : TE !!F+TT 0 E j ; T E j" F ! (E)j nb Inutile de factoriser a gauche. Cette grammaire est LL(1) (c'est l'exemple que l'on a utilis
e tout le temps). Autre exemple : la grammaire S ! aT bj" n'est pas LL(1). Or elle n'est pas r
ecursive a gauche, elle est factoris
ee a gauche et elle T ! cSajd n'est pas ambigue ! 5.4 Analyse ascendante Principe : construire un arbre de d
erivation du bas (les feuilles, ie les unit
es lexicales) vers le haut (la racine, ie l'axiome de d
epart). Le modele g
en
eral utilis
e est le modele par decallages-reductions. C'est a dire que l'on ne s'autorise que deux op
erations : { decallage (shift) : d
ecaller d'une lettre le pointeur sur le mot en entr
ee { reduction (reduce) : r
eduire une cha^ne (suite cons
ecutive de terminaux et non terminaux a gauche du pointeur sur le mot en entr
ee et nissant sur ce pointeur) par un non-terminal en utilisant une des regles de production 2 Attention, le th
eoreme 5.7 ne dit pas que tout grammaire non ambigue, non r
ecursive a gauche et factoris
ee a gauche est : LL(1). 3 si la grammaire est LL(k), on peut utiliser une m
ethode descendante en modiant l
egerement la d
enition des ensembles : PREMIER et SUIVANT (cf exercices) 28  a a a c b a a c b c b c b c b a c b c S S S S S S S S S S S S S Fig. 5.3 - Analyse ascendante Exemple : S ! aSbS jc avec le mot u = aacbaacbcbcbacbc a acbaacbcbcbacbc on ne peut rien reduire, donc on decalle a a cbaacbcbcbacbc on ne peut rien r
eduire, donc on d
ecalle aa c baacbcbcbacbc ah ! On peut r
eduire par S ! c aa S baacbcbcbacbc on ne peut rien r
eduire, donc on d
ecalle ::: aaSbaa c bcbcbacbc on peut utiliser S ! c aaSbaa S bcbcbacbc on ne peut rien r
eduire, donc on d
ecalle aaSbaaS b cbcbacbc on ne peut rien r
eduire, donc on d
ecalle aaSbaaSb c bcbacbc On peut utiliser S ! c aaSbaaSb S bcbacbc On peut utiliser S ! aSbS aaSba S bcbacbc d
ecallage aaSbaS b cbacbc d
ecallage aaSbaSb c bacbc r
eduction par S ! c aaSbaSb S bacbc r
eduction par S ! aSbS aaSb S bacbc r
eduction par S ! aSbS a S bacbc d
ecallage aS b acbc d
ecallage aSb a cbc d
ecallage aSba c bc r
eduction par S ! c aSba S bc d
ecallage aSbaS b c d
ecallage aSbaSb c r
eduction par S ! c aSbaSb S r
eduction par S ! aSbS aSb S r
eduction par S ! aSbS S termine!!!! On a gagn
e, le mot est bien dans le langage. En m^eme temps, on a construit l'arbre (gure 5.3). Conclusion: ca serait bien d'avoir une table qui nous dit si on d
ecalle ou si on r
eduit, et par quoi, lorsque le pointeur est sur une lettre donn
ee. Table d'analyse SLR (on l'appelle comme ca parce que, de m^eme que la m
ethode descendante vue pr
ec
edemment ne permettait d'ana- lyser que les grammaires LL(1), cette m
ethode va permettre d'analyser les grammaires dites LR). Cette table va nous dire ce qu'il faut faire quand on lit une lettre a et qu'on est dans un
etat i - soit on decalle. Dans ce cas, on empile la lettre lue et on va dans un autre
etat j. Ce qui sera not
e dj - soit on reduit par la regle de production num
ero p, c'est a dire qu'on remplace la cha^ne en sommet de pile (qui correspond a la partie droite de la regle num
ero p) par le non-terminal de la partie gauche de la regle de production, et on va dans l'
etat j qui d
epend du non-terminal en question. On note ca rp - soit on accepte le mot. Ce qui sera not
e ACC - soit c'est une erreur. Case vide 29 Construction de la table d'analyse : utilise aussi les ensembles SUIVANT ( et donc PREMIER), plus ce qu'on appelle des fermetures de 0-items. Un 0-item (ou plus simplement item) est une production de la gram- maire avec un "." quelque part dans la partie droite. Par exemple (sur la gram ETF) : E ! E: + T ou encore T ! F: ou encore F ! :(E) Fermeture d'un ensemble d'items I : 1- Mettre chaque item de I dans Fermeture(I) 2- Pour chaque item i de Fermeture(I) de la forme A ! :B pour chaque production B ! rajouter (s'il n'y est pas d
eja) l'item B ! : dans Fermeture(I) npour npour 3- Recommencer 2 jusqu'a ce qu'on n'ajoute rien de nouveau Exemple: soit la grammaire ETF (des expressions arithm
etiques) (1) E ! E + T (3) T ! T  F (5) F ! (E) (2) E ! T (4) T ! F (6) F ! nb et soit l'ensemble d'items fT ! T  :F
E ! E: + T g. La fermeture de cet ensemble d'items est : fT ! T  :F
E ! E: + T
F ! :nb
F ! :(E)g Transition par X d'un ensemble d'items I : )(I
X) =Fermeture(tous les items A ! X:) ou A ! :X 2 I Sur l'exemple ETF : Soit l'ensemble d'items I = fT ! T  :F
E ! E: + T
F ! :nb
F ! :(E)g, on aura )(I
F ) = fT ! T  F:g )(I
+) = fE ! E + :T
T ! :T  F
T ! :F
F ! :nb
F ! :(E)g etc. Collection des items d'une grammaire: 0- Rajouter l'axiome S 0 avec la production : S 0 ! S 1- I0 Fermeture(fS 0 ! :S g) Mettre I0 dans Collection 2- Pour chaque I 2 Collection Pour chaque X tq )(I
X) est non vide ajouter )(I
X) dans Collection npour npour 3- Recommencer 2 jusqu'a ce qu'on n'ajoute rien de nouveau Toujours sur la grammaire ETF : I0 = fS ! :E
E ! :E + T
E ! :T
T ! :T  F
T ! :F
F ! :nb
F ! :(E)g )(I0
E) = fS 0 ! E:
E ! E: + T g = I1 (terminal pour la regle S 0 ! E) )(I0
T) = fE ! T:
T ! T:  F g = I2 (terminal pour la regle 2) )(I0
F ) = fT ! F:g = I3 (terminal pour la regle 4) )(I0
() = fF ! (:E)
E ! :E + T
E ! :T
T ! :T  F
T ! :F
F ! :nb
F ! :(E)g = I4 )(I0
nb) = fF ! nb:g = I5 (terminal pour la regle 6) )(I1
+) = fE ! E + :T
T ! :T  F
T ! :F
F ! :nb
F ! :(E)g = I6 )(I2
) = fT ! T  :F
F ! :nb
F ! :(E)g = I7 )(I4
E) = fF ! (E:)
E ! E: + T g = I8 )(I4
T) = fE ! T:
T ! T:  F g = I2 d
eja vu, ouf )(I4
F) = fT ! F:g = I3 )(I4
nb) = fF ! nb:g = I5 )(I4
() = fF ! (:E)
E ! :E + T
E ! :T
T ! :T  F
T ! :F
F ! :nb
F ! :(E)g = I4 )(I6
T) = fE ! E + T:
T ! T:  F g = I9 (terminal pour regle 1) )(I6
F) = I3 )(I6
nb) = I5 )(I6
() = I4 )(I7
F ) = fT ! T  F:g = I10 (terminal pour regle 3) )(I7
nb) = I5 )(I7
() = I4 )(I8
)) = fF ! (E):g = I11 (terminal pour regle 5) 30 )(I8
+) = fE ! E + :T
T ! :T  F
T ! :F
F ! :nb
F ! :(E)g = I6 )(I9
) = I7 OUFFFFFF : : :! Construction de la table d'analyse SLR : 1- Construire la collection d'items fIo
: : :
In g 2- l'
etat i est contruit a partir de Ii : a) pour chaque )(Ii
a) = Ij : mettre decaller j dans la case M%i
a] b) pour chaque )(Ii
A) = Ij : mettre aller en j dans la case M%i
A] c) pour chaque A ! : (sauf A = S 0 ) contenu dans Ii : mettre reduire A !  dans chaque case M%i
a] ou a 2SUIVANT(A) d) si S 0 ! S: 2 Ii : mettre accepter dans la case M%i
$] Toujours le m^eme exemple: il nous faut les SUIVANT (et PREMIER) : PREMIER SUIVANT E nb ( $+) T nb ( $+*) F nb ( $+*) et donc la table d'analyse LR de cette grammaire est
etat nb +  ( ) $ E T F 0 d5 d4 1 2 3 1 d6 ACC 2 r2 d7 r2 r2 3 r4 r4 r4 r4 4 d5 d4 8 2 3 5 r6 r6 r6 r6 6 d5 d4 9 3 7 d5 d4 10 8 d6 d11 9 r1 d7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Analyseur syntaxique: On part de l'
etat 0 et on empile et d
epile non seulement les symboles (comme lors de l'analyseur LL) mais aussi les etats successifs. Exemple : l'analyse du mot m = 3 + 4$ est donn
ee gure 5.4. La gure 5.5 donne l'analyse du mot 3 + 4  2$. On peut aussi dessiner l'arbre obtenu (gure 5.6) pile entr
ee action $0 3 + 4$ d5 $035 +  4$ r6 : F ! nb $0F +  4$ je suis en 0 avec F : je vais en 3 $0F 3 +  4$ r4 : T ! F $0T +  4$ je suis en 0 avec T : je vais en 2 $0T 2 +  4$ r2 : E ! T $0E +  4$ je suis en 0 avec E : je vais en 1 $0E1 +  4$ d6 $0E1+6 4$ ERREUR !! Ce mot n'appartient pas au langage. Fig. 5.4 - Analyse LR du mot m = 3 + 4$ Remarques Cette m
ethode permet d'analyser plus de grammaires que la m
ethode descendante (car il y a plus de grammaires qui sont LR que de grammaires qui sont LL(1)) En TP on va utiliser un outil (bison) qui construit tout seul une table d'analyse LR (LALR en fait, mais c'est presque pareil) a partir d'une grammaire donn
ee. Dans cette m
ethode d'analyse (LR), ca n'a strictement aucune importance que la grammaire soit r
ecursive a gauche, m^eme au contraire, elle prefere. 31 pile entr
ee action $0 3 + 4  2$ d5 $035 +4  2$ r6 : F ! nb $0F +4  2$ je suis en 0 avec F : je vais en 3 $0F 3 +4  2$ r4 : T ! F $0T +4  2$ je suis en 0 avec T : je vais en 2 $0T 2 +4  2$ r2 : E ! T $0E +4  2$ je suis en 0 avec E : je vais en 1 $0E1 +4  2$ d6 $0E1+6 4  2$ d5 $0E1+645 2$ r6 : F ! nb $0E1+6F 2$ je suis en 6 avec F : je vais en 3 $0E1+6F3 2$ r4 : T ! F $0E1+6T 2$ en 6 avec T : je vais en 9 $0E1+6T9 2$ d7 $0E1+6T97 2$ d5 $0E1+6T9725 $ r6 : F ! nb $0E1+6T97F $ en 7 avec F : je vais en 10 $ 0 E 1 + 6 T 9  7 F 10 $ r3 : T ! T  F $0E1+6T $ en 6 avec T : je vais en 9 $0E1+6T9 $ r1 : E ! E + T $0E $ en 0 avec E : je vais en 1 $0E1 $ ACCEPTE
!!! Fig. 5.5 - Analyse LR du mot m = 3 + 4  2$ 3 + 4 * 2 F F F T T E T E Fig. 5.6 - arbre de derivation du mot 3 + 4  2 32  Les grammaires ambigues provoquent des conits - conit d
ecallage/r
eduction : on ne peut pas d
ecider a la lecture du terminal a s'il faut r
eduire une production S !  ou d
ecaller le terminal - conit r
eduction/r
eduction : on ne peut pas d
ecider a la lecture du terminal a s'il faut r
eduire une production S !  ou une production T !  On doit alors r
esoudre les conits en donnant des priorites aux actions (d
ecaller ou r
eduire) et aux productions. Par exemple, soit la grammaire E ! E + E jE  E jnb Soit a analyser 3 + 4 + 5. Lorsqu'on lit le 2ieme + on a le choix entre - r
eduire ce qu'on a d
eja lu par E ! E + E. Ce qui nous donnera nalement le calcul (3 + 4) + 5 - d
ecaller ce +, ce qui nous donnera nalement le calcul 3 + (4 + 5). Ici on s'en cague car c'est pareil. Mais bon, + est associatif a gauche, donc on pr
eferera r
eduire. Soit a analyser 3+ 4  5. Lorsqu'on lit le  on a encore un choix shift/reduce. Si l'on r
eduit on calcule (3 + 4)  5, si on d
ecalle on calcule 3 + (4  5)! On ne peut plus s'en foutre ! Il faut d
ecaller. Soit a analyser 3  4 + 5. On ne s'en fout pas non plus, il faut r
eduire ! Bref, il faut mettre qlqpart dans l'analyseur le fait que  est prioritaire sur +. Tout ceci se(0)voitS dans !E la table d'analyse quand on essaye de la faire : (2) E ! E  E (1) E ! E + E (3) E ! nb I0 = fS ! :E
E ! :E + E
E ! :E  E
E ! :nbg )(I0
E) = fS ! E:
E ! E: + E
E ! E:  E g = I1 r0 )(I0
nb) = fE ! nb:g = I2 r3 )(I1
+) = fE ! E + :E
E ! :E + E
E ! :E  E
E ! :nbg = I3 )(I1
) = fE ! E  :E
E ! :E + E
E ! :E  E
E ! :nbg = I4 )(I3
E) = fE ! E + E:
E ! E: + E
E ! E:  E
g = I5 )(I3
nb) = I2 )(I4
E) = fE ! E  E:
E ! E: + E
E ! E:  E
g = I6 )(I4
nb) = I2 )(I5
+) = )(I6
+) = I3 et )(I5
) = )(I6
) = I4 Comme Suivant(E)= f+

$g on obtient la table avec les conits :
etat nb +  $ E 0 d2 1 1 d3 d4 ACC 2 r3 r3 r3 3 d2 5 4 d2 6 5 d3 d4 r1 r1 r1 6 d3 d4 r2 r2 r2 C'est exactement ce qu'on vient de dire. 5.5 Erreurs syntaxiques Beaucoup d'erreurs sont par nature syntaxiques (ou r
ev
el
ees lorsque les unit
es lexicales provenant de l'analyseur lexical contredisent les regles grammaticales). Le gestionnaire d'erreur doit - indiquer la pr
esence de l'erreur de facon claire et pr
ecise - traiter l'erreur rapidement pour continuer l'analyse - traiter l'erreur le plus ecacement possible de maniere a ne pas en cr
eer de nouvelles. Heureusement, les erreurs communes (confusion entre deux s
eparateurs (par exemple entre  et ,), oubli de , : : :) sont simples et un m
ecanisme simple de traitement sut en g
en
eral. Cependant, une erreur peut se produire longtemps avant d'^etre d
etect
ee (par exemple l'oubli d'un f ou g dans un programme C). La nature de l'erreur est alors tres dicile a d
eduire. La plupart du temps, le gestionnaire d'erreurs doit deviner ce que le programmeur avait en t^ete. Lorsque le nombre d'erreur devient trop important, il est plus raisonnable de stopper l'analyse 4. Il existe plusieurs strat
egies de r
ecup
eration sur erreur : mode panique, au niveau du syntagme 5, productions d'erreur, correction globale. Une r
ecup
eration inad
equate peut provoquer une avalanche n
efastes d'erreurs illegi- times, c'est a dire d'erreurs qui n'ont pas
et
e faites par le programmeur mais sont la cons
equence du changement 4 par exemple quel doit ^etre le comportement d'un compilateur C confront
e a un programme en Caml? : 5 syntagme, priez pour nous : ::: 33  d'
etat de l'analyseur lors de la r
ecup
eration sur erreur. Ces erreurs ill
egitimes peuvent ^etre syntaxiques mais
egalement s
emantiques. Par exemple, pour se r
ecup
erer d'une erreur, l'analyseur syntaxique peut sauter la d
e- claration d'une variable. Lors de l'utilisation de cette variable, l'analyseur s
emantique indiquera qu'elle n'a pas
et
e d
eclar
ee. 5.5.1 Recuperation en mode panique C'est la m
ethode la plus simple a implanter. Quand il d
ecouvre une erreur, l'analyseur syntaxique
elimine les symboles d'entr
ee les uns apres les autres jusqu'a en rencontrer un qui appartienne a un ensemble d'unit
es lexi- cales de synchronisation, c'est a dire (par exemple) les d
elimiteurs (, end ou g), dont le r^ole dans un programme source est clair. Bien que cette m
ethode saute en g
en
eral une partie consid
erable du texte source sans en v
erier la validit
e, elle a l'avantage de la simplicit
e et ne peut pas entrer dans une boucle innie. 5.5.2 Recuperation au niveau du syntagme Quand une erreur est d
ecouverte, l'analyseur syntaxique peut eectuer des corrections locales. Par exemple, remplacer une , par un , un wihle par un while, ins
erer un  ou une (, : : :Le choix de la modication a faire n'est pas
evident du tout du tout en g
en
eral. En outre, il faut faire attention a ne pas faire de modications qui entrainerait une boucle innie (par exemple d
ecider d'ins
erer systematiquement un symbole juste avant le symbole courant). L'inconv
enient majeure de cette m
ethode est qu'il est pratiquement impossible de g
erer les situations dans les- quelles l'erreur r
eelle s'est produite bien avant le point de d
etection. On implante cette r
ecup
eration sur erreur en remplissant les cases vides des tables d'analyse par des pointeurs vers des routines d'erreur. Ces routines remplacent, ins
erent ou suppriment des symboles d'entr
ee et
emettent les messages appropri
es. Exemple: grammaire des expressions arithm
etiques (1) E ! E + E (3) E ! (E) (2) E ! E  E (4) E ! nb La table d'analyse LR avec routines d'erreur est
etat nb +  ( ) $ E 0 d3 e1 e1 d2 e2 e1 1 1 e3 d4 d5 e3 e2 ACC 2 d3 e1 e1 d2 e2 e1 6 3 r4 r4 r4 r4 r4 r4 4 d3 e1 e1 d2 e2 e1 7 5 d3 e1 e1 d2 e2 e1 8 6 e3 d4 d5 e3 d9 e4 7 r1 r1 d5 r1 r1 r1 8 r2 r2 r2 r2 r2 r2 9 r3 r3 r3 r3 r3 r3 Les routines d'erreur
etant : e1 : (routine appel
ee depuis les
etats 0, 2, 4 et 5 lorsque l'on rencontre un op
erateur ou la n de cha^ne d'entr
ee alors qu'on attend un op
erande ou une parenthese ouvrante) Emettre le diagnostic operande manquant Empiler un nombre quelconque et aller dans l'
etat 3 e2 : (routine appel
ee depuis les
etats 0,1,2,4 et 5 a la vue d'une parenthese fermante) Emettre le diagnostic parenthese fermante excedentaire Ignorer cette parenthese fermante e3 : (routine appel
ee depuis les
etats 1 ou 6 lorsque l'on rencontre un nombre ou une parenthese fermante alors que l'on attend un op
erateur) Emettre le diagnostic operateur manquant Empiler + (par exemple) et aller a l'
etat 4 e4 : (routine appel
ee depuis l'
etat 6 qui attend un op
erateur ou une parenthes fermante lorsque l'on rencontre la n de cha^ne) Emettre le diagnostic parenthese fermante oubliee Empiler une parenthese fermante et aller a l'
etat 9 34 5.5.3 Productions d'erreur Si l'on a une id
ee assez pr
ecise des erreurs courantes qui peuvent ^etre rencontr
ees, il est possible d'augmenter la grammaire du langage avec des productions qui engendrent les constructions erron
ees. Par exemple (pour un compilateur C) : I ! if E I (erreur : il manque les parentheses) I ! if ( E ) then I (erreur : il n'y a pas de then en C) 5.5.4 Correction globale Dans l'id
eal, il est souhaitable que le compilateur eectue aussi peu de changements que possible. Il existe des algorithmes qui permettent de choisir une s
equence minimale de changements correspondant globalement au co^ut de correction le plus faible. Malheureusement, ces m
ethodes sont trop couteuses en temps et en espace pour ^etre implant
ees en pratique et ont donc uniquement un inter^et th
eorique. En outre, le programme correct le plus proche n'est pas forcemment celui que le programmeur avait en t^ete : : : 35 Chapitre 6 L'outil yacc/bison De nombreux outils ont
et
e batis pour construire des analyseurs syntaxiques a partir de grammaires. C'est a dire des outils qui construisent automatiquement une table d'analyse a partir d'une grammaire donn
ee. yacc est un utilitaire d'unix, bison est un produit gnu. yacc/bison accepte en entr
ee la description d'un langage sous forme de regles de productions et produit un programme
ecrit dans un langage de haut niveau (ici, le langage C) qui, une fois compil
e, reconnait des phrases de ce langage (ce programme est donc un analyseur syntaxique). yacc est l'acronyme de Yet Another Compiler Compiler, c'est a dire encore un compilateur de compilateur. Cela n'est pas tout a fait exact, yacc/bison tout seul ne permet pas d'
ecrire un compilateur, il faut rajouter une analyse lexicale (a l'aide de (f)lex par exemple) ainsi que des actions semantiques pour l'analyse s
emantique et la g
en
eration de code. compilateur bison specifications bison.tab.c.y bison.y compilateur C cc.tab.c -ly a.out yacc/bison construit une table d'analyse LALR qui permet de faire une analyse ascendante. Il utilise donc le modele decallages-reductions. 6.1 Structure du chier de speci cations bison %f declaration (en C) de variables, constantes, inclusions de chiers, : : : %g declarations des unites lexicales utilisees declarations de priorites et de types %% regles de production et actions semantiques %% routines C et bloc principal Les symboles terminaux utilisables dans la description du langage sont ; des unites lexicales que l'on doit imp
erativement d
eclarer par %token nom. Par exemple: %token MC sinon %token NOMBRE ; des caracteres entre quotes. Par exemple: '+' 'a' Les symboles non-terminaux sont les caracteres ou les cha^nes de caracteres non d
eclar
ees comme unit
es lexicales. yacc/bison fait la di
erence entre majuscules et minuscules. SI et si ne d
esignent pas le m^eme objet. Les regles de production sont des suites d'instructions de la forme 36  non-terminal : prod1 | prod2... | prodn  Les actions semantiques sont des instructions en C ins
er
ees dans les regles de production. Elles sont ex
ecut
ees chaque fois qu'il y a r
eduction par la production associ
ee. Exemples: G : S B 'X' fprintf("mot reconnu")g  S : A fprint("reduction par A")g T fprintf("reduction par T")g 'a'  La section du bloc principal doit contenir une fonction yylex() eectuant l'analyse lexicale du texte, car l'analyseur syntaxique l'appelle chaque fois qu'il a besoin du terminal suivant. On peut soit
ecrire cette fonction soit utiliser la fonction produite par un compilateur (f)lex appliqu
e a un chier de sp
ecications (f)lex nom.l. Dans ce cas, il faut : ; utiliser le compilateur bison du nom.y avec l'option -d qui produit un chier nom.tab.h contenant les d
enitions (sous forme de #define) des unit
es lexicales (les token) rencontr
ees et du type YYSTYPE s'il est red
eni, ; inclure le nom.tab.h au d
ebut du chier de sp
ecications (f)lex ; cr
eer un.o a partir du lex.yy.c produit par (f)lex ; lors de la compilation C du chier nom.tab.c, il faut faire le lien avec ce.o et rajouter la bibliotheque (f)lex lors de la compilation C du chier nom.tab.c avec : gcc nom.tab.c lex.yy.o -ly -lfl (attention a l'ordre de ces bibliotheques). 6.2 Attributs A chaque symbole (terminal ou non) est associ
e une valeur (de type entier par d
efaut). Cette valeur peut ^etre utilis
ee dans les actions s
emantiques (comme un attribut synthetise). Le symbole $$ r
ef
erence la valeur de l'attribut associ
e au non-terminal de la partie gauche, tandis que $i r
ef
erence la valeur associ
ee au i-eme symbole (terminal ou non-terminal) ou action semantique de la partie droite. Exemple : expr : expr '+' expr f tmp=$1+$3g '+' expr f $$=tmp+$6g Par d
efaut, lorsqu'aucune action n'est indiqu
ee, yacc/bison g
enere l'action f$$=$1g 6.3 Communication avec l'analyseur lexical : yylval L'analyseur syntaxique et l'analyseur lexical peuvent communiquer entre eux par l'interm
ediaire de la variable int yylval. Dans une action lexicale (donc dans le chier (f)lex par exemple), l'instruction return(unite) permet de renvoyer a l'analyseur syntaxique l'unit
e lexicale unite. La valeur de cette unit
e lexicale peut ^etre rang
ee dans yylval. L'analyseur syntaxique prendra automatiquement le contenu de yylval comme valeur de l'attribut associ
e a cette unit
e lexicale. La variable yylval est de type YYSTYPE (d
eclar
e dans la bibliotheque yacc/bison) qui est un int par d
efaut. On peut changer ce type par un #define YYSTYPE autre type C ou encore par %union f champs d'une union C g qui d
eclarera automatiquement YYSTYPE comme
etant une telle union. Par exemple %union { int entier double reel char * chaine } permet de stocker dans yylval a la fois des int, des double et des char *. L'analyseur lexical pourra par exemple contenir 37  {nombre} { yylval.entier=atoi(yytext) return NOMBRE } Le type des lexemes doit alors ^etre pr
ecis
e en utilisant les noms des champs de l'union %token NOMBRE %token IDENT CHAINE COMMENT On peut
egalement typer des non-terminaux (pour pouvoir associer une valeur de type autre que int a un non-terminal) par %type S %type expr 6.4 Variables, fonctions et actions prede nies yyparse() : appel de l'analyseur syntaxique. YYACCEPT : instruction qui permet de stopper l'analyseur syntaxique. YYABORT : instruction qui permet
egalement de stopper l'analyseur, mais yyparse() retourne alors 1, ce qui peut ^etre utilis
e pour signier l'echec de l'analyseur. main() : le main par d
efaut se contente d'appeler yyparse(). L'utilisateur peut
ecrire son propre main dans la partie du bloc principal. %start non-terminal : action pour signier quel non-terminal est l'axiome. Par d
efaut, c'est le premier d
ecrit dans les regles de production. 6.5 Con its shift-reduce et reduce-reduce Lorsque l'analyseur est confront
e a des conits, il rend compte du type et du nombre de conits rencontr
es : >bison exemple.y conflicts: 6 shift/reduce, 2 reduce/reduce Il y a un conit reduce/reduce lorsque le compilateur a le choix entre (au moins) deux productions pour reduire une cha^ne. Les conits shift/reduce apparaissent lorsque le compilateur a le choix entre reduire par une pro- duction et decaller le pointeur sur la cha^ne d'entr
ee. yacc/bison r
esoud les conits de la maniere suivante : conit reduce/reduce : la production choisie est celle apparaissant en premier dans la sp
ecication. conit shift/reduce : c'est le shift qui est eectu
e. Pour voir comment bison a r
esolu les conits, il est n
ecessaire de consulter la table d'analyse qu'il a construit. Pour cela, il faut compiler avec l'option -v. Le chier contenant la table s'appelle nom.output 6.5.1 Associativite et priorite des symboles terminaux On peut essayer de r
esoudre soit m^eme les conits (ou tout du moins pr
eciser comment on veut les r
esoudre) en donnant des associativit
es (droite ou gauche) et des priorit
es aux symboles terminaux. Les d
eclarations suivantes (dans la section des d
enitions) %left term1 term2 %right term3 %left term4 %nonassoc term5 indiquent que les symboles terminaux term1, term2 et term4 sont associatifs a gauche, term3 est associatif a droite, alors que term5 n'est pas associatif. Les priorit
es des symboles sont donn
ees par l'ordre dans lequel apparait leur d
eclaration d'associativit
e, les premiers ayant la plus faible priorit
e. Lorsque les symboles sont dans la m^eme d
eclaration d'associativit
e, ils ont la m^eme priorit
e. La priorit
e (ainsi que l'associativit
e) d'une production est d
enie comme
etant celle de son terminal le plus a droite. On peut forcer la priorit
e d'une production en faisant suivre la production de la d
eclaration %prec terminal-ou-unite-lexicale ce qui a pour eet de donner comme priorit
e (et comme associativit
e) a la production celle du terminal-ou-unite- lexicale (ce terminal-ou-unite-lexicale devant ^etre d
eni, m^eme de maniere factice, dans la partie Ib). Un conit shift/reduce, i.e. un choix entre entre une r
eduction A !  et un d
ecallage d'un symbole d'entr
ee a, est alors r
esolu en appliquant les regles suivantes : si la priorit
e de la production A !  est sup
erieure a celle de a, c'est la r
eduction qui est eectu
ee 38  si les priorit
es sont les m^emes et si la production est associative a gauche, c'est la r
eduction qui est eectu
ee dans les autres cas, c'est le shift qui est eectu
e. 6.6 Recuperation des erreurs Lorsque l'analyseur produit par bison rencontre une erreur, il appelle par d
efaut la fonction yyerror(char *) qui se contente d'acher le message parse error, puis il s'arr^ete. Cette fonction peut ^etre red
enie par l'utilisateur. Il est possible de traiter de maniere plus explicite les erreurs en utilisant le mot cl
e bison error. On peut rajouter dans toute production de la forme A ! 1j2j : : : une production A ! error  Dans ce cas, une production d'erreur sera trait
ee comme une production classique. On pourra donc lui associer une action s
emantique contenant un message d'erreur. Des qu'une erreur est rencontr
ee, tous les caracteres sont aval
es jusqu'a rencontrer le caractere correspondant a . Exemple : La production instr! error indique a l'analyseur qu'a la vue d'une erreur, il doit sauter jusqu'au dela du prochain " " et supposer qu'une instr vient d'^etre reconnue. La routine yyerrok replace l'analyseur dans le mode normal de fonctionnement c'est a dire que l'analyse syn- taxique n'est pas interrompue. 6.7 Exemples de chier.y Cet exemple reconnait les mots qui ont un nombre pair de a et impair de b. Le mot doit se terminer par le symbole $. Cet exemple ne fait pas appel a la fonction yylex g
en
er
ee par le compilateur (f)lex. %% mot : PI '$' {printf("mot accepte\n")YYACCEPT}  PP : 'a' IP | 'b' PI |  IP : 'a' PP | 'b' II | 'a'  PI : 'a' II | 'b' PP | 'b'  II : 'a' PI | 'b' IP | 'a' 'b' | 'b' 'a'  %% int yylex() { char car=getchar() if (car=='a' || car=='b' || car=='$') return(car) else printf("ERREUR : caractere non reconnu : %c ",car) } Ce deuxieme exemple lit des listes d'entiers pr
ec
ed
ees soit du mot somme, soit du mot produit. Une liste d'entiers est compos
ee d'entiers s
epar
es par des virgules et se termine par un point. Lorsque la liste d
ebute par somme, l'ex
ecutable doit acher la somme des entiers, lorsqu'elle d
ebute par produit, il doit en acher le produit. Le chier doit se terminer par $. Cet exemple utilise la fonction yylex g
en
er
ee par le compilateur flex a partir du chier de sp
ecication exemple2.l suivant 39  %{ #include #include "exemple2.tab.h" // INCLUSION DES DEFS DES TOKEN int nbligne=0 %} chiffre 0-9] entier {chiffre}+ espace  \t] %% somme return(SOMME) produit return(PRODUIT) \n nbligne++ .,] return(yytext0]) {entier} { yylval=atoi(yytext) return(NOMBRE) } {espace}+  "$" return(FIN). printf("ERREUR ligne %d : %c inconnu\n",nbligne,yytext0]) %% Le chier de sp
ecications bison est alors le suivant %token SOMME %token PRODUIT %token NOMBRE %token FIN %% texte : liste texte | FIN {printf("Merci et a bientot\n")YYACCEPT}  liste : SOMME sentiers '.' {printf("la somme est %d\n",$2)} | PRODUIT pentiers '.' {printf("le produit est %d\n",$2)}  sentiers : sentiers ',' NOMBRE {$$=$1+yylval} | NOMBRE {$$=yylval}  pentiers : pentiers ',' NOMBRE {$$=$1*yylval} | NOMBRE {$$=yylval}  %% Un Makele pour compiler tout ca est exemple2 : lex.yy.o exemple2.tab.c gcc exemple2.tab.c lex.yy.o -o exemple2 -ly -lfl lex.yy.o : lex.yy.c gcc -c lex.yy.c lex.yy.c : exemple2.l exemple2.tab.h flex exemple2.l exemple2.tab.h : exemple2.y bison -d exemple2.y exemple2.tab.c : exemple2.y bison -d exemple2.y 40 Chapitre 7 Theorie des langages : les automates 7.1 Classi cation des grammaires Nous avons d
eja vu qu'il y avait des langages reguliers et d'autres non r
eguliers. On distingue en fait quatres types de langage, correspondant a quatres types de grammaires. Ces di
erents types d
ependent de la forme des productions. Grammaire de type 3 (reguliere) Les productions sont de la forme A ! wB ou A ! w avec A 2 VN (un seul symbole non terminal), B 2 VN et8w 2 VT (une cha^ne de symboles terminaux) < S ! aSjT jabU jcc Exemple: : T ! cT j" U ! abS Grammaire de type 2 (hors contexte) (algebrique) S Les productions sont de la forme A !  avec A 2 VN et  2 (VN VT ) Exemple (grammaire de Dyck): S ! ( S ) S j" Grammaire de type 1 (contextuelle) S S Les productions sont de la forme  !  avec  2 (VN VT )+ et  2 (VN VT ) et jj  j j  : : : S ! " sont autoris
ees si S 2 VN n'apparait pas dans la partie droite d'une production de G. Les productions Exemple: a A b ! a truc b Le remplacement de A par truc ne se fait que dans le contexte pr
ecis ou A est entour
e par les symboles a et b Grammaire de type 0 : aucune restrictions sur les reglesS S Les productions sont de la forme  !  avec  2 (VN VT )+ et  2 (VN VT ) Propriete 7.1 Les grammaires de type 0 englobent les grammaires de type 1 qui englobent les grammaires de type 2 qui englobent les grammaires de type 3. type 0 type 1 : contextuelle type 2 : hors contexte type 3 : reguliere 7.1.1 Les langages contextuels Exemples de langages contextuels (mais non hors contexte) 1 : Exemple 1: L=fwdw
w 2 fa
b
cg g n'est pas hors contexte, c'est a dire qu'il n'existe pas de grammaire hors contexte permettant de le d
ecrire. Ce langage est une traduction abstraite du probleme consistant a controler 1 par la suite, on dira qu'un langage est de type s'il est de type et pas de type + 1 : i i i 41 que, dans un programme, une variable doit ^etre d
eclar
ee avant d'^etre utilis
ee. Une grammaire (contextuelle) g
en
erant ce langage? Commencons par g
en
erer wdw, ~ on sait faire c'est hors contexte ca :  S ! aSajbSbjcScjd Mais ca ne r
esoud pas notre probleme. Nous on veut ensuite d
eplacer chaque lettre du w. ~ Pour obliger a d
eplacer, mettons plut^ot des non-terminaux (les terminaux permettent de nir et donc autoriserait qu'on s'arr^ete avant d'avoir d
eplac
e tout le monde), et ceci entre deux marqueurs de d
ebut et n :  S0 ! SF S ! aSAjbSB jcSC jdD On obtient par exemple des mots du genre abbcadDACBBAF. Donnons alors un coup de baguette magique sur chaque symbole qui doit ^etre d
eplac
e : 8< DA ! DA0 : DB ! DB 0 DC ! DC 0 puis d
eplacons les : 8< A0A ! AA0 A0B ! BA0 A0C ! CA0 : CB00AA !! AC AB 0 A0 B ! BB 0 B 0 C ! CB 0 0 A0 B ! BC 0 C 0C ! CC 0 Sur notre mot, cela nous pousse a faire: abbacadDACABBAF ! abbcadDA0CBBAF ! abbcadDCBBAA0 F (le A est arriv
e a sa bonne place), et les autres coups de baguettes magiques d
eplacent de m^eme le C ( abbcadDCBBAA0 F ! abbcadDC 0BBAA0 F ! abbcadDBBAC 0 A0 F) puis les autres lettres (abbcadDBBAC 0 A0 F ! abbcadDA0B 0 B 0 C 0A0 F ) Quand ils sont arriv
es a leur place, on les remet normaux (terminaux): 8< A0F ! Fa : BC 00FF !! FFbc Sur le mot en exemple, ca nous permet donc d'avoir: abbcadDA0B 0 B 0 C 0A0 F ! abbcadDA0B 0 B 0 C 0Fa ! abbcadDA0B 0 B 0 Fca ! abbcadDFabbca Il ne reste plus qu'a virer les F et D quand tout est ni. Conclusion: superbe grammaire contextuelle 8> S0 ! SF >> S ! aSAjbSBjcSC jdD >> DA ! DA0 < A0A ! AA0 DB ! DB 0 DC ! DC 0 A0 B ! BA0 A0 C ! CA0 >> B0A ! AB0 0 0 A0 B ! BB 0 B 0 C ! CB 0 >> C0 A ! AC A0 B ! BC 0 C 0C ! CC 0 >: A F ! Fa B 0 F ! Fb C 0F ! F c DF ! " On a une grammaire contextuelle, donc le langage est contextuel 2. Exemple 2 : L=fanbm cndm
n
1
m
1g est contextuel. Ce langage abstrait le probleme de la v
erication de la correspondance entre parametres formels et eectifs d'une fonction. 7.1.2 Les langages reguliers Les langages r
eguliers peuvent ^etre g
en
er
es par une grammaire r
eguliere. Donc toute ER peut s'exprimer par une grammaire, et m^eme par une grammaire r
eguliere. Exemples: S ! aS jbS j" g
enere l'expression (ajb) La grammaire SB ! ajBc g
enere ajb c mais n'est pas r
eguliere. Une grammaire r
eguliere
equivalente (qui ! Bbj" 2 pr
ecisons le, car il aurait pu ^etre carrement de type 0 : 42   S ! ajS 0 g
enere le m^eme langage) est S ! bS c 0 0j  S ! TabbT L'ER (ajb) abb(ajb) est g
en
er
ee par la grammaire non r
eguliere T ! aT jbT j" ou encore par la grammaire 8< S ! aSjbSjT r
eguliere : T ! abbU U ! "jaU jbU  BaBaBaB b ab ab ab est g
en
er
ee par la grammaire non r
eguliere SB !
equivalente a la grammaire r
egu- 8> S ! bSjT W ! bW jX ! bB j" < aU X ! aY liere > TU ! : ! bU jV 8< S ! TaaU V ! aW Y ! "jbY : TU !! abbcT jbabaT jabbcjbaba (qui est non r
eguliere) g
enere (abbcjbaba)+aa(ccjbb) ccU jbbU j" 7.1.3 Les reconnaisseurs Le probleme qui se pose est de pouvoir reconna^tre si un mot donn
e appartient a un langage donn
e. Un recon- naisseur pour un langage est un programme qui prend en entr
ee une cha^ne x et r
epond oui si x est une phrase (un mot) du langage et non sinon. C'est un analyseur syntaxique quoi! Theoreme 7.2 Les automates a etats nis sont des reconnaisseurs pour les langages reguliers. Theoreme 7.3 Les automates a pile sont des reconnaisseurs pour les langages hors contexte. Les grammaires hors contexte et les grammaires r
egulieres jouent donc un r^ole particulierement important en informatique (puisqu'il existe des analyseurs syntaxiques pour elles). Malheureusement, la plupart des langages de programmation usuels ne peuvent ^etre completement d
ecrits par une grammaire hors contexte (et donc encore moins par une grammaire r
eguliere). Les parties sensibles au contexte (regles de compatibilit
e de types, corres- pondance entre le nombre d'arguments formels et eectifs lors de l'appel d'une proc
edure, : : :) sont g
en
eralement d
ecrites de maniere informelle a cot
e de la grammaire du langage qui, elle, est hors contexte. Ainsi, lors de la r
ealisation d'un compilateur, ces deux aspects sont aussi s
epar
es : l'analyse syntaxique s'appuie sur la grammaire (hors contexte) et les contraintes contextuelles sont rajout
ees par la suite. 7.2 Automates a etats nis Denition 7.4 Un automate a etats nis (AEF) est deni par un ensemble ni E d'etats un etat e0 distingue comme etant l'etat initial un ensemble ni T d'etats distingues comme etats naux (ou etats terminaux) un alphabet ! des symboles d'entree une fonction de transition ) qui a tout couple forme d'un etat et d'un symbole de ! fait corres- pondre un ensemble (eventuellement vide) d'etats : )(ei
a) = fei1
: : :
ein g Exemple : ! = fa
bg, E = f0
1
2
3g, e0 = 0, T = f3g )(0
a) = f0
1g, )(0
b) = f0g, )(1
b) = f2g, )(2
b) = f3g (et )(e
l) = sinon) Repr
esentation graphique: a a b b 0 1 2 3 b Fig. 7.1 - Un exemple d'automate Convention: on dessinera un triangle pour l'
etat initial et un carr
e pour les
etats naux. 43 Repr
esentation par une table de transition :
etat a b 0 0,1 0 1 - 2 e0 = 0 et T = f3g 2 - 3 3 - - Attention a toujours bien pr
eciser l'
etat initial et le ou les
etats naux/terminaux. Denition 7.5 Le langage reconnu par un automate est l'ensemble des cha^
nes qui permettent de passer de l'etat initial a un etat terminal. L'automate de la gure 7.1 accepte le langage (r
egulier) (l'expression r
eguliere) (ajb) abb Un automate peut tres facilement ^etre simul
e par un algorithme (et donc on peut
ecrire un programme simulant un automate ni). C'est encore plus facile si l'automate est deterministe, c'est a dire lorsqu'il n'y a pas a choisir entre 2 transitions. Ce que signie donc le th
eoreme 7.2 c'est que l'on peut
ecrire un programme reconnaissant tout mot (toute phrase) de tout langage r
egulier. Ainsi, si l'on veut faire l'analyse lexicale d'un langage r
egulier, il sut d'
ecrire un programme simulant l'automate qui lui est associ
e. 7.2.1 Construction d'un AEF
a partir d'une E.R. (Construction de Thompson, bas
ee sur la r
ecursivit
e des expressions r
egulieres) Pour une expression r
eguliere s, on note A(s) un automate reconnaissant cette expression. { automate acceptant la cha^ne vide { automate acceptant la lettre a a { automate acceptant (r)(s) r s 1. mettre une "-transition de chaque
etat terminal de A(r) vers l'
etat initial de A(s) 2. les
etats terminaux de A(r) ne sont plus terminaux 3. le nouvel
etat initial est celui de A(r) 4. (l'ancien
etat initial de A(s) n'est plus
etat initial) { automate reconnaissant rjs r s 1. cr
eer un nouvel
etat initial q 2. mettre une "-transition de q vers les
etats initiaux de A(r) et A(s) 3. (les
etats initiaux de A(r) et A(s) ne sont plus
etats initiaux) 44  { automate reconnaissant r+ r mettre des "-transition de chaque
etat terminal de A(r) vers son
etat initial Exemple : (abjbca)+ bb(abjcb) a correspond a l'automate donn
e gure 7.2. Mais on peut bien s^ur le simplier et virer pas mal d'"-transitions, pour obtenir par exemple celui donn
e gure 7.3. a b a b b b a b c a c b