Por que você não pode usar quantificadores de repetição na aparência de largura zero atrás de asserções?

Eu sempre tive a impressão de que você não poderia usar quantificadores de repetição em assertivas de largura zero (expressões regulares compatíveis com Perl [PCRE]). No entanto, recentemente me ocorreu que você pode usá-los em declarações antecipadas.

Então minha pergunta é:

Como o mecanismo de regex do PCRE funciona ao pesquisar com uma aparência de largura zero, o que impede a utilização de quantificadores de repetição?

Aqui está um exemplo simples de um PCRE em R:

# Our string x <- 'MaaabcccM' ## Does it contain a 'b', preceeded by an 'a' and followed by zero or more 'c', ## then an 'M'? grepl( '(?<=a)b(?=c*M)' , x , perl=T ) # [1] TRUE ## Does it contain a 'b': (1) preceeded by an 'M' and then zero or more 'a' and ## (2) followed by zero or more 'c' then an 'M'? grepl( '(?<=Ma*)b(?=c*M)' , x , perl = TRUE ) # Error in grepl("(?<=Ma*)b(?=c*M)", x, perl = TRUE) : # invalid regular expression '(?<M=a*)b(?=c*M)' # In addition: Warning message: # In grepl("(?<=Ma*)b(?=c*M)", x, perl = TRUE) : PCRE pattern compilation error # 'lookbehind assertion is not fixed length' # at ')b(?=c*M)' 

A resposta final para essa pergunta está no código do mecanismo e, na parte inferior da resposta, você será capaz de mergulhar na seção do código do mecanismo PCRE responsável por garantir o comprimento fixo em lookbehinds – se você estiver interessado em Conhecendo os melhores detalhes. Enquanto isso, vamos gradualmente ampliar a questão de níveis mais altos.

Lookbehind de largura variável versus Lookbehind de largura infinita

Primeiramente, um rápido esclarecimento sobre os termos. Um número crescente de mecanismos (incluindo o PCRE) suporta alguma forma de lookbehind de largura variável, onde a variação cai dentro de um determinado intervalo, por exemplo:

  • o mecanismo sabe que a largura do que precede deve estar entre 5 e 10 caracteres (não suportado no PCRE)
  • o mecanismo sabe que a largura do que precede deve ser de 5 ou 10 caracteres (com suporte no PCRE)

Em contraste, em lookbehind de largura infinita, você pode usar tokens quantificados como a+

Motores que suportam Lookbehind de largura infinita

