Этапы решения задач на компьютере. Методы и искусство программирования

1 Лекция 3 Рассматриваемые вопросы: 1. Этапы решения задач на компьютерах. 2. Принципы проектирования программ сверху-вниз и снизу-вверх. 3. Трансляция, компиляция и интерпретация. Список используемой для подготовки литературы: 1) Могилев, А.В. Информатика: учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – М.: Издательский центр «Академия», 2009. – 848 с. 2) Информатика: экспресс-подготовка к интернет-тестированию: учеб. пособие / В.М. Титов, О.Н. Рубальская, О.В. Маленкова и др.; под ред. О.Н. Рубальской. – М.: Финансы и статистика; ИНФРА-М, 2010. – 240 с. 3) [1] Глава 3 Подраздел 4. Методы и искусство программирования 3.4.1. Проектирование программ В предыдущем подразделе, посвященном языку Паскаль, приведено немало примеров программ. Однако при анализе готовой программы чаще всего неясно как разработчики к ней пришли. В этом подразделе рассказывается об общих моментах в технологии программирования. Конечно, при разработке небольших учебных программ не все элементы этой технологии следует отрабатывать (да это и не всегда возможно), однако само ее существование должно быть осознано. Современный подход к проектированию программ основан на декомпозиции задачи, которая в свою очередь основана на использовании абстракций. Целью при декомпозиции является создание модулей, которые представляют собой небольшие, относительно самостоятельные программы, взаимодействующие друг с другом по хорошо определенным и простым правилам. Если эта цель достигнута, то разработка отдельных модулей может осуществляться различными людьми независимо друг от друга, при этом объединенная программа будет функционировать правильно. Различают абстракцию через параметризацию и через спецификацию. Смысл абстракции через параметризацию в том, что одним алгоритмом можно решать задачи, отличающиеся различными исходными данными, задаваемыми как параметры. Смысл абстракции через спецификацию в том, что разными алгоритмами можно получить один и тот же искомый результат. При этом описываются результаты работы программы, смысл обращения к программе становится ясным через анализ ее спецификации, а не самого текста программы. Разработка любой программы или программной системы начинается с определения требований к ней для конкретного набора пользователей и заканчивается эксплуатацией системы этими пользователями. Существуют различные подходы и технологии разработки алгоритмов и программ. Хотя программирование в значительной степени искусство, тем не менее, можно систематизировать и обобщить накопленный профессиональный опыт. По современным взглядам проектирование и разработку программ целесообразно разбить на ряд последовательных этапов: 1) постановка задачи; 2) проектирование программы; 3) построение модели; 4) разработка алгоритма; 5) реализация алгоритма; 6) анализ алгоритма и его сложности; 2 7) тестирование программы; 8) документирование. Кратко остановимся на каждом из этих этапов. При постановке задачи для крупных компьютерных программ необходимо провести следующие работы: • выработать требования (свойства, качества и возможности), необходимые для решения проблемы или достижения цели (как правило, эта деятельность носит экспертный характер); • разработать спецификации, включающие: o цель программы; o граничные условия; o описание функций системы; o спецификации входных и выходных данных; o верификационные требования (установление тестовых случаев); o тип и количество документов. В ходе этой работы выявляются свойства, которыми должна обладать система в конечном виде (замысел), описываются функции системы, характеристики интерфейса. Чтобы приступить к решению задачи, необходимо точно ее сформулировать. В первую очередь, это означает определение исходных и выходных данных, т.е. ответы на вопросы: а) что дано? б) что нужно найти? Дальнейшая детализация постановки задачи представляет собой ответы на серию вопросов такого рода: • как определить решение; • каких данных не хватает и все ли они нужны; • какие сделаны допущения и т.п. Проектирование программы осуществляется следующим образом. Сначала производится проектирование архитектуры программной системы. Это предполагает первичную (общую) стадию проектирования и заканчивается декомпозицией спецификаций в структуру системы. Обычно на модульном уровне разрабатывается спецификация каждого модуля: • имя/цель – дается имя модулю и предложение о его функции с формальными параметрами; • неформальное описание – обзор действий модуля; • ссылки – какие модули ссылаются на него и на какие модули ссылается данный модуль; • вход/выход – формальные и фактические параметры, глобальные, локальные и связанные (общие для ряда модулей) переменные; • примечания – полезные комментарии общего характера по модулю. Следующим шагом является детальное проектирование. На этом этапе происходит процедурное описание программы, выбор и оценка алгоритма для реализации каждого модуля. Входной информацией для проектирования являются требования и спецификации системы. Для проектирования программ существуют различные подходы и методы. Современный подход к проектированию основан на декомпозиции, которая, в свою очередь, основана на использовании абстракции. Целью при декомпозиции является создание модулей, которые взаимодействуют друг с другом по определенным простым правилам. Декомпозиция используется для разбиения программы на компоненты, которые затем могут быть объединены. Методы проектирования архитектуры делятся на две группы: 1) ориентированные на обработку; 2) ориентированные на данные. Методы, ориентированные на обработку, включают следующие общие идеи. а) Модульное программирование. Его основные концепции: • каждый модуль реализует единственную независимую функцию; • модуль имеет единственную точку входа/выхода; 3 • размер модуля минимизируется; • каждый модуль разрабатывается независимо от других модулей; • система в целом построена из модулей. Исходя из этих принципов каждый модуль тестируется отдельно, затем после кодирования и тестирования происходит их интеграция и тестируется вся система. б) Функциональная декомпозиция. Подобна стратегии «разделяй и управляй». Практически является декомпозицией в форме пошаговой детализации и концепции скрытия информации. Каждый модуль характеризуется субъективным решением проектировщика, связь осуществляется с помощью хорошо организованных интерфейсов. в) Проектирование с использованием потока данных. Использует поток данных как генеральную линию проектирования программы. Содержит элементы структурного проектирования сверху-вниз с пошаговой детализацией: • экспертиза потоков данных и отображение графа потока данных; • анализ входных, центральных и выходных преобразующих поток данных элементов; • формирование иерархической структуры программы; • детализация и оптимизация структуры программы. г) Технология структурного анализа проекта. Основана на структурном анализе с использованием специальных графических средств построения иерархических функциональных связей между объектами системы. Эффективна на ранних стадиях создания системы, когда диаграммы просты и читаемы. Методы проектирования, основанные на использовании структур данных, описаны ниже. а) Методология Джексона. Структура данных – ключевой элемент в построении проекта. Структура программы определяется структурой данных, подлежащих обработке. Программа представляется как механизм, с помощью которого входные данные преобразуются в выходные. В методе предусматриваются: • разработка и изображение структуры входных и выходных данных; • изображение структуры программы путем соединения изображений этих структурных элементов; • определение дискретных операций над структурами данных; • построение алгоритмов обработки структур данных. б) Методология Уорнера. Подобна предыдущей, но процедура проектирования более детализирована. Используются следующие виды представления проекта: • диаграммы организации данных (описывают входные и выходные данные); • диаграммы логического следования (логический поток этих данных); • список инструкций (команды, используемые в проекте); • псевдокод (описание проекта); • определение входных данных системы; • организация входных данных в иерархическую структуру; • детальное определение формата элементов входного файла; • то же самое для выходных данных; • спецификация программы: чтение, ветвление, вычисление, выходы, вызовы подпрограмм; • составление диаграммы (по типу блок-схем), указывающей логическую последовательность инструкций. в) Метод иерархических диаграмм. В этом методе определяется связь между входными, выходными данными и процессом обработки с помощью иерархической декомпозиции системы (без детализации). По сути используются три элемента: вход, обработка, выход. Алгоритм проектирования по этому методу заключается в следующих шагах: 4 1) начать с наивысшего уровня абстракции, определив вход, выход, обработку; 2) cоединить каждый элемент входа и выхода с соответствующей обработкой; 3) документировать каждый элемент системы, используя диаграммы; 4) детализировать диаграммы, используя шаги 1 – 3. г) Объектно-ориентированная методология проектирования. Основана на концепции упрятывания информации и абстрактных типов данных. Рассматриваются данные, модули и системы в качестве объектов. Каждый объект содержит некоторую структуру данных с набором процедур, знающих как работать с этими данными. По этой методологии создаются абстракции по заданной проблемной области: • определение проблемы; • развитие неформальной стратегии, удовлетворяющей требованиям к системе; • формализация стратегии; • создание объектов и их атрибутов; • определение операций над объектами; • установка интерфейсов; • реализация операций. Построение модели в большинстве случаев является непростой задачей. Чтобы приобрести опыт в моделировании, необходимо изучить как можно больше известных и удачных моделей. При построении моделей, как правило, используют два принципа: дедуктивный (от общего к частному) и индуктивный (от частного к общему). При дедуктивном подходе (рис. 3.2) рассматривается частный случай общеизвестной фундаментальной модели. При заданных предположениях известная модель приспосабливается к условиям моделируемого объекта. Например, можно построить модель свободнопадающего тела на основе известного закона Ньютона ma = mg - Fconp, и в качестве допустимого приближения принять модель равноускоренного движения для малого промежутка времени. Индуктивный способ (рис. 3.3) предполагает выдвижение гипотез, декомпозицию сложного объекта, анализ, затем синтез. Здесь широко используется подобие, аналогичное моделирование, умозаключение с целью формирования каких-либо закономерностей в виде предположений о поведении системы. Технология построения модели при индуктивном способе: 1) эмпирический этап (умозаключение, интуиция, предположение, гипотеза); 2) постановка задачи для моделирования; 3) оценки, количественное и качественное описание; 4) построение модели. Разработка алгоритма – самый сложный и трудоемкий процесс, но и самый интересный в творческом отношении. Выбор метода разработки зависит от постановки задачи, ее модели. (О некоторых приемах и методах разработки алгоритмов говорилось ранее в гл. 1 и будет сказано в следующих разделах данной главы.) На этом этапе необходимо провести анализ правильности алгоритма, что очень непросто и трудоемко. Наиболее распространенная процедура доказательства правильности алгоритма – это прогон его на множестве различных тестов. Однако это не гарантирует того, что не может существовать случая, в котором программа «не сработает». В общей методике доказательства правильности алгоритма предполагают, что алгоритм описан в виде после- 5 довательности шагов. Для каждого шага предлагается некое обоснование его правильности для всех подходящих входных (условиях до данного шага) и выходных данных (условиях после этого шага). Затем предлагается доказательство конечности алгоритма с окончательными исходными входными и выходными данными. На этапе реализации алгоритма происходят конструирование и реализация алгоритма, включающие кодирование, интеграцию, тестирование (сертификацию). По сути проводится перевод проекта в форму программы для конкретного компьютера, сборка системы и ее прогон при тестовых и нормальных условиях для подтверждения ее работы в соответствии со спецификациями системы. Этот этап зависит от того, какой язык программирования выбран, на каком компьютере алгоритм будет реализован. С этим связаны выбор типов данных, вводимых структур данных, связь с окружающей средой и т.п. Важно осознавать интерактивность, вид транслятора (компилятор или интерпретатор), наличие библиотек подпрограмм, модулей и объектов. Анализ алгоритма и его сложности необходим для оценки ресурсов компьютеров, на которых он будет работать, времени обработки конкретных данных, приспособления в работе в локальных сетях и телекоммуникациях. Хотелось бы также иметь для данной задачи количественный критерий для сравнения нескольких алгоритмов с целью выбора более простого и эффективного среди них. Перед началом эксплуатации программы необходим этап ее отладки и тестирования. Тестирование – это процесс исполнения программ с целью выявления (обнаружения) ошибок. Тестирование – процесс деструктивный, поэтому считается, что тест удачный, если обнаружена ошибка. Хорошим считается тест, который имеет большую вероятность обнаружения еще не выявленной ошибки. Удачным считается тест, который обнаруживает еще не выявленную ошибку. Существуют различные способы тестирования программ: • тестирование программы как «черного ящика» - стратегия «черного ящика» определяет тестирование с анализом входных данных и результатов работы программы. Критерием исчерпывающего входного тестирования является использование всех возможных наборов входных данных; • тестирование программы как «белого ящика» заключается в стратегии управления логикой программы, позволяет использовать ее внутреннюю структуру. Критерием выступает исчерпывающее тестирование всех маршрутов и управляющих структур программы. Разумная и реальная стратегия тестирования – сочетание моделей «черного и белого ящиков». Принципы тестирования: • описание предполагаемых значений выходных данных или результатов должно быть необходимой частью тестового набора; • тесты для неправильных и непредусмотренных входных данных следует разрабатывать так же тщательно, как для правильных и предусмотренных; • необходимо проверять не только делает ли программа то, для чего она предназначена, но и не делает ли она то, что не должна делать; • нельзя планировать тестирование в предположении, что ошибки не будут обнаружены; • вероятность наличия необнаруженных ошибок в части программы пропорциональна числу ошибок, уже обнаруженных в этой части; • тестирование – процесс творческий. При разработке программ очень полезным бывает метод «ручного тестирования» без компьютера на основе инспекции и сквозного просмотра (тестирование «всухую»). Инспекция и сквозной просмотр – это набор процедур и приемов обнаружения ошибок при чтении текста. Основные типы ошибок, встречающихся при программировании: • обращения к переменным, значения которым не присвоены или не инициализиро- 6 ваны; • выход индексов за границы массивов; • несоответствие типов или атрибутов переменных величин; • явные или неявные проблемы адресации памяти; • ошибочные передачи управления; • логические ошибки. При проектировании процедуры тестирования предусматривают серии тестов, имеющих наивысшую вероятность обнаружения большинства ошибок. Для целей исчерпывающего тестирования создают эквивалентные разбиения входных параметров, причем предусматривают два класса: правильные входные данные и неправильные (ошибочные входные значения). Для каждого класса эквивалентности строят свой тест. Классом эквивалентности тестов можно назвать такое множество тестов, что выполнение алгоритма на одном из них гарантирует аналогичный результат прогона для других. Особое внимание необходимо уделять тестам на граничных условиях. Граничные условия – это ситуации, возникающие непосредственно на, выше или ниже границ входных и выходных классов эквивалентности (т.е. вблизи границ эквивалентных разбиений). В частности, примерами классов эквивалентных тестов для алгоритма решения квадратного уравнения могут служить следующие классы: множество действительных, отличных от нуля, чисел а, b, с, таких, что b ⋅ b - А ⋅ а ⋅ с < 0; множество чисел а = 0, b и с не равны нулю; b = 0, а и с не равны нулю, и т.п. Сам процесс тестирования может быть пошаговым и/или монолитным. В том и в другом случае используют стратегии нисходящего тестирования, начиная с верхнего, головного модуля, и затем подключая последовательно другие модули (аппарат заглушек), и восходящего тестирования, начиная с тестирования отдельных модулей. В процессе отладки программы используют метод грубой силы - использование выводов промежуточных данных по всей программе (трассировка) или использование автоматических средств. Например, в Турбо Паскале имеется в наличии мощный аппарат автоматической отладки программ (режим Debug). Есть золотое правило программистов – оформляй свои программы в том виде, в каком бы ты хотел видеть программы, написанные другими. К каждому конечному программному продукту необходимо документированное сопровождение в виде помощи (help), файлового текста (readme.txt). [1] Глава 2 Подраздел 2. Понятие о системе программирования 2.2.1. Основные функции и компоненты Системы программирования – это комплекс инструментальных программных средств, предназначенный для работы с программами на одном из языков программирования. Системы программирования предоставляют сервисные возможности программистам для разработки их собственных компьютерных программ. В настоящее время разработка любого системного и прикладного программного обеспечения осуществляется с помощью систем программирования, в состав которых входят: • трансляторы с языков высокого уровня; • средства редактирования, компоновки и загрузки программ; • макроассемблеры (машинно-ориентированные языки); • отладчики машинных программ. Системы программирования, как правило, включают в себя: • текстовый редактор (Edit), осуществляющий функции записи и редактирования исходного текста программы; • загрузчик программ (Load), позволяющий выбрать из директории нужный текстовый файл программы; • запускатель программ (Run), осуществляющий процесс выполнения программы; • компилятор (Compile), предназначенный для компиляции или интерпретации ис- 7 ходного текста программы в машинный код с диагностикой синтаксических и семантических (логических) ошибок; • отладчик (Debug), выполняющий сервисные функции по отладке и тестированию программы; • диспетчер файлов (File), предоставляющий возможность выполнять операции с файлами: сохранение, поиск, уничтожение и т.п. Ядро системы программирования составляет язык. Существующие языки программирования можно разделить на две группы: процедурные и непроцедурные (рис. 2.11). Процедурные (или алгоритмические) языки программирования представляют собой систему предписаний для решения конкретной задачи. Роль компьютера сводится к механическому выполнению этих предписаний. Процедурные языки разделяют на языки низкого и высокого уровня. Языки низкого уровня (машинно-ориентированные) позволяют создавать программы из машинных кодов, обычно в шестнадцатеричной форме. С ними трудно работать, но созданные с их помощью высококвалифицированным программистом программы занимают меньше места в памяти и работают быстрее. С помощью этих языков удобнее разрабатывать системные программы, драйверы (программы для управления устройствами компьютера), некоторые другие виды программ. Программы на языках высокого уровня близки к естественному (английскому) языку и представляют набор заданных команд. Перечислим наиболее известные процедурные системы программирования высокого уровня. 1. Фортран (FORmula TRANslating system – система трансляции формул); старейший язык, и по сей день активно используемый в решении задач математической ориентации. 2. Бейсик (Beginner's All-purpose Symbolic Instruction Code - универсальный символический код инструкций для начинающих); несмотря на многие недостатки и изобилие плохо совместимых версий – самый популярный по числу пользователей. 3. Алгол (ALGOrithmic Language – алгоритмический язык); сыграл большую роль в теории, но для практического программирования сейчас почти не используется. 4. ПЛ/1 (PL/1 Programming Language – язык программирования первый). Многоцелевой язык; сейчас почти не используется. 5. Си (С – «си»); широко используется при создании системного программного обеспечения. 6. Паскаль (Pascal – назван в честь ученого Блеза Паскаля); чрезвычайно популярен как при изучении программирования, так и среди профессионалов. На его базе созданы несколько более мощных языков (Модула, Ада, Дельфи). 7. Кобол (COmmon Business Oriented Language – язык, ориентированный на общий бизнес); в значительной мере вышел из употребления. 8. Дельфи (Delphi) – язык объектно-ориентированного «визуального» программирования; в данный момент чрезвычайно популярен. 9. Джава (Java) – платформенно-независимый язык объектно-ориентированного программирования, чрезвычайно эффективен для создания интерактивных вебстраниц. Среди непроцедурных языков наиболее известны: 1) Лисп (Lisp); 8 2) Пролог (PROgramming in LOGic); 3) Оккам (назван в честь философа У. Оккама). Широкое распространение среди разработчиков программ, а также при обучении программированию, получили системы программирования «Турбо» (Turbo) фирмы Borland, ядром которых являются трансляторы с языков программирования Бейсик, Паскаль, Си, Пролог и др. Интерфейс Турбо-оболочки для любых систем программирования внешне одинаков и предоставляет пользователю стандартный набор функций и команд, описанных выше и отображаемых в главном меню системы. 2.2.2. Трансляция программ и сопутствующие процессы С появлением первых компьютеров программисты серьезно задумывались над проблемой кодирования компьютерных программ. Уже с конца 1940-х гг. стали появляться первые примитивные языки программирования высокого уровня. В них программист записывал решаемую задачу в виде математических формул, а затем, используя специальную таблицу, переводил символ за символом, преобразовывая эти формулы в двухлитерные коды. В дальнейшем специальная программа (впоследствии названная интерпретатором) превращала эти коды в двоичный машинный код. Г.Хоппер разработал первый компилятор в начале 1950-х гг.; он осуществлял функцию объединения команд и в ходе трансляции производил организацию подпрограмм, выделение памяти компьютера, преобразование команд высокого уровня (в то время псевдокодов) в машинные команды. В дальнейшем компиляторы и интерпретаторы для машинно-ориентированных языков (низкого уровня) стали развиваться и прочно вошли в практику компьютерного дела. Идеи трансляции (перекодирования) одних символов в другие легли в основу создания различных языков программирования с соответствующими трансляторами – компиляторами и/или интерпретаторами. Отличие компиляторов от интерпретаторов заключается в процедуре трансляции текста в машинный код. Компилятор преобразует весь текст программы в последовательный набор машинных команд, который в дальнейшем отправляется на выполнение. Интерпретатор же осуществляет трансляцию по принципу синхронного перевода. Каждая отдельная строка программного текста транслируется, а затем, после ее интерпретации, команды этой строки выполняются. Современные трансляторы с языков программирования высокого уровня, систем управления базами данных интегрируют в себе возможности и достоинства компиляторов и интерпретаторов, а в системы программирования добавляют различные сервисные утилиты по трансляции и отладке создаваемых программ. Важнейшим элементом в развитии систем программирования выступили подпрограммы. Появление аппарата подпрограмм существенно облегчило процесс разработки системных и прикладных программ. Подпрограммы позволили формировать библиотеки из наиболее часто употребляемых в программах алгоритмов процедур и функций. В системах программирования обязательно присутствуют стандартные (встроенные в систему) библиотеки подпрограмм. Например, в их число входят подпрограммы вычисления математических функций sin x, cos x, abs x и др. В настоящее время распространены пользовательские и прикладные библиотеки подпрограмм; их число увеличивается; меняется структура библиотечных подпрограмм. В современных языках получили распространение модули (Unit), представляющие специализированные пакеты взаимосвязанных подпрограмм определенного назначения, например по работе с клавиатурой, с графикой и пр. Развитие объектно-ориентированного программирования позволило создавать библиотеки объектов и подпрограмм с объектными типами данных (Object). Примером могут служить оболочки типа Turbo Vision. Современная программа представляет набор команд, операторов и выражений в которых имеются ссылки (прямые или косвенные) на различные подпрограммы из существующих в системе программирования библиотек, модулей, объектов. В этой связи исходный текст программы, как правило, занимает по объему места в памяти в несколько раз меньше, чем его оттранслированный вариант в машинных кодах. Как это происходит? Рассмотрим один из вариантов трансляции программы с языка программирования 9 Паскаль. Исходный текст программы решения квадратного уравнения представлен ниже. Program KvadUravn; var А, В, С, D, X1, Х2: REAL; begin writeln; {*} writeln('введи А,В,С); read(А,В,С); {*} D:=B*B-4*A*C; if D<0 then write('корней нет') {*} else begin X1:=(-B+sqrt(D))/(2*A); {*} X2:=(-B-sqrt(D))/(2*A); {*} write('X1=', X1, 'X2=', X2); {*} end end. Предположив, что этот текст (по отношению к процессу трансляции выступающий как исходный модуль) сформирован одним из текстовых редакторов, попытаемся отправить его на выполнение. Прежде всего, его необходимо перевести в машинный двоичный код (называемый абсолютным или загрузочным модулем). Для этого на первых этапах осуществляется трансляция (в данном случае, как это реализовано в системах программирования Паскаля, компиляция) исходного текста в машинный код (объектный модуль). Однако объектный модуль не может быть использован для выполнения программы, поскольку в нем нет программ по выполнению процедур ввода (read) и вывода (write, writeln), а также вычисления функции извлечения квадратного корня (sqrt). В исходном тексте программы ссылки на указанные библиотечные подпрограммы отмечены знаком { * }. Следующий шаг трансляции – компоновка – заключается в подключении к исходному объектному модулю объектных модулей соответствующих подпрограмм в места ссылок на них (исходные тексты этих подпрограмм в системе вовсе отсутствуют). Другими словами, на место процедуры write помещается подпрограмма, осуществляющая процедуру вывода данных на экран дисплея. Таким образом, после компоновки (или, иначе, редактирования связей – link editor) возникает абсолютный модуль, намного превышающий по объему размер исходного текста программы. Он и является исполняемым компьютером после его запуска. Расширениями его файлового имени, как правило, являются .com или .ехе. В силу того что объектные модули не предназначены для непосредственного исполнения, в них обычно нет привязки составляющих их машинных команд к конкретному месту в ОЗУ. Адреса машинных слов бывают условными, что помогает компоновщику размещать объектные модули в свободных местах ОЗУ (заменяя условные адреса команд на конкретные). Многие системы программирования дополнительно содержат промежуточные этапы трансляции. В этих системах на первом шаге предусмотрена трансляция исходного текста в макроассемблерный код, а затем в объектный модуль. Это связано с историей развития языков программирования, а также с тем, что многие подпрограммы удобнее писать на языке Ассемблера, и подключать их легче на этапе объединения (связывания) ассемблерного модуля с ассемблерными библиотеками подпрограмм. В современных системах программирования, например Турбо Паскаль, Турбо Си, весь этот сложный процесс трансляции с компоновкой подпрограмм скрыт от пользователя и осуществляется специальными компиляторами. Коротко об отладчиках. Эти программы входят в современные системы программирования и предоставляют средства для просмотра и изменения значений переменных в ходе отладки программы, поиска ошибок и т.д. Использование отладчиков значительно облегчает процесс доводки больших программ. 10 Заметим, что описанный процесс трансляции характерен для компиляции. Последовательно реализованный интерпретатор объектного модуля фактически не создает. В этом его и недостаток, и достоинство (экономия машинной памяти). Впрочем у современных ЭВМ, в том числе и персональных, проблема малого ОЗУ отходит на второй план, и интерпретация встречается все реже, так как эффективность этого процесса в целом значительно ниже. Остается непонятным, как детально происходит трансляция. Пользователь может не уметь сам вручную оттранслировать программу (даже столь короткую, как вышеприведенная), но элементарное понимание этого сложного процесса необходимо. Поясним детальнее, как происходит трансляция. На первом этапе транслятор производит синтаксический анализ исходной программы - проверяет, не нарушены ли формальные правила, содержащиеся в данном языке программирования. Например, в Паскале текст +–* может встретиться либо внутри текстовой константы (т.е. в апострофах), либо внутри комментария. Если такой текст встретился в другом месте, то это явная ошибка. В системе программирования встроены описания всех синтаксически разрешенных конструкций, и транслятор применяет их к исходной программе. Для задания синтаксиса применяются формы Бэкуса-Наура и синтаксические диаграммы, о которых будет рассказано в следующей главе. Первой фазой синтаксического анализа является лексический анализ. Он заключается в просмотре литер исходной программы и построении из них лексически допустимых единиц – идентификаторов, ключевых слов языка, чисел и т.д. Во второй фазе эти единицы уже рассматриваются как неделимые и проверяется допустимость их сочетания. Даже если в синтаксическом смысле исходная программа верна, это не означает, что она имеет смысл в рамках данного языка программирования. На следующем этапе семантического анализа транслятор ищет ошибки такого рода: числа употребления слов begin и end не совпадают; переменные не описаны (в языке, требующем обязательного явного описания переменных), т.е. текст программы непонятен (семантика - смысловая сторона языка). Лишь после того, как в программе все синтаксически правильно и семантически понятно, транслятор переводит операторы программы в машинный код. Это отнюдь не означает, что в программе все благополучно - не исключены ошибки этапа исполнения (деление на ноль, выход за границу массива, переполнение разрядов и т.д.). Различные фазы компиляции могут быть как последовательными, так и частично перекрывающимися во времени. В зависимости от способа реализации компилятор читает и обрабатывает исходный текст один или несколько раз, называясь соответственно однопроходным, двухпроходным и т.д. [2] 6.2. Технологии программирования 6.2.1. Этапы решения задач на компьютерах Разработка программного комплекса состоит из нескольких этапов: • постановка задачи; • проектирование; • программирование; • отладка и тестирование; • создание документации; • сопровождение. На этапе постановка задачи формулируются общие требования к программному комплексу. Определяется состав входных и выходных данных, а также форма выдачи результатов. На этапе проектирования осуществляется выбор метода решения задачи, строится 11 математическая модель, производится выбор языка программирования, определяются структуры данных и разрабатываются алгоритмы решения задач. На этапе программирования (кодирования) пишутся программы. В процессе программирования проводится поэтапная отладка программы, при которой разработчик последовательно исправляет ошибки программного кода. После того, как программа написана, проводится проверка правильности и надежности работы программы в различных условиях. Этот процесс называется тестированием. Используются несколько специальных терминов, описывающих различные способы тестирования. Если разработчик теста имеет доступ к исходному коду программы, то такое тестирование называется тестированием «белого ящика», если не имеет, то тестирование называется тестированием «черного ящика». «Альфа»- и «Бета»-тестирование проводятся в реальных производственных условиях. Сначала проводится «Альфа»-тестирование. Этим тестированием занимаются разработчики. Затем программный комплект сдается в опытную эксплуатацию и тестированием начинают заниматься реальные пользователи («Бета»-тестирование). В ходе опытной, а затем и промышленной эксплуатации выявляются не только ошибки работы программы, но и ошибки в описании общих требований к системе. Программисты исправляют ошибки и дорабатывают программный комплекс. Этот процесс называется сопровождением. Тестирование, при котором проверяется, как внесенные изменения повлияли на функциональность предыдущей версии программы, называется регрессионным тестированием. 6.2.2. Принципы проектирования комплексов программ Имеются два способа проектирования комплексов программ. Первый способ – проектирование сверху-вниз. Этот способ основан на принципах системного подхода, при котором одна большая задача разбивается на составляющие подзадачи, каждая из которых в свою очередь также может быть разбита на подзадачи. Связи между подзадачами устанавливаются на уровне данных. Такой подход к созданию программных комплексов носит название структурного программирования, при котором имеется возможность организации совместной работы коллектива программистов. Второй способ – проектирование снизу-вверх. Этот способ предназначен для индивидуальной работы программиста. В этом случае постепенно, шаг за шагом, разрабатываются отдельные модули программного комплекса и наращиваются его функции. 6.2.3. Интегрированные среды программирования Интегрированные среды программирования предназначены для написания и отладки программ. Создание программы включает несколько этапов: написание текста, трансляция и компоновка. Текстовый редактор. Программы, написанные на языке высокого уровня, представляют собой обычный текст, поэтому они могут быть набраны в любом текстовом редакторе. Однако системы программирования часто содержат собственный текстовый редактор, содержащий ряд дополнительных функциональных возможностей. Например, редактор имеет систему встроенных подсказок для написания ключевых слов. Трансляция. Трансляция – это способ преобразования исходного текста программы, написанного на языке высокого уровня, в язык машинных кодов (объектный код). В процессе трансляции проводится лексический, синтаксический и семантический анализ текста программы. Если в программе имеются ошибки, то система программирования выдает соответствующие сообщения. На этапе лексического анализа производится выделение из исходного текста отдельных слов и символов языка и их проверка. Определяются ключевые, имена объектов и данных, удаляются лишние пробелы и комментарии. На этапе синтаксического анализа проверяется возможность получения правильной грамматической фразы исходного языка. На этапе семантического анализа производится проверка типов данных. 12 Существуют два способа трансляции: с помощью компиляторов и с помощью интерпретаторов. Интерпретация. При интерпретации отдельные операторы программы последовательно переводятся в язык машинных кодов, после чего они сразу же выполняются. При интерпретации легче проводить отладку программы. Компиляция. При компиляции сначала осуществляется перевод всего исходного текста программы в язык машинных кодов, а затем начинается процесс выполнения программы. Результатом работы компилятора является загрузочный модуль. Компоновка. Для создания сложных программных комплексов, состоящих из нескольких модулей, объектные модули объединяются в загрузочный модуль с помощью компоновщика (редактора связей или линковщика). [Выдержки] Проведенное обсуждение функционального проектирования сверху-вниз показывает, что этот метод плохо приспособлен для разработки важных систем. Он остается полезной парадигмой для небольших программ и отдельных алгоритмов, он также полезен для описания хорошо понятных алгоритмов, особенно в учебниках по программированию. Но он не масштабируем и не годится для больших практических программных систем. Таблица 1 – Сравнение нисходящего и восходящего проектирований СВЕРХУ-ВНИЗ СНИЗУ-ВВЕРХ это когда задача решается от общего к ча- это когда задача решается от малого к стному, крупные задачи разбиваются на большему, решаются конкретные задачи, их более мелкие и т.д. пока для каждой не результаты объединяются в более крупное найдется простого решения решение ПЛЮСЫ когда доходят до написания кода - уже есть начать можно здесь и сейчас, после первой проект системы итерации можно уже что-то показывать заказчику МИНУСЫ не всегда очевидно как разбивать задачу, качество постановки задач и собрание всего можно попасть в паралич анализа этого в кучу так, что бы работало, да еще и как надо зависит от профессионализма разработчиков, а так же представителей заказчика В общем, делают основной упор на про- В общем, делают основной упор на людей цесс Многим нравится «СНИЗУ – ВВЕРХ» больше, поскольку в нем процесс помогает людям, а не наоборот Широкое распространение при написании программ получили следующие три метода: нисходящий (сверху вниз), восходящий (снизу вверх) и специальный (на данный конкретный случай). В случае нисходящего метода вы начинаете созидательный процесс с программы высокого уровня и спускаетесь до подпрограмм низкого уровня. Восходящий метод работает в обратном направлении: вы начинаете с отдельных специальных подпрограмм, постепенно строите на их основе более сложные конструкции и заканчиваете самым верхним уровнем программы. Специальный подход не имеет заранее установленного метода.