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 "<p>toto<p>" (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 "<p align='>'>".
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.
# je me lance...
Posté par deadbeef . En réponse au message Expressions régulières: votre avis.... Évalué à 5.
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 "<p>toto<p>" (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 "<p align='>'>".
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.