Para o registro, esses mecanismos suportam lookbehind infinito:

  • .NET (c #, vb.net etc.)
  • Módulo de regex Matthew Barnett para Python
  • JGSoft (EditPad etc .; não disponível em uma linguagem de programação).

Tanto quanto eu sei, eles são os únicos.

Variável Lookbehind em PCRE

No PCRE, a seção mais relevante na documentação é esta:

O conteúdo de uma declaração lookbehind é restrito, de forma que todas as strings correspondentes devem ter um tamanho fixo. No entanto, se houver várias alternativas de nível superior, elas não precisam ter o mesmo tamanho fixo.

Portanto, o seguinte lookbehind é válido:

 (?<=a |big )cat 

No entanto, nenhum destes são:

  • (?<=a\s?|big )cat (os lados da alternação não têm largura fixa)
  • (?<=@{1,10})cat (largura variável)
  • (?<=\R)cat ( \R não tem largura fixa, pois pode corresponder a \n , \r\n , etc.)
  • (?<=\X)cat ( \X não tem uma largura fixa como um cluster de grafema Unicode pode conter um número variável de bytes.)
  • (?<=a+)cat (claramente não corrigido)

Lookbehind com correspondência de largura zero, mas repetição infinita

Agora considere isto:

 (?<=(?=@+))(cat#+) 

Em face disto, este é um lookbehind de largura fixa, porque ele só pode encontrar uma correspondência de largura zero (definida pelo lookahead (?=@++) ). Isso é um truque para contornar a limitação infinita do lookbehind?

Não. O PCRE vai se engasgar com isso. Mesmo que o conteúdo do lookbehind seja de largura zero, o PCRE não permitirá repetição infinita no lookbehind. Qualquer lugar. Quando a documentação diz que todas as strings correspondentes devem ter um tamanho fixo, elas devem ser:

Todas as cadeias de caracteres que qualquer um dos seus componentes correspondem devem ter um comprimento fixo.

Soluções alternativas: vida sem Lookbehind infinito

No PCRE, as duas principais soluções para problemas onde os lookbehinds infinitos ajudariam são \K e grupos de captura.

Solução nº 1: \K

A declaração \K diz ao mecanismo para descartar o que foi correspondido até o final da correspondência final retornada.

Suponha que você queira (?<=@+)cat#+ , o que não é legal em PCRE. Em vez disso, você pode usar:

 @+\Kcat#+ 

Solução 2: grupos de captura

Outra maneira de proceder é combinar com o que você teria colocado em um lookbehind e capturar o conteúdo de interesse em um grupo de captura. Você então recupera a correspondência do grupo de captura.

Por exemplo, em vez do (?<=@+)cat#+ ilegal (?<=@+)cat#+ , Você usaria:

 @+(cat#+) 

Em R, isso poderia ser assim:

 matches <- regexpr("@+(cat#+)", subject, perl=TRUE); result <- attr(matches, "capture.start")[,1] attr(result, "match.length") <- attr(matches, "capture.length")[,1] regmatches(subject, result) 

Em idiomas que não suportam \K , esta é frequentemente a única solução.

Internos do motor: o que o código PCRE diz?

A resposta final pode ser encontrada em pcre_compile.c . Se você examinar o bloco de código que começa com este comentário:

Se lookbehind, verifique se este ramo corresponde a uma cadeia de comprimento fixo

Você acha que o trabalho pesado é feito pela function find_fixedlength() .

Eu reproduzo aqui para qualquer um que queira mergulhar em mais detalhes.

 static int find_fixedlength(pcre_uchar *code, BOOL utf, BOOL atend, compile_data *cd) { int length = -1; register int branchlength = 0; register pcre_uchar *cc = code + 1 + LINK_SIZE; /* Scan along the opcodes for this branch. If we get to the end of the branch, check the length against that of the other branches. */ for (;;) { int d; pcre_uchar *ce, *cs; register pcre_uchar op = *cc; switch (op) { /* We only need to continue for OP_CBRA (normal capturing bracket) and OP_BRA (normal non-capturing bracket) because the other variants of these opcodes are all concerned with unlimited repeated groups, which of course are not of fixed length. */ case OP_CBRA: case OP_BRA: case OP_ONCE: case OP_ONCE_NC: case OP_COND: d = find_fixedlength(cc + ((op == OP_CBRA)? IMM2_SIZE : 0), utf, atend, cd); if (d < 0) return d; branchlength += d; do cc += GET(cc, 1); while (*cc == OP_ALT); cc += 1 + LINK_SIZE; break; /* Reached end of a branch; if it's a ket it is the end of a nested call. If it's ALT it is an alternation in a nested call. An ACCEPT is effectively an ALT. If it is END it's the end of the outer call. All can be handled by the same code. Note that we must not include the OP_KETRxxx opcodes here, because they all imply an unlimited repeat. */ case OP_ALT: case OP_KET: case OP_END: case OP_ACCEPT: case OP_ASSERT_ACCEPT: if (length < 0) length = branchlength; else if (length != branchlength) return -1; if (*cc != OP_ALT) return length; cc += 1 + LINK_SIZE; branchlength = 0; break; /* A true recursion implies not fixed length, but a subroutine call may be OK. If the subroutine is a forward reference, we can't deal with it until the end of the pattern, so return -3. */ case OP_RECURSE: if (!atend) return -3; cs = ce = (pcre_uchar *)cd->start_code + GET(cc, 1); /* Start subpattern */ do ce += GET(ce, 1); while (*ce == OP_ALT); /* End subpattern */ if (cc > cs && cc < ce) return -1; /* Recursion */ d = find_fixedlength(cs + IMM2_SIZE, utf, atend, cd); if (d < 0) return d; branchlength += d; cc += 1 + LINK_SIZE; break; /* Skip over assertive subpatterns */ case OP_ASSERT: case OP_ASSERT_NOT: case OP_ASSERTBACK: case OP_ASSERTBACK_NOT: do cc += GET(cc, 1); while (*cc == OP_ALT); cc += PRIV(OP_lengths)[*cc]; break; /* Skip over things that don't match chars */ case OP_MARK: case OP_PRUNE_ARG: case OP_SKIP_ARG: case OP_THEN_ARG: cc += cc[1] + PRIV(OP_lengths)[*cc]; break; case OP_CALLOUT: case OP_CIRC: case OP_CIRCM: case OP_CLOSE: case OP_COMMIT: case OP_CREF: case OP_DEF: case OP_DNCREF: case OP_DNRREF: case OP_DOLL: case OP_DOLLM: case OP_EOD: case OP_EODN: case OP_FAIL: case OP_NOT_WORD_BOUNDARY: case OP_PRUNE: case OP_REVERSE: case OP_RREF: case OP_SET_SOM: case OP_SKIP: case OP_SOD: case OP_SOM: case OP_THEN: case OP_WORD_BOUNDARY: cc += PRIV(OP_lengths)[*cc]; break; /* Handle literal characters */ case OP_CHAR: case OP_CHARI: case OP_NOT: case OP_NOTI: branchlength++; cc += 2; #ifdef SUPPORT_UTF if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]); #endif break; /* Handle exact repetitions. The count is already in characters, but we need to skip over a multibyte character in UTF8 mode. */ case OP_EXACT: case OP_EXACTI: case OP_NOTEXACT: case OP_NOTEXACTI: branchlength += (int)GET2(cc,1); cc += 2 + IMM2_SIZE; #ifdef SUPPORT_UTF if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]); #endif break; case OP_TYPEEXACT: branchlength += GET2(cc,1); if (cc[1 + IMM2_SIZE] == OP_PROP || cc[1 + IMM2_SIZE] == OP_NOTPROP) cc += 2; cc += 1 + IMM2_SIZE + 1; break; /* Handle single-char matchers */ case OP_PROP: case OP_NOTPROP: cc += 2; /* Fall through */ case OP_HSPACE: case OP_VSPACE: case OP_NOT_HSPACE: case OP_NOT_VSPACE: case OP_NOT_DIGIT: case OP_DIGIT: case OP_NOT_WHITESPACE: case OP_WHITESPACE: case OP_NOT_WORDCHAR: case OP_WORDCHAR: case OP_ANY: case OP_ALLANY: branchlength++; cc++; break; /* The single-byte matcher isn't allowed. This only happens in UTF-8 mode; otherwise \C is coded as OP_ALLANY. */ case OP_ANYBYTE: return -2; /* Check a class for variable quantification */ case OP_CLASS: case OP_NCLASS: #if defined SUPPORT_UTF || defined COMPILE_PCRE16 || defined COMPILE_PCRE32 case OP_XCLASS: /* The original code caused an unsigned overflow in 64 bit systems, so now we use a conditional statement. */ if (op == OP_XCLASS) cc += GET(cc, 1); else cc += PRIV(OP_lengths)[OP_CLASS]; #else cc += PRIV(OP_lengths)[OP_CLASS]; #endif switch (*cc) { case OP_CRSTAR: case OP_CRMINSTAR: case OP_CRPLUS: case OP_CRMINPLUS: case OP_CRQUERY: case OP_CRMINQUERY: case OP_CRPOSSTAR: case OP_CRPOSPLUS: case OP_CRPOSQUERY: return -1; case OP_CRRANGE: case OP_CRMINRANGE: case OP_CRPOSRANGE: if (GET2(cc,1) != GET2(cc,1+IMM2_SIZE)) return -1; branchlength += (int)GET2(cc,1); cc += 1 + 2 * IMM2_SIZE; break; default: branchlength++; } break; /* Anything else is variable length */ case OP_ANYNL: case OP_BRAMINZERO: case OP_BRAPOS: case OP_BRAPOSZERO: case OP_BRAZERO: case OP_CBRAPOS: case OP_EXTUNI: case OP_KETRMAX: case OP_KETRMIN: case OP_KETRPOS: case OP_MINPLUS: case OP_MINPLUSI: case OP_MINQUERY: case OP_MINQUERYI: case OP_MINSTAR: case OP_MINSTARI: case OP_MINUPTO: case OP_MINUPTOI: case OP_NOTMINPLUS: case OP_NOTMINPLUSI: case OP_NOTMINQUERY: case OP_NOTMINQUERYI: case OP_NOTMINSTAR: case OP_NOTMINSTARI: case OP_NOTMINUPTO: case OP_NOTMINUPTOI: case OP_NOTPLUS: case OP_NOTPLUSI: case OP_NOTPOSPLUS: case OP_NOTPOSPLUSI: case OP_NOTPOSQUERY: case OP_NOTPOSQUERYI: case OP_NOTPOSSTAR: case OP_NOTPOSSTARI: case OP_NOTPOSUPTO: case OP_NOTPOSUPTOI: case OP_NOTQUERY: case OP_NOTQUERYI: case OP_NOTSTAR: case OP_NOTSTARI: case OP_NOTUPTO: case OP_NOTUPTOI: case OP_PLUS: case OP_PLUSI: case OP_POSPLUS: case OP_POSPLUSI: case OP_POSQUERY: case OP_POSQUERYI: case OP_POSSTAR: case OP_POSSTARI: case OP_POSUPTO: case OP_POSUPTOI: case OP_QUERY: case OP_QUERYI: case OP_REF: case OP_REFI: case OP_DNREF: case OP_DNREFI: case OP_SBRA: case OP_SBRAPOS: case OP_SCBRA: case OP_SCBRAPOS: case OP_SCOND: case OP_SKIPZERO: case OP_STAR: case OP_STARI: case OP_TYPEMINPLUS: case OP_TYPEMINQUERY: case OP_TYPEMINSTAR: case OP_TYPEMINUPTO: case OP_TYPEPLUS: case OP_TYPEPOSPLUS: case OP_TYPEPOSQUERY: case OP_TYPEPOSSTAR: case OP_TYPEPOSUPTO: case OP_TYPEQUERY: case OP_TYPESTAR: case OP_TYPEUPTO: case OP_UPTO: case OP_UPTOI: return -1; /* Catch unrecognized opcodes so that when new ones are added they are not forgotten, as has happened in the past. */ default: return -4; } } /* Control never gets here */ } 

Motores Regex são projetados para funcionar da esquerda para a direita .

Para lookaheads, o mecanismo corresponde ao texto inteiro à direita da posição atual. No entanto, para lookbehinds, o mecanismo regex determina o comprimento da string para voltar atrás e, em seguida, verifica a correspondência (novamente da esquerda para a direita).

Portanto, se você fornecer alguns quantificadores infinitos como * ou + , o lookbehind não funcionará porque o mecanismo não sabe quantos passos devem ser feitos para trás.

Vou dar um exemplo de como lookbehind funciona (o exemplo é bem bobo).

Suponha que você queira corresponder ao sobrenome Panta , somente se o primeiro nome tiver 5-7 caracteres de comprimento.

Vamos pegar a string:

 Full name is Subigya Panta. 

Considere o regex:

 (?<=\b\w{5,7}\b)\sPanta 

Como o motor funciona

O mecanismo reconhece a existência de um lookbehind positivo e, portanto, primeiro procura pela palavra Panta (com um caractere de espaço em branco antes dele). É um jogo.

Agora, o motor parece combinar com o regex dentro do lookbehind. Ele recua 7 caracteres (como o quantificador é ganancioso). O limite da palavra corresponde à posição entre espaço e S Em seguida, ele corresponde a todos os 7 caracteres e, em seguida, o próximo limite da palavra corresponde à posição entre a e o espaço.

O regex dentro do lookbehind é uma correspondência e, portanto, o regex inteiro retorna true porque a string correspondente contém Panta . (Observe que as asserções de lookaround são de largura zero e não consomem nenhum caractere.)

A página do manual pcrepattern documenta a restrição que as asserções lookbehind devem ser de largura fixa ou ter vários padrões de largura fixa separados por | e, em seguida, explica que isso é porque:

A implementação de asserções lookbehind é, para cada alternativa, mover temporariamente a posição atual de volta pelo comprimento fixo e então tentar corresponder. Se houver caracteres insuficientes antes da posição atual, a declaração falhará.

Eu não sei por que eles fazem isso dessa maneira, mas meu palpite é que eles gastaram muito tempo escrevendo um bom mecanismo de RE-matching que avança, e eles não queriam duplicar todo esse esforço para escrever outro que corre para trás. A abordagem óbvia seria passar por cima da corda para trás – o que é fácil – enquanto combina uma versão “reversa” da sua afirmação lookbehind. É possível inverter um RE “real” (DFA-matchable) – o verso de um idioma regular é um idioma regular – mas os ERs “estendidos” do PCRE são IIRC turing completos, e talvez nem seja possível virar um para correr para trás de forma eficiente em geral. E mesmo se fosse, provavelmente ninguém se importou o suficiente para se preocupar. Afinal, olhar para trás afirmações são uma característica muito pequena no grande esquema das coisas.

Intereting Posts