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

Question

我正在尝试使用 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)']

我认为正则表达式公式也可以找到嵌套的括号词/标签对，但它不会返回它们。我应该怎么做？

Answer 1

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

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

因此，如果您的正则表达式与嵌套括号不匹配，那是因为它表达了以下自动机并且与您输入的任何内容都不匹配:

Play with it

作为引用，请查看麻省理工学院关于该主题的类(class):

• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec04.pdf
• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-005-elements-of-software-construction-fall-2011/lecture-notes/MIT6_005F11_lec05.pdf
• http://www.saylor.org/site/wp-content/uploads/2012/01/CS304-2.1-MIT.pdf

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

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

注意:有一些正则表达式引擎确实使用下推来实现嵌套括号匹配。默认的 python re 引擎不是其中之一，但存在一个替代引擎，称为 regex (pip install regex) 可以进行递归匹配(这使得 re engine context free)，cf this code snippet :

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