Передача атрибутов в дмп-процессоре

Замена нетерминала:

Выталкиваем верхушку стека, не очищая из под нее память, получаем на нее указатель.

В зависимости от кода правила кладем в стек цепочку замены в обратном порядке

Передача атрибутов:

Если атрибут копируется из левой части правила вывода в правую, то копируем данные(так как АТГ имеет форму простого присваивания)

Пример

X_{p1, q1}Y_p2 Z_q2

p2  p1//p1 - унаследованный

q2  q1//q1 - унаследованный

Y

123

Z

aa00

X
123
aa00



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

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

Тестирование дмп-процессора

Рассмотрим следующую программу:

program my;

const

con = 1;

label

lab1;

var

a, b : integer;

c, d : rational;

ar : array[1..4] of rational;

begin

c.numerator := 1; c.denominator := 1;

d := c;

a := b + c common d;

if a > c.numerator then begin

a := 1

end else begin

d := simplify c;

end;

ar[ 1 ].numerator := 3;

end.

На выходе мы получим:

Таблица меток:

3

aa01

aa00

lab1

------------

Name |

Таблица типов:

	5
1	GENERIC ARRAY N-Ord Nil 2 4 0 0 N-Ord 32
2	GENERIC RANGE Ord Nil Nil 5 1 4 4 4
3	boolean NAMED ENUM Ord Nil Nil Nil 0 1 2 4
4	rational NAMED RAT N-Ord Nil Nil Nil 0 0 N-Ord 8
5	integer NAMED INT Ord Nil Nil Nil -32768 32767 65536 4
	-------------------------------------------------------------------------------
	Name |Type |Cons |Ord? |Alias|Idx |Base|LeftB |RightB |Variant|Size |

Таблица идентификаторов:

	7
1	ar VAR 1 Nil
2	c VAR 4 Nil
3	d VAR 4 Nil
4	a VAR 5 Nil
5	b VAR 5 Nil
6	con CONST 5 1
7	my SYSTEM No type Nil
8	true CONST 3 1
9	false CONST 3 0
	-----------------------------------
	Name |Mode |TypeIdx| Value|

Программа на ПОЛИЗе:

c

@NUMERATOR

1

@SET

c

@DENOMINATOR

1

@SET

d

c

@SET

a

b

c

d

@COMMON

@ADDINT

@SET

a

c

@NUMERATOR

@>INT

:aa00

@JMPF

a

1

@SET

:aa01

@JMP

:aa00

@DEFL

d

c

@SIMPLIFY

@SET

:aa01

@DEFL

ar

1

2

@SUBS

@NUMERATOR

3

@SET

[Warning]: Label declared, but never used: "lab1"

Рассмотрим детально транслирование фрагмента программы:

ar[ 1 ].numerator

Магазин	Входная цепочка	Выход
VAR	ar[ 1 ].numerator	
тип переменной

id	ar[ 1 ].numerator	
ar
{переменная}
адрес переменной
LE
1
кол-во операндовSUBS
{вычислить адрес}
адрес переменной
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной

{переменная}	[ 1 ].numerator	
ar
LE
1
кол-во операндовSUBS
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


[	[ 1 ].numerator	ar
EXP
тип выражения
{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной

EXP	1 ].numerator	ar
тип выражения
{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


EXP	1 ].numerator	ar
тип выражения

{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


AE	1 ].numerator	ar
тип выражения
SAE
тип выражения
тип выражения

{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


ME	1 ].numerator	ar
тип выражения
SME
тип выражения
тип выражения
SAE
тип выражения
тип выражения

{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


usi	1 ].numerator	ar
1/ integer
{число}
адрес константы
SME
тип выражения
тип выражения
SAE
тип выражения
тип выражения

{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


{число}	].numerator	ar
1
SME
integer
тип выражения
SAE
тип выражения
тип выражения

{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


SME	].numerator	ar 1
integer
integer
SAE
тип выражения
тип выражения

{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


SAE	].numerator	ar 1
integer
тип выражения

{индекс}
тип выражения
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


{индекс}	].numerator	ar 1
integer
{inc}
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


{inc}	].numerator	ar 1
1
кол-во операндов
SXP
кол-во операндов
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


SXP	].numerator	ar 1
2
кол-во операндов
]
LE
кол-во операндов
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


]	].numerator	ar 1
LE
2
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


LE	.numerator	ar 1
2
кол-во операндов
{вычислить адрес}
ar
кол-во операндов SUBS
тип переменной
PAR
входной тип переменной
выходной тип переменной


{вычислить адрес}	.numerator	ar 1
ar
2
тип переменной
PAR
входной тип переменной
выходной тип переменной


{вычислить адрес}	.numerator	ar 1
ar
2
тип переменной
PAR
входной тип переменной
выходной тип переменной


PAR	.numerator	ar 1 2 @SUBS
rational
выходной тип переменной


.	.numerator	ar 1 2 @SUBS
numerator
{числитель}
rational
выходной тип переменной


