Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 201

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 195 196 197 198 199 200 < 201 > 202 203 204 205 206 207 .. 316 >> Следующая

1. Выбрать вход в таблицу, соответствующий значению Entry (текущее состояние).
2. Если Условие отсутствует, то перейти к шагу 4.
3. Вычислить совместно все Условия срабатывания переходов (клетки второй колонки для данного входа):
(a) Если среди результатов есть значения True, то выбрать одну из строк, Условие которой истинно, и перейти к агу 4 для вбран-ной строки3;
(b) Если все значения Условий ложны и есть строка failure, то выбрать эту строку и перейти к шагу 4 для нее;
(c) Если все значения Условий ложны и нет строки failure, то завершить вычисления автомата.
4. Выполнить Действие.
5. В качестве значения переменной Entry установить наименование состояния-преемника (из четвертой колонки таблицы). Перейти к шагу 1.
3 В этом пункте может быть заложено недетерминированное поведение автомата. Очень часто при применении метода конечных автоматов возможность недетерминированного поведения игнорируется: оно исключается путем задания последовательных проверок и выбора первого из действий, для которого значение условия есть True. Это очень похоже на то, как определены условные выражения и оператор переключения в языке С/С++.
10.2.
571
Для данного примера указанной семантики вычислений достаточно (обратите внимание на то, что для завершения процесса используется оператор return 0;). В некоторых случаях может оказаться полезным расширение выразительных возмо ностей таблиц за счет добавления факультативных действий, ассоциированных с состоянием, которые выполня тся в самом начале и в самом конце обработки текуего состояния. Этого мо но достичь, например, с помощью специальных служебных слов:
• start — указание действий, которые выполняются до основных действий и проверок условий перехода (мо ет использоваться в качестве первой графы таблицы),
• finish — указание действий, которые выполняются после основных действий и проверок, но до перехода (может использоваться в качестве последней графы таблицы);
о но так е определять локальные для состояний данне (в примере такие данные определены только для начального состояния), но это должно быть согласовано с правилами локализации имен язка программирования и с общим стилем, в котором написана программа. Заметим, что локальные данные всех состояний конечного автомата долн бть помеены в обий контекст, а приписывание их к конкретным состояниям является ограничением видимости, подобным тому, о котором говорилось при рассмотрении модулей в § 12.2 (еще раз прослеживается аналогия между модулями и состояниями!). Это прагматически следует из того положения, что работа конечного автомата не требует привлечения памяти.
рассмотрим многие вид табличных язков, которые подходят для описания различных типов автоматных алгоритмов. А пока займемся решением вопроса о том, как запрограммировать требуеме действия, когда нет возмо ности воспользоваться таблицей непосредственно. Вот что мо но делать с таблицами, представляими конечный автомат:
1. ттранслировать вручну ;
2. тдать препроцессору для превраения в нормальну программу;
3. спользовать интерпретатор. Рассмотрим последовательно эти три возмо ности.
572
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
10.2.4. Ручная трансляция диаграмм переходов
Решения 1 и 2 ставят следующий вопрос: во что транслировать таблицу переходов? Вариантов может быть очень много. Hиже рассматриваются лишь некоторые из них.
Вариант 1: считать StI и St2 функциями, реализующими все действия состояний.
Программа 10.2.1 Длины слов: рекурсия
#include <stdlib.h> #include <stdio.h> #include <time.h>
char symbol; // Переменная для чтения потока int cnt; // еременная для счета длин слов (из анализа
// возможных решений задачи)
void St2 (); // Предописание функции
void StI ()
{
if ('a'<= symbol && symbol <= 'z') {
printf ("%c", symbol); cnt = 1;
symbol = getchar (); St2 ();
}
else if ( symbol != '\n') {
symbol = getchar (); St1 ();
}
}
void St2 ()
{ if ('a'<= symbol && symbol <= 'z') {
printf ("%c",symbol);
10.2.
573
cnt += 1;
symbol = getchar (); St2 ();
}
else if ( symbol != '\n') {
printf (" - %i\n", cnt); symbol = getchar (); St1 ();
}
else printf (" - %i\n", cnt);
}
void main( void ) {
symbol = getchar (); St1 ();
}
Это плохая программа, в частности, по той причине, что рекурсия есть фактическая резервация памяти для взовов функций, а, как у е отмечалось, для конечного автомата динамического расходования памяти не требуется.
Одна из возможных причин появления такой программы в том, что фактическая потоковая обработка, предполагаемая в таблице конечного автомата, задана неявно. опробуем сделать ее явной, соответствуей предполо е-ниям о виде потоковой обработки, сделанным в § 7.2.
Вариант 2: считать StI и St2 значениями некоторого перечислимого типа
State.
Программа 10.2.2 Длины слов: явный цикл обработки потока
#include <stdlib.h> #include <stdio.h> #include <time.h>
char symbol; int cnt;
enum States { St1, St2 } State; void main( void )
574
ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ
{
State = St1;
Предыдущая << 1 .. 195 196 197 198 199 200 < 201 > 202 203 204 205 206 207 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100