Compilation et thorie des langages

Compilation et thorie des langagesKaouther Nouira Ferchichi20071Chapitre 1Introduction la compilation2Quelques dfinitionsUn traducteur est un programme qui transforme chaque mot dun langage L1 sur un alphabet A1 en un mot dun langage L2 sur un alphabet A2.Un compilateur est un cas particulier de traducteur qui prend en entre un mot reprsentant un programme cest--dire la description dun calcul et qui est charg de produire le rsultat de ce calcul. En pratique, il sagira de traduire un texte reprsentant le calcul vers une suite dinstructions excutables par la machine. 3ExemplesDun langage de haut niveau (Pascal, C++, ML, ) vers un langage dassembleur.Du langage dassembleur vers du code binaire.Dun langage de haut niveau vers les instructions dune machine virtuelle (JVM).4L1L2LnMpM2M1La compilation de n langages pour p architectures ncessite priori la ralisation de np compilateurs.L1L2LnMpM2M1Langage UniverselEn utilisant un langage universelintermdiaire on rduit le problme de construction de np compilateurs.5Repres par rapport au langage naturelUn langage est un ensemble de phrases, units linguistiques formes selon des rgles prcises l'aide d'un alphabet. Un alphabet est un ensemble des signes lmentaires, par exemple les caractres d'un langage crit, les phnomnes d'un langage oral, les notes de musique d'une partition

6La lexicographie dun langageLassemblage linaire dunits lexicales ou lexmes (vocabulaire) form partir de lalphabet du langage.

7Syntaxe dun langageLa syntaxe d'un langage est l'ensemble des rgles qui fixent l'organisation des lexmes au sein d'une phrase.8La smantique d'un langage fixe les rapports entre les phrases et le monde rel, de manire ce que chaque phrase bien forme syntaxiquement ait une signification prcise.

Une phrase bien forme syntaxiquement peut ne pas avoir de signification.

9Un compilateurun compilateur lit un programme source dans un langage source et produit un programme cible qui est le rsultat la traduction du programme source dans un autre langage, le langage cible. Le compilateur produit ventuellement des messages d'erreurs.10Entres et sorties d'un compilateurMessagesProgramme sourceCompilateurProgramme cible11Compilateurfigure 1.2 Les deux parties dun compilateurProgramme sourceCompilateurProgramme cibleAnalyseSynthseMessages12Partie AnalyseAnalyse lexicaleAnalyse syntaxiqueAnalyse SmantiqueGnration du codeOptimisation du codePartie Synthse13A. lexicaleSourceCibleA. syntaxiqueA. smantiqueG. codeO. de codeSymbolesErreurs

14Analyse lexicalee chat ange la souris. Erreurs15Analyse lexicaleConsiste rcuprer les mots, que lon appelle lexmes ou tokens, partir dune suite de caractres. Par exemple dterminer, partir de lnonc suivant: for i: = 1 to vmax do a:= a + i;on peut dgager la suite de tokens suivante:for: mot cli: identificateur:=: affectation1: entierto: mot clvmax: identificateurdo: mot cla: identificateur:= : affectationa: identificateur+: oprateur arithmtiquei: identificateur;: sparateur

16Type de variableType de tokenTokenNumro de symbolemot clfor10mot clto11mot cldo12sparateur;13......affectation:=100+101...identi1000identa1001identvmax1002...entier15001...La table des symboles17Ensuite, lnonc prcdent peut sexprimer ainsi:10, 1000, 100, 5001, 11, 1002, 12, 1001, 100, 1001, 101, 1000, 13for i := 1 to vmax do a := a + i ;c'est--dire comme une suite de rfrence la table des symboles.

18Analyse syntaxiqueSouris la chat le mange.19ErreursAnalyse syntaxiqueLors de lanalyse syntaxique, on vrifie que lordre des tokens correspond lordre dfinit pour le langage. On dit que lon vrifie la syntaxe du langage partir de la dfinition de sa grammaire. Cette phase produit une reprsentation sous forme darbre de la suite des tokens obtenus lors de la phase prcdente. 20Larbre syntaxique obtenu aprs analyse syntaxique

IdentificateurIdentificateurIdentificateurIdentificateur21Analyse smantique Le chas mange la souris.

22ErreursAnalyse smantique Dans cette phase on vrifie que les variables ont un type correct. Par exemple, il faut vrifier que la variable i possde bien le type entier, et que la variable a est bien un nombre. Cette opration seffectue en parcourant larbre syntaxique et en vrifiant chaque niveau que les oprations sont correctes.

