Expressões regulares e 'captura de parênteses' com 'referências anteriores'

7

Sabemos que expressões regulares (ER) são implementadas com autômatos finitos (FA). Em alguma linguagem (como JavaScript) no RE, existem recursos como 'capturando parênteses' com 'referências anteriores':

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions#special-capturing-parentheses

(x) Corresponde a 'x' e se lembra da correspondência, como mostra o exemplo a seguir. Os parênteses são chamados de captura de parênteses. Os '(foo)' e '(bar)' no padrão / (foo) (bar) \ 1 \ 2 / correspondem e lembre-se das duas primeiras palavras da string "foo bar foo bar". O \ 1 e \ 2 no padrão correspondem às duas últimas palavras da sequência.

Quero saber se esse padrão /(foo) (bar) \1 \2/é de fato um ER de acordo com a definição de ER que temos na linguagem formal teórica ou se é algo mais poderoso. E se é assim, eu gostaria de saber se esse tipo de recurso é implementado também com a FA ou de outra maneira (em particular como é implementado).

asv
fonte
Consulte swtch.com/~rsc/regexp/regexp1.html para obter uma excelente descrição das implicações dessa diferença no desempenho no mundo real (nível de implementação). (Edit: Vejo que ele já foi vinculado a esta resposta .) #
Wildcard

Respostas:

7

O ER na teoria dos autômatos é equivalente ao FA, mas para as linguagens de programação (regexp) isso não é mais verdade.

As expressões regulares nas linguagens de programação (como PCRE) são muito mais poderosas que as Expressões regulares (tipo 3) na Teoria dos Automata.

O parêntese correspondente não é regular nem isento de contexto, é um recurso sensível ao contexto. Mas o RegExp da pergunta não suporta totalmente o Tipo 2 ou o Tipo 1.

A correspondência de colchetes não é implementada via FA. No caso do PCRE, é implementado por adivinhação e retorno.

Dê uma olhada na descrição do Perl Monks sobre o PCRE .

Mal
fonte
Obrigado. Nesse caso, o RegExp é um abuso de linguagem (formal).
23/01
5
Bem, é o nome da colisão. A idéia inicial era algo como RE, mas mesmo quando evoluiu, o nome permaneceu.
mal
11
@ asv: Por algum tempo após a introdução da captura, o ER com grupos de captura foi chamado regexp estendido ou ERE. Então, por algum tempo após o Perl apresentar sua versão do RE, ele foi chamado de regex para diferenciá-lo do regexp padronizado POSIX e do ERE (note regexp vs regexp). Hoje em dia as pessoas não se importam.
precisa saber é
9

Essas noções estendidas de expressões regulares capturam mais do que apenas as linguagens regulares. Por exemplo, ([ab]*)\1corresponde ao idioma , que não é regular e nem sequer é livre de contexto (Exemplo 2.38 de Sipser, Introdução à teoria de Computação , 3ª edição).{www{a,b}}

Expressões "regulares" que não correspondem a idiomas regulares não podem ser traduzidas para autômatos finitos, pois os autômatos finitos correspondem apenas aos idiomas regulares. Um efeito colateral disso é que muitas bibliotecas nem tentam compilar para automatizar, o que pode levar a uma correspondência extremamente lenta, mesmo quando uma expressão "regular" é uma expressão regular verdadeira. Russ Cox escreveu um excelente artigo sobre isso, que também se passa em grande parte da história.

David Richerby
fonte
Obrigado pelo seu exemplo e por essas informações. :)
asv
8

As respostas provavelmente estão respondendo ao que você pretende perguntar, mas não ao que está perguntando.

Quero saber se esse padrão /(foo) (bar) \1 \2/é de fato um ER de acordo com a definição de ER que temos na linguagem formal teórica ou se é algo mais poderoso. E se é assim, eu gostaria de saber se esse tipo de recurso é implementado também com a FA ou de outra maneira (em particular como é implementado).

Na verdade, esta é uma expressão regular que pode ser implementado com um autômato finito, porque \1é garantida para avaliar a fooe \2está garantido para avaliar a bar.

Portanto, um mecanismo de expressão regular poderia usar esse fato para criar um autômato finito que descreve exatamente o idioma que você propôs.

No entanto, se você condicionar as capturas , isso poderá se tornar falso, como outros já mencionaram.

(Observe que eu digo que você pode ter problemas, porque um idioma como ainda/(a(aa|aa)|(aa|aa)a)\1\2/ pode ser descrito por meio de uma FA. Eu apenas lhe dei uma condição necessária, e não suficiente. Edit: Apenas me ocorreu que ter uma condicional não é necessário nem necessário. suficiente, como também pode ser transformado em um autômato finito, embora não possa. /(a*)\1//(ab*)\1/

user541686
fonte
Ok, algum padrão particular com 'captura de parênteses' pode ser RE. Boa observação.
Asv
@ asv: Sim. Além disso, acho que outra coisa enganosa sobre todas as respostas aqui (incluindo a minha) é que o problema não é os parênteses de captura, mas as referências anteriores que se referem a elas. Lembro-me de ler que a captura de parênteses pode ser tratada sem retroceder, desde que não haja referências de retorno. No entanto, não sei os detalhes por trás disso se isso pode realmente ser feito usando autômatos finitos ou não (minha impressão é que pode, mas não sei exatamente como). Mas deve haver outras maneiras de lidar com eles sem retroceder, como via análise de LR ou algo parecido.
user541686
Sim, a questão é: backreferences
asv
0

Determinada implementação de regex não cria um DFA. Por exemplo, a implementação do java.util.regex OpenJDK não. Como resultado, seu tempo de correspondência é mais lento que a implementação compilada pelo DFA, como dk.brics.automaton . No entanto, o posterior não suporta a captura de grupo como resultado da implementação subjacente.

vuamitom
fonte
Lembre-se de que a construção de NFA-> DFA pode ser muito cara (2 ^ # nós).
Mevets
Ah, sim, obrigado por apontar isso. Atualizei minha resposta para refletir que apenas o tempo correspondente do impl impl baseado no DFA é menor.
vuamitom