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

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 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 grand, ce qui entre en collision avec la notion de finie automate.

Vous pouvez faire correspondre des éléments imbriqués/appariés jusqu'à une profondeur fixe, la profondeur n'étant limitée que par votre mémoire, car l'automate devient très grand. En pratique, cependant, vous devriez utiliser un automate push-down, c'est-à-dire un analyseur syntaxique pour une grammaire sans contexte, par exemple LL (top-down) ou LR (bottom-up). Vous devez prendre en compte le plus mauvais comportement à l'exécution : 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. Il n'est pas non plus difficile de trouver une grammaire existante pour Java (ou C).
Pour plus d'informations : Théorie des automates à Wikipedia

Answer 2

L'utilisation d'expressions régulières pour vérifier les motifs imbriqués est très simple.

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

Answer 3

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

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

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

HTH

EDIT : vérifier :

• http://dev.perl.org/perl6/rfc/145.html
• informations sur le rubis : http://www.ruby-forum.com/topic/112084
• plus de perl : http://www.perlmonks.org/?node_id=660316
• encore plus de perl : https://metacpan.org/pod/Text::Balanced
• perl, perl, perl : http://perl.plover.com/yak/regex/samples/slide083.html

Et encore une chose par Torsten Marek (qui avait fait remarquer, à juste titre, que ce n'est plus une regex) :

• http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2008-03/msg01047.html

Answer 4

Le site Lemme de pompage pour les langages réguliers est la raison pour laquelle vous ne pouvez pas faire ça.

L'automate généré aura un nombre fini d'états, disons k, donc une chaîne de k+1 accolades ouvrantes aura forcément 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 une infinité de fois et l'automate ne fera pas la différence.

En particulier, s'il accepte k+1 accolades ouvrantes suivies de k+1 accolades fermantes (ce qu'il devrait faire), il acceptera également le nombre pompé d'accolades ouvrantes suivies de k+1 accolades fermantes inchangées (ce qu'il ne devrait pas faire).

Answer 5

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

Néanmoins, les paquets "expression régulière" proposés par de nombreux langages sont nettement plus puissants.

Par exemple, Lua Les expressions régulières ont le caractère " %b() "qui correspondra aux parenthèses équilibrées. Dans votre cas, vous utiliseriez " %b{} "

Un autre outil sophistiqué similaire à sed est gema où il est très facile de faire correspondre des accolades équilibrées avec les éléments suivants {#} .

Ainsi, selon les outils dont vous disposez, votre "expression régulière" (au sens large) peut être capable de correspondre à des parenthèses imbriquées.