Les aventures de QLALR - utiliser QLALR pour générer un parseur pour une aventure textuelle

Qt Quarterly est une revue trimestrielle électronique proposée par Nokia à destination des développeurs et utilisateurs de Qt. Vous pouvez trouver ici les versions originales.

Nokia, Qt, Qt Quarterly et leurs logos sont des marques déposées de Nokia Corporation en Finlande et/ou dans les autres pays. Les autres marques déposées sont détenues par leurs propriétaires respectifs.

Cet article est la traduction de l'article QLALR Adventures - Using QLALR to generate a parser for a text adventure, par Geir Vattekar paru dans la Qt Quarterly Issue 33.

Cet article est une traduction de l'un des tutoriels en anglais écrits par Nokia Corporation and/or its subsidiary(-ies), inclus dans la documentation de Qt. Les éventuels problèmes résultant d'une mauvaise traduction ne sont pas imputables à Nokia.

Un des outils fournis avec Qt est QLALR, le générateur de parseurs (analyseur syntaxique). Il a été utilisé dans le passé pour Qt Script et est maintenant chargé de la lecture des flux Javascript de QML et XML de Qt. Malheureusement, QLALR a été inaccessible à la plupart des utilisateurs Qt à cause de sa documentation inexistante. Cet article va essayer d'y remédier.

QLALR prend un fichier avec une grammaire et produit du code C++ qui le fait correspondre à la grammaire. Les grammaires acceptées sont LALR(1), c'est-à-dire qu'elles ne cherchent pas plus d'un jeton plus loin. Comme yacc (un autre générateur de parseurs), QLALR aide à traiter l'associativité et les ambiguïtés (par exemple changer/réduire les conflits). Cependant, nous n'allons rien faire de très compliqué, nous allons plutôt regarder comment faire un usage basique de QLALR en implémentant un analyseur pour un langage petit et simple.

Pour trouver un exemple approprié, nous sommes remontés dans les années 80, époque à laquelle les aventures textuelles ont connu leurs jours de gloire. Une aventure textuelle raconte une histoire où le joueur peut interagir en tapant des commandes. Ces commandes sont écrites dans un langage beaucoup moins compliqué qu'un langage humain. Habituellement une sorte de pseudo anglais simplifié est utilisé. La grammaire est typiquement petite et précise. Nous avons donc pensé qu'un tel langage était approprié pour un exemple de QLALR.

Nous allons appeler notre langage plover (un nom qui doit faire tilter les vieux aventuriers qui ont joué à Advent \x{0096} l'ancêtre des jeux d'aventures textuelles). Jetons un coup d'œil à quelques phrases écrites en plover.

north
go north
eat the tasty apple
put orange peel in the trash bin

Voici la grammaire complète de plover en BNF (Backus-Naur Form) :

Input ::= Sentence
 
Sentence ::= SingleVerbSentence
          |  OneNounSentence
          |  TwoNounSentence
 
SingleVerbSentence  ::= 'go' SingleVerb
                     |  SingleVerb
 
SingleVerb ::= 'north' | 'south' | 'west' | 'east'
 
OneNounSentence ::= OneNounVerb Noun
 
OneNounVerb ::= 'eat'
 
Noun ::= 'the' ObjectNameList
      | ObjectNameList
 
ObjectNameList ::= OBJECTNAME
                |  ObjectNameList OBJECTNAME
 
TwoNounSentence ::= TwoNounVerb Noun Preposition Noun
 
TwoNounVerb ::= 'put'
 
Preposition ::= 'in'

OBJECTNAME est un jeton qui peut prendre n'importe quel mot, autrement dit comme une variable dans un langage de programmation. Les autres jetons sont définis explicitement.

L'entrée de QLALR est un fichier (d'extension .g) contenant la grammaire, la définition des jetons et le code C++ qui est exécuté lorsque la production est terminée. Ce fichier peut être utilisé pour construire une pile de symboles et garder une trace de l'état d'analyse. De plus, le gestionnaire de jetons doit être implémenté séparément, soit dans le fichier .g, soit dans un fichier source C++ séparé.

Regardons l'implémentation de la classe du parseur.

class CommandInterpreter : public $table
{
public:
    CommandInterpreter();
    ~CommandInterpreter();
 
    Command parse();
 
    int nextToken();
 
    void setInput(const QString &input);
 
    inline void reallocateStack();
 
    inline QString &sym(int index)
    	{ return sym_stack [tos + index - 1]; }
 
private:
    int tos;
    QStringList tokens;
    QVector<QString> sym_stack;
    QVector<int> state_stack;
    QString yylval;
};

Cette classe n'est pas générée. Nous l'utilisons pour créer un front-end facilement utilisable pour plover. $table est remplacé par le nom de la classe générée par QLALR qui contient des constantes, des tables et des fonctions dont nous avons besoin dans la fonction parse().

QLALR implémente son parsage avec une machine à états finie comprenant une pile d'états. Nous gérons nous-même la pile, pendant que QLALR nous dit quels états empiler et quand les dépiler. La variable tos pointe le haut de la pile d'états. Nous en reparlerons plus tard.

