проФорт

Для тех, кому незнакомо что же есть такое "конечные автоматы", прошу обращаться в обзорные статьи: "От тьюрингова программирования к автоматному", раздел на SoftCraft.

Несмотря на то что конечные автоматы — немножко иной подход, никакими "революциями" по переписыванию всего кода он не метастазирует, не заставляет пересаживать мозги на новую колею, не постулирует нового и единственно правильного способа написания кода отныне и вовеки веков, а вполне себе тихо работает, быстро пишется и быстро работает там где он уместен (по крайней мере это так в рамках Форта, которому это вообще свойственно: "включение" новых, как это модно говорить, "парадигм" программирования подключением несколько килобайтовой библиотеки, и само собой что без отключения предыдущих "парадигм").

КА (конечные автоматы, finite-state machines) пусть и имеют за собой некую теоретическую базу (см. "страшную" статью на Wikipedia), на практике не представляют ничего такого сложного и академически высоколобого для освоения и использования. Уверять в этом не буду, а просто покажу это примерами на пальцах.

Таблицы решений (переходов) — по реализации стали частным случаем одного состояния автомата, хотя и приобрели в процессе работы некоторые собственные свойства. С них, простых и начнём.

Для начала работы нужно взять последнюю версию ~profit/lib/chartable.f и положить её в соответствующую папку в DEVEL.

Следующий код:

REQUIRE state-table ~profit/lib/chartable.f

3 state-table one-two-three
1 asc: ." one" ;
2 asc: ." two" ;
3 asc: ." three" ;

1 one-two-three
\ вывод: one
3 one-two-three
\ вывод: three

будет аналогичен функции one-two-three с одним параметром в языке С:

void one_two_three(int n){
switch(n) {
case 1: printf("one"); break;
case 2: printf("two"); break;
case 3: printf("one"); break;
}}

То есть вроде бы это как конструкция case, только разница в том что one-two-three, при вызове, не делает никаких сравнений аргумента, а только сразу переходит к заданной заранее реакции номер которой и будет аргумент (то есть это один косвенный переход вместо нескольких сравнений). Поэтому при создании таблицы нужно сразу указывать кол-во реакций в ней. То есть при создании создаются ячейки которые будут гнёздами для хранения действий-реакций на вызов функции с определённым значением.

Можно задавать действия для нескольких реакций сразу:

REQUIRE state-table ~profit/lib/chartable.f

3 state-table one-two-three
1 2 range: ." onetwo" ;
3 asc: ." three" ;

1 one-two-three
\ вывод: onetwo
3 one-two-three
\ вывод: three

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

REQUIRE state-table ~profit/lib/chartable.f

9 state-table nine
all: ." IV-IX" ;
1 asc: ." I" ;
2 asc: ." II" ;
3 asc: ." III" ;

2 nine .
\ вывод: II

7 nine .
\ вывод: IV-IX

100 nine .
\ вывод: IV-IX

Обратите внимание что в последнем примере при задании некорректного номера реакции выполняется действие "по-умолчанию".

Также я для себя определял "синтаксически-сахарные" слова задающие реакции для групп символов как-то:

• пробел: — задаёт действие на поступивший пробел (код 32)
  
• перевод-строки: — задаёт действие на поступивший перевод строки (код 10, код 13 игнорируется)
  
• разделители: — задаёт действие для кодов от 0-я до 32-х включительно, то есть реакции для пробельных символов
  
• цифры: — задаёт действие для поступающих цифр
  
• латинские-буквы: — задаёт действие для поступающих латинских букв
  
• символ: — задаёт действие для символа который записан сразу после символ:
  
• символы: — задаёт действие для символов которые заданы строкой после слова

Теперь вернёмся к КА. Теоретически автомат — это такой ящик, могущий находится в разных состояниях. В зависимости от своего состояния он будет делать разные действия в ответ на подаваемые на вход данные, в том числе — и переключение себя в другое состояние. В реализации же на SPF автомат представляют из себя группу слов-состояний, в чём-то похожих, в чём-то отличающихся от таблиц решений.

Отличия примерно такие: тогда как таблица решений является по своему эффекту просто поименованной конструкцией case и стоит как бы сама по себе, то для налаживания работы автомата уже нужно строить инфраструктуру: несколько состояний; связи между ними; курсор; обработка специальных реакций состояний автомата, которых нет у таблиц решений (событие о включении состояния, событие об окончании входного потока) и прочее. И самое видное отличие: когда запускаешь состояние (точнее говоря слово созданное через слово state) не делается вызов реакции, вызов слова-состояния только переключает переменную current-state. Реакции состояния вызывает т.н. запускающее слово (о нём — позже) которое будет вызывать реакции текущего состояния подставляя поочерёдно на вход состояний символы из данной заранее строки (хотя технически и можно вызывать реакции текущего состояния "вручную" словом execute-one).

Возьмём для следующего примера задачу подсчёта скобок, при уравновешенном количестве левых и правых скобок выдавать TRUE, при неравном — FALSE:

REQUIRE state-table ~profit/lib/chartable.f

VARIABLE parens \ переменная, счётчик скобок


\ Начало описания автомата
state count-parens          \ задаём состояние
\ кол-во реакций задавать не надо, их всегда 256 реакций на символы + 3 специальных

