Como simular referências anteriores, lookaheads e lookbehinds em autômatos de estados finitos?

Criei uma expressão regular simples lexer e analisador para obter uma expressão regular e gerar sua árvore de análise. Criar um autômato de estado finito não determinístico a partir desta árvore de análise é relativamente simples para expressões regulares básicas. No entanto, parece que não consigo entender como simular referências anteriores, visões e visões atrás.

Pelo que li no livro do dragão roxo, entendi que para simular um lookahead que a expressão regular é correspondida se e somente se a correspondência for seguida por uma correspondência da expressão regular , você cria um finito não determinístico autômato de estado no qual é substituído por . É possível criar um autômato de estado finito determinístico que faz o mesmo?$r/s$$r$$s$$/$$\varepsilon$

Que tal simular olhares negativos e olhares negativos? Eu realmente aprecio isso se você me vincular a um recurso que descreve como fazer isso em detalhes.

Em primeiro lugar, as referências anteriores não podem ser simuladas por autômatos finitos, pois permitem descrever idiomas não regulares. Por exemplo, ([ab]^*)\1corresponde a , que nem sequer é livre de contexto.$\{ww \mid w \in \{a,b\}^*\}$

O olhar à frente e o olhar para trás não são nada de especial no mundo dos autômatos finitos, uma vez que apenas combinamos entradas inteiras aqui. Portanto, a semântica especial de "apenas verifique, mas não consuma" não tem sentido; você apenas concatena e / ou cruza a verificação e o consumo de expressões e usa os autômatos resultantes. A idéia é verificar as expressões antecipadas ou atrasadas enquanto você "consome" a entrada e armazena o resultado em um estado.

Ao implementar regexps, você deseja executar a entrada por meio de um autômato e recuperar os índices de início e fim das correspondências. Essa é uma tarefa muito diferente, portanto não há realmente uma construção para autômatos finitos. Você constrói seu autômato como se a expressão look-ahead ou look-behind estivesse consumindo e altera seu respetivo índice de armazenamento. relatórios em conformidade.

Tome, por exemplo, olhar para trás. Podemos imitar a semântica do regexp executando a verificação regexp simultaneamente ao regexp "match-all" implicitamente consumido. somente de estados onde o autômato da expressão de look-behind está em um estado final é que o autômato da expressão protegida pode ser inserido. Por exemplo, o regexp /(?=c)[ab]+/(assumindo que é o alfabeto completo) - observe que ele se traduz na expressão regular - pode ser correspondido por$\{a,b,c\}$$\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$

^{[ fonte ]}

e você teria que

• armazene o índice atual como sempre que você inserir (inicialmente ou a partir de ) e$i$$q_2$$q_2$
• relate uma correspondência (máxima) de ao índice atual ( ) sempre que você pressionar (sair) .$i$$-1$$q_2$

Observe como a parte esquerda do autômato é o autômato paralelo dos autômatos canônicos para [abc]*e c(iterado), respectivamente.

O futuro pode ser tratado da mesma forma; você precisa se lembrar do índice ao inserir o autômato "principal", do índice quando sair do autômato principal e do autômato antecipado e relatar uma correspondência de a somente quando atingir o final do autômato antecipado Estado.$i$$j$$i$$j$

Observe que o não-determinismo é inerente a isso: o autômato principal e o futuro / atrás podem se sobrepor; portanto, você deve armazenar todas as transições entre elas para relatar as correspondentes posteriormente ou voltar atrás.

A referência autorizada sobre questões pragmáticas por trás da implementação de mecanismos de expressão regular é uma série de três postagens de blog de Russ Cox . Conforme descrito lá, como as referências anteriores tornam seu idioma não regular, elas são implementadas usando o retorno .

Lookaheads e lookbehinds, como muitos recursos dos mecanismos de correspondência de padrões regex, não se encaixam no paradigma de decidir se uma string é ou não membro de um idioma ou não. Em vez de regexes, geralmente procuramos substrings dentro de uma string maior. As "correspondências" são substrings que são membros do idioma e o valor de retorno são os pontos inicial e final da substring na cadeia maior.

O objetivo de olhar para trás e olhar para trás não é tanto introduzir a capacidade de combinar idiomas não regulares, mas sim ajustar o local em que o mecanismo relata os pontos inicial e final da substring correspondente.

