A aparência afeta quais idiomas podem ser correspondidos por expressões regulares?

Existem alguns resources nos mecanismos de regex modernos que permitem a correspondência de idiomas que não puderam ser correspondidos sem esse recurso. Por exemplo, o seguinte regex usando back references coincide com o idioma de todas as strings que consistem em uma palavra que se repete: (.+)\1 . Essa linguagem não é regular e não pode ser correspondida por um regex que não use referências de retorno.

O lookaround também afeta quais idiomas podem ser correspondidos por uma expressão regular? Ou seja, existem idiomas que podem ser combinados usando um lookaround que não poderia ser comparado de outra forma? Se sim, isso é verdade para todos os sabores de lookaround (lookahead negativo ou positivo ou lookbehind) ou apenas para alguns deles?

Como as outras respostas afirmam, as soluções alternativas não adicionam nenhum poder extra às expressões regulares.

Acho que podemos mostrar isso usando o seguinte:

One Pebble 2-NFA (consulte a seção Introdução do documento que se refere a ele).

O 2-PFA 2NFA não lida com lookaheads nesteds, mas, podemos usar uma variante de 2NFAs multi-pebble (veja a seção abaixo).

Introdução

Um 2-NFA é um autômato finito não determinístico que tem a capacidade de se mover para a esquerda ou para a direita em sua input.

Uma máquina de seixos é onde a máquina pode colocar um seixo na fita de input (ou seja, marcar um símbolo de input específico com um pedregulho) e fazer transições possivelmente diferentes com base em se há uma pedrinha na posição de input atual ou não.

Sabe-se que o One Pebble 2-NFA tem o mesmo poder de um DFA normal.

Lookaheads não nesteds

A ideia básica é a seguinte:

O 2NFA nos permite retroceder (ou ‘track front’) movendo para frente ou para trás na fita de input. Então, para uma olhada antecipada, podemos fazer a correspondência para a expressão regular lookahead e, em seguida, voltar atrás no que consumimos, combinando a expressão lookahead. Para saber exatamente quando parar o retrocesso, usamos o pedregulho! Nós soltamos o pedregulho antes de entrarmos no dfa para marcar o ponto onde o retrocesso precisa parar.

Assim, no final da execução da nossa string através do Pebble 2NFA, sabemos se combinamos ou não com a expressão lookahead e se a input restante (ou seja, o que resta para ser consumido) é exatamente o que é necessário para corresponder ao restante.

Então, para uma olhada antecipada da forma u (? = V) w

Nós temos os DFAs para u, v e w.

Do estado de aceitação (sim, podemos supor que existe apenas um) do DFA para u, fazemos uma transição eletrônica para o estado inicial de v, marcando a input com um seixo.

De um estado de aceitação para v, nós e-transtion para um estado que mantém movendo a input para a esquerda, até encontrar um seixo, e então transita para o estado inicial de w.

A partir de um estado de rejeição de v, fazemos a transição para um estado que continua se movendo para a esquerda até encontrar o seixo, e para o estado de aceitação de u (ou seja, de onde paramos).

A prova usada para NFAs regulares para mostrar r1 | r2, ou r * etc, são transferidos para esses 2nfas de seixo. Consulte http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa para mais informações sobre como as máquinas componentes são montadas para fornecer a máquina maior para a expressão r * etc.

A razão pela qual as provas acima para r * etc funcionam é que o backtracking garante que o ponteiro de input esteja sempre no ponto certo, quando entramos no componente nfas para repetição. Além disso, se um seixo estiver em uso, ele estará sendo processado por uma das máquinas de componente lookahead. Como não há transições da máquina lookahead para a máquina lookahead sem recuar completamente e recuperar o seixo, é necessária apenas uma máquina de cascalho.

Por exemplo, considere ([^ a] | a (? = … b)) *

e a string abbb.

Temos o abbb que atravessa o peb2nfa para um (? = … b), no final do qual estamos no estado: (bbb, correspondido) (isto é, na input bbb está restante, e corresponde a ‘a’ seguido de ‘..b’). Agora, por causa do *, voltamos ao início (veja a construção no link acima) e insira o dfa para [^ a]. Faça a correspondência b, volte ao início, insira [^ a] novamente duas vezes e, em seguida, aceite.

Lidando com Lookaheads nesteds

Para lidar com lookaheads nesteds, podemos usar uma versão restrita do 2NFA do k-pebble, conforme definido aqui: Resultados da Complexidade para Autômatos Bidirecionais e de Múltiplos Seixos e suas Lógicas (consulte a Definição 4.1 e o Teorema 4.2).

Em geral, 2 autômatos de seixo podem aceitar conjuntos não regulares, mas com as seguintes restrições, os autômatos de k-pebble podem ser mostrados como regulares (Teorema 4.2 no papel acima).

Se as pedras são P_1, P_2, …, P_K

  • P_ {i + 1} não pode ser colocado a menos que P_i já esteja na fita e P_ {i} não possa ser selecionado a menos que P_ {i + 1} não esteja na fita. Basicamente, os seixos precisam ser usados ​​de uma maneira LIFO.

  • Entre o momento em que P_ {i + 1} é colocado e o tempo em que P_ {i} é selecionado ou P_ {i + 2} é colocado, o autômato pode percorrer apenas a subalava localizada entre a localização atual de P_ {i} e o final da palavra de input que se encontra na direção de P_ {i + 1}. Além disso, nesta sub-palavra, o autômato pode atuar apenas como um autômato de 1 pebble com Pebble P_ {i + 1}. Em particular, não é permitido levantar, colocar ou até sentir a presença de outra pedra.

Portanto, se v é uma expressão lookahead aninhada de profundidade k, então (? = V) é uma expressão lookahead aninhada de profundidade k + 1. Quando entramos em uma máquina lookahead, sabemos exatamente quantos pedregulhos devem ter sido colocados até o momento e, assim, podemos determinar exatamente qual pedregulho colocar e quando saímos dessa máquina, sabemos qual pedrinha deve ser levantada. Todas as máquinas na profundidade t são inseridas colocando o seixo te saído (isto é, retornamos ao processamento de uma máquina de profundidade t-1) removendo o pedregulho t. Qualquer execução da máquina completa se parece com uma chamada dfs recursiva de uma tree e as duas restrições da máquina multi-seixo acima podem ser atendidas.

Agora, quando você combina expressões, para rr1, desde que você concat, os números de pebble de r1 devem ser incrementados pela profundidade de r. Para r * e r | r1, a numeração de pedra continua a mesma.

Assim, qualquer expressão com lookaheads pode ser convertida em uma máquina multi-pebble equivalente com as restrições acima no posicionamento de pebble e, portanto, é regular.

Conclusão

Isso basicamente aborda a desvantagem na prova original de Francis: ser capaz de evitar que as expressões lookahead consumam tudo o que é necessário para futuras correspondências.

Uma vez que os Lookbehinds são apenas uma string finita (não é realmente regex), podemos lidar com eles primeiro, e depois lidar com as mudanças antecipadas.

Desculpem o writeup incompleto, mas uma prova completa envolveria o desenho de muitas figuras.

Parece certo para mim, mas ficarei feliz em saber de quaisquer erros (que eu pareço gostar de :-)).

A resposta para a pergunta que você faz, ou seja, se uma class maior de linguagens que as linguagens regulares pode ser reconhecida com expressões regulares aumentadas por lookaround, é não.

Uma prova é relativamente simples, mas um algoritmo para traduzir uma expressão regular que contenha lookarounds em um sem é confuso.

Primeiro: note que você sempre pode negar uma expressão regular (sobre um alfabeto finito). Dado um autômato de estado finito que reconhece a linguagem gerada pela expressão, você pode simplesmente trocar todos os estados de aceitação por estados que não aceitam para obter uma FSA que reconheça exatamente a negação daquela linguagem, para a qual há uma família de expressões regulares equivalentes .

