Cours de Compilation-Exercices

Description

Master, Supérieur, Master

• cours - matière potentielle : compilation - exercices master d' informatique m1

Cours de Compilation-Exercices Master d'Informatique M1 2011–2012 19 septembre 2011 Table des matieres 2 Analyse lexicale 1 2.1 Expressions regulieres et analyse lexicale . . . . . . . . . . . . . . . . . . . . . . . 1 2.2 Reconnaissance d'une chaıne de caracteres par une expression reguliere . . . . . . 2 2.3 Construction d'automates deterministes a partir d'expressions regulieres .

• numero
• prefixes correspondant
• expreg →
• nr avec nr
• caractere
• int
• automates
• automate
• tables
• table
• langages
• langage
• ligne
• lignes

Sujets

• Caractère
• Numero
• Correspondance
• Langage
• Automate
• String

Informations

• Publié par: onjou
• Nombre de lectures: 153
• Langue: Français

Extrait

Cours de Compilation-Exercices Master d’Informatique M1 2011–2012

Tabledesmati`eres

2

2

19septembre2011

Analyse lexicale 2.1Expressionsre´gulie`resetanalyselexicale....................... 2.2Reconnaissanced’unechaˆınedecaract`eresparuneexpressionre´gulie`re...... 2.3Constructiond’automatesd´eterministes`apartird’expressionsre´guli`eres..... 2.4Tablesdetransitionscompress´ees........................... 2.5 Analyseur lexical pour indexer un programme . . . . . . . . . . . . . . . . . . . . 2.6Repe´ragedesnume´rosdelignes............................ 2.7 Analyse lexicale d’un assembleur . . . . . . . . . . . . . . . . . . . . . . . . . . .

Analyse lexicale

1 1 2 2 3 4 5 8

2.1Expressionsre´guli`eresetanalyselexicale Lebutestd’esquisserunanalyseurlexicalpourlemini-langageci-dessous.Pourchaqueentit´e lexicale,onindiqueletokenassocie´,savaleurainsiquel’expressionr´egulie`requilede´finit.

Motscle´s

Identificateurs Entier Ope´rationarithm´etique Op´erationrelationnelle Chaıˆnesdecaracte`res R´eels

Commentaires

Token IF, THEN, ELSE, BEGIN, END ID INT OP REL STRING REAL

Valeur

le nom de l’identificateur la valeur l’ope´rateur l’ope´rateur lavaleurdelachaıˆne la valeur

ignore´s

Expressionr´eguli`ere lemotlui-mˆeme

lettre (lettre|chiffre)* (-)?(chiffre)+ +|-|*|/ <|<=|>|>=|=|<> ”n’importe quoi” (-)?entier.(entier)?(E (-)?entier)? avec entier=(chiffre)+ (* n’importe quoi *)

On adopte de plus les conventions suivantes : –Lescaract`eresblancs,tabulationetretourchariotnesontpassignificatifsetpeuvent apparaıˆtreennombrequelconque, –Leschaˆınesdecaract`erespeuventcontenirdescaract`eresspe´ciauxquicommencentparle caract`ere\:\”,\n,\t,\\. – les commentaires se terminent au premier*)ˆreetnrctpas´ueveetnonnetprese.io´teebm 1.Donnerlesautomatesfinisde´terministespourchacunedesexpressionsr´egulie`respuispour l’analyseur lexical complet. 2.Donnerunexempledechaˆınedecaracte`resdanslaquelleonpeutreconnaıˆtreplusieurs pr´efixescorrespondant`adestokensdiffe´rents.

September 21, 2011

2

3.Quellessontlesdiffe´rencesentreunanalyseurlexicaletlareconnaissancedesmotsparun automate fini classique. 4.Donnerlastructureg´en´eraledel’analyseurlexical,´etantdonne´lesfonctions´ele´mentaires suivantes : –initdealtdieln’i´teitaogmnaetl’´aeusti –chaine(x, yo)u`xetysont des positions dans le buffer, renvoie la chaˆıne comprise entre les deux positions. –terminal(s`o)usse.nonuofinaltest´etasil’qieui,dntetaut´n –token(s) sisalfinatetn´tuesssoci´e.elotekanr,neovei –transit(s, cdenttstavauieiove´’lner)ssianatrrlpati´eontipee´teuqrac, renvoieechec danslecasou`unetelletransitionn’existepas. –lireoiecaract`erelu`lapasotioin()rtpvnerptreadcnofaL.reffubelsnllieesouch´eonti rencontre une fin de fichier.

2.2Reconnaissanced’unechaıˆnedecaracte`resparuneexpressionr´eguli`ere (Partiel novembre 2000) Danscetexercice,onseproposed’e´crireunefonctiondetestd’appartenanced’unmotau langageL(re´ugile`errnoisserpxeenuraipfin´e)drxpressionsr´egul.eLesse´e´entesre`iessetnorrper par des objets du typeCamlsuivant: type expreg = | Vide (* Langage vide∅*) | Epsilon (* Mot vide*) |Caractereofchar(*Caract`erec*) | Union of expreg * expreg (*r 1 |r 2 *) | Produit of expreg * expreg (*r 1 r 2 *) ∗ | Etoile of expreg (*r*) 1.De´finirunefonctioncontient epsilon:expreg→booledivuqdi´eterminesilemot appartientaulangagede´finiparuneexpressionr´eguli`eredonn´ee. 2.Ond´efinitler´usedirpseenxedu’eeri`ulegr´onsiracnua`tropparrapract`erecdelaman`iree suivante : Res(r, c) ={w|cw∈L(r)} ∗ (a) CalculerRes(r, cd)nausa`olscer= (a|b)aetc∈ {a, b}. ´ (b) Le langageRes(r, crerie´rnilugere`cE.tparuneexpressioˆmmeˆeteer´dceir)i-luutpe une fonctionresidu:expreg→char→expregrdeartit`apnaluclacret decune 0 0 expressionr´egulie`rertelle queL(r) =Res(r, c). ∗ (c) Calculerresidur clscesa`uodnar= (a|b)aetc∈ {a, b}. 3.Ende´duireunefonctionreconnait:expreg→char list→booliuqte´dmiersineeun listedecaracte`resappartientaulangaged´efiniparuneexpressionr´eguli`eredonne´e. 4.Appliquercettefonction`alareconnaissancedumotabaisserpxeluge´rnoeeri`arl’pr= (a|b)∗a

2.3Constructiond’automatesd´eterministes`apartird’expressionsre´guli`eres Onremarquetoutd’abordquesiunautomatefinireconnaıˆtlelangagecorrespondanta` l’expressionre´guli`ererhaquelettreluesuueenlaro`scaorecirfadronspre´rtne’lrtuepnoee occurrence d’une lettre dans l’expressionr. Onindexechaqueoccurrenced’unelettredansl’expressionr´egulie`reparunentierdemanie`rea` distinguerlesdiffe´rentesoccurrencesd’unemˆemelettre.