.	.numerator	ar 1 2 @SUBS
numerator
{числитель}
rational
выходной тип переменной


numerator	numerator	ar 1 2 @SUBS
{числитель}
rational
выходной тип переменной


{числитель}		ar 1 2 @SUBS
rational
выходной тип переменной






ar 1 2 @SUBS @NUMERATOR

Преобразование ПОЛИЗ в язык ассемблера

Технические подробности

В качестве языка ассемблера будет использован 32-битный Microsoft Macro Assembler, версии 6.14. Порождаемые исполняемые файлы будут 32-битными консольными приложениями дляMicrosoft Windows.

Такой выбор обоснован тем, что большинство современных программ являются 32-битными и написаны для операционной системы Microsoft Windows, в то время как программы дляDOS перестают поддерживаться.

Входные данные

После описанного ранее этапа трансляции языка в ПОЛИЗ, мы получаем набор данных, который будет использоваться на этапе преобразования ПОЛИЗ в язык ассемблера. Напомним, что это за данные:

• Таблица типов – таблица, содержащая исчерпывающую информацию обо всех используемых в программе типах данных.

• Таблица переменных и именованных констант – таблица, содержащая исчерпывающую информацию обо всех используемых в программе переменных и константах.

• Таблица меток – таблица, содержащая имена всех меток в программе.

• Программа, транслированная в ПОЛИЗ – текстовый файл, содержащий операнды и команды ПОЛИЗ.

Пример:

const

n = 10;

label

lab1;

var

x: integer;

y: array[1..10] of integer;

begin

lab1:

x := 1;

y[n] := x;

goto lab1;

end.

Таблица типов:

	5
1	GENERIC ARRAY N-Ord Nil 2 5 0 0 N-Ord 40
2	GENERIC RANGE Ord Nil Nil 5 1 10 10 4
3	boolean NAMED ENUM Ord Nil Nil Nil 0 1 2 4
4	rational NAMED RAT N-Ord Nil Nil Nil 0 0 N-Ord 8
5	integer NAMED INT Ord Nil Nil Nil -32768 32767 65536 4
	-------------------------------------------------------------------------------
	Name |Type |Cons |Ord? |Alias|Idx |Base|LeftB |RightB |Variant|Size |

Таблица переменных и именованных констант:

	5
1	y VAR 1 Nil
2	x VAR 5 Nil
3	n CONST 5 10
4	true CONST 3 1
5	false CONST 3 0
	------------------------------------
	Name |Mode |TypeIdx| Value|

Таблица меток:

	1
1	lab1
	------------
	Name |

Программа, транслированная в ПОЛИЗ:

:lab1

@DEFL

x

1

@SET

y

n

2

@SUBS

x

@SET

:lab1

@JMP

Все эти данные записаны в текстовых файлах с известными на момент компиляции именами. Будем предполагать, что в момент начала компиляции все таблицы загружены в память и структурно соответствуют своим описаниям на страницах 39-41.

Модель исполнения ПОЛИЗ

Простейшей моделью для исполнения программы в ПОЛИЗ является стек.

Программа в ПОЛИЗ предполагает четыре вида элементов:

• именованная переменная или константа (например, x)

• число, например (например, 10)

• метка (например, :lab1)

• команда (например,@SET)

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

Рассмотрим пример:

x

1

@ADDINT

В данном случае, мы встречаем xи кладем его в стек. Затем, встречаем1и кладем его в стек. Затем встречаем команду сложения целых чисел@ADDINT, которая работает со стеком следующим образом – она вынимает из него два элемента, производит над ними операцию сложения и кладет результат обратно в стек.

Таким образом, при переводе в язык ассемблера, нашей главной задачей будет реализация стековой машины, эмулирующей исполнение ПОЛИЗ.

Перевод таблицы переменных в сегмент данных ассемблера

Прежде всего, рассмотрим, во что будут транслированы данные. Предположим, что в программе на исходном языке мы имели объявление такого вида:

...

var

a : sometype1;

b : sometype2;

...

После трансляции в ПОЛИЗ мы кроме текста транслированной программы получаем также несколько таблиц – таблицу переменных, таблицу типов и таблицу меток. Таблица переменных и таблица типов представляют собой полное описание всех используемых в программе переменных. Эти переменные необходимо поместить в сегмент данных в ассемблере.

Сгенерированный сегмент данных для приведенного примера будет выглядеть так:

...

_data segment

__variable_a <описание специфичное для типа sometype1>

__variable_b <описание специфичное для типа sometype2>

_data ends

...

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

В зависимости от типа данных могут порождаться различные описания переменной.

1. Для переменной целочисленного типа (integer) описание будет выглядеть так:

__variable_a dd 01h dup (0)

То есть целочисленная переменная представляет собой знаковое двойное слово (4 байта), изначально инициализированное значением 0.

2. Аналогично, для переменной рационального типа (rational):

__variable_a dd 00h, 01h

