Rekursja wzorców
W przypadku wzorców rekurencyjnych masz postać rekursywnego dopasowywania zejść .
Jest to dobre w przypadku różnych problemów, ale gdy chcesz faktycznie przeprowadzić parsowanie rekursywne , musisz wstawić grupy przechwytywania tu i tam, a odzyskanie pełnej struktury analizy w ten sposób jest niewygodne. Moduł Regexp :: Grammars Damiana Conwaya dla Perla przekształca prosty wzorzec w równoważny, który automatycznie wykonuje wszystkie nazwane przechwytywanie w rekursywną strukturę danych, co znacznie ułatwia pobieranie przeanalizowanej struktury. Mam próbkę porównującą te dwa podejścia na końcu tego posta.
Ograniczenia rekursji
Pytanie brzmiało, jakie rodzaje gramatyki mogą pasować do wzorców rekurencyjnych. Cóż, z pewnością są to dopasowujące rekursywne pochodzenie . Jedyną rzeczą, która przychodzi na myśl, jest to, że wzorce rekurencyjne nie radzą sobie z lewą rekurencją . To nakłada ograniczenia na rodzaje gramatyki, do których możesz je zastosować. Czasami możesz zmienić kolejność swoich produkcji, aby wyeliminować lewostronną rekurencję.
BTW, PCRE i Perl różnią się nieco pod względem tego, jak możesz frazować rekursję. Zobacz sekcje „WZORY REKURSYWNE” i „Różnica rekurencji w stosunku do Perla” na stronie podręcznika pcrepattern . np .: Perl może obsłużyć to, ^(.|(.)(?1)\2)$czego wymaga PCRE ^((.)(?1)\2|.)$.
Dema rekurencji
Potrzeba rekurencyjnych wzorców pojawia się zaskakująco często. Jednym z dobrze odwiedzanych przykładów jest sytuacja, w której musisz dopasować coś, co można zagnieździć, na przykład wyważone nawiasy, cudzysłowy, a nawet tagi HTML / XML. Oto mecz dla zbalansowanych parens:
\((?:[^()]*+|(?0))*\)
Uważam, że jest to trudniejsze do odczytania ze względu na jego zwarty charakter. Można to łatwo wyleczyć w /xtrybie, aby białe znaki nie były już istotne:
\( (?: [^()] *+ | (?0) )* \)
Z drugiej strony, ponieważ używamy parens do naszej rekursji, jaśniejszym przykładem byłoby dopasowywanie zagnieżdżonych pojedynczych cudzysłowów:
‘ (?: [^‘’] *+ | (?0) )* ’
Inną zdefiniowaną rekurencyjnie rzeczą, którą możesz chcieć dopasować, byłby 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 rekurencja w PCRE wymaga bardziej skomplikowanych rozwiązań
^(?:((.)(?1)\2|)|((.)(?3)\4|.))
Dzieje się tak z powodu ograniczeń dotyczących działania rekurencji PCRE.
Prawidłowe analizowanie
Dla mnie powyższe przykłady to głównie zapałki zabawek , naprawdę nie wszystkie są tak interesujące. Kiedy staje się interesujący, kiedy masz prawdziwą gramatykę, którą próbujesz przeanalizować. Na przykład RFC 5322 definiuje adres e-mail dość szczegółowo. Oto „gramatyczny” wzorzec pasujący do tego:
$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)+)
(?<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_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 widać, jest to bardzo podobne do BNF. Problem w tym, że to tylko dopasowanie, a nie bicie. I naprawdę nie chcesz po prostu otaczać całości przechwytywaniem parenów, ponieważ to nie mówi ci, która produkcja pasuje do której części. Korzystając ze wspomnianego wcześniej modułu Regexp :: Grammars, możemy.
use strict;
use warnings;
use 5.010;
use Data::Dumper "Dumper";
my $rfc5322 = do {
use Regexp::Grammars;
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>+
<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>)
<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 bardzo nieznacznie innej notacji we wzorcu, otrzymujesz teraz coś, co przechowuje całe drzewo parsowania dla ciebie w %/zmiennej, ze wszystkimi starannie oznaczonymi etykietami. Rezultatem transformacji jest nadal wzór, co widać po =~operatorze. To trochę magiczne.