18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики



Скачать 296.43 Kb.
страница2/4
Дата02.01.2013
Размер296.43 Kb.
ТипДокументы
1   2   3   4

Другие новые базисные функции.

Особый интерес для нашего уровня абстракции представляют 2 подмножества универсума resultsуниверсумы результатов вычислений.

Универсум bytes содержит те значения, которые могут храниться в виде символьных переменных(char). Универсум addresses содержит положительные целые числа, соответствующие действительному размещению памяти (это универсум значений, которые могут храниться в виде указателей).

Универсум typename содержит элементы, представляющие различные типа хранимых переменных. Статическая частичная функция ValueTypе: tasks →typename указывает тип результата при вычислении выражения.

Статические частичные функции LeftTask, RightTask: tasks → tasks указывают соответственно левые и правые операнды бинарных операторов, порядок вычисления которых не предопределен Си (например +). Статическая частичная функция Parent: tasks → tasks указывает родительское выражение для данного выражения. Для выражений, которые не содержатся в каких-либо других выражениях возвращается значение undef.

Статическая частичная функция WhichChild: tasks →{ left,right, only, test,…}( где left,right, only, test – элементы универсума tags) указывает отношения между задачей и ее родителем.

Динамические частичные функции LeftValue, RightValue: tasksresults указывает результаты вычислений соответственно левых и правых операндов бинарных операторов с неопределенным порядком вычисления.

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

Статическая частичная функция ConstVal: tasksresults возвращает значение программных констант.
Макрокоманда DoAssign

Наши правила для распределения памяти немного сложны, так как данное распределение может потребовать большого числа обращений к функции Memory.

Необходимы правила,которые выполняли бы цикл, для того, чтобы систематизировать обращения к функции Memory.

Для выполнения цикла используются несколько выделенных элементов. Выделенный элемент CopyValue: results определяет копируемое значение. CopyType: typename определяет тип копируемого значения. CopyLocation: address определяет местоположение, куда будет скопировано значение. CopyByte: integer указывает, какой байт представления CopyValue копируется в память. OldTask: tasks указывает задачу, которая вызвала процедуру копирования. CopyTask: tasks статический выделенный элемент, показывающий, что выполняется процедура копирования.


Процедура копирования вызывается макрокомандой DoAssign(address, value, type), определенной след образом: DoAssign(address, value, type)

CopyValue := value

CopyType := type

CopyLocation := address

CopyByte := 0

OldTask := CurTask

CurTask := CopyTask

Сам по себе процесс копирования относительно прост. Используем выделенный элемент CopyByte чтобы определить байт представления CopyValue, который мы копируем в данный момент времени.

Копирование байтов выполняется поодиночке, при этом увеличивая значение CopyByte на единицу каждый раз после обращения к памяти. Процесс прекращается, когда все байты окажутся скопированы.

Правила перехода для данной операции:

if CurTask = CopyTask then

if CopyByte < Size(CopyType) then

Memory (CopyLocation +CopyByte):= ResultToByte(CopyValue, CopyByte, CopyType)

CopyByte := CopyByte + 1

elseif CopyByte = Size(CopyType) then

CurTask := NextTask(OldTask)

еndif

endif
Макрокоманда ReportValue

При выполнеии задач, связанных с вычислением выражений вычисленное значение передается функции хранения в родительском выражении (например LeftValue(Parent(CurTask))) . Для этого используется макрокоманда ReportValue.

Определение команды:

ReportValue(value)

if WhichChild(CurTask) = left then

LeftValue(Parent(CurTask)) := value

elseif WhichChild(CurTask) = right then

RightValue(Parent(CurTask)) := value

elseif WhichChild(CurTask) = only then

OnlyValue(Parent(CurTask)) := value

elseif WhichChild(CurTask) = test then

TestValue(Parent(CurTask)) := value

endif
Макрокоманды EvaluateOperands и Moveto

В Си многие бинарные оператора(например оператор присваивания “=”) не определяют порядок вычислений: любой из опреандов может быть вычислен первым. Когда один или более опреандов таких опреаторов создают побочный эффект (например «a[i] = i++»), то значение полученного выражения может зависеть от порядка вычислений. Однако эта неонозначность позволяет оптимизаторам сгенерировать код, минимизирующий затраты ресурсов, требуемых для выполнения конкретных вычислений.

