"현대"regexes의 인식력

Question

실제 현대 정규 표현식이 실제로 인식하는 언어 클래스는 무엇입니까?

역 참조 (예 : (.*)_\1)가있는 제한되지 않은 길이 캡처 그룹이있을 때마다 정규 표현식이 이제는 비정규 언어와 일치합니다. 그러나 이것만으로도 S ::= '(' S ')' | ε과 같은 내용을 검색하기에는 충분하지 않습니다. 문맥이없는 괄호 쌍을 사용하는 언어입니다.

재귀 regexes (나에게는 처음이지만 Perl과 PCRE에는 확실하지만) 대부분의 CFL을 인식하는 것으로 보입니다.

누구든지이 분야의 연구를했거나 읽었습니까? 이 "현대"정규 표현식의 한계는 무엇입니까? LLG 또는 LR 문법의 CFG보다 엄격하게 더 엄격하게 또는 덜 엄격하게 인식합니까? 또는 정규식에서 인식 할 수있는 언어가 있지만 CFG가 아닌 과이 모두 해당 언어가 있습니까?

관련 문서에 대한 링크는 많은 도움이 될 것입니다. 재귀 패턴

Answer 1

패턴 재귀

, 당신은 일치하는 재귀 하강 의 형태를 갖는다.

다양한 문제에 대해서는 문제가 없지만 일단 파싱을 실제로 수행하려면 캡처 그룹을 여기 저기에 삽입해야하며 이런 방식으로 전체 구문 분석 구조를 복구하는 것은 어렵습니다. Damian Conway의 Regexp::Grammars Perl 용 모듈은 단순 패턴을 재귀 적 데이터 구조로 캡처하는 모든 작업을 자동으로 수행하여 파싱 된 구조를 훨씬 쉽게 검색 할 수 있도록 해주는 동일한 패턴으로 변환합니다. 이 게시물 끝에이 두 가지 접근 방식을 비교 한 샘플이 있습니다. 재귀

에

제한 문제는 순환 패턴과 일치 할 수있는 어떤 문법의 종류이었다. 음, 확실히 그들은 recursive descent 타입 matchers입니다. 유일한 점은 재귀 패턴이 left recursion을 처리 할 수 ​​없다는 것입니다. 이것은 문법의 종류에 제약을가합니다. 경우에 따라 왼쪽 재귀를 제거하기 위해 작품의 순서를 변경할 수 있습니다.

BTW, PCRE 및 Perl은 재귀 구문에 허용되는 방식이 약간 다릅니다. pcrepattern 맨 페이지의 "RECURSIVE PATTERNS"및 "Perl과의 재귀 차이"절을 참조하십시오. 예 : Perl은 ^(.|(.)(?1)\2)$을 처리 할 수 ​​있습니다. 여기서 PCRE는 ^((.)(?1)\2|.)$이 필요합니다. 재귀 패턴

재귀 데모

의 필요성은 놀라 울 정도로 자주 발생한다. 자주 방문하는 예제 중 하나는 균형 잡힌 괄호, 따옴표 또는 HTML/XML 태그와 같이 중첩 될 수있는 항목을 일치시켜야 할 때입니다. 교정 된 괄호에 대한 일치 사항은 다음과 같습니다.

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

작고 자연 스럽기 때문에 읽기가 더 까다 롭습니다.

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

:, 명확한 예는 중첩 된 따옴표와 일치하는 것 그리고

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

다시, 우리는 우리의 재귀에 대한 괄호를 사용하고 있기 때문에이는 공백이 더 이상 중요하지 않습니다에 /x 모드를 쉽게 경화입니다

재귀 적으로 정의 할 수있는 또 다른 것으로 일치시킬 수있는 것은 회문입니다. 이 간단한 패턴은 펄에서 작동 :이 같은 것을 사용하는 대부분의 시스템에서 테스트 할 수 있습니다

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

, 패턴에 아주 약간 다른 표기법을 사용하여, 당신은 지금 깔끔하게 표시된 모든 것을 멀리 당신을위한 %/ 변수의 전체 구문 분석 트리를 저장하는 무언가를 얻을. =~ 연산자에서 볼 수 있듯이 변환 결과는 여전히 패턴입니다. 그것은 약간 마술 적입니다.