23Gnration de codeOn gnre le code pour du langage machine ou un langage dassemblage. Voici un exemple de code gnr pour une (pseudo) machine.var_a;les tiquettes des variablesvar_ivar_vmax...; le code du programmemov var_i,1loop:mov A0, (var_i); comparaison i >= vmaxjge A0, (var_vmax), finFor; si vrai aller en finFormov A0, (var_a); calcul de a+iadd A0, A0, (var_i)mov var_a,A0; a:= a+imov A0, (var_i); on incrmente iadd A0, A0, 1mov var_i, Aojmp loop; et on continue la bouclefinFor:...

24Chapitre 2Langage et grammaire25Les langages rguliersDans le cadre d'une classe particulire de langages, les langages rguliers, nous montrons comment dcrire la syntaxe dans un formalisme adapt.26Le mta-langage des expressions rguliresnous dfinissons par rcurrence l'ensemble des expressions rgulires permettant de dfinir la syntaxe d'un langage dfini sur un alphabet donn : expressions de base :(1) si a est un symbole de l'alphabet alors a est une expression rgulire.(2) en peut utiliser le symbole pour dcrire la chane vide.

27 juxtaposition :(3) si e1 et e2 sont des expressions rgulires alors e1e2 est une expression rgulire. alternative :(4) si e1 et e2 sont des expressions rgulires alors e1 | e2 est une expression rgulire. rptition :(5) si e est une expression rgulire alors e* est une expression rgulire.

28On peut noter quelques proprits algbriques du langage des expressions rgulires (e, e1, e2, e3 dsignaient des expressions rgulires) :e = e = ee | e = ee1 | e2 = e2 | e1e1 ( e2 | e3 ) = e1 e2 | e1 e3 et ( e1 | e2 ) e3 = e1 e3 | e2 e329Algorithme de reconnaissance syntaxiquele problme est d'crire un algorithme qui pour un langage rguliers donn dtermine si une squence de symboles, pris dans l'alphabet du langage, est valide syntaxiquement.

Nous pouvons donc dcrire l'algorithme par un automate, appel automate reconnaisseur.30Exemple E2.1 on considre un langage construit sur l'alphabet {a,b,c} est dont la syntaxe est dcrite par l'expression rgulire (ab|c)*. Les chanes ababcabcc, ab, c sont des exemples de chanes correctes syntaxiquement. on veut crire un algorithme qui dtermine si une phrase forme sur {a,b,c} vrifie la syntaxe du langage.

31AlgorithmeEtat : un entier sur [1..3]EtatInitial : l'entier 1Algorithme DmarrerEtat EtatInitial Lire (EC)Tant que EC != " " Selon Etat :Etat = 1 : selon ECEC = "a" : Etat 2 {attente d'un b}

EC = "b": Etat 3 {erreur}

EC="c" : {on reste dans l'tat 1} FinSelonEtat = 2 : si EC = "b" alors Etat 1 sinon Etat 3Etat = 3 : {quelque soit EC, on reste dans l'tat 3}FinSelonLire (EC) FinTanqueEcrire(si Etat = 1 alors "chaine correcte" sinon "chaine incorrecte")

32Reprsentation par un automate de l'algorithme de parcours itratif pour la reconnaissance de l'expression rgulire (a b | c)* 33vraiEC = "c"sinonEC = "a"123EC = "b"EC = "b"Langage et grammaire La notion de grammaire est la base de l'tude formelle des proprits syntaxiques d'un langage.

Ceci constitue un fondement autant pour la conception d'un langage que pour l'criture d'un programme de traduction.

34Nous abordons la notion de grammaire au travers d'exemple simple, tout en prsentant divers mta-langages associs : notation BNF (Backus Naur Form) et EBNF (Extended Backus Naur Form) et diagrammes syntaxiques.

Les grammaires servent notamment de base la construction systmatique (et la gnration automatique) de programmes d'analyse syntaxique.35Notion de grammaireExemple E2.1 PalindromesOn considre l'ensemble des squences palindromes dont les lments sont soit le caractre "a", soit le caractre "b". Un palindrome est une squence gale son inverse. Par exemple, les squences "aabbaa", "a", "baaabaaab" sont des palindromes sur {a, b} et les squences "abbb", "aabbb", "aca" n'en sont pas.36 la squence vide est un palindrome, une squence rduite des caractres "a" ou "b" est un palindrome, si la squence S est un palindrome alors les squences "a" S "a" et "b" S "b" sont des palindromes.

enfin on peut s'intresser la description du langage Pal dont les phrases sont les palindromes forms sur l'alphabet donn {"a", "b"}. Ici, la lexicographie du langage se rduit l'alphabet. La syntaxe est dcrite en numrant les rgles suivantes :

::= " vide " ::= " a " ::= " b " ::= " a " " a " ::= " b " " b "37la description donne ci-dessus utilise la notation BNF. Les symboles en minuscules sont appels les symboles terminaux : il reprsente les signes lmentaires que l'on trouve dans une phrase du langage. le symbole est appel symbole non terminal. Il caractrise ici une phrase du langage. Le symbole vide reprsente la chane vide.

