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

В этом месте я собираюсь нарушить свое правило, что я не представлю что-либо сложное, пока это не будет абсолютно необходимо. Прошло достаточно много времени, чтобы не отметить проблему с генерируемым кодом. В настоящее время синтаксический анализатор использует D0 как «основной» регистр, и D1 для хранения частичной суммы. Эта схема работает отлично потому что мы имеем дело только с «addops» (“+” и “-”) и новое число прибавляется по мере появления. Но в общем форме это не так. Рассмотрим, например выражение

1+(2-(3+(4-5)))

Если мы поместим «1» в D1, то где мы разместим «2»? Так как выражение в общей форме может иметь любую степень сложности, то мы очень быстро используем все регистры!

К счастью есть простое решение. Как и все современные микропроцессоры, 68000 имеет стек, который является отличным местом для хранения переменного числа элементов. Поэтому вместо того, чтобы помещать термы в D0 и D1 давайте затолкнем их в стек. Для тех кто незнаком с ассемблером 68000 – помещение в стек пишется как

–(SP)

и извлечение (SP)+.

Итак, изменим EmitLn в процедуре Expression на

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

и две строки в Add и Subtract:

EmitLn('ADD (SP)+,D0') и EmitLn('SUB (SP)+,D0')

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

И снова, полученный код менее эффективен, чем был до этого, но это необходимый шаг, как вы увидите.

Теперь давайте возьмемся за действительно серьезные дела. Как вы знаете, кроме операторов «addops» существуют и другие… выражения могут также иметь операторы умножения и деления. Вы также знаете, что существует неявный приоритет операторов или иерархия, связанная с выражениями, чтобы в выражениях типа

2 + 3 * 4,

мы знали, что нужно сначала умножить, а затем сложить. (Видите, зачем нам нужен стек? )

В ранние дни технологии компиляторов, люди использовали различные довольно сложные методы для того чтобы правила приоритета операторов соблюдались. Но, оказывается, все же, что ни один из них нам не нужен… эти правила могут быть очень хорошо применены в нашей технике нисходящего синтаксического анализа. До сих пор единственной формой, которую мы применяли для терма была форма одиночной десятичной цифры. В более общей форме мы можем определить терм как произведение показателей (product of factors), то есть

::= [

Что такое показатель? На данный момент это тоже, чем был раннее терм – одиночной цифрой.

Обратите внимание: терм имеет ту же форму, что и выражение. Фактически, мы можем добавить это в наш компилятор осторожно скопировав и переименовав. Но во избежание неразберихи ниже приведен полный листинг всех подпрограмм анализатора. (Заметьте способ, которым мы изменяем порядок операндов в Divide.)

{–}

{ Parse and Translate a Math Factor }

procedure Factor;

begin

EmitLn('MOVE #' + GetNum + ',D0')

end;

{–}

{ Recognize and Translate a Multiply }

procedure Multiply;

begin

Match('*');

Factor;

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

end;

{–}

{ Recognize and Translate a Divide }

procedure Divide;

begin

Match('/');

Factor;

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

EmitLn('DIVS D1,D0');

end;

{–}

{ Parse and Translate a Math Term }

procedure Term;

begin

Factor;

while Look in ['*', '/'] do begin

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

case Look of

'*': Multiply;

'/': Divide;

else Expected('Mulop');

end;

end;

end;

{–}

{ Recognize and Translate an Add }

procedure Add;

begin

Match('+');

Term;

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

end;

{–}

{ Recognize and Translate a Subtract }

procedure Subtract;

begin

Match('-');

Term;

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

EmitLn('NEG D0');

end;

{–}

{ Parse and Translate an Expression }

procedure Expression;

begin

Term;

while Look in ['+', '-'] do begin

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

case Look of

'+': Add;

'-': Subtract;

else Expected('Addop');

end;

end;

end;

{–}

Конфетка! Почти работающий транслятор в 55 строк Паскаля! Получаемый код начинает выглядеть действительно полезным, если не обращать внимание на неэффективность. Запомните, мы не пытаемся создавать сейчас самый компактный код.

Мы можем закончить эту часть синтаксического анализатора добавив поддержку круглых скобок. Как вы знаете, скобки являются механизмом принудительного изменения приоритета операторов. Так, например, в выражении

2*(3+4) ,

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

(1+2)/((3+4)+(5-6))

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

::= ()

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

Сложно это или нет, мы должны позаботиться об этом, добавив несколько строчек в процедуру Factor:

{–}

{ Parse and Translate a Math Factor }

procedure Expression; Forward;

procedure Factor;

begin

if Look = '(' then begin

Match('(');

Expression;

Match(')');

end

else

EmitLn('MOVE #' + GetNum + ',D0');

end;

{–}

Заметьте снова, как легко мы можем дополнять синтаксический анализатор, и как хорошо код Паскаля соответствует синтаксису БНФ.

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

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

–1

Опс! Он не работает, не правда ли? Процедура Expression ожидает, что все числа будут целыми и спотыкается на знаке минус. Вы найдете, что +3 также не будет работать, так же как и что-нибудь типа:

–(3-2).

Существует пара способов для исправления этой проблемы. Самый легкий (хотя и не обязательно самый лучший) способ – вставить ноль в начало выражения, так чтобы -3 стал 0-3. Мы можем легко исправить это в существующей версии Expression:

{–}

{ Parse and Translate an Expression }

procedure Expression;

begin

if IsAddop(Look) then

EmitLn('CLR D0')

else

Term;

while IsAddop(Look) do begin

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

case Look of

'+': Add;

'-': Subtract;

else Expected('Addop');

end;

end;

end;

{–}

Я говорил вам, насколько легко мы сможем вносить изменения! На этот раз они стоили нам всего трех новых строчек Паскаля. Обратите внимание на появление ссылки на новую функцию IsAddop. Как только проверка на addop появилась дважды, я решил выделить ее в отдельную функцию. Форма функции IsAddop должна быть аналогична форме функции IsAlpha. Вот она:

{–}

{ Recognize an Addop }

function IsAddop(c: char): boolean;

begin

IsAddop := c in ['+', '-'];

end;

{–}

ОК, внесите эти изменения в программу и повторно откомпилируйте. Вы должны также включить IsAddop в базовую копию программы Cradle. Она потребуется нам позже. Сейчас попробуйте снова ввести -1. Вау! Эффективность полученного кода довольно плохая… шесть строк кода только для того, чтобы загрузить простую константу… но, по крайней мере, правильно работает. Запомните, мы не пытаемся сделать замену Turbo Pascal.