Преобразование грамматики в атрибутную грамматику

Лекция 2.4

Виртуальная машина

Прежде чем разрабатывать блок формирования целевого кода, необходимо знать грамматику этого кода. Первоначально рассмотрим структуру команд стековой машины и разработаем для нее транслятор. Затем разработаем транслятор для виртуальной 3-х адресной машины. Этот код удобен для оптимизации.

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

В учебных целях для простоты разработаем одноадресную виртуальную машину:

КОП

Адрес

Архитектура виртуальной машины

Нуль-адресные операции: арифметические, отношения, логические

КОП

Адрес = 0

Pop – функция извлечения числа из вершины стека

Push(значение) – процедура записи значения в стек

№		Мат. знак	Мнемо-код
	унарный минус	-	op_um
	модуль	abs	op_abs
	сложение	+	op_add	push(pop+pop)
	вычитание	–	op_sub	buf=pop push(pop-buf)
	умножение	*	op_mult	push(pop*pop)
	деление целочислен	/	op_div	. . . .
	остаток	%	op_mod	. . . .
	меньше	<	op_less	buf=pop if (pop<buf) then push(1) else push(0)
	больше	>	op_grt	. . . .
	равно	=	op_equ	. . . .
	или	|	op_or	push(pop | pop)
	и	&	op_and	. . . .
	не	~	op_not
	Вывод из вершины стека в окно вывода		op_view
	останов		op_stop

Дополнительные команды

№		Мат. знак	Мнемо-код
		>=	op_
		<=	op_
		<>	op_
		!>	op_
		!<	op_
		!=	op_
		e2	op_
		sign	op_

Операции пересылки и перехода

КОП	Адрес переменной
КОП	константа

curr_code.op - поле операции текущей команды

curr_code.adr – адрес перехода или значение константы в текущей команде

var[1..v_max] - массив переменных

code[1..c_max] – массив команд

№	операция	Мнемокод	Выполнение
	Запись константы в стек	op_pushC константа	push(curr_code.adr)
	Запись значения переменной в стек	op_pushV адр_пер	push(var[curr_code.adr])
	Запись вершины стека по адресу	op_pop адр_пер
	Безусловный переход по адресу	op_jamp адр_ком	curr_adr = adr_com
	Условный переход по адресу если результат сравнения Истина	op_jmpC адр_ком	if pop=1 then curr_adr = adr_com else curr_adr=curr_adr + 1

Виртуальная машина в процессе выполнения команд должна обнаруживать и выводить сообщения об ошибках времени выполнения:

· несуществующая операция

· некорректный адрес перехода

· некорректный операнд (деление на ноль)

Алгоритм работы виртуальной машины

Procedure VirtComp(

Code array[1..CMAX) of instr, {целевой код}

Var array[1..VMAX] of integer) {переменные}

begin

curr_adr:=1; {установка начального адр}

curr_code:=code[curr_adr]; {выборка 1 команды}

{команды будут выбираться до команды «СТОП»}

while curr_code.op<>op_stop do

begin

{блок интерпретации команд}

case curr_code.op of

{многоальтернативный оператор выбора}

op_plus: begin push(pop+pop); {сложение}

curr_adr:=curr_adr+1 end;

op_sub: begin buf:=pop; push(pop-buf);

curr_adr:=curr_adr+1 end; {вычитание}

. . . . . . . .

op_less: begin buf:=pop; {сравнение по <}

if pop<buf then push(1)

else push(0) end;

. . . . . . . .

{запись в стек констант и переменных}

op_pushC: begin push(curr_code.adr);

curr_adr:=curr_adr+1 end;

op_pushV: begin push(var[curr_code.adr]]);

curr_adr:=curr_adr+1 end;

{безусловный и условный переход}

op_jamp: curr_adr:=curr_code.adr;

op_jampC: begin if pop=1

then curr_adr:=curr_code.adr]

else curr_adr:=curr_adr+1 end;

else w_err(«некорректный код операции»)

end{case};

curr_code:=code[curr_adr]; {выборка команды}

end {while}

end { VirtComp}

Преобразование грамматики в атрибутную грамматику

(синтаксически управляемый перевод для виртуальной машины)

1. активные действия: {gencode(код_операции, операнд)}

2. действия над атрибутами

Правило

MULT

MULT=id | number | ( EXPR )

Добавляем активные действия, атрибуты

MULT= id_P {gencode(op_pushV, P)} |

number_P {gencode(op_pushC, P)} |

( EXPR )

ADD

ADD = MULT { oper MULT }

ADD = MULT { oper_P {R=P запомнить операция} MULT {gencode(R, 0)} }

Аналогично EXPR

Аналогично LOGIC

Оператор присваивания

STMT= id =EXPR

STMT= id_P =EXPR {gencode(op_pop, Q)} Q:=P

If typeLex=id then

Begin

Buf=valueLex

Getlex();

EXPR();

Gencode(op_pop, buf)

End

Else if typeLex=view then

Оператор вывода VIEW

STMT= view EXPR

STMT= view EXPR {gencode(op_view, 0)}

if typeLex=view then

begin

getlex();

EXPR();

gencode(op_view, 0)

end

else if typeLex=view then