Перевод в полиз условных опереторов, операторов присваивания, операторов циклов.

оператор	код	операнды	симантика
1.Вычисление адреса элемента массива.	SUBS		Вычисление адреса, элемента массива а, - индексные выражения. - число операндов в операн.
2.Вызов функции.	CALL		Вызов функции f аргументами c
3 Преобразование типа. Целые - веществ. Веществ. - целый	I2A A2I	E E	Преобразования типа в значение для выражения Е.
4. Оператор присваивания.	:=
5. Определение метки.	DEFL	m	Определение метки m.
б.Безусловный переход на метку.	BRL	m	Переход на метку m.
7.Просто Безусловный переход.	BR	n	Переход на
			некоторый элемент n, где n - номер элемента в ПОЛИЗ.
8.Условный переход по значению false	BF	r, m	Переход на метку m, если r = FALSE
9.Переход по услов:	BZ ВР ВМ BPZ BMZ	m, r	Переход на метку m. при выполнения соответствующих условиях для r.
10.Начало блока Конец блока	BLBEG BLEND		Начало и конец блока.

Лекция 17

Формальные методы описания перевода. СУ-трансляция. S-атрибутные определения

Формальные методы описания перевода.

Для ЯП перевод должен быть функцией, т.е. для каждой входной программы должно быть не более одной выходной программы.

Простейшие переводы можно задать при помощи гомоморфизма.

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

1. ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -}

2. Задается правило, что H(a)=a при

3. Если , то h(a) задается таблицей

a	h(a)
0	Ноль
1	Один
2	Два
3	Три
…
+	Плюс
-	Минус

Используя данное определение, перевод входной цепочки “-15” будет иметь вид “минус один пять”.

Синтаксически управляемый перевод (трансляция) (СУ-трансляция).

Общая схема СУ-трансляции имеет вид

Входная строка

Дерево разбора

Граф зависимости

Порядок выполнения семантического перевода

Реализация не всегда следует этой схеме. Иногда можно реализовать переход за один проход выполнения семантических правил в процессе семантического анализа без явного построения дерева разбора и графа зависимости. В этом случае экономится время.

Существует два вида записи для связанных с продукциями семантических правил – это синтаксически управляемое определение (СУ-определение) и схема трансляции.

СУ-определение.

СУ-определение – это обобщение КС грамматики в которой каждый грамматический символ имеет связанное с ним множество атрибутов, разделенное на два подмножества: синтезируемые и наследуемые атрибуты этого грамматического символа.

Атрибут может представлять собой все, что угодно – строку, число, тип, адрес памяти и т.д.

Значение атрибута в узде дерева разбора определяется семантическими правилами, связанной с используемой в данном узле продукцией.

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

Значение наследуемого атрибута определяется значением атрибутов соседних (т.е. узлов, дочерних по отношению к родительскому узлу данного) и родительских узлов.

Семантические правила определяют зависимость между атрибутами. Эта зависимость определяется графом.

Граф зависимости определяет порядок выполнения семантических правил, что дает значение атрибутов в узлах дерева разбора входной строки.

Естественно необязательно строить в явном виде дерево и граф. Главное, чтобы для каждой входной строки выполнялись верные действия в правильном порядке.

В СУ-определении каждая продукция грамматики типа имеет связанное с ней множество семантических правил вида: , здесь f – функция, - атрибуты грамматических символов продукции, b – синтезируемый атрибут символа a или наследуемый атрибут одного из грамматических символов правой части продукции.

Пример 1. Построить СУ-определение настольного калькулятора.

Оно связывает с каждым из нетерминалов целочисленный атрибут val. Для каждой продукции семантическое правило вычисляет значение val нетерминала левой части по значению атрибутов нетерминалов правой части.

Продукция

Семантическое правило

n – символ новой строки, lex.лучение цифры значения в лексическом анализе.

Например, получив в качестве строки 3*5+4 n выводится 19.

Дерево будет выглядеть следующим образом.

Пример 2. Наследуемые атрибуты.

Продукция.

Семантическое правило.

L.in:=T.type

T.type:=integer

T.type:= real

Addtype(id.entry, L.in)

Это таблица с наследуемым атрибутом L.in

Теперь будем строить для real id1, id2, id3 дерево разбора с наследуемым атрибутом in в каждом узле, помеченном нетерминалом L.

Значения L.in в трех узлах дает тип идентификаторов id1, id2, id3. Эти значения определяются вычислением значения T.type в левом дочернем по отношению к корню узле, а затем вычислением L.in в нисходящем порядке в трех L узлах правого поддерева корневого узла.

В каждом L узле мы выдаем процедуру L.type для записи в таблицу символов, информация о том, что идентификатор в правом дочернем узле имеет тип real.

S-атрибутные определения

Создание транслятора для произвольного СУ определения достаточно сложно. Рассмотрим класс СУ определений, для которых эта задача упрощается. S-определения – это СУ определение в котором применяется исключительно синтезированные атрибуты. Синтезированные атрибуты могут быть вычислены восходящим синтаксическим анализатором в процессе разбора входной строки. Для хранения атрибутов используется стек. Текущая вершина определяется указателем top. Предполагаем, что синтезированные атрибуты вычисляют непосредственно перед каждой сверткой. Пусть с продукции A ~ XYZ связано семантическое правило А.а = f (X.x, Y.y, Z.z). Перед сверткой X,Y,Z в А значение атрибута Z.z находится в val (top).

X X.x

top ~ Y Y.y

Z Z.z

Y.y val (top 1), X.x val (top 2)

После свертки top уменьшается на 2единицы; состояние А помещается на место X.x, а атрибут Аа получает значение val (top).

L-атрибутные определения

Это определение основано на графах LL (1) и LR (1). СУ определение является L-атрибутным, если каждый наследуемый атрибут с символом X_j, где 1 ≤ j≤ n из правой части продукции А X₁ X_2……… X_n зависит только от:

1. Атрибутов символов X₁ , X₂ ,_…… , X_j-1 . рассматриваемых в продукции слева от X_j

2. Наследуемых атрибутов.

Примечание: каждое S-атрибутное определение является L-атрибутным определением.