авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 |

«Пышкин Е.В. СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ: ОСНОВАНИЕ И РАЗВИТИЕ МЕТОДОВ С примерами на языке C++ Учебное пособие ...»

-- [ Страница 4 ] --

// Здесь должен быть выбран разделяющий элемент x // среди элементов a[ left ]... a[ right ] //...

ixLeft = left;

ixRight = right;

while( ixLeft = ixRight ) { while( a[ ixLeft ] x ) ixLeft++;

while( x a[ ixRight ] ) ixRight--;

if( ixLeft = ixRight ) { copy = a[ ixLeft ];

a[ ixLeft ] = a[ ixRight ];

a[ ixRight ] = copy;

ixLeft++;

ixRight--;

} } // Здесь: получены две подпоследовательности // Первая: a[ left ]... a[ ixRight ] // Вторая a[ ixLeft ]... a[ right ] // Теперь нужно разделить получившиеся подпоследователности, // причем для уменьшения максимальной глубины рекурсии // лучше сначала разделять более короткую if( ixRight – left right – ixLeft ) { Split( a, n, left, ixRight );

Split( a, n, ixLeft, right );

} else { Split( a, n, ixLeft, right );

Split( a, n, left, ixRight );

} } // Функция сортировки Хоара (рекурсивный вариант) void QuickSort( int *a, int n ) { Split( a, n, 0, n-1 );

} Понятно, что наибольшая скорость сортировки может быть достигнута в том случае, когда при каждом очередном разделении подпоследовательность делится на 2 равные части (в этом случае исходная последовательность сортируется за log 2 n разбиений). Наихудший случай возникает тогда, когда в качестве разделяющего элемента выбирается наибольший или наименьший элемент разделяемой подпоследовательности.

В этом случае результатом разделения являются две подпоследовательности, одна из которых содержит лишь 1 элемент, а вторая – все остальные элементы. Очевидно, что при таких разбиениях эффективность сортировки будет сопоставима с эффективностью сортировки простыми обменами.

К сожалению, выбор элемента x, приводящего к желаемому разбиению (такой желаемый элемент называется медианой подпоследовательности), в свою очередь, является трудоемкой задачей. Поэтому разделяющий элемент выбирают каким-либо простым регулярным образом, рассчитывая на то, что в среднем мы не будем получать неравномерные разделения слишком часто.

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

#include stdlib.h #include time.h void Split( int *a, int n, int left, int right ) { //...

// Выбор разделяющего элемента x = a[ left + rand() % (right-left) ];

//...

} void QuickSort( int *a, int n ) { // "Рассеивание" генератора случайных чисел // на основе некоторого псевдослучайного фактора // (чаще всего используют текущее время) srand( (unsigned) time( NULL ) );

// Вызов функции разделения сегментов Split( a, n, 0, n-1 );

} Суммарная эффективность быстрой сортировки оценивается величиной O(n log 2 n) [McConnell J., 2001].

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

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

Для этого следует определить две структуры:

структуру представляющую собой QuickSortStackItem, описание отдельного запроса на разделение (пару индексов left и right);

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

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

#include assert.h // Описание типа "Очередной запрос на разделение" struct QuickSortStackItem { int left;

// Индекс левой границы сегмента int right;

// Индекс правой границы сегмента };

// Описание типа "Стек запросов" struct QuickSortStack { QuickSortStackItem *body;

// Адрес начала области в памяти, // где хранится массив с элементами // стека int size;

// Размер массива body;

int top;

// Вершина стека };

// Функция занесения очередного запроса на разделение в стек inline void Push( QuickSortStack& stack, int left, int right ) { if( right – left = 1 ) { stack.top++;

assert( stack.top stack.size );

stack.body[ stack.top ].left = left;

stack.body[ stack.top ].right = right;

} } // Функция извлечени запроса на разделение из стек inline void Pop( QuickSortStack& stack, int& left, int& right ) { assert( stack.top = 0 );

left = stack.body[ stack.top ].left;

right = stack.body[ stack.top ].right;

stack.top--;

} Тогда схематичная реализация функции сортировки в нерекурсивной форме в первом приближении выглядит следующим образом:

#include stdlib.h #include time.h void QuickSort2( int *a, int n ) { int left;

// Левая граница разделяемого сегмента int right;

// Правая граница разделяемого сегмента int ixLeft;

// Индекс при просмотре слева направо int ixRight;

// Индекс при просмотре справа налево int copy;

// Вспомогательная переменная для перестановки int x;

// Разделяющий элемент QuickSortStack stack;

// Стек запросов stack.size = ?;

// О размере стека запросов см. далее // в этом разделе // Инициализация стека запросов stack.body = new QuickSortStackItem[ stack.size ];

assert( stack.body != 0 );

stack.top = -1;

// Инициализация генератора случайных чисел srand( (unsigned) time( NULL ) );

// Первым разделяемым сегментом является массив в целом Push( stack, 0, n-1 );

// Разделяем, пока в стеке есть запросы while( stack.top = 0 ) { Pop( stack, left, right );

// Выбор разделяющего элемента x = a[ left + rand() % (right-left) ];

// Разделение очередного сегмента (см. листинг 3.25) //...

// Получившиеся подпоследователности заносим в стек // причем для уменьшения требуемого размера стека // сначала лучше помещать более длинные // (то есть короткие будут извлечены раньше) if( ixRight – left right – ixLeft ) { Push( stack, ixLeft, right );

Push( stack, left, ixRight );

} else { Push( stack, left, ixRight );

Push( stack, ixLeft, right );

} } } Критическим моментом в связи с данным алгоритмом является выделение памяти для хранения стека запросов. Следует по возможности уменьшить требования к этой памяти. Оказывается, данный алгоритм можно существенно улучшить, если помещать в стек запросов только длинные сегменты, а с короткими «разбираться на месте». Цикл обработки запросов на разделение в этом случае выглядит следующим образом:

Листинг 3.27. Обработка запросов на разделение в нерекурсивной варианте // Разделяем, пока в стеке есть запросы while( stack.top = 0 ) { Pop( stack, left, right );

// Разделяем короткие пока есть while( left right ) { // Выбор разделяющего элемента x = a[ left + rand() % (right-left) ];

// Разделение очередного сегмента ixLeft = left;

ixRight = right;

while( ixLeft = ixRight ) { while( a[ ixLeft ] x ) ixLeft++;

while( x a[ ixRight ] ) ixRight--;

if( ixLeft = ixRight ) { copy = a[ ixLeft ];

a[ ixLeft ] = a[ ixRight ];

a[ ixRight ] = copy;

ixLeft++;

ixRight--;

} } // В стек заносим только длинную подпоследовательность, // с короткой разбираемся сразу, изменяя значение // индекса left или right if( ixRight – left right – ixLeft ) { Push( stack, ixLeft, right );

right = ixRight;

} else { Push( stack, left, ixRight );

left = ixLeft;

} } // while( left right ) } // while( stack.top = 0 ) В этом случае упорядоченность исходного массива достигается не более чем за log 2 n разделений. С учетом первого запроса стек запросов должен содержать log 2 n 1 элементов. Следовательно, в текст программы должны быть внесены следующие изменения:

#include math.h //...

stack.size = log10( (double) n ) / log10( 2.0 ) + 1;

Окончательный вид нерекурсивной функции сортировки Хоара с дополнениями из листинга 3.27, содержится на прилагаемом к книге компакт-диске. Произвести сравнительный анализ затрат стека приложения при реализации рекурсивного алгоритма с затратами на вспомогательный стек запросов в нерекурсивном варианте читателю предлагается самостоятельно.

