Креншоу Д. Пишем компилятор

Подождите немного. Документ загружается.

241

AddEntry(N, T);

AllocVar(N, T);

end;

{ Parse and Translate a Data Declaration }

procedure Decl;

var Typ: char;

begin

Typ := GetName;

Alloc(GetName, Typ);

end;

{ Parse and Translate Global Declarations }

procedure TopDecls;

begin

while Look <> '.' do begin

case Look of

'b', 'w', 'l': Decl;

else Abort('Unrecognized Keyword ' + Look);

end;

Fin;

end;

Внесите показанные изменения в эти процедуры и испытайте программу. Используйте

одиночные символы "b", "w" и "l" как ключевые слова (сейчас они должны быть в нижнем

регистре). Вы увидите, что в каждом случае мы выделяем память соответствующего

объема. Обратите внимание, глядя на дамп таблицы идентификаторов, что размеры

также сохранены для использования позже. Какого использования? Хорошо, это тема

остальной части этой главы.

ПРИСВАИВАНИЯ

Теперь, когда мы можем объявлять переменные различных размеров, очевидно что мы

должны иметь возможность что-то с ними делать. На первый раз, давайте просто

попробуем загружать их в наш рабочий регистр D0. Имеет смысл использовать ту же

самую идею, которую мы использовали для Alloc, т.е. сделаем процедуру загрузки,

которая может загружать переменные нескольких размеров. Нам также необходимо

продолжать изолировать машино-зависимое содержимое. Процедура загрузки выглядит

так:

{ Load a Variable to Primary Register }

procedure LoadVar(Name, Typ: char);

begin

Move(Typ, Name + '(PC)', 'D0');

end;

По крайней мере для 68000, многие команды оказываются командами MOVE. Было бы

полезно создать отдельный генератор кода только для этих инструкций и затем вызывать

его когда необходимо:

{ Generate a Move Instruction }

procedure Move(Size: char; Source, Dest: String);

begin

EmitLn('MOVE.' + Size + ' ' + Source + ',' + Dest);

end;

242

Обратите внимание, что эти две подпрограммы - строго генераторы кода; они не имеют

проверки ошибок и другой логики. Чтобы завершить картинку, нам необходим еще один

программный уровень, который предоставляет эти функции.

Прежде всего, мы должны удостовериться, что типы, с которыми мы работаем -

загружаемого типа. Это звучит как работа для другого распознавателя:

{ Recognize a Legal Variable Type }

function IsVarType(c: char): boolean;

begin

IsVarType := c in ['B', 'W', 'L'];

end;

Затем, было бы хорошо иметь подпрограмму, которая извлечет тип переменной из

таблицы идентификаторов в то же время проверяя его на допустимость:

{ Get a Variable Type from the Symbol Table }

function VarType(Name: char): char;

var Typ: char;

begin

Typ := TypeOf(Name);

if not IsVarType(Typ) then Abort('Identifier ' + Name +

' is not a variable');

VarType := Typ;

end;

Вооруженная этими инструментами, процедура, выполняющая загрузку переменной,

становится тривиальной:

{ Load a Variable to the Primary Register }

procedure Load(Name: char);

begin

LoadVar(Name, VarType(Name));

end;

(Примечание для обеспокоившихся: я знаю, знаю, все это очень неэффективно. В

промышленной программы мы, возможно, предприняли бы шаги чтобы избежать такого

глубокого вложения вызовов процедур. Не волнуйтесь об этом. Это упражнение,

помните? Более важно сделать его правильно и понять его, чем получить неправильный

ответ но быстро. Если вы закончите свой компилятор и обнаружите, что вы несчастны от

его быстродействия, вы вольны вернуться и доработать код для более быстрой работы).

Было бы хорошей идеей протестировать программу сейчас. Так как мы пока не имеем

процедуры для работы с операциями присваивания, я просто добавил строки:

Load('A');

Load('B');

Load('C');

Load('X');

в основную программу. Таким образом, после того, как раздел объявления завершен, они

будут выполнены чтобы генерировать код для загрузки. Вы можете поиграть с

различными комбинациями объявлений чтобы посмотреть как обрабатываются ошибки.

Я уверен, что вы не будете удивлены, узнав, что сохранение переменных во многом

подобно их загрузке. Необходимые процедуры показаны дальше:

243

{ Store Primary to Variable }

procedure StoreVar(Name, Typ: char);

begin

EmitLn('LEA ' + Name + '(PC),A0');

Move(Typ, 'D0', '(A0)');

end;

{ Store a Variable from the Primary Register }

procedure Store(Name: char);

begin

StoreVar(Name, VarType(Name));

end;

Вы можете проверить их таким же образом, что и загрузку.

Теперь, конечно, достаточно легко использовать их для обработки операций

присваивания. Что мы сделаем - создадим специальную версию процедуры Block,

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

Expression, которая поддерживает в качестве допустимых выражений только одиночные

переменные. Вот они:

{ Parse and Translate an Expression }

procedure Expression;

var Name: char;

begin

Load(GetName);

end;

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

Name := GetName;

Match('=');

Expression;

Store(Name);

end;

{ Parse and Translate a Block of Statements }

procedure Block;

begin

while Look <> '.' do begin

Assignment;

Fin;

end;

(Стоит заметить, что новые процедуры, которые позволяют нам манипулировать

типами, даже проще и яснее чем те, что мы видели ранее. Это в основном блягодаря

нашим усилиям по изоляции подпрограмм генерации кода.)

Есть одна небольшая назойливая проблема. Прежде мы использовали завершающую

точку Паскаля чтобы выбраться из процедуры TopDecl. Теперь это неправильный

символ... он использован для завершения Block. В предудущих программах мы

использовали для выхода символ BEGIN (сокращенно "b"). Но он теперь используется как

символ типа.

Решение, хотя и является отчасти клуджем, достаточно простое. Для обозначения

244

BEGIN мы будем использовать 'B' в верхнем регистре. Так что измените символ в цикле

WHILE внутри TopDecl с "." на "B" и все будет прекрасно.

Теперь мы можем завершить задачу, изменив основную программу следующим

образом:

{ Main Program }

begin

Init;

TopDecls;

Match('B');

Fin;

Block;

DumpTable;

end.

(Обратите внимание, что я должен был расставить несколько обращений к Fin чтобы

избежать проблем переносов строк.)

ОК, запустите эту программу. Попробуйте ввести:

ba { byte a } *** НЕ НАБИРАЙТЕ КОММЕНТАРИИ!!! ***

wb { word b }

lc { long c }

B { begin }

a=a

a=b

a=c

b=a

b=b

b=c

c=a

c=b

c=c

Для каждого объявления вы должны получить сгенерированный код, распределяющий

память. Для каждого присваивания вы должны получить код который загружает

переменную корректного размера и сохраняет ее, также корректного размера.

Есть только одна небольшая проблема: сгенерированный код неправильный!

Взгляните на код для a=c:

MOVE.L C(PC),D0

LEA A(PC),A0

MOVE.B D0,(A0)

Этот код корректный. Он приведет к сохранению младших восьми бит C в A, что

является примлемым поведением. Это почти все, что мы можем ожидать.

Но теперь, взгляните на противоположный случай. Для c=a генерируется такой код:

MOVE.B A(PC),D0

LEA C(PC),A0

MOVE.L D0,(A0)

Это не правильно. Он приведет к сохранению байтовой переменной A в младших

восьми битах D0. Согласно правилам для процессора 68000 старшие 24 бита останутся

неизменными. Это означаем, что когда мы сохраняем все 32 бита в C, любой мусор,

который был в этих старших разрядах, также будет сохранен. Нехорошо.

То, с чем мы сейчас столкнулись назвается проблемой преобразования типов или

245

приведением.

Прежде, чем мы сделаем что-либо с переменными различных типов, даже если это

просто их копирование, мы должны быть готовы встретиться с этой проблемой. Это не

самая простая часть компилятора. Большинство ошибок, которые я видел в

промышленных компиляторах, имели отношение к ошибкам преобразования типов для

некоторой неизвестной комбинации аргументов. Как обычно, существует компромисс

