De véritables outils d'analyse syntaxique

La paresse bien comprise est une vertu proclamée du programmeur Perl. Donc, lorsque c'est approprié, évitez de faire vous-même l'analyse syntaxique. C'est toujours complexe et, souvent, il existe des modules qui sont dédiés à cette analyse syntaxique ou qui l'incluent. Le terme anglais pour analyseur syntaxique est parser.

HTML::Parser [1] est idéal pour analyser du HTML. Pour ce qui est du XML, il existe XML::Parser [2] et XML::SAX [3]. Mentionnons au passage des modules de plus haut niveau qui incluent l'analyse du XML : XML::Twig [4] de Michel Rodriguez (mongueur toulousain) et AxKit [5] de Matt Sergeant. AxKit travaille en tandem avec le serveur web apache.

Finalement, si l'on doit écrire un analyseur syntaxique complexe, Parse::Yapp [6] de François Désarménien (encore un mongueur !) est un excellent générateur de parser qui est un clone de yacc. Ces outils feront probablement l'objet de futurs articles. Finalement l'analyseur syntaxique Parse::RecDescent de Damian Conway sacrifie la rapidité pour la versatilité.

Mais, quelquefois, il est plus simple d'analyser une chaîne à la main. L'idiome Perl pour ce faire est le sujet central de ce collier de perles.

L'idiome m/\G.../gc

Cet idiome présente une manière d'utiliser l'opérateur m// de recherche dans une chaîne par une expression régulière. Dans la suite, je préférerai respectivement les anglicismes match et regex.

En contexte scalaire, l'opérateur de match permet de progresser dans une chaîne de caractères. \G est une ancre qui spécifie la position courante dans ladite chaîne. En effet, à chaque chaîne de caractères est attachée une position courante pour la recherche. Cette position est une forme d'itérateur pour l'opération de match avec la limitation qu'un seul itérateur est possible par chaîne.

L'usage du modificateur /g lors d'un match m// permet de mémoriser la position courante de la recherche dans la chaîne. En cas d'échec, la valeur de cette position est undef, ce qui n'est généralement pas ce qu'on veut. L'addition du modificateur /c inhibe cette remise à "zéro".

Compter le nombre de lignes dans une chaîne

Un uniligne pour compter le nombre de lignes dans une chaîne :

   $nr++ while  "un\ndeux\ntrois\n" =~ m/\G.*?\n/gc;

A chaque itération, on part de la fin du match précédent grâce à l'ancre \G, puis on saute un minimum de caractères grâce à .*? avant de chercher un saut de ligne. On incrémente alors $nr. On sort de la boucle quand on ne trouve plus de match.

Bien sûr, en Perl, on peut procéder de multiples autres manières pour arriver au même résultat :

  grep { $nr++ if $_ eq '\n'} split '', "un\ndeux\ntrois\n";

  $nr = grep { $_ eq '\n' } split '', "un\ndeux\ntrois\n";

  $s =  "un\ndeux\ntrois\n"   
  $nr = grep { substr($s, $_, 1) eq '\n'} for 0..length($s)-1

La fonction pos()

En dehors du match par une regex, la position courante dans une chaîne est accessible par la fonction pos(). Comme beaucoup de fonctions Perl, elle prend la variable $_ comme argument par défaut.

Illustrons par un exemple:

    $s = "Les mongueurs de Perl connaissent bien le langage Perl";

    # Affiche 21, la position après la première occurrence de "Perl"
    $s =~ m/Perl/gc ; print  pos($s),"\n" ;  

    # Affiche toujours 21 car pas de match mais pas de remise à zéro
    # à cause de la présence de l'option /c
    $s =~ m/Python/gc ; print  pos($s),"\n"; 

    # Affiche 54, la position après la seconde occurrence de "Perl"
    $s =~ m/Perl/gc ; print  pos($s),"\n" ;  # affiche "54\n"

    # Affiche 0. Pas de match et remise à zéro car absence de l'option /c.
    # pos($s) retourne undef qui, utilisé en contexte entier par
    # l'addition du 0, est converti en 0.

    $s =~ m/Python/g ;  print pos($s)+0, "\n";

