“现代”正则表达式的认知力

真正的现代正则表达式实际上认可什么类型的语言？

每当有一个带有反向引用的无限长度捕获组（例如(.*)_\1 ），正则表达式现在就匹配一个非正则语言。 但是，它本身不足以匹配像S ::= '(' S ')' | ε S ::= '(' S ')' | ε – 匹配成对副本的上下文无关语言。

递归正则表达式（对我来说是新的，但我确信存在于Perl和PCRE中）至少可以识别大多数CFL。

有没有人做过或读过这方面的研究？ 这些“现代”正则表达式的局限性是什么？ 他们是否认可LL或LR语法的严格多于或者少于CFG？ 或者是否存在可以被正则表达式识别但不是CFG的两种语言，反之亦然？

有关论文的链接将不胜感激。

Answer 1

模式递归

使用递归模式，你有一个递归下降匹配的形式。

这对很多问题都是适用的，但是一旦你想实际进行递归下降解析 ，你需要在这里和那里插入捕获组，这样就很难恢复完整的解析结构。 Damian Conway的Perl的Regexp :: Grammars模块将简单模式转换为等同的模式，自动完成所有命名捕获到递归数据结构中的操作，使解析结构的检索变得更容易。 我有一个比较这两个方法在本文结束的示例。

递归的限制

问题是递归模式可以匹配哪种语法。 那么，他们肯定是递归下降类型匹配器。 唯一想到的是， 递归模式不能处理左递归 。 这对您可以应用的语法种类有所限制。 有时你可以重新排序你的作品，以消除左递归。

顺便说一句，PCRE和Perl在你如何允许递归递归方面略有不同。 请参阅pcrepattern手册页中的“RECURSIVE PATTERNS”和“Perl中的递归差异” 部分 。 例如：Perl可以处理^(.|(.)(?1)\2)$ ，其中PCRE需要^((.)(?1)\2|.)$代替。

递归演示

对递归模式的需求出乎意料地频繁出现。 一个很好的例子是当你需要匹配一些可以嵌套的东西时，比如平衡的括号，引号，甚至是HTML / XML标签。 这里是balenced parens的比赛：

 \((?:[^()]*+|(?0))*\) 

由于其紧凑的特性，我发现更难读。 使用/x模式可以很容易地解决这个问题，使得空白不再有意义：

 \( (?: [^()] *+ | (?0) )* \) 

然后再一次，因为我们正在使用parens递归，所以一个更清晰的例子就是匹配嵌套的单引号：

 ' (?: [^''] *+ | (?0) )* ' 

你可能希望匹配的另一个递归定义的东西将是一个回文。 这个简单的模式在Perl中工作：

 ^((.)(?1)\2|.?)$ 

你可以在大多数系统上使用这样的东西来测试：

 $ perl -nle 'print if /^((.)(?1)\2|.?)$/i' /usr/share/dict/words 

请注意，PCRE的递归实现需要更复杂的

 ^(?:((.)(?1)\2|)|((.)(?3)\4|.)) 

这是因为PCRE递归如何工作的限制。

正确的解析

