Структурное программирование. Трассировка программы

Трассировка программы

Языки блок-схем

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

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

‘Маша’ состоит из 4-х букв.

В языке блок-схем для этого используют рамку, например:

y:=succ(x)

здесь через succ обозначена одноместная функция – следующий за x в естественном порядке натуральных чисел.

Способы определения функций

Наиболее очевидный способ такой конструкции – это композиция или суперпозиция функции, описывающая последовательность применения функций.

φ(x)=f(g(x))

Функция φ – результат композиции функций f и g.

Обозначение суперпозиции процедур в терминах блок-схем.

P₁ → P₂

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

Предикат – условие, определяемое как функция.

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

ение 1 неявно, до начала работы операторов программы.

Для выходных потоков определен оператор записи write(f,e), где e – некоторое выражение.

{f→<a₁, a₂, …, a_n>, e→X}

write(f,e)

{f→<a₂, …, a_n, X>}

Выходные потоки изменяют количество компонентов, в ходе выполнения программы. Такие типы данных называются динамическими.

Очевидно, в ходе выполнения вычислений согласно некоторой блок-схеме для каждого входного состояния S выбирается некоторая ветка блок-схемы, т.е. последовательность операторных блоков S₁, …, S_n. Последовательность значений S₁(S), S₂S₁(S), …, S_nS_n-1…S₁(S) называется трассой выполнения.

Понятие трассы используется для трассировки - проверки работы алгоритмов путем выписывания трассы для данного входного состояния.

x,y:=y,x

x:=X y:=Y

x:=x•y y:=x/y x:=x/y

z:=x x:=y y:=z

x:=x+y y:=x-y x:=x-y

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

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

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

Идея упростить язык блок-схем с помощью выделения небольшого числа операторных конструкций соответствующих удобным и знакомым схемам определения функций.

Структурный подход к программированию выделяет три операторных конструкции (структуры):

1. Композиция

Если S₁ и S₂ – допустимые блок-схемы, то S₁→ S₂ также допустима.

Структура полного условного оператора. Блок-схема – определение (процедуры вычисления) оператора, состоящая из

- операторных блоков в квадратах,

- предикатных блоков в ромбах,

- значков Н (начало вычисления), К (конец вычисления) и

- соединяющих их стрелок.

При этом в операторный блок могут входить несколько стрелок, а выходит единственная. В условный блок входит несколько стрелок, а выходит – две, помеченных знаками + и -, соответствующих значениям true и false. Из значка Н выходит единственная стрелка, не входит ни одна. В значок К входит единственная стрелка, не выходит ни одна.

Содержательная семантика. После выполнения операторного блока выполняется блок, на который указывает единственная выходящая из него стрелка. После выполнения условного блока выполняется блок, на который указывает стрелка, иначе – в зависимости от условий. Первым выполняется блок, на который указывает стрелка Н, последним блок К.

Дата добавления: 2014-01-07