Dans la suite nous nous passerons de =~, car nous effectuerons la recherche dans $_.

Illustrons l'idiome m/\G.../gc par l'écriture d'un analyseur naïf de fichier de configuration qui permet de remplir le hash %config avec des couples clé/valeur de configuration.

Ainsi un fichier .myconfig  contenant :

    a = toto
    b = titi
    c = tutu

reviendra à initialiser %config comme suit :

  $config{'a'} =  "toto";
  $config{'b'} =  "titi";
  $config{'c'} =  "tutu";

Découpage en tranches

Puisque l'objet de ce collier de perles est de présenter des idiomes, rappellons que nous aurions pu exprimer la même chose en terme de tranches de hash :

   @config{ 'a', 'b', 'c'  } =  ( 'toto', 'titi', 'tutu' )

que nous pouvons aussi écrire en utilisant qw() pour créer les listes :

   @config{ qw( a b c ) } =  qw( toto titi tutu );

Voici le script de lecture du fichier de configuration :

    my %config;              # hash qui contiendra la configuration
    open I, ".myconfig" or die $!;
    while(<I>) {
        s/[\s;]+//g;          # supprime blancs et éventuels points virgules
        $config{$1} = $2 if m/\G(\w+)=(\w+)/gc;
        last if m/\G$/gc;    # équivalent à : last if pos == length
    }

Modules d'analyse de fichiers de configuration

L'idiome substr() = "toto"

Il est peu connu que la fonction substr() peut être lhs. Ce sigle pour « left hand side » signifie qu'une expression peut apparaître dans la partie gauche d'une affectation.

On sait que substr($str, $debut, $longueur) retourne la sous-chaîne de $str de longueur $longueur commençant à la position $debut. Mais, en mettant cette expression en lhs, cette sous-chaîne est remplacée par la partie droite de l'affectation. Exemple :

    $s = "groupe de mongers parisiens";
    print substr($s, 10, 7);          # affiche "mongers"
    substr($s, 10, 7) = "mongueurs"; 
    print $s;                         # affiche "groupe de mongeurs parisiens";

Notons que la fonction pos() est aussi lhs de sorte que vous pouvez modifier la position courante dans une chaîne.

visualisation de la progression

Revenons à notre script. Notre analyse syntaxique se bloque si le fichier de configuration n'a pas le format attendu. Elle boucle alors indéfiniment. Corrigeons cela. En cas d'erreur, le script indiquera la position de l'erreur, puis sortira. On le fait en insérant comme marqueur la chaîne "<*>" à la position courante de la chaîne analysée. On sort en affichant cette chaîne modifiée si son analyse ne progresse plus. Adaptons notre script pour afficher la position courante pour ce faire.

Nous incluons aussi Data::Dumper pour pouvoir afficher la valeur de %config à la fin du script.

    use strict;
    use Data::Dumper
    my %config;                  # hash qui contiendra la configuration
    open I, ".myconfig" or die $!;
    while(<I>) {
        my $pos = pos;           # pos() mémorise la position courante
        
        s/[\s+;]+//g; 
        $config{$1} = $2 if m/\G(\w+)=(\w+)/gc;
        last if m/\G$/gc; 

        if ( $pos == pos ) {     # la position courante a-t-elle avancé ?
            substr( $_, pos, 0 ) = "<*>";
            die $_;              # meurt si on n'a pas avancé dans la chaîne
        }
    }
    print Dumper(\%config);

Les parenthèses ne font pas les listes

