Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

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

Cours de Compilation-Exercices Master d’Informatique M1 2011–2012 19 septembre 2011 Table des mati` eres 2 Analyse lexicale 1 2.1 Expressions r´ eguli` eres et analyse lexicale . . . . . . . . . . . . . . . . . . . . . . . 1 2.2 Reconnaissance d’une chaˆ ıne de caract` eres par une expression r´ eguli` ere . . . . . . 2 2.3 Construction d’automates d´ eterministes ` a partir d’expressions r´ eguli` eres . . . . . 2 2.4 Tables de transitions compress´ ees . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.5 Analyseur lexical pour indexer un programme . . . . . . . . . . . . . . . . . . . . 4 2.6 Rep´ erage des num´ eros de lignes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.7 Analyse lexicale d’un assembleur . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Analyse lexicale 2.1 Expressions r´ eguli` eres et analyse lexicale Le but est d’esquisser un analyseur lexical pour le mini-langage ci-dessous. Pour chaque entit´ e lexicale, on indique le token associ´ e, sa valeur ainsi que l’expression r´ eguli` ere qui le d´ eﬁnit. Token Valeur Expression r´ eguli` ere Mots cl´ es IF, THEN, ELSE, BEGIN, END le mot lui-mˆ eme Identiﬁcateurs ID le nom de l’identiﬁcateur lettre (lettre | chiﬀre)* Entier INT la valeur (-)?(chiﬀre)+ Op´ eration arithm´ etique OP l’op´ erateur + | - | * | / Op´ eration relationnelle REL l’op´ erateur < | <= | > | >= | = | <> Chaˆ ınes de caract` eres STRING la valeur de la chaˆ ıne ”n’importe quoi” R´ eels REAL la valeur (-)?entier.(entier)?(E (-)?entier)? avec entier=(chiﬀre)+ Commentaires ignor´ es (* n’importe quoi *) On adopte de plus les conventions suivantes : – Les caract` eres blancs, tabulation et retour chariot ne sont pas signiﬁcatifs et peuvent apparaˆ ıtre en nombre quelconque, – Les chaˆ ınes de caract` eres peuvent contenir des caract` eres sp´ eciaux qui commencent par le caract` ere \: \”, \n, \t, \\. – les commentaires se terminent au premier *) rencontr´ e et ne peuvent pas ˆ etre emboit´ es. 1. Donner les automates ﬁnis d´ eterministes pour chacune des expressions r´ eguli` eres puis pour l’analyseur lexical complet. 2. Donner un exemple de chaˆ ıne de caract` eres dans laquelle on peut reconnaˆ ıtre plusieurs pr´ eﬁxes correspondant ` a des tokens diﬀ´ erents. September 21, 2011 2 3. Quelles sont les diﬀ´ erences entre un analyseur lexical et la reconnaissance des mots par un automate ﬁni classique. 4. Donner la structure g´ en´ erale de l’analyseur lexical, ´ etant donn´ e les fonctions ´ el´ ementaires suivantes : – init d´ esigne l’´ etat initial de l’automate – chaine(x, y) o` u x et y sont des positions dans le buﬀer, renvoie la chaˆ ıne comprise entre les deux positions. – terminal(s) o` u s est un ´ etat, indique si l’´ etat est ﬁnal ou non. – token(s) si s est un ´ etat ﬁnal, renvoie le token associ´ e. – transit(s, c) renvoie l’´ etat suivant de s par la transition ´ etiquet´ ee par c, renvoie echec dans le cas o` u une telle transition n’existe pas. – lire(ptr) renvoie caract` ere lu ` a la position ptr dans le buﬀer. La fonction ´ echoue si elle rencontre une ﬁn de ﬁchier. 2.2 Reconnaissance d’une chaˆ ıne de caract` eres par une expression r´ eguli` ere (Partiel novembre 2000) Dans cet exercice, on se propose d’´ ecrire une fonction de test d’appartenance d’un mot au langage L(r) d´ eﬁni par une expression r´ eguli` ere r. Les expressions r´ eguli` eres seront repr´ esent´ ees par des objets du type Caml suivant: type expreg = | Vide (* Langage vide ∅*) | Epsilon (* Mot vide ϵ *) | Caractere of char (* Caract` ere c *) | Union of expreg * expreg (* r1|r2 *) | Produit of expreg * expreg (* r1r2 *) | Etoile of expreg (* r∗*) 1. D´ eﬁnir une fonction contient epsilon : expreg →bool qui d´ etermine si le mot vide ϵ appartient au langage d´ eﬁni par une expression r´ eguli` ere donn´ ee. 2. On d´ eﬁnit le r´ esidu d’une expression r´ eguli` ere r par rapport ` a un caract` ere c de la mani` ere suivante : Res(r, c) = { w | cw ∈L(r) } (a) Calculer Res(r, c) dans le cas o` u r = (a|b)∗a et c ∈{a, b}. (b) Le langage Res(r, c) peut lui-mˆ eme ˆ etre d´ ecrit par une expression r´ eguli` ere. ´ Ecrire une fonction residu : expreg →char →expreg calculant ` a partir de r et de c une expression r´ eguli` ere r′ telle que L(r′) = Res(r, c). (c) Calculer residu r c dans le cas o` u r = (a|b)∗a et c ∈{a, b}. 3. En d´ eduire une fonction reconnait : expreg →char list →bool qui d´ etermine si une liste de caract` eres appartient au langage d´ eﬁni par une expression r´ eguli` ere donn´ ee. 4. Appliquer cette fonction ` a la reconnaissance du mot aba par l’expression r´ eguli` ere r = (a|b) ∗a 2.3 Construction d’automates d´ eterministes ` a partir d’expressions r´ eguli` eres On remarque tout d’abord que si un automate ﬁni reconnaˆ ıt le langage correspondant ` a l’expression r´ eguli` ere r alors ` a chaque lettre lue sur l’entr´ ee on peut faire correspondre une occurrence d’une lettre dans l’expression r. On indexe chaque occurrence d’une lettre dans l’expression r´ eguli` ere par un entier de mani` ere ` a distinguer les diﬀ´ erentes occurrences d’une mˆ eme lettre. September 21, 2011 3 On prend comme exemple l’expression r´ eguli` ere (a|b)∗a(a|b). Apr` es avoir indic´ e les caract` eres, on obtient l’expression: (a1|b1)∗a2(a3|b2). Si l’entr´ ee est le mot aabaab, alors il correspond ` a l’expression r´ eguli` ere de la mani` ere suivante: a1a1b1a1a2b2 L’id´ ee est de construire un automate dont les ´ etats sont des ensembles de lettres index´ ees correspondant aux occurrences qui peuvent ˆ etre lues ` a un instant. Au d´ epart on regarde quelles sont les premi` eres lettres possibles. Dans notre exemple, il s’agit de a1, b1, a2 Pour construire les transitions, il suﬃt de pouvoir calculer pour chaque occurrence d’une lettre, les occurrences qui peuvent la suivre. Par exemple si on vient de lire a1 alors les caract` eres possibles suivants sont a1, b1, a2, si on vient de lire a2 alors les caract` eres possibles suivants sont a3, b2. Si on est dans l’´ etat initial (a1, b1, a2) et qu’on lit un a alors c’est soit a1 soit a2 et donc les caract` eres qui peuvent ˆ etre lus ensuite sont a1, b1, a2, a3, b2. On va montrer comment calculer syst´ ematiquement l’ensemble des caract` eres suivants. 1. D´ eﬁnir par r´ ecurrence sur la structure d’une expression r´ eguli` ere une fonction bool´ eenne null qui dit si le langage reconnu contient ϵ. 2. D´ eﬁnir par r´ ecurrence sur la structure d’une expression r´ eguli` ere une fonction d´ ebut (resp. ﬁn) qui renvoie l’ensemble des premiers (resp. derniers) caract` eres des mots reconnus. 3. Les caract` eres suivants c dans une expression r´ eguli` ere r sont caract´ eris´ es par la propri´ et´ e suivante: d ∈suivant(c, r) ssi il existe r1, r2 des expressions r´ eguli` eres telles que r1r2 soit une sous-expression de r et d ∈d´ ebut(r2) et c ∈ﬁn(r1) ou bien il existe r1 une expression r´ eguli` ere telle que r∗ 1 soit une sous- expression de r et d ∈d´ ebut(r1) et c ∈ﬁn(r1) ` a partir de cette caract´ erisation d´ eﬁnir par r´ ecurrence une fonction suivant(ci, r). 4. Pour construire l’automate d´ eterministe, on proc` ede de la mani` ere suivante sur l’expression r´ eguli` ere ind´ ex´ ee r: (a) Ajouter un nouveau caract` ere ♯` a la ﬁn de l’expression (b) Calculer la fonction suivant pour chaque caract` ere ind´ ex´ e. (c) Construire l’automate dont les ´ etats sont des ensembles de caract` eres ind´ ex´ es, l’´ etat initial est d´ ebut(r) les ´ etats d’acceptation sont tous ceux qui contiennent ♯. On a une transition de q vers q′ ` a la lecture du caract` ere c si q′ = [ ci∈q suivant(ci, r) Utiliser cet algorithme pour construire des automates d´ eterministes reconnaissant les ex- pressions : uploads/s3/ exos-1.pdf