между сложностью компилятора и потенциальным качеством сгенерированного кода, и,

как обычно, мы выберем путь, который сохранит компилятор простым. Я думаю вы

надете, что с таким подходом мы можем удерживать потенциальную сложность под

достаточным контролем.

ТРУСЛИВЫЙ ВЫХОД

Прежде, чем мы заберемся в детали (и потенциальную сложность) преобразования

типов, я хотел бы, чтобы вы видели, что существует один суперпростой способ решения

проблемы: просто переводить каждую переменную в длинное целое во время загрузки!

Для этого достаточно добавить всего одну строку в LoadVar, хотя, если мы не

собираемся полностью игнорировать эффективность, она должна ограничиваться

проверкой IF. Вот измененная версия:

{ Load a Variable to Primary Register }

procedure LoadVar(Name, Typ: char);

begin

if Typ <> 'L' then

EmitLn('CLR.L D0');

Move(Typ, Name + '(PC)', 'D0');

end;

(Обратите внимание, что StoreVar не нуждается в подобном изменении).

Если вы выполните некоторые тесты с этой новой версией, вы обнаружите, что теперь

все работает правильно, хотя иногда неэффективно. К примеру, рассмотрим случай a=b

(для тех же самых объявлений, что показаны выше). Теперь сгенерированный код

становится:

CLR.L D0

MOVE.W B(PC),D0

LEA A(PC),A0

MOVE.B D0,(A0)

В этом случае CLR оказывается ненужной, так как результат помещается в байтовую

переменную. Небольшая доработка помогла бы нам улучшить его. Однако, все это не так

уж плохо, и это типичного рода неэффективность, которую мы видели прежде в нехитрых

компиляторах.

Я должен подчеркнуть, что устанавливая старшие разряды в нуль, мы фактически

обрабатываем числа как целые числа без знака. Если вместо этого мы хотим

обрабатывать их как целые числа со знаком (более вероятный случай) мы должны делать

расширение знака после загрузки. Просто для того, чтобы обернуть эту часть дискуссии

милой красной ленточкой, давайте изменим LoadVar как показано ниже:

246

{ Load a Variable to Primary Register }

procedure LoadVar(Name, Typ: char);

begin

if Typ = 'B' then

EmitLn('CLR.L D0');

Move(Typ, Name + '(PC)', 'D0');

if Typ = 'W' then

EmitLn('EXT.L D0');

end;

В этой версии байт обрабатывается как беззнаковое число (как в Паскале и Си) в то

время как слово обрабатывается как знаковое.

БОЛЕЕ ПРИЕМЛЕМОЕ РЕШЕНИЕ

Как мы видели, перевод каждой переменной в длинное слово пока она находится в

памяти решает проблему, но это едва ли может быть названо эффективным и, возможно,

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

эффективность. Это означает, что все арифметические операции будут выполняться с

32-битной точностью, что удвоит время выполнения для большинства операций и

сделает его еще больше для умножения и деления. Для этих операций мы должны были

бы вызывать подпрограммы, даже если данные были бы байтом или словом. Все это

слишком походит на уловку, так как уводит нас от всех настоящих проблем.

ОК, значит это решение плохое. Есть ли еще относительно простой способ получить

преобразование данных? Можем ли мы все еще сохранять простоту?

Да, действительно. Все, что нам нужно сделать - выполнить преобразование с другого

конца... т.е. мы выполняем преобразование на выходе, когда данные сохраняются, а не

на входе.

Но запомните, часть присваивания, отвечающая за хранение, в значительной степени

независима от загрузки данных, о которой заботится процедура Expression. Вообще,

выражение может быть произвольно сложным, поэтому как может процедура Assignment

знать, какой тип данных оставлен в регистре D0?

Снова, ответ прост: Мы просто спросим об этом процедуру Expression! Ответ может

быть возвращен как значение функции.

Все это требует изменения некоторых процедур, но эти изменения, как и сам метод,

совсем простые. Прежде всего, так как мы не требуем чтобы LoadVar выполнял всю

работу по преобразованию, давайте возвратимся к простой версии:

{ Load a Variable to Primary Register }

procedure LoadVar(Name, Typ: char);

