"現代"の正規表現の認識力

Question

現代の正規表現は実際にどのような言語クラスを認識していますか？

バックリファレンス（例：(.*)_\1）を持つ無制限の長さのキャプチャグループがある場合、正規表現は現在、非正規言語と一致しています。しかし、これだけでは、S ::= '(' S ')' | εのようなものと一致するには十分ではありません - 文脈自由な括弧の対の言語。

再帰正規表現（私には新しく、PerlとPCREには確信があります）は、少なくともほとんどのCFLを認識しているようです。

誰でもこの分野の研究を行ったことがありますか？これらの「現代」正規表現の限界は何ですか？彼らは厳密にLLGやLRの文法のCFGsより厳密に、あるいは厳密に認識していますか？あるいは、正規表現で認識できる言語はありますが、CFGでは認識できない言語はどちらもありますとは逆ですか？

関連論文へのリンクは非常に高く評価されます。再帰的なパターンで

Answer 1

柄再帰

、あなたはに一致する再帰下降の形を持っています。

これは、さまざまな問題のための罰金ですが、あなたが実際にを解析再帰下降をしたいと、あなたがここにあるキャプチャグループを挿入する必要があり、そしてこのように完全な解析構造を回復するために厄介です。 Damian ConwayのRegexp::Grammars Perl用モジュールは、簡単なパターンを同等のものに変換します。これは、名前付きのすべての名前を自動的に再帰的なデータ構造に取り込み、構文解析された構造を簡単に取得できます。私はこの投稿の最後にこれらの2つのアプローチを比較したサンプルを持っています。質問は再帰的なパターンが一致することができ文法のどのような種類だった再帰

上

制限。まあ、彼らは確かにrecursive descent型マッチャーです。念頭に置いておきたいのは、再帰パターンはleft recursionを処理できないということだけです。これは、それを適用できる文法の種類に制約を課します。場合によっては、作品を並べ替えて左回帰をなくすこともできます。

BTW、PCREとPerlは、再帰のフレーズを許可する方法が少し異なります。 pcrepatternのマンページの "RECURSIVE PATTERNS"と "Perlからの再帰差分"のセクションを参照してください。例：Perlは^(.|(.)(?1)\2)$を処理できますが、PCREには^((.)(?1)\2|.)$が必要です。再帰パターンについて

再帰デモ

必要性は驚くほど頻繁に生じます。適切に訪問された例の1つは、バランスの取れたかっこ、引用符、またはHTML/XMLタグなど、ネストできるものと一致する必要がある場合です。

コンパクトな性質のため、読みにくいです。

‘ (?: [^‘’] *+ | (?0))* ’ 

：、明確な例では、ネストされた単一引用符に一致するだろう次に

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

を再び、我々は再帰を括弧を使用しているので、これは空白はもはや重要作らないために/xモードで容易に硬化可能です

再帰的に定義された別のものは、回文となります。この単純なパターンはPerlで動作します：あなたはこのような何か使用して、ほとんどのシステム上でテストすることができます

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

：再帰のPCREの実装が必要であること

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

注意をより精巧

^(?:((.)(?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 
    } 
} 

ご覧のとおり、パターンに非常にわずかに異なる表記を使用することにより、あなたは今、きちんとラベルされたすべてのもので、%/変数であなたのために離れて全体の構文解析ツリーを保存する何かを得ます。 =~演算子でわかるように、変換の結果はまだパターンです。それはほんの少し魔法です。