Проектирование алгоритма обработки данных

Языки проектирования КП

Для описания процесса проектирования КП используются специализированные языки, называемые языками проектирования (Project Design Language - PDL). PDL в общем случае позволяет описывать проекты КП с точки зрения логики и без учёта специфики конкретной вычислительной системы и расположения программ и данных в физической памяти компьютера. Это не полностью формализованный язык; он обычно легко понимается, так как сохраняет особенности естественного языка. Он способствует установлению взаимопонимания между разработчиками программы и во многих случаях допускает почти прямую трансляцию на традиционные языки программирования.

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

Например, проект КП для решения задачи о выборе максимального из трех заданных чисел на языке PDL может выглядеть так:

Ввод исходных данных:

A ï < первое число >, B ï < второе число >, C ï < третье число >;

Обработка данных:

MAX ï max(A,B,C)

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

< Ответ >ï MAX

В этом тексте использованы в качестве ключевых слов конструкции “Ввод исходных данных с контролем”, “Вывод результатов:”, “Обработка данных:”, “ ï”, “<”, “>”.На естественном русском языке записан смысл вводимых и выводимых данных. Язык математики используется для формальной записи правил обработки данных: max(A,B,C).

PDL для проектирования структурированных компьютерных программ

методом пошагового уточнения

Существует несколько методов проектирования компьютерных программ, среди которых выделяются методы нисходящего ("сверху вниз" или Up-Down) и восходящего ("снизу вверх" или Down-Up) проектирования. Метод нисходящего проектирования называют также методом функциональной декомпозиции []. Ниже будет изложен этот метод, базирующийся на стратегии пошагового уточнения (Stepwise Refinement) и использующий при этом базовые управляющие структуры: ЛУЧ, ВЕТВЛЕНИЕ и ЦИКЛ, - применительно к проектированию КП.

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

Внешний синтаксис языка PDL, предназначенного для проектирования КП на каком-либо процедурном ЯП высокого уровня (целевом ЯП) методом пошагового уточнения, зависит от того, на каком именно ЯП должна быть написана эта КП. Эта зависимость выражается в виде ограничений на вид конструкций, которые разрешено использовать на шаге уточнения обобщённых операторов. Все ограничения входят в состав внешнего синтаксиса этого PDL.

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

По тексту такого проекта можно будет "собрать" текст КП на целевом ЯП, используя название КП как аксиому, а описания шагов уточнения - как правила вывода в построенной в ходе проектирования КС-грамматике. Терминальный словарь в этой грамматике состоит из цепочек основных символов целевого ЯП, а нетерминальный - из имён обобщённых операторов и имени проектируемой КП. Отметим особенности этой КС-грамматики, вытекающие из определения правила как описания шага уточнения:

§ каждый нетерминальный символ встречается в левой части одного и только одного правила,

§ аксиома не входит в правые части правил.

Если запретить рекурсию при уточнении, то получится, что построенная в ходе проектирования КС-грамматика порождает одну единственную цепочку терминальных символов, которая и является текстом проектируемой КП.

В качестве примера рассмотрим схемы правил PDL, предназначенного для проектирования КП на языке Паскаль. Ниже приводятся схемы записей шагов уточнения, использующие управляющие конструкции языка Паскаль. Всюду под нетерминалом <оператор> понимается либо оператор ЯП Паскаль, либо обобщенный оператор.

Схема ЛУЧ:

<имя обобщённого оператора> ® <оператор₁>[;<оператор₂>;…;<оператор_n>]

Схемы ВЕТВЛЕНИЕ:

<имя обобщённого оператора> ® if <условие> then <оператор>[ else <оператор>]

<имя обобщённого оператора> ® case <параметр выбора> of

<список₁ значений параметра>: <оператор₁>;

<список₂ значений параметра >: <оператор₂>;

…;

<список_n значений параметра >: <оператор_n>;

end

Схемы ЦИКЛ:

<обобщённый оператор> ® while <условие> do

until <условие>

<обобщённый оператор> ® for <параметр цикла>:= <начальное значение>

[ down ] to <конечное значение> [ by <шаг изменения параметра>] do

begin <оператор₁; оператор₂; …; оператор_n> end

Использование такого PDL при проектировании КП позволяет получить при "сборке" (порождении из аксиомы) структурированную КП [Хьюз и Мичтом, Йодан].