Системы автоматизации построения трансляторов

Дополнительные материалы: Семантика контекстно-свободных языков

Введение

Допустим, что нам нужно дать точное определение двоичной системы записи чисел. Это можно сделать многими способами. В данном разделе мы рассмотрим метод, который может быть использован и для других систем счисления. В случае двоичной системы этот метод сводится к определению, основанному на следующей констекстно-свободной (КС) грамматике.

B  0 B  1

L  B L  LB

N  L N  L.L

Пример 1.1.

Здесь терминальными символами являются ".", "0" и "1", нетерминальными - B, L и N, обозначающие соответственно бит, список битов и число. Двоичным числом будем считать любую цепочку терминальных символов, выводимую из N при помощи правил (пример 1.1). Эта грамматика в действительности выражает тот факт, что двоичное число представляет собой последовательность из одного или более нулей и единиц, за которой может следовать точка и еще одна последовательность нулей и единиц. Кроме того, грамматика приписывает каждому двоичному числу определенную древовидную структуру. Например, цепочка 1101.01 получает следующую структуру:

Рис. 1.2.

Естественно определять значение двоичной записи (пример 1.1) с помощью некоторого пошагового процесса, сопоставленного ее структуре (рис. 1.2); значение всей двоичной записи строится из значений отдельных частей. Это можно сделать, приписав каждому нетерминалу атрибуты следующим образом:

бит B имеет целочисленный атрибут "значение", обозначаемый v(B).

список битов L имеет целочисленный атрибут "длина", обозначаемый l(L). список битов L имеет целочисленный атрибут "значение", обозначаемый v(L).

число N имеет атрибут "значение", являющийся рациональным числом и обозначаемый v(N).

(Заметим, что у всех нетерминалов L по два атрибута; вообще говоря, каждому нетерминалу можно приписывать любое желаемое число атрибутов).

Грамматику (пример 1.1) можно теперь расширить так, чтобы каждому синтаксическому правилу отвечали семантические правила.

B  0         v(B) = 0

B  1         v(B) = 1 

L  B         v(L) = v(B); l(L) = 1

L1  L2B      v(L1) = 2v(L2) + v(B); l(L1) = l(L2) + 1

N  L         v(N) = v(L)

N  L1:L2     v(N) = v(L1) + v(L2)=2l(L2)

Пример 1.3.

(Индексы в четвертом и шестом правилах применяются для того, чтобы различать вхождения одноименных нетерминалов.). В этих семантических правилах значения атрибутов всех нетерминалов определяются через значения атрибутов их непосредственных потомков, так что окончательные значения определены для всех атрибутов. Предполагается, что смысл обозначений, использованных для записи семантических правил, понятен. Отметим, например, что символ "0" в семантическом правиле v(B) = 0 понимается не так, как символ "0" в синтаксическом правиле B 0. B первом случае "0" обозначает математическое понятие, а именно число нуль, во втором - некоторый символ, имеющий эллиптическую форму. B каком-то смысле, то, что эти два символа выглядят одинаково, - не более чем простое совпадение.

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

Рис. 1.4.

Таким образом, "1101.01" обозначает 13.25 (в десятичной записи).

Такой способ определения семантики КС-языков в сущности хорошо известен, так как он уже использовался несколькими авторами. Однако существует важное расширение этого метода. Именно это расширение и представляет для нас интерес.

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

символ B имеет атрибут "значение", являющийся рациональным числом и обозначаемый v(B).

символ B имеет целочисленный атрибут "масштаб ", обозначаемый s(B).

символ L имеет атрибут "значение", являющийся рациональным числом и обозначаемый v(L).

символ L имеет целочисленный атрибут "длина", обозначаемый l(L).

символ L имеет целочисленный атрибут "масштаб", обозначаемый s(L).

символ N имеет атрибут "значение", принимающий в качестве значений рациональные числа и обозначаемый v(N).

Эти атрибуты можно определить следующим образом:

Здесь при записи семантических правил принято следующее соглашение. Правая часть каждого правила представляет собой определение левой части, таким образом, s(B) = s(L) означает, что сначала должно быть вычислено s(L), а затем полученное значение следует присвоить s(B).