38 ::= " vide " ::= " a " ::= " b " ::= " a " " a " ::= " b " " b "

Les rgles de la grammaire se lisent de la faon suivante: un palindrome est soit vide (1), soit le symbole a (2), soit le symbole b (3), soit le symbole a suivi d'un palindrome suivi d'un symbole a (4), soit le symbole b suivi d'un palindrome suivi d'un symbole b (5). On retrouve donc la juxtaposition (rgles 4 et 5), la rcursion (rgles 4 et 5) et l'alternative (les rgles donnent cinq formes possibles de palindromes).39Exemple E2.2 IdentificateurUn identificateur est une squence de lettres ou de chiffres commenant par une lettre.

Un chiffre est "0", "1", "2", "3", "4", "5", "6", "7", "8" ou "9",

une lettre est "a" ou "b" ou "c",

40Une squence de caractres alphanumriques est reprsente par le symbole ,

Un caractre alphanumrique est reprsent par le symbole ,

Une lettre ou un chiffre sont respectivement reprsents par les symboles ou .

41 ::= | ::= | ::= | ::= " a "|" b "||" z " ::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"42Dfinition, notation BNFUne grammaire est compose de quatre lments nomms Vt, Vnt, A, RP.

G = {Vt, Vnt, A, RP }

Vt est l'ensemble des symboles terminaux. Vnt est l'ensemble des symboles non terminaux. A est l'axiome. l'axiome est le symbole non terminal dsignant l'unit syntaxique qui caractrise le langage tout entier.RP est l'ensemble des rgles dites de production.43Dans l'exemple E2.2 :

Vt = {a, b, , z, 0, 1, ,9}

Vnt = { , , , , }

A =

RP = ::= | ::= | ::= | ::= "a" | "b" | "c" | |"z" ::= "0" | "1" | "2"| "3" | "4" | "5" | "6" | "7" | "8" |"9"44Exemple E2.3 Blocs en PascalVt = {begin, end, ;, :=, if, then, else}Vnt = { , , , , , }A = RP =::= begin end ::= | ; ::= := | if then | if then else ::= |

45Remarqueen fixant des conventions d'criture des symboles et en convenant que la premire rgle dfinit l'axiome, on peut ne donner que l'ensemble des rgles de la grammaire. Vt, Vnt et A s'en dduisant implicitement.46Exemple E2.4 Phrase en franais ::= ::= ::= ::= ::= |

47RemarquesDe manire gnrale, la lexicographie est la partie de la syntaxe qui fixe les rgles d'assemblage linaire des signes de l'alphabet en lexmes, comme par exemple les mots dans une langue naturelle.

4849Table Symbles.Anal. LexAnal. Synt.LexmesSourceIdentificateursArbresrequteErreurs.Grammaire(Syntaxe)EBNFDans la notation EBNF (BNF tendue), on complte le mta-langage par des symboles exprimant des itrations et des options:

[] signifie que la chane est optionnelle (dans la phrase dcrite elle apparat 0 ou 1 fois){} signifie que la chane apparat 0,1, ou plusieurs fois.50Le langage de squences ventuellement vides de "a" peut tre dcrit par les grammaires :

en notation BNF ::= " vide " | " a " en notation EBNF ::= {" a "}

51le langage des squences non vides de "a" peut tre dcrit par la grammaire :en notation BNF ::= " a " | " a " en notation EBNF ::= " a " {" a "}remarque : ::= " a "

52par exemple, une grammaire pour dcrire la syntaxe d'un bloc d'instructions, ventuellement vide, peut-tre :

en BNF ::= begin end ::= vide| ::= | ; En EBNF ::= begin [ {; }]end 53Diagramme syntaxiqueune autre notation trs utilise et celle des diagrammes syntaxiques. Il s'agit d'une description graphique : les symboles terminaux sont reprsents dans des cadres arrondis, les symboles non terminaux dans des rectangles, les liens entre les sous phrases sont reprsents par des flches qui indiquent le sens de lecture des diagrammes.54aqa:(a)55aqa':(b)aa(c);(d)begininstfinbloc : Drivation, arbre de drivationDrivation dune phraseUne drivation dune phrase partir dune grammaire est une suite de r-ecritures qui, partir de laxiome, conduisent la phrase.De faon gnrale, une phrase donne peut tre drive de plusieurs manires partir dune grammaire.56Exemple E2.5Soit la grammaire compose de lexpression rgulire suivante :L ::= aL|aQBQB ::= b | bQBVrifions que aabbb est une phrase correcte par rapport la grammaireLe symbole exprime une r-ecritureL aL aaQB aabQB aabbQB aabbb

