{ Функция получения значения константы в операнде

по его номеру }

begin

Operands[iIdx].ConstVal := iVal;

end;

procedure TTriad.SetOpType(iIdx: integer; OpT: TOpType);

{ Функция записи значения константы в операнд

по его номеру }

begin

Operands[iIdx].OpType := OpT;

end;

function IsEqualOp(const Op1,Op2: TOperand): Boolean;

{ Функция проверки совпадения (эквивалентности)

двух операндов }

begin

{ Операнды равны, если совпадают их типы }

Result := (Op1.OpType = Op2.OpType);

{ и значения в зависимости от типа }

if Result then

case Op1.OpType of

OP_CONST: Result := (Op1.ConstVal = Op2.ConstVal);

OP_VAR: Result := (Op1.VarLink = Op2.VarLink);

OP_LINK: Result := (Op1.TriadNum = Op2.TriadNum);

end;

end;

function TTriad.IsEqual(Trd1: TTriad): Boolean;

{ Функция, проверяющая совпадение (эквивалентность)

двух триад }

begin

{ Триады эквивалентны, если совпадают их типы }

Result := (TriadType = Trd1.TriadType)

{ и оба операнда }

and IsEqualOp(Operands[1],Trd1[1])

and IsEqualOp(Operands[2],Trd1[2]);

end;

function GetOperStr(Op: TOperand): string;

{ Функция формирования строки для отображения

оператора триады }

begin

case Op.OpType of

OP_CONST: Result := IntToStr(Op.ConstVal);

OP_VAR: Result := Op.VarLink.VarName;

OP_LINK: Result := '^'+ IntToStr(Op.TriadNum+1);

end{case};

end;

function TTriad.MakeString(i: integer): string;

begin

Result := Format('%d:'#9'%s (%s, %s)',

[i+1,TriadStr[TriadType],

GetOperStr(Opers[1]),GetOperStr(Opers[2])]);

end;

destructor TTriadList.Destroy;

{ Деструктор для удаления списка триад }

begin

{ Очищаем список триад }

Clear;

{ Вызываем деструктор базового класса }

inherited Destroy;

end;

procedure TTriadList.Clear;

{ Процедура очистки списка триад }

var i: integer;

begin

{ Освобождаем память для всех триад из списка }

for i:=Count-1 downto 0 do TTriad(Items[i]).Free;

{ Вызываем функцию базового класса }

inherited Clear;

end;

procedure TTriadList.DelTriad(iIdx: integer);

{ Функция удаления триады из списка триад }

begin

{ Если это не последняя триада }

if iIdx < Count-1 then

{ и если на нее есть ссылка - переставляем

флаг ссылки на предыдущую }

TTriad(Items[iIdx+1]).IsLinked :=

TTriad(Items[iIdx+1]).IsLinked

or TTriad(Items[iIdx]).IsLinked;

{ Освобождаем память триады }

TTriad(Items[iIdx]).Free;

{ Удаляем ссылку на триаду из списка }

Delete(iIdx);

end;

function TTriadList.GetTriad(iIdx: integer): TTriad;

{ Функция выборки триады из списка по её номеру }

begin

Result := TTriad(Items[iIdx]);

end;

procedure TTriadList.WriteToList(list: TStrings);

{ Процедура вывода списка триад в список строк

для отображения списка триад }

var

i,iCnt: integer;

begin

{ Очищаем список строк }

list.Clear;

iCnt := Count-1;

{ Для всех триад из списка триад }

for i:=0 to iCnt do

{ Формируем строковое представление триады

и добавляем его в список строк }

list.Add(TTriad(Items[i]).MakeString(i));

end;

procedure DelTriadTypes(listTriad: TTriadList;

TrdType: TTriadType);

{ Процедура удаления из списка триад всех триад

заданного типа }

var

i,j,iCnt,iDel: integer;

listNum: TList;

Trd: TTriad; { список для запоминания изменений

индексов триад }

begin

{ Вначале изменение индекса нулевое }

iDel := 0;

iCnt := listTriad.Count-1;

{ Создаем список для запоминания изменений

индексов триад }

listNum := TList.Create;

try

{ Для всех триад списка выполняем запоминание

изменений индекса }

for i:=0 to iCnt do

begin

{ Запоминем изменение индекса данной триады }

listNum.Add(TObject(iDel));

{ Если эта триада удаляемого типа,

то увеличиваем изменение индекса }

if listTriad[i].TriadType = TrdType then Inc(iDel);

end;

{ Для всех триад списка изменяем индексы ссылок }

for i:=iCnt downto 0 do

begin

Trd := listTriad[i];

{ Если эта триада удаляемого типа, то удаляем ее }

if Trd.TriadType = TrdType then listTriad.DelTriad(i)

else

{ Иначе для обоих операндов триады смотрим,

не является ли он ссылкой }

for j:=1 to 2 do

if Trd[j].OpType = OP_LINK then

{ Если операнд является ссылкой на триаду,

уменьшаем её индекс }

Trd.Links[j] :=

Trd.Links[j] - integer(listNum[Trd.Links[j]]);

end;

{ Уничтожаем список для запоминания

изменений индексов триад }

finally listNum.Free;

end;

end;

end.

11. TrdAsm

unit TrdAsm;

{ !!! Зависит от целевой вычислительной системы !!! }

interface

{ Модуль распределения регистров и построения ассемблерного

кода по списку триад }

uses Classes, TrdType, Triads;

