Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Все_пособие_редактир.doc
Скачиваний:
248
Добавлен:
31.10.2018
Размер:
3 Мб
Скачать
☆

9.9.1 Восходящее вычисление наследуемых атрибутов.

Удаление внедренных действий из схемы трансляции

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

Это преобразование вставляет в базовую грамматику новые нетерминалы-маркеры, порождающие λ, то есть каждое вставленное действие заменяется отдельным маркером М и добавляется действие в конец продукции М → λ. Например, схема трансляции

Е → T R

R → + Т {print(' + ')} R | - Т {print(‘ – ‘) } R | λ

T → num { print(num.val) }

преобразуется с помощью нетерминалов М и N в

Е → T R

R → +T M R | - T N R | λ

Т → num {print(num.val)}

М → λ { print(' + ') }

N → λ { print(‘ - ') }

Грамматики в этих двух схемах трансляции задают один и тот же язык, и, построив дерево разбора с дополнительными узлами для действий, можно показать, что дейст­вия выполняются в одном и том же порядке. Действия в преобразованной схеме транс­ляции завершают продукции, так что они могут быть выполнены непосредственно перед сверткой правой части в процессе восходящего разбора.

9.9.2 Наследование атрибутов в стеке синтаксического анализатора

Восходящий синтаксический анализатор сворачивает правую часть продукции А → ХY удалением X и Y с вершины стека синтаксического анализатора и заменой их на А. Предположим, что X имеет синтезируемый атрибут Х.s (который хранится в стеке вместе c Х).

Поскольку значение Х.s находится в стеке перед выполнением любой свертки в поддереве ниже Y, это значение может быть наследовано Y. Таким образом, если насле­дуемый атрибут Y.i определен правилом копирования Y.i:=X.s, то значение Х.s может быть использовано там, где требуется Y.i. Правила копирования играют важную роль в вычислении наследуемых атрибутов в процессе восходящего синтаксиче­ского анализа.

Пример 39

Тип идентификатора может быть передан с помощью правил копирования и наследуемых атрибутов, как показано на рис. 60. Рас­смотрим действия восходящего синтаксического анализатора при входной строке real р, q, r

Значение атрибута Т.tуре можно получить при ис­пользовании продукции для L. Схема трансляции имеет следующий вид

D → Т

{ L.in := T.type }

L

Т → int

{ T.type := integer }

T → real

{ T.type := real}

L →

{ L1.in := L.in }

L1,id

{addtype(id.entty ,L.in) }

L → id

{ addtype(id.entry, L.in) }

Рис.60. L.in=T.type в каждом узле для L

Если проигнорировать действия в приведенной выше схеме трансляции, то последо­вательность шагов синтаксического анализатора при входном потоке real р, q, r будет иметь вид, представленный на рис.61.

Для ясности вместо состояния стека здесь пока­зан соответствующий символ грамматики, а вместо лексем id — соответствующие им идентификаторы.

Предположим, что стек синтаксического анализатора реализован в виде пары массивов — state и val. Если state[i] — грамматический символ X, то в val[i] хранится синтезируемый атрибут X.s.

Входной поток

Состояние стека

Использованная продукция

real p , q , r

-

p , q , r

real

p , q , r

T

T → real

, q , r

Т р

, q , r

T L

L → id

q , r

T L,

, r

T L,q

, r

T L

L → L, id

r

T L,

T L,r

T L

L → L, id

D

D → T L

Рис. 61. При свертке правой части продукции для L, Т находится непосредственно под правой частью

Содержимое массива state показано на рис. 61. Всякий раз, когда сворачивается правая часть продукции L, в стеке непо­средственно под правой частью располагается Т. Этот факт можно использовать для дос­тупа к значению атрибута Т.type.

Другая реализация (рис.62) использует информацию о местоположении Т.type в стеке val относительно его вершины. Пусть top и ntор указывают верхний элемент стека непосред­ственно перед сверткой и после нее.

Продукция

Фрагмент кода

D → TL;

T → int

val[ntop] := integer

T → real

val[ntop] := real

L → L , id

addtype(val[top], val[top-3])

L → id

addtype(val[top], val[top-1])

Рис. 62. Значение T.type используется вместо L.in

Из правил копирования, определяющих L.in, получаем, что вместо L.in можно использовать Т.type.

При применении продукции L → id на вершине стека val находится id.entry, а непо­средственно под ним — T.type. Следовательно, addtype(val[top], val[top-1]) эквива­лентно addtype(id.entry, T.type). Аналогично, поскольку правая часть продукции L → L, id имеет три символа, T.type при ее свертке находится в val[top-3]. Правила копирования для атрибута L.in таким образом устраняются, поскольку вместо него используется значение T.type из стека.