Давайте создадим компилятор! - Джек Креншоу

Однако, из-за тотального переписывания модулей синтаксического анализа я не был только способен включить многого в последнюю главу. Из-за этого наш герой, синтаксический анализатор, когда мы последний раз его видели, был только тенью себя прежнего, содержащий только код, достаточный для анализа и обработки показателя состоящего или из переменной или константы. Основным достижением этой текущей главы должно стать восстановление синтаксического анализатора в его прежней славе. В этом процессе, я надеюсь, вы будете терпеливы, если мы иногда будем рассматривать основы, с которые мы имели дело и давно уже прошли.

Сначала, давайте позаботимся о проблеме, к которой мы обращались прежде: наша текущая версия процедуры Factor, как мы оставили ее в Главе 15, не может обрабатывать отрицательные параметры. Чтобы исправить это мы представим процедуру SignedFactor:

{–}

{ Parse and Translate a Factor with Optional Sign }

procedure SignedFactor;

var Sign: char;

begin

Sign := Look;

if IsAddop(Look) then

GetChar;

Factor;

if Sign = '-' then Negate;

end;

{–}

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

{–}

{ Negate Primary }

procedure Negate;

begin

EmitLn('NEG D0');

end;

{–}

(Здесь и в других местах в этой серии я собираюсь только показывать вам новые подпрограммы. Я рассчитываю, что вы поместите их в соответствующий модуль, который вы должны без проблем определить. Не забывайте добавлять заголовок процедуры в раздел interface модуля.)

В основной программе просто измените вызов процедуры Factor на SignedFactor и протестируйте код. Разве не хорошо компоновщик Turbo и средство make поддерживают все детали?

Да, я знаю, код не очень эффективен. Если мы введем число -3 будет сгенерирован такой код:

MOVE #3,D0

NEG D0

что действительно, действительно грубо. Мы можем сделать лучше, конечно, просто предварительно добавив знак минус к строке, передаваемой в LoadConstant, но это добавляет несколько строк кода в SignedFactor и здесь я применяю философию KISS очень агрессивно. Более того, сказать правду, я думаю что подсознательно наслаждаюсь генерацией «действительно грубого» кода, так как я могу иметь удовольствие наблюдать как он будет становиться драматически лучше, когда мы примемся за методы оптимизации.

Большинство из вас никогда не слышало о Джоне Спрее, поэтому позвольте мне представить его вам здесь. Джон из Новой Зеландии и преподает информатику в одном из ее университетов. Джон написал компилятор для Motorola 6809, основанный на восхитительном, Паскаль-подобном языке собственной разработки, названном «Whimsical». Позднее он перенес компилятор на 68000 и некоторое время это был единственный компилятор, который я имел для своей доморощенной системы на 68000.

К слову сказать, один из моих стандартных тестов для любого компилятора – изучение того, как компилятор работает с пустой программой типа:

program main;

begin

end.

Мой тест измеряет время, требуемое на компиляцию и связывание и размер сгенерированного объектного файла. Бесспорный проигравший в этом тесте – компилятор DEC C для VAX, который тратит 60 секунд на компиляцию на VAX 11/780 и генерирует объектный файл 50k. Компилятор Джона бесспорно сейчас, в будущем и навсегда король по части размера кода. Для данной пустой программе Whimsical генерирует точно два байта, реализуя одну инструкцию:

RET

Устанавливая опцию компилятора генерировать include файл а не автономную программу, Джон может даже урезать этот размер с двух байт до нуля! Несколько трудно добиться нулевого обьектного файла, вы не согласны?

Само собой разумеется, что я рассматриваю Джона как эксперта в оптимизации кода и мне нравится что он однажды сказал: «Лучший способ оптимизации – не оптимизировать вообще, а изначально производить хороший код». Слова, по которым стоит жить. Когда мы начнем оптимизацию мы будем следовать уведомлению Джона и нашим первым шагом будет не добавление щелевого оптимизатора или другого постфактного устройства, но улучшение качества выдаваемого кода перед оптимизацией. Поэтому пометьте SignedFactor как первого хорошего кандидата на внимание и пока оставим его.

Термы и выражения

Я уверен вы знаете, что будет дальше. Мы должны еще раз создать остальные процедуры, которые реализуют синтаксический анализ выражений по методу рекурсивного спуска. Все мы знаем, что иерархия процедур для арифметических выражений такая:

выражение

терм

показатель

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

{–}

{ Parse and Translate an Expression }

procedure Expression;

begin

SignedFactor;

while IsAddop(Look) do

case Look of

'+': Add;

'-': Subtract;

end;

end;

{–}

Эта процедура вызывает две другие процедуры для обработки операций:

{–}

{ Parse and Translate an Addition Operation }

procedure Add;

begin

Match('+');

Push;

Factor;

PopAdd;

end;

{–}

