Транслятор - с чем его едят…

С чего бы начать?

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

1. Двухпроходный транслятор

Достоинства	Недостатки
2-проходный транслятор — это классика (сомнительное достоинство)	Один и тот же файл придется просмотреть и проанализировать целых два раза
Экономия памяти (по сравнению с 1.5-проходным)	Низкое быстродействие

2. Полуторапроходный транслятор

Достоинства	Недостатки
Анализ файла и генерация кода осуществляются в один проход	Требуются дополнительные затраты памяти
Кирпичный оценит этот метод	Кирпичный может и не оценить (хотя вряд ли)
Более высокое быстродействие	Небольшие трудности при генерации листинга
Более простая программа

Теперь по порядку. Двухпроходный транслятор — это классическая модель транслятора. Его принцип действия заключается в следующем: трансляция разбивается на два этапа (или прохода): первый этап — выяснение адресов меток и данных, второй этап — собственно генерация кода. На первом этапе транслятор не генерирует код, а только определяет размер каждой инструкции и сопоставляет каждой метке ее адрес; так как для определения размера инструкции требуется провести ее анализ, на первом проходе выявляется большинство ошибок. По логике вещей, если первый проход завершился неудачей (в смысле, были обнаружены ошибки), второй проход делать не следовало бы, да не тут то было: пользователь хочет получить листинг! Поэтому приходится делать второй проход, причем необходимо предусмотреть, чтобы сообщения об ошибках не дублировались. На втором проходе транслятор (опять!) анализирует каждую строку входного файла (разбивает ее на метку, инструкцию, операнды, — в общем, выполняет почти все операции, сделанные при первом проходе) и генерирует объектный код и листинг программы. По опыту могу сказать, что генерация кода — самый нудный процесс (хотя совсем не тяжелый) и именно благодаря ней исходник программы разрастается, как сорняки после хорошего дождя. На втором проходе единственная обнаруживаемая ошибка, не встречающаяся при первом просмотре — это ссылки на неопределенные метки. Примерно так оно работает. Если у меня получилось объяснить, то из вышесказанного заметно, что одну и ту же работу с вариациями на тему транслятор выполняет дважды и хорошо бы это все объединить и сделать один раз; так и родилась идея построения полуторапроходного транслятора. Возможно, эта идея не нова, но в литературе я ее не встречал. Итак…

В полуторапроходном трансляторе отсутствует основной недостаток двухпроходного транслятора — все делается один единственный раз. Наш девиз: "Ничего не делай дважды" (так и родился генератор курсовиков по программированию, но это другая история…). Сначала о необычном (ненормальном) названии транслятора: честно говоря, за один просмотр далеко не всегда можно сгенерировать код (ну, например, когда есть обращение к метке, которая находится далеко-далеко впереди). Однако второй просмотр файла не производится, проблема решается немного иначе (это и есть заключительный полуторный просмотр), но об этом чуть позже…

Чтобы решить проблему "ссылок вперед", заводится небольшой динамический массив, элементами которого является что-нибудь типа записи:

TReference = Record

LabelName: String;

TargetOffset: Word;

Relative: Boolean;

Line: Integer;

End;

LabelName — имя метки, на которую производится ссылка, TargetOffset — адрес, откуда производится ссылка, Relative — признак относительной адресации (он необходим, поверь пока на слово), Line — номер строки, в которой обнаружена ссылка.

Все метки собраны в отсортированную по имени метки таблицу, элементы которой имеют следующий вид (это справедливо и для 2-проходного транслятора):

TLabel = Record

Name: String;

Offset: Word;

End;

Name — имя метки, Offset — ее адрес.

Алгоритм работы 1.5-проходного транслятора выглядит примерно так: при первом просмотре происходит чтение и анализ входного файла, а также генерация кода; если встречается ссылка на еще неизвестную метку, ссылка запоминается в массиве, а вместо смещения, соответствующего метке, в буфер кода записывается ноль. Так просматривается весь файл. Затем, если были ссылки вперед (наш специальный массивчик не пуст), то проводится заключительный "полупроход" (не знаю, какое слово подобрать), суть которого состоит в следующем: в таблице меток ищется метка с именем LabelName; если она не найдена, то выдается сообщение об ошибке (ссылка на несуществующую метку), в противном случае, в буфер кода по адресу TargetOffset записывается поле Offset записи найденной метки:

PWord (@Buf [Ref [I].TargetOffset])^ := L^.Offset;