Notons que, dans notre script ci-dessus, nous appellons la fonction pos() sans utiliser de parenthèses. En perl, dans l'écriture de l'appel d'une fonction, les parenthèses ne sont là que pour grouper les éléments d'une liste, éventuellement vide, de paramètres. En d'autre termes, l'opérateur de création de liste est la virgule. Ce groupement par les parenthèses est souvent nécessaire car la précédence de l'opérateur d'affection est plus forte que celui de création de liste. Ainsi les parenthèses sont indispensables dans l'expression :

   substr( $_, pos, 0 ) = "<*>";

Car :

   substr $_, pos, 0  = "<*>";

est l'équivalent de :

   substr( $_, pos, (0  = "<*>") );

Cela n'a pas de sens car comme le compilateur le signalera alors, une constante ne peut pas être en position lhs.

Des idiomes de déboguage

Pour voir la progression de l'analyse, il serait typiquement utile de factoriser le code d'affichage de la chaîne avec notre marqueur en une routine print_marked() appelée à chaque invite du débogueur.

La documentation [7] sur le débogueur Perl est disponible en Français Rappelons que l'on lance perl en mode débogueur avec l'option -d. Lançons perl -d monscript pour déboguer le script monscript ou perl -de 0 pour expérimenter ou l'utiliser comme une sorte de ligne de commande. Pour les amateurs de emacs, utilisez M-x perldb pour obtenir le débogueur en mode fenétré.

Les commandes de base sont similaires à celles de tout débogueur et leur usage est supposé connu.

Nous rappellons simplement la syntaxe d'appel :

Prototypage de routine

On aurait pu ajouter un prototype lors de la définition de la routine pour spécifier que le passage de paramètre se fait par référence  sans backslash. Définition de la fonction avec prototype :

    sub print_marked1(\$) {  ... } # prototype \$

L'appel sans backslash :  print_marked $_.

Auquel cas l'appel de la fonction se ferait ainsi :  print_marked1 $_ . Les prototypes ont été créés pour pouvoir définir des routines qui se comportent comme les fonctions prédéfinies.

Ainsi une routine qui réimplementerait push se déclarerait ainsi :

  sub mon_push (\@@);

Cela signifie qu'elle attend un tableau qui sera passé par référence et un nombre indéfini de paramètres passés par valeur. Les prototypes sont une fonctionnalité incomplète et baroque. Je la mentionne pour le cas où vous la rencontriez dans du code. Évitez de l'utiliser.

Action avant l'invite du débogueur

A l'invite du débogueur, tapons < print_marker \$_. La commande < prend pour paramètre une expression Perl qui est exécutée avant chaque invite suivante du débogueur. Dans notre cas, à chaque invite du débogueur notre fonction sera exécutée et nous pourrons voir où nous en sommes dans l'analyse de la chaîne.

Factorisation de l'analyse de configuration en un module

Maintenant, supposons que nous ayons fait de notre analyseur un module Configurateur (donc dans le fichier Configurateur.pm). Cela nous permettra de l'utiliser dans d'autres programmes. Cela donne :

    package Configurateur;
    our %config;
     
    sub import {
        shift;
        local ($_) = shift;
        while (1) {
            m/\G[\s;]+/gc;
            $config{$1} = $2 if m/\G(\w+)=(\w+)/gc;
            if ( $pos == pos ) {
                substr( $_, pos, 0 ) = "<*>";
                die $_;
            }
            last if m/\G$/;
        }
    }
 
    1;

Il sera utilisé de la manière suivante dans notre programme principal :

    use YAML 'Dump';
    use Configurateur <<'EOF';
    toto = 4
    tutu = 5
    EOF
    print Dump \%Configurateur::config;

