Cours de Compilation-Exercices

Publié par

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
Publié le : mardi 27 mars 2012
Lecture(s) : 230
Source : lri.fr
Nombre de pages : 8
Voir plus Voir moins
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.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.