НАЧАЛО

     Если вы прочитали введение, то вы уже в курсе дела. Вы также скопировали программу Cradle в Turbo Pascal и откомпилировали ее. Итак, вы готовы.
     Целью этой главы является обучение синтаксическому анализу и трансляции математических выражений. В результате мы хотели бы видеть серию команд на ассемблере, выполняющую необходимые действия. Выражение √ правая сторона уравнения, например:

     x = 2*y + 3/(4*z)

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

     ОДИНОЧНЫЕ ЦИФРЫ

     В соответствии с общей темой этой серии (KISS-принцип, помнишь?), начнем с самого простого случая, который можно себе представить. Это выражение, состоящее из одной цифры.
     Перед тем как начать, удостоверьтесь, что у вас есть базовая копия Cradle. Мы будем использовать ее для других экспериментов. Затем добавьте следующие строки:

{---------------------------------------------------------------}
{ Parse and Translate a Math Expression }

procedure Expression;
begin
   EmitLn('MOVE #' + GetNum + ',D0')
end;
{---------------------------------------------------------------}

И добавьте строку ⌠Expression;■ в основную программу, которая должна выглядеть так:

{---------------------------------------------------------------}
begin
   Init;
   Expression;
end.
{---------------------------------------------------------------}

     Теперь запустите программу. Попробуйте ввести любую одиночную цифру. Вы получите  результат в виде одной строчки на ассемблере. Затем попробуйте ввести любой другой символ и вы увидите, что синтаксический анализатор правильно сообщает об ошибке.
     Поздравляю! Вы только что написали работающий транслятор!
     Конечно, я понимаю, что он очень ограничен. Но не отмахивайтесь от него. Этот маленький ╚компилятор╩ в ограниченных масштабах делает точно то же, что делает любой большой компилятор: он корректно распознает допустимые утверждения на входном ╚языке╩, который мы для него определили, и производит корректный, выполнимый ассемблерный код, пригодный для перевода в объектный формат. И, что важно, корректно распознает недопустимые утверждения, выдавая сообщение об ошибке. Кому требовалось больше?
     Имеются некоторые другие особенности этой маленькой программы, заслуживающие внимания. Во первых, вы видите, что мы не отделяем генерацию кода от синтаксического анализа┘ как только анализатор узнает что нам нужно, он непосредственно генерирует объектный код. В настоящих компиляторах, конечно, чтение в GetChar должно происходить из файла и затем выполняться запись в другой файл, но этот способ намного проще пока мы экспериментируем.
     Также обратите внимание, что выражение должно где-то сохранить результат. Я выбрал регистр D0 процессора 68000. Я мог бы выбрать другой регистр, но в данном случае это имеет смысл.

     ВЫРАЖЕНИЯ С ДВУМЯ ЦИФРАМИ

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

     1+2
     или 4-3
     или в общем  <term> +/- <term>  (это часть формы Бэкуса-Наура или БНФ.)

     Для того, чтобы сделать это, нам нужна процедура, распознающая термы и сохраняющая результат, и другая процедура, которая распознает и различает ╚+╩ и ╚-╩  и генерирует соответствующий код. Но если процедура Expression  сохраняет свои результаты в регистре D0, то где процедура Term сохранит свои результаты? Ответ:  на том же месте. Мы окажемся перед необходимостью сохранять первый результат процедуры Term где-нибудь, прежде чем мы получим следующий.
     В основном, что нам необходимо сделать √ создать процедуру Term, выполняющую то что раннее выполняла процедура Expression. Поэтому просто переименуйте процедуру Expression в Term и наберите новую версию Expression:

{---------------------------------------------------------------}
{ Parse and Translate an Expression }

procedure Expression;
begin
   Term;
   EmitLn('MOVE D0,D1');
   case Look of
    '+': Add;
    '-': Subtract;
   else Expected('Addop');
   end;
end;
{--------------------------------------------------------------}

Затем выше Expression наберите следующие две процедуры:

{--------------------------------------------------------------}
{ Recognize and Translate an Add }

procedure Add;
begin
   Match('+');
   Term;
   EmitLn('ADD D1,D0');
end;

{-------------------------------------------------------------}
{ Recognize and Translate a Subtract }

procedure Subtract;
begin
   Match('-');
   Term;
   EmitLn('SUB D1,D0');
end;
{-------------------------------------------------------------}

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

• Term (старая версия Expression)
• Add
• Subtract
• Expression

     MOVE #n,D0
     MOVE D0,D1

