Структурированные схемы
Возрастающая сложность программ привлекает все большее внимание к проблемам технологии программирования. Технологические соображения заставили, в первую очередь, пересмотреть принципы организации программ, их структуру. Дейкстра первым высказался против неупорядоченного использования переходов на метки, которое может привести и фактически приводит к переусложнению структуры программы, затрудняющему ее понимание и декомпозицию на более простые фрагменты. Реализуя концепцию так называемого структурированного программирования, он предложил, отказаться от использования переходов и ограничиться более дисциплинирующими средствами управления вычислениями, такими, как условные операторы и операторы цикла.
Класс c труктурированных схем Y (S) определяется в том же (полном) базисе В, который был введен для ССП Y.
Различие между Y и Y (S) проявляется на уровне структур схем. Вместо специальных символов Y вводятся специальные символы: if, then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных оператора в базисе В: простой оператор, условный оператор и оператор цикла.
Простой оператор — это начальный (заключительный) оператор и оператор присваивания.
Условный оператор — это оператор вида
if p then s1 else s0 end,
где p — логическое выражение, s1, s0 — последовательности (может быть, пустые) операторов, среди которых нет ни начального, ни заключительного.
|
|
|
Операторы цикла имеют вид
while p do s end или until p do s end,
где p, s имеют тот же смысл, что и выше.
Ниже приведен пример эквивалентных схем Y и Y (S).
| Стандартная схема программ Y | Структурированная схема программ Y (S) |
| start(х), 1: y:= f (x), 2: if p (y) then7 else 3, 3: y:= f (y), 4: if p (y) then 5 else 7, 5: if p (x) then 6 else 7, 6: x:= h (x) goto 5, 7: stop(х, y). | start(х), y:= f (x), if p (y) thenelse y:= f (y), if p (x) then while p (x) do x:= h (x)end else end end, stop(х, y). |
Структурированные программы универсальны в том смысле, что набора предоставленных им средств достаточно для описания любой вычислимой функции. Задача автоматического преобразования стандартных схем в структурированные имеет отрицательное решение. Доказано, что класс Y мощнее класса Y (S), т.е. схемы Y (S) транслируемы в Y, но не наоборот.
Усилить класс Y (S) можно за счет усложнения логических выражений в условных операторах и операторах цикла Y (SL), введением символов логических операций NOT, OR, AND и атомарных формул, которыми являются логические выражения в старом смысле, например:
NOT p (x) AND q (y,x);
p (g (x, t)) OR q (h (x), x).
В этом случае справедлива
Теорема (Ашкрофт - Манн) Класс стандартных схем Y транслируем в класс схем с логическими операциями Y (SL).
Дата добавления: 2015-12-20; просмотров: 15; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!