Автоматная реализация магазинных автоматов

В. C. Любченко

Программа, демонстрирующая решение описываемой задачи (92 кб)

Предыстория

В форуме сайта SoftCraft [1] в теме «Процессы, которые мы потеряли» А.Легалов отметил, что та или иная технология будет только тогда интересна, когда обладает определенными преимуществами. Или дословно: «Покажите всем, что КА-технология дает эффект, недостижимый с использованием других средств». Эти в целом справедливые слова стали стимулом дальнейших действий, дабы на примере реализации так называемых магазинных автоматов (АМП) в рамках КА-технологии показать ее достоинства (подробнее о КА-технологии см., например, [2]). Тем более, что сравнить есть с чем, т.к. сами АМП подробно описаны в лекциях А.Легалова (см [3,4]) и реализованы им же, но с применением традиционной технологии программирования (см [5]). И несмотря на то, что по словам А.Легалова так сделано с целью достижения простоты решения, ясности и доступности его понимания студентами, представленная реализация АМП перегружена деталями, которые к магазинным автоматам имеют весьма отдаленное отношение. Одна из причин этого – свойства используемой программной технологии.

Об автоматной реализации магазинных автоматов

Задача разбора строк решается во многих случаях. Особенно, если программа должна поддерживать тот или иной диалог общения с пользователем. Пользователь, взаимодействуя с программой, желает, чтобы она не только его понимала, но и помогала ему вести диалог: корректировала ошибки ввода, давала подсказки для ввода команд и т.п. И все это, конечно, в динамике, т.е., к примеру, так, как принято в технологии IntelliSense, используемой в наиболее совершенных современных системах визуального проектирования.

Проблема создания какого-либо диалога/протокола родственна проблемам формализации и реализации языка программирования, где теория конечных автоматов, модели конечных автоматов вообще и модель магазинного автомата в частности – ключевые темы. Но, анализируя литературу по компиляторам, невозможно не заметить разницу между теорией и практикой, разницу между теоретической моделью – конечный автомат (КА), и моделью, используемой для реализации – обычно модель блок-схем (БС). Именно поэтому программисты используют широко известные и отработанные методы программной реализации автоматов. К ним относится, например, SWITCH-технология [6]. Но при таком подходе остается этап преобразования исходной модели, который не только, как можно показать, не всегда однозначен, но при «ручном» преобразовании чреват еще и ошибками.

Но существует другой ныне очень популярный путь реализации моделей – использование виртуальных машин. Такой подход положен и в основу КА-технологии. В ней виртуальная конечно-автоматная машина представлена библиотекой FSA, созданной с помощью средств Microsoft Visual C++. При этом она реализует даже более мощную формальную модель, чем просто модель конечного автомата. В ней модель КА лишь составная (хотя и базовая) часть общей модели (см. описание модели СМКА в [7]). Дальнейший материал не только показывает возможности FSA в реализации автоматных моделей вообще и АМП в частности, но и демонстрирует параллельную модель и технологию на ее базе, которые позволяют создавать решения, аналога которым, по сути, нет в рамках существующих технологий проектирования программ.

Автоматная реализация автомата звучит как тавтология. Но суть идеи именно такова: заданную модель магазинного автомата необходимо реализовать, используя другую автоматную модель - в данном случае автомат Мили. С этой целью к нему необходимо добавить соответствующие структуры данных и определить множество операций над ними. Как это можно сделать далее и будет показано. Ну и конечно не только это.

Структурная модель программы

Структурная модель программы реализующей работу магазинного автомата со структурными связями между блоками представлена на рис.1. листа 1 проекта. Программа состоит из следующих структурных блоков: блок ввода символов – EntranceType (ET), фильтр символов – FilterSymbol (FS), магазинный автомат – PushDown (PD), блоки отображения ошибок разбора – ViewError (VE) и вывода отладочной информации – ViewDebug (VD), блок отображения внутренних состояний блоков – ViewStates (VS).

Блок ET отвечает за техническую реализацию ввода символов. Его задача – выдать символ, а как будет введен символ и откуда это внешнюю среду мало интересует. Смысл в том, что выданные данным блоком символы будут представлять (или, что точнее, как мы увидим, включать) ту последовательность или просто символьную строку, анализ которой нужно провести.

Чтобы не ограничивать возможности блока ET и в то же время контролировать выдаваемую им информацию удобно ввести блок, который будет фильтровать множество символов выдаваемых блоком ЕТ, пропуская через себя только их определенный набор. Кроме того, так можно легко с помощью нескольких таких фильтров организовать разделение одного потока символов на их множество, организовав обработку символов с выхода каждого фильтра. В нашем случае фильтр только один и представлен блоком FL.

Блок FL подключен выходом к блоку, который является ядром программы, выполняя поставленную задачу - анализ (распознавание) последовательности символов. На схеме это блок PD. Если поступивший на его вход символ не соответствует критерию, определяемому правилами (грамматикой) описания входных строк, то блок информирует об этом внешнюю среду.

Информация об ошибках разбора входной строки обрабатывается и отображается блоком отображения ошибок (VE). Определено, что блок PD передает VE только код ошибки. Последний интерпретирует его и выводит информацию об ошибке уже в наглядной форме. Информация об успешной работе по анализу входных символов обрабатывается блоком отображения отладочной информации (VD). Эта информация включает текущий входной символ, символ в вершине стека, шаг разбора и т.п.

Легко видеть, что структурная модель определяет общее направление в реализации программы, разделяя программу на блоки/модули, которые функциональности достаточно независимы. Например, блок АМП независим от технической процедуры ввода символов и/или подхода к реализации фильтрации входного потока символов. Последние блоки могут быть реализованы также независимо друг от друга и самым разным образом. Их функции могут меняться и это ни как не должно влиять на функции, выполняемые блоком PD (АМП). И еще более независимы от этих блоков функции, реализуемые блоками VE, VD и VS. При той или иной реализации эти блоки могут даже отсутствовать.

Модель взаимодействия блоков

Блоки работают параллельно и при этом взаимодействуют друг с другом, а потому нужно определить процедуры (протоколы) общения между ними. Если этого не сделать, то из-за асинхронной работы блоков могут возникнуть ошибки, сбои в работе. Например, если блок ввода выдаст на свой выход символ, а фильтр еще обрабатывает предыдущий, то он для блока PD будет потерян. Или, к примеру, как тому же фильтру узнать, что на его входе появился новый символ? Ведь он может совпадать с предыдущим. Т.е. для согласованной работы блоков, нужно определить перечень сигналов и процедуры обмена ими. На рис.1 листа 2 проекта представлена модель программы, но уже с отражением синхронизирующих связей.

В модели взаимодействия блоков определено, что сигнала sym на выходе блока ET определяет выдаваемый символ (сам символ передается по другому не изображенному на схеме каналу). А появление на одном из входов блока ET сигнала «ok» говорит о том, что символ обработан внешней средой, а потому можно приступить к приему очередного символа.

Значение сигнала «yes» определяет символ уже на выходе блока FL. А сигналы «er» и «ok» на выходах блока PD индицируют ошибку или распознавание последовательности символов. При этом сигнал «er» сопровождается номером ошибки, которая, следуя схеме, передается в блок отображения ошибок. Кроме сигналов «er» и «ok» блок PD формирует сигнал «АМП» информирующий о том, что символ принят в обработку. Данный сигнал соответствует определенному состоянию распознавателя, которому соответствуют символ в вершине стека АМП и символ на его входе. Эта информация воспринимается блоком отображения отладочной информации, который ее выводит (в файл или на экран) в желаемой форме.

Блок VT формирует строку из символов успешно обработанных блоком PD. Добавление текущего символа происходит, если на очередном шаге работы блок PD не выдает сигнал «er». Такой символ запоминается блоком VT в своем буфере распознанных символов.

Также отметим, что работа блоков VE и VD не синхронизирована с работой блока PD. Мы условно считаем, что скорость их работы достаточна для того, чтобы отследить текущее состояние блока PD и отобразить соответствующую этому состоянию информацию. В соответствии с этим же принципом строится и работа блока VS.

О пассивных и активных и фильтрах

Символ, если он входит во множество входных символов, будет пропущен объектом FL. В этом смысле FL представляет собой пассивный фильтр, т.к. этот же символ может отвергнуть объект PD, а потому он и не попадет в выходную строку, которую формирует VT. Таким образом, вместе блоки FL, PD и VT представляют собой активный фильтр, где на вход FL поступаю любые символы, а на выходе блока VT образуется строка из допустимых символов. Таким образом, АМП может быть ядром активного фильтра, выделяющего из последовательности символов не просто отдельные символ/символы, а их последовательность, определяемую грамматикой.

В связи с темой активности фильтров можно представить достаточно фантастическую, но в определенной степени реальную ситуацию. Если есть грамматика, описывающая язык, то можно будет построить систему обучения, которая по ходу будет корректировать фразы языка, допуская «на выход» только корректные его предложения. Т.е. возможно исправление «на лету» «фефектов» речи. По сути, это прямо сейчас (в момент написания этих строк) и продемонстрировал редактор Word, выделив слово «фефект», как нераспознанное им.