где Buf: Array [0..65536] Of Byte – буфер кода, Ref [I] — текущая ссылка, L — указатель на метку в таблице меток, PWord = ^Word (пару слов по поводу PWord: Buf — это массив байтов, в который нам нужно запихнуть слово. Если написать Buf [Ref [I].TargetOffset] := L^.Offset, то значение L^.Offset будет урезано до байта и только затем записано в массив, а это немного не то, ведь нам нужно записать слово, а не байт; @Buf [Ref [I].TargetOffset] возвращает адрес (типа Pointer — указатель на все, что угодно) байта Ref [I].TargetOffset в массиве Buf; так как результат операции взятия адреса — это указатель (и, кроме того, адрес J), то, чтобы записать что-нибудь по адресу, на который указывает указатель, нужно провести разадресацию (допустим, P: ^Word, тогда, чтобы записать значение туда, куда указывает P, нужно записать P^:=…; точно так же и здесь, с той разницей, что так как Pointer — указатель на все, что движется, то необходимо привести тип. Это все равно, что бы ты написала PWord (P)^ := …). Если это немного непонятно, объясню детальнее при встрече). Все было бы хорошо, если б не команда JGE: все команды перехода (ладно, почти все) используют так называемую относительную адресацию. При относительной адресации вместо абсолютного адреса записывается разница между адресом метки и адресом инструкции, следующей за JGE. Признаком относительной адресации является поле Relative. Таким образом, финальный полупроход — это что-то типа этого:

For I := 0 To Refs.Count – 1 Do

Begin

New (L);

R := PReference (Refs.GetItem (I))^;

L^.Name := R.LabelName;

If Lbls.Search (L, Idx) Then

Begin

Dispose (L);

L := Lbls.GetItem (Idx);

If R.Relative Then

PWord (@Buf [R.TargetOffset])^ := L^.Offset – R.TargetOffset – 1

Else

PWord (@Buf [R.TargetOffset])^ := L^.Offset;

End

Else

Error ('Обращение к несуществующей метке ' + R.LabelName);

End;

Комментарии: таблицы меток и ссылок реализованы объектами (классами) вроде тех, что были в пятой лабе по СП в том семестре. Реализация этого всего дела находится в модуле Collections.pas, который прилагается.

Хоть это и выглядит страшным, но, поверь, это гораздо проще двухпроходного транслятора. В этом варианте полупроход занимает 17 строк, в то время как блок первого прохода в двухпроходном трансляторе у меня занял что-то около 165 (ну ладно, писал не для себя, если бы подумал, то сократил бы строчек на 20, но не больше), ну а про второй проход я вообще молчу.

Разбор строк

Программа на ассемблере (согласно методе) может иметь следующий вид:

segname segment

;code goes here

;…

ret

;Data go here

; db …

; dw …

segname ends

end

То есть любая программа должна начинаться со строки вида segname segment, причем вместо слова "segname" может стоять любой идентификатор. Но кто сказал, что перед этой строкой не может быть пустых строк или комментариев? Поэтому их необходимо пропустить. Да, кстати. Чуть выше я упоминал, что при использовании 1.5-проходного транслятора возникают некоторые трудности с листингом. Для того, чтобы нормально строить листинг, придется использовать еще один класс, порожденый от TCollection — TLinesCollection (Listing.pas); обрати внимание, что TLabelCollection и TLinesCollection очень похожи — преимущество объектно-ориентированного подхода… Есть предложение проводить разбор не самого файла, а коллекции строк (которая TLinesCollection), т. е. предварительно прочитать файл в эту коллекцию. И, как показывает практика, этот подход удобнее. Алгоритм первого прохода выглядит примерно так:

1. Пропуск пустых строк и комментариев

2. Если конец (пропустили все строки), то выдать сообщение об ошибке (неожиданный конец файла) и выйти

3. Взять текущую строку и раздраконить ее (по идее, следующая строка после пустых (она же текущая) — это строка типа segname segment):

3.1. Убрать комментарий (если есть)

3.2. Убрать все пробелы и табуляции слева и справа

3.3. Перевести строку в верхний регистр (для удобства)

3.4. Заменить табуляции пробелами (это по желанию)

3.5. Выделить первое слово

3.6. Если первое слово может быть идентификатором, то запомнить его как имя сегмента, иначе выдать какое-нибудь сообщение об ошибке

