Триады и тетрады

Перевод инфиксной записи в суффиксную

Будем полагать, что в некоторой сентенциальной форме основа Х найдена и ее можно заменить на нетерминал в соответствии с правилам u:=X.

Синтаксический распознаватель обратится к некоторой семантической программе и осуществит преобразование, т.е. перевод ее (основы) в суффиксную форму.

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

Е:=Е+Т. Если встретили цепочку Е+Т, то польская (суффиксная) запись уже получена: коды <E> и <T> уже существуют, а программа должна занести в массив "+":

Р(р)="+";

Inc(p).

Есть входная цепочка: A*(B+C), мы должны преобразовать ее в АВС+*, предварительно проверив, правильно ли она получена синтаксически.

Сработал лексический анализатор и выдал i*(i+i). С каждым i связано его физическое имя. Мы могли бы и оставить свои физические имена (А, В, С), но тогда бы пришлось резервировать большую область памяти.

А * (В + С)

| | | | | | | - эти связи должны храниться;

1 2 4 1 3 1 5 - на стадии лексического анализатора каждый символ получает свое индивидуальное имя, проверяется синтаксис (см. прошлый семестр).

1. E:=E+T

2. E:=T

3. T:=T*F

4. T:=F

5. F:=(E)

6. F:=i

Для "6." P(p)=S(j);

Inc(p);

Для "5." и "4." ничего не делаем, продолжаем синтаксический анализ;

Для "3." P(p)='*'; // <T> и <F> уже существуют;

Inc(p); // заносим только '*';

Для "2." ничего не делаем, продолжаем синтаксический анализ;

Для "1." P(p)='+';

Inc(p).

Содержание стека	R – текущий символ входной цепочки	Остаток цепочки	Результат – польская запись
#		—	i*(i+i)#	—
#		(A) – i	*(i+i)#
#i(A) #F	Синтаксический анализатор вызвал п.6 и сразу заменил i на F	*	(i+i)#	A
#T*	Замена по п.4	(	i+i)#	A
#T*(		(B) – i	+i)#	A
#T*(i(B) #T*(F	Замена по п.6	+	i)#	AB
#T*(E+	Замена по п.4, п.2	(C) - i	)#	AB
#T*(E+i(C) #T*(E+F		)	#	ABC
#T*(E+T) #T*(E)	Замена и вызов программы п.1	#	—	ABC+
#T*F #T	Замена и вызов программы п.3	#	—	ABC+*
#E		#	—	ABC+*

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

Тетрады (также называемые "четверками" или трехадресным кодом), состоят из двух операндов, разделенных операцией, и результата операции, записываемого с помощью равенства и обозначаемого целым числом (см. пример на слайде). Таким образом, тетрады содержат явную ссылку на результат операции. В каком-то смысле, это может считаться недостатком тетрад, так как при прямолинейной генерации кода приходится порождать по одной временной переменной на каждую операцию в программе.

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

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