Книга: Давайте создадим компилятор!

Становится интересней

Становится интересней

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

Особенно следует рассмотреть (вздрогните) эффективность. Помните, когда мы работали с односимвольными токенами, каждой проверкой было сравнение одного символа Look с байтовой константой. Мы также использовали в основном оператор Case.

С многосимвольными лексемами, возвращаемыми Scan, все эти проверки становятся сравнением строк. Гораздо медленнее. И не только медленнее но и неудобней, так как в Паскале не существут строкового эквивалента оператора Case. Особенно расточительным кажется проверять то что состоит из одного символа... "=", "+" и другие операторы... используя сравнение строк.

Сравнение строк не является невозможным. Рон Кейн использовал этот подход при написании Small C. Так как мы придерживаемся принципа KISS мы были бы оправданы согласившись с этим подходом. Но тогда я не смог бы рассказать вам об одном из ключевых методов, используемых в «настоящих» компиляторах.

Вы должны запомнить: лексический анализатор будет вызываться часто! Фактически один раз для каждой лексемы во всей исходной программе. Эксперименты показали, что средний компилятор тратит где-то от 20 до 40 процентов своего времени на подпрограммах лексического анализа. Если существовало когда-либо место, где эффективность заслуживает пристального рассмотрения, то это оно.

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

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

Table[1] := 'IF';

Table[2] := 'ELSE';

.

.

Table[n] := 'END';

что может получиться довольно длинным если есть много ключевых слов.

К счастью Turbo Pascal 4.0 имеет расширения, которые устраняют обе эти проблемы. Массивы-константы могут быть обьявлены с использованием средства TP «типизированные константы» а переменные размерности могут быть поддержаны с помощью Си-подобных расширений для указателей.

Сначала, измените ваши объявления подобным образом:

{–}

{ Type Declarations }

type Symbol = string[8];

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

TabPtr = ^SymTab;

{–}

(Размерность, использованная в SymTab не настоящая... память не распределяется непосредственно этим объявлением, а размерность должна быть только «достаточно большой»)

Затем, сразу после этих объявлений, добавьте следующее:

{–}

{ Definition of Keywords and Token Types }

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

('IF', 'ELSE', 'ENDIF', 'END');

{–}

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

{–}

{ Table Lookup }

{ If the input string matches a table entry, return the entry

index. If not, return a zero. }

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;

{–}

Чтобы проверить ее вы можете временно изменить основную программу следующим образом:

{–}

{ Main Program }

begin

ReadLn(Token);

WriteLn(Lookup(Addr(KWList), Token, 4));

end.

{–}

Обратите внимание как вызывается Lookup: функция Addr устанавливает указатель на KWList, который передается в Lookup.

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

Теперь, когда мы можем распознавать ключевые слова, далее необходимо договориться о возвращаемых для них кодах.

Итак, какие кода мы должны возвращать? В действительности есть только два приемлемых варианта. Это похоже на идеальное применения перечислимого типа Паскаля. К примеру, вы можете определить что-то типа

SymType = (IfSym, ElseSym, EndifSym, EndSym, Ident, Number, Operator);

и договориться возвращать переменную этого типа. Давайте попробуем это. Вставьте строку выше в описание типов.

Теперь добавьте два описания переменных:

Token: Symtype; { Current Token }

Value: String[16]; { String Token of Look }

Измените сканер так:

{–}

{ Lexical Scanner }

procedure Scan;

var k: integer;

begin

while Look = CR do

Fin;

if IsAlpha(Look) then begin

Value := GetName;

k := Lookup(Addr(KWlist), Value, 4);

if k = 0 then

Token := Ident

else

Token := SymType(k – 1);

end

else if IsDigit(Look) then begin

Value := GetNum;

Token := Number;

end

else if IsOp(Look) then begin

Value := GetOp;

Token := Operator;

end

else begin

Value := Look;

Token := Operator;

GetChar;

end;

SkipWhite;

end;

{–}

(Заметьте, что Scan сейчас стала процедурой а не функцией).

Наконец, измените основную программу:

{–}

{ Main Program }

begin

Init;

repeat

Scan;

case Token of

Ident: write('Ident ');

Number: Write('Number ');

Operator: Write('Operator ');

IfSym, ElseSym, EndifSym, EndSym: Write('Keyword ');

end;

Writeln(Value);

until Token = EndSym;

end.

{–}

Мы заменили строку Token, используемую раньше, на перечислимый тип. Scan возвращает тип в переменной Token и возвращает саму строку в новой переменной Value.

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

Теперь у нас все работает правильно, и было легко сгенерировать это из того, что мы имели раньше. Однако, она все равно кажется мне немного «перегруженной». Мы можем ее немного упростить, позволив GetName, GetNum, GetOp и Scan работать с глобальными переменными Token и Value, вследствие этого удаляя их локальные копии. Кажется немного умней было бы переместить просмотр таблицы в GetName. Тогда новая форма для этих четырех процедур будет такой:

{–}

{ Get an Identifier }

procedure GetName;

var k: integer;

begin

Value := '';

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

while IsAlNum(Look) do begin

Value := Value + UpCase(Look);

GetChar;

end;

k := Lookup(Addr(KWlist), Value, 4);

if k = 0 then

Token := Ident

else

Token := SymType(k-1);

end;

{–}

{ Get a Number }

procedure GetNum;

begin

Value := '';

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

while IsDigit(Look) do begin

Value := Value + Look;

GetChar;

end;

Token := Number;

end;

{–}

{ Get an Operator }

procedure GetOp;

begin

Value := '';

if not IsOp(Look) then Expected('Operator');

while IsOp(Look) do begin

Value := Value + Look;

GetChar;

end;

Token := Operator;

end;

{–}

{ Lexical Scanner }

procedure Scan;

var k: integer;

begin

while Look = CR do

Fin;

if IsAlpha(Look) then

GetName

else if IsDigit(Look) then

GetNum

else if IsOp(Look) then

GetOp

else begin

Value := Look;

Token := Operator;

GetChar;

end;

SkipWhite;

end;

{–}

Оглавление книги

Оглавление статьи/книги
Похожие страницы

Генерация: 1.776. Запросов К БД/Cache: 3 / 1
поделиться
Вверх Вниз