perlreguts - En ligne dans le Cloud

PROGRAMME:

Nom

perlreguts - Description du moteur d'expressions régulières Perl.

DESCRIPTION

Ce document est une tentative de faire la lumière sur les entrailles du moteur regex et comment il
travaux. Le moteur regex représente une partie importante de la base de code perl, mais est
relativement mal compris. Ce document n'est qu'une maigre tentative d'aborder ce
situation. Il est dérivé de l'expérience de l'auteur, des commentaires dans le code source, d'autres
des articles sur le moteur regex, des retours sur la liste de diffusion perl5-porters, et sans aucun doute d'autres
lieux aussi.

AVIS! Il doit être clairement compris que le comportement et les structures discutés dans ce
représente l'état du moteur tel que l'auteur l'a compris au moment de la rédaction. Ce
is ne pas une définition d'API, c'est purement un guide interne pour ceux qui veulent pirater le
moteur regex, ou comprendre comment fonctionne le moteur regex. Les lecteurs de ce document sont
devrait comprendre la syntaxe regex de perl et son utilisation en détail. Si tu veux apprendre
sur les bases des expressions régulières de Perl, voir perlre. Et si vous voulez remplacer le
moteur regex avec le vôtre, voir perlreapi.

APERÇU

A rapide noter on conditions
Il y a un débat quant à savoir s'il faut dire "regexp" ou "regex". Dans ce document, nous allons
utiliser le terme "regex" à moins qu'il n'y ait une raison particulière de ne pas le faire, auquel cas nous
expliquer pourquoi.

Lorsque nous parlons de regex, nous devons faire la distinction entre leur forme de code source et
leur forme interne. Dans ce document, nous utiliserons le terme « modèle » lorsque nous parlerons de
leur forme textuelle, code source, et le terme "programme" quand on parle de leur
représentation. Ceux-ci correspondent aux termes S-regex et B-regex que Mark Jason Dominus
emploie dans son article sur "Rx" ([1] dans "REFERENCES").

Ce que is a Standard expression moteur?
Un moteur d'expressions régulières est un programme qui prend un ensemble de contraintes spécifiées dans un
mini-langage, puis applique ces contraintes à une chaîne cible et détermine
si la chaîne satisfait ou non les contraintes. Voir perlre pour une définition complète de
la langue.

En termes moins grandioses, la première partie du travail consiste à transformer un modèle en quelque chose que le
l'ordinateur peut efficacement utiliser pour trouver le point correspondant dans la chaîne, et la deuxième partie
effectue la recherche elle-même.

Pour ce faire, nous devons produire un programme en analysant le texte. Nous devons ensuite exécuter le
programme pour trouver le point dans la chaîne qui correspond. Et nous devons tout faire
efficacement.

Structure of a Expression régulière Programme
Haute Niveau

Bien que cela soit un peu déroutant et que certaines personnes s'opposent à la terminologie, cela vaut la peine
en regardant un commentaire qui a été dans expression rationnelle.h pendant des années:

Cette is essentiellement a linéaire codage of a non déterministe état fini click (alias
syntaxe graphiques or "chemin de fer Ordinaire former" in analyse La technologie).

Le terme « forme normale de chemin de fer » est un peu ésotérique, avec « diagramme/tableaux de syntaxe », ou
« diagramme/cartes de chemin de fer » étant des termes plus courants. Néanmoins, il fournit un utile
image mentale d'un programme regex : chaque nœud peut être considéré comme une unité de piste, avec un
entrée unique et dans la plupart des cas un point de sortie unique (il y a des morceaux de voie qui bifurquent,
mais statistiquement peu nombreux), et l'ensemble forme une mise en page avec une seule entrée et une seule
point de sortie. Le processus d'appariement peut être considéré comme une voiture qui se déplace le long de la piste,
l'itinéraire particulier à travers le système étant déterminé par le caractère lu à
chaque point de connexion possible. Une voiture peut tomber de la piste à tout moment, mais elle ne peut
continuer tant qu'il correspond à la piste.

Ainsi, le modèle "/foo(?:\w+|\d+|\s+)bar/" peut être considéré comme le graphique suivant :

[début]
|

|
+-----+-----+
| | |
<\w+> <\d+> <\s+>
| | |
+-----+-----+
|

|
[fin]

La vérité est que les expressions régulières de perl de nos jours sont beaucoup plus
complexe que ce type de structure, mais la visualiser de cette façon peut aider lorsque vous essayez de
prenez vos repères, et cela correspond assez étroitement à la mise en œuvre actuelle.

Pour être plus précis, nous dirons qu'un programme regex est un encodage d'un graphe. Chaque nœud
dans le graphique correspond à une partie du modèle regex d'origine, comme une chaîne littérale
ou une branche, et a un pointeur vers les nœuds représentant le prochain composant à apparier.
Puisque "node" et "opcode" ont déjà d'autres significations dans le source perl, nous appellerons le
nœuds dans un programme regex "regops".