Глава 4. Управление данными в процедурной программе Организация управления данными является не менее важным аспектом качественного структурного и процедурного программирования, чем организация правильной и эффективной последовательности выполняемых действий. Во многих случаях эффективность алгоритмов зависит от выбранных структур данных. В данной главе основной акцент делается на построении моделей данных в процедурной программе.

4.1. Построение модели предметной области В разд. 2.2—2.6 вкратце представлен основной инструментарий разработчика по конструированию составных типов. Правильное совместное использование таких средств как структуры, массивы, перечисления, объединения и др. позволяет построить модель данных, позволяющую наглядно представить в компьютерной программе объекты предметной области.

Постановка демонстрационной задачи Для иллюстрации положений данной главы рассмотрим пример нетрудной задачи обработки текстовой информации.

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

Например, для константы 97 123 402 217 должен быть сформирован следующий текст: «девяносто семь миллиардов сто двадцать три миллиона четыреста две тысячи двести семнадцать».

Дополнительно сформулированы следующие требования:

Десятичные константы задаются в исходном тексте по правилам C++ (то есть незначащие ведущие нули не допускаются).

Некорректные лексемы из входного текста игнорируются.

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

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

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

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

О дальнейшем развитии постановки задачи см. в приложении 1.

Анализ предметной области Очевидно, что решение задачи затрагивает работу, по крайней мере, в двух предметных областях (рис. 4.1): лексический анализ и грамматика русского языка.

Формирование Предварительная структура текстуальных программного проекта наименований Модуль формирования Грамматика фрагментов описаний русского языка Модуль Лексический лексического анализ Основной анализа модуль Модуль обработки параметров Организация командной строки приложения Модуль Инженерия предметной обработки ошибок области Рис. 4.1. Инженерия предметной области В соответствии с требуемыми предметными областями и требованиями постановки задачи решение включает в себя несколько самостоятельных модулей:

Модуль обработки параметров командной строки.

Модуль лексического анализа.

Модуль (или модули) обработки считанных десятичных констант.

Модуль обработки ошибок, диагностируемых программой.

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

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

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

Максимальное количество триад однозначно вытекает из предельной длины обрабатываемых констант (листинг 4.1).

Листинг 4.1. Типы в связи с представлением десятичной константы // Максимальная длина обрабатываемых констант // (не включая сивмол '\0') #define DCONSTLEN // Масимальное число триад десятичных цифр #define THREELIM (DCONSTLEN+2)/ typedef struct { // Решение о введении структурного типа принято, // детали будут рассмотрены позднее } TThree;

// Набор сведений об обрабатываемой десятичной // целочисленной константе typedef struct { char value[ DCONSTLEN + 1 ];

// Значение int ixHighDigit;

// Индекс старшего разряда int ixHighThree;

// Индекс старшей триады TThree three[ THREELIM ];

// Триады разрядов } TypeDConstSet;

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

Массив цифр удобен в ходе инициализации и копирования, однако при работе с отдельными разрядами триады удобно иметь отдельные переменные для сотен, десятков и единиц. Соответствующее обобщение наиболее элегантно достигается использованием объединения (листинг 4.2):

Листинг 4.2. Определение типа для представления триады разрядов // Максимальная длина текстуального представления одной триады #define TEXLIM // Тип: триада разрядов typedef struct { // Для удобства обработки значение триады // представлено в двух формах union { int value[ 3 ];

// В форме массива разрядов struct // В форме отдельных разрядов { int xtdigits;

// единицы (0..19) int tens;

// десятки (0, 2..9) int hundreds;

// сотни (0..9) };

};

char lex[ TEXLIM ];

// Текстуальное наиминование триады } TThree;

Обратите внимание на несколько необычной способ представления цифр. Применительно к задачам обработки автор счел необходимым ввести понятие «расширенная цифра» (eXTended DIGIT). Это связано с тем, что в русском языке для обозначения чисел в интервале 0..19 используются уникальные наименования, в то время как, начиная с числа 20, процесс формирования текстуального наименования подчиняется общему правилу:

число десятков плюс число единиц. С введением понятия «расширенная цифра» данное правило обобщается и на первую «двадцатку»: нуль десятков плюс расширенная цифра.

Очевидно, что в тех случаях, когда используется расширенная цифра (в русском языке это происходит в том случае, когда число десятков равняется 1), число десятков в представлении триады должно быть уменьшено на 1: например, не 1 десяток и 5 единиц, а 0 десятков и 15 единиц (xtdigits).

Построение модели фрагмента грамматики русского языка Задача генерации текстуального представления числа в целом сводится к последовательности представлений триад. К каждой триаде подставляется соответствующее числительное, выступающее в роли существительного (то есть изменяющееся в роде и числе по правилам существительных), например 5 миллионОВ, но 2 миллионА.

Поэтому требуются следующие описания грамматических структур:

Описание грамматической категории рода, необходимой для определения правильной формы окончаний числительных, изменяемых по правилам существительных, а также для Данный прием позволяет обобщить решение и для многих других языков, где наблюдается схожая картина. Более того, в некоторых языках расширенные цифры используются не только в интервале 0..19. Например, во французском языке число 70 называют не septante (хотя такое наименование и присутствует в некоторых диалектах), а soixante-dix (дословно: 60 и 10), 71 – не septente-et-un, а soixante-onze (60 и 11), и т. д. Идентичная картина и для чисел в интервале 90..99, например, quatrevingt-quinze (80 и 15) для числа 95.

определения формы предшествующих им числительных, например, одИН миллион, но одНА тысяча.

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

Описание структуры для представления понятия «расширенная цифра».

Описание набора расширенных цифр.

Описание наименований десятков.

Описание наименований сотен.

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

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

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

Определение грамматических категорий рода и числа наиболее естественно представить в форме типов-перечислений (листинг 4.3).

Листинг 4.3. Определение грамматических категорий рода и числа // Определение грамматической категории рода:

// используется при извлечении правильной // формы окончаний и при определении // свойств числительных, выступающих // в роли существительных (тысяча, миллион и т.д.) enum Gender { Male = 0, // мужской род Female = 1 // женский род };

// Определение грамматической категории числа:

// используется при извлечении правильной // формы окончаний enum Number { Single = 0, // единственное (один) Double = 1, // двойственное (два, три, четыре) Multiple = 2 // множественное (пять, шесть,...) };

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

Однако двойственное число не является изобретением автора книги, а некогда существовало в старославянском языке, оставив в современном языке «нелогичные» окончания родительного падежа после слов «два», «три» и «четыре» [Костомаров, 1994]. Использование архаичного двойственного числа позволяет унифицировать выбор окончаний существительных в зависимости от значения числительного (точнее – в зависимости от значения «расширенной цифры» в конце числительного).

После этого пояснения структура данных, описывающих расширенную цифру, не нуждается в дополнительных комментариях (см. листинги 4.4—4.5).

Листинг 4.4. Определение типа «Расширенная цифра»

// Определение типа "Расширенная цифра" struct ExtendedDigit { const char *name;

// наименование Number number;

// число (грамматическая категория), // в котором употребляется // следующее за расширенной цифрой // существительное или числительное, // например:

// один миллион (единственное) // два миллионА (двойственное) // три миллионА (двойственное) // пять миллионОВ (множественное) };

Листинг 4.5. Инициализация массива «расширенных цифр»

