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

и вставьте следующую функцию:

{–}

{ Look for Symbol in Table }

function InTable(n: char): Boolean;

begin

InTable := ST[n] <> ' ';

end;

{–}

Нам также необходимо инициализировать таблицу пробелами. Следующие строки в Init сделают эту работу:

var i: char;

begin

for i := 'A' to 'Z' do

ST[i] := ' ';

...

Наконец, вставьте следующие две строки в начало Alloc:

if InTable(N) then Abort('Duplicate Variable Name ' + N);

ST[N] := 'v';

Это должно все решить. Теперь компилятор будет отлавливать двойные объявления. Позднее мы также сможем использовать InTable при генерации ссылок на переменные.

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

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

БНФ определение, данное раньше для основной программы, включало операторный блок, который мы пока что игнорировали:

<main> ::= BEGIN <block> END

Сейчас мы можем рассматривать блок просто как серию операций присваивания:

<block> ::= (Assignment)*

Давайте начнем с добавления синтаксического анализатора для блока. Мы начнем с процедуры-заглушки для операции присваивания:

{–}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

begin

GetChar;

end;

{–}

{ Parse and Translate a Block of Statements }

procedure Block;

begin

while Look <> 'e' do

Assignment;

end;

{–}

Измените процедуру Main чтобы она вызывала Block как показано ниже:

{–}

{ Parse and Translate a Main Program }

procedure Main;

begin

Match('b');

Prolog;

Block;

Match('e');

Epilog;

end;

{–}

Эта версия все еще не генерирует никакого кода для «операций присваивания»... все что она делает это съедает символы до тех пор, пока не увидит "e", означающее «END». Но она устанавливает основу для того, что следует дальше.

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

Однако, я понимаю, что большинство из вас используют компьютер 80x86, так что от кода, сгенерированного для 68000 вам мало пользы. Некоторые из вас спрашивали меня, что если бы машинозависимый код мог бы быть собран в одном месте, то было бы проще перенастроить его на другой ЦПУ. Ответ конечно да.

Чтобы сделать это вставьте следующие подпрограммы «генерации кода»:

{–}

{ Clear the Primary Register }

procedure Clear;

begin

EmitLn('CLR D0');

end;

{–}

{ Negate the Primary Register }

procedure Negate;

begin

EmitLn('NEG D0');

end;

{–}

{ Load a Constant Value to Primary Register }

procedure LoadConst(n: integer);

begin

Emit('MOVE #');

WriteLn(n, ',D0');

end;

{–}

{ Load a Variable to Primary Register }

procedure LoadVar(Name: char);

begin

if not InTable(Name) then Undefined(Name);

EmitLn('MOVE ' + Name + '(PC),D0');

end;

{–}

{ Push Primary onto Stack }

procedure Push;

begin

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

end;

{–}

{ Add Top of Stack to Primary }

procedure PopAdd;

begin

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

end;

{–}

{ Subtract Primary from Top of Stack }

procedure PopSub;

begin

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

EmitLn('NEG D0');

end;

{–}

{ Multiply Top of Stack by Primary }

procedure PopMul;

begin

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

end;

{–}

{ Divide Top of Stack by Primary }

procedure PopDiv;

begin

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

EmitLn('EXT.L D7');

EmitLn('DIVS D0,D7');

EmitLn('MOVE D7,D0');

end;

{–}

{ Store Primary to Variable }

procedure Store(Name: char);

begin

if not InTable(Name) then Undefined(Name);

EmitLn('LEA ' + Name + '(PC),A0');

EmitLn('MOVE D0,(A0)')

end;

{–}

Приятная особенность такого подхода, конечно, в том что мы можем перенастроить компилятор на новый ЦПУ просто переписав эти процедуры «генератора кода». Кроме того, позднее мы обнаружим что можем улучшить качество кода немного подправляя эти процедуры без необходимости изменения компилятора.

Обратите внимание, что и LoadVar и Store проверяют таблицу идентификаторов чтобы удостовериться, что переменная определена. Обработчик ошибки Undefined просто вызывает Abort:

{–}

{ Report an Undefined Identifier }

procedure Undefined(n: string);

begin

Abort('Undefined Identifier ' + n);

end;

{–}

Итак, теперь мы наконец готовы начать обработку выполнимого кода. Мы сделаем это заменив пустую версию процедуры Assignment.

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

БНФ для операций присваивания:

<assignment> ::= <ident> = <expression>

<expression> ::= <first term> ( <addop> <term> )*

<first term> ::= <first factor> <rest>

<term> ::= <factor> <rest>

<rest> ::= ( <mulop> <factor> )*

<first factor> ::= [ <addop> ] <factor>

<factor> ::= <var> | <number> | ( <expression> )

Эта БНФ также немного отличается от той, что мы использовали раньше... еще одна «вариация на тему выражений». Эта специфичная версия имеет то, что я считаю лучшей обработкой унарного минуса. Как вы увидите позднее, это позволит нам очень эффективно обрабатывать отрицательные константы. Здесь стоит упомянуть, что мы часто видели преимущества «подстраивания» БНФ по ходу дела, с цель сделать язык легким для анализа. То, что вы видете здесь, немного другое: мы подстраиваем БНФ для того, чтобы сделать генерацию кода более эффективной! Это происходит впервые в этой серии.

Во всяком случае, следующий код реализует эту БНФ:

{–}

{ Parse and Translate a Math Factor }

procedure Expression; Forward;

procedure Factor;

begin

if Look = '(' then begin

Match('(');

Expression;

Match(')');

end

else if IsAlpha(Look) then

LoadVar(GetName)

else

LoadConst(GetNum);

end;

{–}

{ Parse and Translate a Negative Factor }

procedure NegFactor;

begin

Match('-');

if IsDigit(Look) then

LoadConst(-GetNum)

else begin

Factor;

Negate;

end;

end;

{–}

{ Parse and Translate a Leading Factor }

procedure FirstFactor;