on-enter:      parens  0! ;  \ действие при входе в состояние
CHAR ( asc:    parens 1+! ;  \ открывающая круглая скобка
CHAR ) asc: -1 parens  +! ;  \ закрывающая круглая скобка
end-input: parens @ 0= ;     \ когда кончилась обрабатываемая строка
\ Конец описания автомата, всего лишь одно состояние


\ на входе строка со скобками, на выходе — лог. значение указывающее равно ли их кол-во
: подсчитать-скобки ( addr u — f )
1 TO размер-символа   \ указываем обработчику что символы — однобайтные
SWAP поставить-курсор \ устанавливаем курсор на начало строки
count-parens          \ ставим начальное состояние автомата
-символов-обработать  \ пускаем автомат, на входе — кол-во символов которые нужно 
\ обработать начиная с текущего местоположения курсора
;

S" (1+(2-3))" подсчитать-скобки .
\ вывод: -1 (TRUE)
S" (" подсчитать-скобки .
\ вывод: 0

Главное запускающее слово автомата (в нашем примере — подсчитать-скобки), нужно формировать вручную, но поможет тут то что запускающее слово в примере имеет некую "каноническую" форму которой должно хватать для большинства нужд. В следующий раз можно спокойно копировать "шаблон" и просто менять имя первичного состояния на то, что в вашем автомате.

NB. Да, то что нужно задавать переменную размер-символа означает в том числе и то что эта реализация автоматов работает и в Unicode, и в UTF-8 (в упомянутом дипломном проекте).

Этот простенький автомат в виде графа выглядит так:



Пока написанное является просто обёрткой анализа строки, где в лексиконе chartable.f спрятан цикл прохода по строке и вызова соответсвующих реакций для каждого символа строчки. Да и всего одно состояние.

Тогда теперь наложим проверки на наше арифметическое выражение с цифрами, скобками и операциями, которые будут срабатывать на неверных комбинациях вида: "(+)" и "(11)11". Возьмём корректное выражение:

(1+(2-3))

и прикинув какие символы в каждый момент последовательной обработки будут правильными, а какие — ведущими к ошибке, выводим три проверочных состояния:

• ожидание открывающей скобки или цифры — нулевая позиция и позиции после плюса и минуса,
  
• ожидание цифры — позиции после каждой открывающей скобки,
  
• ожидание операции ('+', '-', '*', '/') или закрывающей скобки.

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

Пишем код для описанного автомата:

REQUIRE state-table ~profit/lib/chartable.f

VARIABLE parens  \ переменная, счётчик скобок

state count-parens         \ состояние подсчёта скобок
state wait-for-digit       \ состояние ждать-цифры
state wait-for-digit-or-(  \ состояние ждать-цифры-или-скобки
state wait-for-ops-or-)    \ состояние ждать-действия-или-скобки


: err              \ слово обработчик ошибки
-1 parens !        \ поставить в счётчик заведомо неверное значение
остановить-автомат ;

count-parens \ начинаем задавать реакции для count-parens
all: err ; \ на все символы, кроме заданных явно ниже, реагировать ошибкой
цифры: ; \ цифры игнорировать и пропускать мимо
символы: +-*/  wait-for-digit-or-( ; \ после операции
CHAR ( asc:    parens 1+! wait-for-digit ;
CHAR ) asc: -1 parens  +! wait-for-ops-or-) ;

wait-for-digit
all: err ;
CHAR 0 CHAR 9 range: rollback1 count-parens ;

wait-for-digit-or-(
all: err ;
цифры: rollback1 count-parens ;
CHAR ( asc: тоже-самое ;

wait-for-ops-or-)
all: err ;
символы: +-*/  rollback1 count-parens ;
CHAR ) asc: тоже-самое ;

: подсчитать-скобки ( addr u — f )
\ на входе — строка с арифм. выражением, на выходе — корректность
1 TO размер-символа SWAP поставить-курсор
parens 0!
 wait-for-digit-or-( -символов-обработать
parens @ 0= ;

\ включить-отладку-автомата
S" (1+(2-3))" подсчитать-скобки .
\ вывод: -1 (TRUE)
S" (" подсчитать-скобки .
\ вывод: 0

И смотрим диаграмму переходов автомата:



То что автомат можно соптимизировать и убрать состояние count-parens здесь неважно. Так было сделано для того чтобы оставлять действия по изменению переменной parens в одном месте, а не разносить по трём состояниям. Поэтому также после проверки на корректность очередного поступившего символа и перед переключением автомата в "главное" состояние count-parens, надо "возвращать" символ назад, чтобы главное подсчитывающее состояние могло проанализировать поступивший символ (слово rollback1 в коде реакций проверочных состояний и обозначение "вернуть" на предыдущей картинке).

Желающие самостоятельно продолжить тему применения КА в анализе текстов могут сравнить например коды автоматного сканера (парсера) XML на Pascal'е и на SPF (+ диаграмма).

Примеры кода на chartable.f:

• Решение Python challenge (задача №3)
  
• Преобразование табуляций в тексте
  
• Взятие и распаковка иллюстраций из книг в формате FB2 на основе автоматного xml-сканера

Ссылки по теме "КА и Форт":

• Автомат-сканер текста и таблицы решений — chartable.f
  
• Finite State Machines in Forth, J. V. Noble