неэффективна. Если бы мы писали этот код вручную, то, возможно, просто загрузили бы данные напрямую в D1.
     Вывод: код, генерируемый нашим синтаксическим анализатором, менее эффективный, чем код, написанный вручную. Привыкните к этому. Это в известной мере относится ко всем компиляторам. Ученые посвятили целые жизни вопросу оптимизации кода и существуют методы, призванные улучшить качество генерируемого кода. Некоторые компиляторы выполняют оптимизацию достаточно хорошо, но за это приходится платить сложностью и в любом случае это проигранная битва┘ возможно никогда не придет время, когда хороший программист на ассемблере не смог бы превзойти компилятор. Прежде чем закончится этот урок, я кратко упомяну некоторые способы, которые мы можем применить для небольшой оптимизации, просто, чтобы показать вам, что мы на самом деле сможем сделать некоторые улучшения без излишних проблем. Но запомните, мы здесь для того, чтобы учиться, а не для того, чтобы узнать насколько компактным мы можем сделать код. А сейчас и на протяжении всей этой серии мы старательно будем игнорировать оптимизацию и сконцентрируемся на получении работающего кода.
     Но наш код не работает! В коде есть ошибка! Команда вычитания вычитает D1 (первый аргумент) из D0 (второй аргумент). Но это неправильный способ, так как мы получаем неправильный знак результата. Поэтому исправим процедуру Subtract с помощью замены знака следующим образом:

{-------------------------------------------------------------}
{ Recognize and Translate a Subtract }

procedure Subtract;
begin
   Match('-');
   Term;
   EmitLn('SUB D1,D0');
   EmitLn('NEG D0');
end;
{-------------------------------------------------------------}

     Теперь наш код даже еще менее эффективен, но по крайней мере выдает правильный ответ! К сожалению, правила, которые определяют значение математических выражений, требуют, чтобы условия в выражении следовали в неудобном для нас порядке. Опять, это только один из фактов жизни, с которыми вы учитесь жить. Все это возвратится снова, чтобы преследовать нас, когда мы примемся за деление.
     Итак, на данном этапе мы имеем синтаксический анализатор, который может распознавать сумму или разность двух цифр. Ранее мы могли распознавать только одиночные цифры. Но настоящие выражения могут иметь любую форму (или бесконечность других). Вернитесь и запустите программу с единственным входным символом  ⌠1■.
     Не работает? А почему должен работать? Мы только указали анализатору, что единственным правильными видами выражений являются выражения с двумя термами. Мы должны переписать процедуру Expression так, чтобы она была намного более универсальной и с этого начать создание настоящего синтаксического анализатора.

     ОБЩАЯ ФОРМА ВЫРАЖЕНИЯ

     В реальном мире выражение может состоять из одного или более термов, разделенных "addops" ('+'  или  '-'). В БНФ это может быть записано как:

     <expression> ::= <term> [<addop> <term>]*

Мы можем применить это определение выражения, добавив простой цикл к процедуре Expression:

{---------------------------------------------------------------}
{ Parse and Translate an Expression }

procedure Expression;
begin
   Term;
   while Look in ['+', '-'] do begin
      EmitLn('MOVE D0,D1');
      case Look of
       '+': Add;
       '-': Subtract;
      else Expected('Addop');
      end;
   end;
end;
{--------------------------------------------------------------}

     Эта версия поддерживает любое число термов, и это стоило нам только двух дополнительных строк кода. По мере изучения, вы обнаружите, что это характерно для нисходящих синтаксических анализаторов┘ необходимо только несколько дополнительных строк кода чтобы добавить расширения языка. Это как раз то, что делает наш пошаговый метод возможным. Заметьте также, как хорошо код процедуры Expression соответствует определению БНФ. Это также одна из характеристик метода. Когда вы станете специалистом этого метода, вы сможете превращать БНФ в код синтаксического анализатора примерно с такой же скоростью, с какой вы можете набирать текст на клавиатуре!
     ОК, откомпилируйте новую версию анализатора и испытайте его. Как обычно, проверьте что ╚компилятор╩ обрабатывает любое допустимое выражение и выдает осмысленное сообщение об ошибке для запрещенных. Четко, да? Вы можете заметить, что в нашей тестовой версии любое сообщение об ошибке выводится вместе с генерируемым кодом. Но запомните, это только потому, что мы используем экран как ╚выходной файл╩ в этих экспериментах. В рабочей версии вывод будет разделен┘ один в выходной файл, другой на экран.

     ИСПОЛЬЗОВАНИЕ СТЕКА

     В этом месте я собираюсь нарушить свое правило, что я не представлю что-либо сложное, пока это не будет абсолютно необходимо. Прошло достаточно много времени, чтобы не отметить проблему с генерируемым кодом. В настоящее время синтаксический анализатор использует 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), то есть

     <term> ::= <factor>  [ <mulop> <factor ]*

Что такое показатель? На данный момент это тоже, чем был раннее терм - одиночной цифрой.
     Обратите внимание: терм имеет ту же форму, что и выражение. Фактически, мы можем добавить это в наш компилятор осторожно скопировав и переименовав. Но во избежание неразберихи ниже приведен полный листинг всех подпрограмм  анализатора. (Заметьте способ, которым мы изменяем порядок операндов в 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> ::= (<expression>)

     Здесь появляется рекурсия. Выражение может содержать показатель, который содержит другое выражение, которое содержит показатель и т.д. до бесконечности.
     Сложно это или нет, мы должны позаботиться об этом, добавив несколько строчек в процедуру 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;
{---