const

{ Префикс наименования временных переменных }

TEMP_VARNAME = '_Tmp';

{ Количество доступных регистров процессора }

NUM_PROCREG = 6;

{ Функция распределения регистров и временных переменных

для хранения промежуточных результатов триад }

function MakeRegisters(listTriad: TTriadList): integer;

{ Функция построения ассемблерного кода по списку триад }

function MakeAsmCode(listTriad: TTriadList;

listCode: TStrings;

flagOpt: Boolean): integer;

implementation

uses SysUtils;

function MakeRegisters(listTriad: TTriadList): integer;

{ Функция распределения регистров и временных переменных

для хранения промежуточных результатов триад.

Результат: количество необходимых временных переменных }

var

{ Счетчики и переменные циклов }

i,j,iR,iCnt,iNum : integer;

{ Динамический массив для запоминания занятых регистров }

listReg: TList;

begin

Result := 0;

{ Создаем массив для хранения занятых регистров }

listReg := TList.Create;

if listReg <> nil then

try

{ Обнуляем информационное поле у всех триад }

for i:=listTriad.Count-1 downto 0 do

listTriad[i].Info := 0;

{ Цикл по всем триадам. Обязательно с конца списка! }

for i:=listTriad.Count-1 downto 0 do

{ Цикл по всем (2) операндам }

for j:=1 to 2 do

{ Если триада - линейная операция, или "IF"

(первый операнд), или прсвоение (второй операнд) }

if ((listTriad[i].TrdType in TriadLineSet)

or (listTriad[i].TrdType = TRD_IF) and (j = 1)

or (listTriad[i].TrdType = TRD_ASSIGN) and (j = 2))

{ и при этом операндом является ссылка

на другую триаду }

and (listTriad[i][j].OpType = OP_LINK) then

begin

{ Запорминаем номер триады, на которую ссылка }

iNum := listTriad[i][j].TriadNum;

{ Если этой триаде еще не назначен регистр, и если

это не предыдущая триада,

то надо ей назначить регистр }

if (listTriad[iNum].Info = 0) and (iNum <> i-1) then

begin

{ Количество назначенных регистров

в массиве регистров }

iCnt := listReg.Count-1;

{ Цикл по всему массиву назначенных регистров }

for iR:=0 to iCnt do

begin

{ Если область действия регистра за пределами

текущей триады, то этот регистр свободен и

можно его использовать }

if longint(listReg[iR]) >= i then

begin

{ Запоминаем новую область действия регистра

(iNum) }

listReg[iR] := TObject(iNum);

{ Назначаем регистр триаде с номером iNum }

listTriad[iNum].Info := iR+1;

{ Прерываем цикл по массиву регистров }

Break;

end;

end;

{ Если не один из использованных регистров

не был назначен, надо брать новый регистр }

if listTriad[iNum].Info = 0 then

begin

{ Добавляем запись в массив регистров, указываем

ей область действия iNum }

listReg.Add(TObject(iNum));

{ Назначаем новый регистр триаде с номером iNum }

listTriad[iNum].Info := listReg.Count;

end;

end;

end;

{ Результат функции:

количество записей в массиве регистров - 1,

за вычетом количества доступных регистрв процессора }

Result := listReg.Count - (NUM_PROCREG-1);

finally listReg.Free;

end;

end;

function GetRegName(iInfo: integer): string;

{ Функция наименования регистров процессора }

begin

case iInfo of

0: Result := 'al';

1: Result := 'bl';

2: Result := 'dl';

3: Result := 'ah';

4: Result := 'bh';

5: Result := 'ch';

6: Result := 'dh';

7: Result := 'si';

8: Result := 'di';

{ Если это не один из регистров - значит,

даем имя временной переменной }

else Result :=

Format('%s%d',[TEMP_VARNAME,iInfo-NUM_PROCREG]);

end{case};

end;

function GetOpName(i: integer; listTriad: TTriadList;

iOp: integer): string;

{ Функция наименования операнда триады

i - номер триады в списке;

listTriad - список триад;

iOp - номер операнда триады }

var

iNum: integer; {номенр триады по ссылке}

Triad: TTriad; {текущая триада}

begin

{ Запоминаем текущую триаду }

Triad := listTriad[i];

{ Выборка наименования операнда в зависимости от типа }

case Triad[iOp].OpType of

{ Если константа - значение константы }

OP_CONST: Result := IntToStr(Triad[iOp].ConstVal);

{ Если переменная - ее имя из таблицы идентификаторов }

OP_VAR:

begin

Result := Triad[iOp].VarLink.VarName;

{ Если имя совпадает с именем функции,

заменяем его на Result функции }

if Result = NAME_FUNCT then Result := NAME_RESULT;

end;

{ Иначе - это регистр для временного хранения

результатов триады }

else

begin

{ Запоминаем номер триады }

iNum := Triad[iOp].TriadNum;

{ Если это предыдущая триада, то операнд не нужен }

if iNum = i-1 then Result := ''

else

begin

{ Берем номер регистра, связанного с триадой }

iNum := listTriad[iNum].Info;

{ Если регистра нет, то операнд не нужен }

if iNum = 0 then Result := ''

{ Иначе имя операнда - это имя регистра }

else Result := GetRegName(iNum);

end;

end;

end{case};

end;

function MakeMove(const sReg,{имя регистра}

sPrev,{предыдущая команда}

sVal{предыдущая величина в al}: string;

flagOpt: Boolean{флаг оптимизации}): string;

