Читать онлайн «Давайте создадим компилятор!». Страница 36

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

{–}

{ Scan the Current Identifier for Keywords }

procedure Scan;

begin

if Token = 'x' then

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

end;

{–}

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

Следующая версия MatchString замещает символьно-ориентированную Match. Заметьте, что как и Match она не продвигает входной поток.

{–}

{ Match a Specific Input String }

procedure MatchString(x: string);

begin

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

Next;

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;

{–}

Не забудьте, что новая версия Scan не продвигает входной поток, она только сканирует ключевые слова. Входной поток должен продвигаться каждой процедурой, которую вызывает Block.

В общих чертах, мы должны заменить каждую проверку Look на аналогичную проверку Token. Например:

{–}

{ Parse and Translate a Boolean Expression }

procedure BoolExpression;

begin

BoolTerm;

while IsOrOp(Token) do begin

Push;

case Token of

'|': BoolOr;

'~': BoolXor;

end;

end;

end;

{–}

В процедурах типа Add мы больше не должны использовать Match. Нам необходимо только вызывать Next для продвижения входного потока:

{–}

{ Recognize and Translate an Add }

procedure Add;

begin

Next;

Term;

PopAdd;

end;

{–}

Управляющие структуры фактически более простые. Мы просто вызываем Next для продвижения через ключевые слова управляющих конструкций:

{–}

{ Recognize and Translate an IF Construct }

procedure Block; Forward;

procedure DoIf;

var L1, L2: string;

begin

Next;

BoolExpression;

L1 := NewLabel;

L2 := L1;

BranchFalse(L1);

Block;

if Token = 'l' then begin

Next;

L2 := NewLabel;

Branch(L2);

PostLabel(L1);

Block;

end;

PostLabel(L2);

MatchString('ENDIF');

end;

{–}

Это все необходимые изменения. В листинге Tiny Version 1.1, данном ниже, я также сделал ряд других «усовершенствований», которые в действительности не нужны. Позвольте мне кратко разъяснить их:

1. Я удалил две процедуры Prog и Main и объединил их функции в основной программе. Они кажется не добавляли ясности... фактически они просто немного загрязняли программу.

2. Я удалил ключевые слова PROGRAM и BEGIN из списка ключевых слов. Каждое из них появляется в одном месте, так что нет необходимости искать его.

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

4. Я добавил несколько подпрограмм проверок ошибок типа CheckTable и CheckDup и заменил встроенный код на их вызовы. Это навело порядок во многих подпрограммах.

5. Я убрал проверку ошибок из подпрограмм генерации кода типа Store и поместил их в подпрограммы анализа, к которым они относятся. Смотрите например Assignment.

6. Существовала ошибка в InTable и Locate которая заставляла их проверять все позиции вместо позиций только с достоверными данными. Теперь они проверяют только допустимые ячейки. Это позволяет нам устранить необходимость инициализации таблицы идентификаторов, которая была в Init.

7. Процедура AddEntry теперь имеет два параметра, что помогает сделать программу немного более модульной.

8. Я подчистил код для операторов отношений добавив новые процедуры CompareExpression и NextExpression.

9. Я устранил ошибку в подпрограмме Read... старая версия не выполняла проверку на правильность имени переменной.

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

В следующей главе будет другое отклонение: сперва обсуждение точек с запятой и все, что привело меня такому беспорядку. Затем мы займемся процедурами и типами. Добавление этих возможностей далеко продвинет нас на пути к выведению KISS из категории «игрушечных языков». Мы подобрались очень близко к возможности написать серъезный компилятор.

{–}

program Tiny11;

{–}

{ 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 = 9;

NKW1 = 10;

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

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

'READ', 'WRITE', 'VAR', 'END');

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

{–}

{ 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;

{–}

{ Report a Duplicate Identifier }

procedure Duplicate(n: string);

begin

Abort('Duplicate Identifier ' + n);

end;

{–}

{ Check to Make Sure the Current Token is an Identifier }

procedure CheckIdent;

begin

if Token <> 'x' then Expected('Identifier');

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, CR, LF];

end;

{–}

{ Skip Over Leading White Space }

procedure SkipWhite;

begin

while IsWhite(Look) do

GetChar;

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, NEntry);

end;

{–}

{ Look for Symbol in Table }

function InTable(n: Symbol): Boolean;

begin

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

end;

{–}

{ Check to See if an Identifier is in the Symbol Table }

{ Report an error if it's not. }

procedure CheckTable(N: Symbol);

begin

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

end;

{–}

{ Check the Symbol Table for a Duplicate Identifier }

{ Report an error if identifier is already in table. }

procedure CheckDup(N: Symbol);

begin

if InTable(N) then Duplicate(N);

end;

{–}

{ Add a New Entry to Symbol Table }

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

begin

CheckDup(N);

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

Inc(NEntry);

ST[NEntry] := N;

SType[NEntry] := T;

end;

{–}

{ Get an Identifier }

procedure GetName;

begin

SkipWhite;

if Not IsAlpha(Look) then Expected('Identifier');

Token := 'x';

Value := '';

repeat

Value := Value + UpCase(Look);

GetChar;

until not IsAlNum(Look);

end;

{–}

{ Get a Number }

procedure GetNum;

begin

SkipWhite;

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

Token := '#';

Value := '';

repeat

Value := Value + Look;

GetChar;

until not IsDigit(Look);

end;

{–}

{ Get an Operator }

procedure GetOp;

begin

SkipWhite;

Token := Look;

Value := Look;

GetChar;

end;

{–}

{ Get the Next Input Token }

procedure Next;

begin

SkipWhite;

if IsAlpha(Look) then GetName

else if IsDigit(Look) then GetNum

else GetOp;

end;

{–}

{ Scan the Current Identifier for Keywords }

procedure Scan;

begin

if Token = 'x' then

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 + '''');

Next;

end;

{–}

{ Output a String with Tab }

procedure Emit(s: string);