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



             

Определение атрибутных грамматик


Атрибутной грамматикой называется четверка AG = (G, AS, AI, R), где

  1. G = (N, T, P, S) - приведенная КС-грамматика;
  2. AS - конечное множество синтезируемых атрибутов;
  3. AI - конечное множество наследуемых атрибутов, AS
    AI =
    ;
  4. R - конечное множество семантических правил.

Атрибутная грамматика AG сопоставляет каждому символу X из N

T множество AS(X) синтезируемых атрибутов и множество AI (X) наследуемых атрибутов. Множество всех синтезируемых атрибутов всех символов из N
T обозначается AS, наследуемых - AI . Атрибуты разных символов являются различными атрибутами. Будем обозначать атрибут a символа X как a(X). Значения атрибутов могут быть произвольных типов, например, представлять собой числа, строки, адреса памяти и т.д.

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

X1X2 ... Xn. Атрибутная грамматика AG сопоставляет каждому правилу p из P конечное множество R(p) семантических правил вида

a(Xi) = f(b(Xj), c(Xk), ... , d(Xm))

где 0

j, k, ... , m
n, причем 1
i
n, если
a(X_i) \in A_I (X_i)
(то есть a(Xi) - наследуемый атрибут), и i = 0, если
a(X_i) \in A_S(X_i)
(то есть a(Xi) - синтезируемый атрибут).

Таким образом, семантическое правило определяет значение атрибута a символа Xi на основе значений атрибутов b, c, . . . , d символов Xj , Xk, . . . , Xm соответственно.

В частном случае длина n правой части правила может быть равна нулю, тогда будем говорить, что атрибут a символа Xi "получает в качестве значения константу".

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

Пример 5.5. Рассмотрим атрибутную грамматику, позволяющую вычислить значение вещественного числа, представленного в десятичной записи. Здесь N = {Num, Int, Frac}, T = {digit, .}, S = Num, а правила вывода и семантические правила определяются следующим образом (верхние индексы используются для ссылки на разные вхождения одного и того же нетерминала):




Содержание  Назад  Вперед