Les expressions régulières peuvent-elles être utilisées pour faire correspondre les modèles imbriqués? [dupliquer]

StackOverflow https://stackoverflow.com/questions/133601

  •  02-07-2019
  •  | 
  •  

Question

    

Cette question a déjà une réponse ici:

         

Est-il possible d'écrire une expression régulière qui correspond à un modèle imbriqué qui se produit un nombre inconnu de fois? Par exemple, une expression régulière peut-elle correspondre à une accolade d’ouverture et de fermeture s’il existe un nombre inconnu d’accolades ouverture / fermeture imbriquées dans les accolades extérieures?

Par exemple: 

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

  // More { }
} // End

devrait correspondre: 

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

  // More { }
}
Était-ce utile?

La solution

Non. C'est si facile. Un automate fini (qui est la structure de données sous-jacente à une expression régulière) n'a pas de mémoire en dehors de l'état dans lequel il se trouve, et si vous avez une imbrication arbitrairement profonde, vous avez besoin d'un automate arbitrairement volumineux, qui se heurte à la notion de automate fini .

Vous pouvez associer des éléments imbriqués / appariés jusqu'à une profondeur fixe, où la profondeur n'est limitée que par votre mémoire, car l'automate devient très volumineux. En pratique, cependant, vous devriez utiliser un automate à bascule, c’est-à-dire un analyseur syntaxique pour une grammaire sans contexte, par exemple LL (de haut en bas) ou LR (de bas en haut). Vous devez tenir compte du comportement d’exécution le plus défavorable: O (n ^ 3) vs O (n), avec n = longueur (entrée).

Il existe de nombreux générateurs d’analyseurs disponibles, par exemple, ANTLR pour Java. Trouver une grammaire existante pour Java (ou C) n'est également pas difficile.
Pour plus d'informations, consultez la théorie des automates sur Wikipedia

.

Autres conseils

Utiliser des expressions régulières pour rechercher des motifs imbriqués est très simple. 

'/(\((?>[^()]+|(?1))*\))/'

Solution Perl fonctionnant probablement, si la chaîne est sur une ligne: 

my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;

if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
    print "Found: $1\n" ;
  }

HTH

MODIFIER: vérifier:

Et une dernière chose de Torsten Marek (qui a correctement souligné que ce n'est plus une regex) :

Oui, s'il s'agit d'un moteur .NET RegEx. Le moteur .Net prend en charge la machine à états finis fournie avec une pile externe. voir détails

.

Le Lemme de pompage pour les langues ordinaires est la raison pour laquelle vous ne pouvez pas faire cela.

L’automate généré aura un nombre fini d’états, disons k, donc une chaîne de k + 1 accolades ouvrantes doit obligatoirement avoir un état répété quelque part (lorsque l’automate traite les caractères). La partie de la chaîne entre le même état peut être dupliquée à l'infini et l'automate ne saura pas la différence.

En particulier, s’il accepte k + 1 accolades suivies de k + 1 accolades fermantes (ce qui devrait être le cas), il acceptera également le nombre pompé d’accolades ouvrantes suivi de k ).

Les expressions régulières appropriées ne pourraient pas le faire, car vous quitteriez le domaine des langages normaux pour atterrir dans les territoires en langues sans contexte.

Néanmoins, l'expression "expression régulière" Les packages proposés par de nombreuses langues sont strictement plus puissants.

Par exemple, les expressions régulières Lua ont le " % b () " ; reconnaisseur qui correspondra à la parenthèse équilibrée. Dans votre cas, vous utiliseriez " % b {} "

Un autre outil sophistiqué similaire à sed est le gema , qui vous permet d'associer très facilement des accolades équilibrées à . {#} .

Donc, en fonction des outils dont vous disposez, votre "expression régulière" (dans un sens plus large) peut correspondre aux parenthèses imbriquées.

L'utilisation de la correspondance récursive dans le moteur de regex PHP est beaucoup plus rapide que la correspondance procédurale des crochets. surtout avec des chaînes plus longues.

http://php.net/manual/fr/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;
}

OUI

... en supposant qu'il y ait un nombre maximal de nids où vous seriez heureux de vous arrêter.

Laissez-moi vous expliquer.

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

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

L'expression régulière (pour les commentaires à profondeur unique) est la suivante: 

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

Ceci pourrait facilement être adapté à vos besoins en remplaçant les \ (+ \ * + et \ * + \) + par { et } , en remplaçant le reste par un simple [^ {}] : 

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

( Voici le lien pour l'essayer.)

Pour imbriquer, laissez simplement ce motif dans le bloc lui-même: 

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

Pour rechercher des blocs triples imbriqués, utilisez: 

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

Un schéma clair est apparu. Pour trouver des commentaires imbriqués à une profondeur de N , utilisez simplement l'expression régulière: 

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

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

Un script peut ê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. ??)

Comme mentionné par zsolt, certains moteurs d’expression régulière prennent en charge la récursivité - bien sûr, ce sont généralement ceux qui utilisent un algorithme de retour en arrière, de sorte qu’il ne sera pas particulièrement efficace. exemple: / (? > [^ {}] *) {(? > [^ {}] *) (? R) * (? > [^ {}] *)} / sm

Non, vous entrez dans le domaine des Grammaires sans contexte à ce stade. .

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

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top