Синтаксически управляемый перевод

 

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

Пример 2.17. Составим процедуры перевода в ПОЛИЗ программы на М языке.

ПОЛИЗ представляет собой массив, каждый элемент которого является парой вида (n, k), где n – номер таблицы лексем, k – номер лексемы в таблице. Расширяем набор лексем:

1) в таблицу ограничителей добавляем новые операции ! (18), !F (19), R (20), W (21);

2) для ссылок на номера элементов ПОЛИЗа введем нулевую таблицу лексем, т.е. пара (0, p) - это лексема, обозначающая p-ый элемент в ПОЛИЗе;

3) чтобы различать операнды-переменные и операнды-адреса переменных, обозначим переменные как четвертую таблицу лексем, а адреса – пятую.

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

1) Р – переменная–массив, в который размещается генерируемая программа;

2) free – переменная, хранящая номер первого свободного элемента в массиве P;

3) LEX – переменная, хранящая очередную лексему;

4) put _ lex(LEX) – запись очередной лексемы в массив P, т.е. P[free]:=LEX и free:=free+1;

5) put _ l – запись текущей лексемы в массив P;

6) put _ l 5 – запись текущей лексемы в массив P с изменением четвертого класса лексем на пятый;

7) put _ op - запись в массив P знака операции, считанного процедурой checkop;

8) make(k) - процедура, формирующая лексему-метку (0, k).

 

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

 

Е ® Е1 {( > | < | = ) <instl> E1 <checkop; put_op >}

E1® Т {(+ | - | Ú) <instl> T <checkop; put_op >}

T ® F {( * | / | Ù) <instl> F<checkop; put_op >}

F® I <checkid; put_l> | N <inst(‘int’); put_l> | L <inst(‘bool’); put_l>|

               ØF <checknot; put_lex(‘Ø’)>| (E)

 

Оператор присваивания, дополненный действиями, примет вид:

 

S® I <checkid; put_l5> := E <eqtype; put_lex(‘:=’)>

 

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

Правила условного оператора и оператора цикла примут вид:

 

S® if E <egbool; p1:=free; free:=free+1; put_lex(‘!F’)> then S <p2:=free; free:=free+1; put_lex(‘!’); P[p1]:=make(free)> else S <P[p2]:=make(free)>

S® while <p0:=free> E <egbool; p1:=free; free:=free+1; put_lex(‘!F’)> do S <P[free]:=make(p0); put_lex(‘!’); P[p1]:=make(free) >

 

Правила операторов ввода и вывода с учетом действий записи в ПОЛИЗ будут преобразованы следующим образом:

 

S® write (E <put_lex(‘W’)>) | read (I <checkid; put_l5; put_lex_(‘R’)> )

 

Чтобы в конце ПОЛИЗа была точка, правило Р переписывается в виде:

P®program D1 B <put_lex(‘.’)>.

Таким образом, польская инверсная запись очищена от всех служебных слов, кроме true и false; от ограничителей остаются только знаки операций и знаки «:=», «.».

 

Интерпретатор программы

 

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

1) если очередной элемент ПОЛИЗа является операндом, то его значение заносят в стек;

2) если очередной элемент – операция, то на «верхушке» стека находятся ее операнды, которые извлекаются из стека, над ними выполняется соответствующая операция, результат которой заносится в стек;

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

Пример 2.18. Интерпретировать ПОЛИЗ программы, заданный таблицей 2.5 при введенном значении а равном 7.

 

Таблица 2.5 – ПОЛИЗ исходной программы

 

Лексема	a	r	a	5	>	17	!F	b	a	3	+
(n, k)	(5,1)	(2,20)	(4,1)	(3,1)	(2,16)	(0,17)	(2,19)	(5,1)	(4,1)	(3,2)	(2,8)
Номер	1	2	3	4	5	6	7	8	9	10	11

Продолжение таблицы 2.5 – ПОЛИЗ исходной программы

Лексема	:=	b	W	19	!	a	W	.
(n, k)	(2,5)	(4,1)	(2,21)	(0,19)	(2,18)	(4,1)	(2,21)	(2,1)
Номер	12	13	14	15	16	17	18	19

Процесс интерпретации программы на модельном языке М, записанной в форме ПОЛИЗа, показан в таблице 2.6.

 

Таблица 2.6 – Ход интерпретации ПОЛИЗа программы

 

Стек