[PDF] [PDF] Analyse lexicale

[PDF] Générer un analyseur avec Flex&Bison - ENIB

Générer un analyseur avec Flex&Bison Généralités Analyse lexicale avec Flex Analyse syntaxique avec Bison Association de Flex et Bison Fabrice Harrouet

[PDF] Chapitre 6 : Outil danalyse lexicale : Flex - Pr ABDELMAJID

Description de Flex Quelques exemples simples Format d'un fichier Flex Prof Abdelmajid Dargham Chapitre 6 : Analyse lexicale avec Flex 

[PDF] Analyse lexicale

Outils automatiques: Flex Révision hiver 2018 p 7 Interface avec l'analyseur lexical entrée analyseur lexical (Lien avec l'horizon de l'analyseur lexical )

[PDF] L3 Informatique Compilation TP01 - ANALYSE LEXICALE 1 Objectif

L'objectif de ce TP est de programmer un analyseur lexical pour le langage L symboles h avec flex, vous pouvez inclure symboles h dans votre fichier flex

[PDF] Thème 1 Analyse Lexicale, Analyse Syntaxique - Laure Gonnord

1 1 Un peu de cours 1 1 1 Analyse Lexicale avec flex Le but de l'analyse lexicale est de transformer une suite de symboles en terminaux (un terminal peut être

[PDF] lex et yacc

lexicales, afin qu'elles puissent être partagées par l'analyseur syntaxique et l' analyseur lexical $ flex calc l produit le fichier : lex yy c qui contient le code en c de 

[PDF] Travaux Pratiques Compilation no1 - IGM

Compiler l'analyseur lexical avec flex tp1-ex1 l, ceci engendre un fichier lex yy c — Compiler le fichier C obtenu avec gcc, puis tester l'exécutable a out obtenu

[PDF] Chapitre 1 Construction dun analyseur lexical : scanner - Free

Après l'analyse syntaxique, on récupère un ensemble de tokens Il s'agit de voir Type 1, grammaire context sensitive avec des règles de type uAv → uwv Reconnu Comment spécifier les tokens lorsqu'on les définit dans flex ? L'idée est 

[PDF] Introduction à la compilation - Département dinformatique de l

La configuration de flex est décrite dans un fichier texte (extensions l ou lex) ➢ Flex traduit L'analyseur lexical le plus court recopie le flot d'entrée sur le flot de sortie : Cours de l'analyse reprend avec les autres expressions rationnelles

[PDF] flex et bison pdf

[PDF] analyseur syntaxique avec flex et bison

[PDF] exercice flex avec correction

[PDF] lex yacc exemple

[PDF] allocution bienvenue association

[PDF] fin de la démocratie athénienne

[PDF] l'apogée d'athènes

[PDF] fondation d'athènes

[PDF] apogée d'athènes date

[PDF] auteurs francophones connus

[PDF] liste des auteurs africains et leurs oeuvres pdf

[PDF] auteurs francophones contemporains

[PDF] littérature francophone est elle une littérature française

[PDF] auteurs francophones africains

[PDF] littérature francophone définition

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 1

Analyse lexicale

Sections 2.6 et 3.1 `a 3.4

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 2

* Contenu * •Rˆole de l"analyseur lexical •Vocabulaire •Gestion des erreurs •D´efinitions en th´eorie des langages •Reconnaissance des jetons •Analyse lexicale vorace •Programmation d"un analyseur lexical •Exemple d"analyseur lexical plus complet en C •Outils automatiques: Flex

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 3

Extensions aux expressions arithm´etiques

Section 2.6

Dans les notes de cours du chapitre 2, on a vu la grammaire qui g´en`ere les "suites de chiffres s´epar´es par des signes d"addition ou de soustraction". list→list+digit list→list-digit list→digit digit→0|1|2|3|4|5|6|7|8|9 En utilisant cette syntaxe telle quelle, il n"y aurait pas vraiment de besoin d"analyse lexicale. Chaque jeton (terminal) correspond `a un seul caract`ere. Aussi, rien n"est pr´evu pour des espacements ou des sauts deligne. Les langages r´ealistes ont tendance `a ˆetre plus permissifs.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 4

Espacements et commentaires

La plupart des langages permettent la pr´esence d"espacements entre les jetons. Aussi, la plupart offrent une notation qui permet d"ajouter des commentaires au programme. Bien que les espacements et les commentaires peuvent possiblement jouer un rˆole dans la s´eparation des jetons au niveau du programme source, le traducteur n"est pas int´eress´e outre mesure en leur nature. Ils sont donc rapidement ´elimin´es par les compilateurs. Ils peuvent l"ˆetre au niveau de l"analyseur lexical ou au niveau de l"analyseur syntaxique. C"est normalement beaucoup plus simple de le faire au niveaude l"analyseur lexical.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 5

Constantes `a plusieurs chiffres

