-5

Sabe -se que expressões regulares são padrões de caracteres que associam sequências de caracteres no texto. Sendo assim, seria possível fazer o mesmo para Assembly? Fazer com que exista expressões que traduziriam sequências ou passos como é em Assembly com os opcodes?

Aqui está um exemplo de uma expressão regular: [A-Za-z0-9]. Isso diz que pode ser maiúsculo, minúsculo e existe números que são de 0 até 9. Então, uma expressão regular pode se transformar em Assembly? Assim: mov a, mov b, mov c ... etc.

Se fosse em vez de escrevermos para compiladores e interpretadores poderíamos escrever nativamente na máquina, os opcodes como: mov a, mov b etc. seriam apenas uma expressão regular. Seria como uma regra específica para o processador.

E seria rápido o debug visto que as interrupções funcionariam em qualquer plataforma e tão possível e bem. Quais são as referências sobre esse assunto?

8
  • Não é trivial portar um grafo direcionado de arestas coloridas para ser processado diretamente pelo processador Commented 24/09/2017 às 2:44
  • Porque?Poderia explicar. Sua resposta é sutil, mas não entendo. Commented 24/09/2017 às 2:45
  • Se você me disser quais palavras estranhas eu mencionei acima, posso fazer uma resposta mais direcionada para você =) Se quiser, pode incluir no hall também: gramática regular, linguagem formal, hierarquia de Chomsky, máquina de estados, autômato determinístico Commented 24/09/2017 às 2:48
  • 1
    Não entendi os comentários sobre numerologia pitagórica, nem porque foram escritos nem porque foram excluídos Commented 24/09/2017 às 3:46
  • 1
    Eu creio que a nova edição tirou o espírito original da questão, levei isso para uma discussão no meta Commented 24/09/2017 às 22:05

2 Respostas 2

10

Para responder sua pergunta, Uma expressão regular pode se transformar em assembly?, precisamos entender 2 conceitos a priori:

  1. expressão regular
  2. 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:

  1. string vazia
  2. outro não-terminal
  3. um único terminal
  4. 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:

um grafo da gramática regular

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:

  1. se transação for transação-lambda (a.k.a tranação-epsilon);
  2. 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:

um grafo da máquina de estados

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:

  1. fazer decisões
  2. 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:

  1. Estrela de Kleene * usada para representar laços que ocorrem dentro do grafo
  2. Seleção | usada para representar caminhos diversos que podem ser trilhados a partir de uma origem em comum
  3. Agrupamento () usada para demonstrar uma série de transações que foram disparadas
  4. Lista [], usada para equivaler a uma transação multi-colorida, como a q3->q3
  5. 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 :

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:

  1. carregar valor da memória em registrador
  2. escrever em memória valor do registrados
  3. operações lógicas com operadores e constantes
  4. operações aritméticas com operadores e constantes
  5. operações bitwise com operadores e constantes
  6. 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 ou , 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):

autômato finito não-ambíguo determístico

Demonstração que é não-ambíguo e determinístico:

  1. verifique todas as arestas emergentes de um dado vértice; todas elas tem condições diferentes de disparo para qualquer que seja;
  2. 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:

  1. 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;
  2. 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
    
  3. para cada final de bloco de estado, há um desvio incondicional para o início;

  4. 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;
  5. 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>
    
  6. para cada elemento da transição de lista negada, tem um condicional com salto para o poço;

  7. 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

  1. carregar valor da memória em registrador
  2. escrever em memória valor do registrados
  3. operações lógicas com operadores e constantes
  4. operações aritméticas com operadores e constantes
  5. operações bitwise com operadores e constantes
  6. 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.

0
6

A pergunta como um todo é muito ampla, o que dá para responder é que é possível sim,qualquer coisa pode ser transformado em Assembly. Ou código de máquina que provavelmente é o desejado.

Claro que o que você tem que fazer é criar um compilador, pode até ser um simples já que só precisa da expressão regular. Mas por outro lado qual a utilidade da expressão regular assim se o resto não está?

Pra que fazer isto? Deve estar pensando em performance? Esquece, Assembly não é algo mágico que faz as coisas serem mais rápidas. Se fizer um compilador ruim terá o Assembly que gerará um processamento pior que um bom interpretador de expressão regular pronto. Assembly é sempre a solução extramente ingênua para problemas de performance. Só pensa nisto que está absurdamente longe de poder fazer algo neste nível. Quem consegue fazer sabe que esta não é a solução.

Quer mais performance? É simples, não use expressão regular. De forma geral é algo lento e não traz os benefícios que a maioria das pessoas acreditam em grande parte dos casos.

O que dá performance é usar o algoritmo certo, eles produzem ganhos quase inacreditáveis. Um dos mais simples e conhecidos pode diminuir o tempo de execução em uma fração de milhões. E pode ser escrito em qualquer linguagem lenta que obterá este resultado. Este algoritmo não se aplica à Regex, mas pouco pode se fazer para ter um enorme ganho neste caso.

Não estou dizendo que não terá ganho, mas que não vale o esforço. O que tem por aí já é suficiente.

Onde começar é o que eu digo sempre. Comece pelos fundamentos. Não queime etapas, não ache que dá para ir pelo caminho mais fácil, não acredite que é só perguntar para pessoas aleatórias na internet e saberá o que fazer, até porque isto não é aprender nada.

Aprendizado é construção, se faz com um tijolo de cada vez e não pode pular nenhum. Não pode começar sem alicerce. Alicerce no caso é saber bem o que vem antes de saber programação. Algumas pessoas acham que é possível programar bem sem saber comunicação e expressão ou matemática bem antes de tudo. Não é possível, nunca vi um caso de programador até mesmo razoável que não tivesse uma educação formal em nível razoável. Obviamente que programadores que só decoram um monte de receita não são bons programadores também. Bons programadores não perguntam coisas básicas porque (não estou dizendo que tem algo errado neste pergunta) porque eles aprenderam a achar a informação por conta própria. Perguntar é útil, é bom, mas perguntas boas são aquelas que ajudam construir conhecimento, não as que pedem tudo como fazer.

No caso falta ainda até o entendimento do que é Assembly, de como transformar uma coisa em outra, portanto a distância para conseguir realizar isto é tão grande que a pergunta é mera curiosidade. A parte final da pergunta sequer faz sentido.

Perguntas mais específicas podem ser mais úteis, porém sem o fundamento da computação dominado de nada adiantará.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .