Analyse formelle de code source¶

Analyse lexicale¶

Cette étape consiste à découper le flux de caractères en unités lexicales ou lexèmes (en anglais, tokens) sans se préoccuper de leur signification. En anglais un analyseur lexical est appelé un lexer.

Certains tokens sont constants, comme les opérateurs ou les mots-clés du langage, d’autres sont variables, comme les nombres ou les chaînes de caractères. On utilise souvent des expressions régulières pour décrire les tokens valides d’un langage.

Prenons comme exemple un langage mathématique simplifié dans lequel on peut écrire des multiplications de nombres entiers. Voici les définitions de tokens nécessaires à l’analyse lexicale d’un tel langage :

/**
 * Opérateur de multiplication.
 *
 * Ce token est constant.
 */
STAR : '*'  ;

/**
 * Nombre entier.
 *
 * Ce token est variable, il peut être composé de un ou
 * plusieurs chiffres
 */
NUMBER : ('0'..'9')+ ;

/**
 * Espaces, tabulations et retours à la ligne.
 *
 * Ces tokens sont ignorés par le lexer car ils n'ont pas
 * de signification particulière.
 */
WS : (' '|'\t'|'\r'|'\n')+ {$channel = HIDDEN;}  ;

Dans l’Illustration 16 on peut voir le procédé de découpage en tokens d’une expression multiplicative simple. Les tokens de type WS sont placés dans un flux séparé afin qu’ils soient ignorés par l’analyseur syntaxique.

Découpage d’un flux de caractère en unités lexicales

Analyse syntaxique¶

En anglais un analyseur syntaxique est appelé un parser. L’étape de parsing consiste à reconnaître des « phrases » valides dans le flux de tokens produit par le lexer. Pour cela, on se base généralement sur une grammaire non-contextuelle [1]. Celle-ci définit récursivement l’ensemble des tokens valides du langage et l’ordre dans lequel ils doivent apparaître pour former des phrases correctes. Au fur et à mesure de la reconnaissance de structures valides du langage, le parser produit une représentation arborescente du code source analysé.

Reprenons le langage mathématique simplifié abordé au paragraphe précédent. Dans celui-ci, la règle de grammaire décrivant une expression multiplicative s’écrit de la manière suivante [2] :

/**
 * Définition récursive d'une expression multiplicative.
 */
multiplicative_expression
  : NUMBER (STAR multiplicative_expression)*
  ;

Si on évalue le résultat produit par l’exemple précédent en organisant les tokens de manière arborescente, voici un résultat possible :

Résultat du parsing d’un flux de tokens

Dans l’Illustration 17, on constate que les tokens de type STAR ont été placés comme nœuds de l’arbre et ceux de type NUMBER comme feuilles. Cela permet de représenter l’expression sous une forme voisine de la notation polonaise [3].

Le résultat d’une analyse syntaxique produit toujours un « arbre de syntaxe abstraite » (appelé généralement par son nom anglais : Abstract Syntax Tree ou AST). Cet arbre porte la représentation en deux dimensions du code analysé (là où les flux de caractères et de tokens sont des représentations à une seule dimension).

Analyse sémantique¶

Une fois l’AST construit par le parser, il faut maintenant lui donner du « sens ». C’est l’étape la plus délicate d’un processus d’analyse de langages. Ici on ne produit plus de représentation intermédiaire mais bien une conversion finale vers le format désiré. Ce format désiré peut avoir plusieurs formes :

• Un résultat dans le cas de l’évaluation d’une expression mathématique.
• Une traduction vers un autre langage (par exemple, C vers Java).
• Des instructions en code machine dans le cas d’un compilateur.

Ces formes sont rarement obtenues directement depuis l’AST tel que produit par le parser. Il est alors nécessaire de réécrire des parties de l’AST1 afin d’arriver à une forme assez triviale qui pourra être directement traduite dans le format désiré. Parfois, certaines parties du code analysé seront volontairement exclues, puisque non exploitées par les analyseurs sémantiques pour des raisons de performance. Par exemple, dans les analyseurs de APIWatch, on aura tendance à exclure les sous-arbres des corps de fonctions car ils ne portent que rarement – voire jamais – des informations d’API.

Comme l’AST est une structure arborescente, on utilisera généralement un algorithme du type « visiteur » pour le parcourir. Cette méthode est appelée tree walking en anglais. Elle consiste à analyser chaque nœud de l’arbre récursivement. Il y a deux façons de « visiter » un arbre : avec un parcours en profondeur ou un parcours en largeur. Selon les besoins, l’une ou l’autre de ces méthodes sera utilisée.

Pour en finir avec l’exemple précédent, partons du principe que le parser produit un AST utilisant des objets de ce type (code d’une classe Java) :

class MultiExprAST {
    public String token;
    public MultiExprAST left;
    public MultiExprAST right;
/* classe volontairement incomplète pour des raisons de lisibilité */
}

Voici le code nécessaire pour évaluer le résultat de l’expression mathématique analysée (également en Java) :

int evaluate(MultiExprAST ast) {
    if (ast.token.equals("*"))
        return evaluate(ast.left) * evaluate(ast.right);
    else
        return Integer.valueOf(ast.token);
}

On constate que la fonction evaluate est récursive et qu’elle utilise un parcours en profondeur pour évaluer le résultat de l’expression multiplicative portée par l’AST.

Analyse de langages avec ANTLR¶

La programmation d’analyseurs est une tâche extrêmement fastidieuse, répétitive et sujette aux erreurs. ANTLR est un outil qui permet de définir un langage formel par une grammaire écrite dans une syntaxe dérivée de la Backus-Naur Form [4]. Depuis cette grammaire, ANTLR est capable de générer des analyseurs lexicaux, syntaxiques et même sémantiques, et ce dans de nombreux langages de programmation : Java, C, C++, Python, etc. Dans son livre The Definitive ANTLR Reference, Terrence Parr explique comment écrire et exploiter les grammaires.

La communauté ANTLR met à disposition des grammaires pour de nombreux langages de programmation. Le support des langages Java et C a été implémenté dans la distribution standard de APIWatch à l’aide de ces grammaires.

#include <stdio.h>
int say_hello(char *name, FILE *stream) {
   return fprintf(file, "Hello %s!\n", name);
}

gcc -E hello.c > hello.i

[...]
# 45 "/usr/include/stdio.h" 3 4
struct _IO_FILE;
[...]
# 65 "/usr/include/stdio.h" 3 4
typedef struct _IO_FILE FILE;
[...]
# 322 "/usr/include/stdio.h" 3 4
extern int fprintf (FILE *__restrict __stream,
                    __const char *__restrict __format, ...);
[...]
# 2 "hello.c" 2
int say_hello(char *name, FILE *stream) {
   return fprintf(file, "Hello %s!\n", name);
}

# <n° de ligne> "chemin du fichier source" <indicateurs divers>