57Arbre de drivation58LL ::= aL|aQBQB ::= b | bQBaLaaabbb QBbQBbQBbPrincipe de construction dun arbre de drivationPour toute rgle de la forme :X ::= X1 X2 X3 X Xn59XX1XnX2X360Pour toute rgle de la forme :X ::= X1 | X2 | X3 || XnXX1XnX2X3XXXAmbigut dune grammaireUne grammaire est ambigu si pour au moins une phrase du langage il existe au moins deux arbres de drivation.

61Exemple E2.6 au moins un b Soit le langage des phrases formes de caractres a et b contenant au moins un b.La syntaxe de ce langage peut tre dcrite par la grammaire suivante :P ::= S b SS ::= vide | S a|S bPour la phrase abb, on peut par exemple construire les deux arbres de drivation :6263PP ::= S b SS ::= vide | S a|S bSSSabbbSavidebvidePSSSaSbvidebvideSExemple E2.7 AdditionSoit un sous-ensemble du langage des expressions arithmtiques dans lequel on peut exprimer que des sommes portant sur des chiffres.La grammaire suivante est ambigu:S ::= S+S|CC ::= 0|1|2|3|4|5|6|7|8|9

64Deux arbres de drivation65S ::= S+S|CC ::= 0|1|2|3|4|5|6|7|8|91 + 2 + 3SSSC+SS+1C2C3SSSC+SS+3C1C2En revanche la grammaire suivante, alternative pour dcrire la syntaxe nest pas ambiguS ::= S + C|CC ::= 0|1|2|3|4|5|6|7|8|9

66SSC+SS+3C1C2Chapitre 3Lanalyse lexicale67Les bases thoriquesLanalyse lexicale set reconnatre les symboles utiliss 123, begin, x, les classer (entier, mot-cls, identificateur, commentaire, ) en leur associant une tiquette avant de les transmettre lanalyseur syntaxique. Et en leur trouvant une reprsentation machine efficace par lintermdiaire de la table des symboles.Cette phase doit se faire rapidement on se contentera donc de reconnatre des expressions rgulires qui peuvent tre identifies par des automates tats finis.68Quest ce quun langage rgulier?Lensemble des langages rguliers sur un alphabet A est dfini de manire inductive (plus petit ensemble vrifiant les proprits):, {}, {a}, a A, sont des langages rguliers,Si L1 et L2 sont des langages rguliers alors il en est de mme pour L1 L2 {1 |2 / 1 L1, 2 L2}, Si L1 et L2 sont des langages rguliers alors il en est de mme pour L1L2 {1 2 / 1 L1, 2 L2},Si L est un langage rgulier alors il en est de mme pour L* nn{1 2 n | i L}69Lensemble des expressions rgulires sur un alphabet A est dfini de manire inductive par:, et a pour a A sont des expressions rgulires.Si r1 et r2 sont des expressions rgulires alors il en est de mme pour (r1|r2), r1r2.Si r est une expression rgulire alors il en est de mme pour (r)*.70Chaque expression rgulire r dtermine un langage rgulier L(r).L() = L() = {}L(a) = {a}L((r1|r2)) = L(r1) L(r2)L(r1r2) = L(r1)L(r2)L((r)*) = L(r)*

71Automates tats finisAutomates tats finisUn reconnaisseur pour un langage est un programme qui prend en entre une chane x et rpond "oui" si x est une chane du langage et "non" autrement.

On compile une expression rgulire en un reconnaisseur en construisant un diagramme de transition gnralis appel automate fini.

Un automate fini peut tre dterministe ou non dterministe.73Quest-ce quun automate?Un automate fini non dterministe (AFN) est un modle mathmatique qui consiste :un alphabet A, un ensemble Q dtats dans lequel on distingue un tat initial q0, une relation de transition qui est un sous ensemble de : Q A {} Q,Un sous ensemble d'tats F distingu comme tats d'acceptation ou tats finals.

Si {p, , q} , on crira p q o A {} c. d. il est soit le mot vide soit une lettre. 74

Reprsentation des automatesUn automate est souvent reprsent par un graphe orient dont les sommets sont des tats et les artes tiquetes correspondent aux transitions. 75Automate Fini Non Dterministe76q0q1q3q2q42413tats d'acceptationtats d'acceptationtat InitialExemple1Soit le langage dnot par lexpression rgulire (a | b)* abbNous allons reprsenter l'AFN qui reconnat ce langage.77Exemple 178

(a | b)* abbAutomate Fini Non DterministeUn AFN accepte une chane dentre x si et seulement si il existe un certain chemin dans l'AFN entre ltat de dpart et un tat dacceptation, tel que les tiquettes darcs le long de ce chemin pellent la chaine x.79Automate Fini Non Dterministe80abbaabbbabbaaabbVrifions que les chaines d'entres suivantes sont acceptes par l'AFN.

