Cours de Compilation-Exercices
8
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
8
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Master, Supérieur, Master
Voir
- cours - matière potentielle : compilation - exercices master d' informatique m1
- numero
- prefixes correspondant
- expreg →
- nr avec nr
- caractere
- int
- automates
- automate
- tables
- table
- langages
- langage
- ligne
- lignes
Publié par
Langue
Français
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 (*r1|r2*) | Produit of expreg * expreg (*r1r2*) ∗ | 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.
