9.4. Проектирование алгоритма обработки данных в кп для решения задачи (с использованием pdl)

Методика проектирования структурированной КП

Пусть K - класс задач, для решения которых предназначается проектируемая КП, а I - исполнитель этой КП. Проектирование алгоритма обработки данных в КП идёт по шагам.

На 0-ом шаге записывается нетерминал - <полное имя КП>. Под этим именем она будет фигурировать в среде программирования (будет известна исполнителю I):

<полное имя КП> ::= [<путь в файловой системе ОС>]<идентификатор КП>[.<расширение>]

Идентификатор КП проектировщик должен подобрать таким, чтобы он соответствовал главной функции, выполняемой КП. Нетерминал <полное имя КП> будет являться аксиомой той КС-грамматики, которую будет строить проектировщик в качестве проекта КП. После этого 0-го шага множество N₀ нетерминалов определяется как {<полное имя КП>}, а множество P₀ правил этой грамматики - как пустое множество.

На первом шаге происходит декомпозиция главной функции КП: выбирается подходящая управляющая структура для выделения основных подфункций и определения порядка их выполнения. После этого первый шаг уточнения записывается в виде правила, в левой части которого стоит аксиома (нетерминал <полное имя КП>), а правая имеет вид подобранной проектировщиком управляющей структуры ЯП. В эту структуру в качестве операторов проектировщик вставляет либо операторы языка программирования, либо нетерминалы, соответствующие подфункциям, выделенным проектировщиком при уточнении главной функции КП (обобщенные операторы). Множество нетерминалов N₁ определяется после первого шага как результат добавления к множеству N₀ всех вновь введённых нетерминалов, а множество P₁ правил этой грамматики будет состоять из одного правила - описания первого шага уточнения.

После очередного, k-ого, шага проектировщик уже имеет аксиому и множество P_k описаний шагов детализации в виде правил КС-грамматики (P_k состоит из k правил).

Проектировщик должен проанализировать множество нетерминалов N_k, состоящее из аксиомы и всех нетерминалов (имён обобщённых операторов), входящих в правые части этих k правил.

Если во множестве N_k существует хотя бы один нетерминал, не являющийся левой частью ни одного из этих правил ("непродетализированный" обобщённый оператор), то проектировщик должен построить ещё одно, (k+1)-ое, правило. Его левой частью должен стать один из вышеупомянутых нетерминалов (обобщённый оператор), а правой частью - цепочка из терминалов и нетерминалов, уточняющая этот обобщённый оператор. Эта цепочка - одна из управляющих конструкций языка программирования, составленная из нетерминалов (имён обобщённых операторов, не являющихся операторами ЯП) и терминалов - лексем ЯП. После этого шага множество правил P_k+1 определится как результат объединения множества P_k с вновь построенным правилом, а множество нетерминалов N_k+1 - как результат объединения множества N_k с множеством всех нетерминалов, входящих в правую часть правила, построенного на этом шаге.

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

Примечание. Проектировщик может досрочно прекратить процесс проектирования в тот момент, когда он примет решение о замене всех не уточненных до сих пор нетерминалов на вызовы соответствующих процедур (или функций). Проектирование этих процедур и/или функций здесь производиться не будет: оно откладывается "на потом" или заменяется непосредственным кодированием соответствующего обобщённого оператора (на основе его спецификации).

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

5. Пример Проектирования алгоритма обработки данных в КП для решения задачи о выборе максимального из трех чисел

Продемонстрируем процесс проектирования КП на примере составления проекта КП для решения задачи о выборе максимального из трех заданных чисел. Будем исходить из спецификации этой КП, приведенной выше (см. п. 6.1.7).

В соответствии с методикой проектирования КП путем пошаговой детализации на нулевом шаге введем имя проектируемой КП – MAX_FROM_3.

В результате выполнения нулевого шага N₀ = { MAX_FROM_3}, а P₀ = .

На первом шаге выберем для детализации схему ЛУЧ:

p₁: MAX_FROM_3 <ввод исходных данных с контролем>; <поиск максимума>; <вывод результата>

В результате выполнения этого шага N₁ = { MAX_FROM_3, <ввод исходных данных с контролем>, <поиск максимума>, <вывод результата>}, а P₁ = { p₁ }. Теперь надо выбрать для детализации какой-либо нетерминал из множества N₁. Пусть это будет <ввод исходных данных с контролем >.