begin

case Look of

'+': begin

Match('+');

Factor;

end;

'-': NegFactor;

else Factor;

end;

end;

{–}

{ Recognize and Translate a Multiply }

procedure Multiply;

begin

Match('*');

Factor;

PopMul;

end;

{–}

{ Recognize and Translate a Divide }

procedure Divide;

begin

Match('/');

Factor;

PopDiv;

end;

{–}

{ Common Code Used by Term and FirstTerm }

procedure Term1;

begin

while IsMulop(Look) do begin

Push;

case Look of

'*': Multiply;

'/': Divide;

end;

end;

end;

{–}

{ Parse and Translate a Math Term }

procedure Term;

begin

Factor;

Term1;

end;

{–}

{ Parse and Translate a Leading Term }

procedure FirstTerm;

begin

FirstFactor;

Term1;

end;

{–}

{ Recognize and Translate an Add }

procedure Add;

begin

Match('+');

Term;

PopAdd;

end;

{–}

{ Recognize and Translate a Subtract }

procedure Subtract;

begin

Match('-');

Term;

PopSub;

end;

{–}

{ Parse and Translate an Expression }

procedure Expression;

begin

FirstTerm;

while IsAddop(Look) do begin

Push;

case Look of

'+': Add;

'-': Subtract;

end;

end;

end;

{–}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

Name := GetName;

Match('=');

Expression;

Store(Name);

end;

{–}

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

Следующий шаг также должен быть вам знаком. Мы должны добавить булевы выражения и операторы отношений. Снова, так как мы работали с ними не один раз, я не буду подробно разбирать их за исключением моментов, в которых они отличаются от того, что мы делали прежде. Снова, мы не будем просто копировать их из других файлов потому что я немного изменил некоторые вещи. Большинство изменений просто включают изоляцию машинозависимых частей как мы делали для арифметических операций. Я также несколько изменил процедуру NotFactor для соответствия структуре FirstFactor. Наконец я исправил ошибку в объектном коде для операторов отношений: в инструкции Scc я использовал только младшие 8 бит D0. Нам нужно установить логическую истину для всех 16 битов поэтому я добавил инструкцию для изменения младшего байта.

Для начала нам понадобятся несколько подпрограмм распознавания:

{–}

{ Recognize a Boolean Orop }

function IsOrop(c: char): boolean;

begin

IsOrop := c in ['|', '~'];

end;

{–}

{ Recognize a Relop }

function IsRelop(c: char): boolean;

begin

IsRelop := c in ['=', '#', '<', '>'];

end;

{–}

Также нам понадобятся несколько подпрограмм генерации кода:

{–}

{ Complement the Primary Register }

procedure NotIt;

begin

EmitLn('NOT D0');

end;

{–}

.

.

.

{–}

{ AND Top of Stack with Primary }

procedure PopAnd;

begin

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

end;

{–}

{ OR Top of Stack with Primary }

procedure PopOr;

begin

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

end;

{–}

{ XOR Top of Stack with Primary }

procedure PopXor;

begin

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

end;

{–}

{ Compare Top of Stack with Primary }

procedure PopCompare;

begin

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

end;

{–}

{ Set D0 If Compare was = }

procedure SetEqual;

begin