Automate Fini Non DterministeUn chemin peut tre reprsent par une suite de transitions dtat appele dplacements. Ce diagramme montre les dplacement ralises en acceptant la chane dentre aabb.81

Automate Fini Non DterministeEn gnral, il existe plus dune suite de dplacements pouvant mener ltat dacceptation.Bien dautres suites de dplacements pourrait tre faites sur la chane dentre aabb, mais aucune des autres narrive terminer dans un tat dacceptation.

Cette suite stationne dans ltat de non acceptation 0.82

ExerciceConstruire l'automate pour l'expression a(a|0)*

Vrifier que les mots aaooo aoo aaaa aoaoao sont vrifie par l'AFNDonner le chemin de dplacement de chacun de ces mots.83Automate Fini DterministeLautomate est dit dterministe (AFD) lorsque la relation de transition est une fonction (partielle) de Q A dans Q.

chaque tat et pour chaque caractre dentre, il y a au plus un tat vers lequel une relation peut avoir lieu.84Automate Fini DterministeUn automate fini dterministe a au plus une transition partir de chaque tat sur nimporte quel symbole.

Il est trs facile de dterminer si un automate fini dterministe accepte une chane dentre, puisquil existe au plus un chemin depuis ltat de dpart tiquet par cette chane.Exemple

bLa figure suivante prsente le graphe de transition dun automate fini dterministe qui accepte la langage (a|b)* abbabbaabbbabbaaabbababbNous vrifions que chacune des chaines ne passe que par un seul cheminIl y a conflit temps/ place : Les automates finis dterministes produisent des connaisseurs plus rapides que les automates finis non dterministes.Un automate fini dterministe peut tre beaucoup plus volumineux quun automate fini non dterministe.Transformation d'une expression rgulire en un AFDUne faon de construire un reconnaisseur partir dune expression rgulire consiste construire un AFN partir dune expression rgulire ensuite simuler le comportement de lAFN sur une chane dentre.

Si la vitesse dexcution est essentielle, on peut convertir le AFN en AFD.Construction d'un AFN partir d'une expression rgulireL'algorithme de construction d'AFN utilise la structure syntaxique de l'expression rgulire pour guider le processus de construction.Algorithme de Construction d'un AFN partir d'un L(r)On dcompose dabord r en ses sous expressions. On construit des AFN pour chacun des symboles de base (alphabet) de r.

Pour , construire l'AFN :

Pour a A construire l'AFN :i1f1i2f2ai1 est un nouvel tat de dpart et f1 un nouvel tat dacceptation. Il est clair que cet AFN reconnaisse {}i2 est un nouvel tat de dpart et f2 un nouvel tat dacceptation. Il est clair que cet AFN reconnaisse {a}Supposons que N(s) et N(t) soient les AFN pour les expressions rgulires s et t.Pour lexpression rgulire s|t, construire lAFN compos suivant N(s|t):ifN(s)N(t)Exemple L(r) = r1|r2ii1i2f1f2fr1r2Pour lexpression rgulire stConstruire lAFN compos N(st)

Ltat de dpart de N(s) devient ltat de dpart de lAFN compos.et ltat dacceptation de N(s) est fusionn avec ltat de dpart de N(t).L'tat d'acceptation de N(t) devient l'tat d'acceptation de l'AFN compos.N(s)N(t)fPour lexpression rgulire S*construire lAFN compos N(S*)N(s)ifIci, i est un nouvel tat de dpart et f un nouvel tat dacceptation. Dans lAFN compos, on peut aller de i f directement en suivant un arc tiquet , ou bien on peut aller de i f en traversant N(s) une ou plusieurs fois. Il est clair que lautomate compos reconnaisse (L(s))*.RemarqueChaque fois quon construit un nouvel tat, on lui donne un nom distinct. Ainsi, il ne peut y avoir deux tat dans deux sous-automates qui aient le mme nom.Mme si le mme symbole apparat plusieurs fois dans r, on cre, pour chaque instance de ce symbole, un AFN spar avec ses propres tats.Exemplesoit lexpression rgulire r = (a|b)* abb. La figure suivante prsente un arbre syntaxique pour r:

r = (a|b)* abbpour le composant r1le premier a, on construit lAFN

r = (a|b)* abbpour r2

r = (a|b)* abbr3=r1|r2pour r3=r1|r2 On peut maintenant combiner N(r1) et N(r2) en utilisant la rgle dunion pour obtenir lAFN

r = (a|b)* abbLAFN pour r4 est le mme que celui pour r3LAFN pour (r4)*

r = (a|b)* abbr6= aLAFN pour r6= a