Здесь есть и один тонкий момент. Редактор Word, к примеру, распознает слово лишь после того, как будет введен символ пробела, завершающий текущее слово. В данном случае символ «пробела» - это так называемый концевой маркер. В практике проектирования компиляторов автомат распознающий от автомата обрабатывающего отличаются именно по расширению последних символом концевого маркера [8]. В остальном эти автоматы похожи. Но, исходя из их сравнения, можно сказать, что только распознающий автомат может быть ядром активного фильтра. Только он реагирует на каждый поступающий символ, а не ожидает прихода концевого маркера, чтобы принять то или иное решение. В силу же отсутствия концевого маркера распознаватель и компактнее обрабатывающего автомата.

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

Так что добавленный выше блок VT выполнил функцию не только простого отображения выходной ленты, а по существу ее формирование из символов, прошедших двойную фильтрацию: пассивным фильтром FL и активным фильтром PD. Похоже, так поступает и Word: по вводу «пробела» делает анализ слова, по «точке» - анализ предложения …

И еще о разборке «на лету». Какие-то ошибки можно «ловить» сразу, не дожидаясь концевого маркера. Например, последовательность вложенных скобок не может начинаться с символа закрывающей скобки. Также я не знаю слов, которые начинаются с символа «твердого знака». И, наверное, поэтому Word сразу распознает строчный символ после точки и затем исправляет его (конечно, если настроен на соответствующее действие). Я не знаю, как запрограммированы отмеченные особенности работы редактора Word, но они вполне могут быть сделаны по схеме, рассмотренной нами при реализации окружения магазинного автомата.

Еще раз о фильтрации потока символов

Можно, конечно, просто отбрасывать символы не прошедшие фильтр. Особенно, если это пассивный фильтр. Но как быть, если, к примеру, хочется посмотреть содержимое ленты еще до завершения ввода текущей строки? Очевидно, что это должна быть какая-то команда и, возможно, состоящая даже не из одного символа (тогда лучше, чтобы множество этих символов не пересекалось с множеством входных символов АМП). Это может быть и набор различных команд, но которые хочется выполнить в процессе ввода строки.

В «обычной реализации» сложно это сделать (даже просто представить сложно). В рассматриваемой нами программе – почти элементарно. Что, например, нужно сделать теперь, чтобы отображать содержимое выходной ленты в любой момент при нажатии клавиши «=»? Теперь это сделать очень просто! На структурном уровне все сводится к установлению связи между блоками ET и VT. И все будет работать! Фильтр не пропустит символ «=» на вход АМП, но зато он попадет к объекту VT, который и отреагирует на него выводом текущего содержимого выходной ленты АМП. Теперь в любой момент, нажав клавишу «=» можно будет сразу же увидеть текущее содержимое выходной ленты АМП и, возможно, принять решение какой очередной символ вводить.

Кроме собственно команд внутри тех же скобок должны стоять и другие так называемые лексемы. Это переменные, знаки арифметических выражений и т.п. Фильтрация хороша тем, что, например, применение пассивного фильтра «отсекает» символы не входящие во множество входных символов активного фильтра. И, например, пока «фильтр скобок» ждет закрывающей скобки, «фильтр переменных» распознает переменные, а «фильтр арифметических выражений – правильные их комбинации объединенные знаками арифметических операций и т.д. и т.п. И очевидно, когда появится наконец-то завершающая скобка и фильтр скобок возобновит анализ, фильтры, задействованные до ее появления, должны отработать на «ОК».

Фильтры позволяют разделить общий поток символов на множество направлений и выполнять независимый анализ каждого из таких потоков. И очевидно, что конечный результат распознавания входной последовательности, содержащей все введенные символы, наверное, должен определяться результатами анализа созданных фильтрами потоков. При этом, возможно, что над множеством таких активных фильтров (распознавателей) должен быть объект, анализирующий результаты их совместной работы.

Алгоритмические модели блоков

Алгоритмические модели блоков в форме автоматных моделей представлены на листах 3-9 проекта (листы 3, 4, 5.1, 5.2, 6, 7, 8, 9). Там же есть и необходимые пояснения. Из описаний видно, что модели ориентированы на объектную реализацию, хотя это не является столь уж необходимым и обязательным. Просто и библиотека FSA (см. ссылки на базовый класс LFsaAppl), реализованная на базе С++ и сам язык С++ предоставляют для реализации автоматных моделей средства, которые грех было бы не использовать.