Le programme est représenté par un tableau de structures "regnode", dont une ou plusieurs
représentent un seul regop du programme. Struct "regnode" est la plus petite structure nécessaire,
et a une structure de terrain qui est partagée avec toutes les autres structures plus importantes.

Les pointeurs "suivants" de tous les regops à l'exception de "BRANCH" implémentent la concaténation ; un "suivant"
le pointeur avec une "BRANCHE" à ses deux extrémités relie deux alternatives. [Ici nous avons
l'une des subtiles dépendances syntaxiques : une « BRANCHE » individuelle (par opposition à une collection
d'entre eux) n'est jamais concaténé avec quoi que ce soit en raison de la priorité des opérateurs.]

L'opérande de certains types de regop est une chaîne littérale ; pour d'autres, c'est un regop leader
dans un sous-programme. En particulier, l'opérande d'un nœud « BRANCH » est le premier regop de
la branche.

REMARQUE: Comme le suggère la métaphore du chemin de fer, c'est pas une structure arborescente : la queue du
branche se connecte à la chose suivant l'ensemble des "BRANCH"es. C'est comme une seule ligne
de voie ferrée qui se divise en entrant dans une gare ou une gare de triage et rejoint en
sort de l'autre côté.

Regops

La structure de base d'un regop est définie dans expression rationnelle.h comme suit:

structure regnode {
drapeaux U8 ; /* Diverses fins, parfois outrepassées */
type U8 ; /* Valeur de l'opcode telle que spécifiée par regnodes.h */
U16 next_off ; /* Décalage en taille regnode */
};

D'autres plus grandes structures de type "regnode" sont définies dans regcomp.h. Ils sont presque comme
sous-classes en ce qu'elles ont les mêmes champs que "regnode", avec éventuellement des champs supplémentaires
suivant dans la structure, et dans certains cas la signification spécifique (et le nom) de certains des
les champs de base sont remplacés. Ce qui suit est une description plus complète.

"regnode_1"
"regnode_2"
Les structures "regnode_1" ont le même en-tête, suivi d'un seul argument de quatre octets ;
Les structures "regnode_2" contiennent à la place deux arguments sur deux octets :

regnode_1 U32 arg1 ;
regnode_2 U16 arg1; U16 arg2 ;

"regnode_string"
Les structures "regnode_string", utilisées pour les chaînes littérales, suivent l'en-tête avec un
longueur en octets, puis les données de chaîne. Les chaînes sont remplies à la fin avec zéro octet donc
que la longueur totale du nœud est un multiple de quatre octets :

regnode_string chaîne de caractères[1] ;
U8 str_len; /* remplace les drapeaux */

"regnode_charclass"
Les classes de caractères entre crochets sont représentées par des structures "regnode_charclass", qui
avoir un argument de quatre octets, puis un bitmap de 32 octets (256 bits) indiquant quel
les caractères de la gamme Latin1 sont inclus dans la classe.

regnode_charclass U32 arg1 ;
bitmap de caractères[ANYOF_BITMAP_SIZE] ;

Divers drapeaux dont les noms commencent par "ANYOF_" sont utilisés pour des situations spéciales. Au dessus
Les correspondances Latin1 et les choses inconnues jusqu'à l'exécution sont stockées dans "Perl's pprivate
structure".

"regnode_charclass_posixl"
Il existe également une forme plus grande d'une structure de classe char utilisée pour représenter le caractère POSIX
classes sous "/l" correspondant, appelé "regnode_charclass_posixl" qui a un
Bitmap 32 bits indiquant quelles classes de caractères POSIX ont été incluses.

regnode_charclass_posixl U32 arg1 ;
bitmap de caractères[ANYOF_BITMAP_SIZE] ;
drapeaux de classe U32 ;

regnodes.h définit un tableau appelé "regarglen[]" qui donne la taille de chaque opcode dans
unités de "taille regnode" (4 octets). Une macro est utilisée pour calculer la taille d'un nœud "EXACT"
basé sur son champ "str_len".

Les regops sont définis dans regnodes.h qui est généré à partir regcomp.sym by regcomp.pl.
Actuellement, le nombre maximum possible de regops distincts est limité à 256, avec environ
un quart déjà utilisé.

Un ensemble de macros rend l'accès aux champs plus facile et plus cohérent. Ceux-ci inclus
"OP()", qui est utilisé pour déterminer le type d'une structure de type "regnode" ; "NEXT_OFF()",
qui est le décalage vers le nœud suivant (nous en parlerons plus tard) ; "ARG()", "ARG1()", "ARG2()",
"ARG_SET()", et équivalents pour lire et définir les arguments ; et "STR_LEN()",
"STRING()" et "OPERAND()" pour manipuler les chaînes et les types de roulement regop.

Ce que repop is prochain?

Il existe trois concepts distincts de « suivant » dans le moteur de regex, et il est important de
gardez-les clairs.

· Il y a le « prochain regnode » à partir d'un regnode donné, une valeur qui est rarement utile
sauf que parfois il concorde en valeur avec l'un des autres, et que
parfois, le code suppose qu'il en est toujours ainsi.

· Il y a le " regop suivant " d'un regop/regnode donné. C'est le regop physiquement
situé après le courant, tel que déterminé par la taille du regop courant. C'est
souvent utile, comme lors du vidage de la structure que nous utilisons cet ordre pour traverser.
Parfois, le code suppose que le « prochain regnode » est le même que le « prochain regop », ou
en d'autres termes, suppose que la taille d'un type de regop donné sera toujours un
regnode grand.

· Il y a le "regnext" d'un regop donné. C'est le regop qui est atteint par
sauter en avant par la valeur de "NEXT_OFF()", ou dans quelques cas pour des sauts plus longs par
le champ "arg1" de la structure "regnode_1". Le sous-programme "regnext()" gère cela
de manière transparente. C'est le successeur logique du nœud, qui dans certains cas, comme
celui de la "BRANCH" regop, a une signification particulière.

Processus Aperçu

D'une manière générale, effectuer une correspondance d'une chaîne avec un motif implique les étapes suivantes
étapes:

A. Compilation
1. Analyse de la taille
2. Analyse pour la construction
3. Optimisation et analyse des judas
B. Exécution
4. Position de départ et optimisations sans match
5. Exécution du programme

L'endroit où ces étapes se produisent dans l'exécution réelle d'un programme perl est déterminé par
le modèle implique l'interpolation de toutes les variables de chaîne. Si une interpolation se produit, alors
la compilation se produit au moment de l'exécution. Si ce n'est pas le cas, la compilation est effectuée à la compilation
temps. (Le modificateur "/o" change cela, tout comme "qr//" dans une certaine mesure.) Le moteur
ne s'en soucie pas vraiment.

Compilation
Ce code réside principalement dans regcomp.c, ainsi que les fichiers d'en-tête regcomp.h, expression rationnelle.h
et regnodes.h.

La compilation commence par "pregcomp()", qui est principalement un wrapper d'initialisation qui
fermes s'appuient sur deux autres routines pour le levage de charges lourdes : la première est "reg()", qui est
le point de départ de l'analyse ; le second, "study_chunk()", est responsable de l'optimisation.

L'initialisation dans "pregcomp()" implique principalement la création et le remplissage de données d'un
structure, "RExC_state_t" (définie dans regcomp.c). Presque toutes les routines utilisées en interne dans
regcomp.h prendre un pointeur vers l'une de ces structures comme premier argument, avec le nom
"pRExC_state". Cette structure est utilisée pour stocker l'état de compilation et contient de nombreux
des champs. De même, il existe de nombreuses macros qui opèrent sur cette variable : tout ce qui
comme "RExC_xxxx" est une macro qui opère sur ce pointeur/structure.

Analyse pour Taille

Dans ce passage, le modèle d'entrée est analysé afin de calculer combien d'espace est nécessaire
pour chaque regop que nous aurions besoin d'émettre. La taille est également utilisée pour déterminer si une longue
des sauts seront nécessaires dans le programme.

Cette étape est contrôlée par la définition de la macro "SIZE_ONLY".

L'analyse se déroule à peu près exactement comme pendant la phase de construction, sauf
que la plupart des routines sont court-circuitées pour changer le champ de taille "RExC_size" et ne pas faire
rien d'autre.

Analyse pour construction

Une fois la taille du programme déterminée, le motif est à nouveau analysé, mais cela
le temps pour de vrai. Maintenant, "SIZE_ONLY" sera faux et la construction réelle peut avoir lieu.

"reg()" est le début du processus d'analyse. Il est responsable de l'analyse d'un arbitraire
morceau de motif jusqu'à la fin de la chaîne ou jusqu'à la première parenthèse fermante
rencontres dans le modèle. Cela signifie qu'il peut être utilisé pour analyser la regex de niveau supérieur, ou tout autre
section à l'intérieur d'une parenthèse de regroupement. Il gère également les "parens spéciaux" que perl's
les regex ont. Par exemple, lors de l'analyse de "/x(?:foo)y/" "reg()" sera appelé à un moment donné
pour analyser à partir du "?" jusqu'à et y compris le ")".

De plus, "reg()" est responsable de l'analyse d'une ou plusieurs branches du
motif, et pour les "finir" en définissant correctement leurs prochains pointeurs. En ordre
pour faire l'analyse, il appelle à plusieurs reprises "regbranch()", qui est responsable de
gestion jusqu'au premier "|" symbole qu'il voit.

"regbranch()" appelle à son tour "regpiece()" qui gère les "choses" suivi d'un quantificateur.
Afin d'analyser les "choses", "regatom()" est appelé. C'est la routine de niveau le plus bas,
qui analyse les chaînes constantes, les classes de caractères et les divers symboles spéciaux tels que
"$". Si "regatom()" rencontre un caractère "(", il appelle à son tour "reg()".

