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

Лекция 2.4

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

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

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

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

КОП Адрес

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

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

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

КОП Адрес = 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

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

MULT=id | number | ( EXPR )

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

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

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

numberP {gencode(op_pushC, P)} |

( EXPR )

ADD

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

ADD = MULT { oper MULT }

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

Аналогично EXPR

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

Аналогично LOGIC

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

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

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

STMT= id =EXPR

STMT= idP =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

Наши рекомендации