Необходимо отметить лишь некоторые общие соображения, в какой-то мере повлиявшие на вид автоматных моделей блоков. Во-первых, завершение работы моделей привязано к активности блока ET: пока он работает - работают и остальные блоки, а блок ET завершает свою работу, когда на его входе появляется символ ESC.

Общий алгоритм совместной работы всех блоков следующий.

1. Воспринимаются все символы, вводимые с клавиатуры. Просто те, которые не принадлежат грамматике или не являются командами типа символов «=», ESC или END (Enter) отображаются, но не обрабатываются блоками программы.
2. В любой момент можно ввести команду «=» и программа отобразит строку символов, прошедших активную фильтрацию. Другими словами, чтобы вы не вводили, программа в конечном итоге сформирует синтаксически правильную строку.
3. Выдаваемые программой сообщения ни как не влияют на вид сформированной строки.
4. Завершение работы программы происходит при нажатии клавиши «Esc».

Отличительные особенности работы программы по сравнению со стандартной реализацией [5]:

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

Также необходимо отметить изменения в самом магазинном автомате. Он именно в той форме, с которой начинается его определение, т.е. в форме распознавателя. В его основе та же грамматика, что и АМП в [5], но он много проще, т.к. не содержит обработку концевого маркера, а от этого, как минимум, его таблица переходов компактнее. Соответственно компактнее и проще получается реализация такого автомата.

Об окружении АМП

В проекте магазинный автомат представлен блоком PD. Все остальные блоки вспомогательные. Одни из них явно будут заменены в более совершенной версии программы, другие возможно даже исключены. Так, блок ET для Windows-приложения, скорее всего, будет другим. Для этого же типа приложения несколько иным будет код блоков VE, VD в силу других принципов ввода/вывода информации. Более того, в окончательной версии программы эти блоки и в дополнении к ним блок VS, скорее всего, будут или заблокированы или будут даже отсутствовать совсем. Они необходимы на этапе отладки программы, но не столь уж нужны в реально работающем приложении.

Структура программы такова, что можно заменить и сам центральный блок PD. Даже не обязательно, чтобы он работал на принципе модели магазинного автомата. Но чтобы эти изменения не оказали влияния на остальные блоки, необходимо, чтобы новый блок функционировал в соответствии с определенными для него протоколами взаимодействия с другими объектами. В этом случае последние даже не заметят подмены.

Проект содержит и лист 10, который содержит временную диаграмму работы блоков модели. На ней в динамике отражен переход объектов из одного внутреннего состояния в другое. Сформирована диаграмма на основе информации выдаваемой блоком VS. В данном случае это сделано вручную, но аналогичную работу можно вполне переложить на объект, который такой графический вывод сделает автоматически и даже в реальном времени. Это, хоть и сложная, но достаточно рутинная операция. Но иметь такую диаграмму очень хорошо, т.к. подобная информация очень наглядна и важна с точки зрения анализа работы программы.

Выводы

Безусловно, данный проект намного сложнее даже просто по объему кода, чем представленный в [5]. Но если рассмотреть собственно реализацию магазинного автомата, то в данном проекте она 1) проще и 2) более «автономна». Сложность проекту создает окружение АМП (блока PD), а не сама реализация магазинного автомата. Он не только очень прост, но и может быть легко перенесен в любой другой проект. И все же напомним, что основная цель в [5] была изучение и реализация магазинных автоматов. Мне кажется, что в данном проекте она решена более гармонично и несмотря даже на его относительную сложность. При этом понятие «сложность» нужно относить к проекту в целом, а не к его отдельным частям – блокам, которые очень просты. В [5] реализация это по существу один блок, сложность которого превышает сложность любого из блоков рассмотренного нами проекта автоматной реализации АМП.

Литература

1. Легалов А. Сайт SoftCraft. http://www.softcraft.ru

2. Любченко В.С. Конечно-автоматная технология программирования. http://www.softcraft.ru/design/katech/

3. Легалов А. Применение автоматов с магазинной памятью для нисходящего разбора слева направо. http://www.softcraft.ru/translat/lect/t07-01/

4. Легалов А. Организация автомата с магазинной памятью. http://www.softcraft.ru/translat/lect/t07-02/

5. Легалов А. Программная реализация нисходящего автомата с магазинной памятью. http://www.softcraft.ru/translat/lect/t07-07/

6. Сайт кафедры "Компьютерные технологии" СПбГИТМО(ТУ). http://is.ifmo.ru/

7. Любченко В.С. От машины Тьюринга к машине Мили. «Мир ПК», № 8/02. http://www.osp.ru/pcworld/2002/08/130.htm

8. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов: Пер. с англ. - М.: Мир, 1979 – 654 с.