如何在python中找到所有可能的regex匹配项？

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

寻找：

^{pr2}$

我认为regex公式也可以找到嵌套的括号单词/标记对，但它没有返回它们。我该怎么做？在

Answer 1

现代语言中使用的正则表达式并不代表正则语言。zmo说的对，语言理论中的正则语言是由有限状态自动机表示的，但是现代语言中使用的任何回溯的正则表达式，如捕捉组、查找等，不能用语言理论中的FSAs来表示。如何用DFA甚至NFA来表示（\w+）\1这样的模式？在

您要查找的正则表达式可以如下所示（仅匹配两个级别）：

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

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

匹配项在捕获的组中：

1:（NP（NNP Hoi）（NN哈罗）（NN Hey）（NN（NN Ciao）（NN Adios））

1:（NNP Hoi）

1:（NN哈罗）

1：（NN嘿）

1:（NNP（NN Ciao）（NN Adios））

1:（NN Ciao）

1:（再见）

Answer 2

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

为了解决这个问题，我们使用了一种下推自动机，它被用来定义上下文无关的语法。在

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

Play with it

作为参考，请参考麻省理工学院的课程：

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

注意：有一些正则表达式引擎确实使用下推实现嵌套括号匹配。默认的pythonre引擎不是其中之一，但是存在一个替代引擎，称为^{}（pip install regex），它可以进行递归匹配（这使得重新引擎上下文无关），cfthis code snippet：

^{pr2}$