La construction d'un moteur d'expressions régulières — des ressources en ligne?
Je suis intéressé par la construction d'un moteur d'expressions régulières, comme un side-project, juste à des fins d'apprentissage.
Je sais que la théorie de l'évaluation des expressions régulières, et avoir une compréhension suffisante de des machines à états finis, etc.
Ce qui m'intéresse est de savoir comment un moteur d'expressions régulières est implémentée dans le logiciel. Donc je me demandais si il y avait une sorte de tutoriel ou de ressources en ligne qui explique la mise en œuvre d'un moteur d'expressions régulières, de la traduction de l'expression régulière regex pour un FSM et ainsi de suite. Je ne veux pas de sites qui vient de explique la théorie derrière tout cela.
Grâce.
Vous devez vous connecter pour publier un commentaire.
Russ Cox a une belle collection d'articles sur La Mise En Œuvre Des Expressions Régulières, en particulier son article Expression Régulière Correspondant Peut Être Simple Et Rapide la peine de lire.
Je pense que l'article Comment Regexes Travail par Mark-Jason Dominus est excellent. Elle est destinée à des non-programmeurs, mais il est écrit dans un très façon algorithmique et donc il peut être utilisé pour la mise en œuvre d'un tel moteur, surtout si vous avez de l'expérience à la compilation. Je l'ai fait moi-même.
L'article mentionne aussi les plus avancées de conseils et d'astuces, et dispose de quelques informations sur le moteur de limitations.
Dans le premier chapitre de Beau Code (Amazon, en ligne projet) Brian Kernighan parle de Rob Pike élégant, très petite regex matcher. C'est vraiment simple, mais Kernighan donne sept exercices pour l'étendre, ce qui pourrait être une bonne intro pour vous.
J'ai 2 liens intéressants pour les expressions régulières mécanismes,
simple
Expressions Vraiment Travailler
Si vous êtes à l'aise avec le C, vous aurez probablement bénéficier de regarder le code source pour Perl-compatible regular expressions.
Je suis en retard à la fête, mais j'ai trouvé cette WSU cours de cession les plus utiles lors de la présentation d'un moteur d'expressions régulières implemenetation à un niveau élevé. Je ne sais pas C, alors c'était bien que le matériel a été présenté dans un langage indépendant du format. Surtout, il fait du bon travail en expliquant:
En plus, j'ai trouvé Le rythme du professeur de l'article utile dans la mise en œuvre de la
re2postméthode mentionnée par WSU et Cox.Je vous recommande de lire les WSU l'article premier, puis Russ Cox de l'article pour plus de profondeur.
Le cinquième chapitre de Les algorithmes de par Robert Sedgewick est une très bonne introduction au sujet. Il explique ce qu'est un NFA est et comment une NFA être construit à partir d'une expression régulière. Les exemples ont et des visuels sont très claires. Il a même code pour une simple regex matcher. Et il y a quelques exercices pour mettre en œuvre plus de regex fonctionnalités.
un autre simple et clair implementacion (C, moins de 500 lignes) RecursiveRegexpRaptor
Pour les lecteurs allemands chapitre trois "Pattern-Matching-Algorithmen für einfache Chaînes" de "Algorithmen auf Sequenzen" pourrait être intéressant. L'auteur est Prof. Dr Sven Rahmann, Lehrstuhl XI, Fakultät für Informatik, TU Dortmund. Tous les algorithmes ont Python exemples.