Сопоставление вложенных структур с регулярными выражениями в Python
Кажется, я помню, что регулярные выражения в DotNet имеют специальный механизм, который позволяет правильно сопоставлять вложенные структуры, такие как группировка в "( (a ( ( c ) b ) ) ( d ) e )".
Что является эквивалентом этой функции в Python? Можно ли добиться этого с помощью регулярных выражений с некоторым обходным решением? (Хотя кажется, что это та проблема, для которой текущие реализации регулярных выражений не предназначены)
6 ответов
Вы не можете сделать это, как правило, используя регулярные выражения Python. (Регулярные выражения.NET были расширены с помощью "балансировочных групп", что позволяет использовать вложенные совпадения.)
Тем не менее, PyParsing - очень хороший пакет для таких вещей:
from pyparsing import nestedExpr
data = "( (a ( ( c ) b ) ) ( d ) e )"
print nestedExpr().parseString(data).asList()
Выход:
[[['a', [['c'], 'b']], ['d'], 'e']]
Подробнее о PyParsing:
Регулярные выражения не могут анализировать вложенные структуры. Вложенные структуры не являются регулярными по определению. Они не могут быть построены с помощью регулярной грамматики и не могут быть проанализированы автоматом конечных состояний (регулярное выражение можно рассматривать как сокращенную запись для FSA).
Современные движки "regex" иногда поддерживают некоторые ограниченные "вложенные" конструкции, но с технической точки зрения их больше нельзя называть "обычными".
Редактировать: вложенный парсер falsetru, который я немного изменил, чтобы принимать произвольные шаблоны регулярных выражений для задания разделителей и разделителей элементов, быстрее и проще, чем мой оригинал re.Scanner решение:
import re
def parse_nested(text, left=r'[(]', right=r'[)]', sep=r','):
""" https://stackru.com/a/17141899/190597 (falsetru) """
pat = r'({}|{}|{})'.format(left, right, sep)
tokens = re.split(pat, text)
stack = [[]]
for x in tokens:
if not x or re.match(sep, x):
continue
if re.match(left, x):
# Nest a new list inside the current list
current = []
stack[-1].append(current)
stack.append(current)
elif re.match(right, x):
stack.pop()
if not stack:
raise ValueError('error: opening bracket is missing')
else:
stack[-1].append(x)
if len(stack) > 1:
print(stack)
raise ValueError('error: closing bracket is missing')
return stack.pop()
text = "a {{c1::group {{c2::containing::HINT}} a few}} {{c3::words}} or three"
print(parse_nested(text, r'\s*{{', r'}}\s*'))
доходность
['a', ['c1::group', ['c2::containing::HINT'], 'a few'], ['c3::words'], 'or three']
Вложенные структуры не могут быть сопоставлены только с регулярным выражением Python, но на удивление легко создать базовый синтаксический анализатор (который может обрабатывать вложенные структуры) с помощью re.Scanner:
import re
class Node(list):
def __init__(self, parent=None):
self.parent = parent
class NestedParser(object):
def __init__(self, left='\(', right='\)'):
self.scanner = re.Scanner([
(left, self.left),
(right, self.right),
(r"\s+", None),
(".+?(?=(%s|%s|$))" % (right, left), self.other),
])
self.result = Node()
self.current = self.result
def parse(self, content):
self.scanner.scan(content)
return self.result
def left(self, scanner, token):
new = Node(self.current)
self.current.append(new)
self.current = new
def right(self, scanner, token):
self.current = self.current.parent
def other(self, scanner, token):
self.current.append(token.strip())
Это можно использовать так:
p = NestedParser()
print(p.parse("((a+b)*(c-d))"))
# [[['a+b'], '*', ['c-d']]]
p = NestedParser()
print(p.parse("( (a ( ( c ) b ) ) ( d ) e )"))
# [[['a', [['c'], 'b']], ['d'], 'e']]
По умолчанию NestedParser соответствует вложенным скобкам. Вы можете передать другое регулярное выражение, чтобы соответствовать другим вложенным шаблонам, таким как скобки, [], Например,
p = NestedParser('\[', '\]')
result = (p.parse("Lorem ipsum dolor sit amet [@a xxx yyy [@b xxx yyy [@c xxx yyy]]] lorem ipsum sit amet"))
# ['Lorem ipsum dolor sit amet', ['@a xxx yyy', ['@b xxx yyy', ['@c xxx yyy']]],
# 'lorem ipsum sit amet']
p = NestedParser('<foo>', '</foo>')
print(p.parse("<foo>BAR<foo>BAZ</foo></foo>"))
# [['BAR', ['BAZ']]]
Конечно, pyparsing может сделать намного больше, чем приведенный выше код. Но для этой единственной цели выше NestedParser примерно в 5 раз быстрее для небольших строк:
In [27]: import pyparsing as pp
In [28]: data = "( (a ( ( c ) b ) ) ( d ) e )"
In [32]: %timeit pp.nestedExpr().parseString(data).asList()
1000 loops, best of 3: 1.09 ms per loop
In [33]: %timeit NestedParser().parse(data)
1000 loops, best of 3: 234 us per loop
и примерно в 28 раз быстрее для больших струн:
In [44]: %timeit pp.nestedExpr().parseString('({})'.format(data*10000)).asList()
1 loops, best of 3: 8.27 s per loop
In [45]: %timeit NestedParser().parse('({})'.format(data*10000))
1 loops, best of 3: 297 ms per loop
Python не поддерживает рекурсию в регулярных выражениях. Таким образом, эквиваленты балансировочных групп.NET или регулярных выражений PCRE в Perl не всегда возможны в Python.
Как вы сами сказали: это не та проблема, которую вы действительно должны решить с помощью одного регулярного выражения.
Я бы порекомендовал удалить вложенность из самого регулярного выражения, просмотреть результаты и выполнить регулярные выражения для этого.
Вы говорите о рекурсии? Это не ясно из вашего вопроса. Пример:
ActivePython 2.6.1.1 (ActiveState Software Inc.) based on
Python 2.6.1 (r261:67515, Dec 5 2008, 13:58:38) [MSC v.1500 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> p = re.compile(r"((\w+((\d+)[.;]))(\s+)\d)")
>>> m = p.match("Fred99. \t9")
>>> m
<_sre.SRE_Match object at 0x00454F80>
>>> m.groups()
('Fred99. \t9', 'Fred99.', '9.', '9', ' \t')
Это показывает соответствие вложенных групп. Нумерация групп зависит от порядка, в котором их открывающая скобка встречается в шаблоне.