sym_stack est la pile de symboles, qui, dans notre cas, contient des QString. sym() va chercher les valeurs relatives à la production courante. yylval est modifié par le gestionnaire de jetons quand il rencontre un OBJECTNAME. Nous l'utilisons pour mettre à jour la pile de symboles.

Pour commencer le parsage d'une Command, nous appelons les méthodes setInput() puis parse() qui construiront pour nous la Command lors du parsage. Pour être complet, commençons par regarder la définition de la classe Command (qui n'est pas déclarée dans le fichier .g).

class Command
{
public:
    enum Verb { Eat, Go, Put, North, East, West, South };
    enum Preposition { In };
    enum State { Valid, Invalid };
 
    State state;
    QString errorMessage;
 
    Verb verb;
    QList<QString> nounNames; // First noun
    Preposition preposition;
    QList<QString> secondNames; // Second noun
};

Continuons avec le fichier d'entrée de QLALR :

%parseur CommandParser
%merged_output commandparser.cpp
%start Input

%parseur donne le nom de la classe générée par QLALR. %merged_output spécifie que nous ne voulons qu'un seul fichier de sortie contenant la définition et l'implémentation du code C++ dans le fichier .g. Vous pouvez utiliser %decl et %impl si vous voulez avoir des fichiers d'en-tête et d'implémentation séparés. %start spécifie où le parsage doit commencer. Le code ajouté pour la déclaration est enfermé entre /: et :/, alors que le code de l'implémentation est enfermé entre /. et ./.

Ensuite nous définissons les jetons :

-- The verbs
 
%token EAT "eat"
%token GO "go"
%token NORTH "north"
%token EAST "east"
%token SOUTH "south"
%token WEST "west"
%token PUT "put"
 
-- The preposition
 
%token IN "in"
 
-- Object names
 
%token THE "the"
 
%token OBJECTNAME "object"

Les jetons sont spécifiés par %token. Ceux-ci vont devenir des constantes du parseur généré et devraient être retournées par le gestionnaire de jetons. Notez que les chaîne sont uniquement utilisées pour une gestion des erreurs, autrement dit elles ne sont pas utilisées durant le parsage.

Pour notre petit langage, nous avons implémenté notre propre gestionnaire de jetons à travers la fonction nextToken(). Puisque nous appelons cette fonction nous-même durant le parsage, nous aurions pu utiliser n'importe quel lexer (analyseur lexical), comme lex.

int CommandInterpreter::nextToken()
{
    if (tokens.isEmpty()) {
        return EOF_SYMBOL;
    }
 
    QString nextToken = tokens.takeFirst();
 
    nextToken = nextToken.toLower();
 
    if (nextToken == "eat") {
        return CommandParser::EAT;
    }
 
    ...
 
    if (nextToken == "the") {
        return CommandParser::THE;
    }
 
    yylval = nextToken;
    return CommandParser::OBJECTNAME;
}

tokens est une QStringList qui contient les mots de la phrase plover (par exemple [ 'put' 'gold' 'in' 'chest' ]). Comme vous pouvez le voir, nous retournons simplement la constante du jeton dès que nous l'avons identifiée. Remarquez que nous gardons la valeur du jeton lorsque nous rencontrons un nom d'objet. Nous en aurons besoin plus tard.

Dans cette partie, nous allons jeter un coup d'œil à l'implémentation de la grammaire de plover. C'est ici que QLALR (ou n'importe quel autre générateur de parseurs d'ailleurs) va vraiment nous aider.

Input: Sentence ;
 
Sentence: GO SingleVerbSentence ;
Sentence: SingleVerbSentence ;
Sentence: OneNounSentence ;
Sentence: TwoNounSentence ;

Chaque partie d'une production (soit un jeton, soit une autre production) est séparée par un espace. Si la production comporte des alternatives, elles sont décrites comme ci-dessus pour la production Sentence.

Il est possible d'insérer du code lorsque la production est terminée :

ObjectName: OBJECTNAME ;
/.
    case $rule_number: {
        sym(1) = yylval;
    } break;
./

Le code entre /. et ./ est inséré dans le parseur généré et sera exécuté lorsque le parsage aura correspondu avec la production précédente. $rule_number sera remplacé par le nombre représentant la production dans la grammaire.

La fonction sym() accède à la pile de symboles. Elle va chercher la valeur relative à la production courante. sym(1) sera donc toujours le premier élément de la production courante. Notre pile de symboles est composée de QString. Nous ne gardons la valeur que pour les OBJECTNAME, donc la pile contendra une chaine vide pour toutes les autres parties de la grammaire.

Nous n'allons pas étudier chaque production étant donné que nous avons déjà montré la grammaire de plover en BNF, mais, avant de quitter les productions, voyons comment les objets et les phrases sont parsés.

ObjectList: ObjectList ObjectName ;
 
Noun: THE ObjectList ;
Noun: ObjectList ;
 