Важным свойством грамматики (таблица 1.1) является то, что некоторые из атрибутов, которым присваиваются значения, приписаны нетерминалам, стоящим в правой части соответствующего синтаксического правила, в то время как в 1.3 атрибуты левых частей семантических правил относились только к нетерминалам, стоящим в левой части синтаксического правила. Здесь мы используем как синтезированные атрибуты (вычисляемые через атрибуты потомков данного нетерминала), так и унаследованные атрибуты (вычисляемые через атрибуты предков). Синтезированные атрибуты вычисляются в древовидной структуре снизу вверх, а унаследованные - сверху вниз. Грамматика (таблица 1.1) включает синтезированные атрибуты v(B), v(L), l(L), v(N) и унаследованные атрибуты s(B) и s(L), так что при их вычислении необходимо проходить по дереву в обоих направлениях. Вычисление на структуре, соответствующей цепочке 1101.01, имеет вид:

Рис. 1.6.

Можно заметить, что атрибуты "длина" символов L, стоящих справа от точки, должны быть вычислены снизу вверх до того, как будут вычислены (сверху вниз) атрибуты "масштаб" и атрибуты "значение" (снизу вверх).

Грамматика (таблица 1.1), вероятно, не является "наилучшей возможной" грамматикой для системы двоичной записи, но похоже, что она лучше согласуется с нашей интуицией, чем грамматика (пример 1.3). (Грамматика, которая более точно соответствует нашему традиционному толкованию двоичной нотации, содержит другое множество правил вывода. Эти правила сопоставляют цепочке битов справа от точки иную структуру, вследствие чего атрибут "длина", не играющий принципиальной роли, становится ненужным.)

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

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

Формальные свойства

Придадим теперь идее использования синтезированных и унаследованных атрибутов более точную и более общую форму.

Пусть имеется КС-грамматика G = (V, N, S, P), где V - (конечный) алфавит терминальных и нетерминальных символов; - множество нетерминальных символов; S N - "начальный "символ, не входящий в правые части правил, и P - множество правил.

Семантические правила дополняют G следующим образом. С каждым символом X V связывается конечное множество атрибутов A(X). A(X) разбивается на два непересекающихся множества: множество синтезированных атрибутов A₀(X) и множество унаследованных атрибутов A₁(X). Множество A₁(S) должно быть пустым (то есть начальный символ S не должен иметь унаследованных атрибутов); аналогично, множество A₀(X) пусто, если X - терминальный символ. Каждый атрибут R из множества A(X) имеет (возможно, бесконечное) множество значений VR. Для каждого вхождения X в дерево вывода семантические правила позволяют определить одно значение из множества VR для соответствующего атрибута.

Пусть P состоит из m правил, и пусть p-е правило имеет вид

X_p0  X_p1X_p2...X_pnp ;

Пример 2.1.

где np > 0, X_p0 N и X_pj V для 1 j n_p. Семантическими правилами называются функции f_pjR, определ_нные для всех 1 p m, 0 j n_p и некоторых A₀(X_pj), если j = 0, или A₁(X_pj), если j > 0. Каждая такая функция представляет собой отображение из V₁ x V₂ x ... x V_t в VR для некоторого t = t(p, j, ) > 0, где все _i = _i(p, j, ) являются атрибутами некоторых X_pki , при 0 k_i = k_i(p, j, ) n_p, 1 i t. Другими словами, каждое семантическое правило отображает значения некоторых атрибутов символов и значение некоторого атрибута символа .

Грамматика (таблица 1.1), например, представляется в виде G = ({0, 1, ".", B, L, N}, {B, L, N}, N, {B 0, B 1, L B, L LB, N L, N L.L}).

Атрибутами здесь являются

A₀(B) = {v},    A₁(B) = {s};

A₀(L) = {v, l},        A₁(L) = {s};

A₀(N) = {v},    A₁(N) =

и A₀(x) = A₁(x) =

для x {0, 1, .}. Множествами значений атрибутов будут V_v ={рациональные числа}, V_s = V_l = {целые числа}. Типичным примером правил вывода служит четвeртое правило X₄₀ X₄₁X₄₂ , где n₄ = 2, X₄₀ = X₄₁ = L, X₄₂ = B. Так же типично и семантическое правило f_40v, соответствующее этому правилу вывода. Оно определяет v(X₄₀) через другие атрибуты; в данном случае f_40v отображает Vv x Vv в Vv согласно формуле f_40v(x, y) = x + y. (Это есть не что иное, как правило v(L₁) = v(L₂) + v(B) из (таблица 1.1); используя довольно громоздкую запись, введeнную в предыдущем абзаце, получим:

t(4, 0, v) = 2, ₁(4, 0, v) = ₂(4, 0, v) = v, k₁(4, 0, v) = 1, k₂(4, 0, v) = 2).

