Пример 39

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

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

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

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

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

Е → 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(‘ - ') }

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

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

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

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

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

D → Т	{ L.in:= T.type }
L
Т → int	{ T.type:= integer }
T→ real	{ T.type:= real}
L →	{ L 1 .in:= L.in }
L 1,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 из стека.

Дата добавления: 2014-12-27