Файл: КУРСОВАЯ ПО ТВП.docx

{<i1, v1>, <i2, v2>, …, <in, vn>}.

Каждый параметр i является именем переменной, а соответствующие параметры v являются текущими значениями данных переменных. Любой из параметров v может иметь специальное значение undef, указывающее, что связанная с ним величина в данный момент не определена.

Пусть VARMAP - функция двух параметров, имени переменной и состояния программы. Значение функции VARMAP(ik, s) равно vk (значение, соответствующее параметру ik в состоянии s).

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

Выражения являются основой большинства языков программирования. Более того, мы имеем дело только с очень простыми выражениями. Единственными операторами являются операторы + и ×; выражения могут содержать не более одного оператора; единственными операндами являются скалярные переменные и целочисленные литеральные константы; круглые скобки не используются; значение выражения является целым числом. Ниже следует описание этих выражений: <выражение> → <десятичное_число> | <переменная> | <двоичное_выражение> <двоичное_выражение> → <выражение_слева> <оператор> <выражение_справа> <оператор> → + | ×

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

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

С одной стороны, денотационные описания очень сложны, с другой - они дают великолепный метод краткого описания языка.[1, С.188-191]

3. Аксиоматическая семантика

Если операционная семантика предназначена в основном для того, чтобы чётко зафиксировать правила поведения исполнителя программы, то аксиоматическая (дедуктивная) семантика предназначена в основном для того, чтобы чётко зафиксировать правила поведения исполнителя при доказательстве свойств программ (наиболее интересное из таких свойств - свойство давать определённые результаты при определённых входных данных).

---

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

Вот определение, которое дает толковый словарь: аксиоматическая семантика - семантика языков программирования, в которой значение языковой конструкции или программы на некотором языке программирования определяется "аксиомой". Для каждого конкретного высказывания аксиома указывает, что должно быть истинным после его реализации в контексте того, что было истинным до реализации высказывания. Аксиоматическая семантика играет важную роль в доказательстве корректности программ.

В отличие от операционной семантики дедуктивная семантика отказывается от того, чтобы связывать смысл конструкций языков программирования с каким-либо способом проведения вычислений. Таким образом, она абстрагируется от ряда деталей вычислений, несущественных для понимания смысла программы, и дает возможность говорить об абстрактных свойствах программ. Тем не менее, дедуктивная семантика в основном ориентирована на императивное программирование.[2]

4. Трансляционная семантика

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

В общем случае трансляционный подход может использоваться и для языков высокого уровня. В качестве языка, на который осуществляется перевод, может быть выбран некоторый математический язык (например, язык -исчисления), некоторый другой язык программирования (например, язык Алмо для языков описания алгоритмов или язык Паскаль для языка Сетл) или конкретный машинный язык. Таким образом, транслятор для языка высокого уровня на конкретный машинный язык становится семантическим определением языка.[3]

---

5. Выводы по методам определения семантики

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

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

---

2 Задача о пяти обедающих философах

2.1Постановка задачи

Представим себе парк, по аллеям которого прогуливаются пять философов. В центре парка расположена столовая, в которой накрыт круглый стол. На столе стоил миска со спагетти, пять тарелок и пять вилок. Если философ проголодался, он входит в столовую, занимает свободное место за столом, берет две (обязательное условие!!!) вилки и накладывает на тарелку спагетти. Утолив голод, философ возвращает вилки на стол и покидает столовую.

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

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

Рисунок 2.1.1 – Задача о пяти обедающих философах

2.2 Решение задачи

В данной задачи имеются две опасные ситуации: «заговор соседей» и «голодная смерть»:

• «Заговор соседей» имеет место, когда соседи слева и справа от философа строят козни. Заговорщики поочерёдно забирают вилки то слева, то справа от «жертвы». Такие согласованные действия приводят жертву к вынужденному голоданию, так как он никогда не может воспользоваться обеими вилками;

• «Голодная смерть» возникает, когда философы одновременно проголодаются и одновременно попытаются взять, например, свою левую вилку. При этом возникает тупиковая ситуация, так как никто из них не может начать есть, не имея второй вилки.

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

---

Рисунок 2.2.1 – Решение задачи «Об обедающих философах» с использованием методологии К.Петри

2.3 Листинг процедур, обеспечивающих решение задачи

/* Главная процедура программы «Философ». Существует еще программа «Table» (или «Стол»), которая запускает процессы с передачей параметров запуска.*/

int main(int argc, char* argv[])

{

BOOL fSuccess;

DWORD cbRead, cbWritten, dwMode;

LPSTR lpszPipename="\\\\.\\pipe\\mynamedpipe";

HANDLE hPipe;

srand(atoi(argv[1]));

/* установка именованного соединения со «столом» (необходимо для передачи текущего состояния философа) */

while (1)

{hPipe=CreateFile(

lpszPipename,

GENERIC_READ |

GENERIC_WRITE,

FILE_SHARE_READ,

NULL,

OPEN_EXISTING,

0,

NULL);

if (hPipe != INVALID_HANDLE_VALUE)

break;

if (GetLastError() != ERROR_PIPE_BUSY) return 1;

if (!WaitNamedPipe(lpszPipename, 20000)) return 1;

}

dwMode=PIPE_READMODE_MESSAGE;

fSuccess=SetNamedPipeHandleState(hPipe,

&dwMode,

NULL,

NULL);

if (!fSuccess)

{printf("Ошибка в функции SetNamedPipeHandleState");

return 1;}

fSuccess=ReadFile(hPipe,

chBuf,

512,

&cbRead,

NULL);

if (!fSuccess)

{printf("Ошибка в функции ReadFile");

return 1 ;}

int ind=atoi(chBuf); //запоминаем идентификатор

AnsiString tmp="";

/*создание мьютексов для вилок*/

HANDLE M[2];

/*чтобы не было двух мьютексов с одинаковыми именами, создатся только пять мьютексов. Для исключения взаимной болкировки необходимо,чтобы были философы которые сначала берут правую вилку и были, которые берут левую.*/

if (ind==1) //если философ первый, то создаем мьбтексы с именами M5 и M1

{tmp="M"+IntToStr(5);

M[0] = CreateMutex(NULL, false, tmp.c_str());

tmp="M"+IntToStr(1);

M[1] = CreateMutex(NULL, false, tmp.c_str());

}

Else

/* «нечетный» философ будет брать сначала вилку справа от себя*/

if (ind%2)

{tmp="M"+IntToStr(ind-1);

M[0] = CreateMutex(NULL, false, tmp.c_str());

tmp="M"+IntToStr(ind);

M[1] = CreateMutex(NULL, false, tmp.c_str());

}

else // «четный» философ будет брать сначала вилку слева от себя

{tmp="M"+IntToStr(ind);

M[0] = CreateMutex(NULL, false, tmp.c_str());

---