Автомат-сканер текста и таблицы решений -- chartable.f

profiT

Действующие лица:
Jump-table, они же таблицы переходов, они же таблицы решений, он же ON GOSUB...
Сканер, он же лексический анализатор, он же парсер (хотя тут часто путаница из-за неправильного понимания...).
Автоматы, используемые для разбора строк.

Использовано в моём недо-браузере для разбора HTML (вот к нему пояснительная записка) и ещё кое-где из пока неопубликованного.

Объяснять дополнительно не буду, просто дам примеры (тем более что я уже объяснял в пояснительной записке; плохо ли, хорошо ли, но ещё раз уже лень).

Пример, таблица решений (переходов):

Код:

REQUIRE таблица ~profit/lib/chartable.f

таблица раздватри \ три состояния
выполняет: ." I" ;
выполняет: ." II" ;
выполняет: ." III" ;
9 диапазон: ." IV-IX" ;

раздватри
\ вывод: IV-IX

Вот ещё пример:

Код:

REQUIRE таблица ~profit/lib/chartable.f
256 таблица символы \ таблица обработчиков символов
все: ." не знаю такого" ;
разделители: ." разделитель, но не пробел" ;
пробел: ." пробел" ;
перевод-строки: ." перевод-строки" ;
CHAR 0 CHAR 9 диапазон: ." цифра" ;

CHAR a CHAR z диапазон: ." буква" ;
CHAR A CHAR Z диапазон: тоже-самое ;
CHAR а CHAR я диапазон: тоже-самое ;
CHAR А CHAR Я диапазон: тоже-самое ;

CR KEY символы CR

Автомат разбора текста (каждое состояние=таблица переходов с 256+несколько специальных обработчиков):

Код:

REQUIRE состояние ~profit/lib/chartable.f

VARIABLE счётчик

состояние не-считать
состояние прибавлять
состояние отнимать

не-считать
\ все: ;  \ необязательно, по-умолчанию так и есть
символ: | не-считать ;
символ: +  прибавлять ;
символ: -  отнимать ;

прибавлять
\ взять-из-таблицы не-считать ( \ копируем обработчики |+-, в старой chartable.f ошибка с этим, поэтому закомментировано
символ: | не-считать ;
символ: +  прибавлять ;
символ: -  отнимать ; \ )

CHAR 0 CHAR 9 диапазон:  счётчик 1+! ;

отнимать
\ взять-из-таблицы не-считать ( \ копируем обработчики |+-
символ: | не-считать ;
символ: +  прибавлять ;
символ: -  отнимать ; \ )

CHAR 0 CHAR 9 диапазон:  -1 счётчик +!  ;

: пустить-автомат ( a u -- )
1 TO размер-символа SWAP поставить-курсор
не-считать
-символов-обработать ;

S" 12+345-67|90" пустить-автомат
счётчик @ .
\ вывод: 1

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

Как ещё один пример могу предложить посмотреть (для запуска надо будет тащить всё остальное окружение, поэтому даю только отрывок) отрывок из xml-сканера:

Код:

...
в-тексте
на-входе:  отсюда начать-копить ;
все:  копить-дальше ;
символ: <  сбросить-накопленное в-ожидании-имени-тэга ;
строка-кончилась:  сбросить-накопленное ;

: от-конца-накопленного-текста
накопленный-текст 2@ + начать-копить
отсюда протянуть вернуть-букву  сбросить-накопленное ;

в-ожидании-имени-тэга
все:  вернуть-букву  в-имени-тэга ;
символ: ! в-комментариях ;
символ: >  от-конца-накопленного-текста в-тексте ;
символ: /  в-имени-закрывающегося-тэга ;
строка-кончилась:  от-конца-накопленного-текста ;

в-имени-тэга
на-входе:  отсюда начать-копить ;
все:  копить-дальше ;
разделители:  имя-тэга запомнить  имя-тэга 2@ открыть-тэг  в-ожидании-имени-атрибута ;
символ: >  имя-тэга запомнить  имя-тэга 2@ открыть-тэг  закончить-атрибуты  в-тексте ;
строка-кончилась:  от-конца-накопленного-текста ;