static ExtendedDigit XtDigit[] = { { "", Multiple }, // Нуль - особый случай, // обрабатывается отдельно { "один", Single }, { "два", Double }, { "три", Double }, { "четыре", Double }, { "пять", Multiple }, { "шесть", Multiple }, { "семь", Мultiple }, { "восемь", Multiple }, { "девять", Multiple }, { "десять", Multiple }, { "одиннадцать", Multiple }, { "двенадцать", Multiple }, { "тринадцать", Multiple }, { "четырнадцать", Multiple }, { "пятнадцать", Multiple }, { "шестнадцать", Multiple }, { "семнадцать", Multiple }, { "восемнадцать", Multiple }, { "девятнадцать", Multiple } };

Листинг 4.6 содержит определение массивов наименований десятков и сотен.

Листинг 4.6. Инициализация массивов десятков и сотен // Наименования десятков static const char *Ten[] = { "", "десять", "двадцать", "тридцать", "сорок", "пятьдесят", "шестьдесят", "семьдесят", "восемьдесят", "девяносто" };

// Наименования сотен const char *Hundred[] = { "", "сто", "двести", "триста", "четыреста", "пятьсот", "шестьсот", "семьсот", "восемьсот", "девятьсот" };

Наконец, следует определить основы числительных, изменяемых по правилам склонения существительных, и формы их окончаний. Задачу решает листинг 4.7.

Листинг 4.7. Основания и окончания числительных, выступающих в роли существительных // Тип "основа числительного в роли существительного" struct Stem { const char *name;

// наименование Gender gender;

// род };

// Числительные в роли существительных // используемые при текстуальной записи // больших чисел static Stem ThreeStem[] = { { "", Male }, { "тысяч", Female }, { "миллион", Male }, { "миллиард", Male }, { "квадрильон", Male }, { "квинтильон", Male }, { "септильон", Male }, { "секстильон", Male }, { "октильон", Male }, };

// Формы окончаний числительных // Пример: миллион миллионА миллионОВ // тысячА тысячИ тысяч static const char *Termination[ 2 ][ 3 ] = { /*Single*/ /*Double*/ /*Multiple*/ /* Male */ { "", "а", "ов" }, /* Female */ { "а", "и", "" } };

Совокупность определений грамматики из листингов 4.3—4.7, удобно оформить в виде заголовочного файла. В проекте, содержащемся на компакт-диске, данный файл имеет имя Grammar.rus.

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

4.2. Иерархия функций обработки подготовленных данных При обработке считанных десятичных констант возникают две подзадачи:

Представление набора сведений, описывающих десятичную константу, в соответствии со структурой типа TypeDConstSet.

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

Рассмотрим эти подзадачи подробнее.

Подготовка набора сведений, описывающих десятичную константу Задачу подготовки структуры типа TypeDConstSet на основе считанного из файла значения решает функция CreateDConstSet (листинг 4.8).

Листинг 4.8. Определение функции CreateDConstSet // CREATE DecimalCONSTant info SET // Сформировать набор сведений об обрабатываемой // десятичной константе // Функция возвращает 1, если структура DConstSet успешно // сформирована // Функция возвращает 0, если лексема слишком длинная int CreateDConstSet( TypeDConstSet& DConstSet, char* LexValue ) { if( strlen( LexValue ) DCONSTLEN ) return 0;

strcpy( DConstSet.value, LexValue );

strrev( DConstSet.value );

// теперь символ с индексом // соответствует младшему разряду DConstSet.ixHighDigit = strlen( DConstSet.value ) - 1;

DConstSet.ixHighThree = DConstSet.ixHighDigit / 3;

// Подготовка старшей триады int ixThree = DConstSet.ixHighThree;

PrepareHighThree( DConstSet );

// Подготовка остальных триад while( ixThree 0 ) { ixThree--;

PrepareNextThree( ixThree, DConstSet );

} return 1;

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

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

Листинг 4.9. Определение функций подготовки триад разрядов // PREPARE HIGH THREE // Инициализация старшей триады void PrepareHighThree( TypeDConstSet& DConstSet ) { int ixDigit;

// Индекс цифры в составе константы int ixDigThree;

// Индекс разряда в составе триады for( ixDigit = DConstSet.ixHighThree*3, ixDigThree = 0;

ixDigit = DConstSet.ixHighDigit;

ixDigit++, ixDigThree++ ) { DConstSet.three[DConstSet.ixHighThree].value[ixDigThree] = CharToDigit( DConstSet.value[ ixDigit ] );

} for( ;

ixDigThree 3;

ixDigThree++ ) { DConstSet.three[DConstSet.ixHighThree].value[ixDigThree] = 0;

} // Корректировка десятков и единиц с учетом раширенных цифр TensAsXtDigits( DConstSet.three[ DConstSet.ixHighThree ] );

} // PREPARE NEXT THREE // Инициализация очередной триады void PrepareNextThree( int ixThree, TypeDConstSet& DConstSet ) { int ixDigit;

// Индекс цифры в составе константы int ixDigThree;

// Индекс разряда в составе триады for( ixDigThree = 0, ixDigit = ixThree*3;

ixDigThree 3;

ixDigThree++, ixDigit++ ) { DConstSet.three[ ixThree ].value[ ixDigThree ] = CharToDigit( DConstSet.value[ ixDigit ] );

} // Корректировка десятков и единиц с учетом расширенных цифр TensAsXtDigits( DConstSet.three[ ixThree ] );

} Служебная функциия CharToDigit осуществляет преобразование символа-десятичной цифры в целый код. Ее реализация не представляет труда. Функция TenAsXtDigits учитывает особенность представления чисел с использованием абстракции расширенной цифры (листинг 4.10).

Данную функцию удобно писать, используя альтернативную форму представления триады, задаваемую объединением в составе структурного типа TThree (см. листинг 4.2).

Листинг 4.10. Функция модификации десятков и единиц // Decrease TENS with usage of eXTended DIGITS // Уменьшить десятки в случае использования "расширенных цифр" // В русском языке вместо 10 + дес.цифра = xtdigit void TensAsXtDigits( TThree& three ) { if( three.tens == 1 ) { three.tens--;

three.xtdigits += 10;

} } Таким образом, представление DConstSet сформировано.

Формирование текстуальных наименований Задачу обработки объекта данных типа TypeDConstSet решает функция TranslateDConst, последовательно вызывающая функцию TranslateThree для обработки каждой триады и выводящую сформированный «кусочек» общего представления в файл посредством использования служебной функции OutString. Листинг 4.11 иллюстрирует проектирование основных функций обработки целочисленной константы.

Листинг 4.11. Формирование текстуального представления десятичной константы // "TRANSLATE" Decimal CONSTant // "Перевод" десятичной константы в текстуальное представление void TranslateDConst( TypeDConstSet& DConstSet ) { // Особый случай - константа "нуль" if( DConstSet.ixHighDigit == 0 && DConstSet.value[ 0 ] == '0' ) { OutString( " " );

OutString( "нуль" );

return;

} // Обработка триад разрядов for( int ixThree = DConstSet.ixHighThree;

ixThree = 0;

ixThree-- ) { // Если триада содержит одни нули, // никакого текста генерировать не нужно if( ThreeIsNull( DConstSet.three[ ixThree ] ) ) { strcpy(DConstSet.three[ ixThree ].lex, "" );

continue;

} TranslateThree( ixThree, DConstSet.three[ ixThree ] );

OutString( " " );

OutString( DConstSet.three[ ixThree ].lex );

} } Реализация вспомогательной функции ThreeIsNull элементарна (листинг 4.12).

Листинг 4.12. Определение функции ThreeIsNull // check: THREE IS NULL?

// Проверка: триада содержит одни нули?