r = (a|b)* abbPour obtenir lautomate pour r7 =r5r6,On fusionne les tats 7 et 7 en appelant ltat rsultant 7

r = (a|b)* abbr8= bLAFN pour r8= b

b

r = (a|b)* abbr9= r7r8On fusionne les tats 8 et 8 en appelant ltat rsultant 8

r = (a|b)* abbr10= bLAFN pour r8= b

b

r = (a|b)* abbr11= r9r10On fusionne les tats 9 et 9 en appelant ltat rsultant 9

ExerciceConstruire l'automate pour l'expression a(a|0)*118Reconnaissance des units lexicalesMmorisation du texte d'entreOn utilise un tampon divis en deux moitis de N caractres

On lit N caractres dentres dans chacune des entres du tampon en une seule commande systme de lecture, plutt que dinvoquer une commande de lecture pour chaque caractre dentre.

Sil reste moins que N caractres en entre, un caractre spcial fdf est plac dans le tampon aprs les caractres dentre.On gre deux pointeurs vers le tampon dentres.

La chane de caractres entre les deux pointeurs constitue le lexme courant.

Au dpart les deux pointeurs dsignent le premier caractre du prochain lexme trouver.

Lun appel le pointeur Avant , lit en avant jusqu trouver un modle. n:=*a2*DbutAvantbrUne fois que le prochain lexme est reconnu, le pointeur Avant est positionn sur le caractre sa droite.

DbutAvantia6=ntn=*2abrAprs traitement de ce lexme, les deux pointeurs sont positionns sur le caractre qui suit immdiatement le lexme.

DbutAvantia6=ntn=*2abrSi le pointeur Avant est sur le point de dpasser la marque de moiti, la moiti droite est remplie avec N nouveaux caractres dentre.

snb=r6>DbutAvantin=*2abrDbutAvantia6=ntn=*2abrSi le pointeur Avant est sur le point de dpasser lextrmit droite du tampon, la partie gauche est remplie avec N nouveaux caractres dentres, et le pointeur Avant poursuit circulairement au dbut du tampon.snb=r6>DbutAvantin=*2abrsnb=r6>DbutAvantiars=baloExemple Instr Si expr Alors instr | Si expr Alors instr Sinon instr | expr terme Oprel terme | termeterme id | nbO les terminaux si, alors, sinon, oprel, id et nb(jetons) engendrent les ensembles de chanes donnes par les dfinitions rgulires suivantes.Si siAlors alorsSinon sinonOprel < | | >=Id lettre (lettre | chiffre)*Nb chiffre(Chiffre)*Lettre et chiffre sont dfinis comme suit :Lettre A | B | . | Z | a | b | . |zChiffre 0 | 1 | . |9AFNOn utilise un AFN pour garder trace des informations sur les caractres rencontrs quand le pointeur avant parcourt le texte dentre. On procde par des dplacements de position en position dans le diagramme au fur et mesure de la lecture des caractres.

Ltiquette autre dsigne tous les caractres autres que ceux qui sont indiqus explicitement sur les arcs quittant 0 et 1.

Si le caractre > et un autre caractre sont lus quand on progresse dans la suite darcs depuis ltat initial jusqu ltat dacceptation 8. Alors, tant donn que le caractre supplmentaire ne fait pas partie de loprateur de relation on doit reculer le pointeur avant dun caractre. On utilise une * pour signaler les tats dans lesquels ce recul dans lentre doit tre fait.En gnral, il peut y avoir plusieurs diagrammes de transition, chacun dentre-eux spcifiant un groupe dunits lexicales. Si un chec se produit quand on parcoure un diagramme de transition, alors on recule le pointeur avant l ou il tait ltat initial de ce diagramme et on active le diagramme de transition suivant (le pointeur avant est recul la position du pointeur dbut).Si un chec intervient dans tous les diagrammes de transition, alors une erreur lexicale a t dtecte et on appelle une routine de rcupration sur erreur.RemarqueComme les mots cls sont des suites de lettres, il y a des exceptions la rgle selon laquelle une suite de lettres ou de chiffres dbutant par une lettre est un identificateur.

Plutt que de coder les exceptions dans un diagramme de transition, une astuce consiste traiter les mots cls comme des identificateurs spciaux quand on atteint ltat dacceptation, on excute un certain code pour dterminer si le lexme amenant cet tat dacceptation est un mot cl ou un identificateur.Une technique simple pour sparer les mots cl des identificateurs consiste diviser la table de symboles en deux parties : une partie statique au dbut de la table de symboles dans laquelle on place les mots cl (si, alors, sinon) avant quaucun caractre nait t lu et une partie dynamique en bas pour les identificateurs.Type de variableType de tokenTokenNumro de symbolemot clfor10mot clto11mot cldo12sparateur;13......affectation:=100+101...identi1000identa1001identvmax1002...entier15001...La table des symboles138Linstruction de retour qui suit ltat dacceptation utilise Unilex Id( ) et Ranger Id() pour obtenir lunit lexicale et la valeur dattribut respectivement.

