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

Триада	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5
Шаг 6
1	C (2, 0)	C (2, 0)	C (2, 0)	C (2, 0)	C (2, 0)	C (2, 0)
2	:= (I, ^1)	:= (I, 2)	:= (I, 2)	:= (I, 2)	:= (I, 2)	:= (I, 2)
3	:= (I, 3)	:= (I, 3)	:= (I, 3)	:= (I, 3)	:= (I, 3)	:= (I, 3)
4	* (6, I)	* (6, I)	* (6, I)	C (18, 0)	C (18, 0)	C (18, 0)
5	+ (^4, I)	+ (^4, I)	+ (^4, I)	+ (^4, I)	C (21, 0)	C (21, 0)
6	:= (J, ^5)	:= (J, ^5)	:= (J, ^5)	:= (J, ^5)	:= (J, ^5)	:= (J, 21)
Т	( , )	( I, 2 )	( I, 3 )	( I, 3 )	( I, 3 )	( I, 3 ) ( J, 21 )

Если исключить особые триады типа C(K,0) (которые не порождают объектного кода), то в результате выполнения свертки получим следующую последовательность триад:
1)  := (I, 2)
2)  := (I, 3)
3)  := (J, 21)

Оптимизация объектного кода методом исключения лишних операций

Определим понятие лишней операции. Операция линейного участка с порядковым номером i считается лишней, если существует более ранняя идентичная ей операция с порядковым номером j и никакая переменная, от которой зависит эта операция, не изменялась никакой третьей операций, имеющей порядковый номер между i и j.
Алгоритм исключения лишних операций просматривает операции в порядке их следования. Также как и алгоритму свертки, алгоритму исключения лишних операций проще всего работать с триадами, потому что они полностью отражают взаимосвязь операций.
Чтобы следить за внутренней зависимостью переменных и триад алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам:
 изначально для каждой переменной ее число зависимости равно 0, так как в начале работы программы значение переменной не зависит ни от какой триады;
 после обработки i-ой триады, в которой переменной A присваивается некоторое значение, число зависимости A (dep(A)) получает значение i, так как значение A теперь зависит от данной i-ой триады;
 при обработке i-ой триады ее число зависимости (dep(i)) принимается равным значению: 1+(максимальное из чисел зависимости операндов).
Таким образом, при использовании чисел зависимости триад и переменных можно утверждать, что если i-ая триада идентична j-ой триаде (jАлгоритм исключения лишних операций использует в своей работе также особого вида триады SAME(j,0), которые означают, что некоторая триада i идентична триаде j.
Алгоритм исключения лишних операций последовательно просматривает триады линейного участка. Он состоит из следующих шагов, выполняемых для каждой триады:
1. Если операнд ссылается на особую триаду вида SAME(j,0), то он заменяется на ссылку на триаду с номером j (^j).
2. Вычисляется число зависимости текущей триады с номером i, исходя из чисел зависимости ее операндов.
3. Если существует идентичная j-ая триада, причем jSAME(j,0).
4. Если текущая триада есть присвоение, то вычисляется число зависимости соответствующей переменной.
Рассмотрим работу алгоритма на примере:
D := D + C*B;
A := D + C*B;
C := D + C*B;
Этому фрагменту программы будет соответствовать следующая последовательность триад:
1)  * (C, B)
2)  + (D, ^1)
3)  := (D, ^2)
4)  * (C, B)
5)  + (D, ^4)
6)  := (A, ^5)
7)  * (C, B)
8) + (D, ^7)
9) := (C, ^8)
Работу алгоритма отобразим в табл. 8.
Теперь, если исключить триады особого вида SAME(j,0), то в результате выполнения алгоритма получим следующую последовательность триад:
1)  * (C, B)
2)  + (D, ^1)
3)  := (D, ^2)
4)  + (D, ^1)
5)  := (A, ^4)
6) := (C, ^4)
Обратите внимание, что в итоговой последовательности изменилась нумерация триад и номера в ссылках одних триад на другие. Если в программе компилятора в качестве ссылок использовать не номера триад, а непосредственно указатели на них, то изменение ссылок в таком варианте не потребуется.
Таблица 8.
Пример работы алгоритма исключения лишних операций.

Обрабатываемая		Числа зависимости переменных					Числа зависимости триад		Триады, полученные после выполнения
триада i		A	B	C		D	dep(i)		алгоритма
1) * (C, B)		0	0	0		0	1		1) * (C, B)
2) + (D, ^1)		0	0	0		0	2		2) + (D, ^1)
3) := (D, ^2)		0	0	0		3	3		3) := (D, ^2)
4) * (C, B)		0	0	0		3	1		4) SAME (1, 0)
5) + (D, ^4)		0	0	0		3	4		5) + (D, ^1)
6) := (A, ^5)		6	0	0		3	5		6) := (A, ^5)
7) * (C, B)		6	0	0		3	1		7) SAME (1, 0)
8) + (D, ^7)		6	0	0		3	4		8) SAME (5, 0)
Функции приложенияФункции администратораФункции пользователя9) := (C, ^5)Общий алгоритм генерации и оптимизации объектного кода9) := (C, ^8) Теперь рассмотрим общий вариант алгоритма генерации кода, который получает на входе дерево вывода (построенное в результате синтаксического разбора) и создает по нему фрагмент объектного кода линейного участка результирующей программы. Алгоритм должен выполнить следующую последовательность действий:  построить последовательность триад на основе дерева вывода;  выполнить оптимизацию кода методом свертки;  выполнить оптимизацию кода методом исключения лишних операций;  преобразовать последовательность триад в последовательность команд на языке ассемблера (полученная последовательность команд и будет результатом выполнения алгоритма). Алгоритм преобразования триад в команды языка ассемблера - это единственная машинно-зависимая часть общего алгоритма. При преобразовании компилятора для работы с другим результирующим объектным кодом потребуется изменить только эту часть, при этом все алгоритмы оптимизации и внутреннее представление программы останутся неизменными. В данной работе алгоритм преобразования триад в команды языка ассемблера предлагается разработать самостоятельно. В тривиальном виде такой алгоритм заменяет каждую триаду на последовательность соответствующих команд, а результат ее выполнения запоминается во временной переменной с некоторым именем (например, TMPi, где i - номер триады). Тогда вместо ссылки на эту триаду в другой триаде будет подставлено значение этой переменной. Однако алгоритм может предусматривать и оптимизацию временных переменных.