EmitLn('SEQ D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was != }

procedure SetNEqual;

begin

EmitLn('SNE D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was > }

procedure SetGreater;

begin

EmitLn('SLT D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was < }

procedure SetLess;

begin

EmitLn('SGT D0');

EmitLn('EXT D0');

end;

{–}

Все это дает нам необходимые инструменты. БНФ для булевых выражений такая:

<bool-expr> ::= <bool-term> ( <orop> <bool-term> )*

<bool-term> ::= <not-factor> ( <andop> <not-factor> )*

<not-factor> ::= [ '!' ] <relation>

<relation> ::= <expression> [ <relop> <expression> ]

Зоркие читатели могли бы заметить, что этот синтаксис не включает нетерминал «bool-factor» используемый в ранних версиях. Тогда он был необходим потому, что я также разрешал булевы константы TRUE и FALSE. Но не забудьте, что в TINY нет никакого различия между булевыми и арифметическими типами... они могут свободно смешиваться. Так что нет нужды в этих предопределенных значениях... мы можем просто использовать -1 и 0 соответственно.

В терминологии C мы могли бы всегда использовать определения:

#define TRUE -1

#define FALSE 0

(Так было бы, если бы TINY имел препроцессор.) Позднее, когда мы разрешим объявление констант, эти два значения будут предопределены языком.

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

Итак, если мы удовлетворены синтаксисом, представленным выше, то соответствующий код показан ниже:

{–}

{ Recognize and Translate a Relational «Equals» }

procedure Equals;

begin

Match('=');

Expression;

PopCompare;

SetEqual;

end;

{–}

{ Recognize and Translate a Relational «Not Equals» }

procedure NotEquals;

begin

Match('#');

Expression;

PopCompare;

SetNEqual;

end;

{–}

{ Recognize and Translate a Relational «Less Than» }

procedure Less;

begin

Match('<');

Expression;

PopCompare;

SetLess;

end;

{–}

{ Recognize and Translate a Relational «Greater Than» }

procedure Greater;

begin

Match('>');

Expression;

PopCompare;

SetGreater;

end;

{–}

{ Parse and Translate a Relation }

procedure Relation;

begin

Expression;

if IsRelop(Look) then begin

Push;

case Look of

'=': Equals;

'#': NotEquals;

'<': Less;

'>': Greater;

end;

end;

end;

{–}

{ Parse and Translate a Boolean Factor with Leading NOT }

procedure NotFactor;

begin

if Look = '!' then begin

Match('!');

Relation;

NotIt;

end

else

Relation;

end;

{–}

{ Parse and Translate a Boolean Term }

procedure BoolTerm;

begin

NotFactor;

while Look = '&' do begin

Push;

Match('&');

NotFactor;

PopAnd;

end;

end;

{–}

{ Recognize and Translate a Boolean OR }

procedure BoolOr;

begin

Match('|');

BoolTerm;

PopOr;

end;

{–}

{ Recognize and Translate an Exclusive Or }

procedure BoolXor;

begin

Match('~');

BoolTerm;

PopXor;

end;

{–}

{ Parse and Translate a Boolean Expression }

procedure BoolExpression;

begin

BoolTerm;

while IsOrOp(Look) do begin

Push;

case Look of

'|': BoolOr;

'~': BoolXor;

end;

end;

end;

{–}

Чтобы связать все это вместе не забудьте изменить обращение к Expression в процедурах Factor и Assignment на вызов BoolExpression.

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

pvx,y,zbx=z>ye.

что означает

PROGRAM

VAR X,Y,Z

BEGIN

X = Z > Y

END.

Видите как происходит присваивание булевского значения X?

Мы почти дома. Имея булевы выражения легко добавить управляющие структуры. Для TINY мы разрешим только две из них, IF и WHILE:

<if> ::= IF <bool-expression> <block> [ ELSE <block>] ENDIF

<while> ::= WHILE <bool-expression> <block> ENDWHILE

Еще раз позвольте мне разъяснить решения, подразумевающиеся в этом синтаксисе, который сильно отличается от синтаксиса C или Pascal. В обоих этих языках «тело» IF или WHILE расценивается как одиночный оператор. Если вы предполагаете использовать блок из более чем одного оператора вы должны создать составной утверждение использую BEGIN-END (в Pascal) или '{}' (в C). В TINY (и KISS) нет таких вещей как составное утверждение... одиночное или множественное, они являются в этом языке просто блоками.

В KISS все управляющие структуры имеют явные и уникальные ключевые слова, выделяющие операторный блок поэтому не может быть никакой путаницы где он начинается и заканчивается. Это современный подход, используемый в таких уважаемых языках, как Ada и Modula-2 и он полностью устраняет проблему «висячих else».

Обратите внимание, что я мог бы использовать то же самое ключевое слово END для завершения всех конструкций, как это сделано в Pascal. (Закрывающая '}' в C служит той же самой цели.) Но это всегда вело к неразберихе, вот почему программисты на Pascal предпочитают писать так:

end { loop }

или end { if }

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

Одна последняя мысль: каждая из двух конструкций выше имеют нетерминалы

<bool-expression> и <block>,

расположенные рядом без разделяющих ключевых слов. В Паскале мы ожидали бы в этом месте ключевые слова THEN и DO.

Я не вижу проблем в том, чтобы опустить эти ключевые слова, и синтаксический анализатор также не будет иметь проблем, при условии, что мы не сделаем ошибок в bool-expression. С другой стороны, если мы включим эти дополнительные ключевые слова мы получили бы еще один уровень подстраховки за малые деньги, и с этим у меня также нет проблем. Примите правильное решение каким путем пойти.

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

{–}

{ Branch Unconditional }

procedure Branch(L: string);

begin

EmitLn('BRA ' + L);

end;

{–}

{ Branch False }

procedure BranchFalse(L: string);

begin

EmitLn('TST D0');

EmitLn('BEQ ' + L);

end;

{–}

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

{–}

{ Recognize and Translate an IF Construct }

procedure Block; Forward;

procedure DoIf;

var L1, L2: string;

begin

Match('i');

BoolExpression;

L1 := NewLabel;

L2 := L1;

BranchFalse(L1);

Block;

if Look = 'l' then begin

Match('l');

L2 := NewLabel;

Branch(L2);

PostLabel(L1);

Block;

end;

PostLabel(L2);

Match('e');

end;

{–}

{ Parse and Translate a WHILE Statement }

procedure DoWhile;

var L1, L2: string;

begin

Match('w');

L1 := NewLabel;

L2 := NewLabel;

PostLabel(L1);

BoolExpression;

BranchFalse(L2);

Block;

Match('e');

Branch(L1);

PostLabel(L2);

end;

{–}

Чтобы связать все это вместе нам нужно только изменить процедуру Block чтобы распознавать ключевые слова IF и WHILE. Как обычно мы расширим определение блока так:

<block> ::= ( <statement> )*

где

<statement> ::= <if> | <while> | <assignment>

Соответствующий код:

{–}

{ Parse and Translate a Block of Statements }

procedure Block;

begin

while not(Look in ['e', 'l']) do begin

case Look of

'i': DoIf;

'w': DoWhile;

else Assignment;

end;

end;

end;

{–}

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

Фактически, за исключением односимвольного ограничения, мы получили практически полную версию TINY. Я назову его TINY Version 0.1.

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

Для начала, давайте просто разрешим пробелы. Для этого необходимо только добавить вызовы SkipWhite в конец трех подпрограмм GetName, GetNum и Match. Вызов SkipWhite в Init запускает помпу в случае если есть ведущие пробелы.

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

Вставьте новую процедуру:

{–}

{ Skip Over an End-of-Line }

procedure NewLine;

begin

while Look = CR do begin

GetChar;

if Look = LF then GetChar;

SkipWhite;

end;

end;

{–}

Заметьте, что мы видели эту процедуру раньше в виде процедуры Fin. Я изменил имя, так как новое кажется более соответствующим фактическому назначению. Я также изменил код чтобы учесть множественные переносы и строки только с пробелами.

Следующим шагом будет вставка вызовов NewLine везде, где мы посчитаем перенос допустимым. Как я подчеркивал ранее, этот момент может очень различаться для разных языков. В TINY я решил разрешить их практически в любом месте. Это означает, что нам нужно вызывать NewLine в начале (не в конце как с SkipWhite) процедур GetName, GetNum и Match.

Для процедур, которые имеют циклы While, таких как TopDecl, нам нужен вызов NewLine в начале процедуры и в конце каждого цикла. Таким способом мы можем быть уверены, что NewLine вызывается в начале каждого прохода через цикл.

Если вы все это сделали, испытайте программу и проверьте, что она действительно обрабатывает пробелы и переносы.

Если это так, тогда мы готовы работать с многосимвольными токенами и ключевыми словами. Для начала, добавьте дополнительные объявления (скопированные почти дословно из главы 7):

{–}

{ Type Declarations }

type Symbol = string[8];

SymTab = array[1..1000] of Symbol;

TabPtr = ^SymTab;

{–}

{ Variable Declarations }

var Look : char; { Lookahead Character }

Token: char; { Encoded Token }

Value: string[16]; { Unencoded Token }

ST: Array['A'..'Z'] of char;

{–}

{ Definition of Keywords and Token Types }

const NKW = 9;

NKW1 = 10;

const KWlist: array[1..NKW] of Symbol =

('IF', 'ELSE', 'ENDIF', 'WHILE', 'ENDWHILE',

'VAR', 'BEGIN', 'END', 'PROGRAM');

const KWcode: string[NKW1] = 'xilewevbep';

{–}

Затем добавьте три процедуры, также из седьмой главы:

{–}

{ Table Lookup }

function Lookup(T: TabPtr; s: string; n: integer): integer;

var i: integer;

found: Boolean;

begin

found := false;

i := n;

while (i > 0) and not found do

if s = T^[i] then

found := true

else

dec(i);

Lookup := i;

end;

{–}

.

.

{–}

{ Get an Identifier and Scan it for Keywords }

procedure Scan;

begin

GetName;

Token := KWcode[Lookup(Addr(KWlist), Value, NKW) + 1];

end;

{–}

.

.

{–}

{ Match a Specific Input String }

procedure MatchString(x: string);

begin

if Value <> x then Expected('''' + x + '''');

end;

{–}

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

{–}

{ Get an Identifier }

procedure GetName;

begin

NewLine;

if not IsAlpha(Look) then Expected('Name');

Value := '';

while IsAlNum(Look) do begin

Value := Value + UpCase(Look);

GetChar;

end;

SkipWhite;

end;

{–}

Обратите внимание, что эта процедура оставляет свой результат в глобальной строковой переменной Value.

Затем, мы должны изменить каждую обращение к GetName чтобы отразить ее новую форму. Они происходят в Factor, Assignment и Decl:

{–}

{ Parse and Translate a Math Factor }

procedure BoolExpression; Forward;

procedure Factor;

begin

if Look = '(' then begin

Match('(');

BoolExpression;

Match(')');

end

else if IsAlpha(Look) then begin

GetName;

LoadVar(Value[1]);

end

else

LoadConst(GetNum);

end;

{–}

.

.

{–}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

Name := Value[1];

Match('=');

BoolExpression;

Store(Name);

end;

{–}

.

.

{–}

{ Parse and Translate a Data Declaration }

procedure Decl;

begin

GetName;

Alloc(Value[1]);

while Look = ',' do begin

Match(',');

GetName;

Alloc(Value[1]);

end;

end;

{–}

(Заметьте, что мы все еще разрешаем только односимвольные имена переменных поэтому мы используем здесь простое решение и просто используем первый символ строки.)

Наконец, мы должны внести изменения, позволяющие использовать Token вместо Look как символа для проверки и вызывать Scan в подходящих местах. По большей части это включает удаление вызовов Match, редкие замены вызовов Match на вызовы MatchString, и замену вызовов NewLine на вызовы Scan. Вот затронутые подпрограммы:

{–}

{ Recognize and Translate an IF Construct }

procedure Block; Forward;

procedure DoIf;

var L1, L2: string;

begin

BoolExpression;

L1 := NewLabel;

L2 := L1;

BranchFalse(L1);

Block;

if Token = 'l' then begin

L2 := NewLabel;

Branch(L2);

PostLabel(L1);

Block;

end;

PostLabel(L2);

MatchString('ENDIF');

end;

{–}

{ Parse and Translate a WHILE Statement }

procedure DoWhile;

var L1, L2: string;

begin

L1 := NewLabel;

L2 := NewLabel;

PostLabel(L1);

BoolExpression;

BranchFalse(L2);

Block;

MatchString('ENDWHILE');

Branch(L1);

PostLabel(L2);

end;

{–}

{ Parse and Translate a Block of Statements }

procedure Block;

begin

Scan;

while not(Token in ['e', 'l']) do begin

case Token of

'i': DoIf;

'w': DoWhile;

else Assignment;

end;

Scan;

end;

end;

{–}

{ Parse and Translate Global Declarations }

procedure TopDecls;

begin

Scan;

while Token <> 'b' do begin

case Token of

'v': Decl;

else Abort('Unrecognized Keyword ' + Value);

end;

Scan;

end;

end;

{–}

{ Parse and Translate a Main Program }

procedure Main;

begin

MatchString('BEGIN');

Prolog;

Block;

MatchString('END');

Epilog;

end;

{–}

{ Parse and Translate a Program }

procedure Prog;

begin

MatchString('PROGRAM');

Header;

TopDecls;

Main;

Match('.');

end;

{–}

{ Initialize }

procedure Init;

var i: char;

begin

for i := 'A' to 'Z' do

ST[i] := ' ';

GetChar;

Scan;

end;

{–}

Это должно работать. Если все изменения сделаны правильно, вы должны теперь анализировать программы, которые выглядят как программы. (Если вы не сделали всех изменений, не отчаивайтесь. Полный листинг конечной формы дан ниже.)

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

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

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

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

Вот изменения, которые необходимо сделать. Сперва добавьте новую типизированную константу:

NEntry: integer = 0;

Затем измените определение таблицы идентификаторов как показано ниже:

const MaxEntry = 100;

var ST : array[1..MaxEntry] of Symbol;

(Обратите внимание, что ST не объявлен как SymTab. Это объявление липовое, чтобы заставить Lookup работать. SymTab заняля бы слишком много памяти и поэтому фактически никогда не обьявляется).

Затем мы должны заменить InTable.

{–}

{ Look for Symbol in Table }

function InTable(n: Symbol): Boolean;

begin

InTable := Lookup(@ST, n, MaxEntry) <> 0;

end;

{–}

Нам также необходима новая процедура AddEntry, которая добавляет новый элемент в таблицу:

{–}

{ Add a New Entry to Symbol Table }

procedure AddEntry(N: Symbol; T: char);

begin

if InTable(N) then Abort('Duplicate Identifier ' + N);

if NEntry = MaxEntry then Abort('Symbol Table Full');

Inc(NEntry);

ST[NEntry] := N;

SType[NEntry] := T;

end;

{–}

Эта процедура вызывается из Alloc:

{–}

{ Allocate Storage for a Variable }

procedure Alloc(N: Symbol);

begin

if InTable(N) then Abort('Duplicate Variable Name ' + N);

AddEntry(N, 'v');

.

.

.

{–}

Наконец, мы должны изменить все подпрограммы, которые в настоящее время обрабатывают имена переменных как одиночный символ. Они включают LoadVar и Store (просто измените тип с char на string) и Factor, Assignment и Decl (просто измените Value[1] на Value).

Последняя вещь: измените процедуру Init для очистки массива как показано ниже:

{–}

{ Initialize }

procedure Init;

var i: integer;

begin

for i := 1 to MaxEntry do begin

ST[i] := '';

SType[i] := ' ';

end;

GetChar;

Scan;

end;

{–}

Это должно работать. Испытайте ее и проверьте, что вы действительно можете использовать многосимвольные имена переменных.

У нас осталось последнее односимвольное ограничение – ограничение операторов отношений. Некоторые из операторов отношений действительно состоят из одиночных символов, но другие требуют двух. Это '<=' и '>='. Я также предпочитаю Паскалевское '<>' для «не равно» вместо '#'.

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

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

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

{–}

{ Set D0 If Compare was <= }

procedure SetLessOrEqual;

begin

EmitLn('SGE D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was >= }

procedure SetGreaterOrEqual;

begin

EmitLn('SLE D0');

EmitLn('EXT D0');

end;

{–}

Затем измените подпрограммы анализа отношений как показано ниже:

{–}

{ Recognize and Translate a Relational «Less Than or Equal» }

procedure LessOrEqual;

begin

Match('=');

Expression;

PopCompare;

SetLessOrEqual;

end;

{–}

{ Recognize and Translate a Relational «Not Equals» }

procedure NotEqual;

begin

Match('>');

Expression;

PopCompare;

SetNEqual;

end;

{–}

{ Recognize and Translate a Relational «Less Than» }

procedure Less;

begin

Match('<');

case Look of

'=': LessOrEqual;

'>': NotEqual;

else begin

Expression;

PopCompare;

SetLess;

end;

end;

end;

{–}

{ Recognize and Translate a Relational «Greater Than» }

procedure Greater;

begin

Match('>');

if Look = '=' then begin

Match('=');

Expression;

PopCompare;

SetGreaterOrEqual;

end

else begin

Expression;

PopCompare;

SetGreater;

end;

end;

{–}

Это все, что требуется. Теперь вы можете обрабатывать все операторы отношений. Попробуйте.

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

Современное соглашение, установленное в C и продолженное в Ada и Modula-2, состоит в том, чтобы вывести I/O операторы из самого языка и просто включить их в библиотеку подпрограмм. Это было бы прекрасно, за исключением того, что мы пока не имеем никаких средств поддержки подпрограмм. В любом случае, с этим подходом вы столкнетесь с проблемой переменной длины списка параметров. В Паскале I/O операторы встроены в язык, поэтому это единственные операторы, для которых список параметров может иметь переменное число элементов. В C мы примиряемся с клуджами типа scanf и printf и должны передавать количество параметров в вызываемую процедуру. В Ada и Modula-2 мы должны использовать неудобный (и медленный!) способ отдельного вызова для каждого аргумента.

Так что я думаю, что предпочитаю Паскалевский подход встраивания подпрограмм ввода/вывода, даже если мы не нуждаемся в этом.

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

{–}

{ Read Variable to Primary Register }

procedure ReadVar;

begin

EmitLn('BSR READ');

Store(Value);

end;

{–}

{ Write Variable from Primary Register }

procedure WriteVar;

begin

EmitLn('BSR WRITE');

end;

{–}

Идея состоит в том, что READ загружает значение из входного потока в D0, а WRITE выводит его оттуда.

Эти две процедуры представляют собой нашу первую встречу с потребностью в библиотечных процедурах... компонентах Run Time Library (RTL). Конечно кто-то (а именно мы) должен написать эти подпрограммы, но они не являются непосредственно частью компилятора. Я даже не буду беспокоиться о том, чтобы показать здесь эти подпрограммы, так как они очевидно очень ОС-зависимы. Я просто скажу, что для SK*DOS они особенно просты... почти тривиальны. Одна из причин, по которым я не буду показывать их здесь в том, что вы можете добавлять новые виды возможностей, например приглашение в READ или возможность пользователю повторить ошибочный ввод.

Но это действительно отдельный от компилятора проект, так что теперь я буду подразумевать что библиотека, называемая TINYLIB.LIB, существует.

Так как нам теперь нужно загружать ее, мы должны добавить ее загрузку в процедуру Header:

{–}

{ Write Header Info }

procedure Header;

begin

WriteLn('WARMST', TAB, 'EQU $A01E');

EmitLn('LIB TINYLIB');

end;

{–}

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

{–}

{ Definition of Keywords and Token Types }

const NKW = 11;

NKW1 = 12;

const KWlist: array[1..NKW] of Symbol =

('IF', 'ELSE', 'ENDIF', 'WHILE', 'ENDWHILE',

'READ', 'WRITE', 'VAR', 'BEGIN', 'END',

'PROGRAM');

const KWcode: string[NKW1] = 'xileweRWvbep';

{–}

(Обратите внимание, что здесь я использую кода в верхнем регистре чтобы избежать конфликта с 'w' из WHILE.) Затем нам нужны процедуры для обработки оператора ввода/вывода и его списка параметров:

{–}

{ Process a Read Statement }

procedure DoRead;

begin

Match('(');

GetName;

ReadVar;

while Look = ',' do begin

Match(',');

GetName;

ReadVar;

end;

Match(')');

end;

{–}

{ Process a Write Statement }

procedure DoWrite;

begin

Match('(');

Expression;

WriteVar;

while Look = ',' do begin

Match(',');

Expression;

WriteVar;

end;

Match(')');

end;

{–}

Наконец, мы должны расширить процедуру Block для поддержки новых типов операторов:

{–}

{ Parse and Translate a Block of Statements }

procedure Block;

begin

Scan;

while not(Token in ['e', 'l']) do begin

case Token of

'i': DoIf;

'w': DoWhile;

'R': DoRead;

'W': DoWrite;

else Assignment;

end;

Scan;

end;

end;

{–}

На этом все. Теперь у нас есть язык!

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

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

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

Увидимся.

В справочных целях полный листинг TINY версии 1.0 показан ниже:

{–}

program Tiny10;

{–}

{ Constant Declarations }

const TAB = ^I;

CR = ^M;

LF = ^J;

LCount: integer = 0;

NEntry: integer = 0;

{–}

{ Type Declarations }

type Symbol = string[8];

SymTab = array[1..1000] of Symbol;

TabPtr = ^SymTab;

{–}

{ Variable Declarations }

var Look : char; { Lookahead Character }

Token: char; { Encoded Token }

Value: string[16]; { Unencoded Token }

const MaxEntry = 100;

var ST : array[1..MaxEntry] of Symbol;

SType: array[1..MaxEntry] of char;

{–}

{ Definition of Keywords and Token Types }

const NKW = 11;

NKW1 = 12;

const KWlist: array[1..NKW] of Symbol =

('IF', 'ELSE', 'ENDIF', 'WHILE', 'ENDWHILE',

'READ', 'WRITE', 'VAR', 'BEGIN', 'END',

'PROGRAM');

const KWcode: string[NKW1] = 'xileweRWvbep';

{–}

{ Read New Character From Input Stream }

procedure GetChar;

begin

Read(Look);

end;

{–}

{ Report an Error }

procedure Error(s: string);

begin

WriteLn;

WriteLn(^G, 'Error: ', s, '.');

end;

{–}

{ Report Error and Halt }

procedure Abort(s: string);

begin

Error(s);

Halt;

end;

{–}

{ Report What Was Expected }

procedure Expected(s: string);

begin

Abort(s + ' Expected');

end;

{–}

{ Report an Undefined Identifier }

procedure Undefined(n: string);

begin

Abort('Undefined Identifier ' + n);

end;

{–}

{ Recognize an Alpha Character }

function IsAlpha(c: char): boolean;

begin

IsAlpha := UpCase(c) in ['A'..'Z'];

end;

{–}

{ Recognize a Decimal Digit }

function IsDigit(c: char): boolean;

begin

IsDigit := c in ['0'..'9'];

end;

{–}

{ Recognize an AlphaNumeric Character }

function IsAlNum(c: char): boolean;

begin

IsAlNum := IsAlpha(c) or IsDigit(c);

end;

{–}

{ Recognize an Addop }

function IsAddop(c: char): boolean;

begin

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

end;

{–}

{ Recognize a Mulop }

function IsMulop(c: char): boolean;

begin

IsMulop := c in ['*', '/'];

end;

{–}

{ Recognize a Boolean Orop }

function IsOrop(c: char): boolean;

begin

IsOrop := c in ['|', '~'];

end;

{–}

{ Recognize a Relop }

function IsRelop(c: char): boolean;

begin

IsRelop := c in ['=', '#', '<', '>'];

end;

{–}

{ Recognize White Space }

function IsWhite(c: char): boolean;

begin

IsWhite := c in [' ', TAB];

end;

{–}

{ Skip Over Leading White Space }

procedure SkipWhite;

begin

while IsWhite(Look) do

GetChar;

end;

{–}

{ Skip Over an End-of-Line }

procedure NewLine;

begin

while Look = CR do begin

GetChar;

if Look = LF then GetChar;

SkipWhite;

end;

end;

{–}

{ Match a Specific Input Character }

procedure Match(x: char);

begin

NewLine;

if Look = x then GetChar

else Expected('''' + x + '''');

SkipWhite;

end;

{–}

{ Table Lookup }

function Lookup(T: TabPtr; s: string; n: integer): integer;

var i: integer;

found: Boolean;

begin

found := false;

i := n;

while (i > 0) and not found do

if s = T^[i] then

found := true

else

dec(i);

Lookup := i;

end;

{–}

{ Locate a Symbol in Table }

{ Returns the index of the entry. Zero if not present. }

function Locate(N: Symbol): integer;

begin

Locate := Lookup(@ST, n, MaxEntry);

end;

{–}

{ Look for Symbol in Table }

function InTable(n: Symbol): Boolean;

begin

InTable := Lookup(@ST, n, MaxEntry) <> 0;

end;

{–}

{ Add a New Entry to Symbol Table }

procedure AddEntry(N: Symbol; T: char);

begin

if InTable(N) then Abort('Duplicate Identifier ' + N);

if NEntry = MaxEntry then Abort('Symbol Table Full');

Inc(NEntry);

ST[NEntry] := N;

SType[NEntry] := T;

end;

{–}

{ Get an Identifier }

procedure GetName;

begin

NewLine;

if not IsAlpha(Look) then Expected('Name');

Value := '';

while IsAlNum(Look) do begin

Value := Value + UpCase(Look);

GetChar;

end;

SkipWhite;

end;

{–}

{ Get a Number }

function GetNum: integer;

var Val: integer;

begin

NewLine;

if not IsDigit(Look) then Expected('Integer');

Val := 0;

while IsDigit(Look) do begin

Val := 10 * Val + Ord(Look) – Ord('0');

GetChar;

end;

GetNum := Val;

SkipWhite;

end;

{–}

{ Get an Identifier and Scan it for Keywords }

procedure Scan;

begin

GetName;

Token := KWcode[Lookup(Addr(KWlist), Value, NKW) + 1];

end;

{–}

{ Match a Specific Input String }

procedure MatchString(x: string);

begin

if Value <> x then Expected('''' + x + '''');

end;

{–}

{ Output a String with Tab }

procedure Emit(s: string);

begin

Write(TAB, s);

end;

{–}

{ Output a String with Tab and CRLF }

procedure EmitLn(s: string);

begin

Emit(s);

WriteLn;

end;

{–}

{ Generate a Unique Label }

function NewLabel: string;

var S: string;

begin

Str(LCount, S);

NewLabel := 'L' + S;

Inc(LCount);

end;

{–}

{ Post a Label To Output }

procedure PostLabel(L: string);

begin

WriteLn(L, ':');

end;

{–}

{ Clear the Primary Register }

procedure Clear;

begin

EmitLn('CLR D0');

end;

{–}

{ Negate the Primary Register }

procedure Negate;

begin

EmitLn('NEG D0');

end;

{–}

{ Complement the Primary Register }

procedure NotIt;

begin

EmitLn('NOT D0');

end;

{–}

{ Load a Constant Value to Primary Register }

procedure LoadConst(n: integer);

begin

Emit('MOVE #');

WriteLn(n, ',D0');

end;

{–}

{ Load a Variable to Primary Register }

procedure LoadVar(Name: string);

begin

if not InTable(Name) then Undefined(Name);

EmitLn('MOVE ' + Name + '(PC),D0');

end;

{–}

{ Push Primary onto Stack }

procedure Push;

begin

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

end;

{–}

{ Add Top of Stack to Primary }

procedure PopAdd;

begin

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

end;

{–}

{ Subtract Primary from Top of Stack }

procedure PopSub;

begin

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

EmitLn('NEG D0');

end;

{–}

{ Multiply Top of Stack by Primary }

procedure PopMul;

begin

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

end;

{–}

{ Divide Top of Stack by Primary }

procedure PopDiv;

begin

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

EmitLn('EXT.L D7');

EmitLn('DIVS D0,D7');

EmitLn('MOVE D7,D0');

end;

{–}

{ AND Top of Stack with Primary }

procedure PopAnd;

begin

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

end;

{–}

{ OR Top of Stack with Primary }

procedure PopOr;

begin

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

end;

{–}

{ XOR Top of Stack with Primary }

procedure PopXor;

begin

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

end;

{–}

{ Compare Top of Stack with Primary }

procedure PopCompare;

begin

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

end;

{–}

{ Set D0 If Compare was = }

procedure SetEqual;

begin

EmitLn('SEQ D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was != }

procedure SetNEqual;

begin

EmitLn('SNE D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was > }

procedure SetGreater;

begin

EmitLn('SLT D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was < }

procedure SetLess;

begin

EmitLn('SGT D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was <= }

procedure SetLessOrEqual;

begin

EmitLn('SGE D0');

EmitLn('EXT D0');

end;

{–}

{ Set D0 If Compare was >= }

procedure SetGreaterOrEqual;

begin

EmitLn('SLE D0');

EmitLn('EXT D0');

end;

{–}

{ Store Primary to Variable }

procedure Store(Name: string);

begin

if not InTable(Name) then Undefined(Name);

EmitLn('LEA ' + Name + '(PC),A0');

EmitLn('MOVE D0,(A0)')

end;

{–}

{ Branch Unconditional }

procedure Branch(L: string);

begin

EmitLn('BRA ' + L);

end;

{–}

{ Branch False }

procedure BranchFalse(L: string);

begin

EmitLn('TST D0');

EmitLn('BEQ ' + L);

end;

{–}

{ Read Variable to Primary Register }

procedure ReadVar;

begin

EmitLn('BSR READ');

Store(Value[1]);

end;

{ Write Variable from Primary Register }

procedure WriteVar;

begin

EmitLn('BSR WRITE');

end;

{–}

{ Write Header Info }

procedure Header;

begin

WriteLn('WARMST', TAB, 'EQU $A01E');

end;

{–}

{ Write the Prolog }

procedure Prolog;

begin

PostLabel('MAIN');

end;

{–}

{ Write the Epilog }

procedure Epilog;

begin

EmitLn('DC WARMST');

EmitLn('END MAIN');

end;

{–}

{ Parse and Translate a Math Factor }

procedure BoolExpression; Forward;

procedure Factor;

begin

if Look = '(' then begin

Match('(');

BoolExpression;

Match(')');

end

else if IsAlpha(Look) then begin

GetName;

LoadVar(Value);

end

else

LoadConst(GetNum);

end;

{–}

{ Parse and Translate a Negative Factor }

procedure NegFactor;

begin

Match('-');

if IsDigit(Look) then

LoadConst(-GetNum)

else begin

Factor;

Negate;

end;

end;

{–}

{ Parse and Translate a Leading Factor }

procedure FirstFactor;

begin

case Look of

'+': begin

Match('+');

Factor;

end;

'-': NegFactor;

else Factor;

end;

end;

{–}

{ Recognize and Translate a Multiply }

procedure Multiply;

begin

Match('*');

Factor;

PopMul;

end;

{–}

{ Recognize and Translate a Divide }

procedure Divide;

begin

Match('/');

Factor;

PopDiv;

end;

{–}

{ Common Code Used by Term and FirstTerm }

procedure Term1;

begin

while IsMulop(Look) do begin

Push;

case Look of

'*': Multiply;

'/': Divide;

end;

end;

end;

{–}

{ Parse and Translate a Math Term }

procedure Term;

begin

Factor;

Term1;

end;

{–}

{ Parse and Translate a Leading Term }

procedure FirstTerm;

begin

FirstFactor;

Term1;

end;

{–}

{ Recognize and Translate an Add }

procedure Add;

begin

Match('+');

Term;

PopAdd;

end;

{–}

{ Recognize and Translate a Subtract }

procedure Subtract;

begin

Match('-');

Term;

PopSub;

end;

{–}

{ Parse and Translate an Expression }

procedure Expression;

begin

FirstTerm;

while IsAddop(Look) do begin

Push;

case Look of

'+': Add;

'-': Subtract;

end;

end;

end;

{–}

{ Recognize and Translate a Relational «Equals» }

procedure Equal;

begin

Match('=');

Expression;

PopCompare;

SetEqual;

end;

{–}

{ Recognize and Translate a Relational «Less Than or Equal» }

procedure LessOrEqual;

begin

Match('=');

Expression;

PopCompare;

SetLessOrEqual;

end;

{–}

{ Recognize and Translate a Relational «Not Equals» }

procedure NotEqual;

begin

Match('>');

Expression;

PopCompare;

SetNEqual;

end;

{–}

{ Recognize and Translate a Relational «Less Than» }

procedure Less;

begin

Match('<');

case Look of

'=': LessOrEqual;

'>': NotEqual;

else begin

Expression;

PopCompare;

SetLess;

end;

end;

end;

{–}

{ Recognize and Translate a Relational «Greater Than» }

procedure Greater;

begin

Match('>');

if Look = '=' then begin

Match('=');

Expression;

PopCompare;

SetGreaterOrEqual;

end

else begin

Expression;

PopCompare;

SetGreater;

end;

end;

{–}

{ Parse and Translate a Relation }

procedure Relation;

begin

Expression;

if IsRelop(Look) then begin

Push;

case Look of

'=': Equal;

'<': Less;

'>': Greater;

end;

end;

end;

{–}

{ Parse and Translate a Boolean Factor with Leading NOT }

procedure NotFactor;

begin

if Look = '!' then begin

Match('!');

Relation;

NotIt;

end

else

Relation;

end;

{–}

{ Parse and Translate a Boolean Term }

procedure BoolTerm;

begin

NotFactor;

while Look = '&' do begin

Push;

Match('&');

NotFactor;

PopAnd;

end;

end;

{–}

{ Recognize and Translate a Boolean OR }

procedure BoolOr;

begin

Match('|');

BoolTerm;

PopOr;

end;

{–}

{ Recognize and Translate an Exclusive Or }

procedure BoolXor;

begin

Match('~');

BoolTerm;

PopXor;

end;

{–}

{ Parse and Translate a Boolean Expression }

procedure BoolExpression;

begin

BoolTerm;

while IsOrOp(Look) do begin

Push;

case Look of

'|': BoolOr;

'~': BoolXor;

end;

end;

end;

{–}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: string;

begin

Name := Value;

Match('=');

BoolExpression;

Store(Name);

end;

{–}

{ Recognize and Translate an IF Construct }

procedure Block; Forward;

procedure DoIf;

var L1, L2: string;

begin

BoolExpression;

L1 := NewLabel;

L2 := L1;

BranchFalse(L1);

Block;

if Token = 'l' then begin

L2 := NewLabel;

Branch(L2);

PostLabel(L1);

Block;

end;

PostLabel(L2);

MatchString('ENDIF');

end;

{–}

{ Parse and Translate a WHILE Statement }

procedure DoWhile;

var L1, L2: string;

begin

L1 := NewLabel;

L2 := NewLabel;

PostLabel(L1);

BoolExpression;

BranchFalse(L2);

Block;

MatchString('ENDWHILE');

Branch(L1);

PostLabel(L2);

end;

{–}

{ Process a Read Statement }

procedure DoRead;

begin

Match('(');

GetName;

ReadVar;

while Look = ',' do begin

Match(',');

GetName;

ReadVar;

end;

Match(')');

end;

{–}

{ Process a Write Statement }

procedure DoWrite;

begin

Match('(');

Expression;

WriteVar;

while Look = ',' do begin

Match(',');

Expression;

WriteVar;

end;

Match(')');

end;

{–}

{ Parse and Translate a Block of Statements }

procedure Block;

begin

Scan;

while not(Token in ['e', 'l']) do begin

case Token of

'i': DoIf;

'w': DoWhile;

'R': DoRead;

'W': DoWrite;

else Assignment;

end;

Scan;

end;

end;

{–}

{ Allocate Storage for a Variable }

procedure Alloc(N: Symbol);

begin

if InTable(N) then Abort('Duplicate Variable Name ' + N);

AddEntry(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;

{–}

{ Parse and Translate a Data Declaration }

procedure Decl;

begin

GetName;

Alloc(Value);

while Look = ',' do begin

Match(',');

GetName;

Alloc(Value);

end;

end;

{–}

{ Parse and Translate Global Declarations }

procedure TopDecls;

begin

Scan;

while Token <> 'b' do begin

case Token of

'v': Decl;

else Abort('Unrecognized Keyword ' + Value);

end;

Scan;

end;

end;

{–}

{ Parse and Translate a Main Program }

procedure Main;

begin

MatchString('BEGIN');

Prolog;

Block;

MatchString('END');

Epilog;

end;

{–}

{ Parse and Translate a Program }

procedure Prog;

begin

MatchString('PROGRAM');

Header;

TopDecls;

Main;

Match('.');

end;

{–}

{ Initialize }

procedure Init;

var i: integer;

begin

for i := 1 to MaxEntry do begin

ST[i] := '';

SType[i] := ' ';

end;

GetChar;

Scan;

end;

{–}

{ Main Program }

begin

Init;

Prog;

if Look <> CR then Abort('Unexpected data after ''.''');

end.

{–}