в-имени-закрывающегося-тэга
на-входе:  отсюда начать-копить ;
все:  копить-дальше ;
разделители:  имя-тэга запомнить  имя-тэга 2@ закрыть-тэг  пропустить-атрибуты ;
символ: >  имя-тэга запомнить  имя-тэга 2@ закрыть-тэг  в-тексте ;
строка-кончилась:  от-конца-накопленного-текста ;

TRUE VALUE реагировать-на-закрывающую
в-комментариях
на-входе:  отсюда начать-копить ;
все:  копить-дальше ;
символ: > реагировать-на-закрывающую IF общий-накопитель 2@ внести-комментарий  в-тексте ELSE копить-дальше THEN ;
символ: - дать-букву [CHAR] - = IF копить-дальше  реагировать-на-закрывающую 0= TO реагировать-на-закрывающую
ELSE вернуть-букву THEN копить-дальше ;
...

... которому примерно соответствует эта иллюстрация из моего диплома:

Общие вопросы:
1. Нужно ли делать несколько автоматов? Пока не уверен, но наверно всё-таки надо... С другой стороны во всех программах в которых я использовал эту библиотеку автомат пусть и использовался с разными замкнутыми наборами состояний, но использование их всегда как-то само собой разносилось по времени.
2. Накопители (collectors.f, как полный и работающий пример: ~profit/prog/browser.f)... Насколько оправданно их применение? Не лучше ли всё-таки переносить в кучу? Когда писал браузер это было нужно (всего лишь) пару раз (для WinAPI функций, требовавших строк оканчивающихся на ноль, тогда как у меня были только накопители-обрывки из главного текста).

Вопросы по реализации:
3. Слово 'пустить-автомат'. Пока получается, что определять его надо отдельно от самой библиотеки. Вначале нужно указать сколько занимает каждый символ во входной последовательности: 2 (уникод) или 1 (всё остальное). Потом устанавливаем курсор-бегунок на начало последовательности. И после этого только можно устанавливать начальное состояние автомата. Потому что состояние когда активируется может иметь обработчик, который почти всегда будет использовать текущее значение курсора. И после этого запускаем или '-символов-обработать' с указанием кол-ва символов в последовательности, или 'обрабатывать-до-сигнала' который работает пока переменная 'продолжать-обработку' не равна нулю.
4. Нужно ли делать возможным запуск автомата из обработчика автомата? Опять же, практической необходимости в этом пока не возникало...
5. Я так понимаю, что это должно быть много быстрее чем обычные CASE. Или нет?

WingLion

profiT писал(а):

(вот к нему пояснительная записка: http:/forth.org.ru/~profit/diplom.pdf)

После http: обычно ставится два слэша: http://forth.org.ru/~profit/diplom.pdf

profiT

Спасибо, исправил.

Гость

Пролистнув книгу по Форту(Кейли) натолкнулся на близкую
синтаксическую конструкции ACASE и NCASE из MMS форта
Пр по памяти:
( символьный кейс если A то word1 , если пробел то word2 и т.д
если сравнения не нашли то слова после OTHERWISE )
: ... ACASE A B" word1 word2 word3" OTHERWISE ... ENDCASE ;

: ... NCASE 1 2 3 " word1 word2 word3" OTHERWISE ... ENDCASE ;

profiT

Цитата:

Пролистнув книгу по Форту(Кейли) натолкнулся на близкую
синтаксическую конструкции ACASE и NCASE из MMS форта

Не знаю про реализацию в этой системе. У меня это сделано так:

Код:

: таблица ( число-случаев "имя" -- )
CREATE
HERE TO текущее-состояние
0 DO отдыхают , LOOP
DOES> SWAP CELLS + @ EXECUTE ;

То есть создаётся n адресов подпрограмм, и при вызове созданного слова оно берёт число со стека и вызывает n-й адрес.