{ Parse and Translate a Subtraction Operation }

procedure Subtract;

begin

Match('-');

Push;

Factor;

PopSub;

end;

{–}

Эти три процедуры Push, PopAdd и PopSub – новые подпрограммы генерации кода. Как подразумевает имя, процедура Push генерирует код для помещения основного регистра (D0 в нашей реализации для 68000) в стек. PopAdd и PopSub выталкивают вершину стека и прибавляют или вычитают ее из основного регистра. Код показан ниже:

{–}

{ Push Primary to Stack }

procedure Push;

begin

EmitLn('MOVE D0,-(SP)');

end;

{–}

{ Add TOS to Primary }

procedure PopAdd;

begin

EmitLn('ADD (SP)+,D0');

end;

{–}

{ Subtract TOS from Primary }

procedure PopSub;

begin

EmitLn('SUB (SP)+,D0');

Negate;

end;

{–}

Добавьте эти подпрограммы в Parser и CodeGen и измените основную программу для вызова Expression. Вуаля!

Следующий шаг, конечно, это добавление возможности работы с мульпликативными термами. С этой целью мы добавим процедуру Term и процедуры генерации кода PopMul и PopDiv. Эти процедуры генерации кода показаны ниже:

{–}

{ Multiply TOS by Primary }

procedure PopMul;

begin

EmitLn('MULS (SP)+,D0');

end;

{–}

{ Divide Primary by TOS }

procedure PopDiv;

begin

EmitLn('MOVE (SP)+,D7');

EmitLn('EXT.L D7');

EmitLn('DIVS D0,D7');

EmitLn('MOVE D7,D0');

end;

{–}

Я должен признать, что подпрограмма деления немного перегружена, но с этим ничего нельзя поделать. К сожалению, хотя процессор 68000 позволяет выполнять деление используя вершину стека (TOS), он требует аргументы в неправильном порядке, подобно тому как для вычитания. Поэтому наше единственное спасение в том чтобы вытолкнуть стек в рабочий регистр (D7), выполнить там деление, и затем поместить результат обратно в наш основной регистр D0. Обратите внимание на использование знаковых операций умножения и деления. Этим неявно подразумевается что все наши переменные будут 16-разрядными целыми числами со знаком. Это решение затронет нас позднее, когда мы начнем рассматривать множественные типы данных, преобразования типов и т.п.

Наша процедура Term это практически аналог Expression и выглядит так:

{–}

{ Parse and Translate a Term }

procedure Term;

begin

Factor;

while IsMulop(Look) do

case Look of

'*': Multiply;

'/': Divide;

end;

end;

{–}

Наш следующий шаг – изменение некоторых имен. SignedFactor теперь становится SignedTerm а вызовы Factor в Expression, Add, Subtract и SignedTerm заменяются на вызов Term:

{–}

{ Parse and Translate a Term with Optional Leading Sign }

procedure SignedTerm;

var Sign: char;

begin

Sign := Look;

if IsAddop(Look) then

GetChar;

Term;

if Sign = '-' then Negate;

end;

{–}

...

{–}

{ Parse and Translate an Expression }

procedure Expression;

begin

SignedTerm;

while IsAddop(Look) do

case Look of

'+': Add;

'-': Subtract;

end;

end;

{–}

Если память мне не изменяет мы однажды уже имели и процедуру SignedFactor и SignedTerm. У меня были причины сделать так в то время... они имели отношение к обработке булевой алгебры и, в частности, булевой функции «not». Но, конечно, для арифметических операций дублирование не нужно. В выражении типа:

–x*y

очевидно, что знак идет со всем термом x*y а не просто с показателем x и таким способом Expression и закодирован.

Протестируйте этот новый код, выполнив Main. Она все еще вызывает Expression, так что теперь вы должны быть способны работать с выражениями, содержащими любую из четырех арифметических операций.

Наше последнее дело, относительно выражений, это модификация процедуры Factor для разрешения выражений в скобках. Используя рекурсивный вызов Expression мы можем уменьшить необходимый код практически до нуля. Пять строк, добавленные в Factor, выполнят эту работу:

{–}

{ Parse and Translate a Factor }

procedure Factor;

begin

if Look ='(' then begin

Match('(');

Expression;

Match(')');

end

else if IsDigit(Look) then

LoadConstant(GetNumber)

else if IsAlpha(Look)then

LoadVariable(GetName)

else

Error('Unrecognized character ' + Look);

end;

{–}

К этому моменту ваш «компилятор» должен уметь обрабатывать любые допустимые выражения, которые вы ему подбросите. Еще лучше, что он должен отклонить все недопустимые!

Присваивания

Пока мы здесь, мы могли бы также написать код для работы с операциями присваивания. Этот код должен только запомнить имя конечной переменной, где мы должны сохранить результат выражения, вызвать Expression, затем сохранить число. Процедура показана дальше: