Python正则表达式模块是否使用BRE或ERE？

Question

似乎POSIX将正则表达式实现分为两类:基本正则表达式(BRE)和扩展正则表达式(ERE).

Python re模块引用似乎没有指定.

Answer 1

除了语法中的某些相似性之外,re模块不遵循正则表达式的POSIX标准.

不同的匹配语义

POSIX正则表达式(可以使用DFA/NFA甚至回溯引擎实现)总是找到最左边的最长匹配,而re模块是回溯引擎,它找到最左边的"最早"匹配(根据定义的搜索顺序"最早")通过正则表达式).

在匹配语义的差异可在匹配的情况下,可观察到(Prefix|PrefixSuffix)对抗PrefixSuffix.

• 在POSIX-complaint实现POSIX正则表达式(不是那些只借用语法),正则表达式将匹配PrefixSuffix.
• 相比之下,re引擎(以及许多其他回溯正则表达式引擎)将Prefix仅匹配,因为Prefix在交替中首先指定.

差也可以被看作在匹配的情况下(xxx|xxxxx)*针对xxxxxxxxxx(10串x的):

• 在Cygwin上:

  $ [[ "xxxxxxxxxx" =~ (xxx|xxxxx)* ]] && echo "${BASH_REMATCH[0]}"
  xxxxxxxxxx
  

  所有10个x都匹配.

• 在Python中:

  >>> re.search(r'(?:xxx|xxxxx)*', 'xxxxxxxxxxx').group(0)
  'xxxxxxxxx'
  

  只有9 x匹配,因为它xxx在所有3次重复中选择交替的第一项,并且没有任何强制它回溯并在交替中尝试第二项)

POSIX独有的正则表达式功能

除了匹配语义的不同之外,POSIX正则表达式还定义了用于整理符号,等价类表达式和基于排序的字符范围的语法.这些功能大大增加了正则表达式的表现力.

以等价类表达式为例,从文档中:

等价类表达式应表示属于等价类的整理元素集,如归类顺序中所述.[...].该类应通过将等价类中的任何一个整理元素括在括号相等("[="和"=]")分隔符中来表示.例如,如果'a','à'和'â'属于同一等价类,然后"[[=a=]b]","[[=à=]b]"和"[[=â=]b]"分别相当于"[aàâb]".[...]

由于这些功能在很大程度上取决于区域设置,因此相同的正则表达式在不同的区域设置上的行为可能会有所不同.它还取决于整理顺序的系统上的区域设置数据.

re 正则表达式功能

re借用了Perl的语法,但并未实现Perl正则表达式中的所有功能re.以下是rePOSIX正则表达式中不可用的一些正则表达式功能:

• 贪婪/惰性量词,指定扩展量词的顺序.

  ^{虽然人们通常称*POSIX为贪婪,但它实际上只指定了POSIX中重复的下限和上限.所谓的"贪婪"行为是由最左边最长的匹配规则引起的.}

• 环视断言(前瞻和后视)
• 条件模式 (?(id/name)yes-pattern|no-pattern)
• 速记结构:\b,\s,\d,\w(一些POSIX正则表达式引擎可以实现这些,因为标准的离开行为未定义对于这些情况)

Answer 2

都不是.它基本上是PCRE方言,但是一个独特的实现.

re文档中的第一句话说:

此模块提供与Perl中类似的正则表达式匹配操作.

虽然这并没有立即向新手揭示它们如何与例如POSIX正则表达式相关,但应该是常识,Perl 4及更高版本的Perl 5提供了早期工具的正则表达式功能的大幅扩展功能集,包括POSIX强制要求的功能集.grep -E又名ERE.

该perlre手册页详细描述了正则表达式的功能,但你会发现很多在Python文档以不同的形式相同的细节.Perl手册页包含以下历史记录:

Perl模式匹配中使用的模式是从版本8正则表达式例程中提供的模式演变而来的.(这些例程是由Henry Spencer可自由再分发的V8例程重新实现而得到的(远程).)

(这里,V8指的是Version 8 Unix.Spencer的库基本上(重新)实现了POSIX正则表达式.)

Perl的4进行了大量的便利构造等\d,\s,\w以及符号速记像\t,\f,\n.Perl 5添加了一组重要的扩展(仍然在缓慢增长),包括但不限于

• 非贪婪的量词
• 非回溯量词
• Unicode符号和属性支持
• 非分组括号
• 前瞻和外观
• ...基本上任何开头的东西 (?

因此,"常规"表达决不再是严格的"常规".

这是由最初用于Exim邮件服务器的Philip Hazell在便携式库中重新实现的; 他的PCRE库已经进入无数不同的应用程序,包括许多编程语言(Ruby,PHP,Python等).顺便提一下,尽管有名称,但库并不是严格的"Perl兼容"(不再是); 在功能和行为方面存在差异.(例如,Perl内部更改*为{0,32767}PCRE执行其他操作时的内容.)

早期版本的Python实际上有一个不同的正则表达式实现,并且有计划再次更改它(尽管它基本上仍然是PCRE).这是Python 2.7/3.5的情况.