Par exemple, dans un langage plus r´ealiste, on remplacerait les constantes num´eriques `a un caract`ere par des constantes `aau moinsun caract`ere. C"est normalement l"analyseur lexical qui s"occupe de rassembler la suite de chiffres en un jeton. C"est plus simple ainsi. De plus, l"analyseur syntaxique ne gagne rien `a recevoir les chiffres un `a un. Quand l"analyseur lexical tombe sur une suite de chiffres en entr´ee, il envoie le jeton num`a l"analyseur syntaxique. La valeur du nombre est envoy´eeen tant qu"attributdu jeton.

Par exemple, l"entr´ee:

31 + 28 + 59

est transform´ee en la s´equence de paires jetons/attributs: ?num, 31? ?+,? ?num, 28? ?+,? ?num, 59?

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 6

Identificateurs et mots-cl´es

On souhaite que l"analyseur lexical transforme l"entr´ee suivante: count = count + increment; en la suite de jetons suivants: id=id+id; Toutefois, les attributs li´es aux deux premi`eres apparitions deiddoivent indiquer qu"on a affaire `a l"identificateurcountet celui li´e `a la troisi`eme, `a l"identificateurincrement. Les identificateurs sont normalement list´es dans latable des symboles. Les attributs li´es aux trois jetonsidsont alors des pointeurs vers des entr´ees dans cette table.

Lorsqu"il y a des mots-cl´es et qu"ils sontr´eserv´es, les mots-cl´es sont inscrits au pr´ealable

dans la table des symboles. Une note sp´eciale indique qu"ils"agit de mots-cl´es r´eserv´es

et non de simples identificateurs.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 7

Interface avec l"analyseur lexical

entr´eeanalyseur lexicalanalyseur syntaxiquelire un caract`ere retourner un caract`erefournir un jeton et ses attributs???? L"analyseur lexical et l"analyseur syntaxique forment unepaireproducteur/consomma- teur. L"analyseur lexical doit parfois retourner un caract`ere qu"il vient de lire. Par exemple, il retourne un caract`ere lorsqu"il vient de lire '<" et constate que le caract`ere nouvellement lu n"est pas '=". (Lien avec l"horizon de l"analyseur lexical.) Le canal entre l"analyseur lexical et l"analyseur syntaxique est un tampon d"une capacit´e d"un certain nombre de jetons. L"analyseur syntaxique a parfois besoin de consulter les prochains jetons sans les consommer. (Lien avec l"horizon de l"analyseur syntaxique.) En pratique, ce tampon a rarement besoin d"ˆetre de taille plus que 1. Ainsi, l"analyseur lexical est une fonction directement appel´ee par l"analyseur syntaxique et qui retourne le prochain jeton.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 8

Un analyseur lexical simple en C

lexan()analyseur lexicalutilisegetchar() pour lire des caract. retournecavec ungetc(c,stdin)retourne un jeton `a l"appelant tokenval Les jetons sont retourn´es s´epar´ement des attributs. Les jetons sont retourn´es (`a la C) `a l"appelant sous la forme d"un entier tandis que les attributs sont mis dans une variable globale (tokenval).

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 9

Un analyseur lexical simple en C

#include #include #define NUM 256 int lineno = 1; int tokenval = NONE; int lexan() int t; while (1) { t = getchar(); if (t == " " || t == "\t") ; /* elimine les espaces et les tabulations */ else if (t == "\n") lineno = lineno + 1; else if (isdigit(t)) { tokenval = t - "0"; t = getchar(); while (isdigit(t)) { tokenval = tokenval*10 + t - "0"; t = getchar(); ungetc(t, stdin); return NUM; else { tokenval = NONE; return t;

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 10

Analyse lexicale

Chapitre 3

Aborde la sp´ecification et l"implantation des analyseurs lexicaux. Une m´ethode simple d"implantation d"analyseurs lexicauxconsiste `a bˆatir des diagrammes qui montrent la structure des jetons et ensuite `a traduire `a la main ces diagrammes en code. Les techniques utilis´ees en analyse lexicale s"appliquent non seulement en compilation mais

dans les langages de requˆetes, les syst`emes d"extractiond"information et aussi en g´en´etique.

Toutes ces applications ont en commun la d´etection demotifsdans des chaˆınes. Un lan-

gage de cr´eation automatis´ee d"analyseurs lexicaux, appel´e Lex, permet de sp´ecifier le com-

portement d"un analyseur `a l"aide d"expressions r´eguli`eres. Les expressions r´eguli`eres sont

