Семантику любого языка программирования можно описать двумя способами

Семантику любого языка программирования можно описать двумя способами: содержательно и формально. Содержательное описание семантики: «В команде ввод через запятую указываются имена величин. При выполнении команды ЭВМ ждёт, пока человек введёт соответствующие значения, и по окончании ввода присваивает введённые значения указанным величинам. Признаком конца ввода служит нажатие на специальную клавишу (обычно на этой клавише изображена изогнутая стрелка «8 «). При вводе нескольких чисел они отделяются друг от друга запятой или пробелом». Такой способ описания семантики хорош до тех пор, пока эти описания читают люди. Но встречаются ситуации, когда описание должно быть доступно компьютеру, например, при трансляции программы с данного языка программирования. В этом случае подобные описания неприемлемы. Именно это и послужило стимулом к разработке теории, которая бы позволила осуществить формализацию семантики. Задача формализации семантики языка программирования, однако, оказалась гораздо сложнее, чем задача формализации его синтаксиса. Для описания семантики языка необходимо ввести в рассмотрение правила перехода от одних выражений языка к некоторым другим выражениям, несущим ту же информацию (имеющим тот же смысл), т.е. правила преобразования языковых выражений. Смысл языкового выражения рассматривается здесь как то общее, что имеется у данного выражения и всех других синонимичных ему выражений того же или какого-либо другого (не обязательно естественного) языка.  При таком подходе выражение «описать семантику языка L» означает: (1) указать другой язык L’, на который будут переводиться выражения языка L; (2) задать правила перевода любых выражений с языка L на язык L’ и обратно. Язык L’ называется семантическим языком.

Примеры семантического языка:

I. Язык формальной системы первого порядка, который сам по себе предназначен для описания весьма ограниченной части семантики (говорящую о истинности или ложности утверждений).

II. Построенный Г.Фройденталем [Freudental, 1960] язык Линкос (Lingua Cosmica), предназначаемый для общения с внеземными цивилизациями. Мысль о том, что на основании общности законов мира, в котором мы живём, земляне могут войти в контакт со своими звездными братьями, — логическая основа языка Линкос. Г.Фройденталь сразу же вносит существенную оговорку: Линкос является абстрактной схемой языка, а не его конкретной, «физической» формой. Однако, по мнению автора, первые «буквы» Линкоса должны быть наглядными, их значение должно быть тесно связано с физическим воплощением, наподобие междометий вроде динь-динь-динь или кукареку.

Применительно к языкам программирования выделяют следующие виды семантики: операционная; денотационная (математическая); дедуктивная (аксиоматическая); трансляционная; определенная через расширения и другие.

1.                  Пустота и тотальность стандартных схем

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

Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.

Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и др.), задает вид выражений и операторов схем.

Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов — слов, построенных из этих символов.

Множества символов полного базиса:Х = {x, х1, х2…, у, у1 у2…, z, z1, z2…} — множество символов, называемых переменными;F = {f(0), f(1), f(2)…, g(0), g(1), g(2)…, h(0), h(1), h(2)…} — множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c…;Р = {р(0), р(1), р(2)…; q(0), q(1), q(2)…; } — множество предикатных символов; р(0), q(0) — ; нульместные символы называют логическими константами;{start, stop, …,:= и т. д.} — множество специальных символов.ССП S в базисе В тотальна, если для любой интерпретации I базиса В программа (S, I) останавливается.

ССП S в базисе В пуста, если для любой интерпретации I базиса В программа (S, I) зацикливается.


Ссылка на основную публикацию
Adblock detector