То есть рациональная переменная представляет собой два подряд идущих знаковых двойных слова (8 байт), причем первое двойное слово соответствует числителю дроби, а второе – знаменателю дроби, таким образом рациональная переменная инициализируется значением дроби 0/1.

3. Переменные типа-диапазона и перечислимого типа транслируются таким же образом, как и переменные целочисленного типа. Одним из минусов данной программы является то, что логический тип (boolean) является частным случаем перечислимого типа и, поэтому занимает 4 байта.

4. Переменные, являющиеся массивами рациональных чисел транслируются следующим образом:

__variable_a dd <количество элементов в массиве> dup (0, 1)

При таком объявлении каждый элемент массива инициализируется в значение дроби 0/1. Многомерные массивы приводятся к одномерным массивам с аналогичным количеством элементов.

5. Все остальные переменные-массивы транслируются в:

__variable_a db <размер массива в байтах> dup (0)

6. Константы не попадают в сегмент данных, о том что с ними происходит будет сказано несколько позже.

Рассмотрим пример:

type

tenum1 = (ee1, ee2);

const

ic = 100;

var

i1 : integer;

ia1 : array[1..2] of integer;

ia2 : array[1..3, 1..2] of integer;

ia3 : array[1..3] of array [4..5] of integer;

r1 : rational;

ra1 : array[1..2] of rational;

ra2 : array[1..3, 1..2] of rational;

ra3 : array[1..3] of array [4..5] of rational;

range1 : 10..100;

enum1 : tenum1;

begin

end.

Листинг программы

25
1	GENERIC RANGE Ord Nil Nil 25 10 100 91 4
2	GENERIC ARRAY N-Ord Nil 5 3 0 0 N-Ord 48
3	GENERIC ARRAY N-Ord Nil 4 24 0 0 N-Ord 16
4	GENERIC RANGE Ord Nil Nil 25 4 5 2 4
5	GENERIC RANGE Ord Nil Nil 25 1 3 3 4
6	GENERIC ARRAY N-Ord Nil 9 7 0 0 N-Ord 48
7	GENERIC ARRAY N-Ord Nil 8 24 0 0 N-Ord 16
8	GENERIC RANGE Ord Nil Nil 25 1 2 2 4
9	GENERIC RANGE Ord Nil Nil 25 1 3 3 4
10	GENERIC ARRAY N-Ord Nil 11 24 0 0 N-Ord 16
11	GENERIC RANGE Ord Nil Nil 25 1 2 2 4
12	GENERIC ARRAY N-Ord Nil 15 13 0 0 N-Ord 24
13	GENERIC ARRAY N-Ord Nil 14 25 0 0 N-Ord 8
14	GENERIC RANGE Ord Nil Nil 25 4 5 2 4
15	GENERIC RANGE Ord Nil Nil 25 1 3 3 4
16	GENERIC ARRAY N-Ord Nil 19 17 0 0 N-Ord 24
17	GENERIC ARRAY N-Ord Nil 18 25 0 0 N-Ord 8
18	GENERIC RANGE Ord Nil Nil 25 1 2 2 4
19	GENERIC RANGE Ord Nil Nil 25 1 3 3 4
20	GENERIC ARRAY N-Ord Nil 21 25 0 0 N-Ord 8
21	GENERIC RANGE Ord Nil Nil 25 1 2 2 4
22	tenum1 NAMED ENUM Ord Nil Nil Nil 0 1 2 4
23	boolean NAMED ENUM Ord Nil Nil Nil 0 1 2 4
24	rational NAMED RAT N-Ord Nil Nil Nil 0 0 N-Ord 8
25	integer NAMED INT Ord Nil Nil Nil -32768 32767 65536 4
	-------------------------------------------------------------------------------
	Name |Type |Cons |Ord? |Alias|Idx |Base|LeftB |RightB |Variant|Size |

Таблица с типами данных

15
1	enum1 VAR 22 Nil
2	range1 VAR 1 Nil
3	ra3 VAR 2 Nil
4	ra2 VAR 6 Nil
5	ra1 VAR 10 Nil
6	r1 VAR 24 Nil
7	ia3 VAR 12 Nil
8	ia2 VAR 16 Nil
9	ia1 VAR 20 Nil
10	i1 VAR 25 Nil
11	ic CONST 25 100
12	ee1 CONST 22 0
13	ee2 CONST 22 1
14	true CONST 23 1
15	false CONST 23 0
	------------------------------------
	Name |Mode |TypeIdx| Value|

Таблица с переменными

;

; Generated data segment.

;

_data segment

__variable_ia1 db 8 dup (0) ; Generated variable 'ia1'

__variable_ra2 dd 12 dup (0, 1) ; Generated variable 'ra2'

__variable_ra3 dd 12 dup (0, 1) ; Generated variable 'ra3'

__variable_r1 dd 00h, 01h ; Generated variable 'r1'

__variable_i1 dd 01h dup (0) ; Generated variable 'i1'

