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



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

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

Рассмотрим первую машину, моделирующую самый высокий уровень абстракции ― модель структуры управления языка Си.

Некоторые базисные функции

Универсум tasks состоит из элементов (имен), представляющих задачи, выполняемые

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

Выполняемые задачи часто сопровождаются признаками, характеризующими специфику задачи; указанные признаки составляют универсум tags.

Выделенный элемент(базисная нульместная функция) CurTask: tasks указывает текущую задачу. Порядок выполнения задач определяется статической (!) функцией NextTask: taskstasks, указывающей следующую выполняемую задачу после завершения текущей (имеются и другие функции, управляющие порядком выполнения задач). Статическая функция TaskType: tasks →tags указывает на действие, выполняемое задачей.

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

Макрокоманда: Moveto

При передаче управления конкретной задаче, у нас изменяется значение CurTask, для того, чтобы означить факт передачи управления.

Мы будет использовать макрокоманду Moveto (Task) каждый раз, когда хотим передать управление.

Определение этой команды : Moveto (Task)

CurTask: = Task
Классификация операторов языка Си

Правила перехода абстрактной машины данного уровня абстракции определяются

структурой множества операторов языка. Имеются шесть категорий операторов языка Си.

1. Операторы-выражения, вычисляющие составляющие их выражения.

2. Операторы выбора или ветвления (if, switch).

3. Операторы цикла (for, while, dowhile).

4. Операторы передачи управления (goto, continue, break, return).

5. Операторы с метками (операторы case и default, используемые в области действия

оператора switch, и оператор-обьект оператора goto).

6. Составные операторы, состоящие из списка (возможно пустого) локальных переменных и списка (тоже возможно пустого) операторов.

Операторы-выражения

Операторы-выражения имеют одну из двух форм:

оператор-выражение →;

оператор-выражение →выражение;

Выполнение оператора-выражения сводится к вычислению составляющего его

выражения (если оно не пусто).
Эта операция может сопровождаться побочными эффектами

(например присваиванием значений переменным), а также может не заканчиваться. В абстрактной машине данного уровня вычисление выражений управляется внешней функцией TestValue: tasks →results.

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

дополнительных функций, машина просто переходит к выполнению следующей задачи.

Соответствующее правило перехода:

if TaskType(CurTask) expression then

CurTask :NextTask(CurTask) или Moveto(NextTask(CurTask))

endif

где признак expression ― один из элементов универсума tags.
Операторы выбора

Существует два типа операторов выбора: оператор if и оператор switch.

Условный оператор if имеет одну из следующих форм:

условный_оператор →if (выражение) оператор1

условный_оператор →if (выражение) оператор1 else оператор2

Выполнение оператора if начинается с вычисления условия. Если результат не равен

нулю, выполняется оператор1. Если результат равен нулю и оператор if содержит

выражение else, выполняется оператор2, в противном случае выполняется оператор,

следующий за оператором if. Статические (частичные) функции TrueTask: tasks→tasks и FalseTask: tasks →tasks указывают задачу, которая должна выполняться в том случае, когда условие оператора if принимает ненулевое или нулевое значение соответственно.

Решение о выборе направления, принимаемое оператором if, связывается с некоторым элементом универсума tasks, имеющим признак branch (другими словами, для этого элемента значение функции TaskType branch).

Представленный ниже рисунок иллюстрирует типичную для оператора if схему

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

Если оператор if не содержит выражение else, то подграф оператор2 вместе с входящей и выходящей дугами, показанный в нижней части рисунка,

заменяется на изображенную пунктиром дугу FalseTask, соединяющую задачу branch с

задачей, следующей за оператором if.


(Если подграфы оператор1 или оператор2 содержат оператор передачи управления, то изображенная схема может измениться: NextTask может указывать на задачу, которая не является непосредственно следующей за оператором if.)

Правила перехода для задачи branch:

if TaskType(CurTask) branch then

if TestValue(CurTask) ≠0 then

CurTask :TrueTask(CurTask)

elseif TestValue(CurTask) 0 then

Curtask :FalseTask(CurTask)

endif

endif

Второй оператор ветвления ― switch ― имеет в некотором смысле более простую

семантику, чем оператор if.

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

оператор_switch →switch ( выражение ) тело

где тело ― это оператор, обычно составной.

Внутри тела оператора switch обычно находятся оперторы case и default.

Выполнение оператора switch сводится к вычислению выражения-условия и передаче

управления первому вложенному в данный оператор switch оператору case, помеченному константой, совпадающей со значением условия, или к оператору default. Если указанные операторы не будут найдены, управление передается оператору, непосредственно следующему за оператором switch.

Константы, помечающие операторы case, должны быть

уникальными в пределах одного оператора switch, количество операторов default не

превосходит единицы. Таким образом, можно определить статическую (!) частичную

функцию , указывающую на следующую выполняемую задачу для данного значения условия. Соответственно, правила перехода из состояния выполнения задачи с признаком switch к следующей задаче непосредственно определяются функцией SwitchTask.


