Générateurs d'analyseurs lexicaux et syntaxiques

L'écriture d'analyseurs lexicaux et syntaxiques est une tâche répétitive que l'on a automatisé depuis longtemps dans de nombreux langages de programmation.

Un analyseur lexical s'occupe d'identifier la nature lexicale des objets dans un texte. Il transforme un flux de caractères en un flux de tokens étiquetés.

Un analyseur lexical est facilement créé sur la base d'un ensemble d'expressions régulières décrivant des langages disjoints. Chaque expression régulière identifie de manière unique une classe de token. Ces expressions régulières étant implémentées par des automates à états finis déterministes, l'analyse lexicale en résultant est très performante. Attention : les langages formels sont le plus souvent définis pour qu'une analyse lexicale de ce type soit possible. Ce n'est pas une nécessité et il peut arriver que le problème soit plus complexe, ceci à cause de la nature ambiguë du langage.

Un analyseur syntaxique s'occupe de créer une structure syntaxique (un arbre le plus souvent) à partir d'un flux de tokens.

Un analyseur syntaxique est créé sur la base d'une grammaire hors-contexte. Les règles de grammaire indiquent les énoncés bien formés (syntaxiquement valides). Il faudra encore éventuellement par la suite effectuer des vérifications sur l'arbre syntaxique pour vérifier la validité sémantique des énoncés : vérification du typage des expressions, etc. L'analyse syntaxique d'un langage décrit par une grammaire hors-contexte repose sur un automate à pile. Dans les meilleurs cas, un automate à pile déterministe pourra reconnaître le langage et l'analyseur sera très efficace. Dans d'autres cas, une ambiguité inhérente nécessitera un automate à pile non-déterministe et l'analyseur sera plus lent.

On peut donner un exemple très classique d'analyseur pour un langage d'expressions algébriques. Le langage de l'analyseur sera le langage C et nous utilisons les outils lex et yacc pour générer les analyseurs lexicaux et syntaxiques.

Fichier calc.l :

/*

Analyseur lexical


(C) F. Popineau 1992

L'auteur degage toute responsabilites concernant les consequences
de l'utilisation de ce squelette de grammaire.

*/


%{

#include <stdlib.h>
#include <stdio.h>

/* Valeurs des tokens retournées par le scanner. */

double yylval;
#define YYSTYPE double

#include "y.tab.h"

%}

%option noyywrap

delim     [ \t]
ws        {delim}+
digit     [0-9]
real      [+-]?[1-9]{digit}*\.{digit}*(E[+-]?{digit}+)?
integer   {digit}+

%%

<<EOF>>    { return END; }
{ws}       { /* nothing */ }

"("        { return PAR_OUVR; }
")"        { return PAR_FERM; }

"+"        { return PLUS; }
"-"        { return MINUS; }
"*"        { return MULTIPLY; }
"/"        { return DIVIDE; }
"\n"       { return DOT; }

{real}     { yylval = atof(yytext);
             return(REAL);
           }
{integer}  { /* yylval = nouvel atome numerique avec pour valeur le nombre 
		correspondant a yytext. */
             yylval = atof(yytext);
             return(INTEGER); }

%%

extern int yydebug;

void main(int argc, char **argv)
{
  int res;
  yydebug = argv[1] != NULL;

  while ( yyparse() == 0) ;
}

Fichier calc.y :

%{

#define YYDEBUG 1

#include <stdio.h>
#include <stdlib.h>

#define YYSTYPE double

int yylex (void);
void yyerror(char const *s) { fprintf(stderr, "%s\n", s); }

%}

%token PAR_OUVR PAR_FERM
%token PLUS MINUS MULTIPLY DIVIDE
%token INTEGER REAL END DOT

%left PLUS MINUS
%left MULTIPLY DIVIDE
%right UMINUS

%%

phrase : %empty { return 0; }
        | expr DOT  { printf("Résultat = %f\n", $1); return 0; }
	| DOT {return 0; }
	| END { return 1; }
        | error DOT { yyerrok; return 0; }
 ;

