Реализация конечных автоматов

Конечный автомат представляет модель, которая определяет набор возможных состояний и одномоментно может находиться только в одном изт них. Конечный автомат принимает на вход некоторые данные и переходит в начальное состояние. При обработке отдельной порции данных автомат может переходить в другие состояния. При завершении обработки данных автомат переходит в конечное состояние, что означает завершение обработки данных и завершение работы конечного автомата.

Рассмотрим на примере проверки, является ли строка числом. Схематически конечный автомат в этом случае можно представить следующим образом:

Работу данного автомата можно выразить следующим образом:

• На вход подаются данные, и система переходит в состояние A

• Число может начинаться с цифры или с минуса (если число отрицательное). Это валидное начало строки. И если сначала идет минус, то переходим в состояние B. Если первый символ - цифра - переходим в состояние C

  Любой другой начальный символ будет означать невалидный ввод, и в этом случае переходим в состояние E - это конечное состояние, которое будет означать, что строка не является числом.

• В состоянии B (куда мы попадаем, если первый символ - минус "-"), смотрим на следующий символ. Если он представляет цифру, переходим в состояние C. В ином соучае опять же переходим в конечное состояние E, что означает, что строка не является числом.

• В состоянии C (в которое переходим, если символ - число), смотрим на последующие символы строки. Если символ - цифра, то остаемся в состоянии C.

  Если символ представляет нулевой символ "\0", который символизирует окончание строки, то значит, мы завершили считывание символов строки, и поэтому переходим в состояние D. Это будет означать, что проверка строки успешно завершена, и строка является числом.

  Любой другой (нецифровой) символ означает, что строка не является числом, и в этом случае переходим в состояние E

Реализуем данный автомат с помощью кода ассемблера (программа для Linux):

global _start           

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

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

section .text

; считываем один символ в AL
getchar: 
    mov al, [number + rcx]
    add rcx, 1      ; увеличиваем счетчик считанных символов
    ret

_start:
A:
    call getchar
    cmp al, "-"
    je B       ; если символ - "-", то переход в состояние B

    ; проверяем, является ли символ цифрой
    cmp al, "0"
    jb E       ; если asci-код меньше кода символа "0"

    cmp al, "9"
    ja E       ; если asci-код больше кода символа "9"
    jmp C      ; если цифра - переход в состояние C

; состояние B
B:
    call getchar
    ; проверяем, является ли символ цифрой
    cmp al, "0"
    jb E       ; если asci-код меньше кода символа "0"

    cmp al, "9"
    ja E       ; если asci-код больше кода символа "9"
    jmp C      ; если цифра - переход в состояние C

; состояние C
C:
    call getchar

    test al, al ; если в al нулевой символ - завершитель строки
    jz D       ; переход в состояние D

    ; проверяем, является ли символ цифрой
    cmp al, "0"
    jb E       ; если asci-код меньше кода символа "0"

    cmp al, "9"
    ja E       ; если asci-код больше кода символа "9"
    jmp C      ; если цифра, переход обратно в это же состояние C

; состояние D - успешное завершение
D:
    mov rsi, success
    mov rdx, success_length
    jmp print

; состояние Е - неудачное завершение
E:
    mov rsi, error
    mov rdx, error_length

print:
    mov rdi, 1  ; 1 - дескриптор файла стандартного вызова stdout
    mov rax, 1  ; системная функция write
    syscall

    mov rax, 60
    syscall

В секции data для теста определена входная строка number и два сообщения для вывода результата при успехе и неудаче. Функция getcahr считывает один символ строки в регистр AL. В основной части программы с помощью меток A, B, C, D, E определяем соответствующие состояния и обрабатываем символ из регистра AL. В зависимости от результата выводим определенное сообщение. Пример работы:

root@Eugene:~/asm# nasm -f elf64 hello.asm -o hello.o
root@Eugene:~/asm# ld -o hello hello.o
root@Eugene:~/asm# ./hello
Valid number
root@Eugene:~/asm#