La routine "regtail()" est appelée à la fois par "reg()" et "regbranch()" afin de "définir le
pointeur de queue" correctement. Lors de l'exécution et que nous arrivons à la fin d'une branche, nous devons aller
au nœud suivant les parenthèses de regroupement. Lors de l'analyse, cependant, nous ne savons pas où le
la fin sera jusqu'à ce que nous y arrivions, donc quand nous le ferons, nous devons revenir en arrière et mettre à jour les décalages comme
approprié. "regtail" est utilisé pour rendre cela plus facile.

Une subtilité du processus d'analyse signifie qu'une expression régulière comme "/foo/" est à l'origine analysée
en alternance avec une seule branche. Ce n'est qu'après que l'optimiseur
convertit les alternances de branche unique en une forme plus simple.

Parse Appeler Graphique et a Grammaire

Le graphique des appels ressemble à ceci :

reg() # analyse une regex de niveau supérieur, ou à l'intérieur de
# parents
regbranch() # analyse une seule branche d'une alternance
regpiece() # analyse un motif suivi d'un quantificateur
regatom() # analyse un motif simple
regclass() # utilisé pour gérer une classe
reg() # utilisé pour gérer une parenthèse
# sous-modèle
....

regtail() # terminer la branche

regtail() # termine la séquence de branchement. Attachez chacun
# branche de la queue à la queue du
# séquence
# (NOUVEAU) En mode Débogage, c'est
# regtail_study().

Une forme de grammaire pourrait être quelque chose comme ceci :

atome : constant | classer
quantitatif : '*' | '+' | '?' | '{min max}'
_branche : pièce
| pièce _branche
| rien
branche : _branche
| _branche '|' branche
groupe : '('branche ')'
_pièce : atome | grouper
pièce : _pièce
| _quantité de pièce

Analyse complications

L'implication de la description ci-dessus est qu'un modèle contenant des parenthèses imbriquées
entraînera un graphe d'appels qui parcourt "reg()", "regbranch()", "regpiece()",
"regatom()", "reg()", "regbranche()" etc plusieurs fois, jusqu'au niveau le plus profond d'imbrication
est atteint. Toutes les routines ci-dessus renvoient un pointeur vers un "regnode", qui est généralement le
dernier regnode ajouté au programme. Cependant, une complication est que reg() renvoie NULL
pour analyser la syntaxe "(?:)" pour les modificateurs intégrés, en définissant l'indicateur "TRYAGAIN". le
"TRYAGAIN" se propage vers le haut jusqu'à ce qu'il soit capturé, dans certains cas par "regatom()", mais
sinon inconditionnellement par "regbranch()". Par conséquent, il ne sera jamais retourné par
"regbranch()" à "reg()". Ce drapeau permet à des motifs tels que "(?i)+" d'être détectés comme
les erreurs (Quantificateur suit rien in expression régulière ; marqué by <- ICI in m/(?je)+ <- ICI /).

Une autre complication est que la représentation utilisée pour le programme diffère s'il a besoin
pour stocker Unicode, mais il n'est pas toujours possible de savoir avec certitude si c'est le cas jusqu'à
au milieu de l'analyse. La représentation Unicode du programme est plus grande et ne peut pas
être appariés aussi efficacement. (Voir « Prise en charge de l'Unicode et de la localisation » ci-dessous pour plus de détails
pourquoi.) Si le motif contient un Unicode littéral, il est évident que le programme a besoin
pour stocker Unicode. Sinon, l'analyseur suppose avec optimisme que le plus efficace
représentation peut être utilisée, et commence le dimensionnement sur cette base. Cependant, si alors
rencontre quelque chose dans le modèle qui doit être stocké en Unicode, comme un "\x{...}"
séquence d'échappement représentant un caractère littéral, alors cela signifie que tous précédemment
les tailles calculées doivent être refaites, en utilisant des valeurs appropriées pour l'Unicode
représentation. Actuellement, toutes les constructions d'expressions régulières qui peuvent déclencher ceci sont
analysé par le code dans "regatom()".

