Implementação de Máquinas de Estados Finitos em Assembly NASM

Uma Máquina de Estados Finitos (ou FSM, do inglês Finite State Machine) é um modelo computacional que consiste em um conjunto de estados. Em qualquer momento, a máquina pode estar em apenas um desses estados. Ela recebe uma entrada, inicia em um estado inicial e, à medida que processa a entrada, realiza transições para outros estados. Ao final do processamento, a máquina atinge um estado final, que determina o resultado da operação.

Exemplo: Validando se uma String é um Número

Vamos usar uma FSM para resolver um problema comum: verificar se uma string representa um número inteiro válido (que pode ser positivo ou negativo).

Diagrama da Máquina de Estados

A lógica para essa verificação pode ser representada pelo seguinte diagrama de estados:

A operação desta máquina pode ser descrita da seguinte forma:

• Estado A (Início):

  • Este é o estado inicial. Lemos o primeiro caractere da string.
  • Se for um sinal de menos (-), é um início válido para um número negativo. Transição para o Estado B.
  • Se for um dígito (0-9), é um início válido para um número. Transição para o Estado C.
  • Se for qualquer outro caractere, a string é inválida. Transição para o Estado E (Erro).

• Estado B (Recebeu o sinal negativo):

  • Neste estado, o caractere seguinte deve ser um dígito.
  • Se for um dígito, a string continua válida. Transição para o Estado C.
  • Se não for um dígito, a string é inválida (ex: "-a" ou "--"). Transição para o Estado E (Erro).

• Estado C (Lendo dígitos):

  • Este estado processa a sequência de dígitos do número.
  • Se o próximo caractere for um dígito, o número continua válido. Permanecemos no Estado C.
  • Se o caractere for o terminador nulo (\0), significa que a string terminou de forma válida. Transição para o Estado D (Sucesso).
  • Se for qualquer outro caractere (ex: uma letra no meio do número), a string é inválida. Transição para o Estado E (Erro).

• Estado D (Sucesso):

  • Este é um estado final. Atingi-lo significa que a string é um número válido.

• Estado E (Erro):

  • Este é o outro estado final. Atingi-lo significa que a string não é um número válido.

Implementação em Assembly NASM

Agora, vamos implementar essa lógica em um programa para Linux.

global _start

section .data
    number: db "-12345690", 0

    success: db "Valid number", 10
    success_length equ $-success
    error: db "String is not a number", 10
    error_length equ $-error

    index: dq 0

section .text

; Função para ler o próximo caractere em AL
getchar:
    mov rcx, [index]
    mov al, [number + rcx]
    inc qword [index]
    ret

_start:
; ESTADO A: Início
A:
    call getchar
    cmp al, '-'
    je B       ; Se for '-', transição para o estado B

    ; Verifica se é um dígito
    cmp al, '0'
    jb E       ; Se for menor que '0' (não é dígito), vai para Erro
    cmp al, '9'
    ja E       ; Se for maior que '9' (não é dígito), vai para Erro
    jmp C      ; Se for um dígito, transição para o estado C

; ESTADO B: Recebeu o sinal
B:
    call getchar
    ; Verifica se é um dígito
    cmp al, '0'
    jb E
    cmp al, '9'
    ja E
    jmp C      ; Se for dígito, transição para o estado C

; ESTADO C: Lendo dígitos
C:
    call getchar

    test al, al ; Verifica se AL é o terminador nulo ('\0')
    jz D        ; Se for, transição para o estado D (Sucesso)

    ; Verifica se é um dígito
    cmp al, '0'
    jb E
    cmp al, '9'
    ja E
    jmp C      ; Se for dígito, permanece no estado C

; ESTADO D: Sucesso
D:
    mov rsi, success
    mov rdx, success_length
    jmp print

; ESTADO E: Erro
E:
    mov rsi, error
    mov rdx, error_length

print:
    mov rax, 1
    mov rdi, 1
    syscall

    mov rax, 60
    syscall

Na seção .data, definimos a string de teste number e as mensagens de sucesso e erro. No código, cada estado da FSM é representado por um rótulo (A, B, C, D, E). O programa salta entre esses rótulos com base no caractere lido da string, implementando as transições que descrevemos.

Resultado da execução:

$ nasm -f elf64 fsm.asm -o fsm.o
$ ld fsm.o -o fsm
$ ./fsm
Valid number

Se você alterar a string number para algo inválido, como "12a34" ou "-abc", o programa imprimirá "String is not a number".

Resumo

• Uma Máquina de Estados Finitos (FSM) é um modelo computacional que transita entre um conjunto definido de estados em resposta a uma entrada.
• É uma técnica eficaz para resolver problemas de análise de sequências, como validação de dados, parsing e protocolos de comunicação.
• Em Assembly, os estados de uma FSM podem ser implementados como rótulos, e as transições como saltos condicionais (je, jb, jmp, etc.).