Семантические правила используются для сопоставления цепочкам КС языка"значения" следующим образом¹⁾ . Для любого вывода терминальной цепочки t из S при помощи синтаксических правил построим обычное дерево вывода. А именно, корнем дерева будет S, а каждый узел помечается либо терминальным символом, либо нетерминалом X_p0, соответствующим применению p-го правила для некоторого p; в последнем случае у этого узла будет np непосредственных потомков.

Рис. 2.2.

Пусть теперь X - метка некоторого узла дерева и пусть R A(X) - атрибут символа X. Если A₀(X), то X = X_p0 для некоторого p, если же A₁(X), то X = X_pj для некоторых j и p. В обоих случаях дерево "в районе" этого узла имеет вид (рис. 2.2). По определению атрибут имеет в этом узле значение v, если в соответствующем семантическом правиле

f_pj:V₁x ... x V_tV

все атрибуты ₁, ... , _t уже определены и имеют в узлах с метками X_pk1 , ... , X_pkt значения v₁, ... , v_t соответственно, а v = f_pj(v₁, ... , v_t). Процесс вычисления атрибутов на дереве продолжается до тех пор, пока нельзя будет вычислить больше ни одного атрибута. Вычисленные в результате атрибуты корня дерева представляют собой "значение", соответствующее данному дереву вывода (рис. 1.6).

Естественно потребовать, чтобы семантические правила давали возможность вычислить все атрибуты произвольного узла в любом дереве вывода. Если это условие выполняется, будем говорить, что семантические правила заданы корректно²⁾ . Поскольку деревьев вывода, вообще говоря, бесконечно много, важно уметь определять по самой грамматике, являются ли корректными еe семантические правила.

Отметим, что этот метод определения семантики обладает такой же мощностью, как и всякий другой возможный метод, в том смысле, что значение любого атрибута в любом узле может произвольным образом зависеть от структуры всего дерева. Предположим, например, что в КС грамматике всем символам, кроме S, приписано по два унаследованных атрибута: l ("положение") и t ("дерево"), а всем нетерминалам, кроме того, по одному синтезированному атрибуту s ("поддерево"). Значениями l будут конечные последовательности положительных целых чисел , определяющие местонахождение узла в дереве в соответствии с системой обозначения Дьюи. Атрибуты t и s представляют собой множество упорядоченных пар (l, X), где l - положение узла, а X - символ грамматики, обозначающий метку узла с положением l. Семантическими правилами для каждого синтаксического правила (пример 2.1) служат

Следовательно, для дерева (рис. 1.2), например, мы имеем

s(N) = {(1, L), (2, ⋅), (3, L),

   (1.1, L), (1.2, B), (3.1, L), (3.2, B),

   (1.1.1, L), (1.1.2, B), (1.2.1, 1), (3.1.1, B), (3.2.1, 1),

   (1.1.1.1, L), (1.1.1.2, B), (1.1.2.1, 0), (3.1.1.1, 0),

   (1.1.1.1.1, B), (1.1.1.2.1, 1), (1.1.1.1.2.1, 1)}.

Ясно, что эта запись содержит всю информацию о дереве вывода. Согласно семантическим правилам (2.4), атрибут t во всех узлах (кроме корня) представляет собой множество, характеризующее всe дерево вывода; атрибут l определяет местонахождение этих узлов. Отсюда сразу следует, что любая мыслимая функция, определ_нная на дереве вывода, может быть представлена как атрибут произвольного узла, поскольку эта функция имеет вид f(t, l), для некоторого f. Аналогично, можно показать, что для определения значения, связанного с произвольным деревом вывода, достаточно только синтезированных атрибутов, поскольку синтезированный атрибут w, вычисляемый по формуле

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

Проверка на зацикленность

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

Пусть T - произвольное дерево вывода, соответствующее данной грамматике; метками концевых узлов могут быть только терминальные символы, корню же разрешим иметь меткой не только аксиому, но и любой символ из V . Тогда можно определить ориентированный граф D(T), соответствующий T, взяв в качестве его узлов упорядоченные пары (X, ), где X - узел дерева T, а - атрибут символа, служащего меткой узла X. Дуга из (X₁; 1) в (X₂, ₂) проводится в том и только в том случае, когда семантическое правило, вычисляющее атрибут ₂, непосредственно использует значение атрибута ₁. Например, если T - дерево (рис. 1.2), а в качестве семантических правил взяты правила (таблица 1.1), то орграф D(T) будет иметь такой вид:

Рис. 3.1.

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