Pour éviter le gaspillage de travail lorsqu'un redémarrage est nécessaire, la passe de dimensionnement est abandonnée - "regatom()"
renvoie immédiatement NULL, définissant le drapeau "RESTART_UTF8". (Cette action est encapsulée
à l'aide de la macro "REQUIRE_UTF8".) Cette demande de redémarrage est propagée dans la chaîne d'appel dans un
de la même manière, jusqu'à ce qu'il soit "attrapé" dans "Perl_re_op_compile()", qui marque le motif
comme contenant Unicode, et redémarre la passe de dimensionnement. Il est également possible pour les constructions
dans les blocs de code d'exécution pour s'avérer avoir besoin d'une représentation Unicode., qui est
signalé par "S_compile_runtime_code()" retournant false à "Perl_re_op_compile()".

Le redémarrage était auparavant implémenté à l'aide d'un "longjmp" dans "regatom()" en retour à un "setjmp"
dans "Perl_re_op_compile()", mais cela s'est avéré problématique car ce dernier est un grand
fonction contenant de nombreuses variables automatiques, qui interagissent mal avec l'émergent
flux de contrôle de "setjmp".

Déboguer Sortie

Dans la version de développement 5.9.x de perl, vous pouvez "utiliser re Debug => 'PARSE'" pour voir certains
tracer des informations sur le processus d'analyse. Nous allons commencer par quelques modèles simples et
construire des modèles plus complexes.

Ainsi, lorsque nous analysons "/foo/", nous voyons quelque chose comme le tableau suivant. La gauche montre ce qui est
en cours d'analyse, et le nombre indique où irait le prochain regop. Les trucs sur le
à droite se trouve la sortie de trace du graphique. Les noms sont choisis pour être courts pour le rendre moins
dense à l'écran. 'tsdy' est une forme spéciale de "regtail()" qui fait un peu plus
analyse.

>foo< 1 reg
brnc
faire cuire au four
atome
>< 4 tsdy~ EXACT (EXACT) (1)
~ attacher à FIN (3) décalé à 2

Le programme résultant ressemble alors à :

1 : EXACT (3)
3: FIN(0)

Comme vous pouvez le voir, même si nous avons analysé une branche et un morceau, ce n'était finalement qu'un
atome. Le programme final nous montre comment les choses fonctionnent. Nous avons un regop "EXACT", suivi d'un
"FIN" regop. Le nombre entre parenthèses indique où va le "regnext" du nœud. le
"regnext" d'un regop "END" n'est pas utilisé, car les regops "END" signifient que nous avons réussi la correspondance.
Le nombre sur la gauche indique la position du regop dans le tableau regnode.

Essayons maintenant un modèle plus difficile. Nous allons ajouter un quantificateur, nous avons donc maintenant le modèle
"/foo+/". Nous verrons que "regbranch()" appelle "regpiece()" deux fois.

>foo+< 1 reg
brnc
faire cuire au four
atome
>o+< 3 pièces
atome
>< 6 queue~ EXACT (1)
7 jours ~ EXACT (EXACT) (1)
~ PLUS (FIN) (3)
~ attacher à FIN (6) décalé à 3

Et on se retrouve avec le programme :

1 : EXACT (3)
3: PLUS(6)
4: EXACT (0)
6: FIN(0)

Nous avons maintenant un cas particulier. Le regop "EXACT" a un "regnext" de 0. C'est parce que s'il
correspond, il devrait essayer de se correspondre à nouveau. Le regop "PLUS" gère l'échec réel
du regop "EXACT" et agit de manière appropriée (aller au regnode 6 si le "EXACT" correspond à
au moins une fois, ou à défaut si ce n'est pas le cas).

Maintenant, pour quelque chose de beaucoup plus complexe : "/x(?:foo*|b[a][rR])(foo|bar)$/"

>x(?:foo*|b... 1 reg
brnc
faire cuire au four
atome
>(?:foo*|b[... 3 pièces
atome
>?:foo*|b[a... reg
>foo*|b[a][... brnc
faire cuire au four
atome
>o*|b[a][rR... 5 pièces
atome
>|b[a][rR])... 8 queue~ EXACT (3)
>b[a][rR])(... 9 brnc
10 pièces
atome
>[a][rR])(f... 12 pièces
atome
>a][rR])(fo... clas
>[rR])(foo|... 14 queue~ EXACT (10)
faire cuire au four
atome
>rR])(foo|b... classe
>)(foo|bar)... 25 queue~ EXACT (12)
queue ~ BRANCHE (3)
26 tsdy~ BRANCHE (FIN) (9)
~ attacher à la QUEUE (25) décalée à 16
tsdy~ EXACT (EXACT) (4)
~ ETOILE (FIN) (6)
~ attacher à la QUEUE (25) décalée à 19
tsdy~ EXACT (EXACT) (10)
~ EXACT (EXACT) (12)
~ ANYOF[Rr] (FIN) (14)
~ attacher à la QUEUE (25) décalée à 11
>(foo|bar)$< queue~ EXACT (1)
faire cuire au four
atome
>foo|bar)$< reg
28 brnc
faire cuire au four
atome
>|bar)$< 31 queue~ OUVERT1 (26)
>bar)$< brnc
32 pièces
atome
>)$< 34 queue~ BRANCHE (28)
36 tsdy~ BRANCHE (FIN) (31)
~ attacher à CLOSE1 (34) décalé à 3
tsdy~ EXACT (EXACT) (29)
~ attacher à CLOSE1 (34) décalé à 5
tsdy~ EXACT (EXACT) (32)
~ attacher à CLOSE1 (34) décalé à 2
>$< queue~ BRANCHE (3)
~ BRANCHE (9)
~ QUEUE (25)
faire cuire au four
atome
>< 37 queue~ OUVERT1 (26)
~ BRANCHE (28)
~ BRANCHE (31)
~ FERMER1 (34)
38 tsdy ~ EXACT (EXACT) (1)
~ BRANCHE (FIN) (3)
~ BRANCHE (FIN) (9)
~ QUEUE (FIN) (25)
~ OUVERT1 (FIN) (26)
~ BRANCHE (FIN) (28)
~ BRANCHE (FIN) (31)
~ FERMER1 (FIN) (34)
~ EOL (FIN) (36)
~ attacher à FIN (37) décalé à 1

