Correspondance la plus performante de "tous les caractères"

8

Sur https://www.emacswiki.org/emacs/MultilineRegexp on trouve l'indice à utiliser

[\ 0- \ 377 [: nonascii:]] * \ n

au lieu de la norme

. * \ n

pour faire correspondre n'importe quel caractère jusqu'à une nouvelle ligne pour éviter le débordement de pile pour les textes volumineux (37 Ko). Le débordement est-il le problème ici, ou une exécution correspondante pour le premier est-elle également plus performante que la seconde?

regular-expressions Vroomfondel
la source

Réponses:

9

Dans les expressions rationnelles d'Emacs, .ne correspond pas à tous les personnages. C'est un synonyme de [^\n]. Donc, la raison de l'utilisation [\0-\377[:nonascii:]]est lorsque vous voulez faire correspondre "n'importe quel caractère, même une nouvelle ligne".

Wrt débordant de la pile, .*\ndoit être manipulé très efficacement, c'est-à-dire sans retour en arrière et sans manger la pile. Au contraire, il [\0-\377[:nonascii:]]*\nest géré de manière plutôt inefficace par le moteur d'expression rationnelle d'Emacs car il consommera un peu de la pile pour chaque caractère correspondant, donc sur les textes "énormes", il aura tendance à déborder de la pile.

Notez que l'emacswiki suggère [\0-\377[:nonascii:]]*et non [\0-\377[:nonascii:]]*\n.

Stefan
la source
Merci pour la clarification. Cependant, pour le débordement de pile, êtes-vous sûr que [\ 0- \ 377 [: nonascii:]] * \ n provoquera un débordement? C'est le contraire de ce que prétend le wiki. Est-ce le bcs du \ n à la fin? À quoi servirait alors un modèle comme [\ 0- \ 377 [: nonascii:]] * sans caractère de fin?
Vroomfondel
Toute expression rationnelle qui correspond à «n'importe quoi» consommera de l'espace de pile (avec le moteur d'expression rationnelle d'Emacs, je veux dire), et je ne vois pas pourquoi le [\0-\377[:nonascii:]]*ferait moins alors \\(.\\|\n\\)*. Je pense donc que l'emacswiki a tort sur celui-ci.
Stefan
Y a-t-il un moyen (ou n'importe qui) de clarifier cette question avec autorité?
Vroomfondel
@Vroomfondel testez-le et voyez. Je peux imaginer que l'expression rationnelle avec |pourrait avoir besoin de plus de backtracking, mais si cela dépend de la façon dont il est compilé.
npostavs
3
Cela n'est vrai que si l'expression rationnelle se termine par [\0-\377[:nonascii:]]*(ce qui est plutôt inhabituel, car vous pourriez aussi bien l'utiliser point-maxplutôt que de la rechercher via une telle expression rationnelle) (pour les curieux: le nœud du problème est de savoir si l'ensemble de caractères pouvant correspondre après que le * est disjoint de l'ensemble de caractères qui peut correspondre dans le *. S'il est disjoint, le moteur d'expression régulière sautera l'enregistrement des étapes intermédiaires et évitera donc de consommer de l'espace de pile. Donc .*\n, [^a]*ane consommez pas la pile, alors que .*aEst-ce que).
Stefan