Для выражений, вызывающих такие операторы, наша алгебра должна быть достаточно гибкой, чтобы отражать любой возможный порядок вычислений операндов, даже если это решение принимается во время выполнения программы.

Необходимо предоставить механизм для динамического создания подобных решений. Будем использовать внешнюю функцию ChooseTask для представления решения.

Динамическая функция Vizited: task→ {left, right, both,neither} указывает какое подвыражение вычислялось в данный момент времени. Изначально ф-ция Vizited имеет значение neither для всех задач. Для вычисления выражения сначала вычисляем подвыражение, указанное ф-цией ChooseTsk, после чего вычисляем другое под-выражение. В итоге, когда оба подвыражения оказываются вычисленными, выполняемый требуемый оператор.

Управление задачами осуществляет макрокоманда EVALUATEOPERANDS. Неформально она означает: «Вычисляем оба операнда в порядке, заданном функцией ChooseTask; когда оба оперранда вычислены, делаем…»

Для управления переходами между подзадачами переопределим макрокоманду MoveTo(Task): совершать переход непосредственно между подзадачами данного оператора.

Представление бинарных опрераторов в нашей алгебре:


Определение EvaluateOperands :



Определение Moveto


21. Операционная семантика языка Си в формализме ASM.

Второй уровень определения семантики.

Семантика выражений "Запятая", "условное", OR, AND, sizeof, констант.
Выражение «Запятая»

Синтаксическая форма: выражение-запятая выражение1, выражение2

Вычисление выражение-запятая сводится к вычислению выражение1, выражение2, слева направо, значение выражение2 возвращается в качестве родительского. Выражение «Запятая» представляется в виде последовательности двух выражений, связанных функцией NextTask. Т.о. никаких доп правил перехода для выполнения этого оператора не требуется.
«Условное» выражение

Синтаксическая форма: Условное-выражение → выражение1 ? выражение2 : выражение3

Вычисление условного выражения: вычисляем выражение1. Если получившееся значение не ноль, то вычисляем выражение2 и возвращаем его результат в качестве значения родительского выражения. В противном случае вычисляем выражени3, и возвращаем его результат в качестве значения условного выражения.

Представление в нашей алгебре: подобно представлению условных операторов.



Задачи, соответствующие центральному и правому подвыражению будут изменять соответствующую функцию Value родительского выражения при завершении вычислений подвыражения.
Выражение «Логическое ИЛИ»

Синтаксическая форма: Логическое-ИЛИ → выражение1 || выражение2

Вычисление: Начинаем с вычисления выражение1. Если результат не ноль, то значение родительского выражение равно 1 и выражэение2 не вычисляется. Иначе значение родительского выражения равняется значению выражения2,

Представлениев алгебре: Определим два новых типа задач: OR и makeBool.

Схема представления выражения ИЛИ:



При обработке задачи OR будет проверено выражение1. Если его значение не ноль, тосогласно правилам для задач типа OR значение выражения устанавливается в 1, и вычисление родительского выражения на этом завершается. Иначе управление передается к задачам, вычисляющим выражение2.

Правила для задач типа makeBool будут проверять значение выражения2 и преобазовать его либо в 0, либо в 1.

Правила перехода для OR:

и makeBool:



Выражение «Логическое И»

Синтаксическая форма: Логическое-И→ выражение1& выражение2

Вычисление: Сначала вычисляем выражение1. Если его значение равно 0, то значение родителя тоже 0. В противном случае, значение выражения2 (представленное 0 или 1) является значением родительского выражения.

Представление в алгебре:

Правила перехода:


Оператор SizeOf

Синтаксическая форма:

SizeOf-выражение → sizeof выражение;
SizeOf-выражение → sizeof(название-типа)

Функция ValueType преобразует каждый операнд в значение универсума typename. На основе этой информации используется функция Size, для определения в байтах размера элемента конкретного типа и это число возвращается в качестве результата унарной операции.

Правила перехода:



Константы

Для постоянных выражений функция ConstVal возвращает соответствующее значение.

Правила перехода:


22. Операционная семантика языка Си в формализме ASM.

Второй уровень определения семантики.

Семантика присваиваний.

Присваивания

Синтаксическая форма: выражение-присваивания → выражение1 = выражение2

Вычисление простого выражения присваивания:

Копируем значение выражения2 в память по адресу, заданному выражением1, возвращая это значение в качестве значения родительского выражения.

Этот оператор имеет неоднозначный порядок вычислений.

Представление выражения в алгебре:



В Си есть и другие операторы присваивания(«+=», «*=»), выполняющие матеметические операции над значением выражения2 и значением, хранящимся в ячейке памяти, заданной выражением1.

Результат копируется в область памяти, заданную выражением1. Например выражение i*=2 имеет то же, значение, что и выражение i= i*2. Однако далеко не всегда выражение «a op= b» можно рассматривать, как сокращение от «a = a op b», т.к. выражение а в первом случае вычисляется только один раз, а втором случае – два.

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

Правила перехода для простого оператора присваивания:



Правила перехода для мультипликативного оператора присваивания(«*=»):


Исключениями являются аддитивный и субтрактивный операторы присваивания. «+=» «-=».

В Си можно прибавлять целое число i к указателю p, результатом будет указатель ????????

Таким образом, при выполнении «a +=b» мы должны совершать различные действия, если а – переменная-указатель.

Опишем правила перехода для аддитивного присваивания, вычисляющего указатели:



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

Второй уровень определения семантики.

Общие математические выражения, унарные операции, приведение типов.
Общие математические выражения

В Си большое количество выражений, вычисляющих бинарные операторы (*, +, - и т.д.).

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

Представим правила перехода для мультипликативнных задач:


Правила для операторов сложения и вычитания немного более запутанные, т.к. складывать и вычитать можно как целые числа, так и указатели. Целое число i можно прибавить к указателю p, в результате получится указатель, указывающий на i-ю ячейку после p.

Рассмотрим, например, прибавление указателя р к целому в системе, где целые числа требуют в памяти 4 байта. Выражение «р+1» - указатель на 4-ю ячейку после р.

Подобным образом можно вычитать целое I из указателя р, результатом является указатель на i-.ю ячейку до р.

Более того, можно вычитать два указателя одного типа, получая в результате количество ячеек памяти, лежащих между двумя указателями.

В каждом случае размер ячейки определяется размером типа объекта, на который указывает указатель.

Это требует специальных правил для операторов сложения и вычитания.

Необходимо знать, является ли переменная указателем; для этого используется статическая частичная ф-ция PointerType:tasks→{true,false}.

Для задач, для которых ф-ция PointerType возвращает true, статическая частичная ф-ция PointsToType:tasksTypeName указывает тип объекта, на который указывает указатель.
Правила перехода для оператора сложения


Правила перехода для оператора вычитания:

1   2   3   4

Похожие:

18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconПредмет семантики
Семантика, как и всякая научная дисциплина, имеет свой предмет. Но определить этот предмет не так просто, как это может показаться....
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconВопросы по курсу ксе первый уровень освоения курса – «иметь представление о курсе»
Первый уровень освоения курса – «иметь представление о курсе», т е знать основные определения, положения и принципы
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconВопросы к экзамену Примеры различных направлений, стилей и техник программирования
Операционная семантика языков программирования. Абстрактная машина и интерпретатор
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики icon1. Синтаксис и семантика языков программирования. Алфавит языка Borland Pascal. Описание синтаксиса языка: синтаксические диаграммы
Синтаксис языка совокупность правил, определяющих допустимые конструкции (слова, предложения) языка, его форму
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconКомпьютерная семантика русского языка
Существует только один способ такого разграничения, суть которого сводится к построению формального семантического языка и двухстороннему...
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconЛекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconЛекция Определение языков программирования Прежде чем анализировать конкретные парадигмы программирования, рассмотрим задачу определения систем программирования
Прежде чем анализировать конкретные парадигмы программирования, рассмотрим задачу определения систем программирования. Строится простейшее...
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconС. Н. Селезнёва г. Красноярск, Россия Динамика семантики слова патриарх в культурно-историческом аспекте
Васильев: 1994, 157]. Наиболее ярко история духа народа может наблюдаться в судьбах слов, семантика которых включает компонент аксиологического...
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconМашины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения
Предоставить средства построения т наз исполняемых спецификаций или исполняемых моделей программных систем, т е спецификации asm...
18. Операционная семантика языка Си в формализме asm. Первый уровень определения семантики iconВопросы семантики и прагматики грамматических категорий в курсе русского языка как иностранного

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org