Résultat du programme

1 : EXACT (3)
3: BRANCHE(9)
4 : EXACT (6)
6: STAR(26)
7: EXACT (0)
9: BRANCHE(25)
10 : EXACT (14)
12 : OPTIMISÉ (2 nœuds)
14 : ANYOF[Rr](26)
25: QUEUE(26)
26: OPEN1(28)
28: TRIE-EXACT(34)
[StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf]


30 : OPTIMISÉ (4 nœuds)
34: FERMER1(36)
36: EOL(37)
37: FIN(0)

Ici, nous pouvons voir un programme beaucoup plus complexe, avec diverses optimisations en jeu. À
regnode 10, nous voyons un exemple où une classe de caractères avec un seul caractère était
transformé en un nœud "EXACT". On peut aussi voir où toute une alternance s'est transformée en une
nœud "TRIE-EXACT". En conséquence, certains des regnodes ont été marqués comme optimisés
un moyen. Nous pouvons voir que le symbole "$" a été converti en un regop "EOL", un
morceau de code qui recherche "\n" ou la fin de la chaîne.

Le pointeur suivant pour "BRANCH"es est intéressant en ce qu'il pointe vers où l'exécution devrait
aller si la branche échoue. Lors de l'exécution, si le moteur essaie de passer d'une branche à une
"regnext" qui n'est pas une branche, le moteur saura que l'ensemble des branches
a échoué.

Judas Optimisation et Analyse

Le moteur d'expressions régulières peut être un outil lourd à manier. Sur des cordes longues et complexes
modèles, il peut finir par devoir faire beaucoup de travail pour trouver une correspondance, et encore plus pour décider
qu'aucune correspondance n'est possible. Considérez une situation comme le schéma suivant.

'ababababababababababab' =~ /(a|b)*z/

La partie "(a|b)*" peut correspondre à chaque caractère de la chaîne, puis échouer à chaque fois car
il n'y a pas de "z" dans la chaîne. Donc, évidemment, nous pouvons éviter d'utiliser le moteur regex à moins que
il y a un "z" dans la chaîne. De même dans un modèle comme :

/foo(\w+)bar/

Dans ce cas, nous savons que la chaîne doit contenir un "foo" qui doit être suivi de "bar".
Nous pouvons utiliser la correspondance Fast Boyer-Moore telle qu'implémentée dans "fbm_instr()" pour trouver l'emplacement
de ces chaînes. S'ils n'existent pas, nous n'avons pas besoin de recourir à beaucoup plus
moteur regex coûteux. Mieux encore, s'ils existent, nous pouvons utiliser leurs positions pour
réduire l'espace de recherche que le moteur de regex doit couvrir pour déterminer si l'ensemble
correspondances de motifs.

Différents aspects du modèle peuvent être utilisés pour faciliter les optimisations
le long de ces lignes:

· cordes fixes ancrées

· chaînes fixes flottantes

· exigences de longueur minimale et maximale

· commencer les cours

· Positions de début/fin de ligne

Une autre forme d'optimisation qui peut se produire est l'optimisation "peep-hole" post-analyse,
où les constructions inefficaces sont remplacées par des constructions plus efficaces. Les regops « TAIL »
qui sont utilisés lors de l'analyse pour marquer la fin des branches et la fin des groupes sont
exemples de cela. Ces regops sont utilisés comme espaces réservés pendant la construction et « toujours
match" afin qu'ils puissent être "optimisés" en faisant les choses qui pointent vers le point "TAIL"
à la chose vers laquelle "TAIL" pointe, "sautant" ainsi le nœud.

Une autre optimisation qui peut se produire est celle de la « fusion « EXACTE » », c'est-à-dire où deux
les nœuds "EXACTS" consécutifs sont fusionnés en un seul regop. Une forme encore plus agressive de
c'est qu'une séquence de branches de la forme "EXACT BRANCH ... EXACT" peut être convertie en
un regop "TRIE-EXACT".

Tout cela se passe dans la routine "study_chunk()" qui utilise une structure spéciale
"scan_data_t" pour stocker l'analyse qu'il a effectuée, et fait le "peep-hole"
optimisations au fur et à mesure.

Le code impliqué dans "study_chunk()" est extrêmement cryptique. Fais attention. :-)

Internationaux
L'exécution d'une regex implique généralement deux phases, la première étant la recherche du début
point dans la chaîne d'où nous devons faire correspondre, et le second étant l'exécution du regop
interprète.

Si nous pouvons dire qu'il n'y a pas de point de départ valide, alors nous ne prenons pas la peine d'exécuter le
interprète du tout. De même, si nous savons dès la phase d'analyse que nous ne pouvons pas détecter un
raccourci vers la position de départ, nous allons directement à l'interprète.

Les deux points d'entrée sont "re_intuit_start()" et "pregexec()". Ces routines ont un
relation quelque peu incestueuse avec chevauchement entre leurs fonctions, et "pregexec()"
peut même appeler "re_intuit_start()" tout seul. Néanmoins d'autres parties de la source perl
le code peut appeler l'un ou les deux.

