Les expressions régulières peuvent-elles être utilisées pour correspondre à des modèles nesteds?

Est-il possible d’écrire une expression régulière qui correspond à un modèle nested qui se produit un nombre de fois inconnu? Par exemple, une expression régulière peut-elle correspondre à une accolade d’ouverture et de fermeture lorsqu’il existe un nombre inconnu d’accolades ouvertes / fermées nestedes dans les accolades externes?

Par exemple:

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

Doit correspondre à:

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

Non, c’est aussi simple que ça. Un automate fini (qui est la structure de données sous-jacente à une expression régulière) n’a pas de mémoire autre que l’état dans lequel il se trouve. Si vous avez une imbrication arbitraire profonde, vous avez besoin d’un automate de taille arbitraire.

Vous pouvez associer des éléments nesteds / appariés à une profondeur fixe, la profondeur n’étant limitée que par votre mémoire, car l’automate devient très volumineux. En pratique, cependant, vous devez utiliser un automate déroulant, c’est-à-dire un parsingur syntaxique pour une grammaire sans contexte, par exemple LL (top-down) ou LR (bottom-up). Vous devez prendre en compte le pire comportement à l’exécution: O (n ^ 3) vs. O (n), avec n = longueur (entrée).

Il existe de nombreux générateurs d’parsingurs, par exemple ANTLR pour Java. Trouver une grammaire existante pour Java (ou C) n’est pas non plus difficile.
Pour plus d’informations: Théorie des automates sur Wikipedia

Probablement la solution Perl qui fonctionne, si la chaîne est sur une seule ligne:

 my $NesteD ; $NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ; if ( $Ssortingngy =~ m/\b( \w+$NesteD )/x ) { print "Found: $1\n" ; } 

HTH

MODIFIER: vérifier:

Et encore une chose par Torsten Marek (qui a bien fait remarquer que ce n’est plus une regex):

L’utilisation d’expressions régulières pour vérifier les modèles nesteds est très simple.

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

Oui, s’il s’agit d’un moteur .NET RegEx. Le moteur .Net prend en charge les machines à états finis fournies avec une stack externe. voir les détails

Le lemme de pompage pour les langues régulières est la raison pour laquelle vous ne pouvez pas le faire.

L’automate généré aura un nombre fini d’états, disons k, donc une chaîne de k + 1 accolades sera forcément répété quelque part (comme l’automate traite les caractères). La partie de la chaîne entre le même état peut être dupliquée à l’infini de nombreuses fois et l’automate ne connaîtra pas la différence.

En particulier, si elle accepte les accolades ouvrantes k + 1 suivies des accolades fermantes k + 1 (ce qui devrait être le cas), elle acceptera également le nombre d’accolades ouvrantes suivi par les balises fermantes k + 1 non modifiées (ce qui ne devrait pas être le cas).

Des expressions régulières appropriées ne seraient pas en mesure de le faire car vous quitteriez le domaine des langues régulières pour atterrir dans les territoires des langues libres de contexte.

Néanmoins, les packages «expressions régulières» que de nombreuses langues proposent sont ssortingctement plus puissants.

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

Un autre outil sophistiqué, similaire à sed, est gema , où vous allez très facilement faire correspondre les accolades avec {#} .

Ainsi, selon les outils dont vous disposez, votre “expression régulière” (au sens large) peut être compatible avec les parenthèses nestedes.

L’utilisation de la correspondance récursive dans le moteur de regex PHP est considérablement plus rapide que la correspondance procédurale des crochets. surtout avec des cordes plus longues.

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

par exemple

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

contre.

 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 ssortingng 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; } 

Comme zsolt l’a mentionné, certains moteurs de regex supportent la récursivité – bien sûr, ce sont généralement ceux qui utilisent un algorithme de backtracking, donc ce n’est pas particulièrement efficace. exemple: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

Non, vous entrez dans le domaine des Grammars Context Free à ce stade.

OUI

… en supposant qu’il y ait un nombre maximum de nichées, vous seriez heureux de vous y arrêter.

Laisse-moi expliquer.


@ torsten-marek a raison de dire qu’une expression régulière ne peut pas vérifier les modèles nesteds comme celui-ci, MAIS il est possible de définir un modèle de regex nested qui vous permettra de capturer des structures nestedes comme celle-ci jusqu’à une profondeur maximale . J’en ai créé un pour capturer des commentaires de style EBNF ( 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} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+ 

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

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

( Voici le lien pour l’essayer.)

Pour nidifier, autorisez simplement ce motif dans le bloc lui-même:

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

Pour trouver des blocs nesteds, utilisez:

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

Un schéma clair a émergé. Pour trouver des commentaires nesteds à une profondeur de N , utilisez simplement la regex:

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

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

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

Ma question + réponse est liée et je fais une expression et une méta-expression qui peuvent correspondre à des niveaux arbitraires (finis) d’imbrication. C’est assez fugace mais que pouvez-vous attendre d’autre? Utilisez les backreferences dans le match si votre moteur le supporte.

Non. Vous avez besoin d’un parsingur complet pour ce type de problème.