Remerciez-le!

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

Analyse lexicale 10 septembre 2010 1 Analyse lexicale Un peu de théorie L ’outi

Analyse lexicale 10 septembre 2010 1 Analyse lexicale Un peu de théorie L ’outil ocamllex Commentaires Localisation des erreurs Programmer avec des analyseurs lexicaux C. Paulin (Université Paris Sud) Compilation 2010-2011 1 / 32 Rappel Objectif de l’analyse lexicale et syntaxique Entrée : suite de caractères Sortie : arbre de syntaxe abstraite représentant le programme sous-jacent Structure intermédiaire : suite d’entités lexicales (tokens) Outils théoriques : expressions régulières, grammaires Outils logiciels : Lex et Yacc C. Paulin (Université Paris Sud) Compilation 2010-2011 2 / 32 Principes de l’analyse lexicale Chaque entité lexicale est décrite par une expression régulière. A chaque entité lexicale est associée une action. L ’action produit en général un token, mais peut aussi avoir d’autres effets (compter des lignes, ignorer ou transformer le texte). C. Paulin (Université Paris Sud) Compilation 2010-2011 3 / 32 Sommaire 1 Analyse lexicale Un peu de théorie L ’outil ocamllex Commentaires Localisation des erreurs Programmer avec des analyseurs lexicaux C. Paulin (Université Paris Sud) Compilation 2010-2011 4 / 32 Expressions régulières Les constructions de base: regexp ::= ’caractère’ | regexp regexp | regexp | regexp | regexp * Dans la théorie, on ajoute aussi des expressions régulières pour: le mot vide notée ϵ l’ensemble vide notée ∅ mais qui ne sont pas utilisées dans les analyseurs lexicaux. Chaque expression e représente un langage (ensemble de mots L(e)) qui est dit régulier. L(c) = {c} L(e1 e2) = {m1m2|m1 ∈L(e1), m2 ∈L(e2)} L(e1|e2) = L(e1) ∪L(e2) L(e∗) = S 0≤n L(en) e0 = ϵ en+1 = e(en) C. Paulin (Université Paris Sud) Compilation 2010-2011 5 / 32 Expressions régulières étendues La syntaxe autorisée par ocamllex: regexp ::= "chaîne" | regexp ? | regexp + | [ caractères ] | [ˆ caractères ] | eof | _ | ( regexp ) | regexp as ident caractères ::= (’caractère’ | ’caractère’-’caractère’)+ Précédence plus haute + et *, ensuite ?, puis la concaténation puis le choix |. Exemple: ’a’|’b’* ’c’+ se lit: ’a’|((’b’*) (’c’+)) C. Paulin (Université Paris Sud) Compilation 2010-2011 6 / 32 Résultats Si e est une expression régulière alors il existe un automate ﬁni (que l’on calcule à partir de e) qui reconnait le langage L(e). La réciproque est vraie. Le langage des expressions bien parenthésées {anbn|n ∈N} n’est pas régulier. Exercice donner une expression régulière pour les identiﬁcateurs (suite de caractères alphabétiques) qui ne sont pas le mot clé set. Construire l’automate correspondant. Solution C. Paulin (Université Paris Sud) Compilation 2010-2011 7 / 32 Sommaire 1 Analyse lexicale Un peu de théorie L ’outil ocamllex Commentaires Localisation des erreurs Programmer avec des analyseurs lexicaux C. Paulin (Université Paris Sud) Compilation 2010-2011 8 / 32 ocamllex Syntaxe d’un ﬁchier ocamllex { header } let ident = regexp ... rule entrypoint [arg1... argn] = parse regexp { action } | ... | regexp { action } and entrypoint [arg1... argn] = parse ... and ... { trailer } C. Paulin (Université Paris Sud) Compilation 2010-2011 9 / 32 Résultat de ocamllex La commande ocamllex file.mll 1 produit un ﬁchier ﬁle.ml qui doit ensuite être compilé par ocaml; 2 afﬁche la taille de l’automate et de la table stockant les transitions. Chaque entrypoint déﬁnit une fonction ocaml. Ces fonctions peuvent être paramétrées et ont toujours un argument supplémentaire lexbuf. Ces fonctions peuvent être appelées récursivement dans les actions. C. Paulin (Université Paris Sud) Compilation 2010-2011 10 / 32 Principe de fonctionnement de ocamllex Le ﬁchier ocaml engendré: Le code ocaml du prélude let lex_tables = { ... } let rec entrypoint lexbuf = lex_entrypoint_rec lexbuf 0 and lex_entrypoint_rec lexbuf lex_state = match Lexing.engine lex_tables lex_state lexbuf with | 0 -> ( code de l’action de l’expr reconnue à l’état 0 ) | 1 -> ( code de l’action de l’expr reconnue à l’état 1 ) ... | lex_state -> lexbuf.Lexing.refill_buff lexbuf; lex_entrypoint_rec lexbuf lex_state Le code ocaml du postlude C. Paulin (Université Paris Sud) Compilation 2010-2011 11 / 32 Principe de fonctionnement de ocamllex (2) La table de transitions associe à un état et un caractère l’état suivant dans l’automate. Le stockage de la table de transitions utilise des techniques de représentation de matrices creuses de manière linéaire dans des chaînes de caractères. Des erreurs dans le code ocaml du prélude, des actions ou du postlude ne seront repérées que lors de la compilation de ﬁle.ml par ocaml. Des directives dans le ﬁchier ﬁle.ml #18 "test.mll" permettent de relier les lignes de ﬁle.ml à celles du ﬁchier ocamllex correspondant. C. Paulin (Université Paris Sud) Compilation 2010-2011 12 / 32 Un peu d’algorithmique (matrice creuse) On veut représenter une matrice M(i, j) de taille n × m. On suppose que de nombreuses cases de M ont une valeur constante z et on cherche à représenter M en évitant de stocker z. On utilise un tableau T et on cherche à placer les lignes de M sans les valeurs z dans le tableau T. Pour savoir à quelle ligne appartient un élément de T, on lui associe un second tableau C de même taille. C. Paulin (Université Paris Sud) Compilation 2010-2011 13 / 32 Un peu d’algorithmique (2) Pour placer la ième ligne dans T: on cherche une position p la plus petite possible telle que si M(i, j) ̸= d alors T(p + j) est vide. On stocke p dans un tableau d[i] de taille n. Pour tout j tel que M(i, j) ̸= d on met à jour T[p + j] := M(i, j) et C[p + j] := i La fonction d’accès à M(i, j) à partir de T, d et C sera vue en TD. Cette fonction a un coût constant. C. Paulin (Université Paris Sud) Compilation 2010-2011 14 / 32 Exemple M: 0 1 2 3 4 5 0 z z a z b z 1 a b z z z c 2 z b z z a z 3 a z z z a z 4 b z z z b z d: 0 -2 1 3 2 5 3 1 4 6 0 1 2 3 4 5 6 7 8 9 10 11 12 T: a a b a b a b b c a b C: 0 3 0 1 1 3 2 4 1 2 4 C. Paulin (Université Paris Sud) Compilation 2010-2011 15 / 32 Sommaire 1 Analyse lexicale Un peu de théorie L ’outil ocamllex Commentaires Localisation des erreurs Programmer avec des analyseurs lexicaux C. Paulin (Université Paris Sud) Compilation 2010-2011 16 / 32 Commentaires Exercice Trouver l’expression régulière correspondant à des commentaires qui débutent par /* et se terminent à la première occurrence de */ Construire l’automate correspondant Solution Peut-on mettre en commentaire un code qui contient des commentaires ? Quel est l’avantage des commentaires qui débutent par un caractère spécial par exemple # et se terminent par la ﬁn de ligne ? C. Paulin (Université Paris Sud) Compilation 2010-2011 17 / 32 Commentaires imbriqués Les analyseurs lexicaux permettent de traiter des commentaires imbriqués. On utilise une deuxième fonction d’analyse chargée de lire jusqu’à la ﬁn du commentaire. Possibilité d’avoir un compteur pour marquer le nombre de commentaires restant à fermer. rule nexttoken = parse "/*" {com:=1; comment lexbuf; nexttoken lexbuf} and comment = parse "*/" {if !com > 1 then begin decr com; comment lexbuf end} | "/*" {incr com; comment lexbuf} | eof {raise Error "commentaire non terminé"} | _ {comment lexbuf} C. Paulin (Université Paris Sud) Compilation 2010-2011 18 / 32 Commentaires imbriqués (2) Utilisation de la pile d’appels rule nexttoken = parse "/*" {comment lexbuf; nexttoken lexbuf} and comment = parse "*/" {} | "/*" {comment lexbuf; comment lexbuf} | eof {raise Error "commentaire non terminé"} | _ {comment lexbuf} C. Paulin (Université Paris Sud) Compilation 2010-2011 19 / 32 Le cas des chaînes de caractères Les expressions régulières pour les chaînes de caractère sont assez complexes. Par exemple on écrira "Nom:\"PP\"\\\n" pour représenter la chaîne Nom:"PP"\ terminée par un retour chariot. Elles peuvent aussi être arbitrairement longues. Il est recommandé de lire les chaînes avec une entrée de l’analyseur qui met les caractères au fur et à mesure dans un buffer. C. Paulin (Université Paris Sud) Compilation 2010-2011 20 / 32 Sommaire 1 Analyse lexicale Un peu de théorie L ’outil ocamllex Commentaires Localisation des erreurs Programmer avec des analyseurs lexicaux C. Paulin (Université Paris Sud) Compilation 2010-2011 21 / 32 Localisation des erreurs ocamllex conserve dans la variable lexbuf le nombre de caractères lus par rapport au début du ﬁchier Lexing.lexeme_start lexbuf de type int le nombre de caractères jusqu’au début de l’entité reconnue. Lexing.lexeme_end lexbuf le nombre de caractères jusqu’à la ﬁn de l’entité reconnue. Un type position déﬁni dans Lexing. type position = pos_fname : string; (* nom fichier *) pos_lnum : int; (* no de ligne *) pos_bol : int; (* nbre de car entre début de fichier et début de ligne *) pos_cnum : int; (* nbre de car entre début de fichier et position courante *) Accès à la position: lexbuf.Lexing.lex_curr_p de type uploads/Management/ slides2-lex.pdf