Ranger Id()travaille comme suit : elle a accs au tampon ou lunit lexicale identificateur a t trouve.Elle examine la table des symboles et :Si elle trouve le lexme avec lindication mot cl, Ranger Id ( ) rend 0.Si elle trouve le lexme comme variable du programme, Ranger Id() rend un pointeur vers lentre dans la table des symboles.Si elle ne trouve pas le lexme dans la table des symboles, elle le place en tant que variable et un pointeur vers cette nouvelle entre est retourn.140La procdure Unilex Id( )de manire similaire, recherche le lexme dans la table des symboles. Si le lexme est un mot cl, lunit lexicale correspondante est retourne ; autrement, lunit lexicale ident est retourne.

Chapitre 4L'analyse SyntaxiqueIntroductionL'analyse syntaxique est lune des oprations majeures dun compilateur qui consiste indiquer si un texte est grammaticalement correct et en tirer une reprsentation interne, que lon appelle arbre syntaxique.

GrammaireDfinitionUne grammaire est un ensemble de rgles permettant de dire si une phrase, c'est--dire une suite de mots ou lexmes, est correcte ou non. Les rgles qui nous intressent en informatique sont celles qui donnent une description gnrative du langage, en indiquant comment prcisment construire de telles phrase. exemple Soit la dfinition d'une rgle gnrative suivante:Une phrase se compose dune proposition sujet, dun verbe et dune proposition complment.

Alors quune dfinition de la forme:La subordonne relative complte un nom ou un groupe nominal appartenant la proposition principale nest pas gnrative: elle ne nous dit pas comment effectivement construire une subordonne relative.

Arbres et rgles de grammaireLa structure dune phrase est gnralement rcursive. Par exemple:une phrase contient un groupe nominal et un groupe verbal, Un groupe verbal est compos lui-mme dun groupe nominal. De plus, un groupe nominal peut lui-mme contenir des groupes nominaux sous la forme de subordonnes relatives.Lexpression de la structure dune phrase sexprime sous la forme dun arbre, que lon appelle arbre syntaxique (ou arbre de drivation) dune phrase.Exemplele chat qui est sur la commode regarde la souris

GVLes feuilles de larbre correspondent aux mots de la phraseles nuds non-terminaux correspondent aux catgories grammaticalesLes rgles de grammaire peuvent tre donnes sous la forme de rgles de rcritures (quon appelle aussi parfois rgles de productions) qui indiquent comment une catgorie grammaticale peut tre transforme en une suite de catgories grammaticales ou de mots du vocabulaire.

Exemple | | le | la | les ... chat | commode | souris | ... est | regarde sur | sous | ... qui | que | dont | ...

Quelques lments grammaticaux de Pascal program | ; begin end ...Dfinition d'une drivationA

A . si 1 2 .. n,

on dit que 1 se drive en n.

le symbole signifie "se drive en une tape"pour dire "se drive en zro, une ou plusieurs tapes"

on peut utiliser le symbole *si * et , alors *

+Signifie"se drive en une ou plusieurs tapes"soit une grammaire G et S son axiome; on peut utiliser la relation+pour dfinir L(G), le langage engendr par G. On dit quune chane de terminaux w appartient L(G) ssi S + w. La chane w est appele phrase de G.un langage qui peut tre engendr par une grammaire est dit langage non contextuel.si S * , o peut contenir certains non terminaux, on dit que est une proto-phrase de G.ExempleSoit la grammaire G(VT,VN,S,P)E E+E|E*E|(E)|-E|idla chane -(id+id) est une phrase de la grammaire G car on a la drivation:E -E -(E) -(E+E) -(id+E) -(id+id) Les chanes E, -E, -(E),., -(id+E) sont toutes des proto-phrases de cette grammaire.

On crit E * -(id+id) pour indiquer que E se drive en (id+id)

E -E -(E) -(E+E) -(id+E) -(id+id) A chaque tape dune drivation, on doit faire deux choixIl faut choisir le non terminal remplacerQuelle alternative utiliser pour ce non terminalDrivation gaucheSeul le non treminal le plus gauche est remplac chaque tape. On crit g on peut alors rcrire GE g-E g-(E) g-(E+E) g-(id+E) g-(id+id)E E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idsi S * g on dit que est une proto-phrase gauche de la grammaire considre.Drivation droitele terminal la plus droite est remplace chaque tapeOn crit

