Формальная семантика goto и неструктурных программ

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

В терминах блок-схем goto – это просто стрелка.

Такая семантика даёт возможность точно определить семантику произвольных блок-схем. Пусть блок-схема B содержит n блоков S₁,…,S_n. Неявно мы ввели нумерацию блоков (вместо индексов подошли бы любые иные указатели). Наша задача: построить структурную блок-схему, функционально эквивалентную данной.

Procedure StrucruredB ();

var BlockName: tBlockName; {указатель на выполняемый блок}

bool:boolean;{значение текущего условного блока}

BlockEnd:tBlockName;{ещё один указатель на блок}

{этих переменных нет в исходной блок-схеме}

begin

BlockName:=cFirstBlockName;{указатель на кружок «Н»}

while BlockName<>cLastBlockName {указатель на кружок «К»}do

begin

{Разбор случаев – для каждого операторного блока два случая}

BlockName=ThisBlock: S_ThisBlock;

BlockName:=ThisBlockEnd;

BlockName=ThisBlockName: BlockName:=NextBlockName;

{метка оператора следующего блока}

{С каждым условным блоком связываем 3 случая}

BlockName=ThisBlock: Bool:=B_ThisBlock;

BlockName:=ThisBlockEnd;

BlockName=ThisBlockEnd and Bool=true: BlockName:=PlusBlockName;

{метка на блок, на который указывает стрелка + }

BlockName=ThisBlockName and Bool=false: BlockName:=MinusBlockName;

end;

end;

Данная программа пошагово эквивалентна исходной.

Наши рассуждения фактически доказывают более сильные утверждения:

1) Любая программа может быть записана с единственным циклом и единственным разбором случаев. Такая форма программы называется нормальной.

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

Procedure Structure(B:tFlowChart);

Упражнение ^*. Сделай это!;)

В теории программирования этот результат называется теоремой об универсальной функции (теоремой о существовании компьютера).

Каковы же минимальные средства программирования? Сколько операторов, типов данных, переменных и так далее должен содержать язык программирования, чтобы на нём можно было написать любую программу?

Для прояснения этого вопроса создадим искусственный машинный язык с «паскалеобразным» синтаксисом.

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