L'algorithme de Thompson

Cet article décrit une implantation de l'algorithme de Thompson en C++. L'algorithme de Thompson est un algorithme permettant d'exécuter efficacement des expressions régulières en simulant des automates finis non déterministes (AFN).

L'algorithme de Thompson

Dans son article de 1968, Regular expression search algorithm, Ken Thompson décrit une technique permettant de construire un automate fini non déterministe représentant une expression régulière donnée et d'en simuler l'exécution.

Selon la technique décrite par Thompson, l'expression régulière doit d'abord être convertie en notation post-fixée. Une fois cette étape accomplie, l'automate est construit par la composition successive de fragments d'automate (les détails plus bas). Pour ce faire, Thompson emploie deux piles, une première contenant l'expression régulière précédemment convertie en notation post-fixée et une seconde contenant les fragments d'automate. Bien que cette méthode soit parfaitement fonctionnelle, il est possible de remplacer la conversion explicite de l'expression régulière en notation post-fixée et l'utilisation des deux piles par une descente récursive. Cette seconde approche est certainement plus naturelle de nos jours, mais surtout plus expressive.

Une fois l'automate construit, le tâche consiste simplement à le visiter en conservant, pour chaque étape de calcul, l'ensemble des états atteignables. L'ensemble de départ n'étant composé que d'un seul état: l'état initial de l'automate. L'exécution de l'algorithme cesse dès que la chaîne d'entrée est épuisée ou lorsque l'ensemble des états atteignables est vide. Si, lorsque la chaîne d'entrée est épuisée, l'état acceptant a été atteint, c'est donc dire que la chaîne de caractères est acceptée par l'automate et, par conséquent, correspond à l'expression régulière.

Implantation

Cette description de haut niveau étant complète, voyons comment implanter cet algorithme en C++. Mais dans un premier temps, il importe de déterminer la grammaire d'expression régulière supportée, en l'occurrence:

<regexp>        ::= <branche> { '|' <branche> }
<branche>       ::= <particule> { <particule> }
<particule>     ::= <atome> { '*' | '?' | '+' }
<atome>         ::= '(' <regexp> ')' | <caractere> | <nombre>
<caractere>     ::= 'a' | 'b' | ... | 'z'
<nombre>        ::= '0' | '1' | ... | '9'

Modélisation de l'automate fini non déterministe

L'automate est tout simplement représenté par un graphe de nœuds[1] liés entre eux par des pointeurs - rien de bien surprenant. Tous les nœuds de l'automate sont dérivés d'une classe de base contenant quelques informations de débogage ainsi qu'une méthode permettant de recevoir un visiteur (les détails plus bas).

/! NFA state base class.
struct State {

    //! Define explicitly three kind of state to supplement
    //! C++ polymorphic behavior. Only for debugging purpose.
    typedef enum {
        labeled, split, match
    } Kind;

    //! \brief Construct a state of the defined Kind.
    //! \param[in] kind The state kind.
    State(Kind kind) :
        kind(kind) {
    }

    //! \brief Visitor entry point.
    //! \param visitor The visiting visitor.
    virtual void visit(Visitor* visitor) const {}

    Kind kind;  /**< The state kind. Only for debugging purpose. */
};

Les nœuds de type «Transition» modélisent les états dont le seul arc sortant est étiqueté d'un certain symbole. Par exemple, l'expression régulière ab serait composée de deux transitions étiquetées respectivement a et b.

//! NFA labeled transition.
struct Transition: public State {

    //! \brief Construct a Transition State.
    //! \param[in] label The transition label.
    Transition(char label) :
        State(labeled), label(label) {
    }

    virtual void visit(Visitor* visitor) const {
        visitor->visit_transition(this);
    }

    State* next;    /**< A pointer to the next state. */
    char label;     /**< The state transition label. */
};

Les nœuds de type «Split» représentent les unions, mais permettent également de modéliser des opérateurs plus évolués: *, ? et + (les détails plus bas).

//! NFA splitting state.
struct Split: public State {

    //! \brief Construct a Split State.
    //! \param[in] first The first neighbor State.
    //! \param[in] second The second neighbor State.
    Split(State* first, State* second) :
        State(split), first(first), second(second) {
    }

    virtual void visit(Visitor* visitor) const {
        visitor->visit_split(this);
    }

    State* first;   /**< A pointer to the first following state. */
    State* second;  /**< A pointer to the second following state. */
};

Chaque automate possède un seul nœud de type «Match» représentant, sans surprise, l'état acceptant.

//! NFA accepting state.
struct Match: public State {
    //! \brief Construct a matching state.
    Match() :
        State(match) {
    }

    virtual void visit(Visitor* visitor) const {
        visitor->visit_match(this);
    }
};

Afin de rendre tout cela un peu plus concret, voici ce à quoi ressemble l'expression régulière c|b*a une fois convertie en automate:

c|b*a

La classe NFA contient quant à elle deux pointeurs, un sur le nœud de départ et l'autre sur l'état acceptant, ainsi qu'un pool de mémoire à partir duquel les nœuds de l'automate ont été alloués (les détails plus bas). L'utilisation d'un pool de mémoire pour allouer et libérer les noeuds est nécessaire car le graphe de l'automate n'est pas acyclique, rendant par le fait même les stratégies simplistes de gestion de la mémoire inutilisables. Finalement, le constructeur du NFA est déclaré privé afin de s'assurer que seul le parser d'expressions régulières , la classe RegexParser, ne soit en mesure d'instancier un automate.

class NFA {
protected:

    friend class RegexParser;

    typedef internal::State State;
    typedef internal::StatePool StatePool;
    typedef internal::Visitor Visitor;

    //! \brief NFA constructor.
    //! \param[in] start A pointer to the starting start
    //! \param[in] end A pointer to the accepting state
    //! \param pool The state memory pool
    NFA(State* start, State* end, std::shared_ptr<StatePool> pool) :
        start(start), end(end), pool(pool) {
    }

public:

    //! \brief
    void visit(Visitor* visitor) const {
        visitor->visit_nfa(start, end);
    }

protected:

    State* start;    /**< The NFA start state. */
    State* end;      /**< The NFA accepting state. */
    std::shared_ptr<StatePool> pool;    /**< The state pool. */
};

Il aurait été possible d'utiliser un pool de mémoire de qualité industrielle — boost::pool et alli — pour allouer les nœuds du NFA, mais l'usage est ici tellement spécifique qu'il est tout aussi simple d'en coder un sur mesure. Dans cette optique, l'élément essentiel à remarquer est qu'une fois les nœuds instanciés, aucune déallocation n'aura lieu avant la destruction finale du pool. Un tel comportement rappelle immédiatement la procédure Mark and Release chère au aficionados du langage Pascal ou encore les Obstacks de la librairie GNU libc.

Le design utilisé pour le pool de nœuds est très simple: une liste chaînée de blocs mémoire — poétiquement appelés Chunks — à partir desquels sont successivement alloués les nœuds du NFA. Lorsque le pool est détruit, la mémoire est tout simplement libérée en supprimant la liste chaînée. Ce comportement est possible, car les nœuds du NFA n'allouent pas d'objets dynamiquement; ce faisant leur destructeur n'a pas à être appelé. En outre, les problèmes d'alignement sont évités car les blocs de mémoire sont exclusivement utilisés pour allouer les nœuds du NFA.

class StatePool {

    //! \brief StatePool memory representation.
    //!
    //! No data alignement is performed when a Chunk
    //! allocates memory, i.e. it can't be used in a
    //! general case.
    template <unsigned int chunk_size>
    struct Chunk {
    public:
        //! \brief Default constructor.
        //! \post The next pointer is NULL
        //! \post The data_index is set to 0.
        Chunk(): next(NULL), data_index(0) {}

