18

DotNet の正規表現には、" " でのグループ化のように、ネストされた構造の正しい一致を可能にする特別なメカニズムがあることを覚えているようです( (a ( ( c ) b ) ) ( d ) e )。

この機能に相当する Python は何ですか? これは、正規表現と回避策を使用して実現できますか? (ただし、正規表現の現在の実装が設計されていないような問題のようです)

4

6 に答える 6

22

正規表現は、ネストされた構造を解析できません。ネストされた構造は、定義上、規則的ではありません。それらは通常の文法では構築できず、有限状態オートマトンによって解析することもできません (正規表現は FSA の簡略表記と見なすことができます)。

今日の「正規表現」エンジンは、一部の限定された「入れ子」構造をサポートすることがありますが、技術的な観点からは、もはや「正規」と呼ばれるべきではありません。

于 2009-07-08T23:10:34.723 に答える
20

通常、Pythonの正規表現を使用してこれを行うことはできません。（.NET正規表現は、ネストされた一致を可能にする「バランシンググループ」で拡張されています。）

ただし、PyParsingは、このタイプのものに非常に適したパッケージです。

from pyparsing import nestedExpr

data = "( (a ( ( c ) b ) ) ( d ) e )"
print nestedExpr().parseString(data).asList()

出力は次のとおりです。

[[['a', [['c'], 'b']], ['d'], 'e']]

PyParsingの詳細：

于 2009-07-08T23:14:09.847 に答える
14

編集： falsetruのネストされたパーサーは、区切り文字と項目区切り文字を指定するために任意の正規表現パターンを受け入れるように少し変更しましたが、元のre.Scannerソリューションよりも高速で簡単です。

import re

def parse_nested(text, left=r'[(]', right=r'[)]', sep=r','):
    """ https://stackoverflow.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
于 2013-02-05T19:56:12.803 に答える
2

Python は、正規表現での再帰をサポートしていません。そのため、.NET のバランシング グループや Perl の PCRE 正規表現に相当するものは、Python ではすぐには実現できません。

あなたが言ったように、これは単一の正規表現で実際に解決すべき問題ではありません。

于 2009-07-08T16:38:07.823 に答える
1

正規表現自体からネストを削除し、結果をループして正規表現を実行することをお勧めします。

于 2009-07-08T16:34:13.680 に答える
0

再帰について話しているのですか？あなたの質問からは明らかではありません。例：

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')

これは、ネストされたグループの一致を示しています。グループの番号付けは、パターン内の開き括弧の順序によって異なります。

于 2009-07-08T16:57:31.560 に答える