1611678431-0e68e83522cb9d960ac896aa5d90854d (826635), страница 17

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 17)

else...) и оператор выбора (case).Во-вторых, оператор выбора не допускает умолчаний, что помогает при разработке сложных программ,так как каждая альтернатива представлена подробно, и возможность что-либо упустить уменьшается.В-третьих, благодаря отсутствию умолчаний, запись оператора выбора представлена в симметричномвиде.Оператор цикла имеет вид: do B → S do.Обозначим это соотношение через DO и представим его в следующем виде:DO : do B1  S1  B2  S2    Bn  Sn od ,где n  0 , Bi  Si - охраняемые команды.Пока возможно выбирается охрана Bi со значением истина, и выполняется соответствующий операторSi . Как только все охраны будут иметь значение ложь, выполнение DO завершится.Выбор охраны со значением истина и выполнение соответствующего оператора называетсявыполнением шага цикла. Если истинными являются несколько охран, то выбирается любая из них.Следовательно, оператор DO эквивалентен операторуdo BB  if B1  S1  B2  S2  Bn  Sn fi od или do BB  IF od,где BB - дизъюнкция охран, IF - оператор выбора.Пример.

Алгоритм Евклида.Вариант 1.задать  N , M  ;if N  0 AND M  0  n, m : N , M ;do n  m  if n  m  n : n – m  m  n  m : m – n fi od;выдать  n fiВариант 2.задать  N , M  ;if N  0 AND M  0  n, m : N , M ;do n  m  n : n – m  m  n  m : m – n od;выдать  n fiПусть предикат H 0  R  определяет множество состояний, в которых выполнение DO завершается за0 шагов (в этом случае все охраны с самого начала ложны, после завершения R имеет значение истина):H 0  R   NOT BB AND R .Чтобы оператор цикла DO завершил работу, не производя выборки охраняемой команды,необходимо, чтобы NOT BB  T .

При этом истинность R до выполнения DO является необходимым условиемдля истинности R после выполнения DO .Определим предикат H k  R  как множество состояний, в которых выполнение DO заканчивается за kшагов при значении R истина ( H k  R  будет определяться через H k 1  R  ):H k  R   H 0  R  OR wp IF, H k 1  R  , k  0  wp  DO, R   k : k  0 : H k  R  .Это значит, что должно существовать такое значение k , что потребуется не более чем k шагов, дляобеспечения завершения работы в конечном состоянии, удовлетворяющем постусловию R .Теорема инвариантности для оператора цикла.

Пусть оператор выбора IF и предикат P таковы, чтодля всех состояний справедливо P AND BB   wp  IF, R  .Тогда для оператора цикла справедливо: P AND wp  DO, T    wp  DO, P AND NOT BB  .Предикат P , истинный перед выполнением и после выполнения каждого шага цикла, называетсяинвариантным отношением или просто инвариантом цикла.Это условие означает, что если предикат P первоначально истинен и одна из охраняемых командвыбирается для выполнения, то после ее выполнения P сохранит значение истинности. После завершенияоператора, когда ни одна из охран не является истиной, будем иметь:P AND NOT BB .Работа завершится правильно, если условие wp  DO, T  справедливо и до выполнения DO .

Так каклюбое состояние удовлетворяет T, то wp  DO, T  является слабейшим предусловием для начального состояниятакого, что запуск оператора цикла DO приведет к правильно завершаемой работе.При определении семантики полного языка программирования с использованием аксиоматическогометода для каждого вида операторов языка должны быть сформулированы аксиома или правило логическоговывода. Но определение аксиом и правил логического вывода для некоторых операторов языковпрограммирования - очень сложная задача. Трудно построить «множество основных аксиом, достаточноограниченное для того, чтобы избежать противоречий, но достаточно богатое для того, чтобы служитьотправной точкой для доказательства утверждений о программах» (Э. Дейкстра).Решением такой проблемы является разработка языка, использующего аксиоматического метода,т.

е. содержащей только те операторы, для которых могут быть написаны аксиомы или правила логическоговывода. К сожалению, подобный язык оказался бы слишком маленьким и простым что отражает нынешнеесостояние аксиоматической семантики как науки.Аксиоматическая семантика является мощным инструментом для исследований в областидоказательств правильности программ, она также создает великолепную основу для анализа программ, как вовремя их создания, так и позднее. Однако ее полезность при описании содержания языков программированиявесьма ограничена как для пользователей языка, так и для разработчиков компиляторов.2.4 Денотационная семантикаДенотационная семантика — самый строгий широко известный метод описания значения программ.Она опирается на теорию рекурсивных функций.Основной концепцией денотационной семантики является определение для каждой сущности языканекоего математического объекта и некоей функции, отображающей экземпляры этой сущности в экземплярыэтого математического объекта.

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

Название метода«денотационная семантика» происходит от английского слова denote (обозначать), поскольку математическийобъект обозначает смысл соответствующей синтаксической сущности.Для введения в денотационный метод мы используем очень простую языковую конструкцию —двоичные числа. Синтаксис этих чисел можно описать следующими грамматическими правилами:двоичное_число  01двоичное_число 0двоичное_число 1Для описания двоичных чисел с использованием денотационной семантики и грамматических правил,указанных выше, их фактическое значение связывается с каждым правилом, имеющим в своей правой частиодин терминальный символ.