        //! \brief Reserve N bytes in this chunk.
        //! \param nbytes Number of bytes to allocate/reserve.
        //! \pre The requested number of bytes (nbytes) must be
        //!      smaller or equal (<=) to the chunk_size.
        //! \return A raw pointer to the begining of the reserved
        //!         memory space.
        void* reserve(size_t nbytes) throw(std::logic_error) {

            // Make sure that a Chunk can really
            // serve a request of this size.
            if (nbytes > chunk_size)
                throw std::logic_error("StatePool::Chunk::reserve(): the "
                                       "requested number of bytes is bigger "
                                       "than a chunk_size.");

            // Make sure that we have enough room serve
            // the request. If not return NULL. The pool
            // will handle this by allocating a new chunk.
            if (chunk_size - data_index >= nbytes) {
                void* dptr = &data[data_index];
                data_index += nbytes;
                return dptr;
            }

            return NULL;
        }

        Chunk* next;             /**< A pointer to the
                                      next chunk. */
        unsigned int data_index; /**< Current position
                                      in the data array. */
        char data[chunk_size];   /**< Allocation array of
                                      chunk_size bytes. */
    };

    typedef Chunk<64> MemoryChunk;

public:

    //! \brief Default constructor.
    StatePool() {
        root_chunk = last_chunk = new MemoryChunk;
    }

    //! \brief Destructor.
    //!
    //! Free all memory associated to the states allocated from
    //! this pool. Beware that it won't call the destructor on
    //! those objects.
    ~StatePool() {
        while (root_chunk) {
            MemoryChunk* temp_chunk = root_chunk;
            root_chunk = root_chunk->next;
            delete temp_chunk;
        }
    }

    //! \brief Construct a split state from the pool.
    //! \param[in] first The first neighbor State.
    //! \param[in] second The second neighbor State.
    //! \return A pointer to the newly constructed split state.
    Split* make_split(State* first, State* second) {
        void* split = reserve(sizeof(Split));
        new (static_cast<void*>(split)) Split(first, second);
        return reinterpret_cast<Split*>(split);
    }

    //! \brief Construct a transition state from the pool.
    //! \param label The transition label.
    //! \return A pointer to the newly constructed transition state.
    Transition* make_transition(char label) {
        void* trans = reserve(sizeof(Transition));
        new (static_cast<void*>(trans)) Transition(label);
        return reinterpret_cast<Transition*>(trans);
    }

    //! \brief Construct a match state from the pool.
    //! \return A pointer to the newly constructed match state.
    Match* make_match() {
        void* match = reserve(sizeof(Match));
        new (static_cast<void*>(match)) Match();
        return reinterpret_cast<Match*>(match);
    }

protected:

    //! \brief Reserve N bytes from this pool.
    //! \param nbytes Number of bytes to allocate/reserve.
    //! \return A raw pointer to the begining of the reserved
    //!         memory space.
    void* reserve(size_t nbytes) {
        // Try to reserve N bytes from the last
        // allocated memory chunk.
        void* data = last_chunk->reserve(nbytes);

        // Check if it's a miss. If so, we'll
        // need to allocate a new chunk.
        if (!data) {
            last_chunk->next = new MemoryChunk;
            last_chunk = last_chunk->next;
            data = last_chunk->reserve(nbytes);
        }

        return data;
    }

    StatePool(const StatePool&) {}
    void operator=(const StatePool&) {}

    MemoryChunk* root_chunk; /**< First allocated chunk. */
    MemoryChunk* last_chunk; /**< Last allocated chunk. */
};

Maintenant que la représentation d'un automate est fixée, il s'agit de voir comment en synthétiser un à partir d'une expression régulière.

Construction de l'automate fini non déterministe

Tel que mentionné précédemment, l'automate est composé d'un ensemble de fragments. Ces fragments sont assemblés suivant les opérations de base des expressions régulières.

Les figures ci-dessous montrent comment les fragments sont assemblés en fonction des opérations appliquées.

Un fragment possède toujours un état d'origine et un nombre quelconque d'arcs sortants. Afin de bien visualiser ce que cela peut signifier, la figure ci-dessous présente le fragment final obtenu suite à l'analyse de l'expression régulière a|b|c:

Dernier fragment de l'expression a|b|c.

La classe Fragment est une classe privée de la classe Parser. Il faut voir cette dernière comme un objet de calcul intermédiaire permettant de séparer la logique propre à la construction de l'automate de celle propre à l'analyse syntaxique.

class Fragment {
public:
    //! \brief Construct an empty fragment.
    Fragment(std::shared_ptr<StatePool> pool) :
        start(NULL), pool(pool) {
    }

    //! \brief Construct a fragment consisting of one labeled transition.
    Fragment(char label, std::shared_ptr<StatePool> pool) :
        pool(pool) {
        Transition* state = pool->make_transition(label);
        out_edges.push_back(&state->next);
        start = state;
    }

    //! \brief Concatenate two NFA fragments.
    //! \param[in] frag The fragment to be concatenate.
    void concat(const Fragment& frag) {
        // Set all outgoing edges of the current fragment to
        // point to the concatenated fragment start state.
        for (size_t i = 0; i < out_edges.size(); i++) {
            *out_edges[i] = frag.start;
        }
        // Our outgoing edges are now the one of the
        // concatenated fragment.
        out_edges = frag.out_edges;
    }

    //! \brief Perform the union of two NFA fragments.
    //! \param[in] frag The fragment to be united.
    void split(const Fragment& frag) {
        // Our new start state is a split.
        start = pool->make_split(start, frag.start);

        // Append to our outgoing edges the one from frag.
        for (size_t i = 0; i < frag.out_edges.size(); i++) {
            out_edges.push_back(frag.out_edges[i]);
        }
    }

    //! \brief Perform a closure on this NFA fragment.
    void closure() {
        // Our new start state is a split.
        Split* split = pool->make_split(start, NULL);

        // All outgoing edges point back to the new start.
        for (size_t i = 0; i < out_edges.size(); i++) {
            *out_edges[i] = split;
        }
        start = split;
        out_edges.clear();
        out_edges.push_back(&split->second);
    }

    //! \brief Apply the + operator on this NFA fragment.
    void one_or_more() {
        Split* split = pool->make_split(start, NULL);
        // All outgoing edges point to the new start.
        for (size_t i = 0; i < out_edges.size(); i++) {
            *out_edges[i] = split;
        }
        out_edges.clear();
        out_edges.push_back(&split->second);
    }

    //! \brief Apply the ? operator on this NFA fragment.
    void zero_or_one() {
        Split* split = pool->make_split(start, NULL);
        out_edges.push_back(&split->second);
        start = split;
    }

    //! \brief Convert this fragment to a complete NFA by appending
    //! to it an accepting state.
    std::shared_ptr<NFA> to_nfa() {
        Match* match = pool->make_match();
        // All outgoing edges point to the accepting state.
        for (size_t i = 0; i < out_edges.size(); i++) {
            *out_edges[i] = match;
        }
        return std::shared_ptr<NFA>(new NFA(start, match, pool));
    }

protected:
    State* start;                    /**< The fragment start state. */
    std::vector<State**> out_edges;  /**< List of pointers to the unbouded
                                          outgoing edges of the fragment. */
    std::shared_ptr<StatePool> pool; /**< Pool from which this fragment
                                          allocates NFA states. */
};

Étant donnée la simplicité de la grammaire fixée précédemment, la descente récursive de l'analyseur syntaxique est directement guidée par les caractères de l'expression régulière. Toutefois, si des classes de caractères ou encore des séquences d'échappement devaient être supportées, l'ajout d'une phase d'analyse lexicale serait probablement nécessaire.

Le code ci-dessous devrait paraître très naturel pour quiconque ayant déjà travaillé à des problèmes d'analyse syntaxique.

//! \brief A regexp parser.
class RegexParser {

    typedef internal::State State;
    typedef internal::Split Split;
    typedef internal::Match Match;
    typedef internal::Transition Transition;
    typedef internal::StatePool StatePool;

public:

