Java regex meurt sur débordement de pile: besoin d'une meilleure version

Question

Je travaille sur un JMD (Java MarkDown) (un port Java de MarkDownSharp) mais j'ai un problème avec une regex en particulier. Pour le fichier Markdown_Documentation_Syntax.text cette expression régulière meurt:

private static final String BLOCK_TAGS_1 = "p|div|h[1-6]|blockquote|pre|table|dl|ol|ul|script|noscript|form|fieldset|iframe|math|ins|del"; 
private static final String BLOCKS_NESTED_PATTERN = String.format("" + 
     "(" +      // save in $1 
     "^" +      // start of line (with MULTILINE) 
     "<(%s)" +     // start tag = $2 
     "\\b" +     // word break 
     "(.*\\n)*?" +    // any number of lines, minimally matching 
     "</\\2>" +     // the matching end tag 
     "[ \\t]*" +    // trailing spaces/tags 
     "(?=\\n+|\\Z)" +   // followed by a newline or end of 
     ")", BLOCK_TAGS_1); 

qui se traduit par:

(^<(p|div|h[1-6]|blockquote|pre|table|dl|ol|ul|script|noscript|form|fieldset|iframe|math|ins|del)\b(.*\n)*?</\2>[ \t]*(?=\n+|\Z)) 

Ce modèle est à la recherche des balises de bloc acceptées qui sont fixés au début d'une ligne, suivi par un certain nombre de lignes, puis sont terminées par une balise correspondante suivie d'un retour à la ligne ou d'une terminaison de chaîne. Cela génère:

java.lang.StackOverflowError 
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168) 
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227) 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366) 
    at java.util.regex.Pattern$Curly.match0(Pattern.java:3782) 
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168) 
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357) 
     ... 

Cela peut être traitée en augmentant l'espace de pile pour Java (defaults 128k/400k pour oss/ss IIRC), mais l'expression ci-dessus est lent de toute façon. Donc, je suis à la recherche d'un gourou regex qui peut faire mieux (ou au moins expliquer le problème de performance avec ce modèle). La version C# est un peu lente mais fonctionne bien. PHP semble n'avoir aucun problème avec ça non plus.

Édition: Il s'agit de JDK6u17 exécuté sous Windows 7 64 Édition Intégrale.

Answer 1

Cette partie:

(.*\n)*? 

implique beaucoup de retours en arrière inutile en raison de la * imbriquée et car il y a les caractères qui doivent correspondre à la suite.

Je viens de rencontrer une référence rapide en Perl sur certaines chaînes arbitraires et a obtenu une amélioration de 13-15% juste en passant cette pièce à

(?>.*\n)*? 

qui ne capture pas, indépendante sous-groupement. Cela vous donne deux avantages, il ne perd plus de temps à capturer la chaîne correspondante, et plus important encore, il ne fait plus marche arrière sur le .* qui est une perte de temps de toute façon. Il n'y a aucun moyen que seule une partie de cela. * Aboutisse à un match valide, ce qui signifie explicitement que tout ou rien ne devrait aider.

Je ne sais pas si c'est une amélioration suffisante dans ce cas, cependant.

Answer 2

Bien que l'amélioration du modèle soit utile et utile, Java Matcher est récursif et il est généralement préférable de passer à une solution itérative.

Lorsque j'ai eu des problèmes similaires, je suis passé à jregex (http://jregex.sourceforge.net/) et cela a fonctionné pour moi.

La correspondance de modèle peut avoir réussi maintenant avec la solution améliorée, mais elle peut échouer si un texte 10 fois plus grand a été donné.

PS: Désolé pour necromancing un vieux sujet, mais ce fil est classé très sur Google et il bénéficierait des gens si je le mets ici

Answer 3

Le sous-expression: "(.*\\n)*?" (et la version de réponse améliorée acceptée: "(?>.*\n)*?") , les deux ont un problème: ils ne correspondent pas à un élément de bloc écrit sur une ligne.En d'autres termes, ils ne correspondent pas ceci:

<div>one-liner</div> 

Si ce n'est pas le comportement souhaité, un bon (et beaucoup plus efficace) solution consiste à utiliser simplement:

.*?

Et tour en mode simple ligne.