проФорт

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

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

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

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

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

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

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>state-table </span><span style='color:#000084; '>~profit/lib/chartable.f</span>

<span style='color:#008c00; '>3</span> state-table one-two-three
<span style='color:#008c00; '>1</span> asc: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>one</span><span style='color:#000084; font-weight:bold; '>"</span> ;
<span style='color:#008c00; '>2</span> asc: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>two</span><span style='color:#000084; font-weight:bold; '>"</span> ;
<span style='color:#008c00; '>3</span> asc: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>three</span><span style='color:#000084; font-weight:bold; '>"</span> ;

<span style='color:#008c00; '>1</span> one-two-three
<span style='color:#808080; '>\ вывод: one</span>
<span style='color:#008c00; '>3</span> one-two-three
<span style='color:#808080; '>\ вывод: three</span>

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

<span style='color:#000084; font-weight:bold; '>void</span> one_two_three(<span style='color:#000084; font-weight:bold; '>int</span> n){
<span style='color:#000084; font-weight:bold; '>switch</span>(n) {
<span style='color:#000084; font-weight:bold; '>case </span><span style='color:#008c00; font-weight:bold; '>1</span><span style='color:#800000; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>printf</span>(<span style='color:#0000ff; '>"</span><span style='color:#0000ff; '>one</span><span style='color:#0000ff; '>"</span>); <span style='color:#000084; font-weight:bold; '>break</span>;
<span style='color:#000084; font-weight:bold; '>case </span><span style='color:#008c00; font-weight:bold; '>2</span><span style='color:#800000; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>printf</span>(<span style='color:#0000ff; '>"</span><span style='color:#0000ff; '>two</span><span style='color:#0000ff; '>"</span>); <span style='color:#000084; font-weight:bold; '>break</span>;
<span style='color:#000084; font-weight:bold; '>case </span><span style='color:#008c00; font-weight:bold; '>3</span><span style='color:#800000; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>printf</span>(<span style='color:#0000ff; '>"</span><span style='color:#0000ff; '>one</span><span style='color:#0000ff; '>"</span>); <span style='color:#000084; font-weight:bold; '>break</span>;
}}

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

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

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>state-table </span><span style='color:#000084; '>~profit/lib/chartable.f</span>

<span style='color:#008c00; '>3</span> state-table one-two-three
<span style='color:#008c00; '>1 </span><span style='color:#008c00; '>2</span> range: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>onetwo</span><span style='color:#000084; font-weight:bold; '>"</span> ;
<span style='color:#008c00; '>3</span> asc: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>three</span><span style='color:#000084; font-weight:bold; '>"</span> ;

<span style='color:#008c00; '>1</span> one-two-three
<span style='color:#808080; '>\ вывод: onetwo</span>
<span style='color:#008c00; '>3</span> one-two-three
<span style='color:#808080; '>\ вывод: three</span>

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

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>state-table </span><span style='color:#000084; '>~profit/lib/chartable.f</span>

<span style='color:#008c00; '>9</span> state-table nine
all: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>IV-IX</span><span style='color:#000084; font-weight:bold; '>"</span> ;
<span style='color:#008c00; '>1</span> asc: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>I</span><span style='color:#000084; font-weight:bold; '>"</span> ;
<span style='color:#008c00; '>2</span> asc: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>II</span><span style='color:#000084; font-weight:bold; '>"</span> ;
<span style='color:#008c00; '>3</span> asc: <span style='color:#000084; font-weight:bold; '>." </span><span style='color:#0000ff; '>III</span><span style='color:#000084; font-weight:bold; '>"</span> ;

<span style='color:#008c00; '>2</span> nine <span style='color:#000084; font-weight:bold; '>.</span>
<span style='color:#808080; '>\ вывод: II</span>

<span style='color:#008c00; '>7</span> nine <span style='color:#000084; font-weight:bold; '>.</span>
<span style='color:#808080; '>\ вывод: IV-IX</span>

<span style='color:#008c00; '>100</span> nine <span style='color:#000084; font-weight:bold; '>.</span>
<span style='color:#808080; '>\ вывод: IV-IX</span>

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

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

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

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

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

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

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>state-table </span><span style='color:#000084; '>~profit/lib/chartable.f</span>

<span style='color:#000084; font-weight:bold; '>VARIABLE </span><span style='color:#000084; font-weight:bold; '>parens</span><span style='color:#808080; '> \ переменная, счётчик скобок</span>


<span style='color:#808080; '>\ Начало описания автомата</span>
<span style='color:#000084; font-weight:bold; '>state</span> count-parens         <span style='color:#808080; '> \ задаём состояние</span>
<span style='color:#808080; '>\ кол-во реакций задавать не надо, их всегда 256 реакций на символы + 3 специальных</span>

on-enter:      parens  <span style='color:#000084; font-weight:bold; '>0!</span> ; <span style='color:#808080; '> \ действие при входе в состояние</span>
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>(</span> asc:    parens 1+! ; <span style='color:#808080; '> \ открывающая круглая скобка</span>
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>)</span> asc: <span style='color:#008c00; '>-1</span> parens  <span style='color:#000084; font-weight:bold; '>+!</span> ; <span style='color:#808080; '> \ закрывающая круглая скобка</span>
end-input: parens <span style='color:#000084; font-weight:bold; '>@ </span><span style='color:#000084; font-weight:bold; '>0=</span> ;    <span style='color:#808080; '> \ когда кончилась обрабатываемая строка</span>
<span style='color:#808080; '>\ Конец описания автомата, всего лишь одно состояние</span>