int ThreeIsNull( TThree& three ) { return three.hundreds== && three.tens== && three.xtdigits == 0;

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

Листинг 4.13. Формирование текстуальных представлений триад // "TRANSLATE" a THREE // "Перевод" произвольной триады в текстуальное представление void TranslateThree( int ixThree, TThree& three ) { strcpy( three.lex, "" );

AddToThreeLex( three, Hundred[ three.hundreds ] );

AddToThreeLex( three, Ten[ three.tens ] );

Gender gen = ThreeStem[ ixThree ].gender;

Number num = XtDigit[ three.xtdigits ].number;

if( gen == Male ) // основа мужского рода { AddToThreeLex( three, XtDigit[ three.xtdigits ].name );

} else { // Здесь: основа женского рода if( three.xtdigits == 1 ) AddToThreeLex( three, "одна" );

else if ( three.xtdigits == 2 ) AddToThreeLex( three, "две" );

else AddToThreeLex( three, XtDigit[ three.xtdigits ].name );

} // Завершение: основа + окончание if( ixThree != 0 ) { // Основа с правильным окончанием char TerminatedStem[ STEMLIM ];

strcpy( TerminatedStem, ThreeStem[ ixThree ].name );

strcat( TerminatedStem, Termination[ gen ][ num ] );

AddToThreeLex( three, TerminatedStem );

} CutLastSpace( three );

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

Листинг 4.14. Вспомогательные функции обработки триад // ADD new part TO lexical STRING // Добавление очередного фрагмента к текстуальному представлению void AddToThreeLex( TThree& three, const char *newpart ) { strcat( three.lex, newpart );

if( strlen( newpart ) != 0 ) { strcat( three.lex, " " );

} } // CUT LAST SPACE in the three lexical representation // Удаление последнего пробела в текстуальном представлении void CutLastSpace( TThree& three ) { int lastSpace = strlen( three.lex ) - 1;

three.lex[ lastSpace ] = '\0';

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

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

Модульная структура решения, содержащегося на компакт-диске, представлена на рис. 4.2.

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

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

DecLex ParmOS main GetParameter ProcessParameters ExpressAll CheckExeName Activate_On_Error CheckSrcFileName PassPathDescription Errors CheckFileName info CheckDstFileName error ExistDstFileName warning ComposeDstFileName Функции модуля могут вызываться ScanLex из разных сегментов проекта ScanLex LexD10Zero LexFirst LexD10Const Grammar.rus LexNext Определение LexFinish правил грамматики PassUntilSpace DConst Three Synterm CreateDConstSet TensAsXtDigits PrepareHighThree ThreeIsNull Модуль PrepareNextThree TranslateThree содержит CharToDigit определение AddToThreeLex таблицы синтермов CutLastSpace ExpressDConst TranslateDConst OutString Рис. 4.2. Модульная структура приложения Как явствует из рисунка, многие элементы реализации остались за рамками рассмотрения в данной главе. Читателю предлагается изучить их самостоятельно.

Формирование текстуальных наименований числовых констант DecLex DConst Three Основной процесс ExpressAll CreateDConstSet PrepareHighThree Подготовка DConstSet PrepareNextThree TensAsXtDigits ExpressDConst Формирование DConstSet TranslateDConst Формирование текстов триад ThreeIsNull TranslateThree AddToThreeLex Рис. 4.3. Кросс-функциональная схема 4.4. Полиморфизм в процедурном программировании Употребление понятия «полиморфизм» привычно главным образом в контексте ООП, где под этим понимается, главным образом, динамическое связывание, позволяющее отложить определение типа некоторых объектов на период выполнения. Однако различные формы полиморфизма (обычно называемого статическим) присутствуют и в процедурном программировании.

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

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

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

Дж. Коплиен указывает, что такие методы проектирования для C++ как перегрузка функций, шаблонные функции, передача функций в качестве параметров других функций представляют собой разновидности реализации концепций общности и изменчивости, не входящих в объектную парадигму [Coplien, 1999], а существующих и активно используемых в рамках чисто процедурного кода. Рассмотрим основные механизмы, обеспечивающие реализацию полиморфизма в процедурном программировании, более подробно.

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

В языках программирования для выражения подобных процессов используется механизм перегрузки функций:

struct Circle { //...

};

struct Rectangle { //...

};

void draw( const Circle& ) { // Действия, выполняемые при изображении окружности //...

} void draw( const Rectangle& ) { // Действия, выполняемые при изображении прямоугольника //...

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

Circle shape1;

Rectangle shape2;

draw( shape1 );

// Будет вызвана void draw( const Circle& ) draw( shape2 );

// Будет вызвана void draw( const Rectangle& ) Перегрузка функций является подходящим решением, если известно ограниченное число наборов данных, для которых следует определить сходные по назначению функции. Разумеется, компилятор не в силах установить, насколько в действительности родственны данные функции – ответственность за это лежит на программисте.

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

Листинг 4.15. Перегруженные функции #include stdio.h #include stdlib.h #include assert.h // Комплексное число struct Complex { double re;

// действительная часть double im;

// мнимая часть };

//Сложение комплесных чисел Complex& Add( Complex& arg1, const Complex& arg2 ) { arg1.re += arg2.re;

arg1.im += arg2.im;

return arg1;

} // Вывод комплексного числа void PrintLn( const Complex& arg ) { printf( "%lf+%lfi\n", arg.re, arg.im );

} // Рациональная дробь struct Rational { int numerator;

// числитель int denominator;

// знаменатель };

// Сокращение рациональной дроби void Shorten( Rational& arg ) { // Найти наибольший общий делитель int x = arg.numerator;

int y = arg.denominator;

while( x != y ) { if( x y ) x = x – y;

else y = y – x;

} // Поделить на него числитель и знаменатель arg.numerator /= x;

arg.denominator /= x;

} // Сложение рациональных дробей (упрощенная реализация) Rational& Add( Rational& arg1, const Rational& arg2 ) { int sumNumerator;

int sumDenominator;

sumNumerator = arg1.numerator * arg2.denominator + arg2.numerator * arg1.denominator;

sumDenominator = arg1.denominator * arg2.denominator;

arg1.numerator = sumNumerator;

arg1.denominator = sumDenominator;

Shorten( arg1 );

return arg1;

} // Вывод рациональной дроби void PrintLn( const Rational& arg ) { printf( "%d/%d\n", arg.numerator, arg.denominator );

} // Бином struct Binom { double coeff[ 3 ];

// массив коэффициентов };

// Сложение биномов Binom& Add( Binom& arg1, const Binom& arg2 ) { for( int ix=0;

ix 3;

ix++ ) { arg1.coeff[ ix ] += arg2.coeff[ ix ];

} return arg1;

} // Вывод бинома void PrintLn( const Binom& arg ) { printf( "( " );

for( int ix = 2;

ix 0;

ix-- ) { printf( "%lf, ", arg.coeff[ ix ] );

} printf( "%lf )\n", arg.coeff[ 0 ] );

} Выбор нужной версии перегруженной функции осуществляется компилятором на основе анализа типов аргументов:

void main() { // Обработка комплексных данных Complex c1 = { 5, -2 };

Complex c2 = { 4, 3 };

c1 = Add( c1, c2 );

PrintLn( c1 );

// Обработка дробей Rational r1 = { 1, 2 };

Rational r2 = { 2, 8 };

r1 = Add( r1, r2 );

PrintLn( r1 );

// Обработка биномов Binom b1 = { 5, 0, -2 };

Binom b2 = { -3, 2, 1 };

b1 = Add( b1, b2 );

PrintLn( b1 );

} К обсуждению перегруженных функций, представляемых листингом 4.15, мы вернемся в подразделе «Процедурно-параметрический полиморфизм»

Перегрузка функций поддерживается многими современными языками. Наряду с перегрузкой функций отдельные языки (в том числе – С++) поддерживают перегрузку операций, позволяя придать новый смысл знаку операции применительно к определяемым пользователем типам, например:

Binom operator+( const Binom& arg1, const Binom& arg2 ) { // Реализация сложения двух биномов } Binom& operator=( Binom& arg1, const Binom& arg2 ) { // Реализация присваивания двух биномов } Перегруженные операции позволяют обеспечить наглядные операции над данными типов, не встроенных в язык, по аналогии с встроенными типами:

Binom a, b, c;

//...

c = a + b;

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

Так, при решении задач сортировки последовательность выполняемых в ходе сортировки последовательность действий одна и та же независимо от типов элементов сортируемого массива. К сожалению, функция QiuckSort не подходит для сортировки массива вещественных чисел. Можно воспользоваться методикой, рассмотренной в подразделе «Функции обратного вызова» (см. разд. 3.6), определив функцию сортировки, работающую с побайтовым представлением данных и принимающую указатель на функцию сравнения элементов. Решение, получающееся таким образом, не слишком наглядно. Кроме того, трудно обеспечить полноценный контроль типов.

Язык C++ предоставляет программисту иной механизм построения обобщенного кода – шаблоны функций. Рекурсивный вариант сортировки Хоара в шаблонном виде представлен в листинге 4.16.

Листинг 4.16. Шаблонная версия рекурсивной сортировки Хоара // Шаблонная функция разделения сегмента, ограниченного индексами // left и right template class T void Split( T *a, int n, int left, int right ) { int ixLeft;

// Индекс при просмотре слева направо int ixRight;

// Индекс при просмотре справа налево T copy;

// Вспомогательная переменная для перестановки T x;

// Разделяющий элемент if( right = left ) return;

x = a[ left + rand() % (right-left) ];

ixLeft = left;

ixRight = right;

while( ixLeft = ixRight ) { while( a[ ixLeft ] x ) ixLeft++;

while( x a[ ixRight ] ) ixRight--;

if( ixLeft = ixRight ) { copy = a[ ixLeft ];

a[ ixLeft ] = a[ ixRight ];

a[ ixRight ] = copy;

ixLeft++;

ixRight--;

} } // Здесь: получены две подпоследовательности // Первая: a[ left ]... a[ ixRight ] // Вторая a[ ixLeft ]... a[ right ] // Теперь нужно разделить получившиеся подпоследователности, // причем для уменьшения максимальной глубины рекурсии // лучше сначала разделять более короткую if( ixRight – left right – ixLeft ) { Split( a, n, left, ixRight );

Split( a, n, ixLeft, right );

} else { Split( a, n, ixLeft, right );

Split( a, n, left, ixRight );

} } // Шаблонная функция быстрой сортировки (рекурсивный вариант) template class T void QuickSort( T *a, int n ) { srand( (unsigned) time( NULL ) );

Split( a, n, 0, n-1 );

} Пример использовании шаблонной версии функции сортировки см. на компакт-диске.

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

операции присваивания;

операции отношения.

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

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

Более подробную информацию о методах обобщенного программирования см. в учебном пособии [Пышкин, 2005].

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

В заключение отметим, что перечисленные методы (перегруженные функции, шаблоны функций, функции-параметры) могут во многих случаях выступать в качестве альтернативных вариантов решения одной и той же задачи (см. гл. 2 книги [Coplien, 1999]).

Введение в процедурно-параметрический полиморфизм Вернемся к примеру из листинга 4.15. Что, если нам нужно разработать некий внешний алгоритм, способный обрабатывать как комплексные числа, так и рациональные дроби и биномы некоторым унифицированным образом? Рассмотрим простейший пример, представленный ниже в псевдокоде:

void SumAndPrint( Type& obj1, const Type& obj2 ) { printf( "Input objects:\n" );

PrintLn( obj1 );

PrintLn( obj2 );

Type& sum = Add( obj1, obj2 );

printf( "Sum object:\n" );

PrintLn( sum );

} Один вариант решения лежит на поверхности: оно получается из псевдокода помещением в его начало объявления шаблонной функции – листинг 4.17 уже не псевдокод, а текст на C++!

4.17. Обобщение алгоритма с использованием шаблона template class Type void SumAndPrint( Type& obj1, const Type& obj2 ) { printf( "Input objects:\n" );

PrintLn( obj1 );

PrintLn( obj2 );

Type& sum = Add( obj1, obj2 );

printf( "Sum object:\n" );

PrintLn( sum );

} Решение, представленное в листинге 4.17, универсально с точностью до сигнатур функции Add и PrintLn. Выбор верных экземпляров функции обеспечивается значением параметра шаблона Type, определяемого в ходе компиляции:

Complex a, b;

//...

SumAndPrint( a, b );

// Компилятор выявляет, что в качестве Type // подразумевается Complex, соответственно, // генерируется версия SumAndPrint для // Type = Complex //...

Rational x, y;

//...

SumAndPrint( x, y );

// Компилятор выявляет, что в качестве Type // подразумевается Rational, соответственно, // генерируется версия SumAndPrint для // Type = Rational //...

При компиляции шаблонной функции гарантируется проверка корректности типов, для которых вызывается функция SumAndPrint. Если для некоторого типа функции Add и PrintLn не определены, программа не будет компилироваться. Шаблонное решение легко распространяется на новые типы, для которых определяются соответствующие функции Add и PrintLn.

Однако подобное решение имеет важные недостатки и ограничения:

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

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

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

Модель организации вычислительного процесса, поддерживающий полиморфизм типов и функций в рамках процедурной парадигмы, А.И. Легалов называет процедурно-параметрическим полиморфизмом [Легалов, 2000], [Легалов, 2002]. В нашем случае решение, построенное на базе процедурно-параметрической парадигмы, может выглядеть следующим образом.

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

Таблица 4.1. Явная специализация вместо перегрузки и шаблона Значение Альтернативные реализации функций для разных функции типов Complex Rational Binom Add AddComplex AddRational AddBinom PrintLn PrintLnComplex PrintLnRational PrintLnBinom В соответствии с требующимися альтернативами определяем перечисляемый тип, содержащий уникальные идентификаторы для каждого из поддерживаемых типов:

const int NumTypes = 3;

// Число поддерживаемых типов enum CommonType { Unknown = -1, ComplexType = 0, RationalType, BinomType };

Далее определяется так называемый тип-оболочка, обобщающий поддерживаемый типы:

struct Common { CommonType type;

// Идентификация типа объекта данных void *value;

// Указатель на действительный объект // (указатель на void можно преобразовать // к указателю на любой тип) };

После этого в соответствии с перечнем функций из табл. 4. определяем типы данных и специализированные функции обработки объектов этих типов (содержательно реализация функций идентична функциям листинга 4.15, однако все функции написаны относительно «базового» типа Common):

#include stdio.h // Комплексное число struct Complex { double re;

// действительная часть double im;

// мнимая часть };

//Сложение комплесных чисел Common& AddComplex(Common& arg1, const Common& arg2 ) { // Преобразуем указатели Complex *pArg1 = (Complex *)(arg1.value);

const Complex *pArg2 = (const Complex *)(arg2.value);

// Выполняем действия над объектами данных // "комплексные числа" (*pArg1).re += (*pArg2).re;

(*pArg1).im += (*pArg2).im;

return arg1;

} // Вывод комплексного числа void PrintLnComplex( const Common& arg ) { const Complex *pArg = (const Complex *)(arg.value);

printf( "%lf+%lfi\n", (*pArg).re, (*pArg).im );

} // Рациональная дробь struct Rational { int numerator;

// числитель int denominator;

// знаменатель };

// Сокращение рациональной дроби void Shorten( Rational& arg ) { //...

} // Сложение рациональных дробей (упрощенная реализация) Common& AddRational(Common& arg1, const Common& arg2 ) { Rational *pArg1 = (Rational *)(arg1.value);