Опять же, chartable.f -- не синтаксическая конструкция. Слова, нужные для создания и разворачивания таблиц даже не IMMEDIATE.

chess

profiT писал(а):

5. Я так понимаю, что это должно быть много быстрее чем обычные CASE. Или нет?

Однозначно быстрее - не нужно обходить в среднем половину веток CASE.

profiT

Цитата:

Однозначно быстрее - не нужно обходить в среднем половину веток CASE.

Не понял... Обхода же вообще нет, только косвенный переход?..

chess

profiT писал(а):

Не понял... Обхода же вообще нет, только косвенная адресация?..

Обход был бы в случае использования CASE, а не таблиц.

profiT

Цитата:

Я так понимаю, что это должно быть много быстрее чем обычные CASE. Или нет?

Однозначно быстрее - не нужно обходить в среднем половину веток CASE.

Мне это не так однозначно, потому и спрашиваю. Вроде бы jmp [eax] жрёт (гораздо?) больше тактов, чем jmp "куда-то".

chess

profiT писал(а):

Мне это не так однозначно, потому и спрашиваю. Вроде бы jmp [eax] жрёт (гораздо?) больше тактов, чем jmp "куда-то".

Команда jmp [eax] - косвенный переход, если внутри сегмента - то 3 такта, если межсегментный переход, то максимум 18 тактов, jmp "куда-то" - число тактов такое же.

ygrek

Я просмотрел или как добыть текущий символ, т.е. например в ветке все: как узнать что за символ сейчас в автомате?
Например так

Код:

: этот-символ отсюда размер-символа - размер-символа взять-букву ;

Пожелания:
Стековых комментариев добавить.
Примеры (те что в этом треде) добавить в саму либу.
Оформить в виде модуля.
И наконец залить всё на CVS.

profiT

Цитата:

Я просмотрел или как добыть текущий символ, т.е. например в ветке все: как узнать что за символ сейчас в автомате?

Есть слово "символ" (самое первое определение в библиотеке).

Цитата:

Стековых комментариев добавить.
...
Оформить в виде модуля.

Угу.

Цитата:

Примеры (те что в этом треде) добавить в саму либу.

Чего-то мне кажется что немножко большие примеры, впрочем ладно.

Цитата:

И наконец залить всё на CVS.

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

Опять же меня ещё тревожит вопрос о языке (русские названия слов), но это уже другая немного тема...

profiT

Цитата:

И наконец залить всё на CVS.

Вчера.

profiT

Пример использования. Сразу двойной.

