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

      Много лет назад существовали языки, называемые Tiny BASIC, Tiny Pascal и Tiny C, каждый из которых был подмножеством своего полного родительского языка. Tiny BASIC, к примеру, имел только односимвольные имена переменных и глобальные переменные. Он поддерживал только один тип данных. Звучит знакомо? К этому моменту мы имеем почти все инструменты, необходимые для создания компилятора подобного этому.
      Однако язык, называемый Tiny-такой-то все же несет некоторый багаж, унаследованный от своего родительского языка. Я часто задавался вопросом, хорошая ли это идея. Согласен, язык, основанный на каком-то родительском языке, будет иметь преимущество знакомости, но может также существовать некоторый особенный синтаксис, перенесенный из родительского языка, который может приводить к появлению ненужной сложности в компиляторе. (Нигде это не является большей истиной, чем в Small C).
      Я задавался вопросом, насколько маленьким и простым может быть создан компилятор и при этом все еще быть полезным, если он разрабатывался из условия быть легким и для использования и для синтаксического анализа. Давайте выясним. Этот язык будет называться просто «TINY». Он является подмножеством KISS, который я также еще полностью не определил, что по крайней мере делает нас последовательными (!). Я полагаю вы могли бы назвать его TINY KISS. Но это открывает целую кучу проблем, так что давайте просто придерживаться имени TINY.
      Главные ограничения TINY будут возникать из-за тех вещей, которые мы еще не рассмотрели, таких как типы данных. Подобно своим кузенам Tiny C и Tiny BASIC, TINY будет иметь только один тип данных, 16-разрядное целое число. Первая версия, которую мы разработаем, не будет также иметь вызовов процедур и будет использовать односимвольные имена переменных, хотя, как вы увидите, мы можем удалить эти ограничения без особых усилий.
      Язык, который я придумал, разделит некоторые хорошие особенности Pascal, C и Ada. Получив урок из сравнения компиляторов Pascal и C в предыдущей главе, TINY все же будет иметь преимущественно вкус Паскаля. Везде, где возможно, структура языка будет ограничена ключевыми словами или символами, так что синтаксический анализатор будет знать, что происходит без догадок.
      Другое основное правило: Я хотел бы чтобы в течение всей разработки компилятор производил настоящий выполнимый код. Даже если его не может быть слишком много в самом начале, но по крайней мере он должен быть корректным.
      Наконец, я буду использовать пару ограничений Pascal, которые имеют смысл: Все данные и процедуры должны быть объявлены перед тем, как они используются. Это имеет большой смысл, даже если сейчас единственным типом данных, который мы будем использовать, будет слово. Это правило, в свою очередь, означает, что единственное приемлемое место для размещения выполнимого кода основной программы – в конце листинга.
      Определение верхнего уровня будет аналогично Pascal:
      <program> ::= PROGRAM <top-level decl> <main> '.'
      Мы уже достигли решающей точки. Моей первой мыслью было сделать основной блок необязательным. Кажется бессмысленным писать «программу» без основной программы, но это имеет смысл, если мы разрешим множественные модули, связанные вместе. Фактически я предполагаю учесть это в KISS. Но тогда мы столкнемся с кучей проблем, которые я предпочел бы сейчас не затрагивать. Например, термин «PROGRAM» в действительности становится неправильно употребляемым. MODULE из Modula-2 или UNIT из Turbo Pascal были бы более подходящими. Во-вторых, как насчет правил видимости? Нам необходимо соглашение для работы с видимостью имен в модулях. На данный момент лучше просто сохранить простоту и совершенно игнорировать эту идею.
      Также необходимо определиться с требованием, чтобы основная программа была последней. Я играл с идеей сделать ее размещение нефиксированным как в C. Характер SK*DOS, ОС под которую я компилирую, позволяет сделать это очень просто. Но это в действительности не имеет большого смысла принимая во внимание Pascal-подобное требование, что все данные и процедуры должны быть обьявлены прежде чем они используются. Так как основная программа может вызывать только те процедуры, которые уже были объявлены, единственное местоположение, имеющее смысл – в конце, a la Pascal.
      По данной выше БНФ давайте напишем синтаксический анализатор, который просто распознает скобки:

      {–}
      { Parse and Translate a Program }
      procedure Prog;
      begin
      Match('p');
      Header;
      Prolog;
      Match('.');
      Epilog;
      end;
      {–}

      Процедура Header просто выдает инициализационный код, необходимый ассемблеру:

      {–}
      { Write Header Info }
      procedure Header;
      begin
      WriteLn('WARMST', TAB, 'EQU $A01E');
      end;
      {–}

      Процедуры Prolog и Epilog выдают код для идентификации основной программы и для возвращения в ОС:

      {–}
      { Write the Prolog }
      procedure Prolog;
      begin
      PostLabel('MAIN');
      end;
      {–}
      { Write the Epilog }
      procedure Epilog;
      begin
      EmitLn('DC WARMST');
      EmitLn('END MAIN');
      end;
      {–}

      Основная программа просто вызывает Prog и затем выполняет проверку на чистое завершение:

      {–}
      { Main Program }
      begin
      Init;
      Prog;
      if Look <> CR then Abort('Unexpected data after ''.''');
      end.
      {–}

      Сейчас TINY примет только одну «программу» – пустую:
      PROGRAM . (или 'p.' в нашей стенографии).
      Заметьте, тем не менее, что компилятор генерирует для этой программы корректный код. Она будет выполняться и делать то, что можно ожидать от пустой программы, т.е. ничего кроме элегантного возвращения в ОС.
      Один из моих любимых бенчмарков для компиляторов заключается в компиляции, связывании и выполнении пустой программы для любого языка. Вы можете многое узнать о реализации измеряя предел времени, необходимый для компиляции тривиальной программы. Также интересно измерить количество полученного кода. Во многих компиляторах код может быть довольно большим, потому что они всегда включают целую run-time библиотеку независимо от того, нуждаются они в ней или нет. Ранние версии Turbo Pascal в этом случае производили объектный файл 12К. VAX C генерирует 50К!
      Самые маленькие пустые программы какие я видел, получены компиляторами Модула-2 и они занимают примерно 200-800 байт.
      В случае TINY у нас еще нет run-time библиотеки, так что объектный код действительно крошечный (tiny): два байта. Это стало рекордом, и вероятно останется таковым, так как это минимальный размер, требуемый ОС.
      Следующим шагом будет обработка кода для основной программы. Я буду использовать блок BEGIN из Pascal:
      <main> ::= BEGIN <block> END
      Здесь мы снова приняли решение. Мы могли бы потребовать использовать объявление вида «PROCEDURE MAIN», подобно C. Я должен допустить, что это совсем неплохая идея... Мне не особенно нравится подход Паскаля так как я предпочитаю не иметь проблем с определением местоположения основной программы в листинге Паскаля. Но альтернатива тоже немного неудобна, так как вы должны работать с проверкой ошибок когда пользователь опустит основную программу или сделает орфографическую ошибку в ее названии. Здесь я использую простой выход.
      Другое решение проблемы «где расположена основная программа» может заключаться в требовании имени для программы и заключения основной программы в скобки:
      BEGIN <name>
      END <name>
      аналогично соглашению Модула-2. Это добавляет в язык немного «синтаксического сахара». Подобные вещи легко добавлять и изменять по вашим симпатиям если вы сами проектируете язык.
      Для синтаксического анализа такого определения основного блока измените процедуру Prog следующим образом:

      {–}
      { Parse and Translate a Program }
      procedure Prog;
      begin
      Match('p');
      Header;
      Main;
      Match('.');
      end;
      {–}

      и добавьте новую процедуру:

      {–}
      { Parse and Translate a Main Program }
      procedure Main;
      begin
      Match('b');
      Prolog;
      Match('e');
      Epilog;
      end;
      {–}

      Теперь единственной допустимой программой является программа:
      PROGRAM BEGIN END. (или 'pbe.')
      Разве мы не делаем успехи??? Хорошо, как обычно это становится лучше. Вы могли бы попробовать сделать здесь некоторые преднамеренные ошибки подобные пропуску 'b' или 'e' и посмотреть что случится. Как всегда компилятор должен отметить все недопустимые входные символы.

      Очевидно на следующем шаге необходимо решить, что мы подразумеваем под объявлением. Я намереваюсь иметь два вида объявлений: переменных и процедур/функций. На верхнем уровне разрешены только глобальные объявления, точно как в C.
      Сейчас здесь могут быть только объявления переменных, идентифицируемые по ключевому слову VAR (сокращенно "v").
      <top-level decls> ::= ( <data declaration> )*
      <data declaration> ::= VAR <var-list>
      Обратите внимание, что так как имеется только один тип переменных, нет необходимости объявлять этот тип. Позднее, для полной версии KISS, мы сможем легко добавить описание типа.
      Процедура Prog становится:

      {–}
      { Parse and Translate a Program }
      procedure Prog;
      begin
      Match('p');
      Header;
      TopDecls;
      Main;
      Match('.');
      end;
      {–}

      Теперь добавьте две новые процедуры:

      {–}
      { Process a Data Declaration }
      procedure Decl;
      begin
      Match('v');
      GetChar;
      end;
      {–}
      { Parse and Translate Global Declarations }
      procedure TopDecls;
      begin
      while Look <> 'b' do
      case Look of
      'v': Decl;
      else Abort('Unrecognized Keyword ''' + Look + '''');
      end;
      end;
      {–}

      Заметьте, что на данный момент Decl – просто заглушка. Она не генерирует никакого кода и не обрабатывает список... каждая переменная должна быть в отдельном утверждении VAR.
      ОК, теперь у нас может быть любое число объявлений данных, каждое начинается с "v" вместо VAR, перед блоком BEGIN. Попробуйте несколько вариантов и посмотрите, что происходит.

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

      {–}
      { Parse and Translate a Data Declaration }
      procedure Decl;
      var Name: char;
      begin
      Match('v');
      Alloc(GetName);
      end;
      {–}

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

      {–}
      { Allocate Storage for a Variable }
      procedure Alloc(N: char);
      begin
      WriteLn(N, ':', TAB, 'DC 0');
      end;
      {–}

      Погоняйте программу. Попробуйте входную последовательность, которая объявляет какие-нибудь переменные, например:
      pvxvyvzbe.
      Видите, как распределяется память? Просто, да? Заметьте также, что точка входа «MAIN» появляется в правильном месте.
      Кстати, «настоящий» компилятор имел бы также таблицу идентификаторов для записи используемых переменных. Обычно, таблица идентификаторов необходима для записи типа каждой переменной. Но так как в нашем случае все переменные имеют один и тот же тип, нам не нужна таблица идентификаторов. Оказывается, мы смогли бы находить идентификатор даже без различия типов, но давайте отложим это пока не возникнет такая необходимость.
      Конечно, в действительности мы не анализировали правильный синтаксис для объявления данных, так как он включает список переменных. Наша версия разрешает только одну переменную. Это также легко исправить.
      БНФ для <var-list> следующая:
      <var-list> ::= <ident> (, <ident>)*
      Добавление этого синтаксиса в Decl дает новую версию:

      {–}
      { Parse and Translate a Data Declaration }
      procedure Decl;
      var Name: char;
      begin
      Match('v');
      Alloc(GetName);
      while Look = ',' do begin
      GetChar;
      Alloc(GetName);
      end;
      end;
      {–}

      ОК, теперь откомпилируйте этот код и испытайте его. Попробуйте ряд строк с объявлениями VAR, попробуйте список из нескольких переменных в одной строке и комбинации этих двух. Работает?

      Пока мы работали с объявлениями данных, меня беспокоила одна вещь – то, что Pascal не позволяет инициализировать данные в объявлении. Эта возможность по общему признанию является своего рода излишеством, и ее может не быть в языке, который считается минимальным языком. Но ее также настолько просто добавить, что было бы позором не сделать этого. БНФ становится:
      <var-list> ::= <var> ( <var> )*
      <var> ::= <ident> [ = <integer> ]
      Измените Alloc как показано ниже:

      {–}
      { Allocate Storage for a Variable }
      procedure Alloc(N: char);
      begin
      Write(N, ':', TAB, 'DC ');
      if Look = '=' then begin
      Match('=');
      WriteLn(GetNum);
      end
      else
      WriteLn('0');
      end;
      {–}

      Вот оно: инициализатор в шесть дополнительных строк Pascal.
      Испытайте эту версию TINY и проверьте, что вы действительно можете задавать начальное значение перменных.
      Ей богу, он начинает походить на настоящий компилятор! Конечно, он все еще ничего не делает, но выглядит хорошо, не так ли?
      Перед тем как оставить этот раздел я должен подчеркнуть, что мы использовали две версии GetNum. Одна, более ранняя, возвращала символьное значение, одиночную цифру. Другая принимала многозначное целое число и возвращала целочисленное значение. Любая из них будет работать здесь, так как WriteLn поддерживает оба типа. Но нет никакой причины ограничивать себя одноразрядными значениями, так что правильной версией для использования будет та, которая возвращает целое число. Вот она:

      {–}
      { Get a Number }
      function GetNum: integer;
      var Val: integer;
      begin
      Val := 0;
      if not IsDigit(Look) then Expected('Integer');
      while IsDigit(Look) do begin
      Val := 10 * Val + Ord(Look) – Ord('0');
      GetChar;
      end;
      GetNum := Val;
      end;
      {–}

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

      {–}
      { Allocate Storage for a Variable }
      procedure Alloc(N: char);
      begin
      if InTable(N) then Abort('Duplicate Variable Name ' + N);
      ST[N] := 'v';
      Write(N, ':', TAB, 'DC ');
      if Look = '=' then begin
      Match('=');
      If Look = '-' then begin
      Write(Look);
      Match('-');
      end;
      WriteLn(GetNum);
      end
      else
      WriteLn('0');
      end;
      {–}

      Теперь у вас есть возможность инициализировать переменные отрицательными и/или многозначными значениями.

      Существует одна проблема с компилятором в его текущем состоянии: он ничего не делает для сохранения переменной когда мы ее объявляем. Так что компилятор совершенно спокойно распределит память для нескольких переменных с тем же самым именем. Вы можете легко убедиться в этом набрав строку типа
      pvavavabe.
      Здесь мы объявили переменную A три раза. Как вы можете видеть, компилятор бодро принимает это и генерирует три идентичных метки. Не хорошо.
      Позднее, когда мы начнем ссылаться на переменные, компилятор также будет позволять нам ссылаться на переменные, которые не существуют. Ассемблер отловит обе эти ошибки, но это совсем не кажется дружественным поведением – передавать такую ошибку ассемблеру. Компилятор должен отлавливать такие вещи на уровне исходного языка.
      Так что даже притом, что нам не нужна таблица идентификаторов для записи типов данных, мы должны установить ее только для того, чтобы проверять эти два условия. Так как пока мы все еще ограничены односимвольными именами переменных таблица идентификаторов может быть тривиальной. Чтобы предусмотреть ее сначала добавьте следующее объявление в начало вашей программы:
      var ST: array['A'..'Z'] of char;
      и вставьте следующую функцию: