Bonart

Классические регулярные выражения из математики такую задачу не решают. Но на практике последние версиии популярной библиотеки PCRE умеют:

my $bal = qr/
    (?<bal>            # Name the rule (optional)  
    \{                 # Open brace
    (?>                # Possessive subgroup
        (?> [^{}]+ )   #  Grab all the non braces
    |                  #    or
        (?&bal)        #  Recurse
    )*                 # Zero or more times
    \}                 # Close brace
    )                  # End named rule
/x;

if ('{x{x}y{x}x}' =~ /^$bal$/ ){
    print "It's balanced\n";
}

$_= 'XXXX function xxx() {x{x}y{x}x} XXXX';

while ( /\bfunction\s+(\w+)\(\)\s*($bal)/g ){
    print "function: $1\nbody: $2\n";
}

Да и дотнет не отстает:

string pattern = 
    @"^((?<openBracket>\{) | [^\{\}] |" + 
    @"(?<closeBracket-openBracket>\}))*" +
    @"(?(openBracket)(?!))$";
Regex r = new Regex(pattern, RegexOptions.IgnorePatternWhitespace);