La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Publications similaires

Cours de Compilation-Exercices Master d’Informatique M1 2011–2012
Tabledesmati`eres
2
2
19septembre2011
Analyse lexicale 2.1Expressionsre´gulie`resetanalyselexicale....................... 2.2Reconnaissancedunechaˆınedecaract`eresparuneexpressionre´gulie`re...... 2.3Constructiondautomatesd´eterministes`apartirdexpressionsre´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 Lebutestdesquisserunanalyseurlexicalpourlemini-langageci-dessous.Pourchaqueentit´e lexicale,onindiqueletokenassocie´,savaleurainsiquelexpressionr´egulie`requilede´nit.
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 lope´rateur lope´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,tabulationetretourchariotnesontpassignicatifsetpeuvent apparaıˆtreennombrequelconque, Leschaˆınesdecaract`erespeuventcontenirdescaract`eresspe´ciauxquicommencentparle caract`ere\:\”,\n,\t,\\. – les commentaires se terminent au premier*)ˆreetnrctpas´ueveetnonnetprese.io´teebm 1.Donnerlesautomatesnisde´terministespourchacunedesexpressionsr´egulie`respuispour l’analyseur lexical complet. 2.Donnerunexempledechaˆınedecaracte`resdanslaquelleonpeutreconnaıˆtreplusieurs pr´exescorrespondant`adestokensdie´rents.
September 21, 2011
2
3.Quellessontlesdie´rencesentreunanalyseurlexicaletlareconnaissancedesmotsparun automate fini classique. 4.Donnerlastructureg´en´eraledelanalyseurlexical,´etantdonne´lesfonctions´ele´mentaires suivantes : initdealtdielni´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.nonuonaltest´etasilqieui,dntetaut´n token(s) sisalnatetn´tuesssoci´e.elotekanr,neovei transit(s, cdenttstavauieiove´lner)ssianatrrlpati´eontipee´teuqrac, renvoieechec danslecasou`unetelletransitionnexistepas. lireoiecaract`erelu`lapasotioin()rtpvnerptreadcnofaL.reubelsnllieesouch´eonti rencontre une fin de fichier.
2.2Reconnaissancedunechaıˆnedecaracte`resparuneexpressionr´eguli`ere (Partiel novembre 2000) Danscetexercice,onseproposede´crireunefonctiondetestdappartenancedunmotau langageL(re´ugile`errnoisserpxeenuraipn´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 (*r1|r2*) | Produit of expreg * expreg (*r1r2*) | Etoile of expreg (*r*) 1.De´nirunefonctioncontient epsilon:expregbooledivuqdi´eterminesilemotappartientaulangagede´niparuneexpressionr´eguli`eredonn´ee. 2.Ond´enitler´usedirpseenxedueeri`ulegr´onsiracnua`tropparrapract`erecdelaman`iree suivante : Res(r, c) ={w|cwL(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:expregcharexpregrdeartit`apnaluclacret decune 0 0 expressionr´egulie`rertelle queL(r) =Res(r, c). (c) Calculerresidur clscesa`uodnar= (a|b)aetc∈ {a, b}. 3.Ende´duireunefonctionreconnait:expregchar listbooliuqte´dmiersineeun listedecaracte`resappartientaulangaged´eniparuneexpressionr´eguli`eredonne´e. 4.Appliquercettefonction`alareconnaissancedumotabaisserpxeluge´rnoeeri`arlpr= (a|b)a
2.3Constructiondautomatesd´eterministes`apartirdexpressionsre´guli`eres Onremarquetoutdabordquesiunautomatenireconnaıˆtlelangagecorrespondanta` lexpressionre´guli`ererhaquelettreluesuueenlaro`scaorecirfadronspre´rtnelrtuepnoee occurrence d’une lettre dans l’expressionr. Onindexechaqueoccurrencedunelettredanslexpressionr´egulie`reparunentierdemanie`rea` distinguerlesdie´rentesoccurrencesdunemˆemelettre.