Ясно, что семантические правила являются корректными тогда и только тогда, когда ни один из орграфов D(T) не содержит ориентированного цикла. Дело в том, что если в графе нет ориентированных циклов, то можно применить хорошо известную процедуру, позволяющую присвоить значения всем атрибутам. Если же в некотором графе D(T) есть ориентированный цикл, то ввиду того что грамматика не содержит бесполезных правил, можно утверждать, что существует ориентированный цикл в некотором графе D(T), у которого меткой корня дерева T служит S. Для такого дерева T все атрибуты вычислить не уда_тся. Таким образом, задача "Являются ли семантические правила корректным?" сводится к задаче "Содержат ли орграфы D(T) ориентированные циклы?"

Каждый орграф D(T) можно рассматривать как суперпозицию меньших орграфов Dp, соответствующих правилам X_p0 X_p1 ... X_pn грамматики, 1 p m. В обозначениях разд. 2 орграф D_p имеет узлы (X_pj, ) для 0 j n_p, A(X_pj) и дуги из (X_pki , ) в (X_pj , ) для 0 j n_p, A₀(X_pj), если j = 0, A₁(X_pj ), если j > 0, k_i = k_i(p, j, ), i = i(p, j, ), 1 i t(p, j, ). Другими словами, Dp отражает связи, которые порождают все семантические правила, соответствующие p-му синтаксическому правилу. Например, шести правилам грамматики (таблица 1.1) соответствуют шесть следующих орграфов:

Рис. 3.2.

Орграф (рис. 3.1) получается в результате "объединения" таких подграфов. Вообще, если T имеет в качестве метки корня терминал, D(T) не содержит дуг. Если корень дерева T помечен нетерминальным символом, T имеет вид

Рис. 3.3.

для некоторого p, где T_j - дерево вывода, у которого корень помечен символом X_pj, где 1 j n_p. В первом случае говорят, что T - дерево вывода типа 0, во втором случае T называется деревом вывода типа р. В соответствии с этим определением для того, чтобы по D_p, D(T₁), ... , D(T_np ) построить D(T), нужно для всех j, 1 j n_p совместить узлы, соответствующие атрибутам символа X_pj графа _Dp с соответствующими узлами (отвечающими тем же атрибутам корня дерева T_j) в графе D(T_j ).

Для проверки того, содержит ли граф D(T) ориентированный цикл, нам понадобится ещe одно понятие. Пусть p - номер правила вывода. Обозначим через G_j произвольный орграф (1 j np), множество узлов которого является подмножеством множества A(X_pj) атрибутов символа X_pj. Пусть

D_p[G₁,..., G_np ]

Пример 3.4.

орграф, полученный из D_p добавлением дуг, идущих из (X_pj, ) в (X_pj, ₀), если в графе G_j есть дуга из в ₀

Например, если

и если D₄ - ориентированный граф из (3.2), то D₄(G₁, G₂) имеет вид

Рис. 3.4.

Теперь можно воспользоваться следующим алгоритмом. Для любого X V S(X) будет некоторым множеством ориентированных графов с узлами из A(X). Сначала для всех X N S(X) пусто, а для X = N S(X) состоит из единственного графа с множеством узлов A(X) и не содержащего дуг. Будем добавлять к множествам S(X) новые орграфы при помощи следующей процедуры до тех пор, пока в S(X) не перестанут появляться новые элементы. Выберем целое p; 1 p m и для каждого j, 1 j np, выберем орграф D_0j S(Xpj). Затем добавим в S(X_p0) орграф с множеством узлов A(X_po), обладающий тем свойством, что в нeм дуга от к 0 идeт тогда и только тогда, когда в орграфе

