Метод последовательной детализации (2)

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

 

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

Вернемся к задаче «Интерпретатор», которая рассматривалась в разд. 3.16. Напомним условие: дана исходная символьная строка, имеющая следующий вид:

а b=

На месте а и b стоят десятичные цифры; значком

обозначен один из знаков операций: +, -, *. Нужно, чтобы машина вычислила это выражение и после знака = вывела результат. Операция деления не рассматривается для того, чтобы иметь дело только с целыми числами.

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

1. Операнды а и b могут быть многозначными целыми положительными числами в пределах MaxInt.

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

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

4. Проводится семантический контроль: строка должна быть построена по схеме а

b =. Ошибка, если какой-то элемент отсутствует или нарушен их порядок.

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

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

1. Ввод строки.

2. Синтаксический контроль (нет ли недопустимых символов?).

3. Семантический контроль (правильно ли построено выражение?).

4. Выделение операндов. Проверка операндов на допустимый диапазон значений. Перевод в целые числа.

5. Выполнение операции. Проверка результата на допустимый диапазон.

6. Вывод результата.

Этапы 2, 3, 4, 5 будем рассматривать как подзадачи первого уровня, назвав их (и будущие подпрограммы) соответственно Sintax, Semantika, Operand, Calc

В свою очередь, для их реализации потребуется решение следующих подзадач: пропуск лишних пробелов (Propusk), преобразование символьной цифры в целое число (Cifra). Кроме того, при выделении операндов понадобится распознавать операнд, превышающий максимально допустимое значение (Error). Обобщая все сказанное в схематической форме, получаем некоторую структуру подзадач. Этой структуре будет соответствовать аналогичная структура программных модулей (рис. 49).

 

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

Обратите внимание на то, что функция Error определена как внутренняя в процедуре Operand. Это объясняется тем, что указанная функция используется только в данной процедуре. Другим программным модулям она «не нужна».

Окончательно объединив тексты подпрограмм с основной программой, получаем рабочий вариант программы Interpretator. Теперь ее можно вводить в компьютер.

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

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

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

п. Это ошибки времени исполнения. Они приводят к прерыванию выполнения программы. Как правило, имеются системные программные средства, помогающие в поиске таких ошибок.

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

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

 

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