☰

Existe uma maneira de selecionar a partida mais curta em alternância?

tag-icon • tag-icon awk grep regular-expression
Existe uma maneira de selecionar a partida mais curta em alternância?

Tive a impressão de que grep e awk usavam uma máquina regex NFA (não determinística).
A imagem no meio desta página sobreA correspondência de expressões regulares pode ser simples e rápidaconfirme que esse é o caso.

Sabe-se que uma implementação de NFA pode parar quando a primeira alternância for correspondida. Por exemplo, esta máquina NFA do artigo vinculadoPor exemplo, considere o NFA para abab|abbb:

insira a descrição da imagem aqui

O que corresponde ao regex abab|abbbalcançará o estado correspondente à direita com a string ababbbbao combinar o primeiro abab. Nesse ponto, ele irá parar quando chegar ao fim, para um estado correspondente (S10). Não há necessidade de testar mais entradas, mesmo que outra correspondência abbbseja possível.

Ou seja, neste código:

echo 'catfish' | grep -Eo 'cat|catfish'

O resultado deveria ser, catmas é catfish. Não importa se a alternância é trocada, o resultado é o mesmo.

O que faz o mecanismo grep regex sempre encontrar a correspondência mais longa?

E é possível alterar esse padrão?

Responder1

Eu não acho que exista uma maneira de fazer isso com um compatível com POSIX grepou awk, porque o padrão requer a correspondência mais longa, de fato (veja, por exemplo, a regex(7)página de manual).

Com awkvocê pode obter a saída desejada modificando o awkprograma e o regexp, por exemplo

echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }

Nessa situação, eu procuraria pcregrep(parte da biblioteca de expressões regulares compatível com pcre Perl), que permite especificar um subgrupo numerado com -o:

echo SetValue | pcregrep -o1 '(Set)(Value)?'

ou, porque pcre tem sintaxe para correspondência não gananciosa,

echo SetValue | pcregrep -o0 'Set(Value)??'

Responder2

Até onde pude entender isso, descobri que existem, de fato,duas máquinas NFA:

  • Motor NFA tradicional
    Uma máquina NFA que retrocede e para a quala correspondência mais longa à esquerda nem sempre poderia ser respeitada.

  • Mecanismo POSIX NFA
    Um mecanismo NFA sem retrocesso que processa todos os estados em paralelo e pode escolher qualquer correspondência na string de entrada. A seleção da correspondência mais longa e à esquerda é um requisito do POSIX.

No entanto, uma máquina de retrocesso DFA (Perl) que podeexplodir exponencialmente (2^n)é orientado pelo texto (não pela regex) e pode selecionar o primeiro de uma alternância (ou não).

Diz-se também que umO DFA reconhece todas as correspondências possíveis em paralelo.

E, do autor do artigo vinculado na pergunta, oA implementação de re2 define alternância como: x|y ==> x ou y (prefira x), ou seja: prefira o primeiro de uma alternância.

Portanto, em conclusão, não há como realmente relacionar os AFN ou AFD com qual parte de uma alternância será selecionada, isso depende da implementação específica.

E não, não encontrei uma maneira de dizer a uma implementação específica para alterar seu padrão.

Relacionado:

informação relacionada