__variable_ia3 db 24 dup (0) ; Generated variable 'ia3'

__variable_range1 dd 01h dup (0) ; Generated variable 'range1'

__variable_ia2 db 24 dup (0) ; Generated variable 'ia2'

__variable_enum1 dd 01h dup (0) ; Generated variable 'enum1'

__variable_ra1 dd 4 dup (0, 1) ; Generated variable 'ra1'

_data ends

Сгенерированный сегмент данных на языке ассемблера

Перевод в ассемблер команд ПОЛИЗ

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

Пояснение:

ПОЛИЗ	Язык ассемблера
<Команда 1> <Команда 2>	<Интерпретация команды 1> <Интерпретация команды 2>

Мы будем использовать стек языка ассемблера для моделирования стека исполнения ПОЛИЗ. Прежде всего, определим, какого рода элементы будут находиться в этом стеке.

Если рассмотреть стек исполнения ПОЛИЗ, не рассматривая пока его моделирование в языке ассемблера, то в нем могут находиться элементы следующих типов:

1. Элемент-переменная – соответствует указателю на блок памяти, соответствующий какой-либо переменной, имеющей некоторый определенный тип;

2. Элемент-константа – соответствует константе определенного типа, имеющей определенное значение;

3. Элемент-метка – соответствует метке, которая характеризуется своим именем.

Мы будем считать, что элементы, соответствующие командам в ПОЛИЗ не попадают в стек исполнения ПОЛИЗ. Когда на входной ленте встречается команда – она может произвести некоторые операции с элементами стека и каким-то определенным образом изменить его.

Каждая команда в ПОЛИЗ обладает контрактом – то есть она требует, чтобы элементы стека до ее исполнения удовлетворяли ее предусловию и гарантирует, что, после ее исполнения, элементы стека будут удовлетворять ее постусловию.

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

Шаблон программы

; ; Generated header of assembly. ; .386 .model flat, stdcall option casemap : none include xTraction.asm ; ; Generated data segment. ; _data segment ... _data ends ; ; Generated code segment. ; _text segment _main proc near push ebp mov ebp, esp pusha ... popa mov esp, ebp pop ebp ret 0 _main endp _text ends ; ; Generated footer of assembly ; end _main	Определяет модель используемых инструкций языка ассемблер (i386), модель памяти (flat) и модель вызовов (stdcall).
	Подключает используемую библиотеку (xTraction). Мы используем свою собственную библотеку, написанную на языке ассемблера, которая предоставляет набор шаблонов и функций для перевода команд ПОЛИЗ в язык ассемблера.
	Сгенерированный сегмент данных.
	Сгенерированный сегмент кода.
	Функция соответствующая точке входа в модели вызовов stdcall.
	Сгенерированный перевод команд ПОЛИЗ в язык ассемблера.
	Явное указание точки входа программы.

Особенности разыменовывания указателей в стеке исполнения

Будем полагать, что в стеке исполнения в языке ассемблера могут находиться как указатели на переменные, так и сами значения переменных. При исполнении конкретных операторов (например, оператора сложения целых чисел @ADDINT) удобно делать какие-то предположения об элементах в стеке. Оказывается, что для большинства операторов удобно делать предположения о том, что в стеке исполнения находятся не указатели на элементы, а их значения.

Для пояснения рассмотрим пример в ПОЛИЗ:

x

y

@ADDINT

z

@ADDINT

В данном случае, если бы мы предполагали, что в стеке исполнения находятся указатели на складываемые переменные, то после исполнения последовательности

x

y

@ADDINT

было бы получено число, соответствующее значению (x+y)– и для того, чтобы следующий оператор@ADDINTудовлетворял контракту, пришлось бы создать временную переменную и поместить в нее значение(x+y), после чего поместить указатель на эту временную переменную в стек. Если бы подобные операции выполнялись, например, в цикле, то такая схема привела бы к значительному усложнению управления памятью.

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

x

5

@SET

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

Для того чтобы осуществить это, используется промежуточный стек исполнения ПОЛИЗ внутри транслятора. Каждый элемент этого стека имеет тип (указатель на переменную, значение переменной или метка), а также полную информацию об используемом типе данных (в случае, если элемент не метка).

Описание перевода элементов ПОЛИЗ в язык ассемблера

Команда ПОЛИЗ	Перевод в ассемблер	Пояснение
x	push offset __variable_x	Положить указательна переменную (x) в стек ассемблера. Положить указательна переменную (x) в промежуточный стек исполнения.
<числовая константа>	push <числовая константа>	Положить значениечисловой константы в стек ассемблера. Положить значениечисловой константы в промежуточный стек исполнения.
<именная константа>	push <значение именной константы>	Положить значениеименной константы в стек ассемблера. Положить значениеименной константы в промежуточный стек исполнения.
<метка>		Положить имяметки в промежуточный стек исполнения.

Пример разыменования указателей в стеке исполнения

Рассмотрим пример в ПОЛИЗ, где x– это переменная целочисленного типа:

x

5

@ADDINT

Он будет последовательно следующим образом:

1. Сначала промежуточный стек исполнения пуст.

2. Встретили во входном файле x,

   1. Обратились к таблице переменных и убедились в том, что это переменная.

   2. Написали push offset __variable_xв выходной файл.

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

3. Встретили во входном файле 5

   1. Написали push 5в выходной файл.

   2. Поместили в стек исполнения элемент с типом значениеи типом данныхinteger.

4. Встретили во входном файле @ADDINT – функцию, которая складывает два целых числа.Eе контракт предполагает, что в стеке исполнения находится два целочисленных значения.

   1. Привели стек к виду, когда на верху лежат два целочисленных значения. На верхушке стека лежит целочисленное значение (5), вторым элементом лежит указатель (на переменнуюx). Чтобы реальный стек соответствовал контракту функции надо выполнить разыменование указателя:

      1. Во временный регистр извлекается верхушка стека (в выходной файл пишется pop eax).

      2. Выполняется преобразование указатель к значению для новой верхушки стека (в выходной файл пишется вызов макроса __evaluate_integer_variable).

      3. Извлеченное ранее целочисленное значение помещается назад (в выходной файл пишется push eax).

   2. В выходной файл записывается вызов библиотечной функции __add_integer_integer, соответствующей команде@ADDINTПОЛИЗ.

   3. Первые два элемента удаляются из стека исполнения.

   4. В стек исполнения помещается новый элемент с типом значение и типом данных integer(по контракту, команда@ADDINTкладет в стек значение целочисленного типа).

В выходном файле переведенный фрагмент будет выглядеть так:

push offset __variable_x ; x

push 5 ; 5

pop eax

__evaluate_integer

push eax

call __add_integer ; @ADDINT

add esp, 4

Описание перевода операций по работе с метками

Команда ПОЛИЗ	Перевод в ассемблер	Пояснение
@DEFL	<имя метки>:	Предусловие: В промежуточном стеке верхний элемент является меткой. Вытолкнуть из промежуточного стека элемент, содержащий <имя метки>.
@JMP	jmp <имя метки>	Предусловие: В промежуточном стеке верхний элемент является меткой. Вытолкнуть из промежуточного стека элемент, содержащий <имя метки>.
@JMPF	pop eax cmp eax, 1 jne <имя метки>	Предусловие: В промежуточном стеке верхний элемент является переменной логического типа (4 байта, 0 – если false, 1 – еслиtrue), следующий за верхним элемент является меткой. Вытолкнуть из промежуточного стека элемент. Вытолкнуть из промежуточного стека элемент, содержащий <имя метки>. Постусловие: Данные в регистре eaxпотеряны.

Описание перевода операций по работе с памятью

Команда ПОЛИЗ	Перевод в ассемблер	Пояснение
@SET	push<размер типа в байтах> call __copy_memory add esp, 12	Предусловие: Оба верхних элемента в промежуточном стеке являются указателямина переменные. Узнать тип, на который указывают указатели, и определить его <размер в байтах>. Вытолкнуть из промежуточного стека два элемента. Постусловие: Содержимое памяти по данным указателям идентично.
	__set_integer_variable	Предусловие: Верхний элемент в промежуточном стеке является целочисленным значением. Следующий за ним элемент являетсяуказателемна целочисленную переменную. Вытолкнуть из промежуточного стека два элемента. Постусловие: Значение целого числа по данному указателю равно данному выражению.
	__set_rational_variable	Предусловие: Верхний элемент в промежуточном стеке является рациональным значением. Следующий за ним элемент являетсяуказателемна рациональную переменную. Вытолкнуть из промежуточного стека два элемента. Постусловие: Значение рационального числа по данному указателю равно данному выражению.

Пояснение:__copy_memory– это функция на языке ассемблера, который выполняет копирование данных. Данная функция принадлежит библиотеке функций и макросов, которая была предварительно написана для более удобной трансляции.

Вызов функции соответствует конвенции вызовов stdcall, принятой вC. По этой конвенции стек очищает тот же, кто кладет в него параметры – в данном случае командаadd esp, 12– выталкивает из стека три двойных слова.

Более подробное описание некоторых макросов и функций содержится в приложении.

Команда ПОЛИЗ	Перевод в ассемблер	Пояснение
@SUBS	pop eax mov eax, 1 xor ebx, ebx xor ecx, ecx xor edx, edx k – 1 раз в порядке от младших индексов к старшим вывести: pop ebx sub ebx, <левая граница типа индекса> push eax imul ebx add ecx, eax pop eax mov ebx, <диапазон значений индекса> imul ebx mov eax, ecx mov ebx, <размер индексируемого элемента> imul ebx pop edx add edx, eax push edx	Предусловие: Верхний элемент является целочисленной константой k, определяющей количество операндов. Далее следуют (k–1) целочисленныхзначенийиуказательна разыменовываемую переменную. Вытолкнуть из промежуточного стека (k+1) элемент. Итеративно посчитать адрес смещения. Постусловие: Данные в регистрах eax,ebx,ecx,edxбудут потеряны. На вершине стека исполнения находится корректный указатель на элемент массива соответствующий индексации.

