Forum Programmation.autre Expressions régulières: votre avis...

Posté par Moonz le 14 août 2006 à 11:22.

Étiquettes : aucune

août

2006

Bonjour les moules :). Si parmi vous il y a des fanatiques des expressions régulières, je vous serais très reconnaissant de me donner votre avis :)

Note: je ne demande pas "comment faire" mais "quelle est la meilleure manière de faire". J'aimerais donc, si possible, l'avis de quelqu'un qui s'y connait assez en expressions régulières pour pouvoir écrire son propre moteur d'expressions régulières. Si vous ne savez pas ce qu'est qu'un opérateur possessif ou un "look-behind" (désolé, j'ai oublié le nom français ;)), merci de passer votre chemin...

Ma question est toute conne: On m'a très souvent dit, redit et re-redit que les .* (ou .+) non avides, spa bien. On me dit que par exemple, au lieu de faire:
H.*?o
Il fallait faire:
H[^o]*o
Ma question est: pourquoi ?

Question subsdidiaire (j'ai du écorcher ce mot...):
Est-ce que remplacer <p.*?>.+? par <p[^>]*>(?:(?!).)+ est une bonne manière de faire ? y a t'il encore une meilleure manière de faire ?

Allez, une dernière pour la route: comment on fait les groupements atomiques et les quantificateurs possessifs en python? j'ai pas trouvé dans la doc...

# meuh

Posté par gc (site web personnel) le 14 août 2006 à 13:15. Évalué à 2.

l'avis de quelqu'un qui s'y connait assez en expressions régulières pour pouvoir écrire son propre moteur d'expressions régulières

t'es vraiment vraiment vraaaiment sûr que t'es au bon endroit ?
- [^] # Re: meuh
  
  Posté par Moonz le 14 août 2006 à 17:39. Évalué à 2.
  
  C'est vrai que j'ai longtemps hésité avec programmation.perl
  Hop ----->[]
# Désolé, j'ai oublié le nom anglais

Posté par tripa le 14 août 2006 à 13:40. Évalué à 1.

Qu'appelles-tu un "opérateur possessif"?
- [^] # Re: Désolé, j'ai oublié le nom anglais
  
  Posté par rangzen (site web personnel) le 14 août 2006 à 13:51. Évalué à 4.
  
  AOL
  - [^] # Re: Désolé, j'ai oublié le nom anglais
    
    Posté par tripa le 14 août 2006 à 14:00. Évalué à 1.
    
    C'est nul. :-D
    
    [+]
- [^] # Re: Désolé, j'ai oublié le nom anglais
  
  Posté par Moonz le 14 août 2006 à 17:39. Évalué à 2.
  
  s/opérateur/quantificateur/ (oui, je sais, j'aurais dû me relire plus sérieusement q'un rapide coup d'oeil)
  C'est un quantificateur qui ne rend jamais ce qu'il a consommé (d'où le nom ;)), même quand ça peut faire échouer la reconnaissance... (++, *+ et ?+ en Perl/PCRE)
  http://www.regular-expressions.info/atomic.html
# je me lance...

Posté par deadbeef le 14 août 2006 à 14:12. Évalué à 5.

Je ne sais pas ce que tu appelles "opérateur possessif", mais je vais quand même essayer de répondre (parce que je sais écrire un moteur de regexp :-)).

C'est assez simple en fait, une moteur d'expression régulière est un automate déterministe qui va simplement s'appliquer à parcourir un automate. La seule difficulté d'un tel automate est de résoudre les ambiguïtés qui l'obligent soit à "backtracker", c'est-à-dire à revenir en arrière sur l'automate, soit à gérer les différents parcours possibles en parallèle.

Lorsqu'il existe des ambiguités, d'une part le moteur est forcé de choisir entre :
- prendre le matching le plus court dans la chaine à parcourir
- prendre le matching le plus long dans la chaine à parcourir

Comme il n'existe pas toujours de syntaxe permettant de le préciser (souvent c'est un paramètre optionnel donné au moteur), il existe toujours une possibilité pour que ça ne corresponde pas à ce que veut l'utilisateur.

Reprenons le cas que tu donnes. D'abord, tes deux expressions ne sont pas équivalentes. Soit, par exemple "Hooaioo".

Les matchs partiels possibles sont:
"Hoo" (H.*?o et H[^o]*o)
"Hooaio" (H.*?o uniquement)
"Hooaioo" (H.*?o uniquement)

Maintenant, compliquons un peu l'exemple, testons-le avec l'expression (H.*o.*o). Il existe alors plusieurs matchs possibles:
- H + [vide] + o + oaio + o
- H + o + o + aio + o
- H + ooai + o + [vide] + o
- etc

La question pour le moteur est alors: laquelle choisir ? Soit le moteur est simple, et il prend la première qu'il trouve (en fonction de son implémentation), soit il est plus compliqué et va choisir celle qui favorise le match le plus long ou le plus court (dans le cas du matching partiel de l'exemple d'avant).

Dans ton exemple, je ne dirais pas que l'une des expression est meilleure que l'autre en soi, mais plutôt qu'elles ne matchent pas les mêmes chaines, l'une étant plus puissante (au sens puissance génératrice) donc plus complexe à parcourir. Mais ça n'est un problème que si le temps d'exécution est critique.

Autrement, le problème classique est d'utiliser une expression qui ne soit pas plus puissante que ce que tu veux parser (car ça peut laisser passer des choses non-valides, ce qui peut --ou pas-- être un problème), mais qui le soit suffisamment pour ne pas rejeter une chaine valide (car là c'est toujours un problème).

