Найдите соответствующую скобку с помощью Regex

Что ж, при редактировании удаляются фигурные скобки из токенов и устраняется смысл вопроса, и теперь это легко сделать с помощью регулярных выражений .Net, используя группы балансировки. Это просто сопоставление фигурных скобок, что является базовым примером.
Как и ответ Кенни TM, это будет работать, только если вы удалите фигурные скобки верхнего уровня, или они будут соответствовать всему вводу.
Опять же, это лучше использовать для в рекреационных целях:

(?:                    # 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

Для получения более подробной информации см. Эту статью: Regex Balancing Group подробно

К сожалению, для некоторого вкуса Regex ответ ДА, например. PCRE и .NET, потому что они поддерживают рекурсивный шаблон и операции, подобные стеку соответственно.

Грамматику можно записать как

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

таким образом, в PCRE это можно преобразовать в шаблон:

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

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

См., Например, http://www.ideone.com/SnGsU (я удалил верхний уровень { и } для простоты).

(Конечно, на работе не пробуйте :))

(Кстати, я не знаю, как преобразовать этот PCRE в версию .NET. Если кто-то знает, попробуйте преобразовать шаблон рекурсивного регулярного выражения PCRE в .NET определение балансировочных групп)

Традиционный ответ на этот вопрос - твердое «НЕТ». Как мы узнали в классе компиляторов, обычная грамматика не может использоваться для описания языка с рекурсивным определением (т.е. вы не можете использовать конечный автомат)

Здесь нужен контекстно-свободный синтаксический анализатор, реализация которого сводится к конечному автомату + СТЕК.
См. ANTLR, bison и т. Д.

@Cristi прав насчет регулярного выражения: теоретически невозможно решать рекурсивные выражения с помощью бесстекового конечного автомата. Решение, однако, проще: вам нужно только вести счетчик количества открытых скобок и следить за тем, чтобы оно не опускалось ниже нуля. Это больше экономит память, чем поддержка стека, и вам нужен только счетчик. - не содержание - круглых скобок.

Алгоритм:

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