Python库将正则表达式解析为AST？

Question

为了强调,我不想"使用正则表达式解析" - 我想"将正则表达式解析为符号树".(搜索只带来了前者...)

我的用例:为了加速对数据库的正则表达式搜索,我想解析一个正则表达式,(foo|bar)baz+(bat)*并拉出必须出现在匹配中的所有子串.(在这种情况下,只是baz因为foo/bar是替换而bat会出现0次.)

为此,我需要对正则表达式运算符/语义有所了解.re.DEBUG最近的:

In [7]: re.compile('(foo|bar)baz+(bat)', re.DEBUG)
subpattern 1
  branch
    literal 102
    literal 111
    literal 111
  or
    literal 98
    literal 97
    literal 114
literal 98
literal 97
max_repeat 1 4294967295
  literal 122
subpattern 2
  literal 98
  literal 97
  literal 116

但是,它只是打印出来,据我所知,c实现后来不会保留结构.关于如何在不编写我的所有者解析器的情况下解析它的任何想法？

Answer 1

你也许可以使用这个：

import sre_parse
sre_parse.parse(r'(\d+)foo(.*)')

Answer 2

您只能使用上下文无关语法指定（经典）正则表达式：

 regex = { alternatives };
 alternatives =  primitive { '|' alternatives } ;
 primitive = '(' regex ')' | '[' character_set ']' | ...

这意味着你不能使用正则表达式来解析正则表达式（Perl 是一个例外，但它的“正则表达式”远远超出了“经典”）。

因此，要解析正则表达式，您需要构建自己的解析器并构造某种树（re.Debug 非常接近）或您希望的魔术库。

我怀疑这是最简单的部分。这对你自己来说并不难；请参阅 是否有可在 8 位嵌入式系统上使用的 Flex/bison 替代方案？构建此类解析器的简单方案。

要理解正则表达式的语义（例如，找出“必要的子字符串”），您可能可以构建一个分析器来遍历解析树，并为每个子树（自下而上）计算公共的-细绳。否则，您可能必须实现经典的 NDFA 构造，然后遍历它，或者实现 NDFA 到 DFA 构造，然后遍历 DFA。真正的正则表达式往往包含许多混乱的复杂内容，例如内置字符集、捕获组等。

“公共字符串”可能不仅仅是连续的字符序列，尽管您可以如此狭隘地定义它。它可能包括几个由固定或可变长度字符间隙分隔的常量子字符串，例如，您所需的子字符串本身可能始终可表示为以下形式的“简单正则表达式”：

   (<character>+ ?+) <character>+