对我来说，上面的例子大多是玩具比赛， 其实并不是那么有趣。 当它变得有趣的时候，你有一个真正的语法，你正试图解析。 例如，RFC 5322相当精细地定义了一个邮件地址。 这是一个“语法”模式来匹配它：

 $rfc5322 = qr{ (?(DEFINE) (?<address> (?&mailbox) | (?&group)) (?<mailbox> (?&name_addr) | (?&addr_spec)) (?<name_addr> (?&display_name)? (?&angle_addr)) (?<angle_addr> (?&CFWS)? < (?&addr_spec) > (?&CFWS)?) (?<group> (?&display_name) : (?:(?&mailbox_list) | (?&CFWS))? ; (?&CFWS)?) (?<display_name> (?&phrase)) (?<mailbox_list> (?&mailbox) (?: , (?&mailbox))*) (?<addr_spec> (?&local_part) \@ (?&domain)) (?<local_part> (?&dot_atom) | (?&quoted_string)) (?<domain> (?&dot_atom) | (?&domain_literal)) (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dcontent))* (?&FWS)? \] (?&CFWS)?) (?<dcontent> (?&dtext) | (?&quoted_pair)) (?<dtext> (?&NO_WS_CTL) | [\x21-\x5a\x5e-\x7e]) (?<atext> (?&ALPHA) | (?&DIGIT) | [!#\$%&'*+-/=?^_`{|}~]) (?<atom> (?&CFWS)? (?&atext)+ (?&CFWS)?) (?<dot_atom> (?&CFWS)? (?&dot_atom_text) (?&CFWS)?) (?<dot_atom_text> (?&atext)+ (?: \. (?&atext)+)*) (?<text> [\x01-\x09\x0b\x0c\x0e-\x7f]) (?<quoted_pair> \\ (?&text)) (?<qtext> (?&NO_WS_CTL) | [\x21\x23-\x5b\x5d-\x7e]) (?<qcontent> (?&qtext) | (?&quoted_pair)) (?<quoted_string> (?&CFWS)? (?&DQUOTE) (?:(?&FWS)? (?&qcontent))* (?&FWS)? (?&DQUOTE) (?&CFWS)?) (?<word> (?&atom) | (?&quoted_string)) (?<phrase> (?&word)+) # Folding white space (?<FWS> (?: (?&WSP)* (?&CRLF))? (?&WSP)+) (?<ctext> (?&NO_WS_CTL) | [\x21-\x27\x2a-\x5b\x5d-\x7e]) (?<ccontent> (?&ctext) | (?&quoted_pair) | (?&comment)) (?<comment> \( (?: (?&FWS)? (?&ccontent))* (?&FWS)? \) ) (?<CFWS> (?: (?&FWS)? (?&comment))* (?: (?:(?&FWS)? (?&comment)) | (?&FWS))) # No whitespace control (?<NO_WS_CTL> [\x01-\x08\x0b\x0c\x0e-\x1f\x7f]) (?<ALPHA> [A-Za-z]) (?<DIGIT> [0-9]) (?<CRLF> \x0d \x0a) (?<DQUOTE> ") (?<WSP> [\x20\x09]) ) (?&address) }x; 

如你所见，那非常类似BNF。 问题是这只是一场比赛，而不是一场比赛。 而且你真的不希望只是把捕获的东西包围起来，因为那并不能告诉你哪个产品匹配哪个部分。 使用前面提到的Regexp :: Grammars模块，我们可以。

 #!/usr/bin/env perl use strict; use warnings; use 5.010; use Data::Dumper "Dumper"; my $rfc5322 = do { use Regexp::Grammars; # ...the magic is lexically scoped qr{ # Keep the big stick handy, just in case... # <debug:on> # Match this... <address> # As defined by these... <token: address> <mailbox> | <group> <token: mailbox> <name_addr> | <addr_spec> <token: name_addr> <display_name>? <angle_addr> <token: angle_addr> <CFWS>? \< <addr_spec> \> <CFWS>? <token: group> <display_name> : (?:<mailbox_list> | <CFWS>)? ; <CFWS>? <token: display_name> <phrase> <token: mailbox_list> <[mailbox]> ** (,) <token: addr_spec> <local_part> \@ <domain> <token: local_part> <dot_atom> | <quoted_string> <token: domain> <dot_atom> | <domain_literal> <token: domain_literal> <CFWS>? \[ (?: <FWS>? <[dcontent]>)* <FWS>? <token: dcontent> <dtext> | <quoted_pair> <token: dtext> <.NO_WS_CTL> | [\x21-\x5a\x5e-\x7e] <token: atext> <.ALPHA> | <.DIGIT> | [!#\$%&'*+-/=?^_`{|}~] <token: atom> <.CFWS>? <.atext>+ <.CFWS>? <token: dot_atom> <.CFWS>? <.dot_atom_text> <.CFWS>? <token: dot_atom_text> <.atext>+ (?: \. <.atext>+)* <token: text> [\x01-\x09\x0b\x0c\x0e-\x7f] <token: quoted_pair> \\ <.text> <token: qtext> <.NO_WS_CTL> | [\x21\x23-\x5b\x5d-\x7e] <token: qcontent> <.qtext> | <.quoted_pair> <token: quoted_string> <.CFWS>? <.DQUOTE> (?:<.FWS>? <.qcontent>)* <.FWS>? <.DQUOTE> <.CFWS>? <token: word> <.atom> | <.quoted_string> <token: phrase> <.word>+ # Folding white space <token: FWS> (?: <.WSP>* <.CRLF>)? <.WSP>+ <token: ctext> <.NO_WS_CTL> | [\x21-\x27\x2a-\x5b\x5d-\x7e] <token: ccontent> <.ctext> | <.quoted_pair> | <.comment> <token: comment> \( (?: <.FWS>? <.ccontent>)* <.FWS>? \) <token: CFWS> (?: <.FWS>? <.comment>)* (?: (?:<.FWS>? <.comment>) | <.FWS>) # No whitespace control <token: NO_WS_CTL> [\x01-\x08\x0b\x0c\x0e-\x1f\x7f] <token: ALPHA> [A-Za-z] <token: DIGIT> [0-9] <token: CRLF> \x0d \x0a <token: DQUOTE> " <token: WSP> [\x20\x09] }x; }; while (my $input = <>) { if ($input =~ $rfc5322) { say Dumper \%/; # ...the parse tree of any successful match # appears in this punctuation variable } } 

正如你所看到的，通过在模式中使用一个略微不同的符号，你现在可以得到一些东西，把整个分析树存储在%/变量中，所有东西都整齐地标记出来。 这个转换的结果仍然是一个模式，你可以通过=~操作符来看到。 这只是有点神奇。