L'exécution de l'interprète lui-même était récursive, mais grâce aux efforts de
Dave Mitchell dans la piste de développement 5.9.x, cela a changé : maintenant une pile interne est
maintenu sur le tas et la routine est entièrement itérative. Cela peut rendre les choses délicates car le
le code est assez conservateur quant à l'état qu'il stocke, avec pour résultat que deux
lignes consécutives dans le code peuvent en fait s'exécuter dans des contextes totalement différents en raison de
la récursivité simulée.

Accueille position et pas de correspondance optimisations

"re_intuit_start()" est responsable de la gestion des points de départ et des optimisations sans correspondance comme
déterminé par les résultats de l'analyse effectuée par "study_chunk()" (et décrit dans "Peep-
Optimisation et analyse des trous").

La structure de base de cette routine est d'essayer de trouver les points de départ et/ou de fin de
où le motif pourrait correspondre, et pour s'assurer que la chaîne est suffisamment longue pour correspondre au
schéma. Il essaie d'utiliser des méthodes plus efficaces plutôt que des méthodes moins efficaces et peut
impliquent un recoupement considérable des contraintes pour trouver la place dans la chaîne qui
allumettes. Par exemple, il peut essayer de déterminer qu'une chaîne fixe donnée doit être non seulement
présent mais un certain nombre de caractères avant la fin de la chaîne, ou autre.

Il appelle plusieurs autres routines, telles que "fbm_instr()" qui fait Fast Boyer Moore
correspondance et "find_byclass()" qui est chargé de trouver le début en utilisant le premier
regop obligatoire dans le programme.

Lorsque les critères d'optimisation sont satisfaits, "reg_try()" est appelé pour effectuer le
correspondre.

Programme efficace

"pregexec()" est le point d'entrée principal pour exécuter une regex. Il contient un support pour
initialiser l'état de l'interpréteur regex, exécuter "re_intuit_start()" si nécessaire, et
exécuter l'interpréteur sur la chaîne à partir de différentes positions de départ selon les besoins. Lorsqu'il est
nécessaire d'utiliser l'interpréteur regex "pregexec()" appelle "regtry()".

"regtry()" est le point d'entrée dans l'interpréteur regex. Il attend comme arguments un
pointeur vers une structure "regmatch_info" et un pointeur vers une chaîne. Il renvoie un entier 1
pour le succès et un 0 pour l'échec. Il s'agit essentiellement d'un wrapper de configuration autour de "regmatch()".

"regmatch" est la "boucle récursive" principale de l'interpréteur. C'est essentiellement un interrupteur géant
instruction qui implémente une machine à états, où les états possibles sont les regops
eux-mêmes, plus un certain nombre d'états intermédiaires et de défaillance supplémentaires. Quelques-uns des
les états sont implémentés en tant que sous-routines mais la majeure partie est du code en ligne.

DIVERS

Unicode et Adresse Assistance
Lorsqu'il s'agit de chaînes contenant des caractères qui ne peuvent pas être représentés à l'aide d'un huit
jeu de caractères binaires, perl utilise une représentation interne qui est une version permissive de
Encodage UTF-8 d'Unicode[2]. Cela utilise des octets uniques pour représenter les caractères de l'ASCII
jeu de caractères et des séquences de deux octets ou plus pour tous les autres caractères. (Voir
perlunitut pour plus d'informations sur la relation entre UTF-8 et l'encodage de perl,
utf8. La différence n'est pas importante pour cette discussion.)

Peu importe comment vous le regardez, la prise en charge d'Unicode va être pénible dans un moteur d'expression régulière.
Les astuces qui pourraient convenir lorsque vous avez 256 caractères possibles ne s'adapteront souvent pas à
gérer la taille du jeu de caractères UTF-8. Ce que vous pouvez prendre pour acquis avec ASCII
peut ne pas être vrai avec Unicode. Par exemple, en ASCII, il est prudent de supposer que
"sizeof(char1) == sizeof(char2)", mais en UTF-8, ce n'est pas le cas. Le pliage de cas Unicode est largement
plus complexe que les simples règles de l'ASCII, et même en n'utilisant pas Unicode mais seulement
encodages localisés sur un seul octet, les choses peuvent devenir délicates (par exemple, LATIN SMALL LETTRE
TRANCHANT S (U+00DF, ss) doit correspondre à 'SS' dans une correspondance localisée insensible à la casse).

Pour aggraver les choses, la prise en charge de l'UTF-8 a été un ajout ultérieur au moteur de regex (car il
était de perl) et cela a forcément rendu les choses beaucoup plus compliquées. C'est évidemment
plus facile de concevoir un moteur de regex avec le support Unicode à l'esprit dès le début qu'il ne l'est
pour le remplacer par celui qui ne l'était pas.

Presque tous les regops qui impliquent de regarder la chaîne d'entrée ont deux cas, un pour UTF-8,
et un non. En fait, c'est souvent plus complexe que cela, car le modèle peut être UTF-8 comme
Hé bien.