Пояснение:

Обозначим за M = <размер индексируемого элемента>,заC_i = <указанный i-ый индекс>, за L_i = <левая граница i-го индекса>, заR_i = <правая граница i-го индекса>. Тогда,S_i=<ширина i-го индекса> =R_i – L_i + 1.

Например, рассмотрим массив:

var

a : array [1..10, 2..20, 3..40] of integer;

и индексацию к нему:

a[10, 19]

Тогда, каждый элемент, который индексирован по первым двум индексам, сам представляет собой массив типа array [3..40] of integer, поэтому

M = sizeof(array[3..40] of integer) = 38 * sizeof(integer) =

= 38 * 4 = 152 (байта)

Указано два индекса, 10и19, поэтомуC₁=10, аC₂=19.

Левые и правые границы, соответственно, L₁=1,L₂=2,R₁=10,R₂=20.

Отсюда ширины индексов, S₁=10,S₂=19.

В общем случае, полное смещение в байтах, при индексации по kиндексам вычисляется по формуле:

M * ((C₁ – L₁) * S₂ * S₃ * … * S_K + (C₂ – L₂) * S₃ * … S_K + …

+ (C_K – L_K))

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

Описание перевода арифметических операций.

Команда ПОЛИЗ	Перевод в ассемблер	Пояснение
@ADDINT	call __add_integer add esp, 4	Предусловие: Верхние два элемента являются целочисленными значениями. Вытолкнуть из промежуточного стека два элемента. Положить в промежуточный стек результат операции в виде целочисленного значения. Постусловие: На вершине стека исполнения находится целочисленное значение, соответствующее результату операции.
@SUBINT	call __sub_integer add esp, 4
@MULINT	call __mul_integer add esp, 4
@DIVINT	call _div_integer add esp, 4
@NEGINT	__negate_integer	Предусловие: На вершине стека находится элемент, являющийся целочисленным значением. Вытолкнуть из промежуточного стека элемент. Положить в промежуточный стек результат операции в виде целочисленного значения. Постусловие: На вершине стека исполнения находится целочисленное значение, соответствующее результату операции.
@INC	__increment_integer_variable	Предусловие: На вершине стека находится элемент, являющийся указателемна целочисленное значение. Вытолкнуть из промежуточного стека элемент. Постусловие: Элемент, находящийся по данному указателю, был увеличен на единицу.
@DEC	__decrement_integer_variable	Предусловие: На вершине стека находится элемент, являющийся указателемна целочисленное значение. Вытолкнуть из промежуточного стека элемент. Постусловие: Элемент, находящийся по данному указателю, был уменьшен на единицу.

Абсолютно аналогично транслируются бинарные операции с рациональными числами @ADDRAT,@SUBRAT,@MULRAT,@DIVRAT,@COMMONи унарные@NEGRAT, @FRAC, @INT, и@SIMPLIFY.

Также транслируются бинарные операции с логическим типом @AND,@ORи унарная@NOT. Логический тип рассматривается как целочисленный, принимающий значения0(false) или1(true).

Бинарные операции сравнений рациональных и целых чисел @=INT, @=RAT, @>INT, @>RAT, @<INT, @<RAT, @>=INT, @>=RAT, @<=INT, @<=RAT, @<>INT, @<>RATтранслируются аналогично.

Все они принимают в качестве параметров значения и кладут в стек результирующиезначения.

Команда ПОЛИЗ	Перевод в ассемблер	Пояснение
@NUMERATOR	__numerator_rational_variable	Предусловие: Верхний элемент является указателемна рациональное число. Вытолкнуть из промежуточного стека элемент. Положить в промежуточный стек результат операции в виде указателя на целое число. Постусловие: На вершине стека исполнения находится указатель, соответствующий результату операции (указатель на числитель или указатель на знаменатель рационального числа).
@DENOMINATOR	__denominator_rational_variable
@ITOR	__integer_to_rational	Предусловие: Верхний элемент является целочисленным значением. Вытолкнуть из промежуточного стека элемент. Положить в промежуточный стек результат операции в виде рационального значения. Постусловие: На вершине стека исполнения находится приведенное рациональное значение.
@ITOR2	pop eax pop ebx (возможное разыменовывание указателя) __integer_to_rational push ebx push eax	Предусловие: На вершине стека находится рациональное значение, следующий за ним элемент представляет собой целочисленноезначение. Вытолкнуть из промежуточного стека элемент и сохранить его, изменить тип вершины стека с целочисленного значенияна рациональноезначение. Положить сохраненный элемент на вершину стека. Постусловие: первые два элемента стека представляют собой рациональныезначения.
@INPUT	call __input_integer_variable add esp, 4	Предусловие: На вершине стека находится указатель на целое число. Вытолкнуть из промежуточного стека элемент. Постусловие: Содержимое памяти по данному указателю соответствует введенному с консоли знаковому целому числу.
	__input_rational_variable	Предусловие: На вершине стека находится указатель на рациональное число. Вытолкнуть из промежуточного стека элемент. Постусловие: Содержимое памяти по данному указателю соответствует двум введенным через enterс консоли знаковым целым числам – числителю и знаменателю рационального числа.

