Лекция на тему FALGOL – теоретическая модель языков программирования высокого уровня (Лекция на тему FALGOL - теоретическая модель языков программирования высокого уровня)

Посмотреть архив целиком






FALGOL ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ

ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ



  1. Введение.


В разделе 2 описан синтаксис языка . Семантика языка уточняется несколькими способами – в формах операционной, денотационной и трансформационной семантик. Операционная семантика (раздел 3) представлена описанием абстрактной -машины, основными компонентами которой являются два стека – левый стек, данные для которого представляют собой записи -программ, правый стек, данными для которого являются отдельные инструкции (элементы программ), а также память типа «куча», единицами хранения для которой также являются записи программ. В параграфе 3.1 уточнены средства доступа к этим компонентам -машины, а в параграфе 3.2 описана архитектура и алгоритм работы -машины, реализующей выполнение -программ. В разделе 4 определена денотационная семантика языка путем определения отношений содержательного включения, содержательной эквивалентности и содержательной несравнимости -программ. В разделе 5 приводятся правила эквивалентных преобразований (трансформационная семантика) формул языка , не противоречащих введенной денотационной семантике. Большинство из этих преобразований носит направленный характер, что позволяет определить процесс вычислений как процесс преобразований формулы к нормальной форме, в которой уже невозможно направленное применение этих правил. В разделе 6 рассматривается частный случай модели со статическим связыванием и его расширение атомарными константами.


  1. Синтаксис языка .


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

Множество -термов (далее просто термов) определяется как множество списков на множестве атомов , то есть как множество любых конечных последовательностей (кортежей) элементов термов: , где . Элемент вида назовем процедурой, а терм – ее телом.

Так как термы – списки, то индуктивные определения различных понятий для термов удобно давать рассмотрением случаев: 1) пустого списка , 2) одноэлементного списка с элементом-атомом, 3) одноэлементного списка с элементом-процедурой и 4) конкатенации (сцепления) двух списков.

Введем понятие контекста. Синтаксически контекст определяется как терм, в котором в качестве одного из атомарных подтермов используется символ – «дырка». Пусть множество всевозможных контекстов. Результат замены в контексте «дырки» на будем обозначать как : если – терм, то результатом замены будет терм, если – контекст, то результатом замены будет тоже контекст.

Далее приводятся индуктивные определения понятий:

  • множества номеров переменных терма ,

  • множества номеров свободно используемых переменных терма ,

  • множества номеров свободно изменяемых переменных терма .

Пусть . Тогда

, , , ;

;

.

Определение 1. Терм