3.7. Выделить второе слово

3.8. Если оно равно SEGMENT, то все в порядке, иначе сказать пользователю, чтобы он так не шутил (ошибка: ожидается SEGMENT)

3.9. Если в строке еще что-нибудь осталось, выдать сообшение об ошибке (лишние символы в строке)

4. Организовать цикл от следующей строки до последней строки (For I := Line + 1 To Listing.Count – 1 Do)

4.1. Взять очередную строку (S := Listing.Lines [I]) и раздраконить ее:

4.1.1. Перевести в верхний регистр, убрать комментарии, лишние пробелы слева и справа

4.1.2. Разбить полученную строку на метку, инструкцию, первый операнд и второй операнд (вот об этом и пойдет речь в этом разделе)

4.2. Если метка — непустая строка, то:

4.2.1. Проверить, определена ли метка (New (L); L^.Name := Lbl; If Lbls.Search (L, Z)) Then {Метка определена})

4.2.2. Если да, то выдать сообщение об ошибке (повторное определение метки)

4.2.3. Иначе добавить метку в коллекцию меток (L^.Offset := IP; Lbls.Insert (L))

4.3. Если инструкция — пустая строка, то перейти к следующей итерации цикла (Continue)

4.4. Если первый операнд — DB или DW (почему именно первый операнд, я объясню ниже), то:

4.4.1. Метке присвоить значение инструкции, инструкции присвоить значение первого операнда, первому операнду присвоить значение второго операнда.

4.4.2. Выполнить действия, аналогичные п. 4.2.

4.5. Иначе, если первый операнд — ENDS, то:

4.5.1. Если инструкция — имя сегмента (которое мы запомнили выше, в п. 3.6), то

4.5.1.1.Установить в TRUE какой-нибудь флаг (сигнализирующий о том, что конец сегмента найден)

4.5.1.2.Пропустить все пустые строки

4.5.1.3.Если конец (пропустили все), то выдать сообщение об ошибке (неожиданный конец файла)

4.5.1.4.Иначе, если текущая строка (после раздраконивания) — END, то найден конец программы, выходим

4.5.1.5.Иначе говорим, что ожидалось слово END и выходим все равно

4.5.2. Иначе говорим пользователю, что он перепутал имя сегмента; дальше можно выполнить пункты 4.5.1.1-4.5.1.5, а можно просто выйти

4.6. Иначе, если инструкция — END, собщаем, что пользователь оставил сегмент открытым и выходим

4.7. Генерировать код для текущей инструкции

5. Если конец сегмента не был найден, то собщаем, что пользователь оставил сегмент открытым, а также забыл написать END в конце.

6. Конец

По-хорошему, в п. 4.5 следовало бы убедиться, что второй операнд — пустая строка, а в п. 4.6 следовало убедиться, что оба операнда — пустые строки.

А теперь собственно разбор строки.

Каждая строка в файле может иметь следующий вид (в квадратных скобках заключены необязательные элементы):

[Метка:] [Инструкция [Операнд1 [, Операнд2]]] [;Комментарий]

или

[Имя] [Директива или DB или DW [Операнд1]] [;Комментарий]

Таким образом, метка — это идентификатор, за которым следует двоеточие (но в имя метки оно не включается); инструкция — это идентификатор до первого пробела или табуляции; первый операнд — это все до запятой (или до конца строки), а второй операнд — это все остальное. Обрати внимание, что поле ИМЯ двоеточием не оканчивается, поэтому оно будет понято как ИНСТРУКЦИЯ (это по поводу п. 4.4).

Хорошая новость: тебе не придется писать процедуры для удаления ненужных пробелов/табуляций слева и справа: в Delphi (по крайней мере, в D6) есть процедуры Trim, TrimLeft and TrimRight. TrimLeft удаляет разделители слева, TrimRight — справа, Trim — с обеих сторон. Для перевода строки в верхний регистр удобно использовать функцию UpperCase.

Далее. операндом может быть: а) регистр; б) непосредственный операнд; в) операнд в памяти. Регистр отлечить очень легко: это AX, CX, DX, BX, SP, BP, SI, DI, AL, CL, DL, BL, AH, CH, DH или BH. С непосредственным операндом чуть тяжелее: это может быть: а) десятичное число; б) шестнадцатеричное (Word говорит "шестнадцатеричное", Lingvo — и "шестнадцатеричное", и "шестнадцатиричное") число; в) OFFSET метка. К счастью, непосредственный операнд может быть только вторым операндом в памяти. С десятичными числами все просто. Шестнадцатеричные числа долны начинаться с цифры и заканчиваться постфиксом (или суффиксом) H. Для перевода шестнадцатеричного числа (строки) в целое (Integer) можно воспользоваться стандартной функцией Delphi StrToInt, но с небольшой хитростью: сначала нужно удалить постфикс H, а затем добавить $ перед строкой:

Delete (S, Length (S), 1);

X := StrToInt ('$' + S);

С OFFSET метка меньше всего проблем: удаляешь OFFSET и запоминаешь ссылку на метку:

Delete (S, 1, Length ('OFFSET'));

TrimLeft (S);

New (Ref); //Ref: PReference;

Ref^.LabelName := S;

Ref^.TargetOffset := IP;

Ref^.Relative := True //If Cmd='JGE' Else False

Ref^.Line := LineNumber;

Refs.Insert (Ref);

Кстати: результат директивы OFFSET всегда шестнадцатибитный.

С операндом в памяти больше всего возни. Он может иметь одну из следующих форм:

[константа]

[BYTE константа]

[WORD константа]

Операнд в памяти легко отличить по окружающим его квадратным скобкам. Если внутри скобок указано слово BYTE, то результат восьмибитный, если WORD — то шестнадцатибитный, в противном случае размер результата определяется размером используемого регистра (если он есть). В случае, когда размер операнда определить нельзя (например, MOV [0100h], 45h), должно выдаваться сообщение об ошибке. С константой разбираемся точно также, как и с непосредственным операндом.

Генерация кода: подход, позволяющий упростить транслятор

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

Код	30	31	32	33	34	35
Мнемокод	xor r/m, r8	xor r/m, r16	xor r8, r/m	xor r16, r/m	xor al, i8	xor ax, i16
Код	7D	80 xx110xxx	81 xx110xxx	88	89	8A
Мнемокод	jge/jnl rel8	xor r/m8, i8	xor r/m16, i16	mov r/m, r8	mov r/m, r16	mov r8,r/m
Код	8B	A0	A1	A2	A3	B0-B7
Мнемокод	mov r16,r/m	mov al, m8	mov ax, m16	mov m8, al	mov m16, ax	mov r8, i8
Код	B8-BF	C3	C5	C6	F6 11100xxx	F7 11100xxx
Мнемокод	mov r16,i16	ret	mov m, i8	mov m, i16	mul r8	mul r16
Код	82 xx110xxx	83 xx110xxx
Мнемокод	xor r/m8, i8	xor r/m16, i8

Если внимательно посмотреть на таблицу, можно заметить, что команды MOV и XOR почти одинаковый набор способов адресации. Однако о MOV/XOR чуть позже. С точки зрения генерации кода, команда RET не требует дополнительного внимания: просто записывается C3 в выходной буфер и увеличивается на 1 указатель текущей позиции в буфере (IP). С командой MUL тоже не должно возникнуть проблем: ее размер — строго два байта; в буфер записываются код операции (F6 или F7) и E0+номер регистра; IP+=2. Примерно также обстоят дела с JGE: записываются 7D 00 и запоминается ссылка на метку (не забудь установить Ref^.Relative в True). А теперь о MOV/XOR и упрощении процесса трансляции. Существуют такие способы адресации:

· AL, M8

· AX, M16

· R8, R8

· R8, M8

· R16, R16

· R16, M16

· AL, Imm8

· AX, Imm16

· R8, Imm8

· R16, Imm16

· R16, Imm8 (!)

· M8, AL

· M16, AX

· M8, R8

· M8, I8

· M16, R16

· M16, Imm16

· M16, Imm8 (!)

Адресация	Код для MOV	Код для XOR
AL, [disp16]	A0 disp16	32 06 disp16
AL, Imm8	B0 imm8	34 imm8
AX, [disp16]	A1 disp16	33 06 disp16
AX, Imm16	B8 imm16	35 imm16
R8, R8	8A mrm	32 mrm
R8, [byte disp16]	8A mrm disp16	32 mrm disp16
R8, Imm8	B0+r8 imm8	80 F0+r8 imm8
R16, R16	8B mrm	33 mrm
R16, [word disp16]	8B mrm disp16	33 mrm disp16
R16, Imm16	B8+r16, imm16	81 F0+r16 imm16
R16, Imm8	error	83 F0+r16 imm8
[byte disp16], AL	A2 disp16	30 06 disp16
[byte disp16], R8	88 mrm disp16	30 mrm disp16
[byte disp16], I8	C6 disp16 imm8	80 36 disp16 imm8
[word disp16], AX	A3 disp16	31 06 disp16
[word disp16], R16	89 mrm disp16	31 mrm disp16
[word disp16], Imm16	C7 disp16 imm16	81 36 disp16 imm16
[word disp16], Imm8	error	83 36 disp16 imm8