Дано: желание почитать в выходные (сегодня) книжку. У книжки формат [url=http://www.fictionbook.org/index.php/FictionBook_2.0_-_краткая_информация]FB2[/url]. С форматом этим я борюсь спец. XSL-преобразователем, который делает мне из файла Word'овский файл с нужным мне форматированием для распечатки (альбомная ориентация, три колонки, расстановка переносов, оформление заголовков и абзацов). И всё бы хорошо если бы не иллюстрации. В FB2 они внедряются в исходный текст, в тэг binary через base64. Раньше обходился и вручную вставлял картинку, но у сегодняшней книжки туча иллюстраций.

Хорошо, за два часа программа слеплена и я могу печатать и зачитываться:

Код:

REQUIRE FILE ~ac/lib/str4.f
REQUIRE открыть-тэг ~profit/lib/xmlscanner.f
REQUIRE COMPARE-U ~ac/lib/string/compare-u.f
REQUIRE base64 ~ac/lib/string/conv.f
REQUIRE split ~profit/lib/bac4th-str.f
REQUIRE взять-параметр ~profit/lib/parsecommand.f

REQUIRE ZPLACE ~nn/lib/az.f
CREATE tmp 100 ALLOT

0 VALUE двоичный-тэг?
0 VALUE вывод

:NONAME S" binary" COMPARE-U 0= TO двоичный-тэг? ; TO открыть-тэг

:NONAME двоичный-тэг? IF
S" id" COMPARE-U 0= IF убрать-кавычки

вывод IF вывод CLOSE-FILE THROW THEN

tmp ZPLACE
tmp ASCIIZ> R/W CREATE-FILE THROW TO вывод

ELSE 2DROP THEN ELSE 2DROP 2DROP THEN ; TO внести-атрибут
:NONAME двоичный-тэг? IF ( addr u )
START{ byRows split \ из текста нужно убрать переводы строк
DUP STR@ debase64 вывод WRITE-FILE THROW
}EMERGE
ELSE 2DROP THEN ; TO внести-текст


: вычленить-изображения ( addr u -- ) 1 TO размер-символа SWAP поставить-курсор в-тексте -символов-обработать ;

:NONAME
GetCommandLineA начать-обрабатывать-командную-строку
взять-параметр 2DROP
взять-параметр FILE вычленить-изображения BYE ;
MAINX ! 0 TO SPF-INIT? TRUE TO ?GUI S" extractImg.exe" SAVE BYE

На вход командной строки получает имя FB2-файла, и если в его дереве есть узлы с именем "binary", то их текстовое содержимое будет раскодировано из base64 и положено в файлы с названием из атрибута "id" этого узла.

Сканер используется и в ~profit/lib/parsecommand.f, и в ~profit/lib/xmlscanner.f (да, я знаю что этот недо-сканер неправильно обрабатывает тэги вида "<tag />").

Alex

Привет, адаптация FSM (конечного автомата) от J.V.Noble под spf4

Код:

\ =============================================================================
\ FSM Records                                          M=NSTATES*NINPUTS
\ ptr -++- to FSM
\      ||
\      \/
\
\  | FSM states | FSM inputs | exec-word1 | next-state1 | . . . | exec-wordM | next-stateM | 
\ =============================================================================


: ?ALLOT HERE SWAP ALLOT ;


: FSM: ( NSTATES NINPUTS -- )
  CREATE 2DUP * CELLS 2* 2 CELLS + ?ALLOT DUP >R CELL+ ! DROP R> 2 CELLS + ;

\ terminated definitions of FSM

: FSM; DROP ;

\ execute one step in FSM (ptr) with input N

: FSM! ( N ptr -- ) DUP >R 2@ * +  2* 2+ CELLS R@ + DUP >R @ EXECUTE R> CELL+ @ R> ! ;

: [[ ( ADDR1 -- ADDR2 ) ' OVER ! CELL+ ;
: ]] ( ADDR2 N -- ADDR3 ) OVER ! CELL+ ;
: |  ]] [[ ;


\ === EXAMPLE ============================================


\ : WITHIN OVER - >R - R> U< ;

: DIGIT? ( N -- FLAG) [CHAR] 0 [CHAR] : WITHIN ;
: DP? ( N --FLAG ) [CHAR] . = ;
: MINUS? ( N --FLAG) [CHAR] - = ;

: CAT->COL# ( C -- N )
  DUP  DIGIT? 1 AND                 \ DIGIT -> 1
  OVER MINUS? 2 AND +               \     - -> 2
  SWAP    DP? 3 AND +               \    DP -> 3
;                                   \ OTHER -> 0

3 4 FSM: <FIXED>
\                i  n  p  u  t  s
\
\ state:    other?   digit?   minus?    dp?
\                       
  ( 0 )  [[ DROP 0 | EMIT 1 | EMIT 1 | EMIT 2 ]]
  ( 1 )  [[ DROP 1 | EMIT 1 | DROP 1 | EMIT 2 ]]
  ( 2 )  [[ DROP 2 | EMIT 2 | DROP 2 | DROP 2 ]]
FSM;

: AAA
  0 <FIXED> !
   BEGIN 
    KEY DUP 13 <> OVER 10 <> AND
   WHILE
    DUP CAT->COL# <FIXED> FSM!
   REPEAT
DROP ;

Автомат-сканер текста и таблицы решений -- chartable.f

Кто сейчас на конференции