transform´ees en un automate fini d´eterministe efficace. Plusieurs autres langages emploient des expressions r´eguli`eres. L"utilitaire AWK re¸coit ses

instructions notamment grˆace `a des expressions r´eguli`eres qui sp´ecifient quelles lignes doivent

ˆetre trait´ees et comment. Les interpr`etes de commandes,tels quebashouDOS, reconnaissent des expressions r´eguli`eres simples comme '*.pdf". Le langage Perl les supporte aussi.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 11

Rˆoles de l"analyseur lexical

•Lire une suite de caract`eres de l"entr´ee et produire une suite de jetons (ad´equats pour l"analyse syntaxique). •D´ebarrasser le programme des commentaires et des espace-ments. •Tenir `a jour les coordonn´ees (ligne, colonne) dans le programme pour fin de production des ´eventuels messages d"erreur.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 12

S´eparation lexical-syntaxique

Il y a plusieurs raisons pour avoir une s´eparation entre l"analyseur lexical et l"analyseur syntaxique: •Simplicit´e du design. •Efficacit´e du compilateur. •Plus grande portabilit´e du compilateur. Le jeu de caract`eres en entr´ee peut varier d"une machine `a l"autre. Une plus petite partie du compilateur est "contamin´ee" par ces sp´ecificit´es.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 13

Vocabulaire

Jeton:Cat´egorie lexicale qui est transmise `a l"analyseur syntaxique.

Motif:(pattern) Description des chaˆınes qui peuvent ˆetre interpr´et´ees comme un jeton

donn´e.

Lex`eme:Sous-chaˆıne de l"entr´ee qui a ´et´e reconnue comme ´etantconforme `a un motif.

Sert habituellement `a calculer le(s) attribut(s) du jetonqui s"en trouve ´emis. Jeton

Description du motif

Exemples de lex`emes

const const const if if if relation ou>ou>= id une lettre suivie de lettres et de chiffres pi,count,D2 num une constante num´erique

3.1416,0,6.02E23

literal des caract`eres (sauf") entre"et" "core dumped"

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 14

Gestion des erreurs

Certaines erreurs sont v´eritablement de nature lexicale.Par exemple, ren- contrer le caract`ere ASCII num´ero 14, qui ne doit jamais apparaˆıtre dans les programmes sources d"un langage donn´e. Plusieurs erreurs ne peuvent pas ˆetre g´er´e au niveau de l"analyseur lexical. Par exemple, on retrouve dans le programme source la chaˆıne: fi ( a == f(x) )... Cette erreur nous semble de nature lexicale `a cause de la faute d"orthographe mais 'fi" constitue un identificateur tout `a fait valide.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 15

Gestion des erreurs

Il y a plusieurs moyens de g´erer une erreur lexicale: •Arrˆeter toute la compilation avec un message d"erreur.

•Abandonner des caract`eres de l"entr´ee jusqu"`a ce qu"un jeton bien form´e soit disponible.

•Effectuer une ou plusieurs op´erations d"´edition comme: -Effacer un caract`ere. (Assure la terminaison.) -Ins´erer un caract`ere [ad´equat]. -Remplacer un caract`ere par un autre. -Inverser l"ordre de deux caract`eres cons´ecutifs. •Trouver une distance d"´edition minimale pour obtenir un programme lexicalement valide `a partir du programme source.

Un avantage `a tenter de recouvrer un ´etat stable apr`es uneerreur lexicale consiste `a possiblement

fournir une liste d"erreurs plus compl`ete pour le programme.

Un inconv´enient consiste `a possiblement confondre les ´etapes suivantes de la compilation et ainsi

g´en´erer des erreurs de compilation incongrues.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 16

Analyse Lexicale :

Th´eorie des langages

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 17

D´efinitions en th´eorie des langages

Alphabet:ensemble fini de symboles.

Chaˆıne:suite finie de symboles tir´es d"un alphabet donn´e. Parfois, on dit aussimot. Longueur d"une chaˆıne:nombre de symboles qui constitue la chaˆıne. On d´enote la longueur d"une chaˆınewpar|w|. Chaˆıne vide:chaˆıne de longueur 0, qu"on d´enote?.

Langage:

´Etant donn´e un alphabetΣ, un ensemble de chaˆınes toutes tir´ees deΣ. Concat´enation:On d´enote la concat´enation de deux chaˆıneswetxpar wxet parfois parw·x, lorsqu"on veut un op´erateur visible. Exponentiation:R´ep´etition d"une mˆeme concat´enation, d´enot´eewno`u n?IN. On la d´efinit comme:w0=?etw(n+1)=w·wn.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 18

D´efinitions en th´eorie des langages

Terme

