Теория и реализация языков программирования

         

Простой язык программирования


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

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

Алфавит пробел, единица, нуль, точка; печатать "точка"; перейти на выполнить; тест: если символ на ленте _единицаї, то {печатать "нуль"; (4.1) выполнить: сдвинуться влево на одну клетку; перейти на тест}; печатать "единица"; возврат: сдвинуться вправо на одну клетку; если символ на ленте "нуль", то перейти на возврат.

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

Поскольку каждый язык программирования нужно как- то называть, назовeм наш язык Тьюринголом. Всякая правильная программа на Тьюринголе определяет программу для машины Тьюринга; будем говорить, что программа для машины Тьюринга состоит из:

  • множества "состояний" Q,
  • множества "символов" ?
  • начального "состояния" q0
    Q
  • конечного "состояния" q1
    Q
  • и "функции переходов"
    , отображающей множество

(Q-{q?})x? в ?{-1, 0, +1}xQ. Если

(q, s) = (s', k', q'), то это означает, что если машина находится в состоянии q и обозревает символ s, то она печатает символ s', сдвигает читающее устройство на k клеток вправо (сдвигу на одну клетку влево соответствует случай k = 1) и переходит в состояние q'.
Формально программа машины Тьюринга определяет вычисление для ленты с "любым начальным содержимым", то есть для любой бесконечной в обе стороны последовательности

...,a-3, a-2, a-1, a0, a1, a2, a3,...

Пример 4.2.

(html, txt)

элементов алфавита ? следующим образом. В произвольный момент вычисления существует "текущее состояние" q
Q и целочисленная величина "положение читающего устройства" p. Вначале q = q0 и p = 0. Если q
q? и если
(q, ap) = (s', k', q'), то следующим шагом вычисления будет замена значения p на p + k, q на q' и ap на s'. Если q = q?, вычисление заканчивается. (Вычисление может не закончиться; для программы (4.1) это произойдeт тогда и только тогда, когда aj="единица" для всех j < 0.)

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

(1) Семантическое правило " включить х в B ", связанное с синтаксическим правилом, означает, что x должен стать элементом множества B, где B - атрибут аксиомы S грамматики. Значением B будет множество всех x, для которых существует такое семантическое правило, связанное с каждым применением соответствующего синтаксического правила в дереве вывода. (Это правило можно рассматривать как сокращeнную запись семантического правила



связанного с каждым синтаксическим правилом. Здесь B - синтезированный атрибут, имеющийся у всех нетерминальных символов. Для терминальных символов B(x) пусто. Ясно, что эти правила позволяют получить нужное B(S).)

(2) Семантическое правило "определить f(x) = y", связанное с синтаксическим правилом, означает, что значение функции f в точке x будет равно y; здесь f - атрибут аксиомы S грамматики. Если встречается два правила, задающих значение f(x) для одного и того же значения x, то возникает ситуация ошибки, а дерево вывода, в котором она возникла, называется неправильным.


Далее, к функции f можно обращаться в других семантических правилах при условии, что f(x) будет использоваться только тогда, когда значение функции для аргумента x определено. Любое дерево вывода, для которого

встретилось обращение к неопределeнной величине f(x), называется неправильным. (Правила такого типа важны, например, тогда, когда нужно обеспечить соответствие между описанием и использованием идентификаторов. В приведeнном ниже примере в соответствии с этим соглашением неправильными будут программы, в которых один и тот же идентификатор дважды встречается в качестве метки, или в операторе перехода используется идентификатор, не являющийся меткой оператора. В сущности, это правило можно представлять себе, аналогично (1), как " включить (x, y) в f", если рассматривать f как множество упорядоченных пар; необходимо соответственно ввести дополнительные проверки на зацикленность. Признак "правильно или неправильно" можно считать атрибутом аксиомы S. Построение соответствующих семантических правил, аналогичных (4.3), которые аккуратно определяют запись "определить f(x) = y", несложно и предоставляется читателю.)

(3) Функция "новсимвол", в каком бы правиле она ни встретилась, будет вырабатывать некий абстрактный объект, причeм при каждом обращении к "новсимвол" этот объект будет отличен от всех полученных при предшествовавших обращениях к новсимвол. (Эту функцию легко выразить при помощи других семантических правил, например используя атрибуты l из (2.3), принимающие в разных вершинах дерева разные значения. Функция новсимвол служит подходящим источником "сырья" для построения множеств.)

Мы видели, что соглашения (1), (2) и (3) можно заменить другими семантическими конструкциями, не использующими таких соглашений, следовательно, они не являются "базисными" для семантики. Но они чрезвычайно полезны, так как соответствуют понятиям, которыми часто пользуются, поэтому их можно считать принципиальными для метода описания семантики, представленного в настоящей статье.




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

Нетерминальные символы:

P (программа), S (оператор), L (список операторов), I (идентификатор), O (направление), A (символ алфавита), D (описание).

Терминальные символы:

a b c d e f g h i j k l m n o p q r s t u v w x y z . , : ; ' ' { }

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

Начальный символ: p

Атрибуты:

Имя атрибутаТип значенияЦель введения
QМножество Состояния программы
?Множество Символы программы
q0Элемент множества Q Начальное состояние
q?Элемент множества QКонечное состояние
Функция, отображающая (Q - {q?}) x ? в ? x {-1, 0, +1} x QФункция переходов
метка Функция, отображающая цепочки букв в элементы мн-ва QТаблица состояний для операторных меток
символФункция, отображающая цепочки букв в элементы множества ?Таблица символов для символов ленты
следующееЭлемент множества Q Состояние,непосредственно следующее за оператором или списком операторов
d±1Направление
текст Цепочка буквИдентификатор
СодержаниеЭлемент множества QСостояние в начале выполнения оператора или списка операторов (унаследованный атрибут)


Синтаксические и семантические правила см. в таблица 1.



Таблица 1.
КомментарийСинтаксическое правилоПример Семантическое правило
Буквы1.1 ... 1.26A
a ... A
z
a ...(так же zтекст (A) = a для всех букв) текст (A) = z
Идентификаторы2.1 2.2I
A I
IA
m marilynтекст (I) = текст (A) текст (I) = текст(I) текст
Описания3.1D
алфавит I
алфавит

marilyn
определить символ (текст (I)) = новсимвол; включить символ (текст (I)) в ?
Описания3.2D
D, I
алфавит

marilyn, jayne, brigitta
определить символ (текст (I)) = новсимвол; включить символ (текст (I)) в ?
Оператор печати4.1S
печа- тать I
печатать "jayne"определить
(начало (S), s)= символ(текст (I)), 0, следующий (S)) для всех s
?; следующий (S) = новсимвол; включить

следующий (S) в Q.
Оператор сдвига4.2 S
сдви- нуться О на одну клетку
сдвинуться влево на одну клеткуопределить
(начало (S), s) = (s, d(0), следующий (S) для всех s
?; следующий (S) = новсимвол; включить следующий (S) в Q.
4.2.1 О
влево

влевоd(O) = -1.
4.2.2 О


вправо
вправоd(O) = +1.
Оператор перехода4.3S
перейти на I
перейти на bostonопределить
(начало (S), s)= (s, 0, метка(текст (I)) для всех s
?; следующий (S) = новсимвол; включить

следующий (S) в Q.
Пустой оператор4.4S
следующий (S) = начало (S)
Условный оператор5.1 S1
если символ на ленте I, то S2
еслисимвол на ленте marilyn , то печатать jayneопределить
(начало (S1), s)= (s, 0, метка (следующий (S2)) для всех s
? - символ (текст (I)); определить
(начало (S1), s)= (s, 0, метка (следующий (S2)) для s = символ (текст (I)); начало (S2) = новсимвол; следующий (S1) = следующий (S2); включить начало (S2) в Q.
Помеченный оператор5.2 S1
"I": S2
boston: сдвинуться влево на одну клеткуопределить метка (текст (I))= начало (S1): начало (S2)=начало (S1); следующий (S1)= следующий (S2)
Составной оператор5.3S
{L}
(печатать "jayne" перейти на bostonначало (L)=начало (S); следующий (S) = следующий (L).
Список опера- торов6.1 L
S
печатать "jayne"начало (L)=начало (S); следующий (L) = следующий (S).
6.2L1
L2; S
печатать "jayne" перейти на bostonначало (L2)=начало (L1); начало (S) = следующий (L2). следующий (L1) = следующий (S).
Программа7Р
D; L
алфавит marilyn, jayne, birgitta печатать "jayne"q=новсимвол; включить q0 в Q; начало (L)=q0; q?= следующий (L).
<


/p> Отметим, что каждому оператору S соответствует два состояния: начало (S) - состояние, соответствующее первой команде, входящей в оператор (если таковая имеется), являющееся унаследованным атрибутом символа S, и следующее (S) - состояние, "следующее" за оператором, или состояние, в которое попадает машина после нормального выполнения оператора. В случае оператора перехода, однако, программа не попадeт в состояние следующее (S), поскольку действие оператора состоит в передаче управления в другое место; о состоянии следующее (S) можно сказать, что оно следует за оператором "статически" или "текстуально" , а не "динамически" в ходе выполнения программы.

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

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

Создаeтся впечатление, что такое определение Тьюрингола приближает нас к желанной цели: придать точный смысл тем понятиям, которые встречаются в неформальном руководстве по языку для программиста, причeм сделать это нужно совершенно формально и однозначно.Другими словами, это определение, возможно, отвечает нашему образу мышления при изучении языка. Определение 4.1 оператора печати, например, можно легко перевести на естественный язык, написав

Оператор может иметь вид: печатать "I"

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


Содержание раздела