Trouver la parenthèse correspondante avec Regex

Question

L'entrée est une chaîne représentant une liste d'éléments.

Une liste est définie comme une boucle ouverte { suivie par 0 ou plusieurs éléments séparés par des espaces suivis d'un bouclé fermé }.

Un élément est soit un littéral, soit une liste d'éléments.

Un littéral est une succession de caractères qui ne sont pas des espaces. Si un élément contient une parenthèse bouclée, il doit être échappé avec un antislash: \{ et \}. (Ou vous pourriez supposer Curlies ne sont pas autorisés à l'intérieur littéraux, pour simplifier) ​​

Exemple:

"{abc { def ghi } 7 { 1 {2} {3 4} } {5 6} x\{yz \}foo }" 

Pas Curly à l'intérieur littéraux:

"{abc { def ghi } 7 { 1 {2} {3 4} } {5 6} xyz foo }" 

(Ceci est une définition simplifiée d'une liste Tcl Ce que je veux savoir est: l'entrée peut-elle être divisée en éléments de la boucle la plus externe en utilisant regex?

Résultats attendus:

abc 
{ def ghi } 
7 
{ 1 {2} {3 4} } 
{5 6} 
x{yz 
}foo 

La vraie question est: peut-il être fait avec un Regex?

Je suis plus intéressé par la saveur .NET, mais acceptera toutes les réponses.

Je vais poster ma propre hypothèse dans une réponse, et voir si elle est validée ou détruite.

Answer 1

Eh bien, l'édition supprime les accolades des jetons et prend l'aiguillon de la question, et maintenant il est facilement réalisable avec .Net Regex, en utilisant des groupes d'équilibrage. Il s'agit simplement d'accolades correspondantes, ce qui est un exemple fondamental.
Tout comme la réponse de KennyTM, cela ne fonctionnera que si vous supprimez les accolades de niveau supérieur, ou il correspondra à l'ensemble de l'entrée.
Encore une fois, cela est mieux utilisé à des fins récréatives:

(?:     # try matching... 
    (?:\\[{}]|[^\s{}])+\s*? # a literal (allow escaped curly braces) 
    |      # OR 
    (?<Curly>{)\s*   # "{" and push to stack 
    |      # OR 
    (?<-Curly>})\s*?  # "}", pop from stack and fail if the stack is empty 
)+?     # ...a few times, and stop whenever you can. 
(?(Curly)(?!))   # Make sure there aren't any extra open curly braces 

Pour plus de détails beaucoup plus voir cet article: Regex Balancing Group in Depth

Answer 2

La réponse traditionnelle à ceci est un "NO" retentissant. Comme nous l'avons appris dans la classe des compilateurs, une grammaire régulière ne peut pas être utilisée pour décrire un langage avec une définition récursive (c'est-à-dire que vous ne pouvez pas utiliser une machine d'états finis)

dont la mise en œuvre se résume à une machine à états finis + un STACK.
Voir ANTLR, bison etc.

Answer 3

@Cristi est juste au sujet de la regex: Il est théoriquement impossible de résoudre les expressions récursives utilisant un stackless, automate à états finis. La solution, cependant, est plus simple: il suffit de garder un compteur du nombre de parenthèses ouvertes, et assurez-vous qu'il ne descend pas au-dessous de 0. Il est plus économique de conserver la pile et vous n'avez besoin que de compte - pas le contenu - des parenthèses.

algorithme:

counter = 0      // Number of open parens 
For char c in string:    
    print c       
    if c=='{':      // Keep track on number of open parens 
     counter++ 
    if c=='}': 
     counter-- 
    if counter==1:     // New line if we're back to the top level 
     print "\n" 
    elif counter<1:    // Error if the nesting is malformed 
     print "ERROR: parentheses mismatch" 
     break 

Answer 4

Malheureusement, la réponse est OUI pour une saveur de Regex, par exemple PCRE et .NET, car ils prennent en charge respectivement des opérations récursives et des opérations de type pile.

La grammaire peut être écrite comme

ELEMENT -> (?!\{)\S+ | LIST 
LIST  -> '\{\s*' ELEMENT? ('\s+' ELEMENT)* '\s*\}' 

ainsi dans PCRE, cela peut être transformé en modèle:

\{\s*(?0)?(?:\s+(?0))*\s*\}|(?!\{)(?:[^\s}]|\}(?![\s}]))+ 

# ---------------------------     ^^^^^^^^^ 
#   LIST     Make sure the } is not closing the group 

Voir http://www.ideone.com/SnGsU par exemple (je privais de haut niveau { et } pour plus de simplicité).

(Bien sûr, ne pas essayer au travail :))

(BTW, je ne sais pas comment transformer ce PCRE en saveur .NET. Si quelqu'un sait, s'il vous plaît essayer Converting PCRE recursive regex pattern to .NET balancing groups definition)