@OUTPUT	call __output_integer add esp, 4	Предусловие: На вершине стека находится целочисленное значение.. Вытолкнуть из промежуточного стека элемент. Постусловие: В консоль выведено целое знаковое число.
	call __output_rational add esp, 8	Предусловие: На вершине стека находится рациональное значение. Вытолкнуть из промежуточного стека элемент. Постусловие: В консоль выведено рациональное число в формате <числитель>/<знаменатель>.

Замечание:

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

Для того чтобы разыменовывать указатели дозначений, используются два макроса__evaluate_rationalи__evaluate_integer. Их код приведен в приложении.

Пример

var

a : array[1..4] of integer;

i : integer;

begin

for i := 1 to 4 do

a[i] := i;

for i := 4 downto 1 do

write(a[i]);

end.

; ; Generated header of assembly. ; .386 .model flat, stdcall option casemap : none include xTraction.asm ; ; Generated data segment. ; _data segment __variable_i dd 01h dup (0) __variable_a db 16 dup (0) _data ends ; ; Generated code segment. ; _text segment _main proc near push ebp mov ebp, esp pusha push offset __variable_i push 1 __set_integer_variable $aa00: push offset __variable_i push 4 pop eax __evaluate_integer push eax __less_equals_integer pop eax cmp eax, 1 jne $aa01 push offset __variable_a push offset __variable_i push 2 pop eax mov eax, 1 xor ebx, ebx xor ecx, ecx xor edx, edx __evaluate_integer pop ebx sub ebx, 1 push eax imul ebx add ecx, eax pop eax mov ebx, 4 imul ebx mov eax, ecx mov ebx, 4 imul ebx pop edx add edx, eax push edx push offset __variable_i push 4 call __copy_memory add esp, 12 push offset __variable_i __increment_integer_variable jmp $aa00 $aa01: push offset __variable_i push 4 __set_integer_variable $aa02: push offset __variable_i push 1 pop eax __evaluate_integer push eax __greater_equals_integer pop eax cmp eax, 1 jne $aa03 push offset __variable_a push offset __variable_i push 2 pop eax mov eax, 1 xor ebx, ebx xor ecx, ecx xor edx, edx __evaluate_integer pop ebx sub ebx, 1 push eax imul ebx add ecx, eax pop eax mov ebx, 4 imul ebx mov eax, ecx mov ebx, 4 imul ebx pop edx add edx, eax push edx __evaluate_integer call __output_integer add esp, 4 call __output_cr_lf push offset __variable_i __decrement_integer_variable jmp $aa02 $aa03: popa mov esp, ebp pop ebp ret 0 _main endp _text ends ; ; Generated footer of assembly ; end _main

i 1 @SET :$aa00 @DEFL i 4 @<=INT :$aa01 @JMPF a i 2 @SUBS i @SET i @INC :$aa00 @JMP :$aa01 @DEFL i 4 @SET :$aa02 @DEFL i 1 @>=INT :$aa03 @JMPF a i 2 @SUBS @OUTPUT i @DEC :$aa02 @JMP :$aa03 @DEFL

Приложение (содержит часть библиотечных функций)

; Функция, копирующая память.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] адрес возврата

; [dw] сколько копировать в байтах

; [dw] указатель на то, откуда копировать

; [dw] указатель на то, куда копировать

; ...

;

; После вызова стек имеет вид:

;

; esp -> [dw] адрес возврата

; ...

__copy_memory_arg1$ = 8

__copy_memory_arg2$ = 12

__copy_memory_arg3$ = 16

__copy_memory proc near

push ebp

mov ebp, esp

push edx

push edi

push ecx

push ebx

push eax

mov ebx, 0

mov ecx, dword ptr __copy_memory_arg1$[ebp]

mov edx, dword ptr __copy_memory_arg2$[ebp]

mov edi, dword ptr __copy_memory_arg3$[ebp]

__copy_memory_loop:

cmp ebx, ecx

jnl __copy_memory_exit

mov al, byte ptr [edx]

mov byte ptr [edi], al

inc edi

inc edx

inc ebx

jmp __copy_memory_loop

__copy_memory_exit:

pop eax

pop ebx

pop ecx

pop edi

pop edx

mov esp, ebp

pop ebp

ret 0

__copy_memory endp

; Макрос, устанавливающий значение рациональной переменной.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] числитель рационального числа

; [dw] знаменатель рационального числа

; [dw] указатель на переменную

; ...

;

; После вызова стек имеет вид:

;

; esp -> ...

__set_rational_variable macro

push eax

push ebp

mov ebp, dword ptr [esp + 16]

mov eax, dword ptr [esp + 8]

mov dword ptr [ebp], eax

mov eax, dword ptr [esp + 12]

mov dword ptr [ebp + 4], eax

pop ebp

pop eax

add esp, 12

endm

; Макрос, устанавливающий значение 32-битной целочисленной переменной.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] 32-битное целое число

; [dw] указатель на переменную

;

; После вызова стек имеет вид:

;

; esp -> [dw] тот же указатель на переменную

__set_integer_variable macro

push eax

push ebp

mov ebp, dword ptr [esp + 12]

mov eax, dword ptr [esp + 8]

mov dword ptr [ebp], eax

pop ebp

pop eax

add esp, 8

endm

; Макрос, разыменовающий указатель на дробное число.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] указатель на дробное число

;

; После вызова стек имеет вид:

;

; esp -> [dw] числитель дробного числа

; [dw] знаменатель дробного числа

__evaluate_rational macro

push 0

push eax

push ebp

mov ebp, dword ptr [esp + 12]

mov eax, dword ptr [ebp]

mov dword ptr [esp + 8], eax

mov eax, dword ptr [ebp + 4]

mov dword ptr [esp + 12], eax

pop ebp

pop eax

endm

; Макрос, разыменовающий указатель на целое число.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] указатель на целое число

;

; После вызова стек имеет вид:

;

; esp -> [dw] целое число

__evaluate_integer macro

push eax

push ebp

mov ebp, dword ptr [esp + 8]

mov eax, dword ptr [ebp]

mov dword ptr [esp + 8], eax

pop ebp

pop eax

endm

; Макрос, приводящий целое 32-битное число к дробному.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] целое число

; ...

;

; После вызова стек имеет вид:

;

; esp -> [dw] числитель результата

; [dw] знаменатель результата

__integer_to_rational macro

push 0

push eax

mov eax, dword ptr [esp + 8]

mov dword ptr [esp + 8], 1

mov dword ptr [esp + 4], eax

pop eax

endm

Некоторые арифметические библиотечные функции

;

; Функция, складывающая целые 32-битные числа.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] адрес возврата

; [dw] первое число

; [dw] второе число

; ...

;

; После вызова стек имеет вид:

;

; esp -> [dw] адрес возврата

; [dw] ...

; [dw] сумма

;

__add_integer_arg1$ = 8

__add_integer_arg2$ = 12

__add_integer proc near

push ebp

mov ebp, esp

push eax

push ebx

mov eax, dword ptr __add_integer_arg1$[ebp]

mov ebx, dword ptr __add_integer_arg2$[ebp]

add eax, ebx

mov dword ptr __add_integer_arg2$[ebp], eax

pop ebx

pop eax

mov esp, ebp

pop ebp

ret 0

__add_integer endp

;

; Функция, складывающая рациональные числа.

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] адрес возврата

; [dw] числитель первого числа

; [dw] знаменатель первого числа

; [dw] числитель второго числа

; [dw] знаменатель второго числа

; ...

;

; После вызова стек имеет вид:

;

; esp -> [dw] адрес возврата

; [dw] ...

; [dw] ...

; [dw] числитель результата

; [dw] знаменатель результата

;

__add_rational_arg1$ = 8

__add_rational_arg2$ = 12

__add_rational_arg3$ = 16

__add_rational_arg4$ = 20

__add_rational proc near

push ebp

mov ebp, esp

push eax

push ebx

push ecx

push edx

mov eax, dword ptr __add_rational_arg1$[ebp]

mov ebx, dword ptr __add_rational_arg4$[ebp]

mov ecx, 0

mov edx, 0

imul ebx

add ecx, eax

mov eax, dword ptr __add_rational_arg2$[ebp]

mov ebx, dword ptr __add_rational_arg3$[ebp]

mov edx, 0

imul ebx

add ecx, eax

mov eax, dword ptr __add_rational_arg2$[ebp]

mov ebx, dword ptr __add_rational_arg4$[ebp]

mov edx, 0

imul ebx

mov dword ptr __add_rational_arg3$[ebp], ecx

mov dword ptr __add_rational_arg4$[ebp], eax

pop edx

pop ecx

pop ebx

pop eax

mov esp, ebp

pop ebp

ret 0

__add_rational endp

;

; Макрос, вычисляющий логическое выражение (a or b).

;

; В момент вызова стек имеет вид:

;

; esp -> [dw] логическая величина со значением b

; [dw] логическая величина со значением a

; ...

;

; После вызова стек имеет вид:

;

; esp -> [dw] логическая величина со значением (a or b)

;

__or_boolean macro

push eax

push ebx

mov eax, dword ptr [esp + 8]

mov ebx, dword ptr [esp + 12]

or eax, ebx

and eax, 1

mov dword ptr [esp + 12], eax

pop ebx

pop eax

add esp, 4

endm

88