Ainsi nous pouvons analyser une chaîne de configuration grâce à use Configurateur "toto=4". Cela permet de charger d'un seul coup le module et de faire l'analyse de la chaîne. En effet, l'invocation de use appelle la fonction import() du module invoqué (ici Configurateur) avec pour paramètres le nom du module et éventuellement les paramètres additionnels (ici "toto=4"). Comme son nom le suggère, cette invocation est traditionnellement utilisée pour l'import de symboles dans le package courant, mais elle l'est souvent pour d'autres choses. Ainsi, use strict provoque la modification de drapeaux qui affectent le comportement de l'interpréteur Perl. Il change le mode de Perl pour interdire des pratiques d'écriture incompatibles avec la programmarion en grand. Pour varier les plaisirs, nous faisons le listage des données avec YAML.

Débogage d'un module

Dans notre cas, il y a problème pour déboguer. En effet, use est exécuté lors de la phase de compilation alors que le point d'arrêt de début de débogue est au début de l'exécution. En d'autre termes, le débogueur nous donne la main après avoir exécuté le code que nous voulons déboguer. Gênant.

Heureusement, b load configurateur permet de mettre un point d'arrêt lors de l'exécution du module et donc de pouvoir déboguer celui-ci. Taper h b permet de voir les autres usages de la commande de pose de points d'arrêt.

Le saviez-vous ?

Historique et informations sur des regex

Originellement un outil mathématique, les regex sont très liées à l'histoire d'Unix et l'on peut suivre leur trace jusqu'à son ancêtre MULTICS.

Pourtant, malgré (ou à cause) de cette longue histoire, les systèmes d'expressions régulières sont particulièrement cryptiques et toujours mal intégrés au langage.

Aujourd'hui, Perl est probablement le langage dans lequel les regex sont le mieux intégrées. L'introduction de qr|| a permis de faire des regex des entités de première classe. On dit qu'une entité est de première classe dans un langage lorsqu'elle peut être manipulée comme une valeur qui peut être affectée à des variables. Les regex comme entités de première classe en Perl5 n'ont malheureusement que très peu d'intérêt, car si elle permettent d'assembler les expressions régulières par morceaux elle ne permettent pas la gestion des captures. C'est un des multiples problèmes liés aux regex qui sera résolu par Perl6.

De nombreux langages et outils se sont inspirés de Perl, souvent grâce à l'usage de la bibliothèque PCRE [9] (Perl-Compatible Regular Expressions). Larry Wall remarque : « Perl a souvent été vu comme un langage dans lequel il est facile d'écrire des programmes difficiles à lire. Il est drôle que d'autres langages ont emprunté aussi vite que possible les expressions régulières Perl ».

Conscient de ces déficiences, Larry traite du système d'expressions régulières [10] du futur Perl6 dans son Apocalypse 5. Les apocalypses sont les documents de conception de Perl6. Apocalypse est à prendre ici dans son sens originel de révélation. Par la totale intégration des expressions régulières au langage, il sera possible de faire de l'analyse syntaxique directement en Perl6 sans outils particuliers.

Quelques sources d'information sur les regex dans le cadre de Perl. L'excellent article [11] publié dans linuxmag La documentation Perl sur les regex [12] est disponible en Français.

Dans un cadre dépassant Perl, le wikipedia propose un article [13] intéressant. Le livre [14] de de J. Friedl est une mine. Les pages 312 à 316 de la deuxième édition francaise (2003) traitent de l'idiome m/\G.../gc.

Finalement Dennis Ritchie propose une histoire des regex [15] et des incarnations des regex, de QED à Perl, en passant par ed, sed, grep, ex, vi et awk.

Récapitulatif

• m/\G.../gc est un idiome pour avancer dans l'analyse d'une chaîne.

• substr() = "toto" est un exemple de fonction en position lhs.

• Nous pouvons personnaliser le débogueur à l'aide du fichier ~/.perldb ou ~/.perlddb.ini. Il est possible d'exécuter pas à pas le code chargé par use nom_de_module en mettant un point d'arrêt au début de l'exécution du module avec b load nom_de_module.

Recherche de paquetages sur CPAN

Références

À vous !

Envoyez vos perles à perles@mongueurs.net, elles seront peut-être publiées dans un prochain numéro de Linux Magazine.