Analyse Lexicale

Une suite de caractères est lu par un analyseur lexical, et celui-ci produit une suite de symboles (unités syntaxiques, “tokens”). Ces symboles comprennent des identifiants, des mots réservés, des constantes, des délimiteurs 1), des opérateurs simples ou composés (+ - * / := , e.g., qui sont de petits mots réservés).

Pour faire cette analyse, l'analyseur lexical a besoin de trois choses :

  • expressions rationnelles, des règles permettant de reconnaitre des tokens;
  • automates d'états finis, pour faire la recherche de correspondances entre les expressions rationnelles et la suite de caractères lus;
  • actions (code) pour faire plus que passer un token dans certains cas (répondre “identifiant” et la chaine de caractères, ou “NOMBRE” et la valeur, e.g.).

L'analyseur syntaxique (yacc ou bison, e.g.) demande à l'analyseur lexical (lex ou flex, e.g.) de reconnaitre et passer le prochain token. Lorsqu'il s'agit d'un identifiant, le lexeur l'inscrit (si ce n'est déjà fait) dans la table des symboles avant de le transmettre. L'analyseur syntaxique complètera les informations concernant l'identifiant dans la table des symboles lorsqu'il pourra : dimensions pour un tableau, type et paramètres pour une fonction, etc.

Il y a, comme on a vu en parlant des actions, deux sortes de token :

  • ceux qu'il suffit de reconnaitre, car tout d'eux est prédéfinis (mots réservés, opérateurs)
  • ceux qui sont plus “libres” et doivent être passés sous la forme {type, valeur}; { idf, “Hello”} et {cst_int, 42}, par exemple.

Automates

Reconnaître un identifiant

  • état initial : une lettre → état 2
  • état 2 :
    • tant que {lettre ou chiffre} on reste dans état 1;
    • autre chose : identifiant terminé, état 3
  • état 3 : action, mise dans la table des symboles

Reconnaître un réel

Ce n'est pas si simple (cf. “Flex & Bison”), mais dans notre exemple on s'est contenté de supposer qu'il commence par un chiffre (et pas directement par un point),

  • suivi d'autres chiffres exclusivement pour un entier,
  • suivi d'autres chiffres (ou pas), un point, et encore des chiffres pour un réel
  • l'un ou l'autre se termine par tout caractère qui n'est pas un chiffre

Expressions rationnelles

Comment reconnaitre un commentaire style C : ”/* ... */” ?

( ) groupe
* 0 à n occurrences
+ 1 à n occurrences
\cup union

Posons

  • N \in \left(\Sigma \setminus \left\{ * \right\}\right)
  • M \in \left(\Sigma \setminus \left\{ * \; / \right\}\right)
état lecture état suivant
1 '/' 2
1 \sigma \in N = \Sigma \setminus \left\{'/'\right\} 1
2 '/' 2
2 \sigma \in M 1
2 '*' 3
3 '*' 4
3 \sigma \in N 2
4 '*' 4
4 '/' Fin
4 \sigma \in M 3

Donc, avec /*N^{*} nous arriverons dans l'état 3. Est-ce que \left( *^{*} \cup M N^{*} * \right)^{*} nous emmène de l'état 3 à l'état 4, d'où un simple '/' nous permettra de terminer? Non, mais presque, car il faut le faire au moins une fois. Oon voit que

  1. *^* nous emmène de 3 à 4
  2. M\;N^* \;* nous ramène de 4 à 4
  3. \left( *^{*} \cup M N^{*} * \right)^{*} nous laissera en 4 pourvu que nous y soyons arrivés
  4. \left( *^{*} \cup M N^{*} * \right)^{+} est donc ce qu'il nous faut.

Pour perspective, dans le livre “Flex & Bison” ces commentaires sont traités par un état spécifique déclenché par ”/*” . Dans cet état, on recherche ”*/” et l'on ignore presque tout: ”([^*] | \n) + | . ” – tout sauf “*”, 1..n fois.

Il est aussi donné une expression pour traiter ce cas, mais il déconseille son emploi :

 /\*([^*]|\*+[^/*])*\*+/

ce qui revient (dans notre notation) à

/* \left( N \cup *^{+} M \right)^{*} *^{+} /

1) tels que : '(', ')', '{', '}', '[', ']', ',', ';', ' '
 
m1ilc/compil_td_1.txt · Dernière modification: 2009/12/23 15:05 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki