tre
TRE 0.9.0
Ce projet est à la recherche de mainteneurs. Pour commencer, il y a quelques demandes de traction en attente d'examen.
Faites-moi savoir à [email protected] si vous souhaitez intensifier!
TRE est une bibliothèque de correspondance regexp légère, robuste et efficace, conforme à la POSIX avec des fonctionnalités passionnantes telles que l'appariement approximatif (flou).
L'algorithme de correspondance utilisé dans TRE utilise le temps du pire des cas linéaires dans la longueur de la recherche du texte et le pire des cas quadratiques dans la longueur de l'expression régulière utilisée.
En d'autres termes, la complexité du temps de l'algorithme est O (m ^ 2n), où m est la longueur de l'expression régulière et n est la longueur du texte. L'espace utilisé est également quadratique sur la longueur du regex, mais ne dépend pas de la chaîne recherchée. Ce comportement quadratique ne se produit que sur des cas pathologiques qui sont probablement très rares dans la pratique.
Voici comment travailler avec ce code.
Vous aurez besoin des outils suivants installés sur votre système:
Premièrement, préparez l'arbre. Passer à la racine du répertoire source et exécuter
./utils/autogen.sh
Cela régénérera diverses choses en utilisant les outils préalables afin de vous retrouver avec un arbre à constructeur.
Après cela, vous pouvez exécuter le script de configuration et créer TRE comme d'habitude:
./configure
make
make check
make install
Dans un arbre préparé, cette commande crée un code source Tarball:
./configure && make dist
Alternativement, vous pouvez courir
./utils/build-sources.sh
qui construit les packages de code source et les place dans le sous-répertoire dist . Ce script a besoin d'une commande zip fonctionne.
Tre n'est pas encore un autre correspondant regexp. TRE a certaines fonctionnalités qui ne sont pas là dans la plupart des implémentations compatibles POSIX gratuites. La plupart de ces fonctionnalités ne sont pas non plus présentes dans des implémentations non libres, d'ailleurs.
La correspondance approximative des modèles permet d'approximation des correspondances, ce qui permet aux correspondances d'être proches du modèle recherché sous une certaine proximité. TRE utilise la mesure d'édition (également connue sous le nom de distance de Levenshtein) où les caractères peuvent être insérés, supprimés ou substitués dans le texte recherché afin d'obtenir une correspondance exacte.
Chaque insertion, suppression ou substitution ajoute la distance ou le coût du match. TRE peut signaler les correspondances qui ont un coût inférieur à une valeur de seuil donnée. TRE peut également être utilisé pour rechercher des correspondances avec le coût le plus bas.
TRE comprend une version de l'outil de ligne de commande ANGP (approximatif Grep) pour une correspondance regexp approximative dans le style de Grep. Contrairement aux autres implémentations AGGN (comme celle de Sun Wu et Udi Manber de l'Université de l'Arizona) Tre ACGP permet à tous les regents de toute durée, de n'importe quel nombre d'erreurs et des coûts non uniformes d'insertion, de suppression et de substitution.
POSIX définit précisément le comportement des fonctions regexp. TRE tente de se conformer à ces spécifications aussi strictement que possible. TRE renvoie toujours les correspondances correctes pour les sous-bassins, par exemple. Très peu d'autres implémentations le font correctement. En fait, les seules autres implémentations en plus de Tre que je connais (gratuites ou non) qui obtiennent les choses correctement sont RX par Tom Lord, Regex ++ par John Maddock et l'AT&T AST Regex par Glenn Fowler et Doug McIlroy.
Le TRE standard essaie de se conformer à l'IEEE STD 1003.1-2001, ou des spécifications de base de groupe ouvertes 6, communément appelées «POSIX». Les parties pertinentes sont les spécifications de base sur les expressions régulières (et la justification) et la description de l'API regcomp() .
Pour une excellente enquête sur POSIX Regexp Matchers, voir les pages TestRegex de Glenn Fowler d'AT&T Labs Research.
En raison de l'algorithme de correspondance utilisé dans TRE, le temps maximum consommé par tout appel regexec() est toujours directement proportionnel à la longueur de la chaîne recherchée. Il y a une exception: si des références de dos sont utilisées, la correspondance peut prendre du temps qui augmente de façon exponentielle avec la longueur de la chaîne. En effet, faire correspondre les références de retour est un problème complet NP, et nécessite presque certainement du temps exponentiel pour correspondre dans le pire des cas.
Un appel regexec() n'allouait jamais la mémoire du tas. TRE alloue toute la mémoire dont il a besoin lors d'un appel regcomp() , et un espace de travail temporaire de la trame de pile pour la durée de l'appel regexec() . La quantité d'espace temporaire nécessaire est constante pendant la correspondance et ne dépend pas de la chaîne recherchée. Pour les regexps de taille raisonnable, TRE nécessite moins de 50k de mémoire allouée dynamiquement pendant l'appel regcomp() , moins de 20k pour le tampon de motif compilé et moins de deux kilo-kilo-espaces temporaires de la trame de pile lors d'un appel regexec() . Il n'y a pas de compromis de temps / mémoire. Tre est également petite en taille de code; La liaison statiquement avec TRE augmente la taille exécutable inférieure à 30K (GCC-3.2, x86, GNU / Linux).
TRE prend en charge les jeux de caractères multi -yte. Cela permet d'utiliser les regexps de manière transparente avec, par exemple, des lieux japonais. TRE fournit également une API de caractère large.
TRE fournit des API qui permettent des caractères zéro binaires à la fois dans les regexps et les chaînes recherchées. L'API standard ne peut pas être facilement utilisée pour, par exemple, rechercher des mots imprimables à partir de données binaires (bien qu'elle soit possible avec un certain piratage). La recherche de modèles contenant des zéros binaires incorporés n'est pas du tout possible avec l'API standard.
Tre est complètement sûr. Toutes les fonctions exportées sont rentrées et un seul objet regexp compilé peut être utilisé simultanément dans plusieurs contextes; EG dans main() et un gestionnaire de signaux, ou dans de nombreux threads d'une application multithread.
TRE est portable sur plusieurs plates-formes. Vous trouverez ci-dessous un tableau des plates-formes et des compilateurs utilisés pour développer et tester TRE:
| Plate-forme | Compilateur |
|---|---|
| FreeBSD 14.1 | Clang 18 |
| Ubuntu 22.04 | GCC 11 |
| macOS 14.6 | Clang 14 |
| Windows 11 | Microsoft Visual Studio 2022 |
TRE devrait compiler sans modifications sur la plupart des plates-formes de type POSIX modernes et être facilement portable sur n'importe quelle plate-forme avec une implémentation C hébergée.
Selon la plate-forme, vous devrez peut-être installer LiButf8 pour obtenir une prise en charge de jeu de caractères de caractère et de caractères multi-monte.
TRE est libéré sous une licence qui est essentiellement la même que la licence de style BSD «Clause» utilisée dans NetBSD. Voir la licence de fichier pour plus de détails.
Il y a actuellement deux fonctionnalités, toutes deux liées aux éléments de collation, manquantes à partir de la conformité à 100% POSIX. Ce sont:
Prise en charge des éléments de collation (par exemple [[.<X>.]] , Où <X> est un élément de collation). Il n'est pas possible de prendre en charge les éléments de collation à plusieurs caractères portable, car POSIX ne définit pas un moyen de déterminer si une séquence de caractères est un élément de collation à plusieurs caractères ou non.
Prise en charge des classes d'équivalence, par exemple [[=<X>=]] , où <X> est un élément de collation. Une classe d'équivalence correspond à tout caractère qui a le même poids de collation primaire que <X> . Encore une fois, POSIX ne fournit aucun mécanisme portable pour déterminer le poids de collation primaire d'un élément de collation.
Notez que d'autres implémentations RegexP portables ne prennent pas non plus en charge les éléments de collation. La seule exception est Regex ++, qui est livrée avec sa propre base de données pour la collation d'éléments pour différents lieux. La prise en charge des éléments de collation et des classes d'équivalence n'a pas été largement demandée et n'est pas très élevée sur la liste des TODO pour le moment.
Ce sont d'autres fonctionnalités que je prévois de mettre en œuvre très bientôt:
Toutes les extensions GNU manquantes activées dans GNU Regex, telles que [[:<:]] et [[:>:]] .
Un drapeau REG_SHORTEST regexec() pour renvoyer la correspondance la plus courte au lieu de la correspondance la plus longue.
Syntaxe compatible perl:
[:^class:] correspond à tout sauf aux personnages en classe. Notez que [^[:class:]] fonctionne déjà, ce ne serait qu'un sténographie de commodité.
A correspondance uniquement au début de la chaîne.
Z ne correspond qu'à la fin de la chaîne, ou avant Newline à la fin.
z correspond uniquement à la fin de la chaîne.
l minuscules charbons suivants (pensez à VI).
u Uppercase Next Char (pensez à VI).
L minuscules jusqu'à E (pensez à VI).
U maîtrise jusqu'à E (pensez à VI).
(?=pattern) Affaires de sosie positive zéro-largeur.
(?!pattern) Affirmations de sosie négatives zéro-largeur.
(?<=pattern) Affaires de look positif zéro-largeur.
(?<!pattern) Affaires de look négatifs zéro-largeur.
La documentation en particulier pour les fonctionnalités non standard de TRE, comme la correspondance approximative, est un travail en cours (avec «progrès» défini de manière lâche ...) Si vous souhaitez trouver une extension à utiliser, en lisant l'en-tête include/tre/tre.h pourrait fournir quelques conseils supplémentaires si vous êtes à l'aise avec le code source C.