Объектами в данном случае являются десятичные числа.В примере значащие объекты должны связываться с первыми двумя правилами. Остальные дваправила являются правилами вычислений, поскольку они объединяют терминальный символ, с которым можетассоциироваться объект, с нетерминальным, который может представлять собой некоторую конструкцию.Пусть область определения семантических значений объектов представляет собой множествонеотрицательных десятичных целых чисел Nat . Это именно те объекты, которые мы хотим связать с двоичнымичислами. Семантическая функция M b отображает синтаксические объекты в объекты множества N согласноуказанным выше правилам. Сама функция M b определяется следующим образом:M b  '0 '  0, M b  '1'   1M b  двоичное_число '0 '   2  M b  двоичное_число M b  двоичное_число '1'   2  M b  двоичное_число   1Пример.

Описание значения десятичных синтаксических литеральных констант.десятичное_число  0 1 2 3 4 5 6 7 8 | 9десятичное_число 0 1 2 3 4 5 6 7 8 | 9Денотационные отображения для этих синтаксических правил имеют следующий вид:M d  '0 '  0, M d  '1'   1,  , M d  '9 '   9M d  десятичное_число '0 '   10  M d  десятичное_числоM d  десятичное_число '1'   10  M b  десятичное_число   1M d  десятичное_число '1'   10  M b  десятичное_число   9Денотационную семантику программы можно определить в терминах изменений состояний идеальногокомпьютера. Состояния определяются в терминах значений всех переменных, объявленных в программе. Вденотационной семантике они определяются строгими математическими функциями.

Пусть состояние sпрограммы определяется следующим набором упорядоченных пар:  i1 , v1 , i2 , v2 ,  , in , vn  .Каждый параметр i является именем переменной, а соответствующие параметры v являютсятекущими значениями данных переменных. Любой из параметров v может иметь специальное значение undef,указывающее, что связанная с ним величина в данный момент не определена.Пусть VARMAP - функция двух параметров, имени переменной и состояния программы. Значениефункции VARMAP  ik , s  равно vk (значение, соответствующее параметру ik в состоянии s ).Большинство семантических функций отображения для программ и программных конструкцийотображают состояния в состояния. Эти изменения состояний используются для определения смысла программи программных конструкций.Выражения являются основой большинства языков программирования.

Пусть имеем дело только сочень простыми выражениями. Единственными операторами являются операторы + и  ; выражения могутсодержать не более одного оператора; единственными операндами являются скалярные переменные ицелочисленные литеральные константы; круглые скобки не используются; значение выражения является целымчислом. Ниже следует описание этих выражений в форме БНФ:выражение  деятичное_числопеременнаядвоичное_выражениедвоичное_выражение  выражение_слева операторвыражение_справаоператор   Единственной рассматриваемой ошибкой в выражениях является неопределенное значениепеременной. Разумеется, могут появляться и другие ошибки, но большинство из них зависят от машины.

ПустьZ - набор целых чисел, a error - ошибочное значение. Тогда множество Z  error является множествомзначений, для которых выражение может быть вычислено.Функция отображения для данного выражения E и состояния s приведена ниже. Символ обозначает равенство по определению функции.M E  выражение , s  case выражение ofдесятичное_число  M в  десятичное_число , s переменная  if VARMAP  переменная , s   undefthen errorelse VARMAP  переменная , s двоичное_выражение if ( M E  двоичное_выражение . выражение_слева , s   undef ORM E  двоичное_выражение . выражение_справа , s   undef )then errorelse if ( M E  двоичное_выражение .

оператор , s   ' ' thenM E  двоичное_выражение . выражение_слева , s  M E  двоичное_выражение . выражение_справа , s else M E  двоичное_выражение . выражение_слева , s  M E  двоичное_выражение . выражение_справа , s Оператор присваивания - это вычисление выражения плюс присваивание его значения переменной,находящейся в левой части. Его можно описать следующей функцией:M A  x  E   if M E  E , s   errorthen erroresle  i1, v1 , i2 , v2 ,, in , vn  wherefor j  1, 2,  , n, v j  VARMAP i j , s if i j  xM E  E , s  if i j  x Сравнения, выполняющиеся в строках  i j  x и i j  x  относятся к именам, а не значениям.После определения полной системы для заданного языка ее можно использовать для определениясмысла полных программ этого языка.Денотационная семантика может использоваться для разработки языка.

Операторы, описать которые спомощью денотационной семантики трудно, могут оказаться сложными и для понимания пользователямиязыка, и тогда разработчику следует подумать об альтернативной конструкции.С одной стороны, денотационные описания очень сложны, с другой - они дают великолепный методкраткого описания языка.34, 35. Линейные списки и способы их реализации, операции вставки и удаления. (35)Основные операции со списками. Однонаправленные, двунаправленные и циклические спискиЛекции: фото 30, 31, 32Связные списки представляют собой (как уже было сказано) динамические (фактически,линейные!) структуры данных (динамические цепочки звеньев), в которых однотипные элементы(звенья) каким-либо образом связаны между собой, обычно на физическом уровне.

Характеристики

Список файлов ответов (шпаргалок)