Les expressions régulières peuvent-elles être utilisées pour faire correspondre des motifs imbriqués ?

Question

Est-il possible d'écrire une expression régulière qui correspond à un motif imbriqué qui apparaît un nombre inconnu de fois ? Par exemple, une expression régulière peut-elle faire correspondre une accolade ouvrante et une accolade fermante lorsqu'il existe un nombre inconnu d'accolades ouvrantes/fermantes imbriquées dans les accolades extérieures ?

Par exemple :

public MyMethod()
{
  if (test)
  {
    // More { }
  }

  // More { }
} // End

Devrait correspondre :

{
  if (test)
  {
    // More { }
  }

  // More { }
}

Answer 1

OUI

...en supposant qu'il existe un nombre maximum de nids auquel vous seriez heureux de vous arrêter.

Laissez-moi vous expliquer.

---

@torsten-marek a raison de dire qu'une expression régulière ne peut pas vérifier les motifs imbriqués comme celui-ci, MAIS il est possible de définir un modèle de regex imbriqué qui vous permettra de capturer des structures imbriquées comme ceci jusqu'à une certaine profondeur maximale . J'en ai créé un pour capturer Style EBNF commentaires ( Essayez-le ici ), comme :

(* This is a comment (* this is nested inside (* another level! *) hey *) yo *)

La regex (pour les commentaires à profondeur unique) est la suivante :

m{1} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+

Vous pouvez facilement l'adapter à vos besoins en remplaçant l'option \(+\*+ y \*+\)+ con { y } et en remplaçant tout ce qui se trouve entre les deux par un simple [^{}] :

p{1} = \{(?:[^{}])*\}

( Voici le lien pour essayer cela).

Pour imbriquer, il suffit de laisser ce motif dans le bloc lui-même :

p{2} = \{(?:(?:p{1})|(?:[^{}]))*\}
  ...or...
p{2} = \{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\}

Pour trouver des blocs à triple encastrement, utilisez :

p{3} = \{(?:(?:p{2})|(?:[^{}]))*\}
  ...or...
p{3} = \{(?:(?:\{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\})|(?:[^{}]))*\}

Un schéma clair est apparu. Pour trouver des commentaires imbriqués à une profondeur de N il suffit d'utiliser l'expression rationnelle :

p{N} = \{(?:(?:p{N-1})|(?:[^{}]))*\}

  where N > 1 and
  p{1} = \{(?:[^{}])*\}

Un script pourrait être écrit pour générer récursivement ces regex, mais cela dépasse le cadre de ce dont j'ai besoin. (Ceci est laissé comme un exercice pour le lecteur.

Answer 2

L'utilisation de la correspondance récursive dans le moteur regex de PHP est massivement plus rapide que la correspondance procédurale des parenthèses. e

http://php.net/manual/en/regexp.reference.recursive.php

par exemple

$patt = '!\( (?: (?: (?>[^()]+) | (?R) )* ) \)!x';

preg_match_all( $patt, $str, $m );

vs.

matchBrackets( $str );

function matchBrackets ( $str, $offset = 0 ) {

    $matches = array();

    list( $opener, $closer ) = array( '(', ')' );

    // Return early if there's no match
    if ( false === ( $first_offset = strpos( $str, $opener, $offset ) ) ) {
        return $matches;
    }

    // Step through the string one character at a time storing offsets
    $paren_score = -1;
    $inside_paren = false;
    $match_start = 0;
    $offsets = array();

    for ( $index = $first_offset; $index < strlen( $str ); $index++ ) {
        $char = $str[ $index ];

        if ( $opener === $char ) {
            if ( ! $inside_paren ) {
                $paren_score = 1;
                $match_start = $index;
            }
            else {
                $paren_score++;
            }
            $inside_paren = true;
        }
        elseif ( $closer === $char ) {
            $paren_score--;
        }

        if ( 0 === $paren_score ) {
            $inside_paren = false;
            $paren_score = -1;
            $offsets[] = array( $match_start, $index + 1 );
        }
    }

    while ( $offset = array_shift( $offsets ) ) {

        list( $start, $finish ) = $offset;

        $match = substr( $str, $start, $finish - $start );
        $matches[] = $match;
    }

    return $matches;
}

Answer 3

Comme zsolt l'a mentionné, certains moteurs regex supportent la récursion -- bien sûr, ce sont typiquement ceux qui utilisent un algorithme de retour en arrière, donc ce ne sera pas particulièrement efficace. exemple : /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

Answer 4

Non, vous entrez dans le domaine du Grammaires libres de contexte à ce moment-là.

Answer 5

Cela semble fonctionner : /(\{(?:\{.*\}|[^\{])*\})/m