1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 9
Текст из файла (страница 9)
ь модпли вычислении в точности роль транслятора с Упрощенного Алгола. Нас, однако, не будут интересовать детали перевода Упрощенного Алгола в конкретные программы для РАМ или РАСП. Для наших целей нужно рассматривать лишь время и память, необходимые для выполнения команд, соответствующих операторам иа Упрощенном Алголе. Упрощенный Алгол отличается от всех принятых языков программирования тем, что он разрешает использовать любой тнп математических предписаний, если только их значения понятны, а перевод в команды РАМ или РАСП очевиден. Этот язык не имеет также фиксированного набора типов данных. Переменные могут представлять целые числа, слова и массивы.
Дополнительные типы данных — множества, графы, списки, очереди и т. п. — можно вводить по мере необходимости, Формальные описания типов данных по возможности избегаются. Тип данных какой-то переменной и ее область действия ') должны быть ясны либо по ее названию, либо по контексту. В Упрощенном Алголе применяются традиционные конструкции математики и языков программирования, такие, как выражения, условия, операторы и процедуры. Ниже приведены неформальные описания некоторых из этих конструкций. Никаких попыток дать точное определение не делается, ибо это выходит далеко за рамки тематики данной книги. Заметим, что легко написать программы, смысл которых зависит от деталей, не рассмотренных здесь, но лучше избегать этого, что мы и проделали (мы надеемся) в нашей книге.
Программа на Упрощенном Алголе — это оператор одного из следующих типов: 1) переменная — выражение 2) !! условие !!теп оператор е!зе оператор ') За)тяЫ!е условие з!о оператор Зб) гереа! оператор цпИ! условие 4) !ог переменная ч- исходное значение з1ер размер шага *) ппИ! заключительное значение с!о оператор 5) метка: оператор 6) яо1о метка 7) Ьея!и оператор; оператор; ') Область действия переменной — зто окружение, в котором опа осмыслена.
Например, областью действия индекса суммирования является выражеепе, стоящее под зкаком суммы, я вке его ок пе имеет значения. з) Часть че!зе оператор» ве обязательна. Но такой вариант приводит к обычкой двусмысленности типа «кепрявязапкое еием Мы выбираем традиционный путь к предполагаем, что е!зе спаривается с ближайшим еще ке спаренным Шеп. '! Часть епер размер шагал яе обязательна, если размер шага равен К 4й |.В ЯЗЫК ВЪ|СОКОГО УРОВНЯ вЂ” УПРОЩВННЪ|Г| АЛГОЛ оператор; оператор еп4 8а) ргоседцге имя (список параметров): оператор 8б) ге1пгп выражение 8в) имя процедуры (аргументы) 9а) ген переменная 9б) мт!1е выражение !О) сопппеп1 комментарий 1!) любой другой произвольный оператор Дадим обзор каждого из этих операторов.
!. Оператор присваивания переменная выражение означает, что надо вычислить выражение справа от стрелки и его значение присвоить переменной, стоящей слева от стрелки. Временная сложность оператора присваивания определяется временем, затрачиваемым на вычисление значения выражения и присваивание этого значения переменной. Если значение выражения не принадлежит к данным основного типа, таким как целые числа, то в некоторых случаях можно уменьшить время с помощью указателей.
Например, присваивание А В, где А и  — матрицы размера пхп, обычно потребовало бы 0(п') шагов. Но если В больше нигде не встречается, то путем простого переименования массива можно сделать это время фиксированным, не зависящим от а. 2. В И-операторе И условие 1(|еп оператор е!Ве оператор условием, следующим за И, может быть любое выражение, принимающее значение 1гце или 1а)зе. Если это условие имеет значение 1гце, то надо выполнять оператор, стоящий за 1(зеп.
В противном случае надо выполнять оператор, стоящий за е(зе (если еЬе есть). Вес И-оператора равен сумме весов, требуемых для вычисления значения и проверки его, и веса оператора, стоящего сразу за 1(|еп, или оператора, стоящего за е!Ве, в зависимости от того, какой из них выполнялся на самом деле. 3. Назначение е(|(!е-оператора тт(|Ие условие до оператор и гереа1-оператора гереа1 оператор пп1!! условие ГЛ. Ь МОДЕЛИ ВЫЧИСЛЕНИИ состоит в организации цикла. В «~Ы!е-операторе вычисляется значение условия, идущего после вИ!е. Если оно истинно (принимает значение 1гпе), то выполняется оператор, стоящий после до.
Этот процесс повторяется до тех пор, пока условие ие станет ложным. Если вначале это условие было истинным, то выполнение оператора должно в конце концов привести это условие к значению 1а!зе, чтобы закончилось выполнение вп(1е-оператора. Для вычисления веса «п!(е-оператора суммируются веса всех проверок условия и всех выполненных операторов.
гереа1-оператор трактуется аналогично, но только теперь оператор, стоящий за гереа1, выполняется перед проверкой условия. 4. В 1ог-операторе 1ог переменная исходное значение з!ер размер шага цп111 заключительное значение до оператор "исходное значение", "размер шага*' и "заключительное значение" являются выражениями. В случае когда размер шага положителен, "переменная" (называемая индексом) полагается равной значению выражения для исходного значения.
Если оно больше заключительного значения, то выполнение оператора заканчивается. В противном случае выполняется оператор, стоящий после 4о, значение переменной увеличивается на величину шага и сравнивается с заключительным значением. Процесс повторяется до тех пор, пока значение переменной не превзойдет заключительное значение. Случай, когда размер шага отрицателен, трактуется аналогично с той лишь разницей, что окончание происходит, когда значение переменной становится меньше заключительного значения.
Вес 1ог-оператора должен быть очевиден в свете предшествующего анализа яй!1е-оператора. В приведенном описании совершенно игнорируется такая деталь, как момент вычисления выражений для исходного значения, размера шага и заключительного значения. Может случиться, что выполнение оператора, стоящего после до, изменяет значение выражения для размера шага. В таком случае вычисление значения выражения для размера шага каждый раз, когда переменная возрастает, может привести к результату, отличному от того, который получился бы, если бы размер шага вычислялся раз и навсегда.
Точно так же вычисление размера шага может воздействовать на заключительное значение, а изменение размера шага может повлиять на тест на окончание. Мы обходим эти трудности, отказываясь от программ, в которых подобные явления сделали бы их смысл неясным. 5. Любой оператор можно переделать в помеченный оператор, написав перед ним метку, за которой стоит двоеточие. Главное назначение метки — создание цели для до1о-оператора. Меткам не приписывается никакого веса. ье язык высокого гговня — гпгощеннын хлгол б.
до!о-оператор по(о метка указывает, что дальше выполняется оператор с данной меткой. Этот оператор не может стоять внутри блока типа 7, если сам по(ооператор не находится в том же блоке. Вес по!о-оператора равен 1. ао!о-операторы следует применять изредка, ибо, вообще говоря, они затрудняют понимание программы. Основное применение но!о-оператора — это выход из и Ь!!е-операторов. 7. Последовательность операторов, отделенных друг от друга точками с запятыми и заключенных между выделенными словами Ьед!п и епд, образует оператор, который называется блоком.
Так как блок является оператором, его можно применять всюду, где предусмотрено применение оператора. Обычно программа будет блоком. Вес блока равен сумме весов операторов, составляющих блок. 8. Процедуры. В Упрощенном Алголе процедуры можно определять и впоследствии вызывать. Процедуры определяются оператором определения процедур ргоседпге имя (список параметров): оператор Список параметров — это последовательность фиктивных переменных, называемых формальными параметрами.
Например, следующий оператор определяет процедуру-функцию М11ч: ргоседпге М1)ч (х, у): !! к ) у !Ьеп ге!цгп у е!зе ге!пгп х Аргументы х и у являются формальными параметрами. Процедуры используются одним из двух способов. Один способ — в качестве функции. После того как процедура-функция описана, к ней можно обратиться в некотором выражении, вызывая ее имя с нужными аргументами. В этом случае последним оператором, выполняемым в данной процедуре, должен быть ге!нгп-оператор (8б). Этот оператор приводит к вычислению значения выражения, следующего за выделенным словом ге!пгп, и окончанию выполнения процедуры. Значением функциибудет значение этого выражения. Например, А М1Х(2+3, 7) приводит к тому, что А получает значение 5. Выражения 2+3 и 7 называются фактическими параметрами этого обращения к данной процедуре.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