mrm — это байт ModRM

Способы R8, M8 и R8, R8 одинаково кодируются => их можно объединить

Способы R16, M16 и R16, R16 одинаково кодируются => их можно объединить

Из таблицы видно, что способы кодирования команд очень похожи. Данные о способе кодирования можно представить записью:

TInstruction=Record

AllowMixing: Boolean;

AccDispCode: Byte;

RegImmCode: Byte;

MemImmCode: Byte;

Codes: Array [0..15] Of Byte;

End;

· AllowMixing: True, если разрешается запись восьмибитного непосредственного операнда в шестнадцатибитный приемник;

Поля AccDispCode, RegImmCode и MemImmCode имеют смысл если AllowMixing=TRUE

· AccDispCode — байт для адресации Аккумулятор-Память и наоборот (06 для XOR)

· RegImmCode — байт для адресации Регистр-Непосредственный операнд (F0 для XOR)

· MemImmCode — байт для адресации Память-Непосредственный операнд (36 для XOR)

Таким образом команды MOV и XOR будут иметь следующий вид:

Const

MOV: TInstruction = (AllowMixing:False; AccDispCode:0;RegImmCode:0;

MemImmCode:0; Codes: ($A0,$B0,$A1,$B8,$8A,$B0,$8B,$B8,$00,$A2,$88,

$C6,$A3,$89,$C7,$00));

XOR: TInstruction = (AllowMixing:True; AccDispCode:$06;RegImmCode:$F0;

MemImmCode:$36; Codes: ($32,$34,$33,$35,$32,$80,$33,$81,$83,$30,$30,

$80,$31,$31,$81,$83));

Таким образом, генерация кода сводится к следующему (для MOV и XOR; для остальных инструкций она производится "в лоб"; не забудь про DB и DW):

1. Определить способ адресации, используемый в команде

2. Определить индекс, соответствующий этому способу адресации (AL,[disp]=0, AL,imm8=1,…)

3. Если AllowMixing = True:

3.1. Если индекс = 0, 2, 9, 12, то:

3.1.1. Поместить код Instr.Codes [Index]

3.1.2. Поместить код Instr.AccDispCode

3.2. Если индекс = 5, 7, 8, то

3.2.1. Поместить код Instr.Codes [Index]

3.2.2. Поместить код Instr.RegImmCode

3.3. Если индекс = 11, 14, 15, то

3.3.1. Поместить код Instr.Codes [Index]

3.3.2. Поместить код Instr.MemImmCode

4. Иначе, если AllowMixing = False и индекс = 8,16, выдать сообщение об ошибке

5. Иначе, поместить байт Instr.Codes [Index]

6. Поместить остальные байты, в соответствии с операндами

7. Увеличить IP на длину команды.

8. Конец

Алгоритм не является очень подробным, но я верю, что ты додумаешь и усовершенствуешь его. Да, обрати внимание: если индекс = 5 или 7, то к Codes [Index] прибавляется номер регистра, указанного в команде.

При ассемблировании хорошо было бы формировать листинг: при записи байтов кода операции дублируй их в ListLine.Code; в ListLine.IP записывай значение IP до генерации кода, в ListLine.CmdLen — длину команды (значение, на которое увеличивается IP после генерации кода для данной инструкции). А ListLine.SourceLine вроде бы заполнялось при чтении входного файла…

На финальном полупроходе тебе придется при модификации кода в буфере модифицировать код и в листинге; чтобы облегчить жизнь, в запись TReference было добавлено поле Line — номер строки в листинге. Сообщения об ошибках тоже хорошо было бы помещать в листинг.

Ну, и после заключительного полупрохода не забудь сформировать листинг и, если не было ошибок, файл с объектным кодом. Формат файла вроде бы описан в файле "Техническое задание на проектирование отладчика.doc".

Вроде бы все. Удачи!

Предлагаю ознакомиться с аналогичными статьями: