Креншоу Д. Пишем компилятор
Подождите немного. Документ загружается.
Лекции по построению компилятора на Pascal
procedure ReadVar;
begin
## EmitLn('BSR READ');
## Store(Value[1]);
end;
#
{ Write Variable from Primary Register }
procedure WriteVar;
begin
## EmitLn('BSR WRITE');
end;
#
{--------------------------------------------------------------}
{ Write Header Info }
procedure Header;
begin
## WriteLn('WARMST', TAB, 'EQU $A01E');
end;
#
{--------------------------------------------------------------}
{ Write the Prolog }
procedure Prolog;
begin
## PostLabel('MAIN');
end;
#
{--------------------------------------------------------------}
{ Write the Epilog }
procedure Epilog;
begin
## EmitLn('DC WARMST');
## EmitLn('END MAIN');
end;
#
{---------------------------------------------------------------}
{ Parse and Translate a Math Factor }
procedure BoolExpression; Forward;
procedure Factor;
begin
## if Look = '(' then begin
##### Match('(');
##### BoolExpression;
##### Match(')');
##### end
## else if IsAlpha(Look) then begin
##### GetName;
##### LoadVar(Value);
##### end
## else
##### LoadConst(GetNum);
end;
#
{--------------------------------------------------------------}
{ Parse and Translate a Negative Factor }
procedure NegFactor;
begin
## Match('-');
## if IsDigit(Look) then
##### LoadConst(-GetNum)
## else begin
##### Factor;
##### Negate;
## end;
end;
#
{--------------------------------------------------------------}
{ Parse and Translate a Leading Factor }
151
Лекции по построению компилятора на Pascal
procedure FirstFactor;
begin
## case Look of
#### '+': begin
############ Match('+');
############ Factor;
######### end;
#### '-': NegFactor;
## else# Factor;
## end;
end;
#
{--------------------------------------------------------------}
{ Recognize and Translate a Multiply }
procedure Multiply;
begin
## Match('*');
## Factor;
## PopMul;
end;
#
{-------------------------------------------------------------}
{ Recognize and Translate a Divide }
procedure Divide;
begin
## Match('/');
## Factor;
## PopDiv;
end;
#
{---------------------------------------------------------------}
{ Common Code Used by Term and FirstTerm }
procedure Term1;
begin
## while IsMulop(Look) do begin
##### Push;
##### case Look of
###### '*': Multiply;
###### '/': Divide;
##### end;
## end;
end;
#
{---------------------------------------------------------------}
{ Parse and Translate a Math Term }
procedure Term;
begin
## Factor;
## Term1;
end;
#
{---------------------------------------------------------------}
{ Parse and Translate a Leading Term }
procedure FirstTerm;
begin
## FirstFactor;
## Term1;
end;
#
{--------------------------------------------------------------}
{ Recognize and Translate an Add }
procedure Add;
begin
## Match('+');
## Term;
## PopAdd;
152
Лекции по построению компилятора на Pascal
end;
#
{-------------------------------------------------------------}
{ Recognize and Translate a Subtract }
procedure Subtract;
begin
## Match('-');
## Term;
## PopSub;
end;
#
{---------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
## FirstTerm;
## while IsAddop(Look) do begin
##### Push;
##### case Look of
###### '+': Add;
###### '-': Subtract;
##### end;
## end;
end;
#
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Equals" }
procedure Equal;
begin
## Match('=');
## Expression;
## PopCompare;
## SetEqual;
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;
153
Лекции по построению компилятора на Pascal
####### 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;
#
{---------------------------------------------------------------}
{ Parse and Translate a Relation }
#
procedure Relation;
begin
## Expression;
## if IsRelop(Look) then begin
##### Push;
##### case Look of
###### '=': Equal;
###### '<': Less;
###### '>': Greater;
##### end;
## end;
end;
#
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Factor with Leading NOT }
procedure NotFactor;
begin
## if Look = '!' then begin
##### Match('!');
##### Relation;
##### NotIt;
##### end
## else
##### Relation;
end;
#
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Term }
procedure BoolTerm;
begin
## NotFactor;
## while Look = '&' do begin
##### Push;
##### Match('&');
##### NotFactor;
##### PopAnd;
## end;
end;
#
{--------------------------------------------------------------}
{ Recognize and Translate a Boolean OR }
154
Лекции по построению компилятора на Pascal
procedure BoolOr;
begin
## Match('|');
## BoolTerm;
## PopOr;
end;
#
{--------------------------------------------------------------}
{ Recognize and Translate an Exclusive Or }
procedure BoolXor;
begin
## Match('~');
## BoolTerm;
## PopXor;
end;
#
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Expression }
procedure BoolExpression;
begin
## BoolTerm;
## while IsOrOp(Look) do begin
##### Push;
##### case Look of
###### '|': BoolOr;
###### '~': BoolXor;
##### end;
## end;
end;
#
{--------------------------------------------------------------}
{ Parse and Translate an Assignment Statement }
procedure Assignment;
var Name: string;
begin
## Name := Value;
## Match('=');
## BoolExpression;
## Store(Name);
end;
#
{---------------------------------------------------------------}
{ Recognize and Translate an IF Construct }
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;
155
Лекции по построению компилятора на Pascal
begin
## L1 := NewLabel;
## L2 := NewLabel;
## PostLabel(L1);
## BoolExpression;
## BranchFalse(L2);
## Block;
## MatchString('ENDWHILE');
## Branch(L1);
## PostLabel(L2);
end;
#
{--------------------------------------------------------------}
{ Process a Read Statement }
procedure DoRead;
begin
## Match('(');
## GetName;
## ReadVar;
## while Look = ',' do begin
##### Match(',');
##### GetName;
##### ReadVar;
## end;
## Match(')');
end;
#
{--------------------------------------------------------------}
{ Process a Write Statement }
procedure DoWrite;
begin
## Match('(');
## Expression;
## WriteVar;
## while Look = ',' do begin
##### Match(',');
##### Expression;
##### WriteVar;
## end;
## Match(')');
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;
###### 'R': DoRead;
###### 'W': DoWrite;
##### else Assignment;
##### end;
##### Scan;
## end;
end;
#
{--------------------------------------------------------------}
{ Allocate Storage for a Variable }
procedure Alloc(N: Symbol);
begin
## if InTable(N) then Abort('Duplicate Variable Name ' + N);
## AddEntry(N, 'v');
## Write(N, ':', TAB, 'DC ');
## if Look = '=' then begin
156
Лекции по построению компилятора на Pascal
##### Match('=');
##### If Look = '-' then begin
######## Write(Look);
######## Match('-');
##### end;
##### WriteLn(GetNum);
##### end
## else
##### WriteLn('0');
end;
#
{--------------------------------------------------------------}
{ Parse and Translate a Data Declaration }
procedure Decl;
begin
## GetName;
## Alloc(Value);
## while Look = ',' do begin
##### Match(',');
##### GetName;
##### Alloc(Value);
## 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: integer;
begin
## for i := 1 to MaxEntry do begin
##### ST[i] := '';
157
Лекции по построению компилятора на Pascal
##### SType[i] := ' ';
## end;
## GetChar;
## Scan;
end;
#
{--------------------------------------------------------------}
{ Main Program }
begin
## Init;
## Prog;
## if Look <> CR then Abort('Unexpected data after ''.''');
end.
{--------------------------------------------------------------}
#
158
Лекции по построению компилятора на Pascal
11. Пересмотр лексического анализа
ВВЕДЕНИЕ
У меня есть хорошие и плохие новости. Плохие новости - эта глава не та, которую я вам
обещал последний раз. Более того, и следующая глава также.
Хорошие новости в причине появления этой главы: я нашел способ упростить и улучшить]
лексический анализатор компилятора. Позвольте мне объяснить.
ПРЕДПОСЫЛКА
Если вы помните, мы подробно говорили на тему лексических анализаторов в Главе 7 и я
оставил вас с проектом распределенного сканера который, я чувствовал, был почти
настолько простым, насколько я смог сделать... более чем большинство из того, что я где-
либо видел. Мы использовали эту идею в Главе 10. Полученная структура компилятора была
простой и она делала свою работу.
Однако недавно я начал испытывать проблемы такого рода, которые подсказывают, что
возможно вы делаете что-то неправильно.
Проблемы достигли критической стадии когда я попытался обратиться к вопросу точек с
запятой. Некоторые люди спрашивали меня, действительно ли KISS будет использовать их
для разделения операторов. Я не намеревался использовать точки с запятой просто потому,
что они мне не нравятся и, как вы можете видеть, они не доказали своей необходимости.
Но я знаю, что многие из вас, как и я, привыкли к ним, так что я намеревался написать
короткую главу чтобы показать вам, как легко они могут быть добавлены раз вы так склонны
к ним.
Что ж, оказалось что их совсем непросто добавить. Фактически это было чрезвычайно
трудно.
Я полагаю, что должен был понять что что-то было неправильно из-за проблемы переносов
строк. В последних двух главах мы обращались к этому вопросу и я показал вам, как
работать с переносами с помощью процедуры, названной достаточно соответствующе
NewLine. В TINY Version 1.0 я] расставил вызовы этой процедуры в стратегических местах
кода.
Кажется, что всякий раз, когда я обращался к проблеме переносов, я, однако, находил этот
вопрос сложным и полученный синтаксически анализатор оказывался очень ненадежным...
одно удаление или добавление здесь или там и все разваливалось. Оглядываясь назад, я
понимаю, что это было предупреждение, на которое я просто не обращал внимания.
Когда я попробовал добавить точку с запятой к переносам строк это стало последней каплей.
Я получил слишком сложное решение. Я начал понимать, что необходимо что-то менять
коренным образом.
Итак,] в некотором отношении эта глава заставить нас возвратиться немного назад и
пересмотреть заново вопрос лексического анализа. Сожалею об этом. Это цена, которую вы
платите за возможность следить за мной в режиме реального времени. Но новая версия
определенно усовершенствована и хорошо послужит нам дальше.
Как я сказал, сканер, использованный нами в Главе 10, был почти настолько простым,
насколько возможно. Но все может быть улучшено. Новый сканер более похож на
классический сканер и не так прост как прежде. Но общая структура компилятора даже
проще чем раньше. Она также более надежная и проще для добавления и/или модификации.
Я думаю, что она стоит времени, потраченного на это отклонение. Так что в этой главе я
покажу вам новую структуру. Без сомнения вы будете счастливы узнать, что хотя изменения
влияют на многие процедуры, они не очень глубоки и поэтому мы теряем не очень многое из
того что было сделано до этого.
159
Лекции по построению компилятора на Pascal
Как ни странно, новый сканер намного более стандартен чем старый и он очень похож на
более общий сканер, показанный мной ранее в главе 7. Вы должны помнить день, когда я
сказал:] K-I-S-S!
ПРОБЛЕМА
Проблема начинает проявлять себя в процедуре 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;
{--------------------------------------------------------------}
Как вы можете видеть, Block ориентирован на индивидуальные утверждения программы.
При каждом проходе цикла мы знаем, что мы находимся в начале утверждения. Мы выходим
из блока когда обнаруживаем END или ELSE.
Но предположим, что вместо этого мы встретили точку с запятой. Вышеуказанная процедура
не может ее обработать, так как процедура Scan ожидает и может принимать только токены,
начинающиеся с буквы.
Я повозился с этим немного чтобы найти исправление. Я нашел множество возможных
подходов, но ни один из них меня не удовлетворял. В конце концов я выяснил причину.
Вспомните, что когда мы начинали с наших одно-символьных синтаксических анализаторов,
мы приняли соглашение, по которому предсказывающий символ должен быть всегда
предварительно считан. То есть, мы имели бы символ, соответствующий нашей текущей
позиции во входном потоке, помещенный в глобальной символьной переменной Look, так
что мы могли проверять его столько раз, сколько необходимо. По правилу, которое мы
приняли, каждый распознаватель, если он находил предназначенный ему символ, перемещал
бы Look на следующий символ во входном потоке.
Это простое и фиксированное соглашение служило нам очень хорошо когда мы имели одно-
символьные токены, и все еще служит. Был бы большой смысл применить то же самое
правило и к много символьным токенам.
Но когда мы залезли в лексический анализ, я начал нарушать это простое правило. Сканер из
Главы 10 действительно продвигался к следующему токену если он находил идентификатор
или ключевое слово, но он не делал этого если находил возврат каретки, символ пробела или
оператор.
Теперь, такой смешанный режим работы ввергает нас в глубокую проблему в процедуре
Block, потому что был или нет входной поток продвинут зависит от вида встреченного нами
токена. Если это ключевое слово или левая часть операции присваивания, "курсор", как
определено содержимым Look, был продвинут к следующему символу или к началу
незаполненного пространства. Если, с другой стороны, токен является точкой с запятой, или
если мы нажали возврат каретки курсор не был продвинут.
Само собой разумеется, мы можем добавить достаточно логики чтобы удержаться на
правильном пути. Но это сложно и делает весь анализатор очень ненадежным.
160