Skip navigation.

exploreopera

| Help

Sign up | Help

проФорт

Форт и всё такое

avatar

Конечные автоматы и таблицы решений на SPF

,

Наработка выросла из необходимости быстро написать парсер для html (для дипломной работы и в образовательно-показательных целях задача стояла писать велосипеды и не брать готовое). А как известно, конечные автоматы — это самое оно для сканеров и прочих лексических анализаторов. В итоге всей годовой работы автоматы (дальше — КА) и написание (рисование) схем для анализа html-текстов были наиболее приятной и наиболее богатой на полезные последействия подзадачкой.

Наработка уже немножко выросла из коротких штанишек (хотя и не избавилась до конца от своих родовых, студенческих пятен — например, имён переменных и процедур на русском языке [sic!], только недавно, с месяц назад, задним числом были добавлены синонимы в латинице). Активно используется, например, в ygrek'овых регулярных выражениях на SPF (NFA-реализация) и конечно в моих программках на скорую руку (см. ссылки на примеры кода в конце).

Для тех, кому незнакомо что же есть такое "конечные автоматы", прошу обращаться в обзорные статьи: "От тьюрингова программирования к автоматному", раздел на 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:


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

Распечатка стека возвратовПростой сканер портов - 3

Comments

avatar
а вот интересно, как изменится схема, если перейти на unicode ?
или, говоря иначе, что делать при увеличении числа состояний/переходов?

КА ведь вещь достаточно "рыхлая".... памяти ест много....

By garbler, # 27. July 2007, 05:42:55

avatar

Originally posted by garbler:

а вот интересно, как изменится схема, если перейти на unicode ?

Конкретно реализация HTML-обработчика в дипломке не требовала от меня анализа не-ASCII символов (русских букв и прочего), поэтому все символы с кодами выше 256-и обрабатываются "на общих основаниях", то есть реакцией задавемой через all:.

Originally posted by garbler:

КА ведь вещь достаточно "рыхлая".... памяти ест много....

Хм. Текущая реализация с простым массивом реакций требует 4 байт * (256 реакций на ASCII-символы + 3 спец. сигнала) = ~1Кб на одно состояние автомата. Даже если мы потребуется анализировать все Unicode-множества, то пусть и получится многовато для отдельных применений, но всё равно достаточно по-божески: 4 байт *(65 536 реакций на каждый U-символ+3) = ~64Кб на одно состояние (при UTF-16).

Буде возникнет особая нужда в этом, можно и перевести внутреннюю механику КА на хранение сигналов и реакций на них в виде хэшей…

Пока не нужно было.

By profiT, # 27. July 2007, 06:19:10

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

By exs, # 27. July 2007, 17:40:53

avatar
хм, вообще-то не 64кб, а 256, что уже существенно больше.
а вот с хэшами уже интереснее..... я к тому, что было-бы
интересно подумать о механизме глобальной оптимизации/упаковки
всего автомата. в хаскеле вот для этой цели механизм монад
расширили (дополнительным параметром, по которому и производят
оптимизацию), новый тип называется Arrow.... в общем, тут есть
поле для экспериментов.

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

а о синтаксисе/расширяемости никто и не спорит, я знаю,
что в этом вопросе форт так проектировался изначально и
остальные языки уже заимствовали из форта (ридер-макросы
в лиспе и т.п.). вопросы становления хорошо в статье из
HOPL2 от основателей описаны.

собственно, я даже предполагаю, что на использовании лексикона
расширение алфавита может не отразиться, но сам вопрос
остаётся, что делать в ситуациях, когда ввод не ascii.

более того, этот вопрос остаётся для абсолютно любого
языка программирования :-) и форт тут совершенно не при чём....

By garbler, # 28. July 2007, 10:50:20

avatar

Originally posted by garbler:

хм, вообще-то не 64кб, а 256...

Мда, звиняюсь… Никогда не был силён в арифметике — потому и стал программистом.

Originally posted by garbler:

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

Может быть и интересно, не знаю… Только оптимизировать максимум 20 состояний с не больше чем пятью-семью веточками у каждого (это самый сложный автомат что под рукой) — это как-то пушковоробьино.

Ну, если есть у людей такая задача -- то было бы интересно посмотреть… Хотя вот ygrek давно выцыганивает у меня сбор статистики о работе автомата (фактически — профилирование).

By profiT, # 28. July 2007, 19:20:24

avatar
Достойно упоминания то что дизассемблер SPF (lib/ext/disasm.f) изначально написанный Эндрю МакКюэном в 94-м, работает на двух таблицах переходов по 256 событий: для основной и расширенной систем команд.

А фича тут в том, что можно временно в run-time переопределив отдельные реакции из таблицы переходов получить другое поведение, например, перенос кода на другой адрес вместо дизассемблирования.

By profiT, # 31. July 2007, 13:23:53

avatar
разбор систем команд процессоров - это отдельный разговор :-)
здесь своя специфика, но, даже для этого примера -
только у интела "гранулярность" байтовой будет,
для других процессоров это не так:
например
это фрагмент дизассемблера для NEC V850
idpcmrec.pp порождает iddv850e.ipp который используется
в iddv850e.cpp

у V850 базовой единицей при разборе команды будет 32 бита
(архитектурно - типичный risc)

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

By garbler, # 2. August 2007, 07:53:01

avatar
Да какие проблемы.

Просто частное решение частной задачи на частной архитектуре.

By profiT, # 2. August 2007, 13:07:41

avatar
Anonymous writes:

поведение, например, перенос кода на другой адрес вместо дизассемблирования.

http://fforum.winglion.ru/viewtopic.php?p=9361#9361

В топике нет информации по переносу кода на другой адрес.

By anonymous user, # 24. April 2008, 07:21:35

avatar
Правильная ссылка (это не более чем набросок):
~profit/misc/movecode2.f.

By profiT, # 24. April 2008, 13:23:05

Write a comment

Comment
(BBcode and HTML is turned off for anonymous user comments.)

Please type this security code : c86af4

Smilies