Разработка схемы иерархии

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

Здесь все модули передают информацию в главную управляющую программу ОБРАБОТАТЬ ЗАПРОС. Эта программа активизирует подчиненные модули, проверяет их результаты, принимает решения и осуществляет управления.
Недостатки подхода:

1. С возрастанием сложности программы растет и сложность главного модуля.

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

12. Общая схема трансляции.

Общая схема работы транслятора

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

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

Общая схема работы компилятора

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

Во-первых, он является распознавателем для языка исходной программы. То есть он должен получить на вход цепочку символов входного языка, проверить ее принадлежность языку и, более того, выявить правила, по которым эта цепоч­ка была построена (поскольку на вопрос о принадлежности сам ответ «да» или «нет» представляет мало интереса). Интересно, что генератором цепочек входного языка выступает пользователь — автор исходной программы.

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

программа.

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

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

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

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

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

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

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

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

13. Объектно-ориентированное программирование.

В ООП по отношению к реальному миру в создаваемой системе предметы и понятия заменяются моделями, т.е. отдельными формальными конструкциями представляющими их в программной системе. Модель содержит не все признаки и свойства представляемого ею предмета, а только те которые существенны для разрабатываемой программной системы. Тем самым модель всегда беднее реального предмета. ООП позволяет уменьшить сложность программного обеспечения, повышения надежности ПО, обеспечение возможности модификаций отдельных компонентов, обеспечение возможности повторного использования отдельных компонентов ПО. Объект - реальная сущность, обладающая характерным поведением, отличительными характеристиками и являющейся важной предметной областью. Каждый объект имеет состояние, обладает определенным поведением, уникальной идентичностью.1) Состояние объекта. Состояние –совокупный результат поведения объекта. В любой конкретный момент времени состояние включает в себя перечень свойств объекта и текущие значения этих свойств.2) Поведение объекта. Каждый объект имеет набор действий, кот. с ним можно произвести. Файл-читать, удалить. Программа написанная с использованием ООП обычно состоит из множества объектов, они все взаимодействуют между собой, посредством передачи сообщений меду ними. 3()Поведение –действия и реакция объекта выраженные в терминах передачи сообщений и изменений состояний видимые извне и производимые активность объекта. Достоинства: сокращение времени на разработку, компоненты многоразового использования обычно содержат меньше ошибок. Недостатки: сложность документации, большое количество методов, неэффективность выполнения доступа к данным.

14. Организация бинарного поиска в таблицах.

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

Метод дихотомии заключается в следующем: выяснив, сколько всего элементов в отсортированном массиве, мы сравниваем число "X" со средним элементом массива. Если средний элемент массива больше, чем "X" - значит все элементы массива стоящие после среднего элемента массива тоже больше чем число "X", ведь мы работаем с отсортированным массивом. Следовательно, нам следует продолжить поиск в оставшейся части массива, расположенной до среднего элемента. Выяснив, сколько элементов в оставшейся части массива, мы опять выбираем средний элемент и сравниваем с ним число "X". Итак, для поиска нужного элемента остаётся только четверть массива. Затем границы поиска сужаются ещё больше - до восьмой части массива и так далее, до тех пор, пока не найдётся элемент массива равный числу "X" или пока не останутся два элемента массива, один больше числа "X", а другой меньше.

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

Для наглядности мы не стали наносить все элементы массива на отрезок, но если взглянуть на нижний отрезок и, учитывая, что он, в 32 раза меньший, чем исходный, содержит 2 элемента, становится понятно, что изначально мы имели массив приблизительно из 60 элементов. В результате применения метода дихотомии, выполнив всего лишь 6 операций сравнения, мы смогли закончить поиск. Если бы осуществлялся поиск прямым перебором, то нам потребовалось бы около 30 операций сравнения. Выигрыш на лицо.

15. Основные этапы разработки программного обеспечения.

Разработка начинается на системном уровне и проходит через анализ, проектирование, кодирование, тестирование, сопровждение. при этом моделируются действия стандартного инженерного цикла. 1) Сист. анализ задает роль каждого эл-та в компьютерной системе, взаимод. эл-в друг с другом. Анализ начинается с определенных требований ко всем системным элементам, т.к. ПО явл. частью большой системы и назначение подмножества этих требов. программному эл-ту. Уточняются и детализируются его функции, хар-ки и интерфейс. 2)Проетктирование состоит в создании представлений архитектуры ПО, алгоритмической структуры ПО, структуры данных, вх./вых. интерфейса. Исх. данные для проектирования содержатся в спецификации анализа, т.е. в ходе проектирования вып. трансляция требований к ПО во множестве проектных представлений. 3)Кодирование состоит в переводе рез-в проектирования в текст на языке программирования. 4) Тестирование- выполнение программы для выявления дефектов в функциях, логике и форме реализации программного продукта. 5)Сопровождение – внесение изменений в эксплуатируемое ПО. Цели изменения: исправление ошибок, усовершенствование ПО по требованиям заказчика. Сопровождение закл. в повторном примен. каждого из предшествующих шагов к существующей программе.

16. Понятие и эволюция операционных систем.

ОС относится к системному ПО. К системному ПО относятся такие программы и комплексы программ, кот. явл. общими без которых невозможно вып. или создание других программ. ОС представляет собой комплекс системных управляющих и обрабатывающих программ, кот. с одной стороны выступают как интерфейс между аппар. компьютера и пользователем, а с другой стороны предназначены для наиболее эффективного расходования ресурсов ВС и организации надежных вычислений. ОС выполняет функции управления вычислениями в компьютере, распределяет ресурсы ВС между различными вычислительными процессами и образует ту программную среду, в кот выполняются прикладные программы пользователя. Такая среда наз. операционной. Эволюция ОС.1) 1945-1955Эти ком. не имеют ОС. Созданы ламповые вычислительные устройства. Все задачи организации выч. процесса решались вручную каждым программистом с пульта управления.2)1955-1965 Новая техническая база-полупроводниковые эл-ты. Появились алгоритмические языки, компиляторы.Повились сист. пакетной обработки, кот. автоматизировали запуск одной программы за другой и тем самым увелич. коэффиц. загрузки процессора.3)1965-1980 Переход от отдельных полупров. эл. типа транзисторы к интегральным микосхемам. На одном процессоре вып. попеременно несколько программ.4) 1980 Появление БИС Однопрограммные однопользов.OC MSDOS исп. для комп. построенных на базе intel8088 Мультипрогр. многопольз. ОС UNIX.5)Сер. 80-хСтали развиваться сети РС, работающих под управлением сетевых или распределенных ОС. В сетевых ОС польз. должны быть осведомлены о наличии др. комп.и должны делать логич. вход. в другие комп., чтобы воспользоваться их ресурсами.