===== 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 (( tels que : '(', ')', '{', '}', '[', ']', ',', ';', ' ')), 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 |
|  <jsm>\cup </jsm>  | union |

Posons
  * <jsm> N \in \left(\Sigma \setminus \left\{ * \right\}\right) </jsm>
  * <jsm> M \in \left(\Sigma \setminus \left\{ * \; / \right\}\right) </jsm>

^ état ^  lecture  ^  état suivant  ^
|  1  |  '/'  |  2  |
|  1  |  <jsm> \sigma \in N = \Sigma \setminus \left\{'/'\right\} </jsm>   |  1   |
|  2  |  '/'  |  2  |
|  2  |  <jsm>\sigma \in M </jsm>  |  1  |
|  2  |  '*'  |  3  |
|  3  |  '*'  |  4  |
|  3  |  <jsm>\sigma \in N </jsm>  |  2  |
|  4  |  '*'  |  4  |
|  4  |  '/'  |  Fin  |
|  4  |  <jsm>\sigma \in M </jsm> |  3  |

Donc, avec <jsm> /*N^{*} </jsm> nous arriverons dans l'état 3.  Est-ce que <jsm>\left( *^{*} \cup M N^{*} * \right)^{*}</jsm> 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
  - <jsm>*^*</jsm> nous emmène de 3 à 4
  - <jsm>M\;N^* \;* </jsm> nous ramène de 4 à 4
  - <jsm>\left( *^{*} \cup M N^{*} * \right)^{*}</jsm> nous laissera en 4 pourvu que nous y soyons arrivés
  - <jsm>\left( *^{*} \cup M N^{*} * \right)^{+}</jsm> 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) à

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