Segundo: como as linguagens regulares (e, portanto, as expressões regulares) são fechadas sob a negação, elas também são fechadas na interseção, pois A intersecta B = neg (neg (A) união neg (B)) pelas leis de Morgan. Em outras palavras, com duas expressões regulares, você pode encontrar outra expressão regular que corresponda a ambas.

Isso permite que você simule expressões de referência. Por exemplo, u (? = V) w corresponde apenas às expressões que corresponderão a uv e uw.

Para lookahead negativo, você precisa da expressão regular equivalente à teoria teórica do conjunto A \ B, que é apenas A intersect (nega B) ou equivalentemente neg (neg (A) union B). Assim, para quaisquer expressões regulares r e s, você pode encontrar uma expressão regular rs que corresponda àquelas expressões que correspondam r e que não correspondam s. Em termos de lookahead negativo: u (?! V) w corresponde apenas àquelas expressões que correspondem a uw – uv.

Existem duas razões pelas quais o lookaround é útil.

Primeiro, porque a negação de uma expressão regular pode resultar em algo muito menos arrumado. Por exemplo q(?!u)=q($|[^u]) .

Segundo, expressões regulares fazem mais do que combinar expressões, elas também consomem caracteres de uma string – ou pelo menos é assim que gostamos de pensar nelas. Por exemplo, em python eu me importo com o .start () e .end (), portanto, é claro:

 >>> re.search('q($|[^u])', 'Iraq!').end() 5 >>> re.search('q(?!u)', 'Iraq!').end() 4 

Terceiro, e acho que essa é uma razão muito importante, a negação de expressões regulares não aumenta muito a concatenação. neg (a) neg (b) não é a mesma coisa que neg (ab), o que significa que você não pode traduzir um lookaround fora do contexto em que você o encontra – você tem que processar toda a string. Eu acho que isso torna desagradável para as pessoas trabalharem e quebrarem as intuições das pessoas sobre expressões regulares.

Espero ter respondido à sua pergunta teórica (é tarde da noite, então me perdoe se eu não tiver certeza). Eu concordo com um comentarista que disse que isso tem aplicações práticas. Eu encontrei muito o mesmo problema ao tentar raspar algumas páginas da web muito complicadas.

EDITAR

Minhas desculpas por não ser mais clara: eu não acredito que você possa dar uma prova de regularidade de expressões regulares + lookarounds por indução estrutural, meu u (?! V) exemplo foi destinado a ser apenas isso, um exemplo, e um fácil em que. A razão pela qual uma indução estrutural não funcionará é porque as reações se comportam de uma maneira não-composicional – o ponto que eu estava tentando fazer sobre as negações acima. Eu suspeito que qualquer prova formal direta tenha muitos detalhes confusos. Eu tentei pensar em uma maneira fácil de mostrá-lo, mas não consigo encontrar um em cima da minha cabeça.

Para ilustrar usando o primeiro exemplo de Josh de ^([^a]|(?=..b))*$ isto é equivalente a um 7 estados DFSA com todos os estados aceitando:

 A - (a) -> B - (a) -> C --- (a) --------> D Λ | \ | | (not a) \ (b) | | \ | | v \ v (b) E - (a) -> F \-(not(a)--> G | <- (b) - / | | | | | (not a) | | | | | v | \--------- H <-------------------(b)-----/ 

A expressão regular para o estado A só se parece com:

 ^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$ 

Em outras palavras, qualquer expressão regular que se obtenha eliminando as restrições gerais será, em geral, muito mais longa e muito mais confusa.

Para responder ao comentário de Josh - sim, eu acho que a maneira mais direta de provar a equivalência é através da FSA. O que torna isso mais confuso é que a maneira usual de construir um FSA é através de uma máquina não-determinística - é muito mais fácil expressar como simplesmente a máquina construída a partir de máquinas para u e v com uma transição épsilon para as duas. Claro que isso é equivalente a uma máquina determinista, mas com risco de explosão exponencial de estados. Considerando que a negação é muito mais fácil de fazer através de uma máquina determinista.

A prova geral envolverá a obtenção do produto cartesiano de duas máquinas e a seleção dos estados que você deseja reter em cada ponto em que deseja inserir um lookaround. O exemplo acima ilustra o que quero dizer até certo ponto.

Minhas desculpas por não fornecer uma construção.

EDITAR ADICIONAL: Encontrei uma postagem de blog que descreve um algoritmo para gerar um DFA fora de uma expressão regular aumentada com lookarounds. É interessante porque o autor amplia a ideia de um NFA-e com "transições epsilon marcadas" de maneira óbvia e explica como converter esse autômato em um DFA.

Eu pensei que algo assim seria uma maneira de fazer isso, mas estou satisfeito que alguém tenha escrito isso. Foi além de mim para chegar a algo tão legal.

Eu concordo com os outros posts que lookaround é regular (o que significa que ele não adiciona qualquer capacidade fundamental para expressões regulares), mas eu tenho um argumento para isso que é mais simples IMO do que os outros que tenho visto.

Mostrarei que a solução regular é regular ao fornecer uma construção do DFA. Uma linguagem é regular se e somente se tiver um DFA que a reconheça. Observe que o Perl não usa os DFAs internamente (consulte este documento para obter detalhes: http://swtch.com/~rsc/regexp/regexp1.html ), mas criamos um DFA para fins de prova.

A maneira tradicional de construir um DFA para uma expressão regular é primeiro criar um NFA usando o Algoritmo de Thompson. Dadas duas expressões regulares fragments r1 e r2 , o Algoritmo de Thompson fornece construções para concatenação ( r1r2 ), alternância ( r1|r2 ) e repetição ( r1* ) de expressões regulares. Isso permite que você crie um NFA pouco a pouco que reconheça a expressão regular original. Veja o artigo acima para mais detalhes.

Para mostrar que lookahead positivo e negativo são regulares, fornecerei uma construção para a concatenação de uma expressão regular u com lookahead positivo ou negativo: (?=v) ou (?!v) . Apenas a concatenação requer tratamento especial; as construções usuais de alternância e repetição funcionam bem.

A construção é para ambos u (? = V) e u (?! V) é:

http://imgur.com/ClQpz.png

Em outras palavras, conecte cada estado final do NFA existente para u para um estado de aceitação e para um NFA para v , mas modificado da seguinte maneira. A function f(v) é definida como:

  • Seja aa(v) uma function em um NFA v que altera todo estado de aceitação em um “estado anti-aceitação”. Um estado anti-aceitação é definido como um estado que faz com que a correspondência falhe se qualquer caminho através do NFA terminar nesse estado para uma determinada string s , mesmo que um caminho diferente através de v para s termine em um estado de aceitação.
  • Deixe o loop(v) ser uma function em um NFA v que adiciona uma auto-transição em qualquer estado de aceitação. Em outras palavras, quando um caminho leva a um estado de aceitação, esse caminho pode permanecer no estado de aceitação para sempre, independentemente da input que segue.
  • Para lookahead negativo, f(v) = aa(loop(v)) .
  • Para lookahead positivo, f(v) = aa(neg(v)) .

Para fornecer um exemplo intuitivo de por que isso funciona, usarei o regex (b|a(?:.b))+ , que é uma versão ligeiramente simplificada do regex que propus nos comentários da prova de Francis. Se usarmos a minha construção junto com as construções tradicionais de Thompson, acabaremos com:

texto alternativo

Os e s são transições epsilon (transições que podem ser tomadas sem consumir qualquer input) e os estados anti-aceitação são rotulados com um X Na metade esquerda do gráfico você vê a representação de (a|b)+ : qualquer a ou b coloca o gráfico em um estado de aceitação, mas também permite uma transição de volta para o estado inicial para que possamos fazê-lo novamente. Mas observe que, toda vez que combinamos com um a , também entramos na metade direita do gráfico, onde estamos em estados de anti-aceitação até correspondermos a “any” seguido de b .

Este não é um NFA tradicional porque os NFAs tradicionais não têm estados anti-aceitação. No entanto, podemos usar o algoritmo tradicional NFA-> DFA para converter isso em um DFA tradicional. O algoritmo funciona normalmente, onde simulamos várias execuções do NFA fazendo com que nossos estados DFA correspondam a subconjuntos dos estados NFA nos quais poderíamos estar. A única diferença é que aumentamos ligeiramente a regra para decidir se um estado DFA é um aceitar estado (final) ou não. No algoritmo tradicional, um estado do DFA é um estado de aceitação se algum dos estados do NFA for um estado de aceitação. Modificamos isso para dizer que um estado do DFA é um estado de aceitação se e somente se:

  • = 1 estados NFA é um estado de aceitação e

  • 0 estados de NFA são estados de anti-aceitação.

Esse algoritmo nos dará um DFA que reconhece a expressão regular com lookahead. Ergo, lookahead é regular. Note que lookbehind requer uma prova separada.

Tenho a sensação de que há duas perguntas distintas sendo feitas aqui:

  • Os mecanismos de regex que incorporam “lookaround” são mais poderosos que os mecanismos de regex que não o fazem?
  • O “lookaround” habilita um mecanismo Regex com a capacidade de analisar linguagens que são mais complexas do que aquelas geradas a partir de uma gramática Chomsky Type 3 – Regular ?

A resposta para a primeira questão em um sentido prático é sim. Lookaround dará um mecanismo Regex que usa esse recurso fundamentalmente mais poder do que um que não usa. Isso porque fornece um conjunto mais rico de “âncoras” para o processo de correspondência. Lookaround permite que você defina um Regex inteiro como um possível ponto de ancoragem (asserção de largura zero). Você pode obter uma boa visão geral do poder desse recurso aqui .

Lookaround, embora poderoso, não eleva o mecanismo Regex além dos limites teóricos colocados nele por uma Gramática Tipo 3. Por exemplo, você nunca poderá analisar com segurança um idioma baseado em uma Gramática de Contexto Livre – Tipo 2 usando um mecanismo de Regex equipado com a aparência. Mecanismos Regex são limitados ao poder de uma Automação de Estado Finito e isto fundamentalmente restringe a expressividade de qualquer linguagem que eles possam analisar no nível de uma Gramática Tipo 3. Não importa quantos “truques” sejam adicionados ao seu mecanismo Regex, os idiomas gerados por meio de uma Gramática Livre de Contexto permanecerão sempre além de suas capacidades. Parsing Context Free – A gramática do tipo 2 requer que a automação de empilhamento “lembre” onde está em uma construção de linguagem recursiva. Qualquer coisa que requeira uma avaliação recursiva das regras gramaticais não pode ser analisada usando os mecanismos do Regex.

Resumindo: o Lookaround fornece alguns benefícios práticos para os mecanismos do Regex, mas não “altera o jogo” em um nível teórico.

EDITAR

Existe alguma gramática com complexidade em algum lugar entre Tipo 3 (Regular) e Tipo 2 (Contexto Livre)?

Eu acredito que a resposta é não. A razão é porque não há limite teórico para o tamanho do NFA / DFA necessário para descrever uma linguagem regular. Pode se tornar arbitrariamente grande e, portanto, impraticável de usar (ou especificar). É aqui que os desvios, como “lookaround”, são úteis. Eles fornecem um mecanismo curto para especificar o que, de outra forma, levaria a especificações NFA / DFA muito grandes / complexas. Eles não aumentam a expressividade das linguagens regulares, apenas tornam a especificação mais prática. Uma vez que você chegar a esse ponto, fica claro que existem muitos “resources” que poderiam ser adicionados aos mecanismos do Regex para torná-los mais úteis em um sentido prático – mas nada os tornará capazes de ir além dos limites de uma linguagem Regular. .

A diferença básica entre uma linguagem Regular e uma linguagem Livre de Contexto é que uma linguagem Regular não contém elementos recursivos. Para avaliar uma linguagem recursiva, você precisa de uma Automação Push Down para “lembrar” onde você está na recursion. Um NFA / DFA não empilha informações de estado, portanto, não pode manipular a recursion. Assim, dada uma definição de linguagem não recursiva, haverá algum NFA / DFA (mas não necessariamente uma expressão prática de Regex) para descrevê-lo.

    Intereting Posts