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

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 или возможность пользователю повторить ошибочный ввод.