Des précautions doivent être prises lorsque vous effectuez des modifications pour vous assurer que vous manipulez correctement UTF-8, à la fois
au moment de la compilation et au moment de l'exécution, y compris lorsque la chaîne et le modèle sont
dépareillé.

Base Ouvrages d'art
La structure "regexp" décrite dans perlreapi est commune à tous les moteurs de regex. Deux de ses
Les champs sont destinés à l'usage privé du moteur regex qui a compilé le modèle.
Ce sont les membres "intflags" et pprivate. Le "pprivate" est un pointeur vide vers un
structure arbitraire dont l'utilisation et la gestion relèvent de la responsabilité du compilateur
moteur. perl ne modifiera jamais aucune de ces valeurs. Dans le cas du moteur d'origine, le
la structure pointée par "pprivate" est appelée "regexp_internal".

Ses champs "pprivate" et "intflags" contiennent des données spécifiques à chaque moteur.

Il existe deux structures utilisées pour stocker une expression régulière compilée. Un, le "regexp"
la structure décrite dans perlreapi est peuplée par le moteur en cours. utilisé et certains
de ses champs lus par perl pour implémenter des choses telles que la chaîne de "qr//".

L'autre structure est pointée par le "pprivate" de la structure "regexp" et est en plus
à "intflags" dans la même structure considérée comme la propriété du moteur de regex qui
compilé l'expression régulière ;

La structure regexp contient toutes les données dont perl doit être conscient pour fonctionner correctement
avec l'expression régulière. Il inclut des données sur les optimisations que perl peut utiliser pour
déterminer si le moteur regex doit vraiment être utilisé, et diverses autres informations de contrôle qui
est nécessaire pour exécuter correctement les modèles dans divers contextes tels que le modèle est ancré
d'une manière ou d'une autre, ou quels indicateurs ont été utilisés lors de la compilation, ou si le programme contient
constructions spéciales dont perl doit être conscient.

De plus, il contient deux champs qui sont destinés à l'usage privé de la regex
moteur qui a compilé le modèle. Ce sont les membres « intflags » et pprivate. le
"pprivate" est un pointeur vide vers une structure arbitraire dont l'utilisation et la gestion est le
responsabilité du moteur de compilation. perl ne modifiera jamais aucune de ces valeurs.

Comme mentionné précédemment, dans le cas des moteurs par défaut, le "pprivate" sera un pointeur
à une structure regexp_internal qui contient le programme compilé et toutes les données supplémentaires
qui est privé à l'implémentation du moteur regex.

De Perl "pprivé" structure

La structure suivante est utilisée comme struct "pprivate" par le moteur regex de perl. Puisqu'il
est spécifique à perl, il n'a qu'une valeur de curiosité pour d'autres implémentations de moteur.

typedef struct regexp_interne {
U32 *décalages ; /* annotations de décalage 20001228 MJD
* données sur le mappage du programme à
* la chaîne*/
regnode *regstclass; /* Startclass optionnelle telle qu'identifiée ou
* construit par l'optimiseur */
struct reg_data *données; /* Données diverses supplémentaires utilisées
* par le programme. Utilisé pour le faire
* plus facile à cloner et libre arbitraire
* les données dont les regops ont besoin. Souvent le
* Le champ ARG d'un regop est un index
* dans cette structure */
programme regnode[1] ; /* Comédie injustifiée avec
* compilateur. */
} regexp_interne ;

"compensations"
Offsets contient un mappage de l'offset dans le "programme" vers l'offset dans la chaîne "precomp".
Ceci n'est utilisé que par le débogueur regex visuel d'ActiveState.

"regstclass"
Regop spécial utilisé par "re_intuit_start()" pour vérifier si un motif peut correspondre à
un certain poste. Par exemple, si le moteur de regex sait que le modèle doit
commencer par un « Z », puis il peut analyser la chaîne jusqu'à ce qu'il en trouve un, puis lancer le
moteur regex à partir de là. La routine qui gère cela s'appelle "find_by_class()".
Parfois, ce champ pointe vers un regop intégré au programme, et parfois il
pointe vers un regop synthétique indépendant qui a été construit par l'optimiseur.

"Les données"
Ce champ pointe vers une structure "reg_data", qui est définie comme suit

structure reg_data {
compte U32 ;
U8 *quoi ;
void* données[1] ;
};

Cette structure est utilisée pour gérer les structures de données dont le moteur de regex a besoin pour
gérer spécialement lors d'un clonage ou d'une opération libre sur le produit compilé. Chaque
élément dans le tableau de données a un élément correspondant dans le tableau what. Pendant
les regops de compilation qui nécessitent des structures spéciales stockées ajouteront un élément à chaque
tableau en utilisant le ajouter_données() routine, puis stockez l'index dans le regop.

"programme"
Programme compilé. Intégré dans la structure afin que l'ensemble de la structure puisse être traité comme un
goutte unique.

Utilisez perlreguts en ligne en utilisant les services onworks.net