begin

Move(Typ, Name + '(PC)', 'D0');

end;

Затем, давайте добавим новую процедуру, которая будет выполнять преобразование

из одного типа в другой:

247

{ Convert a Data Item from One Type to Another }

procedure Convert(Source, Dest: char);

begin

if Source <> Dest then begin

if Source = 'B' then

EmitLn('AND.W #$FF,D0');

if Dest = 'L' then

EmitLn('EXT.L D0');

end;

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

переменной любого типа. Вот подпрограммы для этого:

{ Load a Variable to the Primary Register }

function Load(Name: char): char;

var Typ : char;

begin

Typ := VarType(Name);

LoadVar(Name, Typ);

Load := Typ;

end;

{ Store a Variable from the Primary Register }

procedure Store(Name, T1: char);

var T2: char;

begin

T2 := VarType(Name);

Convert(T1, T2);

StoreVar(Name, T2);

end;

Обратите внимание, что Load является функцией, которая не только выдает код для

загрузки, но также возвращает тип переменной. Таким образом, мы всегда знаем, с каким

типом данных мы работаем. Когда мы выполняем Store, мы передаем ей текущий тип

переменной в D0. Так как Store также знает тип переменной назначения, она может

выполнить преобразование необходимым образом.

Вооруженная всеми этими новыми подпрограммами, реализация нашего

элементарного присваивания по существу тривиальна. Процедура Expression теперь

становится функцией возвращающей тип выражения в процедуру Assignment:

{ Parse and Translate an Expression }

function Expression: char;

begin

Expression := Load(GetName);

end;

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

Name := GetName;

Match('=');

Store(Name, Expression);

end;

Снова, заметьте как невероятно просты эти две подпрограммы. Мы изолировали всю

логику типа в Load и Store и хитрость с передачей типа делает остальную работу

248

чрезвычайно простой. Конечно, все это для нашего специального, тривиального случая с

Expression. Естественно, для общего случая это будет более сложно. Но теперь вы

смотрите на финальную версию процедуры Assignment!

Все это выглядит как очень простое и ясное решение, и действительно это так.

Откомпилируйте эту программу и выполните те же самые тесты, что и ранее. Вы увидите,

что все типы данных преобразованы правильно и здесь немного, если вообще есть, зря

потраченных инструкций. Только преобразование "байт-длинное слово" использует две

инструкции когда можно было бы использовать одну, и мы могли бы легко изменить

Convert для обработки этого случая.

Хотя мы в этом случае не рассматривали переменные без знака, я думаю вы можете

видеть, что мы могли бы легко исправить процедуру Convert для работы и с этими

типами. Это "оставлено как упражнение для студента".

ЛИТЕРАЛЬНЫЕ АРГУМЕНТЫ

Зоркие читатели могли бы отметить, однако, что мы еще даже не имеем правильной

формы простого показателя, потому что мы не разрешаем загрузку литеральных

констант, только переменных. Давайте исправим это сейчас.

Для начала нам понадобится функция GetNum. Мы уже видели ее несколько версий,

некоторые возвращают только одиночный символ, некоторые строку, а некоторые целое

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

обрабатывать все, что мы ей подбросим. Обратите внимание, что здесь не возвращается

никакой информации о типах: GetNum не интересуется тем, как будет использоваться

число:

{ Get a Number }

function GetNum: LongInt;

var Val: LongInt;

begin

if not IsDigit(Look) then Expected('Integer');

Val := 0;

while IsDigit(Look) do begin

Val := 10 * Val + Ord(Look) - Ord('0');

GetChar;

end;

GetNum := Val;

SkipWhite;

end;

Теперь, когда работаем с литералами, мы имеем одну небольшую проблему. С

переменными мы знаем какого типа они должны быть потому что они были объявлены с

таким типом. Мы не имеем такой информации о типе для литералов. Когда программист

говорит "-1", означает ли это байт, слово или длинное слово? Мы не имеем никаких

сведений. Очевидным способом было бы использование наибольшего возможного типа,

т.е. длинного слова. Но это плохая идея, потому что когда мы примемся за более

