ft_lex

Mon projet le plus accompli à ce jour. ft_lex m’a permis de découvrir le monde des automates et de la théorie des compilateurs. J’ai hâte de commencer le projet suivant, ft_yacc !.

Aperçu

Une réimplémentation complète du générateur lex, visant la conformité POSIX. Le programme prend en entrée une spécification .l et produit un scanner C complet — une table de transition, un pilote yylex() et une librairie libl — reproduisant fidèlement l’interface de l’outil original.

Le pipeline suit la construction classique d’un compilateur: le fichier .l est analysé en règles et macros, chaque expression régulière est convertie en notation postfixée via l’algorithme du shunting-yard, puis compilée en NFA (Nondeterministic finite automaton, automate fini non déterministe) grâce à la construction de Thompson. Tous les NFA sont ensuite fusionnés et convertis en un unique DFA (Deterministic finite automaton, automate fini déterministe) par construction par sous-ensemble. Les classes de charactères sont représentées par des bitsets ASCII de 128 bits afin d’éviter une trop large expansion. Les tables générées supportent une représentation compressée, via un pipeline de compression en trois étapes, réduisant l’empreinte mémoire au prix d’un accés indirect.

Le runtime yylex() est écrit comme un template C intégré à la compilation via xxd -i, instancié par substitution de marqueurs lors de la génération de code. Il supporte l’interface standard complète: conditions de départ (inclusives et exclusives), ancres BOL (beginning of line), yymore(), REJECT, les modes %array/%pointer, ainsi que les trailing context à longueur fixes ou variables (DFA isolés, simulés à l´exécution).

Pipeline complet.

Défis technique

Comprendre la théorie des automates NFA, DFA, transition spontanée (ε-transition), construction par sous-ensembles — rien de tout ça n’était acquis au départ. Il a fallu construire la théorie avant de pouvoir écrire le code, ce qui a impliqué de travailler à partir du Dragon Book (Compilateurs : principes, techniques et outils, Aho, Sethi, Ullman) et d’autres références (et de dessiner beaucoup de schémas approximatifs) avant même de commancer l’implémentation.

Représentation NFA vs DFA de ab|a.

Faire évoluer la représentation des classes de caractères. Les premières versions n’avaient aucun concept dédié aux classes de charactères — un motif comme [a-z] était compilé en une chaîne de 26 possibilités, ce qui faisait exploser la taille du NFA. Une première tentative de représentation compacte via vector<bool> introduisait des bugs subtils dans la création de l’automate. La conception finale, bitset<128>, est à la fois compacte et correcte.