d on peut alors rcrire GE d-E d-(E) d-(E+E) d-(E+id) d-(id+id)E E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idE E+E|E*E|(E)|-E|idArbres d'analyse et drivationsDfinition Arbre d'analyseUn arbre d'analyse ou syntaxique illustre visuellement la manire dont laxiome dune grammaire se drive en une chane du langage. Si le non terminal A est dfini par la production A XYZ

169alors un arbre syntaxique peut possder un nud intrieur tiquet Aet avoir trois fils tiquets X,Y et Z, de gauche droite.AXYZFormellementtant donn une grammaire non contextuelle, un arbre syntaxique est un arbre possdant les proprits suivantes:La racine est tiquete par laxiomechaque feuille est tiquete par une unit lexicalechaque nud intrieur est tiquet par un non terminal.Si A est le non-terminal tiquetant un nud intrieur et si les tiquettes des fils de ce nud sont, de gauche droite, X1,X2,..,Xn, alors A X1X2.Xn est une production,ici X1,X2, .,Xn reprsentant soit un non terminal, soit un terminal.

Exempleliste liste + chiffreliste liste - chiffreliste chiffrechiffre 0|1|2|3|4|5|6|7|8|9Drivons la chaine 9-5+2AmbigutUne grammaire peut avoir plus dun arbre syntaxique qui engendre une chane donne dunits lexicales. Une telle grammaire est dite ambigu.

Comme une telle chane a habituellement plus dune signification, on a besoin de travailler avec des grammaires non ambigus.Exemple ::= | |::= if then |if then else ::= ::= a | b | c::= >|=| b then if a > c then a:=3 elsea := 9

if

then

a>bif

then

a>c

a:=

3else

a:=

9

if

then

a>bif

then

a>c

a:=

3else

a:=

9Processus danalyseProblmeConstruire larbre syntaxique dune phrase partir dune grammaire.Il existe essentiellement deux types de processus:

lanalyse descendante, dans laquelle on construit larbre en descendant de la racine vers les feuilles.

lanalyse ascendante construit larbre syntaxique en montant des feuilles vers la racine. Analyse descendanteLalgorithme danalyse est rcursif. Son problme est celui de la terminaison: il ne peut sarrter sil y a une infinit dappels embots sans lecture.

DfinitionLanalyse descendante peut-tre considre comme une tentative pour dterminer une drivation gauche associe une chane dentre.

Elle peut-tre aussi vue comme une tentative pour construire un arbre danalyse de la chane dentre, en partant de la racine et en crant les nuds de larbre suivant un ordre prdfini.ExempleS cAdA ab|a

Soit la chane dentre suivant :

w = cadw = cadS cAdA ab|apointeur dentreScAabw = cadS cAdA ab|apointeur dentreScAadRemarqueUne grammaire rcursive gauche peut faire boucler un analyseur par descente rcursive mme sil possde un mcanisme de retour arrire.En effet dans le cas de A A|ab|a, en essayant de dvelopper A, on peut ventuellement se retrouver en train de dvelopper A de nouveau, et cela sans avoirconsomm de symbole en entre.

Nous devons liminer la rcursivit gaucheAAAAAA A|ab|aSuppression de la rcursivit gaucheDfinition: une grammaire est rcursive gauche si elle contient un non-terminal A tel quil existe une drivation A + A, o est une chane quelconque.Suppression de la rcursivit gaucheQuelque soit le nombre de A-productions, il est possible dliminer les rcursivits gauche immdiates par la technique suivante:A A1A A2A A AmA 1A 2..A n

Dans un premier temps, on groupe les A-productions comme suit:A A1| A2| ...| Am|1|2||n o aucune i ne commence par un A. Ensuite on remplace les A-productions par:A 1A|2A|| nAA 1A| 2A| ...| m A|A A1A A2A A AmA 1A 2..A nA A|ab|a

A abA'|aA'A' A'|abAA'abA'Analyse Ascendantenous introduisons un modle gnral danalyse syntaxique ascendante, connu sous le nom danalyse par dcalage-rduction.

Nous nous intressons une forme danalyse par dcalage-rduction facile implmenter, appele analyse par prcdence d'oprateurs.Lanalyse par dcalage-rduction a pour but de construire un arbre danalyse pour une chane source en commenant par les feuilles (le bas) et en remontant vers la racine(le haut). Ce processus peut-tre considr comme la "rduction" dune chane w vers laxiome de la grammaire. A chaque tape de rduction, une sous-chane particulirecorrespondant la partie droite dune production est remplace par le symbole de la partie gauche de cette production. ExempleS aABeA Abc|bB d

La phrase abbcde peut-tre rduite vers S par les tapes suivantes:abbcdeaAbcde production utilise A baAde production utilise A AbcaABe production utilise B dS production utilise S aABeS aABeA Abc|bB dCes rductions, laborent en sens inverse la drivation droite suivante:

S daABe daAde d aAbcde d abbcde