提问者:小点点

如何在python中找到所有可能的正则表达式匹配?


我试图用python及其正则表达式找到所有可能的单词/标记对或其他嵌套组合。

sent = '(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))'

def checkBinary(sentence):
    n = re.findall("\([A-Za-z-0-9\s\)\(]*\)", sentence)
    print(n)

checkBinary(sent)

Output:
['(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))']

寻找:

['(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))', 
 '(NNP Hoi)', 
 '(NN Hallo)',
 '(NN Hey)', 
 '(NNP (NN Ciao) (NN Adios))',
 '(NN Ciao)',
 '(NN Adios)']

我认为正则表达式也可以找到嵌套的括号单词/标记对,但它不返回它们。我该怎么做?


共2个答案

匿名用户

实际上,使用正则表达式是不可能做到这一点的,因为正则表达式表达的是一种由正则语法定义的语言,可以由非有限确定性自动机来解决,其中匹配由状态表示;然后,为了匹配嵌套括号,您需要能够匹配无限多个括号,然后拥有一个具有无限多个状态的自动机。

为了解决这个问题,我们使用了所谓的下推自动机,用于定义上下文无关语法。

因此,如果您的正则表达式与嵌套括号不匹配,那是因为它表示以下自动机,并且与您的输入不匹配:

玩它

请参考麻省理工学院关于该主题的课程:

  • http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec04.pdf

因此,有效解析字符串的方法之一是为嵌套括号构建语法(pip install pyparsingfirst):

>>> import pyparsing
>>> strings = pyparsing.Word(pyparsing.alphanums)
>>> parens  = pyparsing.nestedExpr( '(', ')', content=strings)
>>> parens.parseString('(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))').asList()
[['NP', ['NNP', 'Hoi'], ['NN', 'Hallo'], ['NN', 'Hey'], ['NNP', ['NN', 'Ciao'], ['NN', 'Adios']]]]

注意:有一些正则表达式引擎确实使用下推实现嵌套括号匹配。默认的pythonre引擎不是其中之一,但是存在一个替代引擎,称为regexpip安装regex),它可以进行递归匹配(这使得re引擎上下文自由),参见此代码片段:

>>> import regex
>>> res = regex.search(r'(?<rec>\((?:[^()]++|(?&rec))*\))', '(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))')
>>> res.captures('rec')
['(NNP Hoi)', '(NN Hallo)', '(NN Hey)', '(NN Ciao)', '(NN Adios)', '(NNP (NN Ciao) (NN Adios))', '(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))']

匿名用户

zmo说得对,在语言理论中,正则语言是由有限状态自动机表示的,但是正则表达式使用任何回溯形式,比如那些使用捕获组、查找组等的正则表达式在现代语言中,不能用语言理论中已知的FSA来表示。如何用DFA或偶数和NFA表示像(\w)\1这样的模式?

(?=(\((?:[^\)\(]*\([^\)]*\)|[^\)\(])*?\)))

我测试了这个http://regexhero.net/tester/

匹配在捕获的组中:

1:(NP(NNP-Hoi)(NN-Hallo)(NN-Hey)(NNP(NN-Ciao)(NN-Adios))

1:(北角海)

1:(NN哈罗)

1:(嘿嘿)

1:(NNP(NN Ciao)(NN Adios))

1:(NN Ciao)

1:(NN Adios)