Формальные системы для внутреннего (промежуточного) представления программ.

Триады – набор из 5 операций:

Последовательность триад

Адрес метки для перехода	kon	A	b	c
	+	A	b	C
	br	-	N	-
	cbr	P	N	-
	cbm	A	N	b

Kon – код операции;

C:=a+b

-*/v&

1-й,3-й не используются, а в «b» стоит метка N.

С истемы перевода формальных языков.

Входной язык Выходной язык

(вводим на входе) (получаем на выход.яз.)

Это перевод с одного формального языка на другой формальный язык.

Типы перевода:

1. Гомоморфизм – некоторое отображение, сохраняющее алгебраическую операцию.

В нашем случае конкатенацию.

Вх.строка вых.строка

2. Схемы синтаксически управляемого переводов.

(СУ схемы).

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

Входное правило Выходное правило

E→T T

E→E+T ET+

T→M M

T→T*M TM*

M→a a

M→(E) E

Это СУ схема с 2-мя правилами: входное и выходное.

Пример, как работает эта схема:

E E

T T

T * M T M *

M C

( ) M C

E E

E T E +

+ T

T M T M

M b M b

a a

Как хранится у нас это входное дерево:

E→T E→T

T→T*M T→TM*

T→M T→M

M→(E) M→E

E→E+T E→ET+

E→T E→T

T→M T→M

M→a M→a

T→M T→M

M→b M→b

M→c M→c

Эта схема называется простой схемой СУ перевода. Простые СУ переводы – это подкласс СУ перевода.

Особенностью простых СУ схем является то, что в выходном правиле нетерминалы следуют в том же порядке, что и во входном.

Языки характеризующего перевода.

Грамматика этого языка:

E→T В кружочке обозначены терминалы

E→E+T выходного языка.

T→M

T →T*M

M→а

M→(Е)

Построим дерево:

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

E

T

T * M

M C

( )

E

E T

+

T M

M b

a

Гомоморфизм f(a)

Гомоморфизм g(a)

Для реализации простой схемы СУ достаточно преобразовать МП (магазин с памятью).

Схема перевода в полиз для нашего языка ML без переходов.

Правила:

Схема перевода в полиз с переходами.

	Входное правило	Выходное правило	Длины	Переходы
P	S.	S
P	S;P	SP
S	A	A
S	IF	IF
S	WH	WH
S	BE	BE
A	Id:=E	Образ(Id)E:=
IF	If L then S else S	Lb1 If1 S b2 if2 S
WH	While L do S	Lb1 do1 SMb2 do 2
BE	Begin P end	P
L	EzE	Eez
E	T	T
E	E±T	ET±
T	M	M
T	T*/M	TM*/
M	Id	Образ(id)
M	C	Образ(c)
M	(E)	E
Z	<	<

Примерный порядок перевода таблицы:

1. Строятся согласованные деревья вход и выход;

2. Снизу вверх вычисляются все значения l(длины);

3. Зная l, вычисляется b сверху вниз;

4. Найденные значения подставляем в пустые места;

5. Далее левосторонний обход выходного дерева и получение полиза программы.

Схема перевода в триады.

Нетерминал	Входное правило	Выходное правило	Длины	Переходы	Результат промежуточный
P	S.	S
P	S;P2	S P
S	A	A
S	IF	IF
S	WH	WH
S	BE	BE
A	ID:=E	E:=Образ(Id),,rE		Здесь Не нужно Так как Мы передаем В Начало конструкции
E	T	T
E1	E2±T	E2 T			=Образ (Ген)
T	M	M
T	T2*/M	T2 M			=Образ (Ген)
M	ID	-			=Образ (Id)
M	C	-			=Образ (C)
M	(E)	E
IF	If L then S1 else S2	L
WH	While L do S
L					=Образ (Ген)
BE	Begin P end	P

Assembler

Нетерминал	Входные правила	Выходные правила	Адреса
P	S	S
P	S;P	S P
S	A	A
S	IF	IF
S	WH	WH
S	BE	BE
A	ID:=E	E Mov Образ(Id),
IF		L b1 S1
WH	While L do S	L b1 S
BE	Begin P end	P
p
Z Z Z Z Z Z	< > <= >= = <>
E	T	T
	E±T	E T Mov ax,
T	M	M
	T*/M	T M Mov
M M M	Id C (E)	E