Estou contando com a descrição em http://www.regular-expressions.info/lookaround.html . Os mecanismos de expressão regular que suportam esse recurso (Perl, TCL, Python, Ruby, ...) parecem basear-se no retorno (ou seja, eles suportam um conjunto muito maior de idiomas do que apenas os idiomas regulares). Eles parecem estar implementando esse recurso como uma extensão relativamente "simples" do retorno, em vez de tentar construir autômatos finitos reais para executar a tarefa.

Lookahead positivo

A sintaxe da aparência positiva é (?=regex) . Portanto, por exemplo, q(?=u)corresponde qapenas se for seguido por u, mas não corresponde a u. Eu imagino que eles implementem isso com uma variação no retorno. Crie um FSM para a expressão antes da aparência positiva. Quando isso corresponder, lembre-se de onde terminou e inicie um novo FSM que representa a expressão dentro da cabeça positiva. Se isso corresponder, você terá uma "correspondência", mas a correspondência "terminará" imediatamente antes da posição em que a correspondência positiva do lookahead começou.

A única parte disso que seria difícil sem retroceder é que você precisa se lembrar do ponto da entrada em que o cabeçote inicia e mover a fita de entrada de volta para esta posição depois de terminar a partida.

Lookahead negativo

A sintaxe para lookahead negativo é (?!regex) . Portanto, por exemplo, q(?!u)corresponde qapenas se não for seguido por u. Pode ser um qseguido por outro caractere ou um qno final da string. Eu imagino que isso seja implementado criando um NFA para a expressão lookahead, tendo êxito apenas se o NFA falhar na correspondência com a sequência subsequente.

Se você quiser fazê-lo sem depender de voltar atrás, poderá negar o NFA da expressão lookahead, então trate-o da mesma maneira que você trata lookahead positivo.

Lookbehind positivo

(?<=)(?=q)uuqq$n$$n$$n$

Você pode implementar isso sem retroceder fazendo a interseção de "string que termina com regex " com qualquer parte do regex que vem antes do operador lookbehind. Isso vai ser complicado, porque o regex que está por trás pode precisar olhar mais para trás do que o início atual da entrada.

Lookbehind negativo

A sintaxe para lookbehind negativo é (?<!regex) . Assim, por exemplo, (?<!q)ucorresponde u, mas apenas se não for precedido por q. Portanto, combinaria o uin umbrellae o uin doubt, mas não o uin quick. Novamente, isso parece ser feito calculando o comprimento da regex , fazendo o backup de muitos caracteres, testando a correspondência com a regex , mas agora falhando a correspondência inteira se o lookbehind corresponder.

Você pode implementar isso sem retroceder tomando a negação do regex e fazendo o mesmo que faria para olhar para trás.

Pelo menos para referências anteriores, isso não é possível. Por exemplo, o regex (.*)\1representa um idioma que não é regular. O que isso significa é que é impossível criar um autômato finito (determinístico ou não) que reconheceria essa linguagem. Se você quiser provar isso formalmente, poderá usar o lema de bombeamento .

Eu mesmo estive investigando isso, e você deve implementar o lookahead usando um autômato finito alternado . Quando você encontra um lookahead, executa indeterminadamente o lookahead e o restante da expressão, aceitando apenas se os dois caminhos aceitarem. Você pode converter um AFA em um NFA com ampliação razoável (e, portanto, em um DFA), embora eu não tenha verificado que a construção óbvia funciona bem com os grupos de captura.

O lookbehind de largura fixa deve ser perfeitamente possível sem retroceder. Seja n a largura. A partir do ponto da NFA em que o lookbehind começou, você dividiria os estados olhando para trás, de modo que todos os caminhos para o lookback atrás terminassem com n caracteres no valor de estados que só passariam para o lookback. Em seguida, adicione lookahead ao início desses estados (e compile imediatamente o subgráfico de AFA para NFA, se desejado).

As referências anteriores não são, como já mencionado, não regulares, portanto não podem ser implementadas por um autômato finito. Na verdade, eles são NP-completos. Na implementação em que estou trabalhando, a correspondência rápida sim / não é fundamental, por isso optei por não implementar referências posteriores.