ObjectList: ObjectName ;
/.
    case $rule_number: {
        command.nounNames.append(sym(1));
    } break;
./
 
...
 
TwoNounSentence: PUT Noun IN Second ;
/.
    case $rule_number: {
        command.verb = Command::Put;
        command.preposition = Command::In;
    } break;
./

Notez que chaque partie d'une production aura une valeur différente sur la pile de symboles.

Dans la fonction parse(), nous utilisons des tables générées par QLALR pour implémenter le parsage. QLALR génère aussi quelques fonctions pour nous aider.

La fonction de parsage comporte 3 parties :

• trouver une production ;
• exécuter le code de la production trouvée (comme vu précédemment) ;
• gérer les erreurs de parsage.

Command CommandInterpreter::parse()
{
    Command command;
 
    const int INITIAL_STATE = 0;
    int yytoken = -1;
 
    tos = 0;
    state_stack[++tos] = INITIAL_STATE;
 
    while (true) {
        const int state = state_stack.at(tos);
        if (yytoken == -1 && - TERMINAL_COUNT != action_index [state] ) {
            yytoken = nextToken();
        }
 
        int act = t_action (state, yytoken);
        if (act == ACCEPT_STATE) {
            command.state = Command::Valid;
            return command;
 
        } else if (act > 0) {
            if (++tos == state_stack.size())
                reallocateStack();
            state_stack[tos] = act;
            yytoken = -1;
        } else if (act < 0) {

Cela peut sembler effrayant et incompréhensible mais n'ayez pas peur, ce code est habituellement le même entre les différents parseurs. Continuez donc avec un copier-coller. L'essentiel ici est que la fonction t_action() trouve le prochain état à partir de l'état courant. Elle retourne une valeur positive lorsqu'elle a besoin d'un nouveau jeton et négative lorsque la production est complète. La valeur 0 signifie que le jeton courant ne correspond pas à la grammaire (donc, une erreur).

La boucle while va tourner jusqu'à ce que l'on ait rencontré une erreur ou que l'on atteigne ACCEPT_STATE, c'est-à-dire que l'entrée correspond à la grammaire et que nous avons une commande valide.

        } else if (act < 0) {
            int r = -act - 1;
            tos -= rhs[r];
            act = state_stack.at(tos++);
 
            switch(r) {
./
 
Input: Sentence ;
 
...
 
/.
            } // of the switch
 
            state_stack [tos] = nt_action (act, lhs [r] - TERMINAL_COUNT);
        } else {

Après qu'une production ait été trouvée et que le code (s'il y en a) ait été exécuté, nous enlevons les états utilisés par la production terminée et continuons le parsage de la production où nous nous sommes arrêtés. On fait cela en mettant à jour tos et en appelant nt_action(), qui va chercher l'action à la nouvelle position de tos. Encore une fois, faites juste un copier-coller du code dans votre parseur.

Enfin, la gestion d'erreur :

   } else {
         QString m_errorMessage;
          int ers = state;
          int shifts = 0;
          int reduces = 0;
          int expected_tokens[3];
          for (int tk = 0; tk < TERMINAL_COUNT; ++tk) {
              int k = t_action(ers, tk);
 
              if (! k)
                continue;
              else if (k < 0)
                ++reduces;
              else if (spell[tk]) {
                  if (shifts < 3)
                    expected_tokens[shifts] = tk;
                  ++shifts;
              }
          }
 
...

Pour vérifier quels jetons correspondent avec la grammaire dans un état spécifique, nous appelons t_action() avec tous les jetons que nous avons et ajoutons les jetons acceptés dans un tableau qui peut être utilisé pour les messages d'erreur. Nous ne prenons pas la peine de vous montrer le code pour écrire des messages d'erreur. Les messages d'erreur de plover ne seraient pas vraiment utiles pour les autres langages. Le message « Je n'ai pas compris cette phrase. » par exemple serait très agaçant en sortie d'un compilateur C. Les chaines que nous avons spécifiées pour les jetons ont été ajoutées dans un tableau dont les indices sont égaux aux valeurs des jetons. Vous pouvez donc obtenir le nom d'un jeton en écrivant spell[PloverParser::TO], par exemple.

Pour un exemple plus complexe, vous pouvez jeter un coup d'oeil au fichier .g utilisé pour Qt Script (il est toujours distribué dans src/script/parseur). Vous trouverez aussi quatre exemples dans util/qlalr/examples. Si vous voulez devenir un professionnel de QLALR, essayez de comprendre src/corelib/xml/qxmlstream.g, vous aurez alors atteint votre but.

Le code source des exemples de cet article est disponible sur le site des Qt Quarterly : qq33-qlalr.zip.

Geir Vattekar est un rédacteur technique du framework de développement Qt. L'écriture mise à part, il aime la fiction interactive (jeu d'aventure textuel) et la programmation fonctionnelle.

Au nom de toute l'équipe Qt, j'aimerais adresser le plus grand remerciement à Nokia pour nous avoir autorisés à traduire cet article !

Merci à littledaem pour sa relecture et ses conseils.