    //! \brief Build the NFA for a regular expression.
    //! \param regexp The regular expression string.
    //! \return A heap allocated NFA.
    std::shared_ptr<NFA> parse(const std::string& regexp) {
        pool = std::make_shared<StatePool>();
        this->regexp = regexp;  // Set parser input.
        length = regexp.size(); // Set input size.
        pos = 0;    // Set current position in input.
        advance();  // Put the first symbol in curtok.
        Fragment fragment = parse_regexp(); // Parse the regexp,
        return fragment.to_nfa();           // converts it to an NFA.
    }

protected:

    //! \brief Advance by one curtok.
    //! \post curtok contains the next regexp symbol or the null
    //! char if the input regexp is exhausted.
    void advance() {
        if (pos < length)
            curtok = regexp[pos++];
        else
            curtok = '\0';
    }

    //! \brief Advance curtok by one, checking curtok current value.
    //! \param c The character to match curtok against.
    //! \post curtok contains the next regexp symbol or the null
    //! char if the input regexp is exhausted.
    void advance(char c) {
        if (curtok != c) {
            std::stringstream error_msg;
            error_msg << "expected " << c <<" but got ";
            if (curtok == '\0') { error_msg << "EOL"; }
            else { error_msg << curtok; }
            throw ParseError(error_msg.str(), pos);
        }
        advance();
    }

    //! \brief Parse a regexp.
    //! \return A NFA fragment.
    //!
    //! \<regexp>    ::= \<branche> { '|' \<branche> }
    Fragment parse_regexp() {
        Fragment frag = parse_branch();
        while (curtok == '|') {
            advance('|');
            frag.split(parse_branch());
        }
        return frag;
    }

    //! \brief Parse a regexp branch.
    //! \return A NFA fragment.
    //!
    //! \<branche>   ::= \<particule> { \<particule> }
    Fragment parse_branch() {
        Fragment frag = parse_particule();
        // Particule are delimited either by:
        // - the union symbol;
        // - a close parenthesis;
        // - a null chararter.
        while (curtok != '|' && curtok != ')' && curtok != '\0') {
            frag.concat(parse_particule());
        }
        return frag;
    }

    //! \brief Parse a regexp particule.
    //! \return A NFA fragment.
    //!
    //! \<particule> ::= \<atome> { '*' | '?' | '+' }
    Fragment parse_particule() {
        Fragment frag = parse_atome();
        switch (curtok) {
        case '*':
            frag.closure();
            advance('*');
            break;
        case '+':
            frag.one_or_more();
            advance('+');
            break;
        case '?':
            frag.zero_or_one();
            advance('?');
        }
        return frag;
    }

    //! \brief Parse a regexp atome.
    //! \return A NFA fragment.
    //!
    //! \<atome>     ::= '(' \<regexp> ')' | \<char> | \<number>
    //! \<char>      ::= 'a' | 'b' | ... | 'z'
    //! \<number>    ::= '0' | '1' | ... | '9'
    Fragment parse_atome() {
        Fragment frag(pool);
        if (curtok == '(') {
            advance('(');
            frag = parse_regexp();
            advance(')');
        } else {
            frag = Fragment(curtok, pool);
            advance();
        }
        return frag;
    }

    std::shared_ptr<StatePool> pool;  /**< State memory pool. */
    std::string regexp; /**< The input regular expression. */
    int length;         /**< length of the input regular expression. */
    int pos;            /**< Current position in the input regexp. */
    char curtok;        /**< The current token. */
};

L'algorithme de Thompson per se

Il serait possible d'implanter directement la logique de l'algorithme de Thompson au sein de la classe NFA. Néanmoins, l'utilisation d'un visiteur pour encapsuler celui-ci est très naturelle. En effet, il s'agit de constater que l'algorithme de Thompson consiste essentiellement en une visite de l'automate guidée par la chaîne de caractères donnée en argument.

L'implantation de l'algorithme est présentée ci-dessous.

//! \brief Visitor encapsulating the Thompson algorithm.
//!
//! This visitor is implementing the Thompson NFA simulation.
class ThompsonAlgorithm: public internal::Visitor {

