Construire un moteur regex -- ressources en ligne ?

Question

Je suis intéressé par la construction d'un moteur regex, comme un projet secondaire, juste à des fins d'apprentissage.

Je connais la théorie de l'évaluation des expressions régulières et j'ai une compréhension suffisante des machines à états finis, etc.

Ce qui m'intéresse, c'est de savoir comment un moteur de regex est implémenté dans un logiciel. Je me demandais donc s'il existait une sorte de tutoriel ou de ressource en ligne qui explique l'implémentation d'un moteur regex, la traduction du regex en un FSM, etc. Je ne veux pas de sites qui ne font qu'expliquer la théorie.

Merci.

Answer 1

Russ Cox a une belle collection d'articles sur Mise en œuvre des expressions régulières notamment son article La correspondance par expression régulière peut être simple et rapide qui vaut la peine d'être lu.

Answer 2

Je pense que l'article Comment fonctionnent les Regex de Mark-Jason Dominus est excellent. Il s'adresse à des non-programmeurs, mais il est écrit de manière très algorithmique et peut donc être utilisé pour mettre en œuvre un tel moteur, surtout si vous avez une certaine expérience de la compilation. Je l'ai fait moi-même.

L'article mentionne également des conseils et astuces plus avancés, et contient des informations sur les limitations du moteur.

Answer 3

Dans le premier chapitre de Beau Code Brian Kernighan explique comment Rob Pike a créé un petit matcheur regex élégant. C'est vraiment simple, mais Kernighan donne sept exercices pour l'étendre, ce qui pourrait être une bonne introduction pour vous.

Answer 4

J'ai 2 liens intéressants pour les mécanismes d'expressions régulières,

• La correspondance par expression régulière peut être simple
• Moserware : Comment les expressions régulières de .NET Régulières de .NET

Answer 5

Si vous êtes à l'aise avec le langage C, il vous sera probablement utile de consulter le code source de l'application Expressions régulières compatibles avec Perl .