模式递归
通过递归模式,您可以得到一种递归下降的形式matching.
这对于各种问题来说都很好,但是一旦你想真正进行递归下降parsing,您需要到处插入捕获组,并且以这种方式恢复完整的解析结构很尴尬。达米安康威的正则表达式::语法 http://search.cpan.org/~dconway/Regexp-Grammars-1.012/lib/Regexp/Grammars.pmPerl 的模块将简单模式转换为等效模式,自动将所有命名捕获转换为递归数据结构,从而更轻松地检索已解析的结构。我在本文末尾有一个比较这两种方法的示例。
递归的限制
问题是递归模式可以匹配什么类型的语法。嗯,他们当然是递归下降 http://en.wikipedia.org/wiki/Recursive_descent_parser类型匹配器。我唯一想到的是递归模式无法处理左递归 http://en.wikipedia.org/wiki/Left_recursion.这对您可以应用它们的语法类型施加了限制。有时您可以重新排序您的产品以消除左递归。
顺便说一句,PCRE 和 Perl 在如何表达递归方面略有不同。请参阅“递归模式”和“与 Perl 的递归差异”部分预制模式联机帮助页。例如:Perl可以处理^(.|(.)(?1)\2)$
PCRE 需要的地方^((.)(?1)\2|.)$
反而。
递归演示
对递归模式的需求出人意料地频繁出现。一个常见的例子是当您需要匹配可以嵌套的内容时,例如平衡括号、引号,甚至 HTML/XML 标记。这是平衡括号的匹配:
\((?:[^()]*+|(?0))*\)
我发现由于它的紧凑性,阅读起来比较困难。这很容易治愈/x
使空格不再重要的模式:
\( (?: [^()] *+ | (?0) )* \)
再说一遍,由于我们在递归中使用括号,因此更清晰的示例是匹配嵌套单引号:
‘ (?: [^‘’] *+ | (?0) )* ’
您可能希望匹配的另一个递归定义的东西是回文。这个简单的模式在 Perl 中有效:
^((.)(?1)\2|.?)$
您可以使用以下方法在大多数系统上进行测试:
$ perl -nle 'print if /^((.)(?1)\2|.?)$/i' /usr/share/dict/words
请注意,PCRE 的递归实现需要更精细的
^(?:((.)(?1)\2|)|((.)(?3)\4|.))
这是因为 PCRE 递归工作方式受到限制。
正确的解析
对我来说,上面的例子大多是玩具比赛,而不是全部that有趣,真的。当你有一个真正的语法并试图解析时,它就会变得有趣。例如,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) | (?"ed_string))
(?<domain> (?&dot_atom) | (?&domain_literal))
(?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dcontent))* (?&FWS)?
\] (?&CFWS)?)
(?<dcontent> (?&dtext) | (?"ed_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) | (?"ed_pair))
(?<quoted_string> (?&CFWS)? (?&DQUOTE) (?:(?&FWS)? (?&qcontent))*
(?&FWS)? (?&DQUOTE) (?&CFWS)?)
(?<word> (?&atom) | (?"ed_string))
(?<phrase> (?&word)+)
# Folding white space
(?<FWS> (?: (?&WSP)* (?&CRLF))? (?&WSP)+)
(?<ctext> (?&NO_WS_CTL) | [\x21-\x27\x2a-\x5b\x5d-\x7e])
(?<ccontent> (?&ctext) | (?"ed_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
}
}
正如您所看到的,通过在模式中使用稍有不同的表示法,您现在可以得到将整个解析树存储在%/
变量,所有东西都被整齐地标记。转换的结果仍然是一个模式,正如您可以看到的=~
操作员。这有点神奇。