сложные выражения, мы обнаружим, что это заставит каждое выражение включающее

литералы, также переводить в длинное.

Лучшим подходом было бы выбрать тип, основанный на значении литерала, как

показано далее:

249

{ Load a Constant to the Primary Register }

function LoadNum(N: LongInt): char;

var Typ : char;

begin

if abs(N) <= 127 then

Typ := 'B'

else if abs(N) <= 32767 then

Typ := 'W'

else Typ := 'L';

LoadConst(N, Typ);

LoadNum := Typ;

end;

(Я знаю, знаю, база числа не является в действительности симметричной. Вы можете

хранить -128 в одиночном байте и -32768 в слове. Но это легко исправить и не стоит

затраченного времени или дополнительной сложности возиться с этим сейчас. Стоящая

мысль.)

Заметьте, что LoadNum вызывает новую версию подпрограммы генерации кода

LoadConst, которая имеет дополнительный параметр для определения типа:

{ Load a Constant to the Primary Register }

procedure LoadConst(N: LongInt; Typ: char);

var temp:string;

begin

Str(N, temp);

Move(Typ, '#' + temp, 'D0');

end;

Теперь мы можем изменить процедуру Expression для использования двух возможных

видов показателей:

{ Parse and Translate an Expression }

function Expression: char;

begin

if IsAlpha(Look) then

Expression := Load(GetName)

else

Expression := LoadNum(GetNum);

end;

(Вау, это, уверен, не причинило слишком большого вреда! Всего несколько

дополнительных строк делают всю работу.)

ОК, соберите этот код в вашу программу и испытайте ее. Вы увидите, что она теперь

работает и для переменных и для констант как допустимых выражений.

АДДИТИВНЫЕ ВЫРАЖЕНИЯ

Если вы следовали за этой серией с самого начала, я уверен вы знаете, что будет

дальше. Мы расширим форму выражения для поддержки сначала аддитивных

выражений, затем мультипликативных, а затем общих выражений со скобками.

Хорошо, что мы уже имеем модель для работы с этими более сложными выражениями.

Все, что мы должны сделать, это удостовериться, что все процедуры, вызываемые

Expression, (Term, Factor и т.д.) всегда возвращают идентификатор типа. Если мы

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

Первый шаг прост: мы должны переименовать нашу существующую версию Expression

в Term, как мы делали много раз раньше и создать новую версию Expression:

250

{ Parse and Translate an Expression }

function Expression: char;

var Typ: char;

begin

if IsAddop(Look) then

Typ := Unop

else

Typ := Term;

while IsAddop(Look) do begin

Push(Typ);

case Look of

'+': Typ := Add(Typ);

'-': Typ := Subtract(Typ);

end;

Expression := Typ;

end;

Обратите внимание, как в этой подпрограмме каждый вызов процедуры стал вызовом

функции и как локальная переменная Typ модифицируется при каждом проходе.

Обратите внимание также на новый вызов функции Unop, которая позволяет нам

работать с ведущим унарным минусом. Это изменение не является необходимым... мы

все еще можем использовать форму более похожую на ту, что мы использовали ранее. Я

решил представить Unop как отдельную подпрограмму потому что позднее это позволит

производить несколько лучший код, чем мы делали. Другими словами, я смотрю вперед

на проблему оптимизации.

Для этой версии, тем не менее, мы сохраним тот же самый примитивный старый код,

который делает новую подпрограмму тривиальной:

{ Process a Term with Leading Unary Operator }

function Unop: char;

begin

Clear;

Unop := 'W';

end;

Процедура Push - это подпрограмма генерации кода, которая теперь имеет параметр,

указывающий тип:

{ Push Primary onto Stack }

procedure Push(Size: char);

begin

Move(Size, 'D0', '-(SP)');

end;

Теперь давайте взглянем на функции Add и Subtract. В более старых версиях этих

подпрограмм мы позволяем им вызывать подпрограммы генерации кода PopAdd и

PopSub. Мы продолжим делать это, что делает сами функции чрезвачайно простыми:

{ Recognize and Translate an Add }

function Add(T1: char): char;

begin

Match('+');

Add := PopAdd(T1, Term);

end;