En règle générale, si tu évites les ambiguités de parcours, c'est toujours plus rapide. Typiquement, une expression telle que "aa*b" va systématiquement obliger le moteur à faire un choix, ce qui n'est jamais bon, il vaut toujours mieux mettre "a+b" qui n'est pas ambigu.

Pour ta question subsidiaire, la réponse est OUI et NON :-)

- d'abords, avec deux opérateurs possiblement vides à la suite (.* et ?) c'est sûr que tu facilites pas le travail du moteur, donc plutôt préférer tout simplement "<p.*>"

- ensuite OUI, car "<p[^>]*>" sera toujours moins ambigu que "<p.*?>", ce qui est BIEN, d'autant que "<p.*?>" peut aussi matcher la chaine "toto" (avec .* = ">toto<p")

- mais peut-être que NON, car "<p[^>]*>" ne matchera pas comme tu le souhaites une chaine (non valide xhtml, je le reconnais, mais qui passe en html) telle que "'>".

Donc ça dépend ce que tu veux parser. Un autre problème majeur des expressions régulières, comme tu le vois, c'est qu'on en arrive vite au bout, et qu''il faut ensuite passer aux vraies grammaires, qui sont plus compliquées à mettre en oeuvre.
- [^] # Re: je me lance...
 
 Posté par Moonz le 14 août 2006 à 17:38. Évalué à 2.
 
 Je pense que tu n'a pas bien compris ma question, et je pense avoir pigé pourquoi:
 
 > d'abords, avec deux opérateurs possiblement vides à la suite (.* et ?) c'est sûr que tu facilites pas le travail du moteur, donc plutôt préférer tout simplement "<p.*>"
 
 Donc mea culpa, j'aurais du préciser la syntaxe en introductionr: j'utilise la syntaxe Perl/PCRE. C'est à dire que .*? est la version paresseuse de .* et pas équivalent à (.*)?
 
 > Reprenons le cas que tu donnes. D'abord, tes deux expressions ne sont pas équivalentes.
 Je me met dans le cas où l'opérateur paresseux n'a pas besoin de consommer un "o" pour que la reconnaissance réussisse. Dans ce cas, je suppose quand les expressions sont à peu de choses près équivalentes... non ?
 
 Ma question était donc: dans le cas où l'opérateur paresseux n'a pas besoin de consommer 'o' et où la reconnaissance réussit, utiliser H[^o]*o est-il vraiment plus avantageux que H.*?o ? Je n'ai pas l'impression que le moteur ait beaucoup plus de choix à faire dans la deuxième version...
 - [^] # Re: je me lance...
 
 Posté par deadbeef le 14 août 2006 à 20:29. Évalué à 3.
 
 Ha ok, je ne connaissais pas cette variante syntaxique.
 
 Pour répondre à ta question, il faut que tu te figures comment fonctionne un automate: en gros un ensembre d'états reliés entre eux par des chemins (les "transitions").
 
 H[^o]*o est avantageux parce qu'il se résume au graphe suivant:
 
 [H] -> [tout sauf o] -> [o] -> FIN \-> [o] -> FIN
 
 H.*o lui, se fait ainsi:
 
 [H] -> [tout, y compris o] -> o -> FIN \-> [o] -> FIN
 Autrement dit, dans le premier cas, on a un automate déterministe (DFA), et dans le second cas on a un automate non-déterministe (NFA). La différence entre les deux, c'est que dans le cas du DFA, quand on est dans un état donné, il n'y a jamais deux transitions possible pour un même symbole en entrée (disons une lettre dans notre cas). Ca peut sembler pas grand chose, mais au niveau de l'implémentation et de la complexité, ça n'a rien à voir.
 
 En effet, le parcours d'un automate DFA est par nature beaucoup plus rapide qu'un automate NFA parce que le premier peut s'effectuer en une seule passe et sans backtrack, alors que dans le second cas il faut soit le convertir en DFA (mais ça peut engendrer des DFA monstrueux, et ce n'est pas toujours envisageable), soit avoir un moteur NFA (qui backtracke ou qui parcourt en parallèle si on est riche en RAM), qui sont toujours (beaucoup) plus complexe et plus lent qu'un moteur DFA.
 
 Evidemment, dans le cas de H.*o, si la chaine en entrée est pas trop grande, tu ne verras pas la différence en terme de traitement derrière, mais il n'empêche que le traitement que cela implique est "par nature" plus important.
 
 Si tu veux les maths derrière tout ça:
 http://en.wikipedia.org/wiki/Deterministic_finite_state_mach(...)
 http://en.wikipedia.org/wiki/Nondeterministic_finite_state_m(...)
 - [^] # Re: je me lance...
 
 Posté par Moonz le 15 août 2006 à 12:55. Évalué à 2.
 
 Les deux graphes ne semblent pas bien différent ;)
 Mais je pense avoir compris l'idée... Merci beaucoup pour tes explications ;)
# txt2regex

Posté par B16F4RV4RD1N le 14 août 2006 à 14:58. Évalué à 2.

je ne sais pas si je suis h.s. ou pas, j'ai pas compris grand chose à ton message.

Mais j'ai trouvé il y a peu un programme pour faciliter l'écriture des expressions régutières. Le gars a déjà écrit tout un bouquin sur le sujet, je pense qu'il sait de quoi il parle :

http://txt2regex.sourceforge.net/
Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.