Найти подходящую скобку с Regex - PullRequest
Новая
       22

Найти подходящую скобку с Regex

4 голосов
/ 29 августа 2010

Входные данные представляют собой строку, представляющую список элементов.

Список определяется как открытый вьющийся {, за которым следуют 0 или более элементов, разделенных пробелом, за которым следует закрытый вьющийся }.

Элемент является литералом или спискомэлементов.

Литерал - это последовательность непробельных символов.Если элемент содержит фигурную скобку, его необходимо экранировать обратной косой чертой: \{ и \}.(Или вы могли бы предположить, что curly не разрешены внутри литералов, для простоты)

Пример: 

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

Нет curly внутри литералов: 

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

(Этоупрощенное определение списка Tcl.)

Что я хочу знать: можно ли разбить вход на элементы самого внешнего цикла с помощью регулярных выражений?

Ожидаемый результат: 

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

Реальный вопрос: можно ли это сделать с помощью регулярных выражений?

Меня больше всего интересует .NET-аромат, но я приму любые ответы.

Я опубликую свое собственное предположение в ответ и посмотрим, проверено ли оно или уничтожено.

Ответы [ 4 ]

4 голосов
/ 29 августа 2010

К сожалению, ответ ДА ​​для некоторой разновидности 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-версию. Если кто-то знает, пожалуйста,try Преобразование шаблона рекурсивного регулярного выражения PCRE в определение групп балансировки .NET )

3 голосов
/ 30 августа 2010

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

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

2 голосов
/ 29 августа 2010

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

Что здесь необходимо, так это отсутствие контекстапарсер, реализация которого сводится к конечному автомату + STACK.
См. ANTLR , bison и т. д.

1 голос
/ 29 августа 2010

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

Алгоритм: 

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
...