<span style='color:#808080; '>\ на входе строка со скобками, на выходе — лог. значение указывающее равно ли их кол-во</span>
<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>подсчитать-скобки</span><span style='color:#808080; '> ( addr u — f )</span>
<span style='color:#008c00; '>1</span><span style='color:#800000; '> </span><span style='color:#000084; font-weight:bold; '>TO</span> размер-символа  <span style='color:#808080; '> \ указываем обработчику что символы — однобайтные</span>
<span style='color:#000084; font-weight:bold; '>SWAP</span> поставить-курсор<span style='color:#808080; '> \ устанавливаем курсор на начало строки</span>
count-parens         <span style='color:#808080; '> \ ставим начальное состояние автомата</span>
-символов-обработать <span style='color:#808080; '> \ пускаем автомат, на входе — кол-во символов которые нужно </span>
<span style='color:#808080; '>\ обработать начиная с текущего местоположения курсора</span>
<span style='color:#000084; font-weight:bold; '>;</span>

<span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>(1+(2-3))</span><span style='color:#000084; font-weight:bold; '>"</span> подсчитать-скобки <span style='color:#000084; font-weight:bold; '>.</span>
<span style='color:#808080; '>\ вывод: -1 (TRUE)</span>
<span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>(</span><span style='color:#000084; font-weight:bold; '>"</span> подсчитать-скобки <span style='color:#000084; font-weight:bold; '>.</span>
<span style='color:#808080; '>\ вывод: 0</span>

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

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

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



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

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

(<span style='color:#008c00; '>1</span>+(<span style='color:#008c00; '>2</span>-<span style='color:#008c00; '>3</span>))

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

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

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

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

<span style='color:#000084; font-weight:bold; '>REQUIRE </span><span style='color:#000084; font-weight:bold; '>state-table </span><span style='color:#000084; '>~profit/lib/chartable.f</span>

<span style='color:#000084; font-weight:bold; '>VARIABLE </span><span style='color:#000084; font-weight:bold; '>parens </span><span style='color:#808080; '> \ переменная, счётчик скобок</span>

<span style='color:#000084; font-weight:bold; '>state</span> count-parens        <span style='color:#808080; '> \ состояние подсчёта скобок</span>
<span style='color:#000084; font-weight:bold; '>state</span> wait-for-digit      <span style='color:#808080; '> \ состояние ждать-цифры</span>
<span style='color:#000084; font-weight:bold; '>state</span> wait-for-digit-or-( <span style='color:#808080; '> \ состояние ждать-цифры-или-скобки</span>
<span style='color:#000084; font-weight:bold; '>state</span> wait-for-ops-or-)   <span style='color:#808080; '> \ состояние ждать-действия-или-скобки</span>


<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>err</span>             <span style='color:#808080; '> \ слово обработчик ошибки</span>
<span style='color:#008c00; '>-1</span> parens <span style='color:#000084; font-weight:bold; '>!</span>       <span style='color:#808080; '> \ поставить в счётчик заведомо неверное значение</span>
остановить-автомат<span style='color:#000084; font-weight:bold; '> ;</span>

count-parens<span style='color:#808080; '> \ начинаем задавать реакции для count-parens</span>
all: err ;<span style='color:#808080; '> \ на все символы, кроме заданных явно ниже, реагировать ошибкой</span>
цифры: ;<span style='color:#808080; '> \ цифры игнорировать и пропускать мимо</span>
символы: +-*/  wait-for-digit-or-( ;<span style='color:#808080; '> \ после операции</span>
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>(</span> asc:    parens 1+! wait-for-digit ;
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>)</span> asc: <span style='color:#008c00; '>-1</span> parens  <span style='color:#000084; font-weight:bold; '>+!</span> wait-for-ops-or-) ;

wait-for-digit
all: err ;
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>0 </span><span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>9</span> range: rollback1 count-parens ;

wait-for-digit-or-(
all: err ;
цифры: rollback1 count-parens ;
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>(</span> asc: тоже-самое ;

wait-for-ops-or-)
all: err ;
символы: +-*/  rollback1 count-parens ;
<span style='color:#000084; font-weight:bold; '>CHAR </span><span style='color:#0000ff; '>)</span> asc: тоже-самое ;

<span style='color:#000084; font-weight:bold; '>: </span><span style='color:#000084; font-weight:bold; '>подсчитать-скобки</span><span style='color:#808080; '> ( addr u — f )</span>
<span style='color:#808080; '>\ на входе — строка с арифм. выражением, на выходе — корректность</span>
<span style='color:#008c00; '>1</span><span style='color:#800000; '> </span><span style='color:#000084; font-weight:bold; '>TO</span> размер-символа <span style='color:#000084; font-weight:bold; '>SWAP</span> поставить-курсор
parens <span style='color:#000084; font-weight:bold; '>0!</span>
 wait-for-digit-or-( -символов-обработать
parens <span style='color:#000084; font-weight:bold; '>@ </span><span style='color:#000084; font-weight:bold; '>0=</span><span style='color:#000084; font-weight:bold; '> ;</span>

<span style='color:#808080; '>\ включить-отладку-автомата</span>
<span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>(1+(2-3))</span><span style='color:#000084; font-weight:bold; '>"</span> подсчитать-скобки <span style='color:#000084; font-weight:bold; '>.</span>
<span style='color:#808080; '>\ вывод: -1 (TRUE)</span>
<span style='color:#000084; font-weight:bold; '>S" </span><span style='color:#0000ff; '>(</span><span style='color:#000084; font-weight:bold; '>"</span> подсчитать-скобки <span style='color:#000084; font-weight:bold; '>.</span>
<span style='color:#808080; '>\ вывод: 0</span>

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



То что автомат можно соптимизировать и убрать состояние 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