expr : term { $$ = $1; }
	| term PLUS expr { $$ = $1 + $3; }
	| term MINUS expr { $$ = $1 - $3; }
;

term : factor { $$ = $1; }
	| factor MULTIPLY term { $$ = $1 * $3; }
	| factor DIVIDE term { $$ = $1 / $3; }
;

factor : INTEGER { $$ = $1; }
	| REAL  { $$ = $1; }
	| PAR_OUVR expr PAR_FERM { $$ = $2; }
;

La séquence d'instructions permettant de générer l'analyseur ainsi qu'un court programme pour l'utiliser sont les suivantes :

$ lex calc.l
$ yacc calc.y
$ gcc -o calc lex.yy.c y.tab.c

Ensuite vous pouvez exécuter le programme calc généré pour une petite session :

$ winpty ./calc.exe
2.
Résultat = 2.000000
3.
Résultat = 3.000000
2. + 3.
Résultat = 5.000000
2+3
Résultat = 5.000000
2.+3.
syntax error
2+3*4
Résultat = 14.000000
^D

Vous pouvez consulter les fichiers code/lex.yy.c, code/y.tab.c et code/y.tab.h générés par les outils lex et yacc. Ces fichiers contiennent les tables décrivant l'automate à états finis (pour l'analyseur lexical) et à pile (pour l'analyseur syntaxique).

L'erreur de syntaxe est logique : l'analyseur lexical reconnaît 2. comme un token REAL et ensuite +3. également comme un token REAL. Aucune règle de grammaire ne correspond à REAL REAL.

Homoïconicité

La capacité d'un langage à modifier ses propres programmes, ou à générer du code dynamiquement à l'exécution peut se révéler très utile. C'est le cas par exemple lorsqu'on réalise un moteur d'expressions régulières. La méthode classique consiste à calculer l'automate correspondant à l'expression régulière, à le stocker dans une table et à parcourir cette table lorsqu'on cherche si une chaîne de caractères donnée est reconnue par l'expression régulière.

Si on illustre ce principe sur l'automate élémentaire ci-dessous :

\begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto,%
    position/.style args={#1 degrees from #2}{at=(#2.#1), anchor=#1+180, shift=(#1:2cm)}%
]
\node [state, initial left] (q_0) {$q_0$};
\node [state,right=of q_0] (q_1) {$q_1$};
\node [state, accepting, below=of q_1] (q_2) {$q_2$};
\node [state,below=of q_0] (q_3) {$q_3$};
\path[-latex,
    thick,
    shorten <=2pt,
    shorten >=2pt,]
    (q_0) edge node {a} (q_1)
  (q_1) edge[bend left=30] node {a} (q_2)
  (q_2) edge[bend left=30] node {a} (q_1)
  (q_2) edge node {b} (q_3)
  (q_0) edge node {b} (q_3)
  (q_1) edge[loop right] node {b} (q_1)
  (q_3) edge[loop left] node {a,b} (q_3);
\end{tikzpicture}

La première façon pour coder cet automate consiste à définir la table de transition de l'automate et à parcourir cette table. Le programme C ci-dessous implémente cette technique sur l'exemple donné.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

int dfa[][2] = {
               {1, 3},
               {2, 1},
               {1, 3},
               {3, 3}
};

int match_word(char *s)
{
  int state = 0;
  while (*s != '\0') {
    assert((*s - 97) >=0 && (*s - 97) <= 1); 
    state = dfa[state][*s - 97];
    s++;
  }
  return state == 1;
}

void main(int argc, char *argv)
{
  char buffer[100];
  while (gets(buffer)) {
      printf("%s %s.\n", buffer,
             (match_word(buffer) ? "is matched" : "is not matched"));
  }
}

C'est ce que font les bibliothèques classiques d'expressions régulières dans les langages C/C++/Java.

On trouve ce mécanisme sous la forme des deux fonctions C POSIX regcomp() et regexec(). On voit que regcomp() crée une structure du type dfa[][] et regexec() l'utilise.

Le problème est qu'avec un langage comme C/C++/Java, regcomp() ne peut générer qu'une donnée et non pas du code, puisque on ne dispose pas du compilateur au run-time. L'intérêt de générer du code pour l'automate réside dans une plus grande efficacité : on économise des lookups dans la table au profit de jumps dans le code.

On peut illustrer cette seconde façon de coder l'automate par le programme C ci-dessous. Ici, l'automate est codé «en dur» à l'aide de l'instruction switch.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

int match_word(char *s)
{
  int state = 0;
  while (*s != '\0') {
        assert((*s - 97) >=0 && (*s - 97) <= 1); 
    switch (state) {
    case 0:
      switch (*s) {
      case 'a':
        state = 1;
        break;
      case 'b':
        state = 3;
        break;
      };
      break;
    case 1:
      switch (*s) {
      case 'a':
        state = 2;
        break;
      case 'b':
        /* state = 1; */
        break;
      };
      break;
    case 2:
      switch (*s) {
      case 'a':
        state = 1;
        break;
      case 'b':
        state = 3;
        break;
      };
      break;
    case 3:
      switch (*s) {
      case 'a':
        /* state = 3; */
        break;
      case 'b':
        /* state = 3; */
        break;
      };
      break;
    };
    s++;
  }
  return state == 1;
}

void main(int argc, char *argv)
{
  char buffer[100];
  while (gets(buffer)) {
    printf("%s %s.\n", buffer,
           (match_word(buffer) ? "is matched" : "is not matched"));
  }
}

Certains langages disposent de leur compilateur au run-time. C'est le cas de Lisp et Prolog entre autres (c'est en partie le cas de Python, mais Python ne génère pas du code machine). On peut illustrer la technique sur le code Lisp présenté dans ce fichier : code/dfa.lisp

Lorsque cette technique a été introduite en Lisp par la bibliothèque CL-PPCRE, le moteur d'expressions régulières était 5 à 20 fois plus rapide que l'implémentation de référence en C du projet GNU !

Aujourd'hui, il existe des bibliothèques d'expressions régulières qui disposent d'un compilateur JIT comme celui-ci.

Note : les moteurs d'expressions régulières réels sont complexes, difficiles à comparer, car ils ne proposent pas tous le même ensemble de fonctionnalités.

Automates en Prolog

Les programmes ci-dessous réalisent une transformation d'une expression régulière en NFA, puis de NFA en DFA et enfin permettent de chercher les lignes d'un fichier qui contiennent une chaîne reconnue par l'automate. Ils sont écrits en Prolog. Ils sont incomplets : l'analyseur d'expression régulière reconnaît plus d'options que celles qui sont effectivement traduites (l'opérateur . par exemple n'est pas implémenté).

regex2nfa.pl : analyseur syntaxique d'expressions régulières et conversion en NFA nfa2dfa.pl : conversion de NFA en DFA match.pl : reconnaissance de regex dans une chaîne automate.pl : application à un fichier.

Exemple d'exécution :

  6 ?- raz_fa('q'),
       string_to_list('bc*d',L),
       traduit_regexp(L,A),
       regexp2nfa(A,'q'),
       print_fa('q'), raz_fa('p'),
       nfa2dfa('q','p'),print_fa('p'),
       see('foo.txt'),
       !,
       match_file('p'),
       seen.

Etat de depart : 1
Etats terminaux : [7]
q(1) par b donne q(2)
q(5) par epsilon donne q(3)
q(3) par c donne q(4)
q(4) par epsilon donne q(3)
q(6) par d donne q(7)
q(5) par epsilon donne q(6)
q(4) par epsilon donne q(6)
q(2) par epsilon donne q(5)
Liste des états[p(1),p(2),p(3),p(4)]
Etat de depart : 1
Etats terminaux : [4]
p(1) par b donne p(2)
p(2) par c donne p(3)
p(2) par d donne p(4)
p(3) par c donne p(3)
p(3) par d donne p(4)
'abcdefgh\n'bcd
'reabcdfg\n'bcd
L = [98, 99, 42, 100],
A = conc(b, conc(etoile(c), d)) .

7 ?-

Algorithme de parsing