Давайте создадим компилятор! - Джек Креншоу
Шрифт:
Интервал:
Закладка:
TINY будет иметь только две управляющие конструкции IF и WHILE. KISS будет поддерживать очень богатый набор конструкций включая одну, которую мы не обсуждали здесь ранее... CASE.
KISS будет поддерживать раздельно компилируемые модули.
Одно предостережение: так как я все еще не знаю достаточно об ассемблере для 80x86, все эти модули компилятора все еще будут написаны для поддержки кода 68000. Однако в программах, которые я планирую вам представить, вся генерация кода была тщательно изолирована в отдельном модуле, так что любой предприимчивый студент смог бы перенастроить их на любой другой процессор. Эта задача «оставлена как упражнение для студента». Я сделаю предложение прямо здесь и сейчас: с человеком, который предоставит нам первый надежный перевод для 80x86, я буду счастлив обсудить коллективные авторские права и авторские отчисления от предстоящей книги.
Но хватит говорить. Давайте приступим к изучению типов. Как я сказал ранее, мы будем делать это как и в последней главе: выполняя эксперименты с использованием односимвольных токенов.
Таблица идентификаторов
Должно быть очевидным, что если мы собираемся работать с переменными различных типов, нам понадобится какое-то место для записи их типов. Очевидным средством для этого является таблица идентификаторов и мы уже использовали ее например для различия между локальными и глобальными переменными и между переменными и процедурами.
Структура таблицы идентификаторов для односимвольных токенов особенно проста и мы использовали ее прежде несколько раз. Для работы с ней, мы возьмем некоторые процедуры, которые мы использовали раньше.
Сначала, нам необходимо объявить саму таблицу идентификаторов:
{–}
{ Variable Declarations }
var Look: char; { Lookahead Character }
ST: Array['A'..'Z'] of char; { *** ДОБАВЬТЕ ЭТУ СТРОКУ ***}
{–}
Затем мы должны удостовериться, что она инициализируется в процедуре Init:
{–}
{ Initialize }
procedure Init;
var i: char;
begin
for i := 'A' to 'Z' do
ST[i] := '?';
GetChar;
end;
{–}
Следующая процедура в действительности нам не нужна, но она будет полезна для отладки. Все, что она делает, это формирует дамп содержимого таблицы идентификаторов:
{–}
{ Dump the Symbol Table }
procedure DumpTable;
var i: char;
begin
for i := 'A' to 'Z' do
WriteLn(i, ' ', ST[i]);
end;
{–}
В действительности не имеет значения, где вы поместите эту процедуру... я планирую группировать все подпрограммы таблицы идентификаторов вместе, так что я поместил ее сразу после процедур сообщений об ошибках.
Если вы осторожный тип (как я), вам возможно захотелось бы начать с тестовой программы, которая ничего не делает а просто инициализирует таблицу и затем создает ее дамп. Только для того, чтобы быть уверенным, что все мы находимся на одной волне, ниже я воспроизвожу всю программу, дополненную новыми процедурами. Заметьте, что эта версия включает поддержку пробелов:
{–}
program Types;
{–}
{ Constant Declarations }
const TAB = ^I;
CR = ^M;
LF = ^J;
{–}
{ Variable Declarations }
var Look: char; { Lookahead Character }
ST: Array['A'..'Z'] of char;
{–}
{ 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;
{–}
{ Dump the Symbol Table }
procedure DumpTable;
var i: char;
begin
for i := 'A' to 'Z' do
WriteLn(i, ' ', ST[i]);
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 Fin;
begin
if Look = CR then begin
GetChar;
if Look = LF then
GetChar;
end;
end;
{–}
{ Match a Specific Input Character }
procedure Match(x: char);
begin
if Look = x then GetChar
else Expected('''' + x + '''');
SkipWhite;
end;
{–}
{ Get an Identifier }
function GetName: char;
begin
if not IsAlpha(Look) then Expected('Name');
GetName := UpCase(Look);
GetChar;
SkipWhite;
end;
{–}
{ Get a Number }
function GetNum: char;
begin
if not IsDigit(Look) then Expected('Integer');
GetNum := Look;
GetChar;
SkipWhite;
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;
{–}
{ Initialize }
procedure Init;
var i: char;
begin
for i := 'A' to 'Z' do
ST[i] := '?';
GetChar;
SkipWhite;
end;
{–}
{ Main Program }
begin
Init;
DumpTable;
end.
{–}
ОК, запустите эту программу. Вы должны получить (очень быстро) распечатку всех букв алфавита (потенциальных идентификаторов) сопровождаемых вопросительным знаком. Не очень захватывающе, но это только начало.
Конечно, вообще-то мы хотим видеть типы только тех переменных, которые были определены. Мы можем устранить другие добавив в DumpTable условие IF. Измените цикл следующим образом:
for i := 'A' to 'Z' do
if ST[i] <> '?' then
WriteLn(i, ' ', ST[i]);
Теперь запустите программу снова. Что вы получили?
Хорошо, это даже более скучно чем раньше! Сейчас вообще ничего не выводится, так как в данный момент ни одно из имен не было обьявлено. Мы можем немного приправить результат вставив в основную программу несколько операторов, объявляющих несколько записей. Попробуйте такие:
ST['A'] := 'a';
ST['P'] := 'b';
ST['X'] := 'c';
На этот раз, когда вы запустите программу, вы должны получить распечатку, показывающую, что таблица идентификаторов работает правильно.
Добавление записей
Конечно, заполнение таблицы напрямую – довольно плохая практика и она не сможет хорошо нам послужить в будущем. То, что нам нужно, это процедура, добавляющая записи в таблицу. В то же самое время мы знаем, что нам будет необходимо тестировать таблицу для проверки, что мы не объявляем повторно переменную, которая уже используется (что легко может случиться при наличии всего 26 вариантов!). Для поддержки всего это введите следующие новые процедуры:
{–}
{ Report Type of a Variable }
function TypeOf(N: char): char;
begin
TypeOf := ST[N];
end;
{–}
{ Report if a Variable is in the Table }
function InTable(N: char): boolean;
begin
InTable := TypeOf(N) <> '?';
end;
{–}
{ Check for a Duplicate Variable Name }
procedure CheckDup(N: char);
begin
if InTable(N) then Abort('Duplicate Name ' + N);
end;
{–}
{ Add Entry to Table }
procedure AddEntry(N, T: char);
begin
CheckDup(N);
ST[N] := T;
end;
{–}
Теперь измените три строки в основной программе следующим образом:
AddEntry('A', 'a');
AddEntry('P', 'b');
AddEntry('X', 'c');
и запустите программу снова. Работает? Тогда у нас есть подпрограммы таблицы идентификаторов, необходимые для поддержки нашей работы с типами. В следующем разделе мы начнем их использовать на практике.
Распределение памяти
В других программах, подобных этой, включая сам компилятор TINY, мы уже обращались к вопросу объявления глобальных переменных и кода, генерируемого для них. Давайте создадим здесь урезанную версию «компилятора», чья единственная функция – позволить нам объявлять переменные. Помните, синтаксис для объявления:
<data decl> ::= VAR <identifier>
Снова, мы можем вытащить массу кода из предыдущих программ. Следующий код – это урезанные версии тех процедур. Они значительно упрощены, так как я удалил такие тонкости как списки переменных и инициализаторы. Обратите внимание, что в процедуре Alloc новый вызов AddEntry будет также заботиться о проверке двойных объявлений:
{–}
{ Allocate Storage for a Variable }
procedure Alloc(N: char);
begin
AddEntry(N, 'v');
WriteLn(N, ':', TAB, 'DC 0');
end;
{–}
{ Parse and Translate a Data Declaration }
procedure Decl;
var Name: char;
begin
Match('v');
Alloc(GetName);
end;
{–}
{ Parse and Translate Global Declarations }
procedure TopDecls;
begin
while Look <> '.' do begin
case Look of
'v': Decl;
else Abort('Unrecognized Keyword ' + Look);
end;
Fin;
end;
end;
{–}
Теперь, в основной программе добавьте вызов TopDecl и запустите программу. Попробуйте распределить несколько переменных и обратите внимание на полученный сгенерированный код. Для вас это пройденный этап, поэтому результат должен выглядеть знакомым. Заметьте из кода для TopDecls что программа завершается точкой.
Пока вы здесь, попробуйте объявить две переменные с одинаковыми именами и проверьте что синтаксический анализатор отлавливает ошибку.
Объявление типов