{ Функция, генерящая код занесения значения в регистр al }

begin

{ Если операнд был только что выгружен из al,

или необходимое значение уже есть в аккумуляторе,

нет необходимости записывать его туда снова }

if (Pos(Format(#9'mov'#9'%s,al',[sReg]),sPrev) = 1)

or (sVal = sReg) then

begin

Result := '';

Exit;

end;

if flagOpt then

{ Если оптимизация команд включена }

begin

{ Если значение = 0, то заносим его с помощью XOR }

if sReg = '0' then

begin

if sVal = '-1' then

Result := #9'inc'#9'al'

else

if sVal = '1' then

Result := #9'dec'#9'al'

else

Result := #9'xor'#9'al,al'

end

else

{ Если = 1 - двумя командами: XOR и INC }

if sReg = '1' then

begin

if sVal = '-1' then

Result := #9'neg'#9'al'

else

if sVal = '0' then

Result := #9'inc'#9'al'

else

Result := #9'xor'#9'al,al'#13#10#9'inc'#9'al';

end

else

{ Если = -1 - двумя командами: XOR и DEC }

if sReg = '-1' then

begin

if sVal = '1' then

Result := #9'neg'#9'al'

else

if sVal = '0' then

Result := #9'dec'#9'al'

else

Result := #9'xor'#9'al,al'#13#10#9'dec'#9'al';

end

{ Иначе заполняем al командой MOV }

else Result := Format(#9'mov'#9'al,%s',[sReg]);

end

{ Если оптимизация команд выключена,

всегда заполняем al командой MOV }

else Result := Format(#9'mov'#9'al,%s',[sReg]);

end;

function MakeOpcode(i: integer;{номер текущей триады}

listTriad: TTriadList;{список триад}

const sOp,sReg,{код операции и операнд}

sPrev,{предыдущая команда}

sVal{предыдущая величина в al}: string;

flagOpt: Boolean{флаг оптимизации}): string;

{ Функция, генерящая код линейных операций над al }

var Triad: TTriad;{текущая триада}

begin

{ Запоминаем текущую триаду }

Triad := listTriad[i];

{ Если оптимизация команд включена }

if flagOpt then

begin

{ Если операнд = 0 }

if sReg = '0' then

begin

case Triad.TrdType of

{ Для команды AND результат всегда = 0 }

TRD_AND:

Result := MakeMove('0',sPrev,sVal,flagOpt);

{ Для OR, "+" и "-" ничего не надо делать }

TRD_OR,TRD_ADD,TRD_SUB, TRD_MUL, TRD_DIV: Result := #9#9;

{ Иначе генерим код выполняемой операции }

else Result := Format(#9'%s'#9'al,%s',[sOp,sReg]);

end{case};

end

else

{ Если операнд = 1 }

if sReg = '1' then

begin

case Triad.TrdType of

{ Для команды OR результат всегда = 1 }

TRD_OR:

Result := MakeMove('1',sPrev,sVal,flagOpt);

{ Для AND ничего не надо делать }

TRD_AND: Result := #9#9;

{ Для "+" генерим операцию INC }

TRD_ADD: Result := #9'inc'#9'al';

{ Для "-" генерим операцию DEC }

TRD_SUB: Result := #9'dec'#9'al';

TRD_MUL: Result := #9'mul'#9'al';

TRD_DIV: Result := #9'div'#9'al';

{ Иначе генерим код выполняемой операции }

else Result := Format(#9'%s'#9'al,%s',[sOp,sReg]);

end{case};

end

else

{ Если операнд = -1 }

if sReg = '-1' then

begin

case Triad.TrdType of

{ Для "+" генерим операцию DEC }

TRD_ADD: Result := #9'dec'#9'al';

{ Для "-" генерим операцию INC }

TRD_SUB: Result := #9'inc'#9'al';

{ Для "*" генерим операцию MUL }

TRD_MUL: Result := #9'mul'#9'al';

{ Для "/" генерим операцию DIV }

TRD_DIV: Result := #9'div'#9'al';

{ Иначе генерим код выполняемой операции }

else Result := Format(#9'%s'#9'al,%s',[sOp,sReg]);

end{case};

end

end;

end

{ Если оптимизация команд выключена,

всегда генерим код выполняемой операции }

end;

{ Добавляем к результату информацию о триаде

в качестве комментария }

Result := Result + Format(#9'{ %s }',

[Triad.MakeString(i)]);

end;

function MakeAsmCode(

listTriad: TTriadList;{входной список триад}

listCode: TStrings;{список строк рез. кода}

flagOpt: Boolean{флаг оптимизации}): integer;

{ Функция построения ассемблерного кода по списку триад }

var

i,iCnt: integer;{счетчик и переменная цикла}

sR: string;{строка для имени регистра}

sPrev,sVal: string;

{строки для хранения предыдущей команды и значения al}

procedure TakePrevAsm;

{ Процедура, выделяющая предыдущую команду и значение al

из списка результирующих команд }

var j: integer;

begin

j := listCode.Count;

if j > 0 then

begin

sPrev := listCode[j-1];

sVal := StrPas(PChar(listCode.Objects[j-1]));

end

else

begin

sPrev := '';

sVal := '';

end;

end;

procedure MakeOper1(const sOp,{код операции}

sAddOp: string;{код доп. операции}

iOp: integer{номер операнда в триаде});

{ Функция генерации кода для унарных операций }

var sReg{строка для имени регистра}: string;

begin

{ Берем предыдущую команду и значение из al }

TakePrevAsm;

{ Запоминаем имя операнда }

sReg := GetOpName(i,listTriad,iOp);

{ Если имя пустое, операнд уже есть в регистре al

от выполнения предыдущей триады, иначе его нужно

занести в al - вызываем функцию генерации кода }

if sReg <> '' then

begin

sReg := MakeMove(sReg,sPrev,sVal,flagOpt);

if sReg <> '' then listCode.Add(sReg);

end;

{ Генерим непосредственно код операции }

listCode.Add(Format(#9'%s'#9'al'#9'{ %s }',

[sOp,listTriad[i].MakeString(i)]));

{ Если есть доп. операция, генерим ее код }

if sAddOp <> '' then

listCode.Add(Format(#9'%s'#9'al,1',[sAddOp]));

{ Если триада связана с регистром, запоминаем результат в

этом регистре }

if listTriad[i].Info <> 0 then

begin

sReg := GetRegName(listTriad[i].Info);

{ При этом запоминаем, что сейчас находится в al }

listCode.AddObject(Format(#9'mov'#9'%s,al',[sReg]),

TObject(PChar(sReg)));

end;

end;

procedure MakeOper2(const sOp,{код операции}

sAddOp: string{код доп. операции});

{ Функция генерации кода для бинарных арифметических

и логических операций }

var sReg1,sReg2{строки для имен регистров}: string;

begin

{ Берем предыдущую команду и значение из al }

TakePrevAsm;

{ Запоминаем имя 1 операнда }

sReg1 := GetOpName(i,listTriad,1);

{ Запоминаем имя 2 операнда }

sReg2 := GetOpName(i,listTriad,2);

{ Если имя первого операнда пустое, значит он уже

есть в регистре al от выполнения предыдущей триады -

вызываем функцию генерации кода для второго операнда }

if (sReg1 = '') or (sReg1 = sVal) then

listCode.Add(MakeOpCode(i,listTriad,sOp,sReg2,

sPrev,sVal,flagOpt))

else

{ Если имя второго операнда пустое, значит он уже

есть в регистре al от выполнения предыдущей триады -

вызываем функцию генерации кода для первого операнда }

if (sReg2 = '') or (sReg2 = sVal) then

begin

listCode.Add(MakeOpCode(i,listTriad,sOp,sReg1,

sPrev,sVal,flagOpt));

{ Если есть доп. операция, генерим ее код

(когда операция несимметричная - например "-") }

if sAddOp <> '' then

listCode.Add(Format(#9'%s'#9'al',[sAddOp]));

end

else

{ Если оба операнда не пустые, то надо:

- сначала загрузить в al первый операнд;

- сгенерить код для обработки второго операнда. }

begin

sReg1 := MakeMove(sReg1,sPrev,sVal,flagOpt);

if sReg1 <> '' then listCode.Add(sReg1);

listCode.Add(MakeOpCode(i,listTriad,sOp,sReg2,

sPrev,sVal,flagOpt));

end;

{ Если триада связана с регистром, запоминаем результат в

этом регистре }

if listTriad[i].Info <> 0 then

begin

sReg1 := GetRegName(listTriad[i].Info);

{ При этом запоминаем, что сейчас находится в al }

listCode.AddObject(Format(#9'mov'#9'%s,al',[sReg1]),

TObject(PChar(sReg1)));

end;

end;

procedure MakeCompare(const sOp: string

{флаг операции сравнения});

{ Функция генерации кода для операций сравнения }

var sReg1,sReg2{строки для имен регистров}: string;

begin

{ Берем предыдущую команду и значение из al }

TakePrevAsm;

{ Запоминаем имя 1 операнда }

sReg1 := GetOpName(i,listTriad,1);

{ Запоминаем имя 2 операнда }

sReg2 := GetOpName(i,listTriad,2);

{ Если имя первого операнда пустое, значит он уже

есть в регистре al от выполнения предыдущей триады -

сравниваем al со вторым операндом }

if sReg1 = '' then

listCode.Add(Format(#9'cmp'#9'al,%s'#9'{ %s }',

[sReg2,listTriad[i].MakeString(i)]))

else

{ Если имя второго операнда пустое, значит он уже

есть в регистре al от выполнения предыдущей триады -

сравниваем al с первым операндом в обратном порядке }

if sReg2 = '' then

listCode.Add(Format(#9'cmp'#9'%s,al'#9'{ %s }',

[sReg1,listTriad[i].MakeString(i)]))

else

{ Если оба операнда не пустые, то надо:

- сначала загрузить в al первый операнд;

- сравнить al со вторым операндом. }

begin

sReg1 := MakeMove(sReg1,sPrev,sVal,flagOpt);

if sReg1 <> '' then listCode.Add(sReg1);

listCode.Add(Format(#9'cmp'#9'al,%s'#9'{ %s }',

[sReg2,listTriad[i].MakeString(i)]));

end;

{ Загружаем в младший байт al 1 или 0

в зависимости от флага сравнения }

listCode.Add(Format(#9'set%s'#9'al',[sOp]));

(* Один из вариантов кода:

{ Преобразуем 8 младших бит в 16 бит }

listCode.Add(#9'cbw');

{ Преобразуем 16 младших бит в 32 бита }

listCode.Add(#9'cwde'); *)

(* Другой вариант: *)

listCode.Add(#9'and'#9'al,1');

{ Если триада связана с регистром, запоминаем результат в

этом регистре }

if listTriad[i].Info <> 0 then

begin

sReg1 := GetRegName(listTriad[i].Info);

{ При этом запоминаем, что сейчас находится в al }

listCode.AddObject(Format(#9'mov'#9'%s,al',[sReg1]),

TObject(PChar(sReg1)));

end;

end;

{ Тело основной функции }

begin

{ Берем количество триад в списке }

iCnt := listTriad.Count-1;

{ Цикл по всем триадам от начала списка }

for i:=0 to iCnt do

begin

{ Если триада помечена, создаем локальную метку

в списке команд ассемблера }

if listTriad[i].IsLinked then

listCode.Add(Format('@M%d:',[i+1]));

{ Генерация кода в зависимости от типа триады }

case listTriad[i].TrdType of

{ Код для триады IF }

TRD_IF:

begin

{ Если операнд - констата (это возможно

в результате оптимизации) }

if listTriad[i][1].OpType = OP_CONST then

begin

{ Условный переход превращается в безусловный,

если константа = 0, }

if listTriad[i][1].ConstVal = 0 then

listCode.Add(Format(#9'jmp'#9'@M%d'#9'{ %s }',

[listTriad[i][2].TriadNum+1,

listTriad[i].MakeString(i)]));

{ а иначе вообще генерить код не нужно. }

end

else

{ Если операнд не константа }

begin

{ Берем имя первого операнда }

sR := GetOpName(i,listTriad,1);

{ Если имя первого операнда пустое,

значит он уже есть в регистре al

от выполнения предыдущей триады }

if sR = '' then

{ тогда надо выставить флаг "Z", сравнив al

сам с собой, но учитывая, что предыдущая

триада для IF - это либо сравнение, либо

логическая операция, это можно опустить}

(* listCode.Add(#9'test'#9'al,al') *)

else

{ иначе надо сравнить al с операндом }

listCode.Add(Format(#9'cmp'#9'%s,0',[sR]));

{ Переход по обратному условию "NOT Z"

на ближайшую метку }

listCode.Add(Format(#9'jnz'#9'@F%d'#9'{ %s }',

[i,listTriad[i].MakeString(i)]));

{ Переход по прямому условию на дальнюю метку }

listCode.Add(Format(#9'jmp'#9'@M%d',

[listTriad[i][2].TriadNum+1]));

{ Метка для ближнего перехода }

listCode.Add(Format('@F%d:',[i]));

end;

end;

{ Код для бинарных логических операций }

TRD_OR: MakeOper2('or','');

TRD_XOR: MakeOper2('xor','');

TRD_AND: MakeOper2('and','');

{ Код для операции NOT (т.к. NOT(0)=FFFFFFFF,

то нужна еще операция: AND al,1 }

TRD_NOT: MakeOper1('not','and',1);

{ Код для операций сравнения по их флагам }

TRD_LT: MakeCompare('l');

TRD_GT: MakeCompare('g');

TRD_EQ: MakeCompare('e');

TRD_NEQ: MakeCompare('ne');

{ Код для бинарных арифметических операций }

TRD_ADD: MakeOper2('add','');

TRD_SUB: MakeOper2('sub','neg');

TRD_MUL: MakeOper2('mul','');

TRD_DIV: MakeOper2('div','');

{ Код для унарного минуса }

TRD_UMIN: MakeOper1('neg','',2);

{ Код для операции присвоения }

TRD_ASSIGN:

begin

{ Берем предыдущую команду и значение из al }

TakePrevAsm;

{ Берем имя второго операнда }

sR := GetOpName(i,listTriad,2);

{ Если имя первого операнда пустое,

значит он уже есть в регистре al

от выполнения предыдущей триады }

if sR <> '' then

begin

{ иначе генерим код загрузки операнда в al }

sVal := MakeMove(sR,sPrev,sVal,flagOpt);

if sVal <> '' then listCode.Add(sVal);

end;

{ Из al записываем результат в переменную

с именем первого операнда }

sVal := listTriad[i][1].VarLink.VarName;

if sVal = NAME_FUNCT then sVal := NAME_RESULT;

sVal := Format(#9'mov'#9'%s,al'#9'{ %s }',

[sVal,listTriad[i].MakeString(i)]);

{ При этом запоминаем, что было в al }

listCode.AddObject(sVal,TObject(PChar(sR)));

end;

{ Код для операции безусловного перехода }

TRD_JMP: listCode.Add(

Format(#9'jmp'#9'@M%d'#9'{ %s }',

[listTriad[i][2].TriadNum+1,

listTriad[i].MakeString(i)]));

{ Код для операции NOP }

TRD_NOP: listCode.Add(Format(#9'nop'#9#9'{ %s }',

[listTriad[i].MakeString(i)]));

end{case};

end{for};

Result := listCode.Count;

end;

end.

12. TrdCalc

unit TrdCalc; {!!! Зависит от входного языка !!!}

interface

{ Модуль, вычисляющий значения триад при свертке операций }

uses TrdType;

{ Функция вычисления триады по типу и значениям

двух операндов }

function CalcTriad(Triad: TTriadType;

iOp1,iOp2: integer): integer;

implementation

function CalcTriad(Triad: TTriadType;

iOp1,iOp2: integer): integer;

{ Функция вычисления триады по типу и значениям

двух операндов }

begin

Result := 0;

case Triad of

TRD_OR: Result := (iOp1 or iOp2) and 1;

TRD_XOR: Result := (iOp1 xor iOp2) and 1;

TRD_AND: Result := (iOp1 and iOp2) and 1;

TRD_NOT: Result := (not iOp1) and 1;

TRD_LT: if iOp1<iOp2 then Result := 1 else Result := 0;

TRD_GT: if iOp1>iOp2 then Result := 1 else Result := 0;

TRD_EQ: if iOp1=iOp2 then Result := 1 else Result := 0;

TRD_NEQ: if iOp1<>iOp2 then Result := 1 else Result := 0;

TRD_ADD: Result := iOp1 + iOp2;

TRD_SUB: Result := iOp1 - iOp2;

TRD_MUL: Result := iOp1 * iOp2;

TRD_DIV: Result := iOp1 / iOp2;

TRD_UMIN: Result := -iOp2;

end;

end;

end.

13. TrdMake

unit TrdMake; {!!! Зависит от входного языка !!!}

interface

{ Модуль, обеспечивающий создание списка триад на основе

структуры синтаксического разбора }

uses LexElem, Triads, SyntSymb;

function MakeTriadList(symbTop: TSymbol;

listTriad: TTriadList): TLexem;

{ Функция создания списка триад начиная от корневого

символа дерева синтаксического разбора.

Функция возвращает nil при успешном выполнении, иначе

она возвращает ссылку на лексему, где произошла ошибка }

implementation

uses LexType, TrdType;

function GetLexem(symbOp: TSymbol): TLexem;

{ Функция, проверяющая является ли операнд лексемой }

begin

case symbOp.Rule of

{ Если правил нет, это лексема! }

0: Result := symbOp.Lexem;

{ Если дочерний символ построен по правилу №27 или 28,

то это лексема }

27,28: Result := symbOp[0].Lexem;

{ Если это арифметические скобки, надо проверить,

не является ли лексемой операнд в скобках }

19,26: Result := GetLexem(symbOp[1])

{ Иначе это не лексема }

else Result := nil;

end;

end;

function MakeTriadListNOP(symbTop: TSymbol;

listTriad: TTriadList): TLexem;

{ Функция создания списка триад начиная от корневого

символа дерева синтаксического разбора (без добавления

триады NOP в конец списка) }

var

Opers: TOpArray; { массив операндов триад }

iIns1,iIns2,iIns3: integer; { переменные для запоминания

индексов триад в списке }

function MakeOperand(

iOp{номер операнда},

iSymOp{порядковый номер символа в синт. конструкции},

iMin{минимальная позиция триады в списке},

iSymErr{номер лексемы, на которой

позиционировать ошибку}: integer;

var iIns: integer{индекс триады в списке}): TLexem;

{ Функция формирования ссылки на операнд }

var lexTmp: TLexem;

begin

{ Проверяем, является ли операнд лексемой }

lexTmp := GetLexem(symbTop[iSymOp]);

if lexTmp <> nil then

{ Если да, то берем имя операнда в зависимости от типа }

with lexTmp do

begin

if LexType = LEX_VAR then

begin

if VarInfo.VarName = NAME_RESULT then

begin

{ Проверяем, что переменная имеет допустимое имя }

Result := lexTmp;

Exit;

end;

{ Если это переменная, то запоминаем ссылку

на таблицу идентификаторов }

Opers[iOp].OpType := OP_VAR;

Opers[iOp].VarLink := VarInfo;

end

else

if LexType = LEX_CONST then

begin

{ Если это константа, то запоминаем её значение }

Opers[iOp].OpType := OP_CONST;

Opers[iOp].ConstVal := ConstVal;

end

else

begin

{ Иначе это ошибка, возвращаем лексему как указатель

на место ошибки }

Result := lexTmp;

Exit;

end;

iIns := iMin;

Result := nil;

end

else

{ иначе это синтаксическая конструкция }

begin

{ Вызываем рекурсивно функцию создания списка триад }

Result := MakeTriadListNOP(symbTop[iSymOp],listTriad);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Запоминаем индекс триады }

iIns := listTriad.Count;

{ Если индекс меньше минимального (сисок не менялся) -

это ошибка }

if iIns <= iMin then

begin

Result := symbTop[iSymErr].Lexem;

Exit;

end;

{ Запоминаем ссылку на предыдущую триаду }

Opers[iOp].OpType := OP_LINK;

Opers[iOp].TriadNum := iIns-1;

end;

end;

function MakeOperation(

Trd: TTriadType{тип создаваемой триады}): TLexem;

{ Функция создания списка триад для линейных операций }

begin

{ Создаем ссылку на первый операнд }

Result := MakeOperand(1{op},0{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Создаем ссылку на второй операнд }

Result := MakeOperand(2{op},2{sym},iIns1,

1{sym err},iIns2);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Создаем саму триаду с двумя ссылками на операнды }

listTriad.Add(TTriad.Create(Trd,Opers));

end;

begin

{ Тело главной функции. Начинаем с выбора типа правила }

case symbTop.Rule of

5:{'if(B)EelseE'}

{ Полный условный оператор }

begin

{ Запоминаем ссылку на первый операнд

(условие "if(B)") }

Result := MakeOperand(1{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Второй операнд - ссылка на триаду, номер которой

пока не известен }

Opers[2].OpType := OP_LINK;

Opers[2].TriadNum := 0;

{ Создаем триаду типа "IF" }

listTriad.Add(TTriad.Create(TRD_IF,Opers));

{ Запоминаем ссылку на второй операнд

(раздел "(B)E") }

Result := MakeOperand(2{op},4{sym},iIns1,

3{sym err},iIns2);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Заполняем операнды для триады типа "JMP",

которая должна быть в конце раздела "(B)E" }

Opers[1].OpType := OP_CONST;

Opers[1].ConstVal := 1;

{ Второй операнд - ссылка на триаду, номер которой

пока не известен }

Opers[2].OpType := OP_LINK;

Opers[2].TriadNum := 0;

{ Создаем триаду типа "JMP" }

listTriad.Add(TTriad.Create(TRD_JMP,Opers));

{ Для созданной ранее триады типа "IF" ставим

ссылку в конец последовательности триад,

созданной для раздела "(B)E" }

listTriad[iIns1].Links[2] := iIns2+1;

{ Запоминаем ссылку на третий операнд

(раздел "elseE") }

Result := MakeOperand(2{op},6{sym},iIns2,

5{sym err},iIns3);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Для созданной ранее триады типа "JMP" ставим

ссылку в конец последовательности триад,

созданной для раздела "elseE" }

listTriad[iIns2].Links[2] := iIns3;

end;

6:{'if(B)E'}

{ Неполный условный оператор }

begin

{ Запоминаем ссылку на первый операнд

(условие "if(B)") }

Result := MakeOperand(1{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Второй операнд - ссылка на триаду, номер которой

пока не известен }

Opers[2].OpType := OP_LINK;

Opers[2].TriadNum := 0;

{ Создаем триаду типа "IF" }

listTriad.Add(TTriad.Create(TRD_IF,Opers));

{ Запоминаем ссылку на второй операнд

(раздел "(B)E") }

Result := MakeOperand(2{op},4{sym},iIns1,

3{sym err},iIns2);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Для созданной ранее триады типа "IF" ставим

ссылку в конец последовательности триад,

созданной для раздела "(B)E" }

listTriad[iIns1].Links[2] := iIns2;

end;

8:{'repeat(B)doE'}

{ Оператор цикла "repeat" }

begin

{ Запоминаем ссылку на первый операнд

(условие "repeat(B)") }

iIns3 := listTriad.Count;

Result := MakeOperand(1{op},2{sym},iIns3,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Второй операнд - ссылка на триаду, номер которой

пока не известен }

Opers[2].OpType := OP_LINK;

Opers[2].TriadNum := 0;

{ Создаем триаду типа "IF" }

listTriad.Add(TTriad.Create(TRD_IF,Opers));

{ Запоминаем ссылку на второй операнд

(раздел "doE") }

Result := MakeOperand(2{op},5{sym},iIns1,

4{sym err},iIns2);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Заполняем операнды для триады типа "JMP", которая

должна быть в конце раздела "doE" }

Opers[1].OpType := OP_CONST;

Opers[1].ConstVal := 1;

{ Второй операнд - ссылка на начало созданного

списка триад }

Opers[2].OpType := OP_LINK;

Opers[2].TriadNum := iIns3;

{ Создаем триаду типа "JMP" }

listTriad.Add(TTriad.Create(TRD_JMP,Opers));

{ Для созданной ранее триады типа "IF" ставим

ссылку в конец последовательности триад,

созданной для раздела "doE" }

listTriad[iIns1].Links[2] := iIns2+1;

end;

9:{'a:=E'}

{ Оператор присвоения }

begin

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

то это ошибка }

if symbTop[0].Lexem.LexType <> LEX_VAR then

begin

Result := symbTop[0].Lexem;

Exit;

end;

{ Если имя первого операнда совпадает с именем

параметра, то это семантическая ошибка }

if (symbTop[0].Lexem.VarName = NAME_INPVAR)

or (symbTop[0].Lexem.VarName = NAME_RESULT) then

begin

Result := symbTop[0].Lexem;

Exit;

end;

{ Создаем ссылку на первый операнд - переменную }

Opers[1].OpType := OP_VAR;

Opers[1].VarLink := symbTop[0].Lexem.VarInfo;

{ Создаем ссылку на второй операнд }

Result := MakeOperand(2{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Создаем триаду типа "присвоение" }

listTriad.Add(TTriad.Create(TRD_ASSIGN,Opers));

end;

{ Генерация списка триад для линейных операций }

10:{'BorB'} Result := MakeOperation(TRD_OR);

11:{'BxorB'} Result := MakeOperation(TRD_XOR);

13:{'BandB'} Result := MakeOperation(TRD_AND);

15:{'E<E'} Result := MakeOperation(TRD_LT);

16:{'E>E'} Result := MakeOperation(TRD_GT);

17:{'E=E'} Result := MakeOperation(TRD_EQ);

18:{'E<>E'} Result := MakeOperation(TRD_NEQ);

21:{'E-E'} Result := MakeOperation(TRD_SUB);

22:{'E+E'} Result := MakeOperation(TRD_ADD);

30:{'E*E'} Result := MakeOperation(TRD_MUL);

31:{'E/E'} Result := MakeOperation(TRD_DIV);

20:{not(B)}

begin

{ Создаем ссылку на первый операнд }

Result := MakeOperand(1{op},2{sym},listTriad.Count,

1{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Второй операнд для унарной операции NOT

не имеет значения }

Opers[2].OpType := OP_CONST;

Opers[2].ConstVal := 0;

{ Создаем триаду типа "NOT" }

listTriad.Add(TTriad.Create(TRD_NOT,Opers));

end;

24:{uminE}

begin

{ Создаем ссылку на второй операнд }

Result := MakeOperand(2{op},1{sym},listTriad.Count,

0{sym err},iIns1);

{ Если произошла ошибка, прерываем выполнение }

if Result <> nil then Exit;

{ Первый операнд для унарной операции "-"

должен быть 0 }

Opers[1].OpType := OP_CONST;

Opers[1].ConstVal := 0;

{ Создаем триаду типа "UMIN" }

listTriad.Add(TTriad.Create(TRD_UMIN,Opers));

end;

{ Для логических, арифметических или операторных скобок

рекурсивно вызываем функцию для второго символа }

1,7,19,26:{'progEend.','beginEend','(E)','(B)'}

Result := MakeTriadListNOP(symbTop[1],listTriad);

{ Для списка операторов нужно рекурсивно вызвать

функцию два раза }

3:{E;E}

begin

Result := MakeTriadListNOP(symbTop[0],listTriad);

if Result <> nil then Exit;

Result := MakeTriadListNOP(symbTop[2],listTriad);

end;

{ Для лексем ничего делать не нужно }

27,28: Result := nil;

{ Во всех остальных случаях нужно рекурсивно вызвать

функцию для первого символа }

else Result := MakeTriadListNOP(symbTop[0],listTriad);

end{case Rule};

end;

function MakeTriadList(symbTop: TSymbol;

listTriad: TTriadList): TLexem;

{ Функция создания списка триад начиная от корневого

символа дерева синтаксического разбора }

var

i: integer;

Opers: TOpArray;

Trd: TTriad;

begin

{ Создаем список триад }

Result := MakeTriadListNOP(symbTop,listTriad);

{ Если произошла ошибка, прерываем выполнение,

иначе продолжаем... }

if Result = nil then

with listTriad do

begin

{ Создаем пустую триаду "NOP" в конце списка }

Opers[1].OpType := OP_CONST;

Opers[1].ConstVal := 0;

Opers[2].OpType := OP_CONST;

Opers[2].ConstVal := 0;

Add(TTriad.Create(TRD_NOP,Opers));

{ Для всех триад в списке расставляем флаг ссылки }

for i:=Count-1 downto 0 do

begin

Trd := Triads[i];

if Trd.TrdType in [TRD_IF,TRD_JMP] then

begin

{ Если триада типа "переход" ("IF" или "JMP")

и ссылается на другую триаду,

то ту триаду надо пометить }

if Trd.OpTypes[2] = OP_LINK then

listTriad[Trd.Links[2]].IsLinked := True;

end;

end;

end;

end;

end.

14. TrdType

unit TrdType; {!!! Зависит от входного языка !!!}

interface{ Модуль для описания допустимых типов триад }

const

NAME_PROG = 'myCursov';

NAME_INPVAR = 'InpVar';

NAME_RESULT = 'Result';

NAME_FUNCT = 'CompileTest';

NAME_TYPE = 'word';

type

{ Типы триад, соответствующие типам допустимых операций,

а также три дополнительные типа триад:

- CONST - для алгоритма свёртки объектного кода;

- SAME - для алгоритма исключения лишних операций;

- NOP (No OPerations) - для ссылок на конец списка триад.

}

TTriadType = (TRD_IF, TRD_OR, TRD_XOR, TRD_AND, TRD_NOT,

TRD_LT, TRD_GT, TRD_EQ, TRD_NEQ,

TRD_ADD, TRD_SUB, TRD_MUL, TRD_DIV, TRD_UMIN, TRD_ASSIGN,

TRD_JMP, TRD_CONST, TRD_SAME, TRD_NOP);

{ Массив строковых обозначений триад

для вывода их списка на экран }

TTriadStr = array[TTriadType] of string;

const

TriadStr: TTriadStr =

('if','or','xor','and','not',

'<','>','=','<>','+','-','-',':=',

'jmp','C','same','nop', '*','/',);

{ Множество триад, которые являются линейными операциями }

TriadLineSet : set of TTriadType =

[TRD_OR, TRD_XOR, TRD_AND, TRD_NOT, TRD_ADD, TRD_SUB,

TRD_LT, TRD_GT, TRD_EQ, TRD_NEQ, TRD_UMIN, TRD_MUL, TRD_DIV];

implementation

end.

4. Результати роботи

Вихідний стан

Таблиця лексем

Синтаксичне дерево

Тріади:

Команди

Висновки

Під час виконання даної курсової роботи я розглянула основні складові частини компілятора, практично дослідила основні принципи побудови і функціонування компіляторів. Освоїла методи побудови простих компіляторів для заданої вихідної мови.

Перелік використаної літератури

1. Гордеев А. В. Молчанов Л. Ю. Системное программное обеспечение, - СПб.: Питер. 2002. - 734с.

2. Кампапиец Р. II. Манькоп Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Учеб. пособие для высших и средних учебных заведений. - СПб.: КОРОНА Принт, 2000. - 256 с.

3. Архангельский А.Я. Программирование в Delphi 6 - М.: ЗАО «Издательство БИНОМ», 2003. - 1120 с., ил.

4. Системное программное обеспечение. Лабораторный практикум/ А.Ю. Молчанов- СПб.: Питер, 2005.- 284 с.

Размещено на Allbest.ru