Лабораторная работа №2 проектирование лексического анализатора

Построение списка триад по дереву вывода.

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

Вид узла дерева	Результирующий код	Примечание
	i) act (oper1,oper2)	act - тип триады oper1,oper2 - операнды (листья дерева вывода)
	i) Code(Узел 2,i) i+j) act(oper1,^i+j-1)	Узел 2 - нижележащий узел дерева вывода Code(Узел 2,i) - последовательность триад, порождаемая для Узла2, начиная с триады с номером i j - количество триад, порождаемых для Узла2
	i) Code(Узел 2,i) i+j) act(^i+j-1,oper2)	Узел 2 - нижележащий узел дерева вывода Code(Узел 2,i) - последовательность триад, порождаемая для Узла2, начиная с триады с номером i j - количество триад, порождаемых для Узла2
	i) Code(Узел 2,i) i+j) Code(Узел 3,i+j) i+j+k) act(^i+j-1,^i+j+k-1)	Узел 2, Узел 3 - нижележащие узлы дерева вывода Code(Узел 2,i) - последовательность триад, порождаемая для Узла2, начиная с триады с номером i j - количество триад, порождаемых для Узла2 Code(Узел 3,i+j) - последовательность триад, порождаемая для Узла3, начиная с триады с номером i+j k - количество триад, порождаемых для Узла3

Рассмотрим тот же пример дерева вывода для выражения A := B*C + D - B*10 на рис. 6 и соответствующую ему последовательность триад:

Рис. 6. Дерево вывода для арифметического выражения.

Шаг 1: 1)  Code(U2,1)
i)  :=(A,^i-1)
Шаг 2: 1)  Code(U3,1)
j)  Code(U5,j)
i-1)  -(^j-1,^i-2)
i)  :=(A,^i-1)
Шаг 3: 1)  Code(U4,1)
k)  +(^k-1,D)
j)  Code(U5,j)
i-1)  -(^j-1,^i-2)
i)  :=(A,^i-1)
Шаг 4: 1)  *(B,C)
2)  +(^1,D)
3)  Code(U5,3)
i-1)  -(^j-1,^i-2)
i)  :=(A,^i-1)
Шаг 5: 1)  *(B,C)
2)  +(^1,D)
3)  *(B,10)
4)  -(^2,^3)
5)  :=(A,^4)
Следует обратить внимание, что в данном алгоритме последовательные номера триад (а следовательно, и ссылки на них) устанавливаются не сразу. Это не имеет значение при рекурсивной организации процедуры, но при другом способе обхода дерева вывода в программе генерации кода лучше увязывать триады между собой именно по ссылке (указателю), а не по порядковому номеру.
Для триад разработаны универсальные (машинно-независимые) алгоритмы оптимизации кода. После их выполнения (оптимизации внутреннего представления) триады могут быть преобразованы в команды на языке ассемблера.