Para responder sua pergunta, Uma expressão regular pode se transformar em assembly?, precisamos entender 2 conceitos a priori:
- expressão regular
- assembly
Expressão regular
Não estou tomando como base expressões regulares modernosas com look-behind, agrupamento atômico e retrovisores; estou focando na parte mais regular matematicamente falando. A possibilidade de incluir essas funcionalidades em regex desconfiguram o autômato finito, pois exigem a presença de alguma memória.
Por sinal, a presença de retrovisores implica que resolve problemas sensíveis ao contexto, dois níveis mais baixo na hierarquia de Chmosky.
Uma expressão regular é um esquema de escrever uma gramática regular em uma única linha. Pode ser visto também como uma maneira muito compacta de se montar uma máquina de estados sem memória, com leitura unidirecional na fita.
Gramática regular
Uma gramática regular é obtida através de uma gramática que só tem produções regulares. Uma produção é chamada regular se ela for de um não-terminal para um dos seguintes alvos:
- string vazia
- outro não-terminal
- um único terminal
- um par: terminal e não-terminal
Veja mais nessa resposta sobre meta-linguagem qual a gramática para construir gramáticas. Veja essa outro resposta que fala sobre linguagens formais com intenso carinho, principalmente as partes iniciais.
A partir de uma gramática regular, podemos montar um grafo direcionado que a representa, onde os vértices são não-terminais (com possível exceção do vértice de aceitação) e as arestas representam uma produção gramatical. Tomemos a seguinte gramática como exemplo, com q0
para o símbolo inicial e 0
,1
como sendo os terminais:
q0 -> 1 q1
q1 -> 0 q2
q2 -> 1 q5
q2 -> 1 q3
q3 -> 0 q3
q3 -> 1 q3
q3 -> 0 q4
q4 -> 1 q5
q5 -> 0 q6
q6 -> 1 q7
q7 -> 0 q8
Ela pode ser interpretada como o seguinte grafo:
Fonte da imagem: https://stackoverflow.com/a/22366722/4438007
Uma palavra p
é dita aceita na gramática G
se for possível, através do não-terminal inicial, obter a palavra p
utilizando apenas das transações de G
. p
, para ser considerada uma palavra, deve ser composta apenas de terminais.
Máquina de estados
Uma máquina de estados é uma abstração matemática que representa o como um programa vai se comportar. No caso, estamos tratando de uma autômato de estados finitos. Para ser regular, esse autômato só contém seus estados, seu estado atual e a palavra de leitura.
Todo autômato começa em um estado inicial. Para sair de um estado e entrar em outro, há duas hipóteses apenas:
- se transação for transação-lambda (a.k.a tranação-epsilon);
- se a letra da palavra disponível para ser consumida seja uma das opções da transação, situação na qual a letra será consumida (isto é, ela não poderá jamais ser consultada novamente pela expressão regular) e se andará na transação.
Uma máquina de estados pode ser muito bem representado por um grafo. Vértices representam os estados e arestas transações. Os vértices podem ser coloridos para indicar estados de aceitação (múltiplos estados de aceitação são possíveis) e inicial (apenas um estado inicial é permitido). Arestas são coloridas com a letra que é consumida na transação, ou recebem cor lambda caso representem transições lambda.
Uma máquina de estados representada graficamente pode ser essa:
Uma palavra p
é reconhecida pelo autômato finito se for possível, utilizando-se de seus estados e das duas regras de transação acima descritas, para em um dos estados de aceitação sem que haja nem mais uma letra a ser consumida.
Note que os autômatos não precisam ser determinísticos; por sinal, a própria existência de transações-lambda exigem que o autômato seja não-determinístico. Entretanto, existe um algoritmo que transforma qualquer autômato finito não-determinístico em um autômato finito determinístico.
O autômato acima descrito é não determinístico: pegue a palavra 1010
, em qual estado ela vai parar? As opções são: q6
, q4
e q3
.
Note que, em um autômato finito, percorrer um caminho em um grafo implica em:
- fazer decisões
- entrar em loop
A decisão de sair de um estado x
qualquer depende apenas dele mesmo e da próxima letra disponível na palavra; qualquer conjunto de letras anteriores e de transações disparadas que resultem no mesmo estado, então, passam a ser idempotentes.
Existe um conceito útil no autômato finito que é o chamado poço. Quando se encontra um caracter não esperado pelo autômato, o estado seguinte é o poço. Quando a expressão regular é do tipo pertence à palavra, e não a palavra deve ser idêntica a expressão, o poço tem uma transação-lambda para o estado inicial. Nota: todos os estados tão transações implícitas para o poço com todas as outras letras do alfabeto não descritas em suas transações. Devido a isso, normalmente o poço é ignorado do desenho.
Linguagem regular
Uma linguagem regular é o conjunto de palavras reconhecidas por uma gramática (ou um autômato) que a descreve. Nesse contexto, a gramática (ou autômato) pode ser considerada generativa. Nesse contexto, no lugar de consumir da palavra de entrada, transações são disparadas gerando terminais, até que se chega ao fim e se tem uma nova palavra da linguagem. Falo mais sobre linguagens e palavras nessa resposta. (Autômatos também podem ser generativos, comportando-se de modo semelhante a uma Cadeia de Markov).
Expressão regular, o retorno
A expressão regular, então, é um esquema para se descrever uma linguagem regular. Fica fácil perceber através do grafo da gramática o modo como se constrói uma expressão regular.
De modo geral, os principais operadores da expressão regular são:
- Estrela de Kleene
*
usada para representar laços que ocorrem dentro do grafo
- Seleção
|
usada para representar caminhos diversos que podem ser trilhados a partir de uma origem em comum
- Agrupamento
()
usada para demonstrar uma série de transações que foram disparadas
- Lista
[]
, usada para equivaler a uma transação multi-colorida, como a q3->q3
- Escape
\
, força o caracter seguinte ter significado literal, perdendo seus poderes como meta-caracter
Tendo em vista essas regras de formação, podemos transformar o autômato não-determinístico sem lambda na seguinte expressão regular:
10(1|1[01]*01)010
Expressões regulares mais modernas ganharam outros operadores mais modernosos, como o opcional ?
e a cruz de Kleene +
, mas esses operadores são facilmente transformados nos operadores anteriores.
Compilando expressões regulares com gramáticas livres de contexto
Expressões regulares não podem ser identificadas por expressões regulares. Isso porque, em sua mais básica definição, expressões regulares sofrem auto-aninhamento. Mais sobre isso nessa resposta.
Uma demonstração rápida do auto-aninhamento das expressões regulares:
11100(0101(11111[01][01]*[01]00000)*00)*11100
A gramática geral para uma expressão regular é (em notação BNF-símile):
S -> EXP
EXP -> EXP . EXP
EXP -> NQEXP
EXP -> NQEXP . QUANT
QUANT -> '*'
NQEXP -> '(' . EXP . ')'
NQEXP -> '[' . LETRAS_LISTA . ']'
NQEXP -> '\' . qualquer caracter
NQEXP -> LETRA
LETRAS_LISTA -> ']' . LETRAS_LISTA2
LETRAS_LISTA -> LETRAS_LISTA2
LETRAS_LISTA2 -> todas as outras, exceto ']'
LETRA -> qualquer caracter não especial
Nota:
S
de start
EXP
de expressão
NQEXP
de expressão não quantificada
QUANT
de quantificados
Assembly
Da tag assembly:
Geralmente, um mnemônico é um nome simbólico para uma única instrução em linguagem de máquina executável (um código de operação), e há pelo menos um mnemônico opcode definido para cada instrução de linguagem de máquina. Cada instrução tipicamente consiste de uma operação de código de operação e zero ou mais operandos. A maioria das instruções referem-se a um valor único, ou um par de valores. Operandos podem ser imediatos (valor codificado na própria instrução), os registos especificados na instrução ou implícitas, ou os endereços de dados localizados em outros lugares no armazenamento. Isso é determinado pela arquitetura do processador subjacente: o montador apenas reflete como essa arquitetura funciona.
Normalmente, esses operadores realizam as seguintes computações:
- carregar valor da memória em registrador
- escrever em memória valor do registrados
- operações lógicas com operadores e constantes
- operações aritméticas com operadores e constantes
- operações bitwise com operadores e constantes
- fluxo de operações
É importante ressaltar que as operações lógicas/atiméticas/bitwise são de bitagem fixa para manter a eficiência e a complexidade assintótica.
Operações de desreferenciamento de ponteiro é uma operação de carregar valor da memória para um registrador.
Execução de um programa
Assembly é feito de maneira determinística, cada execução sendo planejada (direta ou indiretamente) pelo programador. O mesmo conjunto de dados é executado, passo a passo, pelo processador.
A única opção de não determinismo que consigo encontrar para processadores não quânticos é o processamento depender de dados randômicos de origem não controlável (não estou falando do random()
de linguagens como c ou java, mas de variáveis que venham de fora do computador; random()
é determinística para a semente passada, enquanto normalmente a semente é dependente da hora do sistema). Ainda assim, esse comportamento pode muito bem ser simulado como uma função oráculo, o comportamento do sistema (ignorando o funcionamento interno do oráculo) se torna determinístico.
Assembly para Regex
Como definir um assembly para expressões regulares? Bem, assembly depende de um conjunto de instruções que são seguidas de maneira determinística. Simplesmente portar o que está escrito na regex sem maiores traduções para uma linguagem de máquina não fará com que ela seja determinística.
Uma alternativa, portanto, seria transformar a expressão regular em um autômato finito e, então, transformá-lo em um autômato finito determinístico. Comumente, isso é implementado como um desvio múltiplo para cada estado e cada estado tento um desvio múltiplo para as letras relevantes. Estados com transações não previstas cairiam para o poço. Implementação do meta-caracter .
e da lista negada recai sobre desvios múltiplos também.
O autômato dos exemplos pode ser descrito pela seguinte gramática regular não-ambígua determinística:
q0 -> 1 q1
q1 -> 0 q2
q2 -> 1 q_{5,3}
q_{5_3} -> 1 q3
q3 -> 0 q_{3_4}
q_{3_4} -> 0 q3
q3 -> 1 q3
q_{5_3} -> 0 q_{6_3_4}
q_{3_4} -> 1 q_{5_3}
q_{6_3_4} -> 0 q3
q_{6_3_4} -> 1 q_{7_5_3}
q_{7_5_3} -> 1 q3
q_{7_5_3} -> 0 q_{8_6_3_4}
q_{8_6_3_4} -> 0 q_{3_4}
q_{8_6_3_4} -> 1 q_{7_5_3}
O que resulta no seguinte grafo (com q0
o estado incial e q_{8_6_3_4}
o único estado de aceitação):
Demonstração que é não-ambíguo e determinístico:
- verifique todas as arestas emergentes de um dado vértice; todas elas tem condições diferentes de disparo para qualquer que seja;
- não há transições-lambda.
Portanto, é não-ambíguo e determinístico.
Para representar em unidades atômicas, as seguintes transações poderiam virar um assembly mais ou menos da seguinte maneira:
- define a tabela de estados com rótulos; se o autômato se encontra no estado
q_{5_3}
, ele irá para o conteúdo do rótulo q_{5_3}
com um desvio;
o passo contido no início
é um desvio para o rótulo correto; isso pode ser feito elaborando um vetor de rótulos relacionando cada posição a um rótulo; nesse caso, o desvio seria:
# sejam os trechos começados por "#" comentários até o final da linha
# sejam "reg_a", "reg_b", "reg_c" registradores de propósito geral
# seja "reg_est" o registrador específico para guardar o estado do autômato
# seja strings começadas com "$" constantes
# seja a operação "set a, b" a operação que seta em "a" o valor de "b"
# seja "add y, x, a" a operação que salva em "y" o valor da soma de "x" e "a"
# seja "[a]" o acesso ao local de memória apontado por "a", portanto retornando o conteúdo apontado pelo ponteiro "a"
# seja "jmp a" a operação de salto incondicional para a posição "a" da pilha de execução
# seja "label a" o rótulo chamado "a", usado para futura referência de desvios incondicionais
# seja "<a>" a referência ao rótulo "a"
label inicio:
set reg_a, $pos_vetor_rotulos
add reg_b, reg_a, reg_est
set reg_a, [reg_b]
jmp reg_est
para cada final de bloco de estado, há um desvio incondicional para o início
;
- para cada transição finita afirmativa disparada, tem um condicional alterando o estado para o vértice no final da aresta da transição disparada; caso seja aceito em alguma dessas condições, salto para o fim do bloco;
para a transição acima, caso não tenha saltado para o fim do bloco, o próximo estado será o poço;
# exemplo para o estado q_{5_3}
# seja "reg_c" o registrador que contém o caracter sendo consumido da palavra
# seja "jneq dest, v1, v2" o salto condicionado para "dest" caso "v1" e "v2" sejam não iguais
label q_{5_3}:
jneq <q_{5_3}_1>, reg_c, '0'
set reg_est, <q_{6_3_4}>
jmp <fim_q_{5_3}>
label q_{5_3}_1:
jneq <q_{5_3}_2>, reg_c, '1'
set reg_est, <q_3>
jmp <fim_q_{5_3}>
label q_{5_3}_2:
set reg_est, <poço>
label fim_q_{5_3}:
jmp <inicio>
para cada elemento da transição de lista negada, tem um condicional com salto para o poço;
- para transições coringas (normalmente denominada pelo meta-caracter
.
ou pelo conteúdo válido em uma lista ligada), tem o salto determinado para o próximo estado dessa transição.
Com isso, teríamos um código assembly-símile de expressões regulares.
Conclusão
Utilizando-se das limitações de uma linguagem de montagem
- carregar valor da memória em registrador
- escrever em memória valor do registrados
- operações lógicas com operadores e constantes
- operações aritméticas com operadores e constantes
- operações bitwise com operadores e constantes
- fluxo de operações
o código representativo de uma expressão regular ficaria muito extenso e ilegível. Para fins de depuração, melhor seria transformar no autômato finito não-ambíguo determinístico e mostrar em qual estado se encontra o reconhecimento do padrão passado.
Graficamente, fica muito interessante verificar o estado atual do processamento destacado no AFD, assim como também seria interessante acompanhar na palavra passada para se encontrar o padrão qual a posição sendo reconhecida naquele momento. Também seria interessante mapear o estado do autômato determinístico para as suas posições equivalentes na expressão regular.