Типичная схема упраления оператора switch
if TaskType(CurTask) = switch then

Moveto(SwitchTask(CurTask,TestValue(CurTask)))

endif

Операторы цикла

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

Оператор-while →while ( выражение ) тело

Выполнение оператора сводится к циклическому вычислению выражения-условия с

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


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

оператор-do-while →do тело while ( выражение );

где тело – это оператор.

Оператор do-while идентичен оператору while за исключением того, что выражение-условие и оператор тела выполняются в обратном порядке. Как и в случае оператора while,для реализации этой схемы не требуется никаких новых правил перехода.
Оператор for

Наиболее полная синтаксическая оператора for:

Оператор-for→for (инициализатор; проверка_условия; изменения_параметра)тело,

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

При описании этой схемы будем считать, что все выражения присутствуют.

Выполнение оператора for начинается с вычисления инициализатора. Далее выполняем проверку условия, если результат не ноль, то выполняем оператор тела цикла, производим изменение парамтра и затем вновь проверяем наше условие. Если результат проверки – ноль, то управление передаается оператору, непосредственно следующему за операторм цикла for.


Если в графе оператора for отсутствует одно или более из выражений инициализатора, проверка_условия, изменение_параметра, то соответствующие задачи пропускаются вместе с дугой NextTask, указывающей на следующую выполняющуюся задачу нашего графа.

Если пропущена проверка _условия, то пропускаются обе задачи: test и branch, которые создают бесконечный цикл.
Оператооры перехода.

Операторы перехода могут иметь одну из следующих форм:
Оператор-перехода →goto идентификатор;

Оператор-перехода → continue;

Оператор-перехода →break;

Оператор-перехода →return;

Оператор-перехода →return выражение;
Каждый из этих операторов перехода является командой, указывающей, что управление должно быть безоговорочно передано другой задаче из графа задач:

  • Операторы goto непосредственно указывают задачу, которой необходимо передать управление;

  • Операторы continue могут встречаться только внутри оператора тела цикла. Для данного оператора continue С пусть S будет наименьшим оператором цикла, содержащим оператор С. Тогда при выполнении оператора С управление будет передано задаче оператора S,следующей за оператором тела S, например для оператора for управление передается выражению изменения_параметра, для оператора while управление передается к выражению-условию

  • Оператор break может встречаться внутри тела цикла или внутри оператора switch. Пусть дан оператор break B, и пусть S – наименьший оператор цикла или оператор switch, содержащий B. Тогда при выполнении оператора B управление будет передано задаче, непосредственно следующей за оператором S.

  • Оператор return встречается в теле функции. Он указывает, что выполнение текущей функции должно быть завершено. При выполнении оператора return значение функции CurTask устанавливается в undef,



Правила перехода для операторов перехода: if TaskType(CurTask)= jump then

Moveto(NextTask(CurTask))

endif

Операторы с меткой

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

Оператор-с-меткой →идентификатор : оператор

Оператор-с-меткой →case константа-выражение : оператор

Оператор-с-меткой →default : оператор
Операторы с меткой указывают цели в операторах goto и switch. NextTask и SwitchTask возвращают в каждом случае соответствующие задачи.

Никаких дополнительных правил перехода не требуется.
Составные операторы.

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

Составной-оператор →{список_объявлений, список_операторов}

Где один из списков (или оба) могут быть пустыми.

Так как функция NextTask указывает порядок выполнения задач, нам не требуется дополнительных правил для составных операторов. Каждый оператор или объявление составного оператора связаны со своим преемником посредством функции NextTask.

Начальное и заключительное состояния

В начальном состоянии машины верхнего уровня абстракции функция CurTask указывает

на первый оператор программы.

Заключительным состоянием машины данного уровня является любое состояние, в

котором CurTask undef. В этом состоянии значение TaskType(undef) undef (и не

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

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

Базисные функции и макросы.

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

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

(определённой и оформленной в теле программы ) и динамической.

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

В Си можно придумывать и изменять типы.

Статическая функция Size: typename→ integer. Указывает сколько байтов памяти использует величина указанного типа. Динамическая функция Memory: addresses bytes отображает величины, хранящиея в памяти в указанном байте.

Так как большинство интересующх величин имеют размер больше байта, то нам необходимы средства для хранения элементов универсума results в виде отдельных байтов.Предположим, например, что целое число 258 представлено в памяти конкретной системы четырьмя байтами 0,0,1 и 2, хрянящимися последовательно.Необходим способ по значению элемента results получать значение составляющих байтов и наоборот.

Статическая частичная (n+1)-значная функция ByteToResul:

Преобразует представление в памяти для значения заданного типа в значение элемента универсума results. n – максимальное кол-во байтов, используемых для представления в памяти любого заданного типа. Для тпов, чьё представление в памяти использует меньше, чем n байтов, неиспользуемые параметры игнорируются.

Статическая частичная функция ResultToByte: возвращает определенный байт представления в памяти заданного элемента из заданного универсума.

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

MemoryValue (addr,type) – сокращение
  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