Ne sınıf dil gerçek modern yukarıdaki diyagram aslında tanıdınız mı?

Geri-referans (örneğin (.*)_\1) ile sınırsız uzunluğu yakalayan bir grup olduğunda bir düzenli ifade olmayan normal bir dil eşleşen. Ama bu, kendi başına, S ::= '(' S ')' | ε — parens çiftleri eşleşen bağlam-ücretsiz dil gibi bir şey eşleştirmek için yeterli değil.

Özyinelemeli yukarıdaki diyagram benim için yeni, ama emin değilim Perl var ve / olan) en az en Uygulamalar tanımak için görünür.

Herkes yapmış ya da herhangi bir araştırma okudum bu alanda? Ne bu sınırlamaları "" yukarıdaki diyagram? modern Ya da kesinlikle, kesinlikle daha az CFGs'den, LL veya LR gramer tanır mı? Ya da düzenli ancak bir CFG değil tarafından tanınacak her iki dilde var olabilirvetam tersi?

İlgili makaleler linkler çok makbule geçer.

Desen Özyineleme

Özyinelemeli desenleri ile, özyinelemeli kökenli bir form vareşleşen.

Bu çeşitli sorunlar için iyi, ama sonra aslında özyinelemeli iniş yapmak istiyorumayrıştırmayakalama grupları orada burada eklemek gerekir , ve bu garip bir şekilde tam ayrıştırma yapısı kurtarmak için. Damian Conway Regexp::Grammars Perl modülü için otomatik olarak tüm bu yok bir özyinelemeli bir veri yapısı, ayrıştırılmış yapısının çok daha kolay erişim için yapım yakalayan adında bir eşdeğer içine basit desen dönüştürür. Bir örnek bu mesajın sonunda bu iki yaklaşımı karşılaştıran var.

Özyineleme ile ilgili kısıtlamalar

Soru özyinelemeli desenleri maç ne oldu. Kesinlikle recursive descent yazın matchers ediyorlar. Aklına gelen tek şey buözyinelemeli desenler olamaz left recursion kolu.Bu uygulayabilirsiniz aynı türden bir kısıtlama koyar. Bazen sol özyineleme ortadan kaldırmak için yapımları yeniden sıralayabilirsiniz.

BTW, ancak sisteminizde Perl ve biraz özyineleme ifade iznin konusunda farklı düşünüyoruz. “TEKRARLAMALI örnekler” ve “Perl dan Özyineleme fark”. bölümlere bakın ^em>pcrepatternkılavuz. örn: Perl / yerine ^((.)(?1)\2|.)$ gerektirdiği ^(.|(.)(?1)\2)$ işleyebilir.

Özyineleme Demolar

Özyinelemeli desenler ihtiyacı şaşırtıcı derecede sık ortaya çıkar. İyi ziyaret edilen bir örnek, dengeli parantez, tırnak, hatta HTML/XML etiketleri gibi yuvayı bir şey karşılamak için gerekli zaman. İşte balenced parens için: maç

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

Bu yanıltıcıdır kompakt doğası yüzünden okuma bulmak. Bu /x modu ile kolayca tedavi edilebilir boşluk artık önemli yapmak için:

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

Bizim için özyineleme parens kullanıyoruz o günden sonra bir daha, daha net bir örnek, iç içe geçmiş tek tırnak eşleşen olurdu:

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

Maç için isteyebilirsiniz özyinelemeli olarak tanımlanan başka bir şey bir örnek olurdu. Bu basit desen Perl ile çalışır:

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

çoğu sistemde bu gibi bir şey kullanarak test edebilirsiniz

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

Özyineleme / uygulanması daha ayrıntılı gerektirdiğini unutmayın

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

Bu / özyineleme nasıl çalıştığına ilişkin kısıtlamalar.

Ayrıştırmak

Bana, çoğunlukla oyuncak yukarıdaki örnekler, tüm maçlarbuilginç, gerçekten. Gerçek bir dilbilgisi olması ilginç hale geldiğinde ayrıştırmak için çalışıyoruz. Örneğin, RFC 5322 posta adresi yerine özenle tanımlar. İşte bir “gramer bu maç için” desen:

$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;

Gördüğünüz gibi, bu gibi BNF çok. Sorun sadece bir maç, bir yakalama değil. Ve gerçekten bunun neresini bahisler sana gelmez yakalama parens ile her şeyi kuşatır istemiyorum. Daha önce de belirttiğim Regexp::Gramerleri kullanarak modül edebiliriz.

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

Gördüğünüz gibi, her şey düzgün etiketli desen çok az farklı bir gösterim kullanarak, şimdi sizin için tüm ayrıştırma ağacı %/ değişken saklayan bir şeyler getir. Dönüşüm sonucu =~ operatör tarafından gördüğünüz gibi hala bir desen. Biraz büyülü.