Пример 36

Синтезируемые атрибуты в стеке синтаксического анализатора

Восходящее выполнение S-атрибутных определений

Для определения трансляций можно исполь­зовать синтаксически управляемые определения. Рассмотрим реализацию таких трансляторов. Создание транслятора для произвольного синтаксически управ­ляемого определения может оказаться сложной задачей; однако имеются большие классы полезных синтаксически управляемых определений, трансляторы для которых строятся достаточно просто. К таким классам относятся S-атрибутные определения, т.е. синтаксически управляемые определения, в ко­торых применяются исключительно синтезируемые атрибуты.

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

Восходящий синтаксический анализатор для хранения информации о разобранных поддеревьях использует стек. Можно использовать дополнительные поля в стеке синтаксического анализатора для хранения значений синтезируемых атрибутов. Пример стека синтаксического анализатора с пространством для хране­ния одного значения атрибута показан на рис. 55. Стек реализован с по­мощью пары массивов — state и val. Каждая запись state является указателем (или ин­дексом) на запись в таблице LR(1)-анализа. Если символ i -го состояния — А, то val[i] содержит значение атрибута, связанного с узлом дерева разбора, соответствующим этому А.

	state	val
	..…	……
	X	X.x
	У	Y.y
top→	Z	Z.z
	..…	..…

Рис. 55. Стек синтаксического анализатора с полем для синтезируемого атрибута

Текущая вершина стека определяется указателем top. Считаем, что синтези­руемые атрибуты вычисляются непосредственно перед каждой сверткой. Предположим, что с продукцией А → XYZ связано семантическое правило

А.а:=f(X.x,Y.y,Z.z). Перед Сверткой XYZ в А значение атрибута Z.z находится в val[top], значение Y.y — в vaI[top-1] иX.x — в val[top-2]. Если символ не имеет атрибутов, то соответствующая запись в массиве val не определена. После свертки top уменьшается на 2, состояние, соответствую­щее А, помещается в state[top] (т.е. на место Х.х), а значение синтезируемого атрибута А.а — в val[top].

Рассмотрим синтаксически управляемое определение калькулятора, приведен­ное на рис. 49. Синтезируемые атрибуты в аннотированном дереве разбора на рис. 50 могут быть вычислены LR-анализатором в процессе восходящего разбора входной строки 3*5 + 4n. Как и ранее, полагаем, что лексический анализатор обеспечивает значение атрибута digit. lexval — числовое значение каждой лексемы, представляющей цифру. При переносе синтаксическим анализатором лексемы digit в стек, он помещается в state[top], а значение атрибута — в val[top].

Для вычисления атрибутов модифицируем синтаксический анализатор, чтобы он выполнял фрагменты кода, пока­занные на рис. 56, непосредственно перед выполнением соответствующей свертки. Можно связать вычисление атрибутов со свертками, поскольку каждая свертка определяет используемую продукцию. Фрагменты кода получены из семантиче­ских правил на рис. 40 путем замены каждого атрибута позицией в массиве val.

Продукция	Фрагмент кода
L → Е n	print(val[top])
E → E 1 + T	val[ntop]:=val[top-2]+val[top]
E → Т
Т → T 1 * F	val[ntop]:=val[top-2]*val[top] i
T → F
F → (E)	val[ntop]^::=val[top-1]
F→ digit

Рис. 56. Реализация калькулятора с помощью LR-анализатора

Фрагменты кода не показывают, каким образом происходит работа с ntop и top. При свертке продукции с r символами в правой части значение ntop устанавливается равным tор-r+ 1, а после выполнения фрагмента кода top становится равным ntop.

Последовательность действий, выполняемых синтаксическим ана­лизатором для входной строки 3*5 + 4 n показана на рис. 57. В таблице представлено содержимое полей state и val стека после каждого действия синтаксического анализатора. Состояние стека заменяется соответствующим грамматическим символом, и вместо лексемы digit используется введенная цифра.

Вход	state	val	Используемая продукция
3*5+4 n	_	_
*5+4 n	3
*5+4 n	F		F → digit
*5+4 n	T		T → F
*5+4 n	T *	3 _
+4 n	T * 5	3 _	F → digit
+4 n	T * F	3 _ 5
+4n	T		T → T * F
+4 n	E		E → T
+4 n	E +	15 _
n	E + 4	15 _ 4
n	E + F	15 _ 4	F → digit
	E + T	15 _ 4	T → F
n	E		E → E + T
	E n	19 _
	L		L → E n

Рис. 57. Действия транслятора для входной строки 3*5 +4n

Рассмотрим последовательность событий для входного символа 3. На первом шаге синтаксический анализатор переносит в стек состояние, соответствующее лексеме digit (значение ее атрибута равно 3). Состояние представлено тройкой; в поле val находится значение 3. На следующем шаге синтаксический анализатор выполняет свертку в соот­ветствии с продукцией F→ digit и семантическое правило F.val:= digit. lexval. Третий шаг состоит в свертке по продукции T → F. С этой продукцией не связан никакой фраг­мент кода, поэтому массив val остается неизменным. После каждой свертки вершина стека val содержит значение атрибута, связанное с левой частью сворачиваю­щей продукции. При реализации фрагменты кода выполняются непосредственно перед сверткой. Таким образом, можно связать с продукцией действие, выполняемое в процессе свертки в соответствии с данной продукцией.

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