До сих пор мы рассматривали решения для пар графов, при котором графы сохраняли свои первоначальные иерархические взаимоотношения. Часто первоначальное разбиение, намеченное проектировщиком, может быть оптимизировано путем простого использования параллельности для обеспечения более высокой производительности в рамках существующей иерархии, поддерживая соответствие целям проекта. Однако, максимальный параллелизм каждой пары графов (то есть каждой подсистемы) не предполагает максимального параллелизма всей системы. Таким образом, необходимо иметь расширение всей модели, если она нуждается в оптимизации. До того, как расширить иерархию нам необходимо проверить, имеется ли несоответствие или рекурсия среди этих подсистем. Несоответствие может быть между аргументами, объявленными в заголовке графа, и аргументами, используемыми, когда имя графа появляется в качестве промежуточного модуля. Нам необходима другая древовидная структура, а именно, дерево системы на расширенном уровне. На рис. 6. приводится пример сложной системы и ее дерева.
C помощью дерева системы могут быть обнаружены взаимно рекурсивные графы, которые приводят к циклам в дереве. Чтобы избежать неоднозначности, необходимо помнить, что модули проверки отличается от промежуточных модулей. Модуль проверки может иметь набор подграфов, которые являются возможными и только один из его подграфов может выполняться в каждый момент времени. Промежуточный модуль может быть расширен произвольно. Различие между деревом системы и деревом модуля явное. Если модуль не может быть расширен дальше, он называется “нижним модулем”.
Рис. 6. Пример сложной системы: 6а — система; 6b — дерево системы.
Основное достоинство восходящего реструктурирования состоит из двух функций: комбинирование и повторного анализа. Комбинирование предназначено для преобразования глобальной системы или локальной совокупности путем связывания их потомков и перестановки промежуточных модулей. Результатом может оказаться настолько сложная структура, что проектировщик не разберется в новом проекте. Ключом к пониманию новой структуры является тот факт, что все области и противообласти не были изменены. Данный метод позволяет структурировать проект до необходимой степени. Это может быть сделано путем связывания блоков, за которыми следуют их потомки, но, не включая те, которые проектировщик не хочет реструктурировать, хотя они могут иметь своих собственных потомков.
Закончив комбинирование, результирующая иерархия графов закончится на наборе нижних или объявленными “нижними” модулей. Далее следует повторный анализ новой пары графов, снова использую критерий достижения максимально возможной параллельности. Пример, приводимый на рис.7, показывает результаты для системы на рис.6 после восходящей обработки. Можно видеть, что лучшей декомпозицией является разбиение всей системы на подсистемы таким образом, что одна из них имеет другую подсистему, которая имеет свою собственную внутреннюю структуру, а не первоначальную стратегию трех подсистем.
Рис.7. Новая* структура, полученная методом комбинирования.
Лекция № 7
Формы Бэкуса Наура.
Формы Бэкуса Наура (БНФ) являются языком для выражения синтаксиса других языков. Для того, что ввести БНФ, воспользуемся описанием цифр, констант и упрощенных арифметических выражений.
То, что единица является цифрой, выражается в БНФ следующим образом:
:: =1 (*)
Чтобы отметить, что понятие цифра не может встречаться в предложениях описываемого языка, а используется лишь для того, чтобы понять, описать эти предложения, это понятие заключается в угловые скобки ‘’. Такое понятие является синтаксическим и называется нетерминалом (нетерминальным символом). Символ, который может встречаться в предложениях описываемого языка, называется терминалом (терминальным символом). Запись (*) называется продукцией или правилом (заменой). Левая часть правила – нетерминальный символ, а правая часть – непустая конечная цепочка нетерминальных и/или терминальных символов.
Символ ‘ ::= ’ читается как «может состоять из».
Если понятие, выраженное нетерминальными символами, включает набор терминальных символов, то используется символ ‘ | ’, который читается как «или».
Полное описание понятия «цифра» будет выглядеть следующим образом:
:: = 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ,
т.е. нетерминальный символ выражен через все терминальные символы.
Введем понятие константы целого типа. Константа целого типа – это конечная последовательность не менее чем из одной цифры.
Тогда константы целого типа могут быть следующим образом рекурсивно определены:
:: =
:: =
:: = 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Приведенное правило образует грамматику для языка констант.
Предложениями этого языка являются те последовательности терминальных символов, которые могут быть выделены из нетерминальных символов. Вывод производится следующим образом: начинаем с последовательности, состоящей из нетерминального символа, последовательно заменяем один из нетерминальных символов текущей последовательности на соответствующую правую часть правила до тех пор, пока не получается последовательность, состоящая лишь из терминальных символов в предложении.
Например, выведем предложение «325»:
= = 5 =
= 5 = 25 = 325
Символ ‘=’ обозначает одну замену, непосредственный вывод.
Грамматика упрощенных арифметических выражений:
:: = +
:: = —
:: = *
:: = ()
:: =
:: =
:: =
:: = 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Пример: представление предложения (1+2)*4 методом выбора:
= * = ( ) * = ( + ) * = ( + ) * = ( + ) * = ( 1 + ) * = ( 1 + ) * = ( 1 + ) * = ( 1 + 2 ) * = ( 1 + 2 ) * = ( 1 + 2 ) * = ( 1 + 2 ) * 4
Замена может производиться, начиная либо с последнего нетерминала, либо с первого, и так до получения терминала, но с учетом того, что в каждой итерации выполняется только одна замена.
Дерево разбора.
*
( )
+
4
1 2
Это дерево соответствует тем правилам замены, которые исполнялись ранее (см. пример выше). Каждая ветка дерева разбора продолжается до тех пор, пока не закончится терминальным символом.
Главное различие между выбором и деревом разбора в том, что дерево разбора не фиксирует порядка, в котором были сделаны некоторые шаги выводов. Выводы, соответствующие одному дереву разбора, считаются эквивалентными.
Для грамматики упрощенных арифметических выражений появляется следующая опасность:
Пример: = + *
+
*
или
*
+
Грамматика, в которой имеется более одного дерева разбора для некоторого предложения, называется неоднозначной.
Можно написать однозначную грамматику, в которой говорится, что умножение имеет приоритет над сложением (кроме того случая, когда для преодоления приоритет используются скобки). Для этого вводятся нетерминальные символы и :
::= | + | —
::= | *
::== | ()
:: =
:: = 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Также для БНФ вводятся фигурные скобки ‘{…}’ для облегчения понимания и записи.
Лекция ¹ 8
Синтаксис SDL
::=
::=|.
::= |
|
|
::=
====
::===
::=|[,]
::=|[,]
::=|
::=|
::= whiledo|
while|
ifthen|
ifthen
else|
switchcasesdefault|
switchcases
::=|
::=*|
—|
()|
::=| —
Лекция № 9
Проектирование.
Это второй формализуемый этап. Целью этого этапа является получение алгоритма и базисная структура. На стадии проектирования разрабатываются алгоритмы заданной спецификации, и формируется общая структура информационных систем.
Систему необходимо разбить на небольшие части таким образом, чтобы ответственность за реализацию каждой такой части можно было возложить либо на одного разработчика, либо на группу исполнителей. При этом для каждого определенного таким образом модуля системы должны быть сформулированы предъявляемые к нему требования:
- Реализуемые функции,
- Размеры,
- Время выполнения
и т.д.
В процессе проектирования системы по мере выполнения спецификации на отдельные подмодули, последние представляют в виде древовидной схемы, показывающей вложение элементов системы (стратификации системы). Такая схема называется базисной, и она неадекватна спецификации системы.
Пример: базисная схема для случая обработки типичного компилятора.
управляющая программа
синтаксический генератор
анализатор кода
блок сканирования подпрограммы вывод на печать
таблицы
символов
чтение
Смысл базисной схемы заключается в разбиении проекта так, чтобы его можно было наиболее эффективно предложить различным исполнителям. Если проект подразумевает
исполнение не одним человеком в течение короткого заданного времени, то необходимо минимизировать интерфейсы между исполнителями различных подсистем.
| Требования |
Рис.8 Модель процессов проектирования типичной программной системы
Эта модель не зависит от методологии. Все указанные в ней действия должны выполняться в той или форме во всякой разработке независимо оттого, какой язык программирования был принят, использовалось ли структурное программирование или объектно-ориентированное.
На этапе выполнения внешнего проекта высокого уровня определяется взаимодействие с пользователем, но не рассматриваются многие его детали, например, такие, как форматы ввода-вывода. Исходный внешний проект переводят к двум параллельным процессам. В процессе детального внешнего проектирования завершается определение взаимодействия с пользователем, описываются его мельчайшие подробности. В процессе разработки архитектуры системы выполняется ее разложение на множество программ, подсистем или компонент и определяются сопряжения между ними. Эти два шага ведут к процессу проектирования структурной программы, в котором проектируются модули, их сопряжения и взаимосвязи для каждой программы, компоненты или подсистемы. Следующий процесс – внешнее проектирование модуля. Это точное определение всех сопряжений модуля. Последний шаг – проектирование логики модуля – состоит в разработке внутренней логики каждого модуля; он включает также выражение этой логики текстом конкретной программы. Проектирование базы данных – процесс определения всех внешних для программной системы структур данных, например, записи в файле ли в базе данных.
На рис.8 иллюстрируются основные зависимости между процессами проектирования, но он не служит планом работы над каким-нибудь конкретным проектом. Возможны перекрытия между разными процессами, но не должно быть перекрытия между несмежными процессами.
Лекция №10
Сложность системы.
Сложность – основная причина ошибок перевода и одна из главных причин ненадежности программного обеспечения. На этапе проектирования также решается вопрос минимизации сложности.
В общем случае сложность объекта является функцией взаимодействия между его компонентами. Например, сложность внешнего проекта программной системы в некоторой степени определяется связями между всеми ее внешними сопряжениями (между командами пользователя и соотношением между входной и выходной информацией системы). Сложность архитектуры системы определяется связями между подсистемами, а сложность отдельного модуля – функция связи между его командами.
Борьба со сложностью.
1. Независимость, т.е. максимальное усиление независимости компонент (высокочастотная динамика заключается в единых компонентах, а межкомпонентные взаимодействия – низкочастотная динамика систем)
2. Иерархическая структура (позволяет стратифицировать систему по уровням понимания).
Страты – такая иерархия системы, когда на каждом уровне рассматривается система целиком с точки зрения разных понятий.
Пример: Страница текста (система)
На уровне набора букв (например, буква «а» встречается в 100 раз чаще буквы «ъ», комбинация «аб» встречается чаще «ащ» в 50 раз и т.д.)
На уровне слова (количество глаголов, существительных и других частей речи).
На уровне предложения (правила синтаксиса, семантики и т.д.).
Каждый уровень иерархии ссылается на другой (предыдущий). Например, слово – единица на предыдущем уровне предложения, но в то же время состоит из букв, которые анализируются на другом уровне.
3. Проявление связей.
Проектное решение любого уровня имеет некоторую внутреннюю организацию или форму. Для минимизации сложности необходим метод проявления этой внутренней формы с тем, чтобы в соответствии с нею разбить проект на части.
При внешнем проектировании разбиение системы в соответствии с ее внутренней формой называется концептуальной целостностью. При разработке архитектуры системы и проектировании структуры программы рассматриваются методы определения этой внутренней формы для дальнейшего разбиения системы на множество компонент с высокой степенью независимостью.
При проектировании логики программы дисциплина, называемая структурным программированием, имеет целью помимо прочего привести эту логику в соответствие с несколькими базовыми стандартными формами.
Лекция № 11
