Иванова Г.С. - Основы программирования
.pdf/. Этапы создания программного обеспечения
Текст
программы N
Текстовый
редактор
Исходная
программа
<имя>.оЬ| J^
Объектная
программа
<имя>Лри
Библиотека
объектных
программ
Рис. 1.5. Схема процесса подготовки профаммы к выполнению
На рис. 1.5 представлена схема процесса подготовки программы к вы полнению.
Вначале осуществляют ввод программы в компьютер. Для ввода исполь зуют специальную программу - текстовый редактор^ с помощью которого создают файл, содержащий текст программы.
Затем программу необходимо перевести в последовательность машин ных команд (машинный код). Для этого запускают специальную программупереводчик - компилятор, В процессе разбора и преобразования программы компилятор может обнаружить ошибки. Тогда он аварийно завершает рабо ту, выдав программисту сообщения об ошибках компиляции. Для исправле ния этих ошибок обычно достаточно внимательно изучить соответствующий фрагмент с учетом текста сообщения об ошибке и внести требуемое измене ние в программу. После исправления ошибок процесс компиляции повторя ют. Если с точки зрения компилятора программа написана правильно, то он строит так называемый объектный код, содержащий текст программы на ма шинном языке. В среде программированияЗог1апс1 Pascal этот код не перепи сывается в файл, а сохраняется в памяти до выполнения следующего этапа. В других средах и языках программирования на диске создается объектный файл, как правило, с расширением .obj.
21
/. Этапы создания программного обеспечения
граммы в пошаговом режиме и проверить содержимое интересующих нас переменных (рис. 1.6, б).
Современные языки программирования, как правило, имеют так называ емые среды. Среда языка программирования объединяет специализирован ный текстовый редактор, компилятор, компоновщик, программу выдачи справочной информации, отладчик и другое программное обеспечение, ис пользуемое при разработке программ в единый пакет. Таким образом, среда языка программирования обеспечивает программисту все необходимые средства для реализации программы.
Помимо указанных выше типов ошибок, обнаруживаемых автоматичес ки компилятором, компоновщиком или операционной системой, существует еще группа очень опасных логических ошибок. Наличие таких ошибок в про грамме приводит к выдаче н е п р а в и л ь н ы х результатов. Для их обна ружения параллельно с отладкой программы осуществляют ее тестирование.
Тестированием называют процесс выполнения программы при различ ных тестовых наборах данных с целью обиаруэ/сеиия ошибок. Правильный подбор тестовых данных - отдельная и достаточно сложная задача. Некото рые аспекты тестирования программ будут обсуждаться в параграфе 3.2.
Для поиска логических ошибок также можно использовать отладчик: по шагам отследить процесс получения результата. Однако полезно бывает вы полнить программу вручную, фиксируя результаты выполнения команд на бумаге. При этом очень поможет пример расчета, выполненный вручную на этапе анализа и выбора методов.
Параллельно с процессом разработки программного продукта на всех этапах должно выполняться составление документации как для выполнения следующего этапа, так и для последующего сопровождения и модификации. Кроме того, важной составляющей этапа реализации является создание не обходимой документации для пользователей.
1.5. Модификация
Первоначально этап модификации не включался в процесс разработки программного обеспечения, но практика показала, что в большинстве случа ев разработанное программное обеспечение через некоторое время обновля ется, и, следовательно, в процессе разработки программного продукта необ ходимо учитывать возможность его модификации.
Причинами выпуска новых версий являются:
•необходимость исправления ошибок, выявленных в процессе дли тельной эксплуатации;
•необходимость совершенствования, например, улучшения интерфей са или расширения состава выполняемых функций;
•изменение среды (появление новых технических средств и/или про граммных продуктов).
23
Часть I. Основы алгоритмизации и процедурное программирование
Обычно программа состоит из нескольких частей, каждая из которых компилируется отдельно. Для объединения нескольких фрагментов в единую программу используют специальную программу -- компоновщик. В процессе связывания тйкже могут быть зафиксированы ошибки, которые называют ошибками компоновки. Для исправления таких ошибок, как правило, необхо димо сверить заголовки используемых подпрограмм и обращения к ним. Ис правив обнаруженные ошибки, вновь запускают компилятор и компоновщик. В результате компоновки получается готовая к выполнению программа, ко торую при желании можно сохранить в файле с расширением .ехе.
В процессе выполнения программа запрашивает, если это предусмотре но программистом, ввод исходных данных, осуществляет требуемую обра ботку и производит вывод результатов (рис. 1.6, а). При этом могут быть об наружены ситуации, когда продолжение работы программы теряет смысл, например, обнаружено «деление на нуль» или попытка открыть не существу ющий файл для чтения из него и т. п. Такие ошибки называют ошибками вы полнения. Для исправления этих ошибок может потребоваться их локализа ция, т.е. уточнение, при выполнении какого фрагмента программы зафикси ровано нарушение нормального вычислительного процесса.
Процесс локализации и исправления ошибок получил название отладки программы. При отладке программы часто используют специальные про граммы - отладчики, которые позволяют выполнить любой фрагмент про-
Исходные |
Программа |
5i Результаты |
|
данные |
|||
|
|
Отладочная
^^^^ информация
Результаты
Рис. 1.6. Процесс выполнения программы (а) и ее отладки с помощью отладчика (б)
22
Часть I. Основы алгоритмизации и процедурное программирование
На этом этапе, используя проектную документацию, в программный продукт вносят необходимые изменения, которые могут потребовать пере смотра проектных решений, принятых на предшествующих этапах.
1.6. Практикум. Разработка алгоритмов методом пошаговой детализации
Создание программы - процесс сложный, поэтому практически с любо го этапа возможен возврат на предыдущие этапы для исправления ошибок или принятия других проектных решений. Чаще всего такого рода возвраты являются следствием ошибок, допущенных при логическом проектировании программы. Поэтому в процессе программирования необходимо особое вни мание уделять разработке алгоритмов.
Для разработки алгоритмов программ часто используют метод пошаго вой детал^1зации [4, 9]. С использованием данного метода разработку алго ритмов выполняют поэтапно. На первом этапе описывают решение постав ленной задачи, выделяя подзадачи и считая их решенными. На следующем - аналогично описывают решение подзадач, формулируя уже подзадачи следу ющего уровня. Процесс продолжают до тех пор, пока не дойдут до подзадач, алгоритмы решения которых очевидны. При этом, описывая решение каждой задачи, желательно использовать не более одной-двух конструкций, таких как цикл или ветвление, чтобы четче представлять структуру программы.
Пример 1.3, Разработать программу, которая с заданной точностью 8 на ходит значение аргумента х по заданному значению функции у при изве стном значении п
(х+1)п-1
у = -
где п>1, х> 0.
При п >1 данная функция является монотонно возрастающей. Для на хождения значения х можно применить метод половинного деления. Суть данного метода заключается в следующем. Вначале определяют отрезок [xj, Х2] такой, что f(X]) < у < f(x2). Затем делят его пополам х^ = (Х]+Х2)/2 и определяют, в какой половине отрезка находится х, для чего сравнивают Г(х^) и у. Полученный отрезок опять делят пополам и так до тех пор, пока раз ность Xj и Х2 не станет меньше заданного значения е.
Для разработки алгоритма программы используем метод пошаговой де тализации.
24
/. Этапы создания программного обеспечения
Шаг L Определяем общую структуру программы.
Программа:
Ввести у, п, eps. Определить х. Вывести X, у.
Конец.
Шаг 2. Детализируем операцию определения х.
Определить х:
Определить х1 такое, что f(xl) < у. Определить х2 такое, что f(x2) > у. Определить х на интервале [х1, х2].
Все.
Шаг 3, Детализируем операцию определения х1. Значение х1 должно быть подобрано так, чтобы выполнялось условие f(xl) < у. Известно, что X > О, следовательно, можно взять некоторое значение х, например, х1=1, и последовательно уменьшая его, например в два раза, определить значение х1, удовлетворяющее данному условию.
Определить х1: х1:=1
цикл-пока f(xl) > у х1:=х1/2
все-цикл
Все.
Щаг 4, Детализируем операцию определения х2. Значение х2 определя ем аналогично х1, но исходное значение будем увеличивать в два раза.
Определить х2:
х2:=1
цикл-пока f(x2) < у х2:=х2*2
все-цикл
Все.
Шаг 5, Детализируем операцию определения х. Определение х выпол няется последовательным сокращением отрезка [х1, х2].
Определить х: цикл-пока x2-xl>eps
Сократить отрезок [х1, х2]. все-цикл
Все.
25
Часть 1. Основы алгоритмизации и процедурное программирова
Шаг 6, Детализируем операцию сокращения интервала определения х. Сокращение отрезка достигается делением пополам и отбрасыванием поло вины, не удовлетворяющей условию f(x]) ^ у ^ f(x2)
Сократить интервал определения х:
xt:=(xl |
+х2)/2 |
если f(xt) > у |
|
то |
х2 := xt |
иначе х1 :=xt все-если
Все.
Таким образом, за щесть шагов мы разработали весь алгоритм, который выглядит следующим образом.
Программа:
Ввести у, п, eps. х1:=1
цикл-пока f(xl) > у х1:=х1/2
все-цикл
х2:=1
цикл-пока f(x2) < у х2 := х2/2
все-цикл
цикл-пока х2-х1 > eps xt:=(xl +х2)/2 если f(xt) > у
то х2 := xt иначе х1 := xt
все-если все-цикл
Вывести xt, у. Конец.
Таким образом, на каждом шаге решается одна достаточно простая за дача, что существенно облегчает разработку алгоритма и является основным достоинством метода пошаговой детализации.
При разработке алгоритма методом пошаговой детализации мы исполь зовали псевдокод, но можно было использовать и схемы алгоритма, в которых решение каждой подзадачи обозначено блоком «предопределенный процесс».
26
/. Этапы создания программного обеспечения
Задания для самопроверки
Задание 1. Разработайте алгоритм программы, определяющей первые 10 чисел последовательности Фибоначчи, которая формируется следующим образом:
Fi =р2= l,Fn = Fn.i +Fn.2»
где п > 2. Алгоритм представьте в виде схемы и запишите псевдокодом.
Задание 2. Разработайте алгоритм программы, которая определяет квадратный корень из числа А с точностью до целой части, учитывая, что сумма первых п нечет ных натуральных чисел равна п^:
1 = 12
I + 3 = 4 = 22 14-3 + 5 = 9 = 32
1 + 3 + 5 + 7 = 16 = 42 и т. д.
Алгоритм представьте в виде схемы и запишите псевдокодом.
2.ПРОСТЕЙШИЕ КОНСТРУКЦИИ ЯЗЫКА
кпростейшим конструкциям языка относятся способы представления скалярных данных, конструкции выражений, оператор присваивания и операторы ввода-вывода, без которых не обходится ни одна программа. Однако прежде чем рассматривать эти конст
рукции, выясним, что собой представляет язык программирования и каким образом
выполняется его описание.
2.1. Синтаксис и семантика языка программирования
Любой язык, в том числе и язык программирования, подчиняется ряду правил. Их принято разделять на правила, определяющие синтаксис языка, и правила, определяющие его семантику.
Синтаксис языка - совокупность правил, определяющих допустимые конструкции (слова, предложения) языка, его форму.
Семантика языка - совокупность правил, определяющих смысл синтак сически корректных конструкций языка, его содерэюание.
Языки программирования относятся к группе формальных языков, для которых в отличие от естественных языков однозначно определены синтак сис и семантика. Описание синтаксиса языка включает определение алфави та и правил построения различных конструкций языка из символов алфави та и более простых конструкций. Для этого обычно используют форму Бэку-
са-Наура (БНФ) или синтаксические диаграммы. Описание конструкции в
БНФ состоит из символов алфавита языка, названий более простых конст рукций и двух специальных знаков:
«::=» - читается как «может быть заменено на», «I» - читается как «или».
При этом символы алфавита языка, которые часто называют терминаль ными символами или терминалами, записывают в неизменном виде. Назва ния конструкций языка (нетерминальные символы или нетерминалы), опр деляемых через некоторые другие символы, при записи заключают в угловые скобки («< », « >»).
Например, правила построения конструкции <Целое>, записанные в БНФ, могут выглядеть следующим образом:
28
2. Простейшие конструкции языка
<Целое> ::= <3нак> <Целое без знака> | <Целое без знака>
<Целое без знака> ::= <Целое без знака> <Цифра> | <Цифра> <Цифра> ::= О I 1 I 2 I 3 I 4 I 5 I 6 I 7 I 8 I 9
<3нак> ::= + | -
Для отображения того, что конструкция <Целое без знака> может вклю чать неограниченное количество цифр, использовано правило с левосторон ней рекурсией. Многократное применение этого правила позволяет постро ить целое число с любым количеством цифр.
Синтаксические диаграммы отображают правила построения конструк ций в более наглядной форме. На такой диаграмме символы алфавита изоб ражают блоками в овальных рамках, названия конструкций - в прямоуголь ных, а правила построения конструкций - в виде линий со стрелками на кон цах. При этом, если линия входит в блок, то в описываемую конструкцию должен входить соответствующий символ. Разветвление линии означает, что при построении конструкции возможны варианты.
На рис. 2.1 представлена синтаксическая диаграмма, иллюстрирующая первые два правила описания конструкции <Целое>. Из диаграммы видно, что целое число может быть записано со знаком или без и включать произ вольное количество цифр.
Для описания синтаксических конструкций своего языка Н. Вирт ис пользовал именно синтаксические диаграммы, поэтому в тех случаях, когда словесное описание синтаксиса конструкции длинно и нечетко, мы будем ис пользовать синтаксические диаграммы.
Алфавит языка программирования Borland Pas<cal 7.0 включает:
• строчные, прописные буквы латинского алфавита (a..z, A..Z) и знак подчеркивания ( _ ), который также во многих случаях считается буквой; кроме того, существенно то, что строчные и прописные буквы не различают ся: а неотличимо отА^Ь-отВ и т. д.;
•цифры (0...9);
•специальные знаки, состоящие из одного и двух символов:
|
+ - * / = : <<>> [ ] |
|||
{ |
} ( |
) ^ |
@ |
$ # о |
<= |
>= |
:= |
(* |
*); |
• служебные слова (эти сочета ния считаются единым целым и их нельзя использовать в программе в другом качестве):
Цифра
^Знак"^ияк- W
Рис. 2.1. Синтаксическая диаграмма конструкции <Целое>
29
Часть 1. Основы алгоритмизации и процедурное программирование
absolute |
end |
inline |
procedure |
to |
and |
external |
interface |
program |
type |
array |
file |
interrupt |
public |
unit |
begin |
for |
label |
record |
until |
case |
forward |
mod |
repeat |
uses |
const |
fidnction |
nil |
set |
var |
div |
goto |
not |
shl |
while |
do |
if |
of |
shr |
with |
downto |
implementation |
or |
string |
xor |
else |
in |
private |
then |
|
|
Примечание. Обратите внимание, что рус |
Буква |
ские буквы в конструкциях языка использовать |
Буква |
нельзя. Они допускаются только при определении |
строковых и символьных данных. |
|
Цифра |
Из символов алфавита в соответст |
|
вии с правилами синтаксиса строят раз |
Рис. 2.2. Синтаксическая |
личные конструкции. Простейшей из них |
диафамма <Идентификатор> |
является конструкция <Идентификатор>. |
|
Эта конструкция используется во многих |
более сложных конструкциях для обозначения имен программных объектов (полей данных, процедур, функций и т. п.). В Borland Pascal идентификатор представляет собой последовательность букв латинского алфавита (включая символ подчеркивания) и цифр, которая обязательно начинается с буквы, на пример: аааа, Ь121, Parametral, _а и т. п. Синтаксическая диаграмма иденти фикатора приведена на рис. 2.2. Остальные конструкции будут рассмотрены в последующих разделах.
Семантику языка программирования закладывают в его компилятор. Та ким образом, синтаксически корректная программа, написанная на языке программирования, после преобразования ее в последовательность машин ных команд обеспечит выполнение компьютером требуемых операций.
2.2. Ст1^ктура программы
Программа на Borland Pascal состоит из трех частей: заголовка, раздела описаний и раздела операторов.
З а г о л о в о к программы не является обязательным, он состоит из слу жебного слова program и идентификатора - имени программы.
Р а з д е л |
о п и с а н и й содержит описания всех используемых про |
граммой ресурсов (полей данных, подпрограмм и т.д.). |
|
Р а з д е л |
о п е р а т о р о в заключается в так называемые оператор |
ные скобки begin ...end и заканчивается точкой. Между операторными скоб-
30