const Rational *pArg2 = (const Rational *)(arg2.value);

int sumNumerator;

int sumDenominator;

sumNumerator = (*pArg1).numerator * (*pArg2).denominator + (*pArg2).numerator * (*pArg1).denominator;


sumDenominator = (*pArg1).denominator * (*pArg2).denominator;

(*pArg1).numerator = sumNumerator;

(*pArg1).denominator = sumDenominator;

Shorten( *pArg1 );

return arg1;

} // Вывод рациональной дроби void PrintLnRational( const Common& arg ) { const Rational *pArg = (const Rational *)(arg.value);

printf( "%d/%d\n", (*pArg).numerator, (*pArg).denominator );

} // Бином struct Binom { double coeff[ 3 ];

// массив коэффициентов };

// Сложение биномов Common& AddBinom( Common& arg1, const Common& arg2 ) { Binom *pArg1 = (Binom *)(arg1.value);

const Binom *pArg2 = (const Binom *)(arg2.value);

for( int ix = 0;

ix 3;

ix++ ) { (*pArg1).coeff[ ix ] += (*pArg2).coeff[ ix ];

} return arg1;

} // Вывод бинома void PrintLnBinom( const Common& arg ) { const Binom *pArg = (const Binom *)(arg.value);

printf( "( " );

for( int ix = 2;

ix 0;

ix-- ) { printf( "%lf, ", (*pArg).coeff[ ix ] );

} printf( "%lf )\n", (*pArg).coeff[ 0 ] );

} Теперь для каждого из значений функций из первого столбца табл. 4. определим таблицу привязки различных экземпляров функции в зависимости от типа данных:

// Массив указателей на функции сложения Common& (*Add[ NumTypes ])( Common&, const Common& ) = { AddComplex, AddRational, AddBinom };

// Массив указателей на функции вывода void (*PrintLn[ NumTypes ])( const Common& ) = { PrintLnComplex, PrintLnRational, PrintLnBinom };

Обобщенная версия алгоритма может теперь быть записана следующим образом:

void SumAndPrint( Common& obj1, const Common& obj2 ) { printf( "Input objects:\n" );

PrintLn[ obj1.type ]( obj1 );

PrintLn[ obj2.type ]( obj2 );

Common& sum = Add[ obj1.type ]( obj1, obj2 );

printf( "Sum object:\n" );

PrintLn[ sum.type ]( sum );

} А.И. Легалов определяет параметрический полиморфизм как метод, обеспечивающий полиморфизм функций путем создания параметрического обобщения, объединяющего альтернативные специализации [Легалов, 2000].

В нашем случае роль такого обобщения выполняют перечисление CommonType и тип Common. Таким образом, удается обеспечить полиморфизм аргументов функций обработки данных конкретных типов (Complex, Rational, Binom и, возможно, других) без изменения обобщающей процедуры. Это особенно важно в тех случаях когда тип объектов, подвергаемых обработке обобщенной функцией, заранее неизвестен и определяется только в ходе вычислительного процесса.

Для того чтобы воспользоваться рассмотренным механизмом, для каждого поддерживаемого типа удобно определить специализированные функции, создающие «упакованный» объект типа Common и разрушающие его:

#include assert.h void CreateComplex( Common& obj, double re, double im ) { obj.type = ComplexType;

obj.value = (void *) new Complex;

assert( obj.value != NULL );

((Complex *)(obj.value))-re = re;

((Complex *)(obj.value))-im = im;

} void DestroyComplex( Common& obj ) { obj.type = Unknown;

if( obj.value != NULL ) delete (Complex*)(obj.value);

} void CreateRational( Common& obj, int numerator, int denominator ) { obj.type = RationalType;

obj.value = (void *) new Rational;

assert( obj.value != NULL );

((Rational *)(obj.value))-numerator = numerator;

((Rational *)(obj.value))-denominator = denominator;

} void DestroyRational( Common& obj ) { obj.type = Unknown;

if( obj.value != NULL ) delete (Rational*)(obj.value);

} void CreateBinom( Common& obj, double a, double b, double c ) { obj.type = BinomType;

obj.value = (void *) new Binom;

assert( obj.value != NULL );

((Binom *)(obj.value))-coeff[ 2 ] = a;

((Binom *)(obj.value))-coeff[ 1 ] = b;

((Binom *)(obj.value))-coeff[ 0 ] = c;

} void DestroyBinom( Common& obj ) { obj.type = Unknown;

if( obj.value != NULL ) delete (Binom*)(obj.value);

} Тестирующая программа (листинг 4.18) иллюстрирует процесс полиморфного разрешения типов функций чисто в рамках процедурной парадигмы (см. также соответствующую программу на компакт-диске).

Листинг 4.18. Процедурно-параметрический полиморфизм void main() { // Объекты испытаний // (в них поочередно упаковываются объекты данных разных типов) Common obj1;

Common obj2;

// Обработка объектов типа Complex CreateComplex( obj1, 1, -1 );

CreateComplex( obj2, 3, 2 );

SumAndPrint( obj1, obj2 );

DestroyComplex( obj1 );

DestroyComplex( obj2 );

// Обработка объектов типа Rational CreateRational( obj1, 1, 2 );

CreateRational( obj2, 1, 4 );

SumAndPrint( obj1, obj2 );

DestroyRational( obj1 );

DestroyRational( obj2 );

// Обработка объектов типа Binom CreateBinom( obj1, 2, 4, -1 );

CreateBinom( obj2, 3, 1, 6 );

SumAndPrint( obj1, obj2 );

DestroyBinom( obj1 );

DestroyBinom( obj2 );

} В результате исполнения этой программы будет напечатан следующий текст, свидетельствующий о выполнении нужных версий функций из семейств Add и PrintLn:

Input objects:

1.000000+-1.000000i 3.000000+2.000000i Sum object:

4.000000+1.000000i Input objects:

1/ 1/ Sum object:

3/ Input objects:

( 2.000000, 4.000000, -1.000000 ) ( 3.000000, 1.000000, 6.000000 ) Sum object:

( 5.000000, 5.000000, 5.000000 ) О развитии теории и практики процедурно-параметрической парадигмы программирования см. [Легалов, 2000], [Легалов, 2002] и на сайте www.softcraft.ru.

Глава 7. Визуализация проектирования в примерах и иллюстрациях Б. Шнейдерман указывал, что сложность ПО может иметь логический, структурный или психологический характер [Shneiderman, 1980].

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

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

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

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

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

7.1. Визуальный формализм на базе L-сети М.Ф. Лекарев предложил формализм, названный им L-сеть, который ориентирован на решение широкого класса задач. Несмотря но то, что математическую основу L-сети составляет модель конечного автомата, ее нельзя считать просто «новым синтаксисом» автоматной вычислительной схемы.

В [Лекарев, 1997] показано, что использование модели конечного автомата для разработки программ, требует двух важных дополнений:

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

Автомат должен быть полностью определенным (это обеспечивает надежность разрабатываемого ПО).

В основе визуальной модели программирования на базе L-сети лежит два комплекта примитивов, один из которых ориентирован на представление программы в форме сети автоматов (сеть разветвленного управления), а другой – на представление программы в форме иерархической сети функциональных модулей (сеть последовательного управления). В качестве функционального модуля может выступать отдельный фрагмент сети, имеющий явно определенную точку входа (такой функциональный модуль называется сетевой программой) или операционный модуль. Операционные модули представляют собой процедуры, разрабатываемые на конечном языке программирования (например, на C++). Проекты, выполненные с использованием L-сети, показали независимость определяемой L-сетью вычислительной платформы от языка и методологии программирования, используемой при написании операционных модулей [Лекарев, Мелехин, Пышкин, 1995], [Лекарев, 1997], [Лекарев, 2000-5], [Пышкин, 1999].

