СТАНОВИТСЯ ИНТЕРЕСНЕЙ
Хорошо, сейчас мы имеем довольно хороший лексический анализатор, который разбивает входной поток на лексемы. Мы могли бы использовать его как есть и иметь полезный компилятор. Но есть некоторые другие аспекты лексического анализа, которые мы должны охватить.
Особенно следует рассмотреть (вздрогните) эффективность. Помните, когда мы работали с одно-символьными токенами, каждой проверкой было сравнение одного символа Look с байтовой константой. Мы также использовали в основном оператор Case.
С много символьными лексемами, возвращаемыми Scan, все эти проверки становятся сравнением строк. Гораздо медленнее. И не только медленнее но и неудобней, так как в Паскале не существует строкового эквивалента оператора Case. Особенно расточительным кажется проверять то что состоит из одного символа... "=", "+" и другие операторы... используя сравнение строк.
Сравнение строк не является невозможным. Рон Кейн использовал этот подход при написании Small C. Так как мы придерживаемся принципа KISS мы были бы оправданы согласившись с этим подходом. Но тогда я не смог бы рассказать вам об одном из ключевых методов, используемых в "настоящих" компиляторах.
Вы должны запомнить: лексический анализатор будет вызываться часто! Фактически один раз для каждой лексемы во всей исходной программе. Эксперименты показали, что средний компилятор тратит где-то от 20 до 40 процентов своего времени на подпрограммах лексического анализа. Если существовало когда-либо место, где эффективность заслуживает пристального рассмотрения, то это оно.
По этой причине большинство создателей компиляторов заставляют лексический анализатор выполнять немного больше работы, "токенизируя" входной поток. Идея состоит в том, чтобы сравнивать каждую лексему со списком допустимых ключевых слов и операторов и возвращать уникальный код для каждой распознанной. В случае обычного имени переменной или числа мы просто возвращаем код, который говорит, к какому типу лексем они относятся и сохраняем где-нибудь текущую строку.
Первое, что нам нужно - это способ идентификации ключевых слов. Мы всегда можем сделать это с помощью последовательных проверок IF, но несомненно было бы хорошо, если бы мы имели универсальную подпрограмму, которая могла бы сравнивать данную строку с таблицей ключевых слов. (Между прочим, позднее нам понадобится такая же подпрограмма для работы с таблицей идентификаторов). Это обычно выявляет проблему Паскаля, потому что стандартный Паскаль не имеет массивов переменной длины. Это настоящая головная боль - объявлять различные подпрограммы поиска для каждой таблицы. Стандартный Паскаль также не позволяет инициализировать массивы, поэтому вам придется видеть код типа:
Table[1] := 'IF';
Table[2] := 'ELSE';
.
.
Table[n] := 'END';
что может получиться довольно длинным если есть много ключевых слов.
К счастью Turbo Pascal 4.0 имеет расширения, которые устраняют обе эти проблемы. Массивы-константы могут быть объявлены с использованием средства TP "типизированные константы" а переменные размерности могут быть поддержаны с помощью Си-подобных расширений для указателей.
Сначала, измените ваши объявления подобным образом:
|
Code: |
|
{ Type Declarations } type Symbol = string[8]; SymTab = array[1..1000] of Symbol; TabPtr = ^SymTab; |
(Размерность, использованная в SymTab не настоящая... память не распределяется непосредственно этим объявлением, а размерность должна быть только "достаточно большой")
Затем, сразу после этих объявлений, добавьте следующее:
|
Code: |
|
{ Definition of Keywords and Token Types } const KWlist: array [1..4] of Symbol = ('IF', 'ELSE', 'ENDIF', 'END'); |
Затем, вставьте следующую новую функцию:
|
Code: |
|
{ 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; |
Чтобы проверить ее вы можете временно изменить основную программу следующим образом:
|
Code: |
|
{ 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 }
Измените сканер так:
|
Code: |
|
{ 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 сейчас стала процедурой а не функцией).
|
Code: |
|
{ 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. Тогда новая форма для этих четырех процедур будет такой:
|
Code: |
|
{ 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; |
Просьба писать ваши замечания, наблюдения и все остальное,
что поможет улучшить предоставляемую информацию на этом сайте.
ВСЕ КОММЕНТАРИИ МОДЕРИРУЮТСЯ ВРУЧНУЮ, ТАК ЧТО СПАМИТЬ БЕСПОЛЕЗНО!