如何在Python中实现递归正则表达式？

Question

我想知道在Python中怎么实现递归的正则表达式匹配（我找不到任何例子 :( ）。比如说，怎么写一个可以匹配“括号平衡”的字符串的表达式，比如“foo(bar(bar(foo)))(foo1)bar1”。

Answer 1

使用PyPi的regex库，你可以通过命令 pip install regex 轻松安装。接下来，你可以使用以下内容：

import regex

pattern = r'[^()]*+(\((?>[^()]|(?1))*+\)[^()]*+)++'
text = 'foo(bar(bar(foo)))(foo1)bar1'
print(bool(regex.fullmatch(pattern, text)))
# => True

可以查看这个 Python示例，以及这个 正则表达式模式示例（注意，示例中添加了 \A 和 \z 这两个锚点，因为 regex.fullmatch 需要完全匹配整个字符串）。

模式详细信息

• \A - 在 regex.fullmatch 中隐含的 - 字符串的开始
• [^()]*+ - 0个或多个不是 ( 和 ) 的字符（这是一个贪婪匹配，不允许回溯到模式中）
• (\((?>[^()]|(?1))*+\)[^()]*+)++ - 1次或多次出现的第1组模式：
  • \( - 一个 ( 字符
  • (?>[^()]|(?1))*+ - 1次或多次重复（贪婪匹配）
    • [^()] - 任何不是 ( 和 ) 的字符
    • | - 或者
    • (?1) - 一个正则表达式子程序，递归第1组模式
  • \) - 一个 ) 字符
  • [^()]*+ - 0个或多个不是 ( 和 ) 的字符（贪婪匹配）
• \z - 在 regex.fullmatch 中隐含的 - 字符串的结束。

可以在 regular-expressions.info 查看关于模式和正则表达式子程序的更多信息。

Answer 2

你无法通过正则表达式来实现这个。Python不支持递归的正则表达式。

Answer 3

你可以使用 pyparsing 这个工具。

#!/usr/bin/env python
from pyparsing import nestedExpr
import sys
astring=sys.argv[1]
if not astring.startswith('('):
    astring='('+astring+')'

expr = nestedExpr('(', ')')
result=expr.parseString(astring).asList()[0]
print(result)

运行这个代码会得到：

% test.py "foo(bar(bar(foo)))(foo1)bar1"
['foo', ['bar', ['bar', ['foo']]], ['foo1'], 'bar1']