Lexical analysis
****************

Regular languages allow to describe the tokens we will use.  The ``interesting'' languages (such as arithmetics) are not regular, so we already know we will need more powerful techniques.  Typically it means Lex will never be enough, we will need Yacc.

But then, since regular languages are context free languages (i.e., virtually, Yacc can do everything Flex does), why not using just Yacc. Simplify because of speed: FSM have more efficient implementations than FIXME: Finish this sentence!

Flex Expressions
================

There is one difference between the theory of finite state machine (recognizers), and those actually used in practice: the latter must recognize the longest match.

Here is the expressions supported by Flex.  Note that this is more than plain regular expressions.

x
     match the character x

.
     any character (byte) except newline

[xyz]
     a "character class"; in this case, the pattern matches either an x, a y, or a z

[abj-oZ]
     a "character class" with a range in it; matches an a, a b, any letter from j through o, or a Z

[^A-Z]
     a "negated character class", i.e., any character but those in the class.  In this case, any character EXCEPT an uppercase letter.

[^A-Z\n]
     any character EXCEPT an uppercase letter or a newline

R*
     zero or more R's, where R is any regular expression

R+
     one or more R's

R?
     zero or one R's (that is, "an optional R")

R{2,5}
     anywhere from two to five R's

R{2,}
     two or more R's

R{4}
     exactly 4 R's

{NAME}
     the expansion of the "NAME" definition

"[xyz]\"foo"
     the literal string: [xyz]"foo

\X
     if X is an a, b, f, n, r, t, or v, then the ANSI-C interpretation of \X. Otherwise, a literal X (used to escape operators such as *)

\0
     a NUL character (ASCII code 0)

\123
     the character with octal value 123

\x2a
     the character with hexadecimal value 2a

(R)
     match an R; parentheses are used to override precedence

RS
     the regular expression R followed by the regular expression S; called "concatenation"

R|S
     either an R or an S

^R
     an R, but only at the beginning of a line (i.e., which just starting to scan, or right after a newline has been scanned).

R$
     an R, but only at the end of a line (i.e., just before a newline).

<S>R
     an R, but only in start condition S

<<EOF>>
     an end-of-file

Flex files
==========

     Lex Directives
     %{
     Prologue
     %}
     Lex Directives
     %%
     Rules
     %%
     Epilogue

Le prologue et l'épilogue sont des sections de C.

La section des directives permet de

  - régler le comportement de lex (comme les options),

  - définir les états et les états exclusifs,

  - introduire des abréviations.

If the distinction between inclusive and exclusive start conditions is still a little vague, here's a simple example illustrating the connection between the two.  The set of rules:

     %s example
     %%

     <example>foo   do_something();

     bar            something_else();

is equivalent to

     %x example
     %%

     <example>foo   do_something();

     <INITIAL,example>bar    something_else();

Without the <INITIAL,example> qualifier, the bar pattern in the second example wouldn't be active (i.e., couldn't match) when in start condition example.  If we just used <example> to qualify bar, though, then it would only be active in example and not in INITIAL, while in the first example it's active in both, because in the first example the example starting condition is an *inclusive* (%s) start condition.

Rules
=====

La forme générales des règles est :

     MOTIF             ACTION

L'exemple suivant implémente wc :

     %{
     int num_lines = 0, num_chars = 0;
     %}
     %noyywrap
     %%
     \n      ++num_lines; ++num_chars;
     .       ++num_chars;

     %%
     int
     main (void)
     {
       yylex ();
       printf ("# of lines = %d, # of chars = %d\n",
               num_lines, num_chars );
     }

Du point de vue de la priorité, lorsque plusieurs règles sont concurrentes, la liste est lue de haut en bas.  Ceci est extrêmement utilisé lorsque l'on a des mots clés et des identificateurs.  L'action par défaut sur les caractères inconnus est de les propager vers stdout, donc toujours terminer par une règle attrape-miettes.

     %{
     enum token_e { VAR = 257, TYPE, INT, ID };
     %}
     %%
     "var"           return VAR;
     "type"          return TYPE;
     [0-9]+          return INT;
     [a-zA-Z][a-zA-Z_0-9]*  return ID;
     .               yyerror ("illegal token");

Les abréviations permettent d'alléger l'écriture des règles :

     int     [0-9]+
     id      [a-zA-Z][a-zA-Z_0-9]*
     %%
     "var"           return VAR;
     "type"          return TYPE;
     {int}           return INT;
     {id}            return ID;
     .               {
                        yyerror ("illegal token");
                        exit (1);
                     }

States
======

On peut écrire des règles complexes pour les longs lexèmes tels que les chaînes de caractères et les commentaires.  Ne pas oublier dans ces cas-ci que par défault . ne reconnaît pas les retours à la ligne. Mais cette approche a plusieurs problèmes :

  - Caractères d'échappement dans les chaînes de caractères.

  - Dépassement de capacité du tampon de l'analyseur lexical (souvent 4K).

  - Risque encore plus inutile dans le cas des commentaires, qui sont généralement purement et simplement jeté au niveau lexical.

La réponse à ces problèmes est l'utilisation d'états.  Les états peuvent se comprendre comme des sous-analyseurs lexicaux.  Quand on découvre l'ouverture d'une chaîne ou d'un commentaire, on bascule vers le sous analyseur correspondant.

Les états se déclarent par la directive %x NOM-DE-L'ÉTAT. L'état par défaut est INITIAL.  On utilise BEGIN pour sauter d'un état à un autre.  On utilise ensuite <NOM-DE-L'ÉTAT> pour spécifier le bloc qui correspond au sous-analyseur.

     %x STATE_COMMENT STATE_STRING
     %%
     "/*"     	BEGIN STATE_COMMENT;

     <STATE_COMMENT>{ /* Comments. */
       "*/"  BEGIN INITIAL;
       .|\n  ;

       <<EOF>> {
         yyerror ("Unexpected end of file in a comment");
         exit (1);
       }
     }

Semantic Values
===============

L'analyseur lexicale doit reconnaître les catégories grammaticales des mots (ceci est le mot-clé begin, ceci est un espace, ceci est un identificateur).  Dans certains cas, la catégorie n'est pas une information suffisante : dans le cas de chaînes de caractères, d'identificateurs, les littéraux etc. la valeur est également nécessaire.

Pour calculer la valeur d'un lexème sont disponibles yytext, un char * sur le début du lexème reconnu, et yyleng, sa longueur.  La transmission de la valeur depuis l'analyseur lexical vers son client se passe par variables globales.

     [0-9]+     the_value = atoi (yytext); return INT;

En règle générale le client de l'analyseur lexical est un analyseur syntaxique produit par yacc ou équivalent.  La convention est alors d'utiliser la variable globale yylval.  Comme on peut avoir plusieurs types de valeur, yylval est une union :

     %{
     union
     {
       int integer;
       char *string;
     } yylval;
     %}
     {int}    yylval.integer = atoi (yytext); return INT;
     {id}     yylval.string = strndup (yytext, yyleng); return ID

Locations in the Scanner
========================

Flex vs. Lex
============

<<EOF>>

Exclusive states

``Bugs'' in the understanding of abbreviations.

Free.

Portable.

Stands as its own standard.

Generation of C++.