Moc rozpoznawania" nowoczesnych " wyrażeń regularnych
Jaką klasę języków właściwie rozpoznają współczesne wyrażenia regularne?
Gdy istnieje nieograniczona Grupa przechwytywania długości z back-reference (np. (.*)_\1
), regex jest teraz dopasowywany do języka nieregularnego. Ale to samo w sobie nie wystarczy, aby dopasować coś w rodzaju S ::= '(' S ')' | ε
- języka bezkontekstowego dopasowywania par paren.
Rekurencyjne wyrażenia regularne (które są dla mnie nowe, ale jestem pewien, że istnieją w Perlu i PCRE) wydają się rozpoznawać przynajmniej większość CFL.
Ma ktoś robił lub czytał jakieś badania w tej dziedzinie? Jakie są ograniczenia tych" nowoczesnych " wyrażeń regularnych? Czy rozpoznają ściśle mniej lub bardziej niż CFGs gramatyki LL lub LR? Czy istnieją oba języki, które mogą być rozpoznawane przez regex, ale nie przez CFG i odwrotnie?
Linki do odpowiednich artykułów byłyby bardzo mile widziane.
1 answers
Rekurencja Wzorca
Z rekurencyjnymi wzorami, masz postać rekurencyjnego zejścia dopasowania.
Jest to w porządku dla różnych problemów, ale gdy chcesz wykonać rekurencyjne parsowanie , musisz wstawić grupy przechwytywania tu i tam, a odzyskanie pełnej struktury parsowania w ten sposób jest niezręczne. Damian Conway ' s Regexp:: Grammars moduł dla Perla przekształca prosty wzór w równoważny, który automatycznie robi wszystko, co nazwane przechwytywanie w rekurencyjną strukturę danych, co znacznie ułatwia pobieranie analizowanej struktury. Mam próbkę porównującą te dwa podejścia na końcu tego postu.
Ograniczenia rekurencji
Pytanie brzmiało, jakie rodzaje gramatyk mogą pasować do wzorców rekurencyjnych. Cóż, z pewnością są to rekurencyjne spadki typu matchers. Jedyne co przychodzi mi na myśl to to, że rekurencyjne wzorce nie mogą obsłużyć rekurencja . to nakłada ograniczenie na rodzaje gramatyk, do których można je zastosować. Czasami można zmienić kolejność produkcji, aby wyeliminować lewe rekurencje.
BTW, PCRE i Perl różnią się nieco sposobem wyrażenia rekursji. Zobacz sekcje "recursive PATTERNS" i "Recursion difference from Perl" na stronie podręcznika pcrepattern. na przykład: Perl potrafi obsłużyć ^(.|(.)(?1)\2)$
, gdzie PCRE wymaga ^((.)(?1)\2|.)$
.
Recursion Demos
Potrzeba dla rekurencyjnych wzorców powstaje zaskakująco często. Jednym z dobrze odwiedzanych przykładów jest dopasowanie czegoś, co może się zagnieżdżać, takiego jak zrównoważone nawiasy, cudzysłowy, a nawet znaczniki HTML / XML. Oto mecz dla balancerów:
\((?:[^()]*+|(?0))*\)
[15]}uważam, że trudniejsze do odczytania ze względu na jego zwartą naturę. Jest to łatwe do wyleczenia w trybie /x
, aby spacje przestały być znaczące:
\( (?: [^()] *+ | (?0) )* \)
Z drugiej strony, ponieważ używamy parens dla naszej rekurencji, jaśniejszym przykładem może być dopasowanie zagnieżdżonych pojedynczych cudzysłowów:
‘ (?: [^‘’] *+ | (?0) )* ’
Inną rekurencyjnie zdefiniowaną rzeczą, którą możesz chcieć dopasować, będzie palindrom. Ten prosty wzorzec działa w Perlu:
^((.)(?1)\2|.?)$
Które możesz przetestować na większości systemów używając czegoś takiego:
$ perl -nle 'print if /^((.)(?1)\2|.?)$/i' /usr/share/dict/words
Zauważ, że implementacja rekurencji PCRE wymaga bardziej rozbudowanego
^(?:((.)(?1)\2|)|((.)(?3)\4|.))
Jest to spowodowane ograniczeniami w sposobie działania rekurencji PCRE.
Właściwe Parsowanie
Dla mnie powyższe przykłady to głównie zabawkowe mecze, nie wszystkie , które są naprawdę interesujące. Kiedy staje się to interesujące, gdy masz prawdziwą gramatykę, którą próbujesz przeanalizować. Na przykład, RFC 5322 definiuje adres pocztowy dość szczegółowo. Oto wzór "gramatyczny"pasujący do niego:
$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;
Jak widzisz, to bardzo podobne do BNF. Problem w tym, że to tylko dopasowanie, a nie schwytanie. I naprawdę nie chcesz otaczać całej sprawy przechwytywaniem parenów, bo to nie mówi ci, która produkcja pasuje do której części. Używając wcześniej wspomnianego modułu regexp:: Grammars, możemy.
#!/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
}
}
Jak widzisz, używając nieco innej notacji we wzorze, otrzymujesz teraz coś, co przechowuje całe drzewo parse dla ciebie w zmiennej %/
, ze wszystkim starannie oznaczonym. Wynik transformacji jest nadal wzorcem, co widać po operatorze =~
. To trochę magiczne.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-01-30 22:14:09