5. Реализация перевода с использованием атрибутных транслирующих грамматик

5.1. Реализация перевода нисходящими методами

Рассмотрим построение L-атрибутного детерминированного процессора с магазинной памятью, сокращенно ДМП-процессора, реализующего перевод, определяемый L-атрибутной транслирующей грамматикой в форме простого присваивания, входной грамматикой которого является LL(I)-грамматика.

Рассмотрим транслирующую грамматику, описывающую перевод оператора цикла for языка Pascal:

(1) F for i := E S E {нач_ц} do Op {кон_ц}

(2) S to

(3) S downto

(4) E c

(5) Op i := c

(6) Op F

Управляющая таблица LL(1)-анализатора, реализующего цепочечный перевод, описываемый данной транслирующей грамматикой, представлена на рис. 5.1.

	for	I	:=	to		downto	c	do	ε
F	ЗАМ,1
S				ЗАМ,2		ЗАМ,3
E							ЗАМ,4
Op	ЗАМ,6	ЗАМ,5
for	ВЫБР
i		ВЫБР
:=			ВЫБР
to				ВЫБР
downto						ВЫБР
c							ВЫБР
do								ВЫБР
{нач_ц}	ВЫДАЧА {нач_ц}
{кон_ц}	ВЫДАЧА {кон_ц}
									Допуск

Рис. 5.1

Здесь элемент ЗАМ, <номер правила> обозначает замену верхнего символа магазина по правилу с указанным номером, элемент ВЫБР обозначает выброс верхнего символа магазина, элемент ВЫДАЧА – выдачу операционного символа на выходную ленту.

Дополним эту транслирующую грамматику атрибутами:

(1) F for i_n := E_v1 S_p E_v2 {нач_ц}_{q1,q2,q3,q4,m1,m2} do Op {кон_ц}_q5,q6,q7,q8

q1, q5 n (n – имя переменной цикла)

q2 v1 (v1 – синтезированный атрибут, начальное условие цикла)

q3, q6 p (p – синтезированный атрибут для обозначения направления изменения переменной цикла)

q4 v2 (v2 – синтезированный атрибут, конечное условие цикла) m1,m2 NewLabel() (m1 – метка начала цикла, m2 – метка конца цикла)

q7 m1; q8 m2

(2) S_q to_p

q p (p = inc)

(3) S_q downto_p

q p (p = dec)

(4) E_q с_p

q p (p – значение константы)

(5) O_p i _p1:= c_p2 {Присвоить}_q1,q2

q1 p1 (p1 – имя переменной); q2 p2 (p2 – значение константы)

(6) Op F

Операционный символ {нач_ц} служит для представления в выходной цепочке следующей последовательности действий:

1. присваивание начального значения переменной цикла (mov q1, q2);

2. установка метки начала цикла (m1:);

3. проверка условия и в случае его невыполнения переход на метку конца цикла (cmp q1, q3; для q4 =inc – jg m2, для q4 = dec – jl m2).

С помощью операционного символа {кон_ц} может быть оформлена (после разбора входной последовательности, соответствующей телу цикла) заключительная часть цикла:

1. увеличение или уменьшение на 1 переменной цикла (q6 q5);

2. переход на метку начала цикла (jmp q7);

3. установка метки конца цикла (q8:).

Проектирование L-атрибутного ДМП-процессора начинается с построения ДМП-процессора, реализующего цепочечный перевод, описываемый соответствующей транслирующей грамматикой перевода. Затем каждый магазинный символ полученного таким образом ДМП-процессора дополняется множеством полей для представления его атрибутов, а управляющая таблица – действиями по вычислению атрибутов и записи их в соответствующие поля. Магазинный символ с n атрибутами представляется в магазине n + 1 ячейками, верхняя из которых содержит имя символа, а остальные – поля для атрибутов. Поля магазинного символа доступны для записи и извлечения атрибутов от момента вталкивания символа в магазин до момента его выталкивания из магазина.

Начальная конфигурация L-атрибутного ДМП-процессора следующая: в магазине находится маркер дна и начальный символ грамматики, поля начального символа грамматики, соответствующие унаследованным атрибутам, заполняются начальными значениями атрибутов, которые задаются L-атрибутной грамматикой, а в поля, соответствующие синтезированным атрибутам, заносятся пустые указатели.

F

Рис. 5.2

В нашем примере начальный символ грамматики не имеет атрибутов, следовательно, начальная конфигурация будет простой (рис. 5.2).

В случае замены нетерминала X в верхушке магазина в соответствии с управляющей таблицей M (X, a) = (,y) L-атрибутный ДМП-процессор вталкивает в магазин цепочку символов из правой части распознаваемого правила и выдает цепочку операционных символов y. При этом вычисляются атрибуты операционных символов, не вталкиваемых в магазин, и заполняются поля атрибутов магазинных символов и символов цепочки , вталкиваемых в магазин.

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

Для входной последовательности for k := 1 to 10 do r = 0 замена верхнего символа магазина F представлена на рис. 5.3.

for

i

:=

E

S

E

{нач_ц}

do

Op

{кон_ц}

Рис. 5.3

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

В нашем примере терминалы for и :=, не имеющие атрибутов, просто выталкиваются из магазина, а значение атрибута терминала i (имя переменной цикла k) копируется в соответствии с ссылками (рис. 5.4).

Замена нетерминала E произведена на рис. 5.5.

E

S

E

{нач_ц}

k

do

Op

{кон_ц}

k

Рис. 5.4

c

S

E

{нач_ц}

k

do

Op

{кон_ц}

k

Рис. 5.5

Далее над магазином выполняются следующие действия:

1. выбрасывается терминал c, при этом значение его атрибута 1 получает соответствующий унаследованный атрибут операционного символа {нач_ц};

2. нетерминал S заменяется на терминал to, который выбрасывается из магазина, причем полученное его атрибутом значение inc наследуют соответствующие атрибуты операционных символов {нач_ц} и {кон_ц};

3. нетерминал E заменяется на терминал c, который выбрасывается из магазина, причем значение его атрибута 10 получает соответствующий унаследованный атрибут операционного символа {кон_ц}.

В результате будет получена конфигурация магазина, представленная на рис. 5.6.

В случае, когда верхний символ магазина X – операционный символ, операция ВЫДАЧА(Х) ДМП-процессора расширяется следующим образом:

1. Значения унаследованных атрибутов извлекаются из соответствующих полей верхнего магазинного символа и используются затем при выдаче символа в выходную цепочку. При этом следует помнить, что если операционный символ появился в результате преобразования исходной грамматики в форму простого присваивания, то такой символ в выходную цепочку не выдается.

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

В нашем примере это будет выглядеть так, как на рис. 5.7.