Конечный автомат

Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: </p data-lazy-src=

M = (Q, Sigma, delta, q_0, F) » width=»» height=»» />, где:

Q — множество состояний автомата;
q — начальное (стартовое) состояние автомата ();
F — множество заключительных (или допускающих) состояний, таких что ;
Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
δ — заданное отображение множества во множество (Q)» width=»» height=»» /> подмножеств Q: (Q)» width=»» height=»» /> (иногда δ называют функцией переходов автомата).

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

Содержание

Другие способы описания

Диаграмма состояний (или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого — состояния КА, ребра — переходы из одного состояния в другое, а нагрузка — символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Если рассмотреть случай, когда автомат задан следующим образом: </p data-lazy-src=

M = (Q, Sigma, delta, S, F) » width=»» height=»» />, где:

S — множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма — наличие нескольких начальных (стартовых) состояний у автомата </p data-lazy-src=

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет — так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

Специализированные языки программирования

Язык последовательных функциональных схем SFC (Sequential Function Chart) — графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.

Разработка моделей с использованием конечных автоматов

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

Примечания

См. также

Ссылки

Конечные автоматы
Формальные методы

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Конечный автомат» в других словарях:

конечный автомат — КА Вычислительная модель, описывающая автомат с конечным числом состояний. КА широко применяются в программировании, например в лексических анализаторах компиляторов. [http://www.morepc.ru/dict/] конечный автомат Спецификация последовательности… … Справочник технического переводчика

Конечный автомат — математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы. По английски: Finite state machine См … Финансовый словарь

конечный автомат — baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. конечный автомат, m pranc. automate final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas

КОНЕЧНЫЙ АВТОМАТ — автомат, у к рого множество состояний, а также множество входных и выходных сигналов являются конечными. К. а. может быть моделью технич. устройства (ЭВМ, релейное устройство) либо биол. системы (идеализир. нервная система животного). Важными… … Большой энциклопедический политехнический словарь

конечный автомат в модульном исполнении — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite modular automaton … Справочник технического переводчика

конечный автомат доступности — (МСЭ Т Y.1711). [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN availability state machineASM … Справочник технического переводчика

Конечный автомат с памятью — Конечный автомат с памятью математическая модель устройства, поведение которого зависит как от входных условий, так и от предыдущего состояния. Для описания конечного автомата с памятью используются языки операторных схем, регулярных… … Википедия

детерминированный конечный автомат — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite deterministic automaton … Справочник технического переводчика

Автомат Мура — (автомат второго рода) в теории вычислений конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван … Википедия

Конечный — Содержание 1 Конечный 2 Конечная 3 Конечные 4 Фамилия … Википедия

Управление состоянием приложения с помощью конечного автомата

Конечный автомат — это модель системы, у которой есть конечное количество состояний и переходов между этими состояниями.

Звучит заумно, но всё это можно представить в виде лампочки. У неё есть два состояния: включена и выключена. Чтобы перевести лампочку из одного состояния в другое, мы подаём сигнал — нажимаем на кнопку включения. Тогда срабатывает переход, и состояние лампочки меняется.

Набор состояний и переходов между ними можно нарисовать в виде графа, где вершинами будут состояния, а рёбрами — переходы.

Граф состояний и переходов лампочки

Такая абстракция хорошо подходит для построения пользовательских интерфейсов. Например — чтобы управлять состоянием приложения или какой-то его части.

Чё-та сложна. В чём польза?

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

С конечным автоматом не возникает ситуации, когда «мы что-то нажали, и всё исчезло». Потому что причинно-следственные связи прописаны жёстко и не разбросаны по приложению в разных местах.

Понятно, что если система очень сложная, то и количество переходов будет быстро расти. Но тогда стоит задуматься о разделении приложения на несколько автоматов, не зависящих друг от друга.

А ещё список переходов даёт возможность быстро нагенерировать кучу автотестов на изменения состояния.

Обзор тупого приложения для примера

Допустим, у нас есть приложение, которое загружает данные с сервера по нажатию на кнопку. (Работает в последнем Хроме, за другие браузеры не ручаюсь. В Сафари точно не работает.)

В этом приложении есть несколько состояний, которые отображаются на экране.

Отображение ошибки, когда данные не загрузились, или что-то пошло не так

Тогда возможные переходы между состояниями:

с главной по нажатию на кнопку «загрузить» переходим в состояние загрузки;
из состояния загрузки попадаем в отображение данных, если всё ок;
либо в отображение ошибки, если что-то не ок;
из отображения данных или ошибки можем попасть на главную по нажатию на кнопку «очистить»;
из отображения данных можем перейти в состояние загрузки, если нажмём на кнопку «загрузить ещё».

Если представить это дело в виде графа, то получится так:

Граф состояний и переходов приложения из примера

Фейковое API

Для эмуляции загрузки данных будем использовать джейсон-плейсхолдер. Напишем небольшую функцию, которая будет запрашивать данные с сервера:

Состояния, переходы и сам автомат

Теперь опишем состояния для нашего автомата. Состояния будут находиться в объекте states, где каждое состояние будет строковым значением ключей внутри:

Переходы будут функциями, которые возвращают новое состояние. Это новое состояние мы будем использовать, чтобы перевести автомат в него.

Внутри функции может быть несколько условий, по которым мы будем решать, какое состояние требуется вернуть.

Сам автомат опишем в виде класса. В конструктор будем передавать начальное состояние, список возможных переходов, и данные, которые будет содержать автомат.

Метод stateOf будет показывать, в каком состоянии находится автомат сейчас. Приватный метод updateState будет обновлять состояние и данные, если требуется.

Запуск переходов

Чтобы можно было управлять переходами извне, создадим метод performTransition. Он будет принимать название перехода и проверять, возможен ли такой переход. Если возможен, то будет обновлять состояние.

В теории всё просто: вот мы загружаем данные, значит переводим автомат в states.LOADING. Вот они загрузились, значит переводим в states.SUCCESS. Но на деле: как управлять потоком событий? как узнать, что данные действительно загрузились? как определить, что не произошла ошибка по пути?

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

Генераторы и асинхронные генераторы

Генератор — это функция, которая может приостанавливать своё выполнение и продолжать его позже. В основе работы генераторов лежат итераторы, поэтому любой генератор можно проитерировать через for. of.

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

Этот генератор будет последовательно выбрасывать состояние загрузки, а в потом — состояние успеха.

Чтобы получить данные из генератора, мы можем проитерировать его вручную:

Либо через for. of:

Тогда если мы хотим применить подобный переход к автомату, то мы немного изменим метод performTransition:

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

Запрос асинхронный, чтобы получить его результат, мы будем использовать await. Но await можно использовать только внутри асинхронной функции, поэтому генератор перехода станет асинхронным.

Асинхронный генератор почти не отличается от обычного, только вместо значений он выбрасывает промисы. И итерировать его придётся через for await. of:

Так как генератор выбрасывает промисы, то чтобы их развернуть, нам и здесь понадобится await. Поэтому метод performTransition тоже становится асинхронным.

Не только состояние, но ещё и данные

Состояния мы теперь записываем и обрабатываем, но пока что никуда не записываем данные от сервера.

В автомате для этого у нас есть поле data. Будем его обновлять при получении данных из перехода если они есть:

И в performTransition соответственно записываем их в поле data:

Рендер интерфейса

Окей, теперь надо это как-то отрисовать. Можно сюда вкорячить какой-нибудь Реакт, но мы пишем всё с нуля, поэтому и отрисовщик напишем тоже свой.

Функция-рендер будет принимать состояние автомата и данные, которые он содержит. По состоянию будет выбирать, какой шаблон надо отрисовывать. Если использовать Реакт, то не многое изменится: мы просто будем возвращать не строки, а компоненты.

Использовать это будем так:

Да-да, innerHTML лучше не использовать, приложение лучше полностью не перерисовывать. Но камон, этот пост не об этом

Отрисовка изменений

Тот же рендер мы будем использовать и когда автомат будет менять своё состояние.

Чтобы отследить изменения, нам понадобится как-то подписаться на обновления состояния. Создадим метод subscribe и чуть обновим updateState:

Теперь создадим экземпляр автомата, и в subscribe передадим событие update, на которое подписываемся и колбек:

И осталось повесить вызовы переходов на события, например — клики по кнопкам. Вызывать переходы будем методом performTransition:

Кнопка «загрузить ещё»

Я сделал два разных способа загрузки данных: один перетирает старые данные из автомата, второй — добавляет новые к старым. Работают они через два разных перехода: loadMore и reload от состояния states.SUCCESS.

В этой статье это уже не поместится, но ссылку на исходники я оставлю, если интересно почитайте

Но зачем писать с нуля

Конечно, писать с нуля это не надо. Есть куча библиотек, которые реализуют конечные автоматы. Например, вот:

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

Конечные автоматы: преобразователи и распознаватели. Конечные автоматы Простой конечный автомат

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

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

Автомат начинает работу в состоянии q 0 , считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Другие способы описания

Диаграмма состояний (или иногда граф переходов ) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф , вершины которого — состояния КА, ребра — переходы из одного состояния в другое, а — символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированный конечный автомат

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Если рассмотреть случай, когда автомат задан следующим образом: , где:

Тогда появляется третий признак недетерминизма — наличие нескольких начальных (стартовых) состояний у автомата .

Автоматы и регулярные языки

Специализированные языки программирования

Язык последовательных функциональных схем SFC (Sequential Function Chart) — графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.

Разработка моделей с использованием конечных автоматов

Примечания

См. также

Секвенциальная логика (Последовательностная логика)

Ссылки

Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109–188. — URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Применение конечных автоматов для решения задач автоматизации
Пример реализации конечного автомата на языке Python для фреймворка Django

Wikimedia Foundation . 2010 .

Кейнс, Джон Мейнард
Диаграмма состояний (теория автоматов)

Смотреть что такое «Конечный автомат» в других словарях:

конечный автомат — КА Вычислительная модель, описывающая автомат с конечным числом состояний. КА широко применяются в программировании, например в лексических анализаторах компиляторов. конечный автомат Спецификация последовательности… …

конечный автомат доступности — (МСЭ Т Y.1711). Тематики электросвязь, основные понятия EN availability state machineASM … Справочник технического переводчика

Детерминированные конечные автоматы

Дискретно-детерминированные модели (F -схемы)

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F —схему ), характеризующуюся шестью элементами: конечным множеством Х входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z 0 , z 0 Î Z ; функцией переходов j(z , x ); функцией выходов y(z , x ). Автомат, задаваемый F -схемой: F = áZ , X , Y , y, j, z 0 ñ, функционирует в дискретном времени, моментами которого являются такты, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t -му такту при t = 0, 1, 2, …, через z (t ), x (t ), y (t ). При этом по условию z (0) = z 0 , а z (t )ÎZ , x (t )ÎX , y (t )ÎY .

Входной алфавит: «антилопа», «охотник».

Выходной алфавит: «съесть», «спать», «убежать»

Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t = 0, 1, 2, … дискретного времени F -автомат находится в определенном состоянии z (t ) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z (0) = z 0 . В момент t , будучи в состоянии z (t ), автомат способен воспринять на входном канале сигнал x (t )ÎX и выдать на выходном канале сигнал y (t ) = y[z (t ), x (t )], переходя в состояние z(t +1) = j[z (t ), x (t )], z (t )Î Z , y (t )ÎY . Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y . Другими словами, если на вход конечного автомата, установленного в начальное состояние z 0 , подавать в некоторой последовательности буквы входного алфавита x (0), x (1), x (2), …, т.е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y (0), y (1), y (2), …, образуя выходное слово.

Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t -м такте на вход автомата, находящегося в состоянии z (t ), подается некоторый сигнал x (t ), на который он реагирует переходом (t +1)-го такта в новое состояние z (t +1) и выдачей некоторого выходного сигнала. Сказанное выше можно описать следующими уравнениями: для F -автомата первого рода, называемого также автоматом Мили ,

z (t +1) = j[z (t ), x (t )], t = 0, 1, 2, …; (2.15)

y (t ) = y[z (t ), x (t )], t = 0, 1, 2, …; (2.16)

для F -автомата второго рода

z (t +1) = j[z (t ), x (t )], t = 0, 1, 2, …; (2.17)

y (t ) = y[z (t ), x (t – 1)], t = 1, 2, 3,…. (2.18)

Автомат второго рода, для которого

y (t ) = y[z (t )], t = 0, 1, 2, …, (2.19)

т.е. функция выхода не зависит от входной переменной x (t ), называется автоматом Мура .

Таким образом, уравнения (2.15)-(2.19), полностью задающие
F -автомат, являются частным случаем уравнений (2.3) и (2.4), когда
система S – детерминированная и на её единственный вход поступает дискретный сигнал X .

По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием. При этом, согласно (2.16), работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x (t ) определенный выходной сигнал y (t ), т.е. реализует логическую функцию вида

y (t ) = y[ x (t )], t = 0, 1, 2, … .

Эта функция называется булевой, если алфавит X и Y , которым принадлежат значения сигналов x и y , состоят из двух букв.

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

Возможные приложения F -схемы. Чтобы задать конечный F -автомат, необходимо описать все элементы множества F = , т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние z 0 , в котором автомат находится в состоянии t = 0. Существуют несколько способов задания работы F -автоматов, но наиболее часто используются табличный, графический и матричный.

В табличном способе задаются таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. Первый слева столбец соответствует начальному состоянию z 0 . На пересечении i -й строки и k -го столбца таблицы переходов помещается соответствующее значение j(z k , x i ) функции переходов, а в таблице выходов – соответствующее значение y(z k , x i ) функции выходов. Для F -автомата Мура обе таблицы можно совместить.

Описание работы F -автомата Мили таблицами переходов j и выходов y иллюстрируется табл. 2.1, а описание F -автомата Мура – таблицей переходов (табл. 2.2).

Синтаксический разбор строк и конечные автоматы

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

Допустим, в программе, которую вы пишете, нужен модуль, анализирующий текст HTML-страницы. Мы напишем функцию, которая, получив строку, содержащую тэг, извлекала бы из этой строки все атрибуты тэга и их значения. Структуру тэга можно схематично представить следующим образом: <ТЭГ атрибут1 = «значение» атрибут2 = «значение» . > На первый взгляд задача кажется очень простой, однако ситуация осложняется из-за достаточно мягких правил языка HTML. Между именем атрибута, знаком равенства и значением может стоять любое число разделительных символов (пробелов, символов табуляции и даже символов перехода на новую строку), или же разделительные символы могут вообще отсутствовать. Значения атрибутов могут быть либо заключены в кавычки, либо нет, при этом значение, заключенное в двойные кавычки, может содержать символы одинарных кавычек, и наоборот. Кроме того, не всем атрибутам тэгов присваиваются значения.

Для решения указанной проблемы мы напишем функцию ParseTag, анализирующую переданный ей тэг и создающую списки атрибутов тэга и их значений. Функция ParseTag действует по принципу конечного автомата . Конечные автоматы и подобные им структуры широко применяются при обработке строк. Сферы наиболее частого применения конечных автоматов включают поиск подстрок по заданному образцу, обработку регулярных выражений (regular expressions), лексический и синтаксический анализ. Конечные автоматы широко применяются в трансляторах и интерпретаторах (не говоря уже о таких задачах, как проектирование логических устройств).

Строгое определение конечных автоматов можно найти в любом учебнике по теории алгоритмов, мы же здесь ограничимся интуитивным определением. В каждый данный момент времени конечный автомат может находиться в одном из возможных состояний (число состояний, в которых может находиться конечный автомат – конечно). Автомат последовательно считывает символы входного текста (строки). Каждый считанный символ либо переводит автомат в новое состояние, либо оставляет его в прежнем состоянии. Формально автомат можно описать при помощи функции переходов . Аргументами этой функции являются предыдущее состояние автомата и очередной считанный символ, а значением – новое состояние автомата.

Множество состояний для нашего автомата включает:

ReadTag – читает имя тэга;
WaitAttr – ожидает имя атрибута;
WaitAttrOrEq – ожидает имя атрибута или символ ‘=’;
ReadAttr – читает имя атрибута;
WaitValue – ожидает значение атрибута;
ReadValue – читает значение атрибута без кавычек;
ReadValueSQ – читает значение атрибута в одинарных кавычках;
ReadValueDQ – читает значение атрибута в двойных кавычках.

Следуя терминологии конечных автоматов, мы можем назвать состояния WaitAttr, WaitAttrOrEq, ReadAttr и ReadValue допускающими. Это означает, что если после обработки переданной строки автомат находится в каком-либо другом состоянии, значит, тэг содержит ошибку (автомат не проверяет, завершается ли строка символом ‘>’, это – задача блока, вызывающего функцию ParseTag).

Процесс программной реализации автомата можно упростить, построив для него диаграмму переходов . Далее приводится диаграмма переходов для нашего автомата. Цифры на диаграмме соответствуют номерам состояний, перечисленных выше.

Пояснения к диаграмме:

b — любой символ кроме разделителя

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

Фактически представленная функция выполняет две операции: выделяет в переданной строке синтаксические элементы (tokens) и определяет, что представляет собой данный элемент (имя тэга, имя атрибута, значение атрибута). Решение о том, чем является следующий элемент, принимается заранее, на основании данных о предыдущем элементе и простых правил: за именем тэга следует имя атрибута; за именем атрибута следует либо имя атрибута, либо символ ‘=’; за символом ‘=’ следует значение атрибута.

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

Входное математическое выражение может содержать целочисленные константы, символы арифметических операций и скобки. Между символами операций, скобками и числами допустимо любое количество пробелов. Функция CheckMath возвращает значение 0, если переданное ей выражение не содержит ошибок. Если выражение содержит ошибку, функция возвращает положительное число, соответствующее позиции символа, в которой была обнаружена ошибка. Если число открытых скобок не равно числу закрытых, функция возвращает либо -1, либо -2, в зависимости от того, каких скобок не хватает.

В данной функции задействованы следующие состояния:

Start – начальное состояние;
InDigit – прочитана цифра;
AfterDigit – прочитан разделитель после цифры;
InOp – прочитан символ арифметической операции;
InLPrnt – прочитана открывающая скобка;
InRPrnt – прочитана закрывающая скобка.

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

голоса

Рейтинг статьи

Читайте так же:

Атомэнергосбыт передать показания счетчика без регистрации