Comment pouvons-nous faire correspondre un ^ nb ^ n avec une expression rationnelle Java?

Question

_{Cette est la deuxième partie d'une série d'actions éducatives regex articles. Il montre comment lookaheads et les références imbriquées peuvent être utilisés pour correspondre à la non-régulière languge aⁿbⁿ. Les références imbriquées sont d'abord introduits dans: Comment cette regex trouver triangulaire numéros?}

L'un de l'archétype du non-langages réguliers est:

L = { aⁿbⁿ: n > 0 }

C'est la langue de tous les non-vide cordes composé d'un certain nombre de a'suivi d'un nombre égal de b'. Exemples de chaînes de caractères dans cette langue sont ab, aabb, aaabbb.

Ce langage peut être montrer à des non-régulière, par le lemme de pompage. C'est en fait un archétype du contexte de la langue, qui peut être généré par le contexte de la grammaire S → aSb | ab.

Néanmoins, moderne regex implémentations reconnaissent clairement plus que juste des langages réguliers. Qui est, ils ne sont pas "régulière" par le langage formel de la théorie de la définition. PCRE et Perl supporte récursive regex, et .NET prend en charge l'équilibrage des groupes de définition. Encore moins de "fantaisie", par exemple la référence arrière de correspondance, signifie que la regex n'est pas régulière.

Mais juste comment puissant est cette "base" de fonctionnalités? Peut-on reconnaître L avec Java regex, par exemple? Pouvons-nous peut-être combiner lookarounds et les références imbriquées et d'avoir un modèle qui fonctionne avec, par exemple, String.matches pour correspondre à cordes, comme ab, aabb, aaabbb, etc?

Références

• perlfaq6: puis-je utiliser les expressions régulières de Perl pour correspondre texte équilibré?
• MSDN - Expression Régulière des Éléments de la Langue - l'Équilibrage des Définitions de Groupe
• pcre.org - PCRE page de man
• regular-expressions.info - Lookarounds et de Regroupement et de références arrières
• java.util.regex.Pattern

Liés à des questions

• Ne lookaround affecter les langues peuvent être obtenues par les expressions régulières?
• .NET Regex Équilibrage des Groupes vs PCRE Récursive Modèles

Answer 1

Etant donné que rien n’a été fait pour que PCRE prenne en charge des modèles récursifs, je voudrais simplement souligner l’exemple le plus simple et le plus efficace de PCRE qui décrit le langage en question:

 /^(a(?1)?b)$/
 

Answer 2

Comme mentionné dans la question - avec .NET de l'équilibrage de groupe, les modèles du type unⁿbⁿcⁿdⁿzⁿ peut être adapté facilement que

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))
$

Par exemple: http://www.ideone.com/usuOE

---

Edit:

Il y a aussi un PCRE modèle pour le langage généralisé avec récursive modèle, mais une anticipation est nécessaire. Je ne pense pas que c'est une traduction directe de la ci-dessus.

^
  (?=(a(?-1)?b))  a+
  (?=(b(?-1)?c))  b+
  ...
  (?=(x(?-1)?y))  x+
     (y(?-1)?z)
$

Par exemple: http://www.ideone.com/9gUwF