ВВЕДЕНИЕ

     В предыдущих главах мы изучили многие из методов, необходимых для создания полноценного компилятора. Мы разработали операции присваивания (с булевыми и арифметическими выражениями), операторы отношений и управляющие конструкции. Мы все еще не обращались к вопросу вызова процедур и функций, но даже без них мы могли бы в принципе создать мини-язык. Я всегда думал, что было бы забавно просто посмотреть, насколько маленьким можно было бы построить язык, чтобы он все еще оставался полезным. Теперь мы уже почти готовы сделать это. Существует проблема: хотя мы знаем, как анализировать и транслировать конструкции, мы все еще совершенно не знаем, как сложить их все вместе в язык.
     В этих ранних главах разработка наших программ имела явно восходящий характер. В случае с синтаксическим анализом выражений, например, мы начали с самых низкоуровневых конструкций, индивидуальных констант и переменных и прошли свой путь до более сложных выражений.
     Большинство людей считают, что нисходящий способ разработки лучше, чем восходящий. Я тоже так думаю, но способ, который мы использовали, казался естественно достаточным для тех вещей, которые мы анализировали.
     Тем не менее вы не должны думать, что последовательный подход, который мы применяли во всех этих главах, является принципиально восходящим. В этой главе я хотел бы показать вам, что этот подход может работать точно также, когда применяется сверху вниз... может быть даже лучше. Мы рассмотрим языки типа C и Pascal и увидим как могут быть построены законченные компиляторы начиная сверху.
     В следующей главе мы применим ту же самую методику для создания законченного транслятора подмножества языка KISS, который я буду называть TINY. Но одна из моих целей в этой серии состоит в том, чтобы вы не только могли увидеть как работает компилятор для TINY или KISS, но чтобы вы также могли разрабатывать и создавать компиляторы своих собственных языков. Примеры Си и Паскаля помогут вам в этом. Одна вещь, которую я хотел чтобы вы увидели, состоит в том, что естественная структура компилятора очень сильно зависит от транслируемого языка, поэтому простота и легкость конструирования компилятора очень сильно зависит от того, позволите ли вы языку определять структуру программы.
     Немного сложнее получить полный компилятор C или Pascal, да мы и не будем. Но мы можем расчистить верхние уровни так, чтобы вы увидели как это делается.
     Давайте начнем.

     ВЕРХНИЙ УРОВЕНЬ

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

     begin
           solve the problem
     end

     Конечно, я соглашусь с вами, что это не слишком большая подсказка о том, что расположено на следующем уровене, но я все равно запишу это просто для того, чтобы  почувствовать, что я действительно начинаю с вершины.
     В нашем случае, общая функция компилятора заключается в компиляции законченной программы. С этого начинается любое определение языка, записанное в БНФ. На что походит верхний уровень БНФ? Хорошо, это немного зависит от транслируемого языка. Давайте взглянем на Pascal.

     СТРУКТУРА ПАСКАЛЯ

     Большинство книг по Pascal включают БНФ определение языка. Вот несколько первых строк одного из них:

     <program> ::= <program-header> <block> '.'

     <program-header> ::= PROGRAM <ident>

     <block> ::= <declarations> <statements>

     Мы можем написать подпрограммы распознавания для работы с каждым из этих элементов подобно тому, как мы делали это прежде. Для каждого из них мы будем      использовать знакомые нам односимвольные токены, затем понемногу расширяя их. Давайте начнем с первого распознавателя: непосредственно программы.
     Для ее трансляции мы начнем с новой копии Cradle. Так как мы возвращаемся к односимвольным именам мы будем просто использовать "p" для обозначения "program".
     К новой копии Cradle добавьте следующий код и вставьте обращение к нему из основной программы:

{--------------------------------------------------------------}
{ Parse and Translate A Program }

procedure Prog;
var  Name: char;
begin
   Match('p');            { Handles program header part }
   Name := GetName;
   Prolog(Name);
   Match('.');
   Epilog(Name);
end;
{--------------------------------------------------------------}

     Процедуры Prolog и Epilog выполняют все, что необходимо для связи программы с операционной системой так чтобы она могла выполняться как программа. Само собой разумеется, эта часть будет очень ОС-зависима. Помните, что я выдаю код для 68000, работающий под ОС, которую я использую - SK*DOS. Я понимаю, что большинство из вас использует PC и вы предпочли бы увидеть что-нибудь другое, но я слишком далеко зашел, чтобы что-то сейчас менять!
     В любом случае, SK*DOS особенно простая для общения операционная система. Вот код для Prolog и Epilog:

{--------------------------------------------------------------}
{ Write the Prolog }

procedure Prolog;
begin
   EmitLn('WARMST EQU $A01E');
end;

{--------------------------------------------------------------}
{ Write the Epilog }

procedure Epilog(Name: char);
begin
   EmitLn('DC WARMST');
   EmitLn('END ' + Name);
end;
{--------------------------------------------------------------}

     Как обычно добавьте этот код и испытайте "компилятор". В настоящее время существует только одна допустимая входная последовательность:

     px. (где х - это любая одиночная буква, имя программы).

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

     РАСШИРЕНИЕ

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

{--------------------------------------------------------------}
{ Parse and Translate a Pascal Block }

procedure DoBlock(Name: char);
begin
end;
{--------------------------------------------------------------}

     и измените Prog следующим образом:

{--------------------------------------------------------------}
{ Parse and Translate A Program }

procedure Prog;
var  Name: char;
begin
   Match('p');
   Name := GetName;
   Prolog;
   DoBlock(Name);
   Match('.');
   Epilog(Name);
end;
{--------------------------------------------------------------}

     Это конечно не должно изменить поведения программы, и не меняет. Но сейчас определение Prog закончено и мы можем перейти к расширению DoBlock. Это получается прямо из его БНФ определения:

{--------------------------------------------------------------}
{ Parse and Translate a Pascal Block }

procedure DoBlock(Name: char);
begin
   Declarations;
   PostLabel(Name);
   Statements;
end;
{--------------------------------------------------------------}

     Процедура PostLabel была определена в главе по ветвлениям. Скопируйте ее в вашу копию Cradle.
     Я возможно должен объяснить причину вставки метки. Это имеет отношение к работе SK*DOS. В отличие от некоторых других ОС, SK*DOS позволяет точке входа в основную программу находиться в любом месте программы. Все, что вы должны сделать, это дать этой точке имя. Вызов PostLabel помещает это имя как раз перед первым выполнимым утверждением в основной программе. Как SK*DOS узнает какая из множества меток является точкой входа, спросите вы? Та, которая соответствует утверждению END в конце программы.
     Теперь нам нужны заглушки для процедур Declarations и Statements. Сделайте их пустыми процедурами как мы делали это раньше.
     Программа все еще делает то же самое? Тогда мы можем перейти к следующему этапу.

     ОБЪЯВЛЕНИЯ

     БНФ для объявлений в Pascal такая:

     <declarations> ::= ( <label list>    |
                          <constant list> |
                          <type list>     |
                          <variable list> |
                          <procedure>     |
                          <function>         )*

(Заметьте, что я использую более либеральное определение, используемое в Turbo Pascal. В определении стандартного Pascal каждая из этих частей должна следовать в определенном порядке относительно других).
     Как обычно давайте позволим одиночным символам представлять каждый из этих типов объявлений. Новая форма для Declarations:

{--------------------------------------------------------------}
{ Parse and Translate the Declaration Part }

procedure Declarations;
begin
   while Look in ['l', 'c', 't', 'v', 'p', 'f'] do
      case Look of
       'l': Labels;
       'c': Constants;
       't': Types;
       'v': Variables;
       'p': DoProcedure;
       'f': DoFunction;
      end;
end;
{--------------------------------------------------------------}

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

{--------------------------------------------------------------}
{ Process Label Statement }

procedure Labels;
begin
   Match('l');
end;

{--------------------------------------------------------------}
{ Process Const Statement }

procedure Constants;
begin
   Match('c');
end;

{--------------------------------------------------------------}
{ Process Type Statement }
procedure Types;
begin
   Match('t');
end;

{--------------------------------------------------------------}
{ Process Var Statement }

procedure Variables;
begin
   Match('v');
end;

{--------------------------------------------------------------}
{ Process Procedure Definition }

procedure DoProcedure;
begin
   Match('p');
end;

{--------------------------------------------------------------}
{ Process Function Definition }

procedure DoFunction;
begin
   Match('f');
end;
{--------------------------------------------------------------}

     Теперь испытайте компилятор используя несколько характерных входных последовательностей. Вы можете смешивать объявления любым образом, каким вам нравится пока последним символом в программе не будет ".", указывающий на конец программы. Конечно, ни одно из этих объявлений фактически ничего не объявляет, так что вам не нужны (и вы не можете использовать) любые символы, кроме тех, которые обозначают ключевые слова.
     Мы можем расширить раздел операторов аналогичным способом. БНФ для него будет:

     <statements> ::= <compound statement>

     <compound statement> ::= BEGIN <statement>(';' <statement>) END

     Заметьте, что утверждение может начинаться с любого идентификатора, исключая END.  Так что первая пустой формой процедуры Statements будет:

{--------------------------------------------------------------}
{ Parse and Translate the Statement Part }

procedure Statements;
begin
   Match('b');
   while Look <> 'e' do
      GetChar;
   Match('e');
end;
{--------------------------------------------------------------}

     Сейчас компилятор примет любое число объявлений, сопровождаемое блоком BEGIN основной программы. Сам этот блок может содержать любые символы (за исключением END), но они должны присутствовать.
     Простейшая входная форма сейчас

     'pxbe.'

     Испытайте ее. Также попробуйте некоторые ее комбинации. Сделайте некоторые преднамеренные ошибки и посмотрите что произойдет.
     К этому моменту вы должны начать видеть основную линию. Мы начинаем с пустого транслятора для обработки программы, затем в свою очередь мы расширяем каждую процедуру,  основанную на ее БНФ определении. Подобно тому, как более низкоуровневые БНФ определения добавляют детали и развивают определения более высокого уровня, более низкоуровневые распознаватели будут анализировать более детально входную программу. Когда последняя заглушка будет расширена, компилятор будет закончен. Это нисходящая разработка/реализация в ее чистейшей форме.
     Вы могли бы заметить, что даже хотя мы и добавляли процедуры, выходной результат программы не изменялся. Так и должно быть. На этих верхних уровнях не требуется никакой выдачи кода. Распознаватели функционируют просто как распознаватели. Они принимают входные последовательности, отлавливают плохие и направляют хорошие в нужные места, так что они делают свою работу. Если бы мы занимались этим немног