На втором шаге для детализации снова выберем схему ЛУЧ – в соответствии со спецификацией задачи в п.6.1.7:

p₂: <ввод исходных данных с контролем> <ввод A с контролем>; <ввод B с контролем>; <ввод C с контролем> .

В результате второго шага N₂ = N ₁ { <ввод A с контролем>, <ввод B с контролем>, <ввод C с контролем> }, а P₂ = { p₁, p₂ }.

Для третьего шага детализации выберем нетерминал <ввод A с контролем> и схему ЛУЧ:

p₃: <ввод A с контролем > Writeln (“Введите первое число”, G); Readln (G);

Writeln (“ А = ”, G); <контроль введенного данного>; A := G;

После этого N₃ = N₂ <контроль введенного данного>, P₃ = { p₁, p₂, p₃ }. Аналогично выполним следующие два шага детализации:

p₄: <ввод B с контролем > Writeln (“Введите второе число”, G); Readln (G);

Writeln (“ B = ”, G); <контроль введенного данного>; B := G;

p₅: <ввод C с контролем > Writeln (“Введите третье число”, G); Readln (G);

Writeln (“ C = ”, G); <контроль введенного данного>; C := G;

в результате выполнения которых N₅ = N₃ , а P₅ = { p₁, p₂, p₃, p₄, p₅ }.

На очередном шаге детализации выберем подходящую управляющую структуру для нетерминала <вывод результата> - это ЛУЧ, который в этом случае состоит из одного оператора:

p₆: <вывод результата> Writeln (“A = ”, A, “B = ”, B, “C = ”, C, “ Самое большое число - ”, MAX, “ .”) .

Теперь N₆ = N ₂ , а P₆ = { p₁, p₂, p₃, p₄, p₅, p₆}.

К этому моменту остался “непродетализированный” нетерминал <поиск максимума>. В соответствии со спецификацией задачи продетализируем его по схеме ЛУЧ:

p₇: <поиск максимума> <максимум из двух>; <максимум из трех> ,

в результате чего получим N₇ = N₂ {<максимум из двух>, <максимум из трех>}, а P₇ = { p₁, p₂, p₃, p₄, p₅, p₆, p₇}.

Для детализации двух возникших на этом шаге нетерминалов понадобится схема ВЕТВЛЕНИЕ:

p₈: < максимум из двух >

if A > B then Begin MAX := A; Writeln (“Первое число не меньше второго.”) end

else Begin MAX := B; Writeln (“Второе число больше первого.”) end

p₉: < максимум из трех > if MAX < C then MAX := C;

После девятого шага N₉ = N₇ , а P₉ = { p₁, p₂, p₃, p₄, p₅, p₆, p₇, p₈, p₉ }. Теперь остался только один “непродетализированный” нетерминал - <контроль введенного данного>. Для его детализации используем схему ЦИКЛ (с предусловием):

P₁₀: <контроль введенного данного> while G < 0 OR G > 65535 do

Begin

<диагностическое сообщение об ошибке ввода>;

Writeln (“Повторите ввод!”); Readln (G);

Writeln (“Теперь Вы ввели ”, G);

end

После десятого шага N₁₀ = N₇ <диагностическое сообщение об ошибке ввода>, а P₁₀ = { p₁, p₂, p₃, p₄, p₅, p₆, p₇, p₈, p₉, p₁₀ }.

Для детализации последнего нетерминала используем схему ВЕТВЛЕНИЕ:

P₁₁: <диагностическое сообщение об ошибке ввода> if G > 99999

then Writeln (“Количество цифр во вводимом числе не должно быть больше 5.”)

else Writeln (“Вводимое число должно быть неотрицательным

и не должно превышать 65535.”)

Теперь N₁₁= N₁₀, а P₁₁ = { p₁, p₂, p₃, p₄, p₅, p₆, p₇, p₈, p₉, p₁₀ , p₁₁ }.

Проектирование завершено. Тем самым построена КС-грамматика, в которой терминальные символы – это символы языка Паскаль, множество нетерминальных символов N = N₁₁, аксиома - MAX_FROM_3, а множество правил P = P₁₁.