D´efinition

pr´efixedes

Une chaˆınewtelle que?vtel quewv=s.

suffixedes

Une chaˆınewtelle que?vtel quevw=s.

sous-chaˆınedes

Une chaˆınewtelle que?u,vtel queuwv=s.

pr´efixe, suffixe ou sous- chaˆınepropredes Une chaˆınew,s?=w?=?, telle quewest un pr´efixe, suffixe ou sous-chaˆıne des, respectivement. sous-s´equencedes Une chaˆınewobtenue desen laissant tomber cer- tains des symboles mais en conservant leur ordre.

Op´eration

D´efinition

uniondeLetM

L?M={s|s?Lous?M}

concat´enationdeLetM

LM={st|s?Lett?M}

fermeture de KleenedeL

L?=∞?

i=0L i fermeture positivedeL

L+=∞?

i=1L i

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 19

D´efinitions en th´eorie des langages

Lesexpressions r´eguli`erespeuvent ˆetre d´efinies inductivement ainsi. Supposons queretssont des

expressions r´eguli`eres, alors les termes suivants sont aussi des expressions r´eguli`eres: •t=∅, tel queL(t) =∅; •t=?, tel queL(t) ={?}; •t=ao`ua?Σ, tel queL(t) ={a}; •t=r|s, tel queL(t) =L(r)?L(s); •t=rs, tel queL(t) =L(r)L(s); •t=r?, tel queL(t) = (L(r))?; •t= (r), tel queL(t) =L(r). On dit qu"un langageLestr´eguliers"il existe une expression r´eguli`erertelle queL(r) =L.

Il faut utiliser des parenth`eses lorsqu"on veut affecter l"ordre d"application des op´erateurs sachant qu"ils

sont ordonn´es ainsi: ?,·et|, du plus prioritaire au moins prioritaire. Il existe des langages qui ne sont pas r´eguliers. Par exemple,{ww|w? {a,b}?}est irr´egulier. Deux expressions r´eguli`eresretssont dites´equivalentessiL(r) =L(s).

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 20

D´efinitions en th´eorie des langages

Loisr|r≡rr|s≡s|r

r|(s|t)≡(r|s)|t r(st)≡(rs)tr(s|t)≡rs|rt r| ∅ ≡ ∅ |r≡rr∅ ≡ ∅r≡ ∅

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 21

D´efinitions en th´eorie des langages

Uned´efinition r´eguli`ere, ´etant donn´eΣ, est une suite de d´efinitions de la forme: d

1→r1

d

2→r2

d n→rn o`uriest une expression r´eguli`ere sur l"alphabetΣ? {d1,...,di-1}. Note:il ne faut pas confondre les d´efinitions r´eguli`eres avec les gram- maires hors-contexte.

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 22

D´efinitions en th´eorie des langages

Exemple 3.5: Les identificateurs en C sont des chaˆınes de lettres, chiffres etunder- scores. letter →A|...|Z|a|...|z| digit→0|...|9 id→letter (letter |digit)? Exemple 3.6: Les nombres entiers ou fractionnaires non sign´es sont deschaˆınes comme

5280,0.01234,6.336E4ou1.89E-4

digit→0|...|9 digits→digit digit? optionalFraction→.digits|? optionalExponent→(E(+|-|?)digits)|? number→digits optionalFraction optionalExponent

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 23

D´efinitions en th´eorie des langages

Voici quelques abr´eviations:

•r+≡rr? •r?≡r|? •[abc]≡a|b|c •[a-z]≡a|...|z •[ˆa-z]≡n"importe quel caract`ere saufa,...,z •[A-Za-z ]≡[A-Z]|[a-z]|[ •[ˆA-Za-z n"importe quel caract`ere sauf ceux dans[A-Za-z

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 24

Analyse Lexicale :

Reconnaissance des jetons

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 25

Reconnaissance des jetons

Notre but est d"ˆetre capable de reconnaˆıtre les jetons pour une certaine grammaire.

Voici le fragment de grammaire:

stmt→ifexprthenstmt |ifexprthenstmtelsestmt expr→termrelopterm |term term→id |num

et voici les d´efinitions r´eguli`eres qui g´en`erent les terminaux qui nous int´eressent:

if→if then→then else→else relop→<|<=|=|<>|>|>= id→letter(letter|digit)? delim→blank|tab|newline ws→delim+

IFT-3101Compilation et interpr´etation

R´evision hiver 2018 p. 26

Reconnaissance des jetons

Expression

r

´eguli`ere

Jeton

Attribut

ws if if then then else else id id pointeur vers la table des symb. num num valeur de la constante relop LT relop LE relop EQ relopquotesdbs_dbs13.pdfusesText_19