Формальная семантика goto и неструктурных программ.
Оператор goto не изменяет пользовательские переменные. В реальности goto изменяет системную переменную, счетчик команд, содержащую указатель (метку, имя, адрес) следующего в порядке выполнения оператора.
В терминах блок-схем goto – это просто стрелка.
Такая семантика даёт возможность точно определить семантику произвольных блок-схем. Пусть блок-схема B содержит n блоков S1,…,Sn. Неявно мы ввели нумерацию блоков (вместо индексов подошли бы любые иные указатели). Наша задача: построить структурную блок-схему, функционально эквивалентную данной.
Procedure StrucruredB ( );
var BlockName: tBlockName; {указатель на выполняемый блок}
bool:boolean;{значение текущего условного блока}
BlockEnd:tBlockName;{ещё один указатель на блок}
{этих переменных нет в исходной блок-схеме}
begin
BlockName:=cFirstBlockName;{указатель на кружок «Н»}
while BlockName<>cLastBlockName {указатель на кружок «К»}do
begin
{Разбор случаев – для каждого операторного блока два случая}
BlockName=ThisBlock : SThisBlock;
BlockName:=ThisBlockEnd;
BlockName=ThisBlockName : BlockName:=NextBlockName;
{метка оператора следующего блока}
{С каждым условным блоком связываем 3 случая}
BlockName=ThisBlock : Bool:=BThisBlock;
BlockName:=ThisBlockEnd;
BlockName=ThisBlockEnd and Bool=true : BlockName:=PlusBlockName;
{метка на блок, на который указывает стрелка + }
BlockName=ThisBlockName and Bool=false : BlockName:=MinusBlockName;
end;
end;
Данная программа пошагово эквивалентна исходной.
Наши рассуждения фактически доказывают более сильные утверждения:
1) Любая программа может быть записана с единственным циклом и единственным разбором случаев. Такая форма программы называется нормальной.
2) Этот переход можно осуществить алгоритмически – написать интерпретатор блок-схем, который по произвольной блок-схеме (для него – входные данные) исполняет алгоритм, описанный этой блок-схемой.
Procedure Structure(B:tFlowChart);
Упражнение*. Сделай это! ;)
В теории программирования этот результат называется теоремой об универсальной функции (теоремой о существовании компьютера).
Каковы же минимальные средства программирования? Сколько операторов, типов данных, переменных и так далее должен содержать язык программирования, чтобы на нём можно было написать любую программу?
Для прояснения этого вопроса создадим искусственный машинный язык с «паскалеобразным» синтаксисом.