существует ориентированный путь из (X_p0; ) в (X_p0; '): Ясно, что этот процесс рано или поздно закончится и новые орграфы перестанут порождаться, поскольку вообще существует лишь конечное число ориентированных графов. В случае грамматики (таблица 1.1) алгоритм построит следующие множества:

Пусть T - дерево вывода с корнем X, и пусть D'(T) - ориентированный граф с множеством узлов A(X), у которого есть дуга из в ' тогда и только тогда, когда в D(T) существует ориентированный путь из (X, ) в (X, '). Покажем, что после окончания работы описанного выше алгоритма для всех X V S(X) - это множество всех D'(T), где T - дерево вывода с корнем X ⁴⁾ . Действительно, построение не добавляет к S(X) новых ориентированных графов, не являющихся D'(T). Алгоритм можно даже легко обобщить так, чтобы для каждого графа из S(X) он печатал на выходе соответствующее дерево вывода T. Обратно, если T - дерево вывода, мы можем показать индукцией по числу узлов дерева T, что D'(T) принадлежит некоторому множеству S(X). В противном случае T должно иметь вид (3.3) и D(T) "составлен" из . По индукции и вследствие того, что при j j' из D(T_j) в D(T_j' ) не проходит дуг вне D_p, дуги в , составляющей рассматриваемый путь графа D(T), можно заменить соответствующими дугами в , где . Поэтому ориентированный граф, включаемый в S(X_p0) на базе , просто совпадает с D'(T).

Вышеприведeнный алгоритм решает задачу, поставленную в этом разделе.

Теорема. Семантические правила, добавленные к грамматике так, как это сделано в разд. 2, являются корректными тогда и только тогда, когда ни один из ориентированных графов (3.5) ни при каком выборе p и не содержит ориентированных циклов.

Доказательство. Если (3.5) содержит ориентированный цикл, то, как было показано выше, некоторый D(T) содержит ориентированный цикл. Наоборот, если T - дерево с наименьшим возможным числом улов, такое, что D(T) содержит ориентированный цикл, то T должно иметь вид (рис. 3.3), а D(T) "составляется" из . Из минимальности T следует, что ориентированный цикл включает по меньшей мере одну дугу графа D_p, и, следовательно, можно, рассуждая, как выше, все дуги, образующие этот цикл и лежащие в одном из графов , заменить дугами графа (3.5).

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

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

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

Алфавит пробел, единица, нуль, точка;

печатать "точка"; перейти на выполнить;

тест: если символ на ленте _единицаї, то

{печатать "нуль";                                                    (4.1)

  выполнить: сдвинуться влево на одну клетку;

  перейти на тест};

печатать "единица";

возврат: сдвинуться вправо на одну клетку;

если символ на ленте "нуль", то перейти на возврат.

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

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

• множества "состояний" Q,
• множества "символов" Σ
• начального "состояния" q₀ Q
• конечного "состояния" q₁ 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, a₀, a₁, a₂, a₃,...

Пример 4.2.

элементов алфавита Σ следующим образом. В произвольный момент вычисления существует "текущее состояние" q Q и целочисленная величина "положение читающего устройства" p. Вначале q = q₀ и p = 0. Если q q_∞ и если (q, a_p) = (s', k', q'), то следующим шагом вычисления будет замена значения p на p + k, q на q' и a_p на s'. Если q = q_∞, вычисление заканчивается. (Вычисление может не закончиться; для программы (4.1) это произойдeт тогда и только тогда, когда a_j="единица" для всех _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

Атрибуты:

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

Отметим, что каждому оператору 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, безотносительно к тому, какой символ находится в обозреваемой клетке. После этого выполнение программы продолжится с новой инструкции, которая определяется (другими правилами) как следующая за данным оператором

Обсуждение

Идея определения семантики с помощью синтезированных атрибутов, связанных с каждым нетерминальным символом и семантических правил, сопоставленных каждому правилу вывода, принадлежит Айронсу [6, 7]. Первоначально каждый нетерминальный символ имел ровно один атрибут, называвшийся его "трансляцией" . Эта идея использовалась Айронсом и позже другими авторами, особенно Маклюром [14] при построении "синтаксически управляемых компиляторов" , переводивших языки программирования в машинный код.

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

Автору к настоящему времени известно несколько работ, внесших принципиальный вклад в решение задачи формального описания семантики языков программирования. Это определение Алгола 60 средствами расширенного алгоритма Маркова, данное Дебаккером [1], определение Алгола 60 с помощью λ-исчисления, принадлежащее Ландину [9, 10, 11] (см. также Бeм [2, 3], определение Микро-Алгола с помощью рекурсивных функций, применяемых к программе и к _векторам состоянийї, принадлежащее Маккарти [12] (см. также Маккарти и Пэинтер [13]; определение языка Эйлер средствами семантических правил, применяемых во время синтаксического анализа программы, предложенное Виртом и Вебером [16], и определение языка PL=I, данное Венской лабораторией фирмы IBM и основанное на работе Маккарти и Ландина, а также на понятии абстрактной машины, введ_нном Элготом [4, 5]. Наиболее существенная разница между предшествующими методами и описанием языка Тьюрингол, привед_нным в таблица 1, состоит в том, что остальные определения представляют собой довольно сложные процессы, применяемые ко всей программе; можно сказать, что человек, прежде чем он поймeт описание языка, должен будет понять, как устроен его компилятор. Эта трудность особенно ощутима в работе Дебаккера, определяющего машину, подобную Марковским алгоритмам, но значительно более сложную. Эта машина имеет около 800 команд. На каждом шаге вычисления машины нужно выполнять последнюю применимую команду, так что мы не можем проверить, нужно ли выполнить команду номер 100, до тех пор, пока не убедимся, что остальные 700 команд неприменимы. Кроме того, в процессе работы машины список пополняется новыми командами. Ясно, что читателю чрезвычайно трудно понять работу такой машины или формально доказать ee основные свойства. Описание Тьюрингола, напротив, определяет каждую конструкцию языка только через еe "непосредственное окружение" , сводя тем самым к минимуму взаимосвязи между определениями разных частей языка. Определение составных операторов, операторов перехода и т.д. не влияет существенно на определение оператора печати; например, любое из правил 4.1, 4.2, 4.3, 4.4, 5.1, 5.3 можно выбросить, и получится строгое определение другого языка. Такая локализация и разделение семантических

правил помогает сделать определение более понятным и кратким. Хотя определения остальных авторов, упомянутые выше, не так сложны, как определение Дебаккера, в их работах всe-таки присутствуют относительно сложные зависимости между отдельными частями определения. Рассмотрим, например, формальное определение языка Эйлер, данное Виртом и Вебером [16]. Это краткое описание весьма сложного языка и потому, безусловно, оно является одним из наиболее удачных формальных определений. И всe же, несмотря на то, что Вирт и Вебер проверили своe определение с помощью моделирования на вычислительной машине, весьма вероятно, что некоторые черты Эйлера удивят его создателей. Следующая программа на Эйлере синтаксически и семантически правильна, хотя после метки L нигде не встречаются двоеточия:

Результатом работы этой программы будет 1, 2, 2, 3! Промахи такого рода не являются неожиданностью при алгоритмическом определении языка. При использовании методов разд. 4 подобные ошибки менее вероятны.

Есть основания утверждать, что ни одна из предыдущих схем (формального определения семантики) не в состоянии дать такого же краткого и простого для понимания определения Тьюрингола, как то, которое представлено выше. Кроме того (хотя детали окончательно не проработаны), оказывается, что Алгол 60, Эйлер, Микро- Алгол и PL=1 также можно определить методами разд. 4, причeм все преимущества по сравнению с остальными методами сохраняются. Правда, здесь автор не может быть беспристрастным судьeй, поэтому для подтверждения такой точки зрения требуется некоторый дополнительный опыт.

Отметим, что семантические правила в том виде, в котором они даны в настоящей статье, не зависят от конкретно выбранного метода синтаксического анализа. На самом деле они привязаны даже к конкретным формам синтаксиса. Единственное от чего зависят семантические правила - это имя нетерминала в левой части синтаксического правила и имени нетерминалов в правой его части. Конкретные знаки пунктуации и порядок, в котором нетерминалы располагаются в правых частях правил, несущественны с точки зрения семантических правил. Таким образом, рассматриваемое здесь определение семантики хорошо сочетается с идеей Маккарти об "абстрактном синтаксисе" [12, 13].

Когда синтаксис неоднозначен в том смысле, что некоторые цепочки языка имеют более одного дерева вывода, семантические правила дают для каждого дерева вывода своe "значение" . Предположим, например, что к грамматике (1.3) добавлены правила

Грамматика в результате становится синтаксически неоднозначной, но остаeтся по-прежнему семантически однозначной, поскольку атрибут v(N) имеет одно и то же значение для всех деревьев вывода. С другой стороны, если изменить правило 5.2 определения Тьюрингола с S I : S на S S : I, грамматика станет неоднозначной как синтаксически, так и семантически.

¹⁾ На самом деле значение здесь приписывается дереву вывода цепочки, а не ей самой. Если грамматика неоднозначна, это не одно и то же (см. последнюю страницу статьи). - Прим. перев.
²⁾ В оригинале well defined. - Прим. ред.
³⁾ В правой части формулы нужно добавить ещe член . - Прим. ред.
⁴⁾ Если, как определялось выше, концевыми узлами T могут быть только терминальные символы, то S(X) будет содержать все D'(T), а не совпадать со множеством всех D'(T). Чтобы не вносить в последующие построения несущественных исправлений, проще в этом абзаце считать T любым деревом вывода с корнем X (то есть не обязательно продолженным до терминалов). - Прим. ред.