    typedef internal::State State;
    typedef internal::Split Split;
    typedef internal::Transition Transition;
    typedef internal::Match Match;

public:

    //! \brief Simulate the NFA over the input string.
    //! \param str The string to match.
    //! \param nfa The NFA to execute.
    bool accept(const std::string& str, const std::shared_ptr<NFA> nfa) {

        input = str;         // Set the input string.
        pos = 0;             // Set current position in the input.
        length = str.size(); // Set the input length.
        curtok = 'a';        // Just to be sure that it's not a null char.

        nfa->visit(this);

        // In order to accept the input
        // - the final set must contain the accepting state (end) or
        //   matched is true, which means that the matching state was
        //   visited during the last iteration
        // - and the input must have all been consumed.
        return (matched || current.find(end) != current.end()) && curtok == '\0';
    }

    void visit_nfa(const State* start, const State* end) {
        this->start = start;
        this->end = end;

        current.clear();        // Prime the "current" set
        current.insert(start);  // for the first iteration.

        // Iterate over every input characters or until there is
        // no more accessible state in the "current" set.
        while (curtok != '\0' && current.size() != 0) {
            matched = false;
            advance();

            // We visit every accessible state.
            for (std::set<const State*>::const_iterator i = current.begin();
                   i != current.end(); ++i) {

                (*i)->visit(this);
            }

            current.swap(next); // Swap the "current" set with the
            next.clear();       // "next" set and then clear the
                                // "next" set for the next iteration.
        }
    }

    void visit_transition(const Transition* trans) {
        // If we can follow the transition based
        // on the current token, insert the next
        // state in the "next" state.
        if (curtok == trans->label)
            next.insert(trans->next);
    }

    void visit_split(const Split* split) {
        // It's a split, visit both branches.
        split->first->visit(this);
        split->second->visit(this);
    }

    void visit_match(const Match* match) {
        matched = true;
    }

protected:

    //! \brief Advance by one curtok.
    //! \post curtok contains the next regexp symbol or the null
    //! char if the input is exhausted.
    void advance() {
        if (pos < length) {
            curtok = input[pos++];
        } else {
            curtok = '\0';
        }
    }

    bool matched;       /**< Have we visited the accepting
                             state on the last iteration. */
    char curtok;        /**< The char we're looking at in the input string. */
    int pos;            /**< The current position in the input string. */
    int length;         /**< The input string length. */
    std::string input;  /**< The string to match. */
    const State* start; /**< Pointer to the start state. */
    const State* end;   /**< Pointer to the accepting state. */
    std::set<const State*> current; /**< The set of states being visited. */
    std::set<const State*> next;    /**< The set of states to be visited. */
};

Une fois l'algorithme instancié, il s'agit tout simplement d'appeler la méthode accept(const std::string&, std::shared_ptr<NFA>) avec comme arguments un NFA et la chaîne de caractères contre laquelle on souhaite simuler celui-ci.

Conclusion

L'algorithme de Thompson est d'une élégance rare. De plus, son implantation se révèle être d'une concision appréciable.

L'implantation présentée ci-dessus n'est évidemment pas optimisée, mais demeure supérieure, de par la nature même de l'algorithme utilisé, à toutes les implantations récursives exploitant du retour sur trace. Plus précisément, la complexité de l'algorithme de Thompson est bornée à O(mn), où m est la taille de l'expression régulière et n la taille du texte analysé. En comparaison, les implantations récursives exploitant du retour sur trace affichent une complexité O(2n), où n est la taille du texte. Évidemment, de tels comportements ne surviennent que pour quelques cas pathologiques. Mais, tout bien considéré, autant s'en tenir éloigné.

Le code source peut être visionné en ligne (thompson.cpp). La documentation Doxygen peut être consultée ici.

Mathieu Turcotte, septembre 2010.

  1. Le terme nœud est employé dans l'espoir de bien faire ressortir le fait qu'il ne s'agit pas d'«états» au sens où la littérature sur les automates l'entend normalement.