Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 44
Текст из файла (страница 44)
Если предположить, что процесс вычисления проходит вверх по дереву синтаксического анализа, то нетерминальный символ, находящийся в правой части, уже имел бы приписанное ему значение. В таком случае синтаксическое правило потребовало бы наличия функции, вычислившей значение левой части правила, которое, в свою очередь, представляет собой значение всей правой части. 163 З.б.
Описание смысла враграмм: динамическая семантика Пусть область определения семантических значений объектов представляет собой множество неотрицательных десятичных целых чисел Х. Это именно те объекты, которые мы хотим связать с лвоичными числами. Семантическая функция Мь,„отображает синтаксические объекты в объекты множества Х согласно указанным выше грамматическим правилам. Сама функция Ми„опрелеляется слелуюшим образом: Ми„(0)=0 Мьы( ! ) Мы„(<двоичное число> '0') = 2 ' Мъ„(<двоичное число>) Мь,„(<двоичное число> '1') = +2 ' Мъ„(<двоичное число>) + 1 Отметим.
что мы заключилн синтаксические цифры в апострофы, чтобы отличать их от математических цифр. Отношение между этими категориялчи подобно отношениям между цифрами в кодировке АБС!! и математическими цифрами. Когда программа считывает число как строку, то прежде, чем это число сможет использоваться в проврамме, оно должно быть преобразовано в математическое число. Значения, или обозначенные объекты (которыми в паннам случае являются десятичные числа), могут быть приписаны к узлам указанного выше дерева синтаксического анализа, образуя дерево, показанное на рис. 3.11. Это — синтаксически управляемая семантика. Синтаксические сущности отображаются в математические объекты, имеюшие конкретное значение.
6 <двоичное чисвоз ~ ! ! Рис. 3.П. Дерево синтаксического анапы за числа I /О с обозначенными абъектиии Приведем подобный пример лля описания значения десятичных синтаксических лнтерачьных констант, который поналобится нам в дальнейшем, <десятичное число>еО!1!2!3!4!5!6!7!8!9 ! <десятичное число>( 0 1 1 !2 ! 3 ! 4 ! 5 ! 6 ! 7 ! 8 ! 9) Денотационные отображения для этих синтаксических правил имеют следующий вид: Меч('0')=О,Ме.с('1'),Мвчс('2',",Ми~с('9') 9 Мв (<десятичное число> '0') = 10' Мв (<двончное число>) Мв„,(<десятичное число> '1') = 1О ' Мв «десятичное число>) + 1 Мв„(<десятичное число> '9') = 10 ' Мв„(<десятичное число") + 9 Глава 3.
Описание синтаксиса и семантики В слелующих разлелах мы прелставим ленотационные семантики лля нескольких простых конструкций. Важнейшил1 слеланным злесь упрощением является прелположение о том, что и синтаксис. и семантика конструкщай корректны. Помимо этого, предполагается, что существует только два скалярных типа — целый и булевскиИ. 3.6.3.2. Состояние программы Денотационную семантику программы можно опрелелить в терминах изменений состояния идеального компьютера. Подобным образом определялись операционные семантики. приблизительно так же определяются и денотационные.
Правда. лля простоты они определяются только в терминах значений всех переменных. объявленных в программе. Операционная и ленотационная семантики различаются тем. что изменения состояний в операционной семантике определяются запрограммироваиньв|и алгоритмами, а в денотационной семантике они определяются строгими математическими функциями. Пусть состояние з программы определяется следующим набором упорядоченных пар: (<Б, т~>, <ьл тз>, ..., <(„, ч„>( Каждый параметр ~ является именем переменной, а соответствующие параметры ч являются текущими значениями данных переменных. Любой из параметров т может иметь специальное значение нибеГ, указывающее, что связанная с ним величина в данный момент не определена.
Пусть ЧАИМАР— функция двух параметров, имени переменной и состояния программы. Значение функции ЧАИМАР((л з) равно т; (значение, соответствующее параметру 1> в состоянии з). Большинство семантических функциИ отображения для программ и программных конструкций отображают состояния в состояния. Эти изменения состояний используются для определения смысла программ и программных конструкций. Отметим, что такие языковые конструкции, как выражения, отображаются не в состояния, а в величины. 3.6.3.3. Выражения Выражения являются основой большинства языков программирования и не имеют побочных эффектов. Более того, мы имеем дело только с очень простыми выражениями. Единственными операторами являются операторы + и ', выражения ма~уз солержать не более одного оператора; единственными операнлами являются скалярные переменные и целочисленные литеральные константы; круглые скобки не используются; значение выражения является целым числом.
Ниже слелует описание этих выражений в форме БНФ: <выражение> ~ <десятичное число> ! <перемеиная> !<двоичное выражение> <двоичиое выражение> -э <выражение слева> <оператор> <выражение справа> <оператор> -э +1~ Единственной рассматриваемой нами ошибкой в выражениях является неопределенное значение переменной. Разумеется, могут появляться и другие ошибки, но большинство из них зависят от машины. Пусть Š— набор целых чисел, а еггег — ошибочное значение. Тогда множество с н (еггог( является множеством значений, для которых выражение может быть вычислено. Ниже приведена искомая функция отображения для данного выражения Е и состояния з.
Чтобы отличать определения математической функции от операторов присваива- З.б. Описание смысла программ: динамичвскав семантика ння языков программирования. для определения математических функций мы использо- вали символ д= М,(< выражение >,з) д= сазе < выражение > ог < десятичное число » = М~ (< десятичное число >, з) < переменная » = !Г ЧАКМАР (< переменная >, з) = надет Йеп еггог еЬе ЧАКМАР(< переменная >, з) < двоичное выражение»= 1ЯМ,(< двоичное выражение >.< выражение слева >, з) = ввдеГОй М,(< двоичное выражение >.< выражение справа >, з) = инаят) Йеп еггог е!зе !Г(< лвоичное выражение >.< оператор > = '+' Йеп М, (< двоичное выражение >.< выражение слева >, з) + М,(< двоичное выражение >.< выражение справа >,з) е(зе М,(< двоичное выражение >.< выражение слева >,з) ' М,(< двоичное выражение >.< выражение справа >, з) 3.6.3.4.
Операторы присваивания Оператор присваивания — зто вычисление выражения плюс присваивание его значения переменной, находящейся в левой части. Сказанное можно описать следующей функцией: М,(х = Е, з) о= !т" М,(Е, з) = еггог Йеп еггог еЬе з'= (< 1,', ч,' >, < !т', ч.; >,..., < ь';ч,'>» епеге Рог) = 1,2, ..., и, ч,'=ЧА)(МАР(1„, з) !Г! <>х; М (Е, з) !(1, = х Отметим, что два сравнения, выполняющиеся в двух последних строках (1„<> х и 1, = х), относятся к именам, а не значениям. 3.6.3.5. Логически управляемые циклы с предварительной ироверкойусловия Денотационная семантика простого логически управляемого цикла обманчиво проста.
Для простоты дальнейшего обсуждения предположим, что существуют две другие функции М„ и Мь, отображающие списки операторов в состояния, а булевские выражения — в булевские значения (или значение еггог), соответственно. Эта функция имеет следующий вид: М~(нЬЕ1е В ао !., 5) о = 1Г МЫВ, 3) = ввает Йеп еггог е!зе (т" Мь(В, з) = Га!зе Йеп з е1зе !Г Мя(1, з) = еггог Йеп еггог еЬе М~(нЬь1е Ь ао 1., Мя(1., |)) Глава 3. Ооисцние синтаксисе и семантики Значение цикла является просто значением переменных, объявленных в программе, после заданного количества выполнений операторов цикла (предполагается. что ошибок при этом не было).
В сущности, цикл был превращен из итерации в рекурсию. причем контроль над последней математически определялся другиыи рекурсивными функциями отображений состояний. Математически строго описать рекурсию легче, чем итерацию. Это определение, подобно реальным циклам программ, может ничего не вычислять вследствие своей бесконечности. 3.6.3.6.
Оценке Объекты и функции, подобные использованным в приведенных выше выражениях, могут определяться и для других синтаксических сущностей языков программирования. После определения полной системы для заданного языка ее можно использовать лля определения смысла полных программ этого языка. Это создает основу лля очень строгого способа мышления в программировании.
Денотационная семантика может использоваться для разработки языка. Например, операторы, описать которые с помощью денотационной семантики трудно, могут оказаться сложными и для понимания пользователями языка, и тогда разработчику следует подумать об альтернативной конструкции. Значительное количество работ было посвящено возможности использования денотационных описаний языка для автоматического порождения компиляторов ()опез, 1980; М!1оз ег а!..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
