قوة الاعتراف من regexes "الحديثة"

Question

وماذا فئة من اللغات التي regexes الحديثة الحقيقية تعترف فعلا؟

وكلما كان هناك مجموعة طول اسر غير محدود مع الخلفية المرجعية (على سبيل المثال (.*)_\1) باستخدام التعابير المنطقية الآن مطابقة لغة غير العادية. ولكن هذا، في حد ذاته، ليس كافيا لتتناسب شيء من هذا القبيل S ::= '(' S ')' | ε - لغة خالية من السياق من مطابقة أزواج من أقواس

وتظهر regexes تكراري (والتي هي جديدة بالنسبة لي، لكنني الوجود أكد في بيرل وPCRE) الاعتراف على الأقل معظم المصابيح.

ولقد فعلت كل أو قراءة أي بحث في هذا المجال؟ ما هي حدود هذه regexes "الحديثة"؟ هل يعترفون بدقة أكثر أو بدقة أقل من CFGS، من LL أو LR قواعد النحو؟ أو لا توجد على حد سواء اللغات التي يمكن التعرف عليه بواسطة باستخدام التعابير المنطقية ولكن ليس CFG <م> و العكس؟

وصلات لمقالات ذات الصلة سيكون محل تقدير كبير.

Answer 1

تحليل نمط العودية

ومع أنماط متكررة، لديك شكل من أصل عودي <م> مطابقة .

وهذا على ما يرام لمجموعة متنوعة من المشاكل، ولكن مرة واحدة تريد أن تفعل في الواقع النسب العودية <م> إعراب ، تحتاج إلى إدراج مجموعة التقاط هنا وهناك، وهذا هو حرج لاسترداد هيكل تحليل كامل في هذا الطريق. داميان كونواي التعبير العادي :: القواعد النحوية وحدة ل بيرل تحول نمط بسيط في واحد يعادل أن يفعل تلقائيا كل ما يدعى التقاط إلى بنية بيانات متكررة، مما يجعل لاسترجاع أسهل بكثير من هيكل تحليل. لدي عينة مقارنة هذين النهجين في نهاية هذا النشر.

تحليل القيود المفروضة على العودية

وكان السؤال ما هي أنواع من قواعد النحو إلى أن أنماط متكررة يمكن أن المباراة. حسنا، انهم بالتأكيد العودية أصل نوع matchers. الشيء الوحيد الذي يتبادر إلى الذهن هو أن أنماط متكررة على لا يمكن معالجة اليسار العودية . هذا يضع قيدا على أنواع قواعد النحو التي يمكنك تطبيقها على. في بعض الأحيان يمكنك إعادة ترتيب الإنتاج الخاص للقضاء على العودية اليسرى.

وراجع للشغل، PCRE وبيرل تختلف قليلا عن كيفية كنت يسمح لعبارة العودية. مشاهدة المقاطع على "أنماط متكررة" و "الفرق العودية من بيرل" في pcrepattern manpage. على سبيل المثال: بيرل يستطيع التعامل مع ^(.|(.)(?1)\2)$ حيث يتطلب PCRE ^((.)(?1)\2|.)$ بدلا

تحليل العودية ديموس

والحاجة إلى أنماط متكررة تنشأ من المستغرب في كثير من الأحيان. وأحد الأمثلة جيدا زار هو عندما تحتاج لمطابقة شيء يمكن أن العش، مثل الأقواس متوازنة، ونقلت وأو حتى HTML / XML به. وفيما يلي المباراة لأقواس balenced:

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

وأجد أن اصعب لقراءة بسبب طبيعته المدمجة. هذا هو قابل للشفاء بسهولة مع وضع /x لجعل المسافات لم تعد هامة:

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

وبعد ذلك مرة أخرى، منذ نستخدمه أقواس للالعودية لدينا، مثال أكثر وضوحا ستكون مطابقة علامات الاقتباس المفردة المتداخلة:

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

وآخر شيء محددة بشكل متكرر قد ترغب في مباراة ستكون سياق متناظر. هذا النمط بسيط يعمل في بيرل:

^((.)(?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 مثل. المشكلة هي انها مجرد مباراة، وليس القبض عليه. وكنت حقا لا أريد أن مجرد تحيط كل شيء مع أقواس التقاط لأن ذلك لا أقول لكم فيه إنتاج مطابقة أي جزء. باستخدام وحدة التعبير العادي :: القواعد النحوية التي سبق ذكرها، يمكننا.

#!/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
    }
}

وكما ترون، باستخدام التدوين جدا مختلف قليلا في نمط، يمكنك الآن الحصول على شيء الذي يخزن شجرة تحليل كامل بعيدا عنك في متغير %/، مع كل ما وصفت بدقة. ونتيجة لهذا التحول لا يزال نمط، وكما ترون من قبل المشغل =~. انها مجرد السحرية قليلا.