Среда последовательного управления В рамках L-сети используется модель функционального модуля с двумя выходами, которая, как показано в [Лекарев, 2000-1], хорошо отвечает запросам практики.

OM( OpenFile ) input = fopen( “input.txt”, “rt” );


if( input == NULL ) ABEND;

NORMEND:

OpenFile TRANS ENDOM STEP Рис. 7.1. Варианты завершения операционного модуля Действительно, даже в стандартной библиотеке C многие функции (Лекарев приводит оценку в 60%) определены таким образом, что могут завершиться успехом или неуспехом (например, открытие файла, резервирование динамической памяти, считывание данных из файла и т. д.).

Для подобных действий абстракция модуля с двумя выходами оказывается как нельзя более пригодной. В модели L-сети определены следующие способы завершения операционных модулей (рис. 7.1):

Завершение с шагом (Step). В среде последовательного управления этот вид завершения операционного модуля (изображаемый внизу графического примитива) также называется успешным (NORMEND, от англ. Normal End).

Завершение с переходом по дуге сети (Trans, от англ. transition). В среде последовательного управления этот вид завершения (изображаемый справа или слева) также называется неуспешным завершением (ABEND, от англ. abnormal end).

Интерфейсы данных LNetQSort 0 a[] n- Push n PARM left Pop Return right QuickSortStackItem IsShortExist body[] top InitSplit size QuickSortStack ixLeft FindPair ixRight x SwapPair copy Internal LeftIsShorter IsRightExist IsLeftExist ixRight left right ixLeft Push Push PrepareLeft PrepareRight Рис. 7.2. Сортировка Хоара в форме L-сети На рис. 7.2 представлена реализация алгоритма нерекурсивной сортировки Хоара в форме L-сети, идентичная по организации вычислительного процесса алгоритму из листинга 3.27. Отметим наглядный характер обращения к тем функциональным модулям, для которых используются два способа завершения. Схема управления вычислительным процессом столь наглядна, что, вероятно, не требует пояснений.

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

Возврат управления с шагом по сети (SReturn), который в среде последовательного управления можно также называть возвратом с успехом (Return).

Возврат управления с переходом (TReturn), который в среде последовательного управления можно также называть возвратом с неуспехом (AbReturn).

ScanIdent TReturn SReturn Рис. 7.3. Варианты завершения сетевой программы Среда разветвленного управления Основным элементом модели разветвленного управления L-сети является дуга L-сети (рис. 7.4). Дуга L-сети является обобщением (generalization) дуги графа переходов конечного автомата и состоит из трех основных элементов:

обособленное условие (возможно, маскируемое) – CondS (CONDition Special);

функциональный модуль, вызываемый при истинности обособленного условия;

переход по дуге (Transition).

переход CondS Рис. 7.4. Дуга L-сети В зависимости от выполнения условия и способа завершения функционального модуля осуществляется либо переход по дуге (Transition), изображаемый явно, либо шаг по сети (к следующей дуге), который не изображается, но подразумевается (рис. 7.5).

Семантика переходов при вызове операционного модуля TRANS STEP Семантика переходов при вызове сетевой программы TReturn SReturn Рис. 7.5. Дуга как часть сложного ветвления Несколько дуг, размещенных друг под другом, образуют так называемое сложное ветвление. На рис. 7.6 приведена сетевая программа считывания идентификатора (по функциональности эквивалентная реализации конечного автомата из разд. 3.2, листинг. 3.11), которая содержит 2 сложных ветвления. Фактически, вертикальная линия сложного ветвления является геометрическим образом состояния конечного автомата [Лекарев, 1997].

ScanIdent EOF getlit TReturn BLANK null LAT LexFirst getlit MASK_LAT LD LexNext MASK_LD BLANK null null null ERROR LexStop TReturn SReturn Рис. 7.6. Сетевая программа считывания идентификатора Обособленное условие может быть опущено. В этом случае управление передается функциональному модулю, указанному на дуге. В большинстве случаев функциональные модули, вызываемые в среде разветвленного управления, завершаются переходом по дуге сети (к этому «подталкивает»

особенность графики сложных ветвлений). Поэтому в среде разветвленного управления нормальным завершением функционального модуля (NormEnd – для операционного модуля и Return – для сетевой программы) считается именно переход по дуге (Transition), в то время как неуспешным завершением (AbEnd и AbReturn) считается шаг по сети.

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

Управление данными В основе концепции управления данными в L-сети лежит обобщение механизма связывания через общий интерфейс, рассмотренного в разд. 3.5.

В тех случаях, когда возможности, обеспечиваемые общим интерфейсом недостаточны (например, при реализации рекурсивных алгоритмов, требующих функциональных модулей с параметрами), реализуется динамическое связывание с данными. Подробнее о динамически связываемых интерфейсах см. в [Лекарев, 1997].

7.2. Визуальный язык ДРАКОН Интересным средством, нацеленным на визуализацию структурно императивного проектирования, является язык ДРАКОН (Дружелюбный Русский Язык, Который Обеспечивает Наглядность) и соответствующая теория [Паронджанов, 1999]. Язык ДРАКОН был разработан в НПО автоматики и приборостроения (г. Москва) и применен при построении ПО космического корабля «Буран».

Разработчики визуального формализма на основе языка ДРАКОН, критикуя неадекватность изобразительны средств схем алгоритмов и программ, отталкивались от двух руководящих принципов:

Легкость понимания программ – более важное требование, чем удобство их написания.

Текст не является наиболее адекватной формой формализации знаний.

В результате синтаксис ДРАКОН-схем содержит довольно большое число графоэлементов (икон).

Алгоритм в виде ДРАКОН-схемы может изображаться в двух основных видах – в виде примитива (используемого для алгоритмически простых задач) и в виде силуэта (используемого для запутанных, разветвленных алгоритмов). Пример примитива программы, распознающей идентификаторы в некотором файле, представлен на рис. 7.7.

ScanIdents input = OpenFile() ReadIdent ( input ) нет EOF да PrintIdent() Конец Рис. 7.7. ДРАКОН-примитив Силуэт состоит из набора так называемых веток, соответствующих отдельным частям алгоритма. На рис. 7.8 представлен силуэт алгоритма распознавания очередного идентификатора. Некоторые элементы ДРАКОН схемы пояснены на рисунке с помощью выносок.

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

Учитывая, что важным аспектом проектирования с использованием ДРАКОН-схем является обеспечение эргономичности восприятия, вводится правила построения эргономичных схем, определяющие пространственное размещение веток:

Порядок работы веток «слева направо».

Порядок размещения передачи управления веткам «слева направо».

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

правилам.

ReadIdent Заголовок с параметром input Имя First litera Next litera Finish Error ветки Нахождение Вывод Очередная первой Комментарий Завершение сообщения литера литеры об ошибке Шапка synterm = synterm = Вставка GetLit() GetLit() Рис. 7.8. ДРАКОН-силуэт synterm synterm Выбор SPACE LETTER EOF default SPACE LETTER EOF default LexFirst() LexNext() Конец First litera Next litera Finish Error Finish Next litera Finish Error Ветка имеет Адрес ветки несколько выходов (переход) Нетрудно заметить, что схема на рис. 7.8 соответствует перечисленным Для реализации отдельных функциональных блоков применяются текстовые средства программирования на основе известных алгоритмических языков. В [Паронджанов, 1999] перечисляется ряд гибридных визуально-текстовых языков из семейства ДРАКОН, в которых обеспечено строгое разграничение визуального синтаксиса (ДРАКОН схемы) и текстового синтаксиса (например, языков C и Pascal). В этом смысле конструктивная идея разграничения визуальной и текстовой составляющей проектирования родственна L-сети М.Ф. Лекарева.

Визуальный язык ДРАКОН образует наглядную среду для первоначального обучения программированию и мог бы быть весьма полезен при организации школьных курсов информатики.

Методы проектирования, ориентированные на ДРАКОН-схемы, позволяют преодолеть алгоритмическую сложность. Вопрос о преодолении структурной сложности ПО и сложности построения хороших абстракций данных предметной области остается открытым. Определенное неудобство представляет также использование новой терминологии вместо устоявшихся наименований, например, «вопрос» вместо общеупотребительного «условие», «шампур» вместо «основная ветвь программы», «вставка» вместо «предопределенный процесс» или «подпрограмма» и т. д., хотя, разумеется, это не является определяющим фактором.

7.3. Визуализация проектирования систем, основанных на событиях Исходя из тематики книги, в данном разделе мы рассматриваем развитие подходок к визуализации проектирования класса реактивных систем, которые либо не привязаны к определенной модели программирования, либо в существенной степени ориентированы на структурное проектирование.

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

Здесь мы рассмотрим основные важные для практики свойства диаграмм Харела.

Суперсостояния (superstates) Суперсостояния позволяют объединить группы состояний по принципу «исключающего ИЛИ» (XOR), из каждого из которых осуществляются эквивалентные переходы (рис. 7.9).

D x A A x x2 x2 x2 x C C B B x Рис. 7.9. Суперсостояния «XOR»

Объединение группы состояний по принципу «И» (AND) позволяет объединить переходы в эти состояния и создать основу для декомпозиции сложной управляющей структуры на более простые (рис. 7.10).

D D x3 x A A x x x2 x2 x2 x C C B B Рис. 7.10. Суперсостояния «AND»

Диаграммы (statecharts) Д. Харела содержат средства для визуализации учета «истории суперсостояния», обеспечивая переход в то состояние из группы, в котором автомат находился в последний раз, когда управление передавалось суперсостоянию (рис. 7.11).

D D H x3& [in On] x On On x x x2 x2 x2 x C C Off Off x3& [in Off] Рис. 7.11. Учет истории Для представления аппаратных и программных триггерных схем наличие такого формализма весьма полезно.

Пример использования диаграмм Харела для описания программного компонента, реализующего простой диалог DialogWindow возможностью установки флага во всплывающем окне CheckBoxWindows, содержащем поле CheckBox, представлен на рис. 7.12.

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

CheckBoxWindow DialogWindow check Display Checked click click ok cancel ok Unchecked Off Рис. 7.12. Событийный компонент Ортогональная декомпозиция Во многих случаях проектирование и изучение системы существенно упрощается, если удается выделить компоненты, работающие независимо с возможной синхронизацией параллельной работы.

На рис. 7.13 суперсостояние G образуется декартовым произведением суперсостояний S и T, то есть G S T. «Быть в суперсостоянии G »

означает одновременное выполнение условий «быть в суперсостоянии S »

(то есть в одном из состояний: A или B) и «быть в суперсостоянии T » (то есть в одном из состояний: C, D или E). Начальной парой состояний является пара (A,C), из которой, при поступлении сигнала x1 осуществляется синхронные переходы их A в C и из B в D, то есть в парное состояние (B,D).

G S T C A x x x2 x1 x4 D E x B G=SxT Рис. 7.13. Ортогональная декомпозиция Ортогональная декомпозиция позволяет более наглядно представить особенности функционирования системы в целом. Осуществление декомпозиции в связи с физической и логической обособленностью суперсостояний (компонентов системы) позволяет упростить проектирование и представление сложной системы, основанной на событиях.

На рис. 7.14 приведена диаграмма функционирования электронного секундомера с двумя кнопками. Кнопка a используется для управления режимами отображения («бегущее» время или отсечка). Кнопка b используется для пуска и остановки секундомера. Начальным состоянием является состояние zero.

stopwatch zero b a [in off] run display reg on a a b b [in on] lap off Рис. 7.14. Диаграмма функционирования секундомера В реальных системах переходы в одном суперсостоянии могут зависеть от другого суперсостояния. Такая зависимость обозначается на диаграмме условием в квадратных скобках (на рис. 7.14 при нажатии кнопки a автомат, «заведующий» отображением, переходит в состояние lap, если автомат, управляющий режимами пуска-остановки находится в состоянии on, в противном случае, из состояния reg осуществляется переход в состояние zero).

Для сравнения на рис. 7.15 приведена диаграмма конечного автомата без осуществленной ортогональной декомпозиции. Нетрудно убедиться, что логика переходов стала существенно менее очевидной.

a b b zero reg, on reg, off b a a a b lap, on lap, off b Рис. 7.15. Секундомер в форме конечного автомата Диаграммы Харела содержат также формализмы для представления переходов, управляемых условиями, для реализации временных задержек состояний и переходов, для параметризации состояний и др. Подробнее об основных компонентах диаграмм Харела см. в [Harel, 1987].

SWITCH-технология В связи с особым характером систем, управляемых событиями, а также систем реального времени, развивается особый класс средств программирования таких систем [Шопырин, Шалыто, 2004]. Один из активно развиваемых подходов является предложенная А.А. Шалыто SWITCH-технология [Шалыто, 1998], [Шалыто, Туккель, 2000].

Первоначальная область применения SWITCH-технологии – построение ПО систем логического управления, в частности, логических контроллеров. В дальнейшем были созданы варианты SWITCH-технологии, ориентированные на более широкий класс систем управления, реагирующих на события.

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

При этом входные и выходные воздействия реализуются функциями. В ходе работ по развитию SWITCH-технологии были разработаны средства интеграции автоматной модели программирования с объектно ориентированными технологиями.

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

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

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

На третьем этапе, на основании схемы связей автомата и требуемого поведения программы, строится граф переходов автомата (рис. 7.17).

Отметим возможность использования на графе переходов приоритетов событий. Поскольку действия могут изображаться как на дугах, так и в состояниях, полученный автомат называют «смешанным». Очевидно, что визуальными прототипами SWITCH-технологий в части изображения графов переходов смешанных автоматов можно считать диаграммы Харела и расширенные сети переходов (Augmented Transition Networks, ATN) [Jacob, 1985].

Чтение литеры и определение синтерма Инициализация A z лексемы Синтерм = LETTER e Синтерм = SPACE Регистрация e2 z очередной литеры Синтерм = ENDFILE e Синтерм = DIGIT10 Регистрация e4 z конца лексемы Некорректная литера e Проигнорировать z литеру Обработка События ошибки z некорректной литеры Выходные функции Рис. 7.16. Построение схемы связей автомата Наличие схемы связей обеспечивает переход от неформальных определений обрабатываемых объектов к формальным идентификаторам, используемых для обозначений автоматов, событий, входных и выходных функций.

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

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

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

Выполняемые Приоритет событий действия A 0. Начало сканирования 4. Ошибка z e1 2: e1 v e4 e1 v e 2: e4 v e z1 e 1. Очередная литера 2. Литера игнорируется 1: ixLex = ixLast z2 z 2: e2 v e e2 v e 3. Завершение лексемы События z Выходные функции z3: ;

z1: ixLex = -1;

ixLast = 30;

z2: ixLex++;

z4: ixLex++;

lex.value[ ixLex ] = ‘\0’;

lex.value[ ixLex ] = lit.value;



Pages:     | 1 |   ...   | 2 | 3 || 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.