РАБОТА С ТОЧКАМИ С ЗАПЯТОЙ
Есть два различных способа работы с точками с запятой используемые в популярных языках. В Паскале точка с запятой расценивается как разделитель операторов. Точка с запятой не требуется после последнего утверждения в блоке. Синтаксис:
<block> ::= <statement> ( ';' <statement>)*
<statement> ::= <assignment> | <if> | <while> ... | null
(пустое утверждение важно!)
Паскаль также определяет некоторые точки с запятой в других местах, таких как после утверждения PROGRAM.
В C и Ada, с другой стороны, точка с запятой рассматривается как терминатор операторов и следует после всех утверждений (с некоторыми смущающими и путающими исключениями). Синтаксис для них простой:
<block> ::= ( <statement> ';')*
Из двух синтаксисов, синтаксис Паскаля внешне выглядит более рациональным, но опыт показал, что он ведет к некоторым странным трудностям. Люди так привыкают ставить точку с запятой после каждого утверждения, что они также предпочитают ставить ее и после последнего утверждения в блоке. Это обычно не приносит какого-либо вреда... она просто обрабатывается как пустое утверждение. Многие программисты на Паскале, включая вашего покорного слугу, делают точно также. Но есть одно место, в котором вы абсолютно не можете поставить точку с запятой - прямо перед ELSE. Это маленький подводный камень стоил мне множества дополнительных компиляций, особенно когда ELSE добавляется к существующему коду. Так что выбор C/Ada оказывается лучше. Очевидно, Никлаус Вирт думает также: в Modula-2 он отказался от Паскалевского подхода.
Имея эти два синтаксиса, легко (теперь, когда мы реорганизовали синтаксический анализатор!) добавить эти возможности в наш анализатор. Давайте сначала возьмем последний случай, так как он проще.
Для начала я упростил программу представив новую подпрограмму распознавания:
{--------------------------------------------------------------}
{ Match a Semicolon }
procedure Semi;
begin
MatchString(';');
end;
{--------------------------------------------------------------}
Эта процедура очень похожа на наш старый Match. Она требует чтобы следующим токеном была точка с запятой. Найдя его, она переходит к следующему.
Так как точка с запятой следует за утверждением, процедура 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;
'x': Assignment;
end;
Semi;
Scan;
end;
end;
{--------------------------------------------------------------}
Внимательно взгляните на тонкие изменения в операторе case. Вызов Assigment теперь ограничивается проверкой Token. Это позволит избежать вызова Assigment когда токен является точкой с запятой (что случается когда утверждение пустое).
Так как объявления - тоже утверждения, мы также должны добавить вызов Semi в процедуру TopDecl:
{--------------------------------------------------------------}
{ Parse and Translate Global Declarations }
procedure TopDecls;
begin
Scan;
while Token = 'v' do begin
Alloc;
while Token = ',' do
Alloc;
Semi;
end;
end;
{--------------------------------------------------------------}
Наконец нам нужен вызов для утверждения PROGRAM:
{--------------------------------------------------------------}
{ Main Program }
begin
Init;
MatchString('PROGRAM');
Semi;
Header;
TopDecls;
MatchString('BEGIN');
Prolog;
Block;
MatchString('END');
Epilog;
end.
{--------------------------------------------------------------}
Проще некуда. Испробуйте это с копией TINY и скажите как вам это нравится.
Версия Паскаля немного сложнее, но она все равно требует только небольших изменений и то только в процедуре Block. Для максимальной простоты давайте разобьем процедуру на две части. Следующая процедура обрабатывает только одно утверждение:
{--------------------------------------------------------------}
{ Parse and Translate a Single Statement }
procedure Statement;
begin
Scan;
case Token of
'i': DoIf;
'w': DoWhile;
'R': DoRead;
'W': DoWrite;
'x': Assignment;
end;
end;
{--------------------------------------------------------------}
Используя эту процедуру мы можем переписать Block так:
{--------------------------------------------------------------}
{ Parse and Translate a Block of Statements }
procedure Block;
begin
Statement;
while Token = ';' do begin
Next;
Statement;
end;
end;
{--------------------------------------------------------------}
Это, уверен, не повредило, не так ли? Теперь мы можем анализировать точки с запятой в Паскаль подобном стиле.
РАСПРЕДЕЛЕНИЕ ПАМЯТИ
В других программах, подобных этой, включая сам компилятор 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 что программа завершается точкой.
Пока вы здесь, попробуйте объявить две переменные с одинаковыми именами и проверьте что синтаксический анализатор отлавливает ошибку.
РАСПРЕДЕЛЕННЫЕ СКАНЕРЫ ПРОТИВ ЦЕНТРАЛИЗОВАННЫХ
Структура лексического анализатора, которую я только что вам показал, весьма стандартна и примерно 99% всех компиляторов используют что-то очень близкое к ней. Это, однако, не единственно возможная структура, или даже не всегда самая лучшая.
Проблема со стандартным подходом состоит в том, что сканер не имеет никаких сведений о контексте. Например, он не может различить оператор присваивания "=" и оператор отношения "=" (возможно именно поэтому и C и Паскаль используют для них различные строки). Все, что сканер может сделать, это передать оператор синтаксическому анализатору, который может точно сказать исходя из контекста, какой это оператор. Точно так же, ключевое слово "IF" не может быть посредине арифметического выражения, но если ему случится оказаться там, сканер не увидит в этом никакой проблемы и возвратит его синтаксическому анализатору, правильно закодировав как "IF".
С таким подходом, мы в действительности не используем всю информацию, имеющуюся в нашем распоряжении. В середине выражения, например синтаксический анализатор "знает", что нет нужды искать ключевое слово, но он не имеет никакой возможности сказать это сканеру. Так что сканер продолжает делать это. Это, конечно, замедляет компиляцию.
В настоящих компиляторах проектировщики часто принимают меры для передачи подробной информации между сканером и парсером, только чтобы избежать такого рода проблем. Но это может быть неуклюже и, конечно, уничтожит часть модульности в структуре компилятора.
Альтернативой является поиск какого-то способа для использования контекстной информации, которая исходит из знания того, где мы находимся в синтаксическом анализаторе. Это возвращает нас обратно к понятию распределенного сканера, в котором различные части сканера вызываются в зависимости от контекста.
В языке KISS, как и большинстве языков, ключевые слова появляются только в начале утверждения. В таких местах, как выражения они запрещены. Также, с одним небольшим исключением (много символьные операторы отношений), которое легко обрабатывается, все операторы одно-символьны, что означает, что нам совсем не нужен GetOp.
Так что, оказывается, даже с много символьными токенами мы все еще можем всегда точно определить вид лексемы исходя из текущего предсказывающего символа, исключая самое начало утверждения.
Даже в этой точке, единственным видом лексемы, который мы можем принять, является идентификатор. Нам необходимо только определить, является ли этот идентификатор ключевым словом или левой частью оператора присваивания.
Тогда мы заканчиваем все еще нуждаясь только в GetName и GetNum, которые используются так же, как мы использовали их в ранних главах.
Сначала вам может показаться, что это шаг назад и довольно примитивный способ. Фактически же, это усовершенствование классического сканера, так как мы используем подпрограммы сканирования только там, где они действительно нужны. В тех местах, где ключевые слова не разрешены, мы не замедляем компиляцию, ища их.
РАСШИРЕНИЕ
Чтобы расширить компилятор мы должны просто работать с возможностями языка последовательно. Я хочу начать с пустой процедуры, которая ничего не делает, затем добавлять детали в пошаговом режиме. Давайте начнем с обработки блока в соответствии с его PDL выше. Мы можем сделать это в два этапа. Сначала добавьте пустую процедуру:
{--------------------------------------------------------------}
{ Parse and Translate a Pascal Block }
procedure DoBlock(Name: char);
begin
end;
{--------------------------------------------------------------}
и измените Prog следующим образом:
{--------------------------------------------------------------}
{ Parse and Translate A Program }
procedure Prog;
var Name: char;
begin
Match('p');
Name := GetName;
Prolog;
DoBlock(Name);
Match('.');
Epilog(Name);
end;
{--------------------------------------------------------------}
Это конечно не должно изменить поведения программы, и не меняет. Но сейчас определение Prog закончено и мы можем перейти к расширению DoBlock. Это получается прямо из его БНФ определения:
{--------------------------------------------------------------}
{ Parse and Translate a Pascal Block }
procedure DoBlock(Name: char);
begin
Declarations;
PostLabel(Name);
Statements;
end;
{--------------------------------------------------------------}
Процедура PostLabel была определена в главе по ветвлениям. Скопируйте ее в вашу копию Cradle.
Я возможно должен объяснить причину вставки метки. Это имеет отношение к работе SK*DOS. В отличие от некоторых других ОС, SK*DOS позволяет точке входа в основную программу находиться в любом месте программы. Все, что вы должны сделать, это дать этой точке имя. Вызов PostLabel помещает это имя как раз перед первым выполнимым утверждением в основной программе. Как SK*DOS узнает какая из множества меток является точкой входа, спросите вы? Та, которая соответствует утверждению END в конце программы.
Теперь нам нужны заглушки для процедур Declarations и Statements. Сделайте их пустыми процедурами как мы делали это раньше.
Программа все еще делает то же самое? Тогда мы можем перейти к следующему этапу.
РАСШИРЕНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА
Хотя я обещал вам где-то в Главе 14, что мы никогда снова не будем переписывать каждую одиночную функцию заново, я начал делать это с Главы 15. Единственная причина: эта длинная пауз между двумя главами делала обзор кажущимся чрезвычайно оправданным... даже необходимым и для вас и для меня. Более важно, решение собрать процедуры в модули заставило нас взглянуть на каждую из них снова, хотели мы этого или нет. И, наконец, откровенно говоря, за последние четыре года у меня появились некоторые новые идеи, которые гарантировали свежий взгляд на некоторые старые вещи. Когда я с начала начал эту серию я был искренне поражен и обрадован, узнав насколько простыми могут быть сделаны подпрограммы анализа. Но в этот последний раз я удивил сам себя снова и был способен делать их точно также, но даже немного проще.
Однако, из-за тотального переписывания модулей синтаксического анализа я не был только способен включить многого в последнюю главу. Из-за этого наш герой, синтаксический анализатор, когда мы последний раз его видели, был только тенью себя прежнего, содержащий только код, достаточный для анализа и обработки показателя состоящего или из переменной или константы. Основным достижением этой текущей главы должно стать восстановление синтаксического анализатора в его прежней славе. В этом процессе, я надеюсь, вы будете терпеливы, если мы иногда будем рассматривать основы, с которые мы имели дело и давно уже прошли.
Сначала, давайте позаботимся о проблеме, к которой мы обращались прежде: наша текущая версия процедуры Factor, как мы оставили ее в Главе 15, не может обрабатывать отрицательные параметры. Чтобы исправить это мы представим процедуру SignedFactor:
{--------------------------------------------------------------}
{ Parse and Translate a Factor with Optional Sign }
procedure SignedFactor;
var Sign: char;
begin
Sign := Look;
if IsAddop(Look) then
GetChar;
Factor;
if Sign = '-' then Negate;
end;
{--------------------------------------------------------------}
Заметьте, что эта процедура вызывает новую подпрограмму генерации кода Negate:
{--------------------------------------------------------------}
{ Negate Primary }
procedure Negate;
begin
EmitLn('NEG D0');
end;
{--------------------------------------------------------------}
(Здесь и в других местах в этой серии я собираюсь только показывать вам новые подпрограммы. Я рассчитываю, что вы поместите их в соответствующий модуль, который вы должны без проблем определить. Не забывайте добавлять заголовок процедуры в раздел interface модуля.)
В основной программе просто измените вызов процедуры Factor на SignedFactor и протестируйте код. Разве не хорошо компоновщик Turbo и средство make поддерживают все детали?
Да, я знаю, код не очень эффективен. Если мы введем число -3 будет сгенерирован такой код:
MOVE #3,D0
NEG D0
что действительно, действительно грубо. Мы можем сделать лучше, конечно, просто предварительно добавив знак минус к строке, передаваемой в LoadConstant, но это добавляет несколько строк кода в SignedFactor и здесь я применяю философию KISS очень агрессивно. Более того, сказать правду, я думаю что подсознательно наслаждаюсь генерацией "действительно грубого" кода, так как я могу иметь удовольствие наблюдать как он будет становиться драматически лучше, когда мы примемся за методы оптимизации.
Большинство из вас никогда не слышало о Джоне Спрее, поэтому позвольте мне представить его вам здесь. Джон из Новой Зеландии и преподает информатику в одном из ее университетов. Джон написал компилятор для Motorola 6809, основанный на восхитительном, Паскаль подобном языке собственной разработки, названном "Whimsical". Позднее он перенес компилятор на 68000 и некоторое время это был единственный компилятор, который я имел для своей доморощенной системы на 68000.
К слову сказать, один из моих стандартных тестов для любого компилятора - изучение того, как компилятор работает с пустой программой типа:
program main;
begin
end.
Мой тест измеряет время, требуемое на компиляцию и связывание, и размер сгенерированного объектного файла. Бесспорный проигравший в этом тесте - компилятор DEC C для VAX, который тратит 60 секунд на компиляцию на VAX 11/780 и генерирует объектный файл 50k. Компилятор Джона бесспорно сейчас, в будущем и навсегда король по части размера кода. Для данной пустой программе Whimsical генерирует точно два байта, реализуя одну инструкцию:
RET
Устанавливая опцию компилятора генерировать include файл а не автономную программу, Джон может даже урезать этот размер с двух байт до нуля! Несколько трудно добиться нулевого объектного файла, вы не согласны?
Само собой разумеется, что я рассматриваю Джона как эксперта в оптимизации кода и мне нравится что он однажды сказал: "Лучший способ оптимизации - не оптимизировать вообще, а изначально производить хороший код". Слова, по которым стоит жить. Когда мы начнем оптимизацию мы будем следовать уведомлению Джона и нашим первым шагом будет не добавление щелевого оптимизатора или другого постфактного устройства, но улучшение качества выдаваемого кода перед оптимизацией. Поэтому пометьте SignedFactor как первого хорошего кандидата на внимание и пока оставим его.
REPEAT-UNTIL
Имеется одна конструкция, которую я взял напрямую из Паскаля. Синтаксис:
REPEAT <block> UNTIL <condition>
и синтаксически-управляемый перевод:
REPEAT { L = NewLabel;
PostLabel(L) }
<block>
UNTIL
<condition> { Emit(BEQ L) }
Как обычно, код вытекает отсюда довольно легко:
{--------------------------------------------------------------}
{ Parse and Translate a REPEAT Statement }
procedure DoRepeat;
var L: string;
begin
Match('r');
L := NewLabel;
PostLabel(L);
Block;
Match('u');
Condition;
EmitLn('BEQ ' + L);
end;
{--------------------------------------------------------------}
Как и прежде, мы должны добавить вызов DoRepeat в Block. Хотя на этот раз есть различия. Я решил использовать "r" вместо REPEAT (естественно), но я также решил использовать "u" вместо UNTIL. Это означает, что "u" должен быть добавлен к множеству символов в условии while. Это символы, которые сигнализируют о выходе из текущего блока... символы "follow", на жаргоне разработчиков компиляторов.
{--------------------------------------------------------------}
{ Recognize and Translate a Statement Block }
procedure Block;
begin
while not(Look in ['e', 'l', 'u']) do begin
case Look of
'i': DoIf;
'w': DoWhile;
'p': DoLoop;
'r': DoRepeat;
else Other;
end;
end;
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;
{--------------------------------------------------------------}
Эти две процедуры функционально почти идентичны тем, которые я показал вам в Главе 7. Каждая из них выбирает текущий токен, или идентификатор или число, в глобальную строковую переменную Value. Они также присваивают кодированной версии, Token, соответствующий код. Входной поток останавливается на Look, содержащем первый символ, не являющийся частью токена.
Мы можем сделать то же самое для операторов, даже много символьных, с помощью процедуры типа:
{--------------------------------------------------------------}
{ Get an Operator }
procedure GetOp;
begin
Token := Look;
Value := '';
repeat
Value := Value + Look;
GetChar;
until IsAlpha(Look) or IsDigit(Look) or IsWhite(Look);
end;
{--------------------------------------------------------------}
Обратите внимание, что GetOps возвращает в качестве закодированного токена первый символ оператора. Это важно, потому что это означает, что теперь мы можем использовать этот одиночный символ для управления синтаксическим анализатором вместо предсказывающего символа.
Нам нужно связать эти процедуры вместе в одну процедуру, которая может обрабатывать все три случая. Следующая процедура будет считывать любой из этих типов токенов и всегда оставлять входной поток за ним:
{--------------------------------------------------------------}
{ Get the Next Input Token }
procedure Next;
begin
SkipWhite;
if IsAlpha(Look) then GetName
else if IsDigit(Look) then GetNum
else GetOp;
end;
{--------------------------------------------------------------}
Обратите внимание, что здесь я поместил SkipWhite перед вызовами а не после. Это означает в основном, что переменная Look не будет содержать значимого значения и, следовательно, мы не должны использовать ее как тестируемое значение при синтаксическом анализе, как мы делали до этого. Это большое отклонение от нашего нормального подхода.
Теперь, не забудьте, что раньше я избегал обработки символов возврата каретки (CR) и перевода строки (LF) как незаполненного пространства. Причина была в том, что так как SkipWhite вызывается последней в сканере, встреча с LF инициировала бы чтение из входного потока. Если бы мы были на последней строке программы, мы не могли бы выйти до тех пор, пока мы не введем другую строку с отличным от пробела символом. Именно поэтому мне требовалась вторая процедура NewLine для обработки CRLF.
Но сейчас, когда первым происходит вызов SkipWhite, это то поведение, которое нам нужно. Компилятор должен знать, что появился другой токен или он не должен вызывать Next. Другими словами, он еще не обнаружил завершающий END. Поэтому мы будем настаивать на дополнительных данных до тех пор, пока не найдем что-либо.
Все это означает, что мы можем значительно упростить и программу и концепции, обрабатывая CR и LF как незаполненное пространство и убрав NewLine. Вы можете сделать это просто изменив функцию IsWhite:
{--------------------------------------------------------------}
{ Recognize White Space }
function IsWhite(c: char): boolean;
begin
IsWhite := c in [' ', TAB, CR, LF];
end;
{--------------------------------------------------------------}
Мы уже пробовали аналогичные подпрограммы в Главе 7, но вы могли бы также попробовать и эти. Добавьте их к копии Cradle и вызовите Next в основной программе:
{--------------------------------------------------------------}
{ Main Program }
begin
Init;
repeat
Next;
WriteLn(Token, ' ', Value);
until Token = '.';
end.
{--------------------------------------------------------------}
Откомпилируйте и проверьте, что вы можете разделять программу на серии токенов и вы получаете правильные кода для каждого токена.
Почти работает, но не совсем. Существуют две потенциальные проблемы: Во-первых, в KISS/TINY почти все наши операторы - одно-символьные. Единственное исключение составляют операторы отношений >=, <= и <>. Было бы позором обрабатывать все операторы как строки и выполнять сравнение строк когда почти всегда удовлетворит сравнение одиночных символов. Второе, и более важное, программа не работает, когда два оператора появляются вместе как в (a+b)*(c+d). Здесь строка после b была бы интерпретирована как один оператор ")*(".
Можно устранить эту проблему. К примеру мы могли бы просто дать GetOp список допустимых символов и обрабатывать скобки как отличный от других тип операторов. Но это хлопотное дело.
К счастью, имеется лучший способ, который решает все эти проблемы. Так как почти все операторы одно-символьные, давайте просто позволим GetOp получать только один символ одновременно. Это не только упрощает GetOp, но также немного ускоряет программу. У нас все еще остается проблема операторов отношений, но мы в любом случае обрабатывали их как специальные случаи.
Так что вот финальная версия GetOp:
{--------------------------------------------------------------}
{ Get an Operator }
procedure GetOp;
begin
SkipWhite;
Token := Look;
Value := Look;
GetChar;
end;
{--------------------------------------------------------------}
Обратите внимание, что я все еще присваиваю Value значение. Если вас действительно затрагивает эффективность, вы могли бы это опустить. Когда мы ожидаем оператор, мы в любом случае будем проверять только Token, так что значение этой строки не будет иметь значение. Но мне кажется хорошая практика дать ей значение на всякий случай.
Испытайте эту версию с каким-нибудь реалистично выглядящим кодом. Вы должны быть способны разделять любую программу на ее индивидуальные токены, но предупреждаю, что двух символьные операторы отношений будут отсканированы как два раздельных токена. Это нормально... мы будем выполнять их синтаксический анализ таким способом.
Теперь, в главе 7 функция Next была объединена с процедурой Scan, которая также сверяла каждый идентификатор со списком ключевых слов и кодировала каждый найденный. Как я упомянул тогда, последнее, что мы захотели бы сделать - использовать такую процедуру в местах, где ключевые слова не должны появляться, таких как выражения. Если бы мы сделали это, список ключевых слов просматривался бы для каждого идентификатора, появляющегося в коде. Нехорошо.
Правильней было бы в этом случае просто разделить функции выборки токенов и поиска ключевых слов. Версия 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;
{--------------------------------------------------------------}
РЕШЕНИЯ, РЕШЕНИЯ
Несмотря на относительную простоту обоих сканеров, много идей вошло в них и много решений было сделано. Я хотел бы поделиться этими мыслями с вами сейчас чтобы вы могли принимать свои собственные решения, соответствующие вашему приложению. Сначала заметьте, что обе версии GetName переводят входные символы в верхний регистр. Очевидно, здесь было принято проектное решение, и это один из тех случаев, когда синтаксис языка распределяется по лексическому анализатору. В языке Си регистр символов имеет значение. Для такого языка мы, очевидно, не сможем преобразовывать символы в верхний регистр. Дизайн, который я использую, предполагает язык, подобный Pascal, в котором регистр символов не имеет значения. Для таких языков проще идти вперед и преобразовывать все идентификаторы в верхний регистр в лексическом анализаторе, так что мы не должны волноваться позднее, когда вы сравниваем строки.
Мы могли бы даже пойти дальше и преобразовывать символы в верхний регистр прямо когда они заходят, в GetChar. Этот метод также работает, и я использовал его в прошлом, но он слишком ограничивающий. В частности, он также преобразует символы, которые могут быть частью строк в кавычках, что не является хорошей идеей. Так что если вы вообще собираетесь преобразовывать символы в верхний регистр, GetName подходящее место сделать это.
Обратите внимание, что функция GetNumber в этом сканере возвращает строку, так же как и GetName. Это одна из тех вещей, относительно которых я колебался почти что ежедневно, и последнее колебание было всего десять минут назад. Альтернативный подход и подход, который я использовал много раз в прошлых главах возвращает целочисленный результат.
Оба подхода имеют свои преимущества. Так как мы выбираем число, метод, который немедленно приходит на ум - возвращать его как целое число. Но имейте ввиду, что возможно число будет использоваться в операторе вывода который возвращает его во внешний мир. Кто-то, или мы или код, скрытый внутри оператора вывода, окажется перед необходимостью снова преобразовывать число обратно в строку. Turbo Pascal включает такие подпрограммы преобразования строк, но зачем использовать их если мы не должны? Зачем преобразовывать число из строковой в целочисленную форму только для того, чтобы конвертировать его обратно в генераторе кода, всего несколько операторов спустя?
Кроме того, как вы скоро увидите, нам будет необходимо временное место для хранения токена, который мы извлекли. Если мы обрабатываем числа в их строковой форме, мы можем сохранять значение и переменной и числа в той же самой строке. В противном случае мы должны создать вторую, целочисленную переменную.
С другой стороны, мы обнаружим, что обработка числа как строки фактически уничтожает любую возможность дальнейшей оптимизации. Когда мы доберемся до точки, где мы начнем заниматься генерацией кода, мы столкнемся со случаями, в которых мы выполняем вычисления с константами. Для таких случаев действительно глупо генерировать код, выполняющий арифметику с константами во время выполнения. Гораздо лучше позволить синтаксическому анализатору выполнять арифметику во время компиляции и просто кодировать результат. Чтобы сделать это нам необходимо сохранять константы как целые числа а не строки.
В конце концов обратно к строковому подходу меня склонило энергичное тестирование KISS, плюс напоминание самому себе, что мы тщательно избегаем проблем эффективности кода. Одна из вещей, которые заставляют нашу нехитрую схему синтаксического анализа работать, без сложностей "настоящего" компилятора, это то, что мы прямо сказали что мы не затрагиваем эффективность кода. Это дает нам массу свободы выполнять работу простейшим путем а не эффективнейшим, и эту свободу мы должны стремиться не потерять, не смотря на призывы к эффективности звучащие в наших ушах. В дополнение к тому, что я большой сторонник философии KISS я также защитник "ленивого программирования", что в этом контексте означает не программировать что-либо пока вы не нуждаетесь в этом. Как говорит П. Дж. Плоджер "никогда не откладывайте на завтра то, что вы можете отложить насовсем". Годами писался код, предоставлявший возможности, которые не были никогда использованы. Я научился этому сам на горьком опыте. Так что вывод таков: мы не будем конвертировать в целое число потому, что это нам не нужно.
Для тех из вас, что все еще думает, что нам может быть нужна целочисленная версия (и действительно она может нам понадобиться), вот она:
{--------------------------------------------------------------}
{ Get a Number (integer version) }
function GetNumber: longint;
var
n: longint;
begin
n := 0;
if not IsDigit(Look) then Expected('Integer');
while IsDigit(Look) do begin
n := 10 * n + (Ord(Look) - Ord('0'));
GetChar;
end;
GetNumber := n;
end;
{--------------------------------------------------------------}
Вы могли бы отложить ее, как я предполагаю, на черный день.
СЕМАНТИКА ПАРАМЕТРОВ
До этого мы имели дело с синтаксисом передачи параметров и получили механизм синтаксического анализа для его обработки. Сейчас мы должны рассмотреть семантику, т.е. действия, которые должны быть предприняты когда мы столкнемся с параметрами. Это ставит нас перед вопросом выбора способа передачи параметров.
Существует более чем один способ передачи параметров и способ, которым мы сделаем это, может иметь глубокое влияние на характер языка. Так что это одна из тех областей, где я не могу просто дать вам свое решение. Скорее, было бы важно чтобы мы потратили некоторое время на рассмотрение альтернатив, так чтобы вы могли, если захотите, пойти своим путем.
Есть два основных способа передачи параметров:
·
По значению
· По ссылке (адресу)
Различия лучше всего видны в свете небольшого исторического обзора.
Старые компиляторы Фортрана передавали все параметры по ссылке. Другими словами, фактически передавался адрес параметра. Это означало, что вызываемая подпрограмма была вольна и считывать и изменять этот параметр, что часто и происходило, как будто это была просто глобальная переменная. Это был фактически самый эффективный способ и он был довольно простым, так как тот же самый механизм использовался во всех случаях с одним исключением, которое я кратко затрону.
Хотя имелись и проблемы. Многие люди чувствовали, что этот метод создавал слишком большую связь между вызванной и вызывающей подпрограммой. Фактически, это давало подпрограмме полный доступ ко всем переменным, которые появлялись в списке параметров.
Часто нам не хотелось бы фактически изменять параметр а только использовать его как входные данные. К примеру, мы могли бы передавать счетчик элементов в подпрограмму и хотели бы затем использовать этот счетчик в цикле DO. Во избежание изменения значения в вызываемой программе мы должны были сделать локальную копию входного параметра и оперировать только его копией. Некоторые программисты на Фортране фактически сделали практикой копирование всех параметров, исключая те, которые должны были использоваться как возвращаемые значения. Само собой разумеется, все это копирование победило добрую часть эффективности, связанной с этим методом.
Существовала, однако, еще более коварная проблема, которая была в действительности не просто ошибкой соглашения "передача по ссылке", а плохой сходимостью нескольких решений реализации.
Предположим, у нас есть подпрограмма:
SUBROUTINE FOO(X, Y, N)
где N - какой-то входной счетчик или флажок. Часто нам бы хотелось иметь возможность передавать литерал или даже выражение вместо переменной, как например:
CALL FOO(A, B, J + 1)
Третий параметр не является переменной, и поэтому он не имеет никакого адреса. Самые ранние компиляторы Фортрана не позволяли таких вещей, так что мы должны были прибегать к ухищрениям типа:
K = J + 1
CALL FOO(A, B, K)
Здесь снова требовалось копирование и это бремя ложилось на программистов. Не хорошо.
Более поздние реализации Фортрана избавились от этого, разрешив использовать выражения как параметры. Что они делали - назначали сгенерированную компилятором переменную, сохраняли значение выражения в этой переменной и затем предавали адрес выражения.
Пока все хорошо. Даже если подпрограмма ошибочно изменила значение анонимной переменной, кто об этом знал или кого это заботило? При следующем вызове она в любом случае была бы рассчитана повторно.
Проблема возникла когда кто-то решил сделать вещи более эффективными. Они рассуждали, достаточно справедливо, что наиболее общим видом "выражений" было одиночное целочисленное значение, как в:
CALL FOO(A, B, 4)
Казалось неэффективным подходить к проблеме "вычисления" такого целого числа и сохранять его во временной переменной только для передачи через список параметров. Так как мы в любом случае передавали адрес, казалось имелся большой смысл в том, чтобы просто передавать адрес целочисленного литерала, 4 в примере выше.
Чтобы сделать вопрос более интересным большинство компиляторов тогда и сейчас идентифицирует все литералы и сохраняет их отдельно в "литерном пуле", так что мы должны сохранять только одно значение для каждого уникального литерала. Такая комбинация проектных решений: передача выражений, оптимизация литералов как специальных случаев и использование литерного пула - это то, что вело к бедствию.
Чтобы увидеть, как это работает, вообразите, что мы вызываем подпрограмму FOO как в примере выше, передавая ей литерал 4. Фактически, что передается - это адрес литерала 4, который сохранен в литерном пуле. Этот адрес соответствует формальному параметру K в самой подпрограмме.
Теперь предположите, что без ведома программиста подпрограмма FOO фактически присваивает K значение -7. Неожиданно, литерал 4 в литерном пуле меняется на -7. В дальнейшем, каждое выражение, использующее 4, и каждая подпрограмма, в которую передают 4, будут использовать вместо этого значение -7! Само собой разумеется, что это может привести к несколько причудливому и труднообъяснимому поведению. Все это дало концепции передачи по ссылке плохое имя, хотя, как мы видели, в действительности это была комбинация проектных решений, ведущая к проблеме.
Несмотря на проблему, подход Фортрана имел свои положительные моменты. Главный из них - тот факт, что мы не должны поддерживать множество механизмов. Та же самая схема передачи адреса аргумента работает для всех случаев, включая массивы. Так что размер компилятора может быть сокращен.
Частично из-за этого подводного камня Фортрана и частично просто из-за уменьшенной связи, современные языки типа C, Pascal, Ada и Modula 2 в основном передают скаляры по значению.
Это означает, что значение скаляра копируется в отдельное значение, используемое только для вызова. Так как передаваемое значение - копия, вызываемая процедура может использовать его как локальную переменную и изменять ее любым способом, каким нравится. Значение в вызывающей программе не будет изменено.
Сначала может показаться, что это немного неэффективно из-за необходимости копировать параметр. Но запомните, что мы в любом случае окажемся перед необходимостью выбирать какое-то значение, является ли оно непосредственно параметром или его адресом. Внутри подпрограммы, использование передачи по значению определенно более эффективно, так как мы устраняем один уровень косвенности. Наконец, мы видели раньше, что в Фортране часто было необходимо в любом случае делать копии внутри подпрограммы, так что передача по значению уменьшает количество локальных переменных. В целом, передача по значению лучше.
Исключая одну маленькую деталь: если все параметры передаются по значению, у вызванной процедуры нет никакого способа возвратить результат в вызвавшую! Переданный параметр не изменяется в вызвавшей подпрограмме а только в вызванной. Ясно, что так работы не сделать.
Существуют два эквивалентных ответа на эту проблему. В Паскале Вирт предусмотрел параметры-переменные, которые передаются по ссылке. VAR параметр не что иное как наш старый друг параметр Фортрана с новым именем и расцветкой для маскировки. Вирт аккуратно обходит проблему "изменения литерала" так же как проблему "адрес выражения" с помощью простого средства, разрешая использовать в качестве фактических параметров только переменные. Другими словами, это тоже самое ограничение, которое накладывали самые ранние версии Фортрана.
Си делает ту же самую вещь, но явно. В C все параметры передаются по значению. Однако одним из видов переменных, которые поддерживает С, является указатель. Так передавая указатель по значению, вы в действительности передаете то, на что он указывает по ссылке. В некоторых случаях это работает даже еще лучше, потому что даже хотя вы и можете изменить указываемую переменную на все, что хотите, вы все же не сможете изменить сам указатель. В функции типа strcpy, к примеру, где указатель увеличивается при копировании строки, мы в действительности увеличиваем только копии указателей, так что значение указателей в вызвавшей процедуре все еще остается каким было. Чтобы изменить указатель вы должны передавать указатель на указатель.
Так как мы просто проводим эксперименты, мы рассмотрим и передачу по значению, и передачу по ссылке. Таким образом у нас будет возможность использовать любой из них как нам нужно. Стоит упомянуть, что было бы тяжело использовать здесь подход С, так как указатель это другой тип а типы мы еще не изучали!
СИНТАКСИЧЕСКИЙ АНАЛИЗ
К этому моменту мы распределили все подпрограммы, составляющие наш Cradle, в модули, которые мы можем вытаскивать когда они необходимы. Очевидно, они будут развиваться дальше когда мы снова продолжим процесс восстановления, но большая часть их содержимого и несомненно архитектура, которую они подразумевают, определена. Остается воплотить синтаксис языка в модуль синтаксического анализа. Мы не будем делать многого из этого в этой главе, но я хочу сделать немного просто чтобы оставить вас с хорошим чувством, что мы все еще знаем что делаем. Так что прежде, чем мы продолжим, давай сгенерируем синтаксический анализатор достаточный только для обработки одиночного показателя в выражении. В процессе мы также обнаружим, что по необходимости создали также модуль генератора кода.
Помните самую первую главу этой серии? Мы считывали целочисленное значение, скажем n, и генерировали код для его загрузки в регистр D0 через move:
MOVE #n,D0
Немного погодя, мы повторили этот процесс для переменной,
MOVE X(PC),D0
а затем для показателя, который может быть и константой и переменной. В память о прошлом, давайте повторим этот процесс Определите следующий новый модуль:
{--------------------------------------------------------------}
unit Parser;
{--------------------------------------------------------------}
interface
uses Input, Scanner, Errors, CodeGen;
procedure Factor;
{--------------------------------------------------------------}
implementation
{--------------------------------------------------------------}
{ Parse and Translate a Factor }
procedure Factor;
begin
LoadConstant(GetNumber);
end;
end.
{--------------------------------------------------------------}
Как вы можете видеть, этот модуль вызывает процедуру LoadConstant, которая фактически выполняет вывод ассемблерного кода. Модуль также использует новый модуль CodeGen. Этот шаг представляет последнее главное изменение в нашей архитектуре с более ранних глав: перемещение машинно-зависимого кода в отдельный модуль. Если я дойду до конца, вне CodeGen не будет ни одной строчки кода, которая указывала бы на то, что мы нацелены на процессор 68000. И это то место, которое показывает, что моя цель достижима.
Для тех из вас, кто желает, чтобы я использовал архитектуру 80x86 (или любую другую) вместо 68000, вот мой ответ: просто замените CodeGen на подходящий для вашего ЦПУ.
Пока наш генератор кода содержит только одну процедуру. Вот этот модуль:
{--------------------------------------------------------------}
unit CodeGen;
{--------------------------------------------------------------}
interface
uses Output;
procedure LoadConstant(n: string);
{--------------------------------------------------------------}
implementation
{--------------------------------------------------------------}
{ Load the Primary Register with a Constant }
procedure LoadConstant(n: string);
begin
EmitLn('MOVE #' + n + ',D0' );
end;
end.
{--------------------------------------------------------------}
Скопируйте и откомпилируйте этот модуль и выполните следующую основную программу:
{--------------------------------------------------------------}
program Main;
uses WinCRT, Input, Output, Errors, Scanner, Parser;
begin
Factor;
end.
{--------------------------------------------------------------}
Вот он, сгенерированный код, такой как мы и надеялись.
Теперь, я надеюсь, вы можете начать видеть преимущества модульной архитектуры нашего нового проекта. Здесь мы имеем основную программу длиной всего пять строк. Это все, что нам нужно видеть, если мы не захотим видеть больше. И пока все эти модули сидят здесь терпеливо ожидая когда смогут послужить нам. Наше преимущество в том, что мы имеем простой и короткий код, но мощных союзников. Что остается сделать, это расширить модули до уровня возможностей более ранних глав. Мы сделаем это в следующей главе, но прежде, чем я закончу, давайте закончим синтаксический анализ показателя только для того, чтобы убедить себя, что мы знаем как. Конечная версия CodeGen включает новую процедуру LoadVariable:
{--------------------------------------------------------------}
unit CodeGen;
{--------------------------------------------------------------}
interface
uses Output;
procedure LoadConstant(n: string);
procedure LoadVariable(Name: string);
{--------------------------------------------------------------}
implementation
{--------------------------------------------------------------}
{ Load the Primary Register with a Constant }
procedure LoadConstant(n: string);
begin
EmitLn('MOVE #' + n + ',D0' );
end;
{--------------------------------------------------------------}
{ Load a Variable to the Primary Register }
procedure LoadVariable(Name: string);
begin
EmitLn('MOVE ' + Name + '(PC),D0');
end;
end.
{--------------------------------------------------------------}
Сам модуль Parser не изменяется, но мы имеем более сложную версию процедуры Factor:
{--------------------------------------------------------------}
{ Parse and Translate a Factor }
procedure Factor;
begin
if IsDigit(Look) then
LoadConstant(GetNumber)
else if IsAlpha(Look)then
LoadVariable(GetName)
else
Error('Unrecognized character ' + Look);
end;
{--------------------------------------------------------------}
Теперь, без изменений основной программы, вы должны обнаружить, что программа обрабатывает и переменный и постоянный показатель. К этому моменту наша архитектура почти завершена; у нас есть модули, выполняющие всю грязную работу и достаточно кода в синтаксическом анализаторе и генераторе кода, чтобы продемонстрировать что все работает. Остается расширить модули которые мы определили, в особенности синтаксический анализатор и генератор кода, для поддержки более сложных синтаксических элементов, которые составляют настоящий язык. Так как мы делали это много раз прежде в предыдущих главах, не должно занять у нас много времени вернуться назад к тому месту, где мы были до долгого перерыва. Мы продолжим этот процесс в Главе 16, которая скоро появится. Увидимся.
СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР
Теперь, когда мы прошли через процесс принятия решений, мы можем поспешить с разработкой синтаксического анализатора. Вы делали это со мной несколько раз до этого, поэтому вы знаете последовательность: мы начнем с новой копии Cradle и будем добавлять процедуры одна за другой. Так что давайте сделаем это.
Мы начинаем, как и в случае с арифметикой, работая с булевыми литералами а не с переменными. Это дает нам новый вид входного токена, поэтому нам также нужна новая программа распознавания и новая процедура для чтения экземпляров этого типа токенов. Давайте начнем, определив эти две новые процедуры:
{--------------------------------------------------------------}
{ Recognize a Boolean Literal }
function IsBoolean(c: char): Boolean;
begin
IsBoolean := UpCase(c) in ['T', 'F'];
end;
{--------------------------------------------------------------}
{ Get a Boolean Literal }
function GetBoolean: Boolean;
var c: char;
begin
if not IsBoolean(Look) then Expected('Boolean Literal');
GetBoolean := UpCase(Look) = 'T';
GetChar;
end;
{--------------------------------------------------------------}
Внесите эти подпрограммы в вашу программу. Вы можете протестировать их, добавив в основную программу оператор печати:
WriteLn(GetBoolean);
Откомпилируйте программу и протестируйте ее. Как обычно пока не очень впечатляет но скоро будет.
Теперь, когда мы работали с числовыми данными, мы должны были организовать генерацию кода для загрузки значений в D0. Нам необходимо сделать то же самое и для булевых данных. Обычным способом кодирования булевых переменных является использование 0 для представления FALSE и какого-либо другого значения для TRUE. Многие языки, как например C, используют для его представления целое число 1. Но я предпочитаю FFFF (или -1) потому что побитовое NOT также возвратит логическое NOT. Итак, нам теперь нужно выдать правильный ассемблерный код для загрузки этих значений. Первая засечка на синтаксическом анализаторе булевых выражений (BoolExpression, конечно):
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Expression }
procedure BoolExpression;
begin
if not IsBoolean(Look) then Expected('Boolean Literal');
if GetBoolean then
EmitLn('MOVE #-1,D0')
else
EmitLn('CLR D0');
end;
{---------------------------------------------------------------}
Добавьте эту процедуру в ваш анализатор и вызовите ее из основной программы (заменив оператор печати, который вы только что там поместили). Как вы можете видеть, мы все еще не имеем значительной части синтаксического анализатора, но выходной код начинает выглядеть более реалистичным.
Затем, конечно, мы должны расширить определение булевого выражения. У нас уже есть правило в БНФ:
<b-expression> ::= <b-term> [<orop> <b-term>]*
Я предпочитаю Паскалевскую версию "orop" - OR и XOR. Но так как мы сохраняем одно-символьные токены, я буду кодировать их знаками '|' и '~'. Следующая версия BoolExpression - почти полная копия арифметической процедуры Expression:
{--------------------------------------------------------------}
{ Recognize and Translate a Boolean OR }
procedure BoolOr;
begin
Match('|');
BoolTerm;
EmitLn('OR (SP)+,D0');
end;
{--------------------------------------------------------------}
{ Recognize and Translate an Exclusive Or }
procedure BoolXor;
begin
Match('~');
BoolTerm;
EmitLn('EOR (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Expression }
procedure BoolExpression;
begin
BoolTerm;
while IsOrOp(Look) do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'|': BoolOr;
'~': BoolXor;
end;
end;
end;
{---------------------------------------------------------------}
Обратите внимание на новую процедуру IsOrOp, которая также является копией, на этот раз IsAddOp:
{--------------------------------------------------------------}
{ Recognize a Boolean Orop }
function IsOrop(c: char): Boolean;
begin
IsOrop := c in ['|', '~'];
end;
{--------------------------------------------------------------}
ОК, переименуйте старую версию BoolExpression в BoolTerm, затем наберите код, представленный выше. Откомпилируйте и протестируйте эту версию. К этому моменту выходной код начинает выглядеть довольно хорошим. Конечно, нет большого смысла от булевой алгебры над постоянными значениями, но скоро мы расширим булевы типы, с которыми мы работаем.
Возможно вы уже предположили, какой будет следующий шаг: булевская версия Term.
Переименуйте текущую процедуру BoolTerm в NotFactor, и введите следующую новую версию BoolTerm. Заметьте, что она намного более простая, чем числовая версия, так как здесь нет эквивалента деления.
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Term }
procedure BoolTerm;
begin
NotFactor;
while Look = '&' do begin
EmitLn('MOVE D0,-(SP)');
Match('&');
NotFactor;
EmitLn('AND (SP)+,D0');
end;
end;
{--------------------------------------------------------------}
Теперь мы почти дома. Мы транслируем сложные булевы выражения, хотя только и для постоянных значений. Следующий шаг - учесть NOT. Напишите следующую процедуру:
{--------------------------------------------------------------}
{ Parse and Translate a Boolean Factor with NOT }
procedure NotFactor;
begin
if Look = '!' then begin
Match('!');
BoolFactor;
EmitLn('EOR #-1,D0');
end
else
BoolFactor;
end;
{--------------------------------------------------------------}
И переименуйте предыдущую процедуру в BoolFactor. Теперь испытайте компилятор. К этому времени синтаксический анализатор должен обрабатывать любое булево выражение, которое вы позаботитесь ему подкинуть. Работает? Отлавливает ли он неправильно сформированные выражения?
Если вы следили за тем, что мы делали в синтаксическом анализаторе для математических выражений вы знаете что далее мы расширили определение показателя для включения переменных и круглых скобок. Мы не должны делать это для булевого показателя, потому что об этих маленьких вещах позаботится наш следующий шаг. Необходима только одна дополнительная строка в BoolFactor, чтобы позаботиться об отношениях:
{--------------------------------------------------------------}
{ Parse and Translate a Boolean Factor }
procedure BoolFactor;
begin
if IsBoolean(Look) then
if GetBoolean then
EmitLn('MOVE #-1,D0')
else
EmitLn('CLR D0')
else Relation;
end;
{--------------------------------------------------------------}
Вы могли бы задаться вопросом, когда я собираюсь предоставить булевские переменные и булевские выражения в скобках. Отвечаю: никогда. Помните, ранее мы убрали их из грамматики. Прямо сейчас я собираюсь кодировать грамматику, которую мы уже согласовали. Сам компилятор не может видеть разницы между булевыми переменными или выражениями и арифметическими переменными или выражениями... все это будет обрабатываться в Relation в любом случае.
Конечно, понадобится некоторый код для Relation. Однако, я не чувствую себя комфортно, добавляя еще код, не проверив с начала тот, который мы уже имеем. Так что давайте сейчас просто напишем фиктивную версию Relation, которая ничего не делает за исключением того, что съедает текущий символ и выводит небольшое сообщение:
{---------------------------------------------------------------}
{ Parse and Translate a Relation }
procedure Relation;
begin
WriteLn('<Relation>');
GetChar;
end;
{--------------------------------------------------------------}
ОК, наберите этот код и испытайте его. Все старые дела все еще должны работать... у вас должна быть возможность генерировать код для AND, OR и NOT. Кроме того, если вы наберете любой алфавитный символ, вы должны получить небольшой заменитель <Relation>, где должен быть булев показатель. Вы получили это? Отлично, тогда давайте перейдем к полной версии Relation.
Чтобы получить ее, тем не менее, сначала мы должны положить небольшое основание. Вспомните, что отношение имеет форму:
<relation> ::= | <expression> [<relop> <expression]
Так как у нас появился новый вид операторов, нам также понадобится новая логическая функция для ее распознавания. Эта функция показана ниже. Из-за ограничения в один символ, я придерживаюсь четырех операторов, которые могут быть закодированы такими символами ("не равно" закодировано как "#").
{--------------------------------------------------------------}
{ Recognize a Relop }
function IsRelop(c: char): Boolean;
begin
IsRelop := c in ['=', '#', '<', '>'];
end;
{--------------------------------------------------------------}
Теперь вспомните, что мы используем нуль или -1 в регистре D0 для представления логического значения и также то, что операторы цикла ожидают, что будет установлен соответствующий флаг. При реализации всего этого для 68000 все становится немного сложным.
Так как операторы цикла выполняются только по флажкам, было бы хорошо (а также довольно эффективно) просто установить эти флажки и совсем ничего не загружать в D0. Это было бы прекрасно для циклов и ветвлений, но запомните, что отношения могут быть использованы везде, где могут быть использованы булевы показатели. Мы можем сохранять его результат в булевой переменной. Так как мы не можем знать пока как будет использоваться результат, мы должны учесть оба случая.
Сравнение числовых данных достаточно просто... 68000 имеет команду для этого... но она устанавливает флажки а не значение. Более того, всегда будут устанавливаться те же самые флажки (ноль если равно, и т.д.), в то время, как нам необходим по-разному установленный флажок нуля для каждого различного оператора отношения.
Решение заключается в инструкции Scc процессора 68000, которая устанавливает значение байта в 0000 или FFFF (забавно как это работает!) в зависимости от результата определенного условия. Если мы сделаем байтом результата регистр D0, мы получим необходимое логическое значение.
К сожалению, имеется одно заключительное осложнение: в отличие от почти всех других команд в наборе 68000, Scc не сбрасывает флажки условий в соответствии с сохраняемыми данными. Поэтому мы должны сделать последний шаг, проверить D0 и установить соответствующим образом флажки. Это должно быть похоже на оборот вокруг луны для получения того, что мы хотим: мы сначала выполняем проверку, затем проверяем флажки, чтобы установить данные в D0, затем тестируем D0 чтобы установить флажки снова. Это окольный путь, но это самый простой способ получить правильные флажки и, в конце концов, это всего лишь пара инструкций.
Я мог бы упомянуть здесь, что эта область, по моему мнению, показывает самые большие различия между эффективностью вручную написанного на ассемблере и сгенерированного компилятором кода. Мы уже видели, что мы теряем эффективность при арифметических операциях, хотя позже я планирую показать вам как ее немного улучшить. Мы также видели, что управляющие конструкции сами по себе могут быть реализованы довольно эффективно... обычно очень сложно улучшить код, сгенерированный для IF или WHILE. Но практически каждый компилятор, который я когда-либо видел, генерирует ужасный код, по сравнению с ассемблером, для вычисления булевых функций и особенно отношений. Причина как раз в том, о чем я упомянул выше. Когда я пишу код на ассемблере, я двигаюсь вперед и выполняю проверку наиболее удобным для меня способом, и затем подготавливаю ветвление так чтобы переход был выполнен на нужную ветку. Фактически, я "подстраиваю" каждое ветвление под ситуацию. Компилятор не может сделать этого (практически) и он также не может знать, что нам не нужно сохранять результат проверки как булевскую переменную. Поэтому он должен генерировать код по очень строгим правилам и часто заканчивает сохранением результата как булевой переменной, которая никогда не будет использована для чего-либо.
В любом случае мы теперь готовы рассмотреть код для Relation. Он показан ниже с сопровождающими процедурами:
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Equals" }
procedure Equals;
begin
Match('=');
Expression;
EmitLn('CMP (SP)+,D0');
EmitLn('SEQ D0');
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Not Equals" }
procedure NotEquals;
begin
Match('#');
Expression;
EmitLn('CMP (SP)+,D0');
EmitLn('SNE D0');
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Less Than" }
procedure Less;
begin
Match('<');
Expression;
EmitLn('CMP (SP)+,D0');
EmitLn('SGE D0');
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Greater Than" }
procedure Greater;
begin
Match('>');
Expression;
EmitLn('CMP (SP)+,D0');
EmitLn('SLE D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate a Relation }
procedure Relation;
begin
Expression;
if IsRelop(Look) then begin
EmitLn('MOVE D0,-(SP)');
case Look of
'=': Equals;
'#': NotEquals;
'<': Less;
'>': Greater;
end;
EmitLn('TST D0');
end;
end;
{---------------------------------------------------------------}
Теперь этот вызов Expression выглядит знакомым! Вот где редактор вашей системы оказывается полезным. Мы уже генерировали код для Expression и его близнецов на предыдущих уроках. Теперь вы можете скопировать их в ваш файл. Не забудьте использовать одно-символьную версию. Просто чтобы быть уверенным, я продублировал арифметические процедуры ниже. Если вы наблюдательны, вы также увидите, что я их немного изменил чтобы привести в соответствие с последней версией синтаксиса. Эти изменения не являются необходимыми, так что вы можете предпочесть оставить все как есть до тех пор, пока не будете уверены, что все работает.
{---------------------------------------------------------------}
{ Parse and Translate an Identifier }
procedure Ident;
var Name: char;
begin
Name:= GetName;
if Look = '(' then begin
Match('(');
Match(')');
EmitLn('BSR ' + Name);
end
else
EmitLn('MOVE ' + Name + '(PC),D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate a Math Factor }
procedure Expression; Forward;
procedure Factor;
begin
if Look = '(' then begin
Match('(');
Expression;
Match(')');
end
else if IsAlpha(Look) then
Ident
else
EmitLn('MOVE #' + GetNum + ',D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate the First Math Factor }
procedure SignedFactor;
begin
if Look = '+' then
GetChar;
if Look = '-' then begin
GetChar;
if IsDigit(Look) then
EmitLn('MOVE #-' + GetNum + ',D0')
else begin
Factor;
EmitLn('NEG D0');
end;
end
else Factor;
end;
{--------------------------------------------------------------}
{ Recognize and Translate a Multiply }
procedure Multiply;
begin
Match('*');
Factor;
EmitLn('MULS (SP)+,D0');
end;
{-------------------------------------------------------------}
{ Recognize and Translate a Divide }
procedure Divide;
begin
Match('/');
Factor;
EmitLn('MOVE (SP)+,D1');
EmitLn('EXS.L D0');
EmitLn('DIVS D1,D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate a Math Term }
procedure Term;
begin
SignedFactor;
while Look in ['*', '/'] do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'*': Multiply;
'/': Divide;
end;
end;
end;
{---------------------------------------------------------------}
{ Recognize and Translate an Add }
procedure Add;
begin
Match('+');
Term;
EmitLn('ADD (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Subtract }
procedure Subtract;
begin
Match('-');
Term;
EmitLn('SUB (SP)+,D0');
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
Term;
while IsAddop(Look) do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'+': Add;
'-': Subtract;
end;
end;
end;
{---------------------------------------------------------------}
Теперь вы получили что-то... синтаксический анализатор, который может обрабатывать и арифметику, и булеву алгебру и их комбинации через использование операторов отношений. Я советую вам сохранить копию этого синтаксического анализатора в безопасном месте для будущих обращений, потому что на нашем следующем шаге мы собираемся разделить его.
СИНТАКСИЧЕСКИЙ САХАР
Вся эта дискуссия поднимает вопрос "синтаксического сахара"... конструкций, которые добавлены к языку не потому, что они нужны, но потому, что они заставляют программы выглядеть правильно для программиста. В конце концов, хорошо иметь маленький простой компилятор, но от него было бы мало пользы если бы полученный язык был закодированным или сложным для программирования. На ум приходит язык FORTH. Если мы можем добавить в язык возможности, которые делают программы более легкими для чтения и понимания, и если эти возможности предохраняют программиста от ошибок, тогда мы бы сделали это. Особенно если эти конструкции не добавляют слишком много сложности в язык или его компилятор.
Как пример можно было бы рассмотреть точку с запятой, но существуют множество других, такие как "THEN" в операторе IF, "DO" в операторе WHILE или даже утверждение "PROGRAM" которое я убрал из TINY. Ни один из этих токенов не добавляет много к синтаксису языка... компилятор может выяснить, что происходит и без них. Но некоторые люди чувствуют, что они улучшают читаемость программ и это может быть очень важно.
Существуют две школы мысли на эту тему, которые хорошо представлены двумя из наших наиболее популярных языков C и Pascal.
По мнению минималистов весь подобный сахар должен быть выброшен. Они доказывают, что это загромождает язык и увеличивает число нажатий клавиш, которое должен сделать программист. Возможно более важно, что каждый дополнительный токен или ключевое слово представляет собой ловушку, лежащую в ожидании невнимательного программиста. Если вы не учтете токен, пропустите его или сделаете в нем орфографическую ошибку, компилятор достанет вас. Поэтому эти люди утверждают, что лучший подход - избегать таких вещей. Этот народ предпочитает язык типа C, который имеет минимум ненужных ключевых слов и пунктуации.
Те, кто относятся к другой школе, предпочитают язык Pascal. Они доказывают, что необходимость набрать несколько дополнительных символов - это малая цена за удобочитаемость. В конце концов, люди тоже должны читать программы. Их самый лучший аргумент в том, что каждая такая конструкция является возможностью сообщить компилятору, что вы действительно хотите того, что сказали. Сахарные токены служат в качестве полезных ориентиров, помогающих вам не сбиться с пути..
Различия хорошо представлены этими двум языками. Наиболее часто слышимая претензия к C - что он слишком прощающий. Когда вы делаете ошибку в C, ошибочный код часто является другой допустимой конструкцией C. Так что компилятор просто счастливо продолжает компиляцию и оставляет вам нахождение ошибок в течение отладки. Я предполагаю именно поэтому отладчики так популярны среди C программистов.
С другой стороны, если компилируется программа на Паскале, вы можете быть вполне уверены, что программа будет делать то, что вы ей сказали. Если имеется ошибка во время выполнения, возможно это ошибка разработки.
Самым лучшим примером полезного сахара является непосредственно точка с запятой. Рассмотрите фрагмент кода:
a=1+(2*b+c) b...
Так как нет никакого оператора, соединяющего токен 'b' с остальной частью выражения, компилятор заключит, что выражение заканчивается на ')' а 'b' - это начало нового утверждения. Но предположим, что я просто пропустил предполагаемый оператор и в действительности хотел сказать:
a=1+(2*b+c)*b...
В этом случае компилятор выдаст ошибку, хорошо, но она не будет очень осмысленной, так как он будет ожидать знак '=' после 'b', который в действительности не должен быть там.
Если, наоборот, я вставлю точку с запятой после 'b', тогда не может остаться сомнений где, как я предполагаю, заканчивается утверждение. Синтаксический сахар, т.о., может служить очень полезной цели, предоставляя некоторую дополнительную подстраховку что мы остаемся на правильном пути.
Я нахожусь где-то посередине между этими подходами. Я склоняюсь к преимуществам Паскалевской точки зрения... я был бы очень доволен находить свои ошибки во время компиляции а не во время выполнения. Но я также ненавижу просто бросаться словами без явной причины как в COBOL. Пока что я последовательно выкинул большинство Паскалевского сахара из KISS/TINY. Но я конечно не испытываю сильных чувств к любому способу и я также могу видеть значение разбрасывания небольшого количества сахара только для дополнительной подстраховки, которую он дает. Если вам нравится этот последний подход, такие вещи легко добавить. Только запомните, что как и точка с запятой каждая ложка сахара - это что-то, что может потенциально привести к ошибке компиляции при ее пропуске.
СЛОВО ОБ ОПТИМИЗАЦИИ
Раннее в этой главе я обещал дать несколько подсказок как мы можем повысить качество генерируемого кода. Как я сказал, получение компактного кода не является главной целью этой книги. Но вам нужно, по крайней мере, знать, что мы не зря проводим свое время… что мы действительно можем модифицировать анализатор, для получения лучшего кода не выбрасывая то, что мы уже сделали к настоящему времени. Обычно небольшая оптимизация не слишком трудна… просто в синтаксический анализатор вставляется дополнительный код.
Существуют два основных метода, которые мы можем использовать:
· Попытаться исправить код после того, как он сгенерирован.
Это понятие «щелевой» оптимизации. Основная идея в том, что известно какие комбинации инструкций компилятор собирается произвести и также известно которые из них «плохие» (такие как код для числа -1). Итак, все что нужно сделать – просканировать полученный код, найти такие комбинации инструкций и заменить их на более «хорошие». Это вид макрорасширений наоборот и прямой пример метода сопоставления с образцом. Единственная сложность в том, что может существовать множество таких комбинаций. Этот метод называется «щелевой» оптимизацией просто потому, что оптимизатор работает с маленькой группой инструкций. «Щелевая» оптимизация может драматически влиять на качество кода и не требует при этом больших изменений в структуре компилятора. Но все же за это приходится платить скоростью, размером и сложностью компилятора. Поиск всех комбинаций требует проверки множества условий, каждая из которых является источником ошибки. И, естественно, это требует много времени.
В классической реализации «щелевого» оптимизатора, оптимизация выполняется как второй проход компилятора. Выходной код записывается на диск и затем оптимизатор считывает и обрабатывает этот файл снова. Фактически, оптимизатор может быть даже отдельной от компилятора программой. Так как оптимизатор только обрабатывает код в маленьком «окне» инструкций (отсюда и название), лучшей реализацией было бы буферизировать несколько срок выходного кода и сканировать буфер каждый раз после EmitLn.
· Попытаться сразу генерировать лучший код.
В этом методе выполняется проверка дополнительных условий перед выводом кода. Как тривиальный пример, мы должны были бы идентифицировать нуль и выдать CLR вместо загрузки, или даже совсем ничего не делать, как в случае с прибавлением нуля, например. Конкретней, если мы решили распознавать унарный минус в процедуре Factor вместо Expression, то мы должны обрабатывать –1 как обычную константу, а не генерировать ее из положительных. Ни одна из этих вещей не является слишком сложной для реализации… просто они требуют включения дополнительных проверок в код, поэтому я не включил их в программу. Как только мы дойдем до получения работающего компилятора, генерирующего полезный выполнимый код, мы всегда сможем вернуться и доработать программу для получения более компактного кода. Именно поэтому в мире существует «Версия 2.0».
Существует еще один, достойный упоминания, способ оптимизации, обещающий достаточно компактный код без излишних хлопот. Это мое «изобретение», в том смысле, что я нигде не видел публикаций по этому методу, хотя я и не питаю иллюзий что это придумано мной.
Способ заключается в том, чтобы избежать частого использования стека, лучше используя регистры центрального процессора. Вспомните, когда мы выполняли только сложение и вычитание, то мы использовали регистры D0 и D1 а не стек? Это работало, потому для этих двух операций стек никогда не использовал более чем две ячейки.
Хорошо, процессор 68000 имеет восемь регистров данных. Почему бы не использовать их как стек? В любой момент своей работы синтаксический анализатор «знает» как много элементов в стеке, поэтому он может правильно ими манипулировать. Мы можем определить частный указатель стека, который следит, на каком уровне мы находимся и адресует соответствующий регистр. Процедура Factor, например, должна загружать данные не в регистр D0, а в тот, который является текущей вершиной стека.
Что мы получаем, заменяя стек в RAM на локальный стек созданный из регистров. Для большинства выражений уровень стека никогда не превысит восьми, поэтому мы получаем достаточно хороший код. Конечно, мы должны предусмотреть те случаи, когда уровень стека превысит восемь, но это также не проблема. Мы просто позволим стеку перетекать в стек ЦПУ. Для уровней выше восьми код не хуже, чем тот, который мы генерируем сейчас, а для уровней ниже восьми он значительно лучше.
Я реализовал этот метод, просто для того, чтобы удостовериться в том, что он работает перед тем, как представить его вам. Он работает. На практике вы не можете в действительности использовать все восемь уровней... вам, как минимум, нужен один свободный регистр для изменения порядка операндов при делении. Для выражений, включающих вызовы функций, также необходимо зарезервировать регистр. Но все равно, существует возможность улучшения размера кода для большинства выражений.
Итак, вы видите, что получение лучшего кода не настолько трудно, но это усложняет наш транслятор... это сложность, без которой мы можем сейчас обойтись. По этой причине, я очень советую продолжать игнорировать вопросы эффективности в этой книге, усвоив, что мы действительно можем повысить качество кода, не выбрасывая того, что уже сделано.
В следующей главе я покажу вам как работать с переменными и вызовами функций. Я также покажу вам как легко добавить поддержку много символьных токенов и пробелов.
СНОВА ОПЕРАТОРЫ ОТНОШЕНИЙ
У нас осталось последнее одно-символьное ограничение - ограничение операторов отношений. Некоторые из операторов отношений действительно состоят из одиночных символов, но другие требуют двух. Это '<=' и '>='. Я также предпочитаю Паскалевское '<>' для "не равно" вместо '#'.
Как вы помните, в главе 7 я указал, что стандартный способ работы с операторами отношений - включить их в список ключевых слов и позволить лексическому анализатору отыскивать их. Но, опять, это требует выполнение полного анализа выражения, тогда как до этого мы у нас была возможность ограничить использование сканера началом утверждения.
Я упомянул тогда, что мы все же можем избежать неприятностей с этим, так как много символьных операторов отношений немного и они ограничены в применении. Было бы легко обрабатывать их просто как специальные случаи и поддерживать их специальным способом.
Требуемые изменения влияют только на подпрограммы генерации кода и процедуры Relation и ее друзей. С начала, нам понадобятся еще две подпрограммы генерации кода:
{---------------------------------------------------------------}
{ Set D0 If Compare was <= }
procedure SetLessOrEqual;
begin
EmitLn('SGE D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was >= }
procedure SetGreaterOrEqual;
begin
EmitLn('SLE D0');
EmitLn('EXT D0');
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;
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;
{---------------------------------------------------------------}
Это все, что требуется. Теперь вы можете обрабатывать все операторы отношений. Попробуйте.
СОВСЕМ КАК КЛАССИЧЕСКИЙ?
Прежде чем мы продолжим, однако, я думаю что должен разъяснить связи между модулями и функциональные возможности этих модулей. Те из вас, кто знаком с теорией компиляции как обучавшиеся в университетах, конечно распознают имена Scanner, Parser и CodeGen, все из которых являются компонентами классической реализации компилятора. Вы можете думать, что я отказался от своих обязательств по отношению к философии KISS и отдрейфовал к более стандартной архитектуре чем мы имели. Более пристальный взгляд, однако, должен убедить вас, что хотя имена схожи, функциональность совершенно различна.
Вместе, сканер и парсер классической реализации составляют так называемый "front end", а генератор кода "back end". Подпрограммы "front end" обрабатывают языко зависимые, связанные с синтаксисом аспекты исходного языка, в то время как генератор кода, или "back end", работает с зависимыми от целевой машины частями проблемы. В классических компиляторах два конца (ends) сообщаются через файл инструкций, написанный на промежуточном языке (IL).
Как правило, классический сканер это одиночная процедура, оперирующая как сопроцедура с синтаксическим анализатором. Она "токенизирует" исходный файл, считывая его символ за символом, распознавая элементы языка, транслируя их в токены и передавая их синтаксическому анализатору. Вы можете думать о синтаксическом анализаторе как об абстрактной машине, выполняющей "op кода", которыми являются токены. Точно также, синтаксический анализатор генерирует "op кода" второй абстрактной машины, которая механизирует IL. Как правило, IL файл записывается на диск синтаксическим анализатором и считывается снова генератором кода.
Наша организация совершенно другая. Мы не имеем лексического анализатора в классическом смысле; наш модуль Scanner, хотя и имеет схожее имя, не является одиночной процедурой или сопроцедурой, а просто набором раздельных подпрограмм, которые вызываются синтаксическим анализатором когда необходимо.
Аналогично, классический генератор кода, "back end", в своем роде тоже транслятор, считывающий "исходный" IL файл и выдающий объектный файл. Наш генератор кода не работает таким способом. В нашем компиляторе нет никакого промежуточного языка; каждая конструкция в синтаксисе исходного языка преобразуется в ассемблер как только она распознана синтаксическим анализатором. Подобно Scanner, модуль CodeGen состоит из индивидуальных процедур, которые вызываются синтаксическим анализатором когда необходимо.
Философия "кодируй как только найдешь" не может производить самый эффективный код в мире - например, мы не обеспечили (пока!) удобное место для оптимизатора - но она несомненно упрощает компилятор, не правда ли?
И этот наблюдение заставляет меня повторить снова то, как нам удавалось сводить функции компилятора к таким сравнительно простым условиям. Я набрался красноречивости на эту тему в прошлых главах, поэтому здесь я не буду слишком ее трогать. Однако, из-за времени, прошедшего с этих последних монологов, я надеюсь что вы предоставите мне совсем немного времени напомнить себе, так же как и вам, как мы попали сюда. Мы дошли до этого применяя несколько принципов, которые создатели коммерческих компилятором редко имеют роскошь использовать. Вот они:
· Философия KISS - никогда не делай сложные вещи без причины.
· Ленивое кодирование - Никогда не откладывай на завтра то, что можешь отложить навсегда. (П. Дж. Плоджер).
· Скептицизм - упрямо отказывайтесь делать что-либо только потому, что это всегда делалось таким способом.
· Принятие неэффективного кода.
· Отклонение произвольных ограничений.
Когда я сделал обзор истории конструирования компиляторов, я узнал, что практически каждый промышленный компилятор в истории страдал из-за предналоженных условий, которые сильно влияли на его дизайн. Первоначальный компилятор Fortran Джона Бэкуса должен был конкурировать с ассемблером и следовательно был вынужден производить чрезвычайно эффективный код. Компиляторы IBM для мини ЭВМ 70-х должны были выполняться в очень небольших объемах ОЗУ тогда доступных - таких небольших как 4k. Ранние компиляторы Ada должны были компилировать себя. Бринч Хансен решил, что его компилятор Паскаля, разработанный для IBM PC должен выполняться на 64k машинах. Компиляторы, разработанные на курсах Computer Science, должны были компилировать широкий диапазон языков и следовательно требовали LALR синтаксических анализаторов.
В каждом из этих случаев эти предвзятые ограничения буквально доминировали над проектом компилятора.
Хороший пример - компилятор Бринч Хансена, описанный в его превосходной книге "Brinch Hansen on Pascal Compilers" (строго рекомендую). Хотя его компилятор один из самых ясных и незатемненных реализаций компилятора, что я видел, одно решение, компилировать большие файлы в небольшом ОЗУ, полностью управляло дизайном и он закончил не на одном а многих промежуточных файлах, как и управляющими ими программах для их записи и считывания.
Временами, архитектуры, возникающие из таких решений, находили свое место в учениях компьютерной науки и принимались на веру. По мнению одного человека, пришло время чтобы они были критически пересмотрены. Условия, требования, среды, которые вели к классическим архитектурам не такие же, какие мы имеем сейчас. Нет никакой причины полагать, что решения тоже должны быть те же самыми.
В этой обучающей серии мы следовали по шагам таких пионеров в мире маленьких компиляторов для PC как Леор Золман, Рон Каин и Джеймс Хендрих, тех кто не знал достаточно теорию компиляции чтобы знать, что они "не могли делать это таким способом". Мы решительно отказались принимать произвольные ограничения, а скорее делали так, как было проще В результате мы развили архитектуру, которая, хотя и совершенно отлична от классической, делает работу простым и прямым способом.
Я закончу эти философствования обзором понятия промежуточного языка. Хотя я отметил перед этим, что мы не имеем его в нашем компиляторе, это не совсем точно; у нас он есть, или по крайней мере мы развиваем его, в том смысле, что мы определяем функции генерации кода для вызова из парсера. В сущности, каждый вызов процедуры генерации кода можно рассматривать как инструкцию на промежуточном языке. Если мы когда либо найдем необходимым формализировать промежуточный язык, вот способ, которым бы мы сделали это: выдать кода из синтаксического анализатора, представляющие собой вызовы процедур генератора кода, а затем обработать каждый код вызывая эти процедуры в отдельном проходе, реализованном в "back end". Откровенно говоря, я не вижу, что мы когда либо найдем потребность в таком подходе, но это связь, если вы решите следовать ему, между классическим и текущим подходами.
СПИСКИ, ЗАПЯТЫЕ И КОМАНДНЫЕ СТРОКИ.
Прежде чем возвратиться к основной цели нашего обучения, я хотел бы немного выступить.
Сколько раз вы работали с программой или операционной системой, которая имела жесткие правила того, как вы должны разделять элементы в списке? (Попробую, последний раз вы использовали MS DOS!). Некоторые программы требуют пробелов как разделителей, некоторые требуют запятые. Хуже всего, что некоторые требуют и того и другого в разных местах. Большинство довольно неумолимы к нарушениям их правил.
Я думаю, это непростительно. Слишком просто написать синтаксически анализатор, который поддерживает и пробелы и запятые гибким способом. Рассмотрите следующую процедуру:
{--------------------------------------------------------------}
{ Skip Over a Comma }
procedure SkipComma;
begin
SkipWhite;
if Look = ',' then begin
GetChar;
SkipWhite;
end;
end;
{--------------------------------------------------------------}
Эта процедура из восьми строк пропустит разделитель, состоящий из любого числа (включая ноль) пробелов, с нулем или одной запятой, вложенной в строку.
Временно измените вызов SkipWhite в Scan на вызов SkipComma и попробуйте ввести какие-нибудь списки. Хорошо работает, да? Разве вы не хотите, чтобы больше создателей программ знало о SkipComma?
К слову сказать, я обнаружил, что добавление эквивалента SkipComma в мою программу на ассемблере для Z80 заняло всего шесть дополнительных байт кода. Даже на 64K машинах это не слишком большая цена за дружелюбие к пользователю.
Я думаю вы можете видеть к чему я клоню. Даже если вы в своей жизни не написали ни одной строчки кода для компилятора, в каждой программе существуют места, где вы можете использовать понятие синтаксического анализа. Любая программа, которая обрабатывает командные строки, нуждается в нем. Фактически, если вы подумаете немного об этом, вы придете к заключению, что всякий раз, когда вы пишете программу, обрабатывающую ввод пользователя, вы определяете язык. Люди общаются с помощью языков и неявный синтаксис в вашей программе определяет этот язык. Настоящий вопрос: вы собираетесь определять его преднамеренно и явно, или просто позволите существовать независимо от того, как программа завершает синтаксический анализ?
Я утверждаю, что у вас будет лучший, более дружественный интерфейс если вы потратите время на то, чтобы определить синтаксис явно. Запишите синтаксические уравнения или нарисуйте "railroad-track" диаграммы и закодируйте синтаксический анализатор используя методы, которые я показал вам здесь. Вы получите более хорошую программу и ее будет проще писать, в придачу.
ССЫЛКИ
1. Crenshaw, J.W., "Object-Oriented Design of Assemblers and Compilers," Proc. Software Development '91 Conference, Miller Freeman, San Francisco, CA, February 1991, pp. 143-155.
2. Crenshaw, J.W., "A Perfect Marriage," Computer Language, Volume 8, #6, June 1991, pp. 44-55.
3. Crenshaw, J.W., "Syntax-Driven Object-Oriented Design," Proc. 1991 Embedded Systems Conference, Miller Freeman, San Francisco, CA, September 1991, pp. 45-60.
СТАНОВИТСЯ ИНТЕРЕСНЕЙ
Хорошо, сейчас мы имеем довольно хороший лексический анализатор, который разбивает входной поток на лексемы. Мы могли бы использовать его как есть и иметь полезный компилятор. Но есть некоторые другие аспекты лексического анализа, которые мы должны охватить.
Особенно следует рассмотреть (вздрогните) эффективность. Помните, когда мы работали с одно-символьными токенами, каждой проверкой было сравнение одного символа 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;
{--------------------------------------------------------------}
СТРУКТУРА ПАСКАЛЯ
Большинство книг по Pascal включают БНФ определение языка. Вот несколько первых строк одного из них:
<program> ::= <program-header> <block> '.'
<program-header> ::= PROGRAM <ident>
<block> ::= <declarations> <statements>
Мы можем написать подпрограммы распознавания для работы с каждым из этих элементов подобно тому, как мы делали это прежде. Для каждого из них мы будем использовать знакомые нам одно-символьные токены, затем понемногу расширяя их. Давайте начнем с первого распознавателя: непосредственно программы.
Для ее трансляции мы начнем с новой копии Cradle. Так как мы возвращаемся к одно-символьным именам мы будем просто использовать "p" для обозначения "program".
К новой копии Cradle добавьте следующий код и вставьте обращение к нему из основной программы:
{--------------------------------------------------------------}
{ Parse and Translate A Program }
procedure Prog;
var Name: char;
begin
Match('p'); { Handles program header part }
Name := GetName;
Prolog(Name);
Match('.');
Epilog(Name);
end;
{--------------------------------------------------------------}
Процедуры Prolog и Epilog выполняют все, что необходимо для связи программы с операционной системой так чтобы она могла выполняться как программа. Само собой разумеется, эта часть будет очень ОС-зависима. Помните, что я выдаю код для 68000, работающий под ОС, которую я использую - SK*DOS. Я понимаю, что большинство из вас использует PC и вы предпочли бы увидеть что-нибудь другое, но я слишком далеко зашел, чтобы что-то сейчас менять!
В любом случае, SK*DOS особенно простая для общения операционная система. Вот код для Prolog и Epilog:
{--------------------------------------------------------------}
{ Write the Prolog }
procedure Prolog;
begin
EmitLn('WARMST EQU $A01E');
end;
{--------------------------------------------------------------}
{ Write the Epilog }
procedure Epilog(Name: char);
begin
EmitLn('DC WARMST');
EmitLn('END ' + Name);
end;
{--------------------------------------------------------------}
Как обычно добавьте этот код и испытайте "компилятор". В настоящее время существует только одна допустимая входная последовательность:
px. (где х - это любая одиночная буква, имя программы).
Хорошо, как обычно наша первая попытка не очень впечатляет, но я уверен к настоящему времени вы знаете, что дальше станет интересней. Есть одна важная вещь, которую следует отметить: на выходе получается работающая, законченная и выполнимая программа (по крайней мере после того, как она будет ассемблирована).
Это очень важно. Приятная особенность нисходящего метода состоит в том, что на любом этапе вы можете компилировать подмножество завершенного языка и получить программу, которая будет работать на конечной машине. Отсюда, затем, нам необходимо только добавлять возможности, расширяя конструкции языка. Это очень похоже на то, что мы уже делали, за исключением того, что мы подходили к этому с другого конца.
СТРУКТУРА СИ
Язык C совсем другой вопрос, как вы увидите. Книги по C редко включают БНФ определения языка. Возможно дело в том, что этот язык очень сложен для описания в БНФ.
Одна из причин что я показываю вам сейчас эти структуры в том что я могу впечатлить вас двумя фактами:
1. Определение языка управляет структурой компилятора. Что работает для одного языка может быть бедствием для другого. Это очень плохая идея попытаться принудительно встроить данную структуру в компилятор. Скорее вы должны позволить БНФ управлять структурой, как мы делали здесь.
2. Язык, для которого сложно написать БНФ также будет возможно сложен для написания компилятора. Си - популярный язык и он имеет репутацию как позволяющий сделать практически все, что возможно. Несмотря на успех Small С, С является непростым для анализа языком.
Программа на C имеет меньше структур, чем ее аналог на Pascal. На верхнем уровне все в C является статическим объявлением или данных или функций. Мы можем зафиксировать эту мысль так:
<program> ::= ( <global declaration> )*
<global declaration> ::= <data declaration> | <function>
В Small C функции могут иметь только тип по умолчанию int, который не объявлен. Это делает входную программу легкой для синтаксического анализа: первым токеном является или "int", "char" или имя функции. В Small C команды препроцессора также обрабатываются компилятором соответствующе, так что синтаксис становится:
<global declaration> ::= '#' <preprocessor command> |
'int' <data list> |
'char' <data list> |
<ident> <function body> |
Хотя мы в действительности больше заинтересованы здесь в полном C , я покажу вам код, соответствующий структуре верхнего уровня Small C.
{--------------------------------------------------------------}
{ Parse and Translate A Program }
procedure Prog;
begin
while Look <> ^Z do begin
case Look of
'#': PreProc;
'i': IntDecl;
'c': CharDecl;
else DoFunction(Int);
end;
end;
end;
{--------------------------------------------------------------}
Обратите внимание, что я должен был использовать ^Z чтобы указать на конец исходного кода. C не имеет ключевого слова типа END или "." для индикации конца программы.
С полным Си все не так просто. Проблема возникает потому, что в полном Си функции могут также иметь типы. Так что когда компилятор видит ключевое слово типа "int" он все еще не знает ожидать ли объявления данных или определение функции. Дела становятся более сложными так как следующим токеном может быть не имя... он может начинаться с "*" или "(" или комбинаций этих двух.
Точнее говоря, БНФ для полного Си начинается с:
<program> ::= ( <top-level decl> )*
<top-level decl> ::= <function def> | <data decl>
<data decl> ::= [<class>] <type> <decl-list>
<function def> ::= [<class>] [<type>] <function decl>
Теперь вы можете увидеть проблему: первые две части объявлений для данных и функций могут быть одинаковыми. Из-за неоднозначности в этой грамматике выше, она является неподходящей для рекурсивного синтаксического анализатора. Можем ли мы преобразовать ее в одну из подходящих? Да, с небольшой работой. Предположим мы запишем ее таким образом:
<top-level decl> ::= [<class>] <decl>
<decl> ::= <type> <typed decl> | <function decl>
<typed decl> ::= <data list> | <function decl>
Мы можем написать подпрограмму синтаксического анализа для определений классов и типов и позволять им отложить их сведения и продолжать выполнение даже не зная обрабатывается ли функция или объявление данных.
Для начала, наберите следующую версию основной программы:
{--------------------------------------------------------------}
{ Main Program }
begin
Init;
while Look <> ^Z do begin
GetClass;
GetType;
TopDecl;
end;
end.
{--------------------------------------------------------------}
На первый раз просто сделайте три процедуры-заглушки которые ничего не делают, а только вызывают GetChar.
Работает ли эта программа? Хорошо, было бы трудно не сделать это, так как мы в действительности не требовали от нее какой-либо работы. Уже говорилось, что компилятор Си примет практически все без отказа. Несомненно это правда для этого компилятора, потому что в действительности все, что он делает, это съедает входные символы до тех пор, пока не найдет ^Z.
Затем давайте заставим GetClass делать что-нибудь стоящее. Объявите глобальную переменную
var Class: char;
и измените GetClass
{--------------------------------------------------------------}
{ Get a Storage Class Specifier }
Procedure GetClass;
begin
if Look in ['a', 'x', 's'] then begin
Class := Look;
GetChar;
end
else Class := 'a';
end;
{--------------------------------------------------------------}
Здесь я использовал три одиночных символа для представления трех классов памяти "auto", "extern" и "static". Это не единственные три возможных класса... есть также "register" и "typedef", но это должно дать вам представление. Заметьте, что класс по умолчанию "auto".
Мы можем сделать подобную вещь для типов. Введите следующую процедуру:
{--------------------------------------------------------------}
{ Get a Type Specifier }
procedure GetType;
begin
Typ := ' ';
if Look = 'u' then begin
Sign := 'u';
Typ := 'i';
GetChar;
end
else Sign := 's';
if Look in ['i', 'l', 'c'] then begin
Typ := Look;
GetChar;
end;
end;
{--------------------------------------------------------------}
Обратите внимание, что вы должны добавить еще две глобальные переменные Sign и Typ.
С этими двумя процедурами компилятор будет обрабатывать определение классов и типов и сохранять их результаты. Мы можем сейчас обрабатывать остальные объявления.
Мы еще ни коим образом не выбрались из леса, потому что все еще существуют много сложностей только в определении типов до того, как мы дойдем даже до фактических данных или имен функций. Давайте притворимся на мгновение, что мы прошли все эти заслоны и следующим во входном потоке является имя. Если имя сопровождается левой скобкой, то мы имеем объявление функции. Если нет, то мы имеем по крайней мере один элемент данных, и возможно список, каждый элемент которого может иметь инициализатор.
Вставьте следующую версию TopDecl:
{--------------------------------------------------------------}
{ Process a Top-Level Declaration }
procedure TopDecl;
var Name: char;
begin
Name := Getname;
if Look = '(' then
DoFunc(Name)
else
DoData(Name);
end;
{--------------------------------------------------------------}
(Заметьте, что так как мы уже прочитали имя, мы должны передать его соответствующей подпрограмме.)
Наконец, добавьте две процедуры DoFunc и DoData:
{--------------------------------------------------------------}
{ Process a Function Definition }
procedure DoFunc(n: char);
begin
Match('(');
Match(')');
Match('{');
Match('}');
if Typ = ' ' then Typ := 'i';
Writeln(Class, Sign, Typ, ' function ', n);
end;
{--------------------------------------------------------------}
{ Process a Data Declaration }
procedure DoData(n: char);
begin
if Typ = ' ' then Expected('Type declaration');
Writeln(Class, Sign, Typ, ' data ', n);
while Look = ',' do begin
Match(',');
n := GetName;
WriteLn(Class, Sign, Typ, ' data ', n);
end;
Match(';');
end;
{--------------------------------------------------------------}
Так как мы еще далеки от получения выполнимого кода, я решил чтобы эти две подпрограммы только сообщали нам, что они нашли.
Протестируйте эту программу. Для объявления данных дайте список, разделенный запятыми. Мы не можем пока еще обрабатывать инициализаторы. Мы также не можем обрабатывать списки параметров функций но символы "(){}" должны быть.
Мы все еще очень далеко от того, чтобы иметь компилятор C, но то что у нас есть обрабатывает правильные виды входных данных и распознает и хорошие и плохие входных данные. В процессе этого естественная структура компилятора начинает принимать форму.
Можем ли мы продолжать пока не получим что-то, что действует более похоже на компилятор. Конечно мы можем. Должны ли мы? Это другой вопрос. Я не знаю как вы, но у меня начинает кружиться голова, а мы все еще далеки от того, чтобы даже получить что-то кроме объявления данных.
К этому моменту, я думаю, вы можете видеть как структура компилятора развивается из определения языка. Структуры, которые мы увидели для наших двух примеров, Pascal и C, отличаются как день и ночь. Pascal был разработан, по крайней мере частично, чтобы быть легким для синтаксического анализа и это отразилось в компиляторе. Вообще, Pascal более структурирован и мы имеем более конкретные идеи какие виды конструкций ожидать в любой точке. В C наоборот, программа по существу является списком объявлений завершаемых только концом файла.
Мы могли бы развивать обе эти структуры намного дальше, но помните, что наша цель здесь не в том, чтобы построить компилятор C или Pascal, а скорее изучать компиляторы вообще. Для тех из вас, кто хотят иметь дело с Pascal или C, я надеюсь, что дал вам достаточно начал чтобы вы могли взять их отсюда (хотя вам скоро понадобятся некоторые вещи, которые мы еще не охватили здесь, такие как типы и вызовы процедур). Остальные будьте со мной в следующей главе. Там я проведу вас через разработку законченного компилятора для TINY, подмножества KISS.
Увидимся.
ТАБЛИЦА ИДЕНТИФИКАТОРОВ
Существует одна проблема с компилятором в его текущем состоянии: он ничего не делает для сохранения переменной когда мы ее объявляем. Так что компилятор совершенно спокойно распределит память для нескольких переменных с тем же самым именем. Вы можете легко убедиться в этом набрав строку типа
pvavavabe.
Здесь мы объявили переменную A три раза. Как вы можете видеть, компилятор бодро принимает это и генерирует три идентичных метки. Не хорошо.
Позднее, когда мы начнем ссылаться на переменные, компилятор также будет позволять нам ссылаться на переменные, которые не существуют. Ассемблер отловит обе эти ошибки, но это совсем не кажется дружественным поведением - передавать такую ошибку ассемблеру. Компилятор должен отлавливать такие вещи на уровне исходного языка.
Так что даже притом, что нам не нужна таблица идентификаторов для записи типов данных, мы должны установить ее только для того, чтобы проверять эти два условия. Так как пока мы все еще ограничены одно-символьными именами переменных таблица идентификаторов может быть тривиальной. Чтобы предусмотреть ее сначала добавьте следующее объявление в начало вашей программы:
var ST: array['A'..'Z'] of char;
и вставьте следующую функцию:
{--------------------------------------------------------------}
{ Look for Symbol in Table }
function InTable(n: char): Boolean;
begin
InTable := ST[n] <> ' ';
end;
{--------------------------------------------------------------}
Нам также необходимо инициализировать таблицу пробелами. Следующие строки в Init сделают эту работу:
var i: char;
begin
for i := 'A' to 'Z' do
ST[i] := ' ';
...
Наконец, вставьте следующие две строки в начало Alloc:
if InTable(N) then Abort('Duplicate Variable Name ' + N);
ST[N] := 'v';
Это должно все решить. Теперь компилятор будет отлавливать двойные объявления. Позднее мы также сможем использовать InTable при генерации ссылок на переменные.
Если вы осторожный тип (как я), вам возможно захотелось бы начать с тестовой программы, которая ничего не делает а просто инициализирует таблицу и затем создает ее дамп. Только для того, чтобы быть уверенным, что все мы находимся на одной волне, ниже я воспроизвожу всю программу, дополненную новыми процедурами. Заметьте, что эта версия включает поддержку пробелов:
{--------------------------------------------------------------}
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';
На этот раз, когда вы запустите программу, вы должны получить распечатку, показывающую, что таблица идентификаторов работает правильно.
ТЕРМЫ И ВЫРАЖЕНИЯ
Я уверен вы знаете, что будет дальше. Мы должны еще раз создать остальные процедуры, которые реализуют синтаксический анализ выражений по методу рекурсивного спуска. Все мы знаем, что иерархия процедур для арифметических выражений такая:
выражение
терм
показатель
Однако сейчас давайте продолжим разработку по шагам и рассмотрим выражения только с аддитивными термами. Код для реализации выражений, включающих возможно первый терм со знаком, показан ниже:
{--------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
SignedFactor;
while IsAddop(Look) do
case Look of
'+': Add;
'-': Subtract;
end;
end;
{--------------------------------------------------------------}
Эта процедура вызывает две другие процедуры для обработки операций:
{--------------------------------------------------------------}
{ Parse and Translate an Addition Operation }
procedure Add;
begin
Match('+');
Push;
Factor;
PopAdd;
end;
{--------------------------------------------------------------}
{ Parse and Translate a Subtraction Operation }
procedure Subtract;
begin
Match('-');
Push;
Factor;
PopSub;
end;
{--------------------------------------------------------------}
Эти три процедуры Push, PopAdd и PopSub - новые подпрограммы генерации кода. Как подразумевает имя, процедура Push генерирует код для помещения основного регистра (D0 в нашей реализации для 68000) в стек. PopAdd и PopSub выталкивают вершину стека и прибавляют или вычитают ее из основного регистра. Код показан ниже:
{--------------------------------------------------------------}
{ Push Primary to Stack }
procedure Push;
begin
EmitLn('MOVE D0,-(SP)');
end;
{--------------------------------------------------------------}
{ Add TOS to Primary }
procedure PopAdd;
begin
EmitLn('ADD (SP)+,D0');
end;
{--------------------------------------------------------------}
{ Subtract TOS from Primary }
procedure PopSub;
begin
EmitLn('SUB (SP)+,D0');
Negate;
end;
{--------------------------------------------------------------}
Добавьте эти подпрограммы в Parser и CodeGen и измените основную программу для вызова Expression. Вуа ля!
Следующий шаг, конечно, это добавление возможности работы с мульпликативными термами. С этой целью мы добавим процедуру Term и процедуры генерации кода PopMul и PopDiv. Эти процедуры генерации кода показаны ниже:
{--------------------------------------------------------------}
{ Multiply TOS by Primary }
procedure PopMul;
begin
EmitLn('MULS (SP)+,D0');
end;
{--------------------------------------------------------------}
{ Divide Primary by TOS }
procedure PopDiv;
begin
EmitLn('MOVE (SP)+,D7');
EmitLn('EXT.L D7');
EmitLn('DIVS D0,D7');
EmitLn('MOVE D7,D0');
end;
{--------------------------------------------------------------}
Я должен признать, что подпрограмма деления немного перегружена, но с этим ничего нельзя поделать. К сожалению, хотя процессор 68000 позволяет выполнять деление используя вершину стека (TOS), он требует аргументы в неправильном порядке, подобно тому как для вычитания. Поэтому наше единственное спасение в том чтобы вытолкнуть стек в рабочий регистр (D7), выполнить там деление, и затем поместить результат обратно в наш основной регистр D0. Обратите внимание на использование знаковых операций умножения и деления. Этим неявно подразумевается что все наши переменные будут 16-разрядными целыми числами со знаком. Это решение затронет нас позднее, когда мы начнем рассматривать множественные типы данных, преобразования типов и т.п.
Наша процедура Term это практически аналог Expression и выглядит так:
{--------------------------------------------------------------}
{ Parse and Translate a Term }
procedure Term;
begin
Factor;
while IsMulop(Look) do
case Look of
'*': Multiply;
'/': Divide;
end;
end;
{--------------------------------------------------------------}
Наш следующий шаг - изменение некоторых имен. SignedFactor теперь становится SignedTerm а вызовы Factor в Expression, Add, Subtract и SignedTerm заменяются на вызов Term:
{--------------------------------------------------------------}
{ Parse and Translate a Term with Optional Leading Sign }
procedure SignedTerm;
var Sign: char;
begin
Sign := Look;
if IsAddop(Look) then
GetChar;
Term;
if Sign = '-' then Negate;
end;
{--------------------------------------------------------------}
...
{--------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
SignedTerm;
while IsAddop(Look) do
case Look of
'+': Add;
'-': Subtract;
end;
end;
{--------------------------------------------------------------}
Если память мне не изменяет мы однажды уже имели и процедуру SignedFactor и SignedTerm. У меня были причины сделать так в то время... они имели отношение к обработке булевой алгебры и, в частности, булевой функции "not". Но, конечно, для арифметических операций дублирование не нужно. В выражении типа:
-x*y
очевидно, что знак идет со всем термом x*y а не просто с показателем x и таким способом Expression и закодирован.
Протестируйте этот новый код, выполнив Main. Она все еще вызывает Expression, так что теперь вы должны быть способны работать с выражениями, содержащими любую из четырех арифметических операций.
Наше последнее дело, относительно выражений, это модификация процедуры Factor для разрешения выражений в скобках. Используя рекурсивный вызов Expression мы можем уменьшить необходимый код практически до нуля. Пять строк, добавленные в Factor, выполнят эту работу:
{--------------------------------------------------------------}
{ Parse and Translate a Factor }
procedure Factor;
begin
if Look ='(' then begin
Match('(');
Expression;
Match(')');
end
else if IsDigit(Look) then
LoadConstant(GetNumber)
else if IsAlpha(Look)then
LoadVariable(GetName)
else
Error('Unrecognized character ' + Look);
end;
{--------------------------------------------------------------}
К этому моменту ваш "компилятор" должен уметь обрабатывать любые допустимые выражения, которые вы ему подбросите. Еще лучше, что он должен отклонить все недопустимые!
Definition of Keywords and Token
{--------------------------------------------------------------}
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);
begin
Write(TAB, s);
end;
{--------------------------------------------------------------}
{ Output a String with Tab and CRLF }
procedure EmitLn(s: string);
begin
Emit(s);
WriteLn;
end;
{--------------------------------------------------------------}
{ Generate a Unique Label }
function NewLabel: string;
var S: string;
begin
Str(LCount, S);
NewLabel := 'L' + S;
Inc(LCount);
end;
{--------------------------------------------------------------}
{ Post a Label To Output }
procedure PostLabel(L: string);
begin
WriteLn(L, ':');
end;
{---------------------------------------------------------------}
{ Clear the Primary Register }
procedure Clear;
begin
EmitLn('CLR D0');
end;
{---------------------------------------------------------------}
{ Negate the Primary Register }
procedure Negate;
begin
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Complement the Primary Register }
procedure NotIt;
begin
EmitLn('NOT D0');
end;
{---------------------------------------------------------------}
{ Load a Constant Value to Primary Register }
procedure LoadConst(n: string);
begin
Emit('MOVE #');
WriteLn(n, ',D0');
end;
{---------------------------------------------------------------}
{ Load a Variable to Primary Register }
procedure LoadVar(Name: string);
begin
if not InTable(Name) then Undefined(Name);
EmitLn('MOVE ' + Name + '(PC),D0');
end;
{---------------------------------------------------------------}
{ Push Primary onto Stack }
procedure Push;
begin
EmitLn('MOVE D0,-(SP)');
end;
{---------------------------------------------------------------}
{ Add Top of Stack to Primary }
procedure PopAdd;
begin
EmitLn('ADD (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Subtract Primary from Top of Stack }
procedure PopSub;
begin
EmitLn('SUB (SP)+,D0');
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Multiply Top of Stack by Primary }
procedure PopMul;
begin
EmitLn('MULS (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Divide Top of Stack by Primary }
procedure PopDiv;
begin
EmitLn('MOVE (SP)+,D7');
EmitLn('EXT.L D7');
EmitLn('DIVS D0,D7');
EmitLn('MOVE D7,D0');
end;
{---------------------------------------------------------------}
{ AND Top of Stack with Primary }
procedure PopAnd;
begin
EmitLn('AND (SP)+,D0');
end;
{---------------------------------------------------------------}
{ OR Top of Stack with Primary }
procedure PopOr;
begin
EmitLn('OR (SP)+,D0');
end;
{---------------------------------------------------------------}
{ XOR Top of Stack with Primary }
procedure PopXor;
begin
EmitLn('EOR (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Compare Top of Stack with Primary }
procedure PopCompare;
begin
EmitLn('CMP (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was = }
procedure SetEqual;
begin
EmitLn('SEQ D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was != }
procedure SetNEqual;
begin
EmitLn('SNE D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was > }
procedure SetGreater;
begin
EmitLn('SLT D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was < }
procedure SetLess;
begin
EmitLn('SGT D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was <= }
procedure SetLessOrEqual;
begin
EmitLn('SGE D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was >= }
procedure SetGreaterOrEqual;
begin
EmitLn('SLE D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Store Primary to Variable }
procedure Store(Name: string);
begin
EmitLn('LEA ' + Name + '(PC),A0');
EmitLn('MOVE D0,(A0)')
end;
{---------------------------------------------------------------}
{ Branch Unconditional }
procedure Branch(L: string);
begin
EmitLn('BRA ' + L);
end;
{---------------------------------------------------------------}
{ Branch False }
procedure BranchFalse(L: string);
begin
EmitLn('TST D0');
EmitLn('BEQ ' + L);
end;
{---------------------------------------------------------------}
{ Read Variable to Primary Register }
procedure ReadIt(Name: string);
begin
EmitLn('BSR READ');
Store(Name);
end;
{ Write from Primary Register }
procedure WriteIt;
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;
{---------------------------------------------------------------}
{ Allocate Storage for a Static Variable }
procedure Allocate(Name, Val: string);
begin
WriteLn(Name, ':', TAB, 'DC ', Val);
end;
{---------------------------------------------------------------}
{ Parse and Translate a Math Factor }
procedure BoolExpression; Forward;
procedure Factor;
begin
if Token = '(' then begin
Next;
BoolExpression;
MatchString(')');
end
else begin
if Token = 'x' then
LoadVar(Value)
else if Token = '#' then
LoadConst(Value)
else Expected('Math Factor');
Next;
end;
end;
{--------------------------------------------------------------}
{ Recognize and Translate a Multiply }
procedure Multiply;
begin
Next;
Factor;
PopMul;
end;
{-------------------------------------------------------------}
{ Recognize and Translate a Divide }
procedure Divide;
begin
Next;
Factor;
PopDiv;
end;
{---------------------------------------------------------------}
{ Parse and Translate a Math Term }
procedure Term;
begin
Factor;
while IsMulop(Token) do begin
Push;
case Token of
'*': Multiply;
'/': Divide;
end;
end;
end;
{--------------------------------------------------------------}
{ Recognize and Translate an Add }
procedure Add;
begin
Next;
Term;
PopAdd;
end;
{-------------------------------------------------------------}
{ Recognize and Translate a Subtract }
procedure Subtract;
begin
Next;
Term;
PopSub;
end;
{---------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
if IsAddop(Token) then
Clear
else
Term;
while IsAddop(Token) do begin
Push;
case Token of
'+': Add;
'-': Subtract;
end;
end;
end;
{---------------------------------------------------------------}
{ Get Another Expression and Compare }
procedure CompareExpression;
begin
Expression;
PopCompare;
end;
{---------------------------------------------------------------}
{ Get The Next Expression and Compare }
procedure NextExpression;
begin
Next;
CompareExpression;
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Equals" }
procedure Equal;
begin
NextExpression;
SetEqual;
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational " Less Than or Equal" }
procedure LessOrEqual;
begin
NextExpression;
SetLessOrEqual;
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Not Equals" }
procedure NotEqual;
begin
NextExpression;
SetNEqual;
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Less Than" }
procedure Less;
begin
Next;
case Token of
'=': LessOrEqual;
'>': NotEqual;
else begin
CompareExpression;
SetLess;
end;
end;
end;
{---------------------------------------------------------------}
{ Recognize and Translate a Relational "Greater Than" }
procedure Greater;
begin
Next;
if Token = '=' then begin
NextExpression;
SetGreaterOrEqual;
end
else begin
CompareExpression;
SetGreater;
end;
end;
{---------------------------------------------------------------}
{ Parse and Translate a Relation }
procedure Relation;
begin
Expression;
if IsRelop(Token) then begin
Push;
case Token of
'=': Equal;
'<': Less;
'>': Greater;
end;
end;
end;
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Factor with Leading NOT }
procedure NotFactor;
begin
if Token = '!' then begin
Next;
Relation;
NotIt;
end
else
Relation;
end;
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Term }
procedure BoolTerm;
begin
NotFactor;
while Token = '&' do begin
Push;
Next;
NotFactor;
PopAnd;
end;
end;
{--------------------------------------------------------------}
{ Recognize and Translate a Boolean OR }
procedure BoolOr;
begin
Next;
BoolTerm;
PopOr;
end;
{--------------------------------------------------------------}
{ Recognize and Translate an Exclusive Or }
procedure BoolXor;
begin
Next;
BoolTerm;
PopXor;
end;
{---------------------------------------------------------------}
{ Parse and Translate a Boolean Expression }
procedure BoolExpression;
begin
BoolTerm;
while IsOrOp(Token) do begin
Push;
case Token of
'|': BoolOr;
'~': BoolXor;
end;
end;
end;
{--------------------------------------------------------------}
{ Parse and Translate an Assignment Statement }
procedure Assignment;
var Name: string;
begin
CheckTable(Value);
Name := Value;
Next;
MatchString('=');
BoolExpression;
Store(Name);
end;
{---------------------------------------------------------------}
{ 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;
{--------------------------------------------------------------}
{ Parse and Translate a WHILE Statement }
procedure DoWhile;
var L1, L2: string;
begin
Next;
L1 := NewLabel;
L2 := NewLabel;
PostLabel(L1);
BoolExpression;
BranchFalse(L2);
Block;
MatchString('ENDWHILE');
Branch(L1);
PostLabel(L2);
end;
{--------------------------------------------------------------}
{ Read a Single Variable }
procedure ReadVar;
begin
CheckIdent;
CheckTable(Value);
ReadIt(Value);
Next;
end;
{--------------------------------------------------------------}
{ Process a Read Statement }
procedure DoRead;
begin
Next;
MatchString('(');
ReadVar;
while Token = ',' do begin
Next;
ReadVar;
end;
MatchString(')');
end;
{--------------------------------------------------------------}
{ Process a Write Statement }
procedure DoWrite;
begin
Next;
MatchString('(');
Expression;
WriteIt;
while Token = ',' do begin
Next;
Expression;
WriteIt;
end;
MatchString(')');
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;
begin
Next;
if Token <> 'x' then Expected('Variable Name');
CheckDup(Value);
AddEntry(Value, 'v');
Allocate(Value, '0');
Next;
end;
{--------------------------------------------------------------}
{ Parse and Translate Global Declarations }
procedure TopDecls;
begin
Scan;
while Token = 'v' do
Alloc;
while Token = ',' do
Alloc;
end;
{--------------------------------------------------------------}
{ Initialize }
procedure Init;
begin
GetChar;
Next;
end;
{--------------------------------------------------------------}
{ Main Program }
begin
Init;
MatchString('PROGRAM');
Header;
TopDecls;
MatchString('BEGIN');
Prolog;
Block;
MatchString('END');
Epilog;
end.
{--------------------------------------------------------------}
ТОЧКИ С ЗАПЯТОЙ
Со времен появления Алгола точки с запятой были частью почти каждого современного языка. Все мы использовали их считая это само собой разумеющимся. Однако я полагаю, что больше ошибок компиляции происходило из-за неправильно размещенной или отсутствующей точки с запятой, чем в любом другом случае. И если бы мы получали один пенни за каждое дополнительное нажатие клавиши, использованное программистами для набора этих маленьких мошенников, мы смогли бы оплатить национальный долг.
Будучи воспитанным на Фортране, я потратил много времени чтобы привыкнуть к использованию точек с запятой и сказать по правде я никогда полностью не понимал почему они необходимы. Так как я программирую на Паскале и так как использование точек с запятой в Паскале особенно мудрено, этот один небольшой символ является моим наибольшим источником ошибок.
Когда я начал разработку KISS, я решил критически относиться к каждой конструкции в других языках и попытаться избежать наиболее общих проблем, происходящих с ними. Это ставит точку с запятой очень высоко в моем хит-листе.
Чтобы понять роль точки с запятой, вы должны изучить краткую предысторию.
Ранние языки программирования были строчно-ориентированными. В Фортране, например, различные части утверждения занимали определенные столбцы и поля, в которых они должны были располагаться. Так как некоторые утверждения были слишком длинными для одной строки, существовал механизм "карта продолжения" ("continuation card"), позволяющий компилятору знать, что данная карта все еще является частью предыдущей строки. Механизм дожил до наших дней, хотя перфокарты теперь - дела отдаленного прошлого.
Когда появились другие языки, они также приняли различные механизмы для работы с многострочными операторами. Хороший пример - BASIC. Важно осознать, тем не менее, что механизм Фортрана был затребован не столько строчной ориентацией языка, сколько ориентацией по столбцам. В тех версиях Фортрана, где разрешен ввод в свободной форме, он больше не нужен.
Когда отцы Алгола представили этот язык, они хотели уйти от строчно-ориентированных программ подобных Фортрану или Бейсику и разрешить ввод в свободной форме. Это дало возможность связывать множество утверждений в одну строку как например:
a=b; c=d; e=e+1;
В случаях подобных этому, точка с запятой почти обязательна. Та же самая строка без точек с запятой выглядит просто "странной":
a=b c= d e=e+1
Я полагаю, что это главная... возможно единственная... причина точек с запятой: не давать программам выглядеть странно.
Но идея со связыванием множества утверждений вместе в одну строку в лучшем случае сомнительная. Это не очень хороший стиль программирования и возвращение назад к дням, когда считалось важным сэкономить карты. В наши дни CRT и выровненного кода ясность программ гораздо лучше обеспечивается сохранением раздельных утверждений. Все-таки хорошо иметь возможность множественных утверждений, но это позор - оставлять программистов в рабстве у точек с запятой только чтобы этот редкий случай не "выглядел странно".
Когда я начинал KISS, я попытался держать глаза открытыми. Я решил, что буду использовать точки с запятой когда это станет необходимо для синтаксического анализатора, но только тогда. Я рассчитывал, что это случится примерно в то время, когда я добавил возможность разложения утверждений на несколько строк. Но как вы можете видеть это никогда не случилось. Компилятор TINY совершенно счастлив анализировать наиболее сложные утверждения, разложенные на любое число строк, без точек с запятой.
Однако, есть люди, которые использовали точки с запятой так долго, что они чувствуют себя без них голыми. Я один из них. Как только KISS стал достаточно хорошо определен, я попробовал написать на этом языке несколько программ-примеров. Я обнаружил, к своему ужасу, что пытаюсь в любом случае расставлять точки с запятой. Так что теперь я стою перед перспективой нового потока ошибок компилятора, вызванных нежелательными точками с запятой. Тьфу!
Возможно более важно, что есть читатели, которые разрабатывают свои собственные языки, которые могут включать точки с запятой или которые хотят использовать методы из этого руководства для компиляции стандартных языков типа C. В обоих случаях, нам необходима возможность работать с точками с запятой.
ТРУСЛИВЫЙ ВЫХОД
Прежде, чем мы заберемся в детали (и потенциальную сложность) преобразования типов, я хотел бы, чтобы вы видели, что существует один супер простой способ решения проблемы: просто переводить каждую переменную в длинное целое во время загрузки!
Для этого достаточно добавить всего одну строку в LoadVar, хотя, если мы не собираемся полностью игнорировать эффективность, она должна ограничиваться проверкой IF. Вот измененная версия:
{---------------------------------------------------------------}
{ Load a Variable to Primary Register }
procedure LoadVar(Name, Typ: char);
begin
if Typ <> 'L' then
EmitLn('CLR.L D0');
Move(Typ, Name + '(PC)', 'D0');
end;
{---------------------------------------------------------------}
(Обратите внимание, что StoreVar не нуждается в подобном изменении).
Если вы выполните некоторые тесты с этой новой версией, вы обнаружите, что теперь все работает правильно, хотя иногда неэффективно. К примеру, рассмотрим случай a=b (для тех же самых объявлений, что показаны выше). Теперь сгенерированный код становится:
CLR.L D0
MOVE.W B(PC),D0
LEA A(PC),A0
MOVE.B D0,(A0)
В этом случае CLR оказывается ненужной, так как результат помещается в байтовую переменную. Небольшая доработка помогла бы нам улучшить его. Однако, все это не так уж плохо, и это типичного рода неэффективность, которую мы видели прежде в нехитрых компиляторах.
Я должен подчеркнуть, что устанавливая старшие разряды в нуль, мы фактически обрабатываем числа как целые числа без знака. Если вместо этого мы хотим обрабатывать их как целые числа со знаком (более вероятный случай) мы должны делать расширение знака после загрузки. Просто для того, чтобы обернуть эту часть дискуссии милой красной ленточкой, давайте изменим LoadVar как показано ниже:
{---------------------------------------------------------------}
{ Load a Variable to Primary Register }
procedure LoadVar(Name, Typ: char);
begin
if Typ = 'B' then
EmitLn('CLR.L D0');
Move(Typ, Name + '(PC)', 'D0');
if Typ = 'W' then
EmitLn('EXT.L D0');
end;
{---------------------------------------------------------------}
В этой версии байт обрабатывается как без-знаковое число (как в Паскале и Си) в то время как слово обрабатывается как знаковое.
УМНОЖЕНИЕ
Если вы убедились, что сам синтаксический анализатор работает правильно, мы должны выяснить, что необходимо сделать для генерации правильного кода. С этого места дела становятся немного труднее так как правила более сложные.
Давайте с начала возьмем случай умножения. Эта операция аналогична "addops" в том, что оба операнда должны быть одного и того же размера. Она отличается в трех важных отношениях:
· Тип произведения обычно не такой же как тип двух операндов. Для произведения двух слов мы получаем в результате длинное слово.
· 68000 не поддерживает умножение 32 x 32, так что необходим вызов подпрограммы для программного умножения.
· Он также не поддерживает умножение 8 x 8, поэтому байтовые операнды должны быть переведены до слова.
Действия, которые мы должны выполнить, лучше всего показывает следующая таблица:
| T1
T2 | B | W | L | ||||
| B | Преобразовать D0 в W
Преобразовать D7 в W MULS Result = W | Преобразовать D0 в W
MULS Result = L | Преобразовать D0 в L
JSR MUL32 Result = L | ||||
| W | Преобразовать D7 в W
MULS Result = L | MULS
Result = L | Преобразовать D0 в L
JSR MUL32 Result = L | ||||
| L | Преобразовать D7 в L
JSR MUL32 Result = L | Преобразовать D7 в L
JSR MUL32 Result = L | JSR MUL32
Result = L |
Эта таблица показывает действия, предпринимаемые для каждой комбинации типов операндов. Есть три вещи, на которые необходимо обратить внимание: во-первых, мы предполагаем, что существует библиотечная подпрограмма MUL32, которая выполняет 32 x 32 умножение, оставляя 32-битное (не 64) произведение. Если в процессе этого происходит переполнение мы игнорируем его и возвращаем только младшие 32 бита.
Во-вторых, заметьте, что таблица симметрична. Наконец, обратите внимание, что произведение это всегда длинное слово, за исключением случая когда оба операнда байты. (Стоит заметить, между прочим, что это означает что результатом многих выражений будет длинное слово, нравится нам это или нет. Возможно идея перевода всех их заранее не была уж такой возмутительной, в конце концов!)
Теперь ясно, что мы должны будем генерировать различный код для 16-разрядного и 32-разрядного умножения. Для этого лучше всего иметь отдельные подпрограммы генерации кода для этих двух случаев:
{---------------------------------------------------------------}
{ Multiply Top of Stack by Primary (Word) }
procedure GenMult;
begin
EmitLn('MULS D7,D0')
end;
{---------------------------------------------------------------}
{ Multiply Top of Stack by Primary (Long) }
procedure GenLongMult;
begin
EmitLn('JSR MUL32');
end;
{---------------------------------------------------------------}
Исследование кода ниже для PopMul должно убедить вас, что условия в таблице выполнены:
{---------------------------------------------------------------}
{ Generate Code to Multiply Primary by Stack }
function PopMul(T1, T2: char): char;
var T: char;
begin
Pop(T1);
T := SameType(T1, T2);
Convert(T, 'W', 'D7');
Convert(T, 'W', 'D0');
if T = 'L' then
GenLongMult
else
GenMult;
if T = 'B' then
PopMul := 'W'
else
PopMul:= 'L';
end;
{---------------------------------------------------------------}
Как вы можете видеть, подпрограмма начинается совсем как PopAdd. Два аргумента приводятся к тому же самому типу. Два вызова Convert заботятся о случаях, когда оба операнда - байты. Сами данные переводятся до слова, но подпрограмма помнит тип чтобы назначать корректный тип результату. В заключение мы вызываем одну из двух подпрограмм генерации кода и затем назначаем тип результата. Не слишком сложно, действительно.
Я полагаю, что сейчас вы уже тестируете программу. Попробуйте все комбинации размеров операндов.
УМНОЖЕНИЕ И ДЕЛЕНИЕ
Теперь давайте возьмемся за действительно серьезные дела. Как вы знаете, кроме операторов "addops" существуют и другие… выражения могут также иметь операторы умножения и деления. Вы также знаете, что существует неявный приоритет операторов или иерархия, связанная с выражениями, чтобы в выражениях типа
2 + 3 * 4,
мы знали, что нужно сначала умножить, а затем сложить. (Видите, зачем нам нужен стек?)
В ранние дни технологии компиляторов, люди использовали различные довольно сложные методы для того чтобы правила приоритета операторов соблюдались. Но, оказывается, все же, что ни один из них нам не нужен… эти правила могут быть очень хорошо применены в нашей технике нисходящего синтаксического анализа. До сих пор единственной формой, которую мы применяли для терма была форма одиночной десятичной цифры. В более общей форме мы можем определить терм как произведение показателей (product of factors), то есть
<term> ::= <factor> [ <mulop> <factor ]*
Что такое показатель? На данный момент это тоже, чем был раннее терм - одиночной цифрой.
Обратите внимание: терм имеет ту же форму, что и выражение. Фактически, мы можем добавить это, в наш компилятор осторожно скопировав и переименовав. Но во избежание неразберихи ниже приведен полный листинг всех подпрограмм анализатора. (Заметьте способ, которым мы изменяем порядок операндов в Divide.)
{---------------------------------------------------------------}
{ Parse and Translate a Math Factor }
procedure Factor;
begin
EmitLn('MOVE #' + GetNum + ',D0')
end;
{--------------------------------------------------------------}
{ Recognize and Translate a Multiply }
procedure Multiply;
begin
Match('*');
Factor;
EmitLn('MULS (SP)+,D0');
end;
{-------------------------------------------------------------}
{ Recognize and Translate a Divide }
procedure Divide;
begin
Match('/');
Factor;
EmitLn('MOVE (SP)+,D1');
EmitLn('DIVS D1,D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate a Math Term }
procedure Term;
begin
Factor;
while Look in ['*', '/'] do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'*': Multiply;
'/': Divide;
else Expected('Mulop');
end;
end;
end;
{--------------------------------------------------------------}
{ Recognize and Translate an Add }
procedure Add;
begin
Match('+');
Term;
EmitLn('ADD (SP)+,D0');
end;
{-------------------------------------------------------------}
{ Recognize and Translate a Subtract }
procedure Subtract;
begin
Match('-');
Term;
EmitLn('SUB (SP)+,D0');
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
Term;
while Look in ['+', '-'] do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'+': Add;
'-': Subtract;
else Expected('Addop');
end;
end;
end;
{--------------------------------------------------------------}
Конфетка! Почти работающий транслятор в 55 строк Паскаля! Получаемый код начинает выглядеть действительно полезным, если не обращать внимание на неэффективность. Запомните, мы не пытаемся создавать сейчас самый компактный код.
УНАРНЫЙ МИНУС
На данном этапе мы имеем синтаксический анализатор, который поддерживает почти любые выражения, правильно? ОК, тогда испробуйте следующее предложение:
-1
Опс! Он не работает, не правда ли? Процедура Expression ожидает, что все числа будут целыми и спотыкается на знаке минус. Вы найдете, что +3 также не будет работать, так же как и что-нибудь типа:
-(3-2).
Существует пара способов для исправления этой проблемы. Самый легкий (хотя и не обязательно самый лучший) способ – вставить ноль в начало выражения, так чтобы -3 стал 0-3. Мы можем легко исправить это в существующей версии Expression:
{---------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
if IsAddop(Look) then
EmitLn('CLR D0')
else
Term;
while IsAddop(Look) do begin
EmitLn('MOVE D0,-(SP)');
case Look of
'+': Add;
'-': Subtract;
else Expected('Addop');
end;
end;
end;
{--------------------------------------------------------------}
Я говорил вам, насколько легко мы сможем вносить изменения! На этот раз они стоили нам всего трех новых строчек Паскаля. Обратите внимание на появление ссылки на новую функцию IsAddop. Как только проверка на addop появилась дважды, я решил выделить ее в отдельную функцию. Форма функции IsAddop должна быть аналогична форме функции IsAlpha. Вот она:
{--------------------------------------------------------------}
{ Recognize an Addop }
function IsAddop(c: char): boolean;
begin
IsAddop := c in ['+', '-'];
end;
{--------------------------------------------------------------}
ОК, внесите эти изменения в программу и повторно откомпилируйте. Вы должны также включить IsAddop в базовую копию программы Cradle. Она потребуется нам позже. Сейчас попробуйте снова ввести -1. Вау! Эффективность полученного кода довольно плохая… шесть строк кода только для того, чтобы загрузить простую константу… но, по крайней мере, правильно работает. Запомните, мы не пытаемся сделать замену Turbo Pascal.
На данном этапе мы почти завершили создание структуры нашего синтаксического анализатора выражений. Эта версия программы должна правильно распознавать и компилировать почти любое выражение, которое вы ей подсунете. Она все еще ограничена тем, что поддерживает показатели, состоящие только из одной цифры. Но я надеюсь, что теперь вы начинаете понимать, что мы можем расширять возможности синтаксического анализатора делая незначительные изменения. Вы возможно даже не будете удивлены, когда услышите, что переменная или даже вызов функции это просто один из видов показателя.
В следующей главе я покажу, как можно легко расширить наш синтаксический анализатор для поддержки всех этих возможностей, и я также покажу как легко мы можем добавить много символьные числа и имена переменных. Итак, вы видите, что мы совсем недалеко от действительно полезного синтаксического анализатора.
УПРАВЛЯЮЩИЕ СТРУКТУРЫ
Мы почти дома. Имея булевы выражения легко добавить управляющие структуры. Для TINY мы разрешим только две из них, IF и WHILE:
<if> ::= IF <bool-expression> <block> [ ELSE <block>] ENDIF
<while> ::= WHILE <bool-expression> <block> ENDWHILE
Еще раз позвольте мне разъяснить решения, подразумевающиеся в этом синтаксисе, который сильно отличается от синтаксиса C или Pascal. В обоих этих языках "тело" IF или WHILE расценивается как одиночный оператор. Если вы предполагаете использовать блок из более чем одного оператора вы должны создать составной утверждение использую BEGIN-END (в Pascal) или '{}' (в C). В TINY (и KISS) нет таких вещей как составное утверждение... одиночное или множественное, они являются в этом языке просто блоками.
В KISS все управляющие структуры имеют явные и уникальные ключевые слова, выделяющие операторный блок поэтому не может быть никакой путаницы где он начинается и заканчивается. Это современный подход, используемый в таких уважаемых языках, как Ada и Modula-2 и он полностью устраняет проблему "висячих else".
Обратите внимание, что я мог бы использовать то же самое ключевое слово END для завершения всех конструкций, как это сделано в Pascal. (Закрывающая '}' в C служит той же самой цели.) Но это всегда вело к неразберихе, вот почему программисты на Pascal предпочитают писать так:
end { loop }
или end { if }
Как я объяснил в пятой части, использование уникальных терминальных ключевых слов увеличивает размер списка ключевых слов и, следовательно, замедляет лексический анализ, но в данном случае это кажется небольшой ценой за дополнительную подстраховку. Лучше обнаруживать ошибки во время компиляции, чем во время выполнения.
Одна последняя мысль: каждая из двух конструкций выше имеют нетерминалы
<bool-expression> и <block>,
расположенные рядом без разделяющих ключевых слов. В Паскале мы ожидали бы в этом месте ключевые слова THEN и DO.
Я не вижу проблем в том, чтобы опустить эти ключевые слова, и синтаксический анализатор также не будет иметь проблем, при условии, что мы не сделаем ошибок в bool-expression. С другой стороны, если мы включим эти дополнительные ключевые слова мы получили бы еще один уровень подстраховки за малые деньги, и с этим у меня также нет проблем. Примите правильное решение, каким путем пойти.
ОК, после этого небольшого объяснения давайте продолжим. Как обычно нам понадобятся несколько новых подпрограмм генерации кода. Они генерируют код для условных и безусловных переходов:
{---------------------------------------------------------------}
{ Branch Unconditional }
procedure Branch(L: string);
begin
EmitLn('BRA ' + L);
end;
{---------------------------------------------------------------}
{ Branch False }
procedure BranchFalse(L: string);
begin
EmitLn('TST D0');
EmitLn('BEQ ' + L);
end;
{--------------------------------------------------------------}
Исключая изоляцию подпрограмм генератора кода, код для анализа управляющих конструкций такой же, как вы видели прежде:
{---------------------------------------------------------------}
{ Recognize and Translate an IF Construct }
procedure Block; Forward;
procedure DoIf;
var L1, L2: string;
begin
Match('i');
BoolExpression;
L1 := NewLabel;
L2 := L1;
BranchFalse(L1);
Block;
if Look = 'l' then begin
Match('l');
L2 := NewLabel;
Branch(L2);
PostLabel(L1);
Block;
end;
PostLabel(L2);
Match('e');
end;
{--------------------------------------------------------------}
{ Parse and Translate a WHILE Statement }
procedure DoWhile;
var L1, L2: string;
begin
Match('w');
L1 := NewLabel;
L2 := NewLabel;
PostLabel(L1);
BoolExpression;
BranchFalse(L2);
Block;
Match('e');
Branch(L1);
PostLabel(L2);
end;
{--------------------------------------------------------------}
Чтобы связать все это вместе нам нужно только изменить процедуру Block чтобы распознавать ключевые слова IF и WHILE. Как обычно мы расширим определение блока так:
<block> ::= ( <statement> )*
где
<statement> ::= <if> | <while> | <assignment>
Соответствующий
код:
{--------------------------------------------------------------}
{ Parse and Translate a Block of Statements }
procedure Block;
begin
while not(Look in ['e', 'l']) do begin
case Look of
'i': DoIf;
'w': DoWhile;
else Assignment;
end;
end;
end;
{--------------------------------------------------------------}
Добавьте подпрограммы, которые я дал, откомпилируйте и протестируйте их. У вас должна быть возможность анализировать одно-символьные версии любых управляющих конструкции. Выглядит довольно хорошо!
Фактически, за исключением одно-символьного ограничения, мы получили практически полную версию TINY. Я назову его TINY Version 0.1.
ВЕРХНИЙ УРОВЕНЬ
Одна из самых больших ошибок людей при нисходящем проектировании заключается в неправильном выборе истинной вершины. Они думают, что знают какой должна быть общая структура проекта и поэтому они продолжают и записывают ее.
Всякий раз, когда я начинаю новый проект, я всегда хочу сделать это в самом начале. На языке разработки программ (program design language - PDL) этот верхний уровень походит на что-нибудь вроде:
begin
solve the problem
end
Конечно, я соглашусь с вами, что это не слишком большая подсказка о том, что расположено на следующем уровне, но я все равно запишу это просто для того, чтобы почувствовать, что я действительно начинаю с вершины.
В нашем случае, общая функция компилятора заключается в компиляции законченной программы. С этого начинается любое определение языка, записанное в БНФ. На что походит верхний уровень БНФ? Хорошо, это немного зависит от транслируемого языка.
Давайте взглянем на Pascal.
ВОЗВРАЩЕНИЕ СИМВОЛА
По существу, все сканеры, которые я когда-либо видел, и которые написаны на Паскале, использовали механизм перечислимых типов, который я только что описал. Это конечно работающий механизм, но он не кажется мне самым простым подходом.
Прежде всего, список возможных типов символов может получиться довольно длинным. Здесь я использовал только один символ "Operator" для обозначения всех операторов, но я видел другие проекты, в которых фактически возвращаются различные кода для каждого.
Существует, конечно, другой простой тип, который может быть возвращен как код: символ. Вместо возвращения значения "Operator" для знака "+", что неправильного в том, чтобы просто возвращать сам символ? Символ - такая же хорошая переменная для кодирования различных типов лексем, она легко может быть использована в операторах Case, и это гораздо проще набрать. Что может быть проще?
Кроме того, мы уже имели опыт с идеей кодировать ключевые слова как одиночные символы. Наши предыдущие программы уже написаны таким способом, так что использование этого метода минимизирует изменения того, что мы уже сделали.
Некоторые из вас могут почувствовать, что идея с возвращение символьных кодов слишком детская. Я должен допустить, что она становится немного неуклюжей для операторов типа "<=". Если вы хотите остаться с перечислимыми типами, хорошо. Для остальных я хотел бы показать как изменить то, что мы сделали выше, для поддержки такого подхода.
Во-первых, сейчас вы можете удалить объявление типа SymType... он нам больше не понадобится. И вы можете изменить тип Token в char.
Затем, чтобы заменить SymType, добавьте следующую константу:
const KWcode: string[5] = 'xilee';
(Я буду кодировать все идентификаторы одиночным символом 'x').
Наконец измените Scan и его родственников следующим образом:
{--------------------------------------------------------------}
{ Get an Identifier }
procedure GetName;
begin
Value := '';
if not IsAlpha(Look) then Expected('Name');
while IsAlNum(Look) do begin
Value := Value + UpCase(Look);
GetChar;
end;
Token := KWcode[Lookup(Addr(KWlist), Value, 4) + 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 := '#';
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;
if Length(Value) = 1 then
Token := Value[1]
else
Token := '?';
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 begin
GetOp
else begin
Value := Look;
Token := '?';
GetChar;
end;
SkipWhite;
end;
{--------------------------------------------------------------}
{ Main Program }
begin
Init;
repeat
Scan;
case Token of
'x': write('Ident ');
'#': Write('Number ');
'i', 'l', 'e': Write('Keyword ');
else Write('Operator ');
end;
Writeln(Value);
until Value = 'END';
end.
{--------------------------------------------------------------}
Эта программа должна работать также как и предыдущая версия. Небольшое различие в структуре, может быть, но она кажется мне более простой.
Эта серия статей является руководством
Эта серия статей является руководством по теории и практике разработки синтаксических анализаторов и компиляторов языков программирования. Прежде чем вы закончите чтение этой книги, мы раскроем все аспекты конструирования компиляторов, создадим новый язык программирования, и построим работающий компилятор.
Хотя я по образованию и не специалист в компьютерах, я интересовался компиляторами в течение многих лет. Я покупал и старался разобраться с содержимым практически каждой выпущенной на эту тему книги. И, должен признаться, это был долгий путь. Эти книги написаны для специалистов в компьютерной науке и слишком трудны для понимания большинству из нас. Но с течением лет часть из прочитанного начала доходить до меня. Закрепить полученное позволило то, что я начал самостоятельно пробовать это на своем собственном компьютере. Сейчас я хочу поделиться с вами своими знаниями. После прочтения этой книги вы не станете ни специалистом, ни узнаете всех секретов теории конструирования компиляторов. Я намеренно полностью игнорирую большинство теоретических аспектов этой темы. Вы изучите только практические аспекты, необходимые для создания работающей системы.
В течение всей книги я буду проводить эксперименты на компьютере, а вы будете повторять их за мной и ставить свои собственные эксперименты. Я буду использовать Turbo Pascal 4.0 и периодически буду включать примеры, написанные в TP. Эти примеры вы будете копировать себе в компьютер и выполнять. Если у вас не установлен Turbo Pascal вам будет трудно следить за ходом обучения, поэтому я настоятельно рекомендую его поставить. Кроме того, это просто замечательный продукт и для множества других задач!
Некоторые тексты программ будут показаны как примеры или как законченные продукты, которые вы можете копировать без необходимости понимания принципов их работы. Но я надеюсь сделать гораздо больше: я хочу научить вас КАК это делается, чтобы вы могли делать это самостоятельно, и не только повторять то, что я делаю, но и улучшать.
В последней главе мы изучили методы, используемые для синтаксического анализа и трансляции математических выражений в общей форме. Мы закончили созданием простого синтаксического анализатора, поддерживающего выражения произвольной сложности с двумя ограничениями:
·
Разрешены только числовые показатели
· Числовые показатели ограничены одиночной цифрой.
В этой главе мы избавимся от этих ограничений. Мы также расширим то что сделали, добавив операции присваивания и вызовы функций. Запомните, однако, что второе ограничение было главным образом наложено нами самими... выбрано для удобства, чтобы облегчить себе жизнь и сконцентрироваться на фундаментальных принципах. Как вы увидите, от этого ограничения легко освободиться, так что не слишком задерживайтесь на этом. Мы будем использовать это прием пока он служит нам, уверенные в том, что сможем избавиться от него, когда будем готовы.
В трех первых частях этой серии мы рассмотрели синтаксический анализ и компиляцию математических выражений, постепенно и методично пройдя от очень простых одно-символьных "выражений", состоящих из одного терма, через выражения в более общей форме и закончив достаточно полным синтаксическим анализатором, способным анализировать и транслировать операции присваивания с много символьными токенами, вложенными пробелами и вызовами функций. Сейчас я собираюсь провести вас сквозь этот процесс еще раз, но уже с целью интерпретации а не компиляции объектного кода.
Если эта серия о компиляторах, то почему мы должны беспокоиться об интерпретаторах? Просто я хочу чтобы вы увидели как изменяется характер синтаксического анализатора при изменении целей. Я также хочу объединить понятия этих двух типов трансляторов, чтобы вы могли видеть не только различия но и сходства.
Рассмотрим следующее присваивание:
x = 2 * y + 3
В компиляторе мы хотим заставить центральный процессор выполнить это присваивание во время выполнения. Сам транслятор не выполняет никаких арифметических операций… он только выдает объектный код, который заставит процессор сделать это когда код выполнится. В примере выше компилятор выдал бы код для вычисления значения выражения и сохранения результата в переменной x.
Для интерпретатора, напротив, никакого объектного кода не генерируется. Вместо этого арифметические операции выполняются немедленно как только происходит синтаксический анализ. К примеру, когда синтаксический анализ присваивания завершен, x будет содержать новое значение.
Метод, который мы применяем во всей этой серии, называется "синтаксически-управляемым переводом". Как вы знаете к настоящему времен, структура синтаксического анализатора очень близко привязана к синтаксису анализируемых нами конструкций. Мы создали процедуры на Pascal, которые распознают каждую конструкцию языка. Каждая из этих конструкций (и процедур) связана с соответствующим "действием", которое выполняет все необходимое как только конструкция распознана. В нашем компиляторе каждое действие включает выдачу объектного кода для выполнения позднее во время исполнения. В интерпретаторе каждое действие включает что-то для немедленного выполнения.
В четырех первых главах этой серии мы сконцентрировали свое внимание на синтаксическом анализе математических выражений и операций присваивания. В этой главе мы остановимся на новой и захватывающей теме: синтаксическом анализе и трансляции управляющих конструкций таких как, например, операторы IF.
Эта тема дорога для моего сердца, потому что является для меня поворотной точкой. Я играл с синтаксическим анализом выражений также как мы делали это в этой серии, но я все же чувствовал, что нахожусь еще очень далеко от возможности поддержки полного языка. В конце концов, реальные языки имеют ветвления, циклы, подпрограммы и все такое. Возможно вы разделяли некоторые из этих мыслей. Некоторое время назад, тем не менее, я должен был реализовать управляющие конструкции для структурного препроцессора ассемблера, который я писал. Вообразите мое удивление, когда я обнаружил, что это было гораздо проще, чем синтаксический анализ выражений, через который я уже прошел. Я помню подумал "Эй, это же просто!". После того, как мы закончим этот урок, я готов поспорить, что вы будете думать так же.
В пятой части этой серии мы рассмотрели управляющие конструкции и разработали подпрограммы синтаксического анализа для трансляции их в объектный код. Мы закончили с хорошим, относительно богатым набором конструкций.
Однако, когда мы оставили синтаксический анализатор, в наших возможностях существовал один большой пробел: мы не обращались к вопросу условия ветвления. Чтобы заполнить пустоту, я представил вам фиктивную подпрограмму анализа Condition, которая служила только как заменитель настоящей.
Одним из дел, которыми мы займемся на этом уроке, будет заполнение этого пробела посредством расширения Condition до настоящего анализатора/транслятора.
В последней главе я оставил вас с компилятором который должен почти работать, за исключением того, что мы все еще ограничены одно-символьными токенами. Цель этого урока состоит в том, чтобы избавиться от этого ограничения раз и навсегда. Это означает, что мы должны иметь дело с концепцией лексического анализатора (сканера).
Возможно я должен упомянуть, почему нам вообще нужен лексический анализатор... в конце концов до настоящего времени мы были способны хорошо справляться и без него даже когда мы предусмотрели много символьные токены.
Единственная причина, на самом деле, имеет отношение к ключевым словам. Это факт компьютерной жизни, что синтаксис ключевого слова имеет ту же самую форму, что и синтаксис любого другого идентификатора. Мы не можем сказать пока не получим полное слово действительно ли это ключевое слово. К примеру переменная IFILE и ключевое слово IF выглядят просто одинаковыми до тех пор, пока вы не получите третий символ. В примерах до настоящего времени мы были всегда способны принять решение, основанное на первом символе токена, но это больше невозможно когда присутствуют ключевые слова. Нам необходимо знать, что данная строка является ключевым словом до того, как мы начнем ее обрабатывать. И именно поэтому нам нужен сканер.
На последнем уроке я также пообещал, что мы могли бы предусмотреть нормальные токены без глобальных изменений того, что мы уже сделали. Я не солгал... мы можем, как вы увидите позднее. Но каждый раз, когда я намеревался встроить эти элементы в синтаксический анализатор, который мы уже построили, у меня возникали плохие чувства в отношении их. Все это слишком походило на временную меру. В конце концов я выяснил причину проблемы: я установил программу лексического анализа не объяснив вам вначале все о лексическом анализе, и какие есть альтернативы. До настоящего времени я старательно избегал давать вам много теории и, конечно, альтернативные варианты. Я обычно не воспринимаю хорошо учебники которые дают двадцать пять различных способов сделать что-то, но никаких сведений о том, какой способ лучше всего вам подходит. Я попытался избежать этой ловушки, просто показав вам один способ, который работает.
Этот урок будет отличаться от других уроков в нашей серии по синтаксическому анализу и конструированию компиляторов. На этом уроке не будет никаких экспериментов или кода. На этот раз я хотел бы просто поговорить с вами некоторое время. К счастью, это будет короткий урок и затем мы сможем продолжить с того места где остановились, надо надеяться с обновленной энергией.
Когда я учился в университете, я обнаружил, что могу всегда следить за профессорской лекцией намного лучше, если знал куда он идет. Готов поспорить, с вами было то же самое.
Так что я подумал, может быть пришло время рассказать вам куда мы идем с этой серией: что нас ждет в будущих главах и вообще что к чему. Я также поделюсь своими общими мыслями о полезности того, что мы делали.
В предыдущих главах мы изучили многие из методов, необходимых для создания полноценного компилятора. Мы разработали операции присваивания (с булевыми и арифметическими выражениями), операторы отношений и управляющие конструкции. Мы все еще не обращались к вопросу вызова процедур и функций, но даже без них мы могли бы в принципе создать мини-язык. Я всегда думал, что было бы забавно просто посмотреть, насколько маленьким можно было бы построить язык, чтобы он все еще оставался полезным. Теперь мы уже почти готовы сделать это. Существует проблема: хотя мы знаем, как анализировать и транслировать конструкции, мы все еще совершенно не знаем, как сложить их все вместе в язык.
В этих ранних главах разработка наших программ имела явно восходящий характер. В случае с синтаксическим анализом выражений, например, мы начали с самых низкоуровневых конструкций, индивидуальных констант и переменных и прошли свой путь до более сложных выражений.
Большинство людей считают, что нисходящий способ разработки лучше, чем восходящий. Я тоже так думаю, но способ, который мы использовали, казался естественно достаточным для тех вещей, которые мы анализировали.
Тем не менее вы не должны думать, что последовательный подход, который мы применяли во всех этих главах, является принципиально восходящим. В этой главе я хотел бы показать вам, что этот подход может работать точно также, когда применяется сверху вниз... может быть даже лучше. Мы рассмотрим языки типа C и Pascal и увидим как могут быть построены законченные компиляторы начиная сверху.
В следующей главе мы применим ту же самую методику для создания законченного транслятора подмножества языка KISS, который я буду называть TINY. Но одна из моих целей в этой серии состоит в том, чтобы вы не только могли увидеть как работает компилятор для TINY или KISS, но чтобы вы также могли разрабатывать и создавать компиляторы своих собственных языков. Примеры Си и Паскаля помогут вам в этом. Одна вещь, которую я хотел чтобы вы увидели, состоит в том, что естественная структура компилятора очень сильно зависит от транслируемого языка, поэтому простота и легкость конструирования компилятора очень сильно зависит от того, позволите ли вы языку определять структуру программы.
Немного сложнее получить полный компилятор C или Pascal, да мы и не будем. Но мы можем расчистить верхние уровни так, чтобы вы увидели как это делается.
Давайте начнем.
В последней главе я показал вам основную идею нисходящей разработки компилятора. Я показал вам первые несколько шагов этого процесса для компиляторов Pascal и C, но я остановился далеко от его завершения. Причина была проста: если мы собираемся построить настоящий, функциональный компилятор для какого-нибудь языка, я предпочел бы сделать это для KISS, языка, который я определил в этой обучающей серии.
В этой главе мы собираемся сделать это же для подмножества KISS, которое я решил назвать TINY.
Этот процесс по существу будет аналогичен выделенному в главе 9, за исключением одного заметного различия. В той главе я предложил вам начать с полного БНФ описания языка. Это было бы прекрасно для какого-нибудь языка типа Pascal или C, определения которого устоялись. В случае же с TINY, однако, мы еще не имеем полного описания... мы будем определять язык по ходу дела. Это нормально. Фактически, это предпочтительней, так как мы можем немного подстраивать язык по ходу дела для сохранения простоты анализа.
Так что в последующей разработке мы фактически будем выполнять нисходящую разработку и языка и его компилятора. БНФ описание будет расти вместе с компилятором.
В ходе этого будет принят ряд решений, каждое из которых будет влиять на БНФ и, следовательно, характер языка. В каждой решающей точке я попытаюсь не забывать объяснять решение и разумное обоснование своего выбора. Если вам случится придерживаться другого мнения и вы предпочтете другой вариант, вы можете пойти своим путем. Сейчас вы имеет базу для этого. Я полагаю важно отметить, что ничего из того, что мы здесь делаем не подчинено каким-либо жесткими правилами. Когда вы разрабатываете свой язык вы не должны стесняться делать это своим способом.
Многие из вас могут сейчас спросить: зачем нужно начинать с самого начала? У нас есть работающее подмножество KISS как результат главы 7 (лексический анализ). Почему бы просто не расширить его как нужно? Ответ тройной. Прежде всего, я сделал несколько изменений для упрощения программы... типа изоляции процедур генерации кода, в результате чего мы можем более легко выполнять преобразование для различных машин. Во-вторых, я хочу, чтобы вы увидели что разработка действительно может быть выполнена сверху вниз как это подчеркнуто в последней главе. Наконец, нам всем нужна практика. Каждый раз, когда я прохожу через эти упражнения, я начинаю понимать немного больше, и вы будете тоже.
У меня есть хорошие и плохие новости. Плохие новости - эта глава не та, которую я вам обещал последний раз. Более того, и следующая глава также.
Хорошие новости в причине появления этой главы: я нашел способ упростить и улучшить лексический анализатор компилятора. Позвольте мне объяснить.
Эта глава - второе из тех отклонений в сторону, которые не вписываются в основное направление этой обучающей серии. Я упомянул в прошлый раз, что я накопил некоторые изменения, которые должны быть внесены в структуру компилятора. Поэтому я должен был отклониться чтобы разработать новую структуру и показать ее вам.
Теперь, когда все это позади, я могу сказать что я намерен сделать прежде всего. Это не должно занять много времени и затем мы сможем вернуться в основное русло.
Некоторые люди спрашивали меня о вещах, которые предоставляют другие языки, но к которым я пока что не обращался в этой серии. Две самых больших из них - это точки с запятой и комментарии. Возможно вы тоже задумывались о них и гадали как изменился бы компилятор если бы мы работали с ними. Только для того, чтобы вы могли проследовать дальше без тревожащего чувства, что что-то пропущено, мы рассмотрим здесь эти вопросы.
Наконец- то мы принимаемся за хорошую главу!
К этому моменту мы изучили почти все основные особенности компиляторов и синтаксического анализа. Мы узнали как транслировать арифметические выражения, булевы выражения, управляющие конструкции, объявления данных и операторы ввода/вывода. Мы определили язык TINY 1.3, который воплощает все эти возможности, и написали элементарный компилятор, который может их транслировать. Добавив файловый ввод/вывод мы могли бы действительно иметь работающий компилятор, способный производить выполнимые объектные файлы из программ, написанных на TINY. С таким компилятором мы могли бы писать простые программы, способные считывать целочисленные данные, выполнять над ними вычисления и выводить результаты.
Все это хорошо, но то, что у нас есть, это все еще только игрушечный язык. Мы не можем считывать и выводить даже одиночные символы текста и у нас все еще нет процедур.
Эти возможности, которые будут обсуждены в следующих двух главах, так сказать отделят мужчин от игрушек. "Настоящие" языки имеют более одного типа данных и они поддерживают вызовы процедур. Более чем любые другие, именно эти две возможности дают языку большую часть его характера и индивидуальности. Как только мы предоставим их, наши языки, TINY и его преемники, перестанут быть игрушками и получат характер настоящих языков, пригодных для серьезного программирования.
В течение нескольких предыдущих глав я обещал вам урок по этим двум важным темам. Каждый раз появлялись другие проблемы, которые требовали отклонения и работы с ними. Наконец у нас появилась возможность оставить все эти проблемы в покое и вернуться в основное русло. В этой главе я охвачу процедуры. В следующий раз мы поговорим об основных типах данных.
В последней главе (Часть 13, Процедуры) я упомянул, что в ней и в следующей главе мы рассмотрим две возможности, которые помогут отделить игрушечный язык от настоящего, пригодного к использованию. В ней мы рассмотрели вызовы процедур. Многие из вас терпеливо ждали, начиная с Августа'89 когда я выдам вторую. Хорошо, вот она.
В этой главе мы поговорим о том, как работать с различными типами данных. Как и в последней главе, я не буду сейчас включать эти возможности непосредственно в компилятор TINY. Вместо этого я буду использовать тот же самый подход, который так хорошо служил нам в прошлом: использование только фрагментов синтаксического анализатора и одно-символьных токенов. Как обычно, это позволит нам добраться непосредственно до сути вопроса не продираясь сквозь массу ненужного кода. Так как основные проблемы при работе с множественными типами данных возникают в арифметических операциях, на них мы и сконцентрируем свое внимание.
Несколько предупреждений: Во-первых, есть некоторые типы, которые я не буду охватывать в этой главе. Здесь мы будем говорить только о простых, встроенных типах. Мы даже не будем работать с массивами, указателями или строками, я охвачу их в следующих нескольких главах.
Во-вторых, мы также не будем обсуждать и типы, определяемые пользователем. Это будет значительно позже, по той простой причине, что я все еще не убедил себя, что эти определяемые пользователем типы должны быть в языке KISS. В более поздних главах я собираюсь охватить по крайней мере основные концепции определяемых пользователем типов, записей и т.д., просто для того, чтобы серия была полной. Но действительно ли они будут включены как часть KISS - все еще открытый вопрос. Я открыт для комментариев и предложений по этой теме.
Наконец, я должен предупредить вас: то, что мы собираемся сделать может добавить массу дополнительных сложностей и в синтаксический анализатор и в генерируемый код. Поддерживать различные типы достаточно просто. Сложность возникает когда вы добавляете правила преобразования между типами. Вообще-то, будет ли ваш компилятор простым или сложным зависит от способа, выбранного вами для определения правил преобразования типов. Даже если вы решите запретить любые преобразования типов (как в Ada, например) проблема все еще остается, и она встроена в математику. Когда вы умножаете два коротких числа, к примеру, вы можете получить длинный результат.
Я подошел к этой проблеме очень осторожно, пытаясь сохранить простоту. Но мы не можем полностью избежать сложности. Как обычно случается, мы оказываемся перед необходимостью выбирать между качеством кода и сложностью и, как обычно, я предпочитаю выбрать самый простой подход.
Могло ли действительно пройти четыре года с тех пор, как я написал четырнадцатую главу этой серии? Действительно ли возможно, что шесть долгих лет прошли с тех пор как я начал ее? Забавно, как летит время когда вы весело его проводите, не так ли?
Я не буду тратить много времени на извинения; просто подчеркну, что это случилось, и приоритеты меняются. За четыре года, начиная с четырнадцатой главы, я сумел стать уволенным, развестись, получить нервный срыв, начал новую карьеру как писатель, начал другую как консультант, двигался, работал на две системы реального времени и вырастил четырнадцать птенцов, трех голубей, шесть опоссумов и утку. Некоторое время синтаксический анализ исходного кода был не слишком высоко в моем списке приоритетов. Не написал ни одной вещи бесплатно, только за деньги. Но я пытаюсь быть верным и понимаю и чувствую свою ответственность перед вами, читателями, закончить то, что начал. Как сказала черепаха в одной из старых историй моего сына, я возможно медленная, но я надежная. Я уверен, что есть люди, стремящиеся увидеть последнюю катушку этого фильма, и я собираюсь дать им ее. Так что, если вы один из тех, кто ждал более или менее терпеливо, что из этого получится, благодарю за ваше терпение. Я приношу извинения за задержку. Давайте продолжим.
Эта обучающая серия обещает стать возможно одной из самых долгоиграющих мини-серий в истории, конкурирующей только с задержкой на Томе IV Кнута. Начатая в 1988, эта серия вошла в четырехлетнюю паузу в 1990, когда "заботы мира сего", изменения в приоритетах и интересах и необходимость зарабатывать на жизнь казалось забросили ее после Главы 14. Долго терпевшие из вас были наконец вознаграждены весной прошлого года долгожданной Главой 15. В ней я начал попытку поставить серию обратно на рельсы и по ходу дела сделать ее проще для достижения цели, которая состоит в том, чтобы обеспечить вас не только достаточным пониманием трудных тем теории компиляции, но также достаточными инструментами в виде фиксированных подпрограмм и концепций, так чтобы вы были способны продолжать самостоятельно и стали достаточно опытными для того, чтобы создавать свои собственные синтаксические анализаторы и трансляторы. Из-за этой длинной паузы я подумал что следует вернуться назад и повторно рассмотреть концепции, которые мы до этого охватили а также заново сделать некоторые части программы. В прошлом мы никогда сильно не касались разработки программных инструментов промышленного качества... в конце концов я пытался обучать (и обучаться) концепциям, а не промышленной практике. Чтобы сделать это я старался давать вам не законченные компиляторы и анализаторы, а только те отрывки кода, которые иллюстрировали частные случаи, которые мы рассматривали в текущий момент.
Я все еще верю, что это хороший способ изучения любого вопроса; никто не захочет вносить в изменения в программу в 100,000 строк только для того чтобы попробовать новую идею. Но идея работы с обрывками кода а не полными программами также имеет свои недостатки из-за которых мы писали те же самые фрагменты кода много раз. Хотя было полностью доказано, что повторение является хорошим способом обучения новым идеям, также правда и то, что оно может быть не слишком хорошей вещью. Ко времени, когда я завершил Главу 14, я казалось достиг пределов своих способностей манипулировать множеством файлов и множественными версиями тех же самых программ. Кто знает, может быть это одна из причин, по которым я кажется выдохся в то время.
ВВОД/ВЫВОД
Теперь у нас есть полный, работающий язык, за исключением одного небольшого смущающего факта: у нас нет никакого способа получить или вывести данные. Нам нужны подпрограммы ввода/вывода.
Современное соглашение, установленное в C и продолженное в Ada и Modula-2, состоит в том, чтобы вывести I/O операторы из самого языка и просто включить их в библиотеку подпрограмм. Это было бы прекрасно, за исключением того, что мы пока не имеем никаких средств поддержки подпрограмм. В любом случае, с этим подходом вы столкнетесь с проблемой переменной длины списка параметров. В Паскале I/O операторы встроены в язык, поэтому это единственные операторы, для которых список параметров может иметь переменное число элементов. В C мы примиряемся с клуджами типа scanf и printf и должны передавать количество параметров в вызываемую процедуру. В Ada и Modula-2 мы должны использовать неудобный (и медленный!) способ отдельного вызова для каждого аргумента.
Так что я думаю, что предпочитаю Паскалевский подход встраивания подпрограмм ввода/вывода, даже если мы не нуждаемся в этом.
Как обычно, для этого нам нужны еще несколько подпрограмм генерации кода. Они, оказывается, самые простые из всех, потому что все, что мы делаем это вызываем библиотечные процедуры для выполнения работы.
{---------------------------------------------------------------}
{ Read Variable to Primary Register }
procedure ReadVar;
begin
EmitLn('BSR READ');
Store(Value);
end;
{---------------------------------------------------------------}
{ Write Variable from Primary Register }
procedure WriteVar;
begin
EmitLn('BSR WRITE');
end;
{--------------------------------------------------------------}
Идея состоит в том, что READ загружает значение из входного потока в D0, а WRITE выводит его оттуда.
Эти две процедуры представляют собой нашу первую встречу с потребностью в библиотечных процедурах... компонентах Run Time Library (RTL). Конечно кто-то (а именно мы) должен написать эти подпрограммы, но они не являются непосредственно частью компилятора. Я даже не буду беспокоиться о том, чтобы показать здесь эти подпрограммы, так как они очевидно очень ОС-зависимы. Я просто скажу, что для SK*DOS они особенно просты... почти тривиальны. Одна из причин, по которым я не буду показывать их здесь в том, что вы можете добавлять новые виды возможностей, например приглашение в READ или возможность пользователю повторить ошибочный ввод.
Но это действительно отдельный от компилятора проект, так что теперь я буду подразумевать что библиотека, называемая TINYLIB.LIB, существует.
Так как нам теперь нужно загружать ее, мы должны добавить ее загрузку в процедуру Header:
{--------------------------------------------------------------}
{ Write Header Info }
procedure Header;
begin
WriteLn('WARMST', TAB, 'EQU $A01E');
EmitLn('LIB TINYLIB');
end;
{--------------------------------------------------------------}
Она возьмет на себя эту часть работы. Теперь нам также необходимо распознавать команды ввода и вывода. Мы можем сделать это добавив еще два ключевых слова в наш список:
{--------------------------------------------------------------}
{ Definition of Keywords and Token Types }
const NKW = 11;
NKW1 = 12;
const KWlist: array[1..NKW] of Symbol =
('IF', 'ELSE', 'ENDIF', 'WHILE', 'ENDWHILE',
'READ', 'WRITE', 'VAR', 'BEGIN', 'END',
'PROGRAM');
const KWcode: string[NKW1] = 'xileweRWvbep';
{--------------------------------------------------------------}
(Обратите внимание, что здесь я использую кода в верхнем регистре чтобы избежать конфликта с 'w' из WHILE.)
Затем нам нужны процедуры для обработки оператора ввода/вывода и его списка параметров:
{--------------------------------------------------------------}
{ 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;
{--------------------------------------------------------------}
Наконец, мы должны расширить процедуру 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;
{--------------------------------------------------------------}
На этом все. Теперь у нас есть язык!
ВЫПОЛНИМЫЕ УТВЕРЖДЕНИЯ
К этому времени мы можем генерировать пустую программу, которая имеет несколько объявленных переменных и возможно инициализированных. Но пока мы не генерировали ни строки выполнимого кода.
Верите ли вы или нет, но мы почти имеем пригодный для использования компилятор! Отсутствует только выполнимый код, который должен входить в основную программу. Но этот код - это только операции присваивания и операторы управления... все вещи, которые мы сделали раньше. Так что у нас не должно занять слишком много времени предусмотреть также и их.
БНФ определение, данное раньше для основной программы, включало операторный блок, который мы пока что игнорировали:
<main> ::= BEGIN <block> END
Сейчас мы можем рассматривать блок просто как серию операций присваивания:
<block> ::= (Assignment)*
Давайте начнем с добавления синтаксического анализатора для блока. Мы начнем с процедуры-заглушки для операции присваивания:
{--------------------------------------------------------------}
{ Parse and Translate an Assignment Statement }
procedure Assignment;
begin
GetChar;
end;
{--------------------------------------------------------------}
{ Parse and Translate a Block of Statements }
procedure Block;
begin
while Look <> 'e' do
Assignment;
end;
{--------------------------------------------------------------}
Измените процедуру Main чтобы она вызывала Block как показано ниже:
{--------------------------------------------------------------}
{ Parse and Translate a Main Program }
procedure Main;
begin
Match('b');
Prolog;
Block;
Match('e');
Epilog;
end;
{--------------------------------------------------------------}
Эта версия все еще не генерирует никакого кода для "операций присваивания"... все что она делает это съедает символы до тех пор, пока не увидит "e", означающее "END". Но она устанавливает основу для того, что следует дальше.
Следующий шаг, конечно, - это расширение кода для операций присваивания. Это то, что мы делали много раз до этого, поэтому я не буду задерживаться на этом. На этот раз, однако, я хотел бы работать с генерацией кода немного по-другому. До настоящего времени мы всегда просто вставляли Emits, которые генерируют выходной код в соответствии с подпрограммами синтаксического анализа. Немного неструктурно, возможно, но это кажется самым простым способом и помогает видеть, какой код должен быть выдан для каждой конструкции.
Однако, я понимаю, что большинство из вас используют компьютер 80x86, так что от кода, сгенерированного для 68000 вам мало пользы. Некоторые из вас спрашивали меня, что если бы машиннозависимый код мог бы быть собран в одном месте, то было бы проще перенастроить его на другой ЦПУ. Ответ конечно да.
Чтобы сделать это вставьте следующие подпрограммы "генерации кода":
{---------------------------------------------------------------}
{ Clear the Primary Register }
procedure Clear;
begin
EmitLn('CLR D0');
end;
{---------------------------------------------------------------}
{ Negate the Primary Register }
procedure Negate;
begin
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Load a Constant Value to Primary Register }
procedure LoadConst(n: integer);
begin
Emit('MOVE #');
WriteLn(n, ',D0');
end;
{---------------------------------------------------------------}
{ Load a Variable to Primary Register }
procedure LoadVar(Name: char);
begin
if not InTable(Name) then Undefined(Name);
EmitLn('MOVE ' + Name + '(PC),D0');
end;
{---------------------------------------------------------------}
{ Push Primary onto Stack }
procedure Push;
begin
EmitLn('MOVE D0,-(SP)');
end;
{---------------------------------------------------------------}
{ Add Top of Stack to Primary }
procedure PopAdd;
begin
EmitLn('ADD (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Subtract Primary from Top of Stack }
procedure PopSub;
begin
EmitLn('SUB (SP)+,D0');
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Multiply Top of Stack by Primary }
procedure PopMul;
begin
EmitLn('MULS (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Divide Top of Stack by Primary }
procedure PopDiv;
begin
EmitLn('MOVE (SP)+,D7');
EmitLn('EXT.L D7');
EmitLn('DIVS D0,D7');
EmitLn('MOVE D7,D0');
end;
{---------------------------------------------------------------}
{ Store Primary to Variable }
procedure Store(Name: char);
begin
if not InTable(Name) then Undefined(Name);
EmitLn('LEA ' + Name + '(PC),A0');
EmitLn('MOVE D0,(A0)')
end;
{---------------------------------------------------------------}
Приятная особенность такого подхода, конечно, в том что мы можем перенастроить компилятор на новый ЦПУ просто переписав эти процедуры "генератора кода". Кроме того, позднее мы обнаружим что можем улучшить качество кода немного подправляя эти процедуры без необходимости изменения компилятора.
Обратите внимание, что и LoadVar и Store проверяют таблицу идентификаторов чтобы удостовериться, что переменная определена. Обработчик ошибки Undefined просто вызывает Abort:
{--------------------------------------------------------------}
{ Report an Undefined Identifier }
procedure Undefined(n: string);
begin
Abort('Undefined Identifier ' + n);
end;
{--------------------------------------------------------------}
Итак, теперь мы наконец готовы начать обработку выполнимого кода. Мы сделаем это заменив пустую версию процедуры Assignment.
Мы проходили этот путь много раз прежде, так что все это должно быть вам знакомо. Фактически, если бы не изменения, связанные с генерацией кода, мы могли бы просто скопировать процедуры из седьмой части. Так как мы сделали некоторые изменения я не буду их просто копировать, но мы пройдем немного быстрее, чем обычно.
БНФ для операций присваивания:
<assignment> ::= <ident> = <expression>
<expression> ::= <first term> ( <addop> <term> )*
<first term> ::= <first factor> <rest>
<term> ::= <factor> <rest>
<rest> ::= ( <mulop> <factor> )*
<first factor> ::= [ <addop> ] <factor>
<factor> ::= <var> | <number> | ( <expression> )
Эта БНФ также немного отличается от той, что мы использовали раньше... еще одна "вариация на тему выражений". Эта специфичная версия имеет то, что я считаю лучшей обработкой унарного минуса. Как вы увидите позднее, это позволит нам очень эффективно обрабатывать отрицательные константы. Здесь стоит упомянуть, что мы часто видели преимущества "подстраивания" БНФ по ходу дела, с цель сделать язык легким для анализа. То, что вы видите здесь, немного другое: мы подстраиваем БНФ для того, чтобы сделать генерацию кода более эффективной! Это происходит впервые в этой серии.
Во всяком случае, следующий код реализует эту БНФ:
{---------------------------------------------------------------}
{ Parse and Translate a Math Factor }
procedure Expression; Forward;
procedure Factor;
begin
if Look = '(' then begin
Match('(');
Expression;
Match(')');
end
else if IsAlpha(Look) then
LoadVar(GetName)
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 }
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;
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;
{--------------------------------------------------------------}
{ Parse and Translate an Assignment Statement }
procedure Assignment;
var Name: char;
begin
Name := GetName;
Match('=');
Expression;
Store(Name);
end;
{--------------------------------------------------------------}
ОК, если вы вставили весь этот код, тогда откомпилируйте и проверьте его. Вы должны увидеть приемлемо выглядящий код, представляющий собой законченную программу, которая будет ассемблироваться и выполняться. У нас есть компилятор!
ВЫРАЖЕНИЯ С ДВУМЯ ЦИФРАМИ
Теперь, давайте немного улучшим то, что у нас есть. По общему признанию, выражение, состоящее только из одного символа, не удовлетворит наших потребностей надолго, так что давайте посмотрим, как мы можем расширить возможности компилятора. Предположим, что мы хотим обрабатывать выражения вида:
1+2
или
4-3
или в общем <term> +/- <term> (это часть формы Бэкуса-Наура или БНФ.)
Для того, чтобы сделать это, нам нужна процедура, распознающая термы и сохраняющая результат, и другая процедура, которая распознает и различает «+» и «-» и генерирует соответствующий код. Но если процедура Expression сохраняет свои результаты в регистре D0, то где процедура Term сохранит свои результаты? Ответ: на том же месте. Мы окажемся перед необходимостью сохранять первый результат процедуры Term где-нибудь, прежде чем мы получим следующий.
В основном, что нам необходимо сделать – создать процедуру Term, выполняющую то что раннее выполняла процедура Expression. Поэтому просто переименуйте процедуру Expression в Term и наберите новую версию Expression:
{---------------------------------------------------------------}
{ Parse and Translate an Expression }
procedure Expression;
begin
Term;
EmitLn('MOVE D0,D1');
case Look of
'+': Add;
'-': Subtract;
else Expected('Addop');
end;
end;
{--------------------------------------------------------------}
Затем выше Expression наберите следующие две процедуры:
{--------------------------------------------------------------}
{ Recognize and Translate an Add }
procedure Add;
begin
Match('+');
Term;
EmitLn('ADD D1,D0');
end;
{-------------------------------------------------------------}
{ Recognize and Translate a Subtract }
procedure Subtract;
begin
Match('-');
Term;
EmitLn('SUB D1,D0');
end;
{-------------------------------------------------------------}
Когда вы закончите, порядок подпрограмм должен быть следующий:
· Term (старая версия Expression)
· Add
· Subtract
· Expression
Теперь запустите программу. Испробуйте любую комбинацию, которую вы только можете придумать, из двух одиночных цифр, разделенных «+» или «-». Вы должны получить ряд из четырех инструкций на ассемблере. Затем испытайте выражения с заведомыми ошибками в них. Перехватывает анализатор ошибки?
Посмотрите на полученный объектный код. Можно сделать два замечания. Во-первых, сгенерированный код не такой, какой бы написали мы. Последовательность
MOVE #n,D0
MOVE D0,D1
неэффективна. Если бы мы писали этот код вручную, то, возможно, просто загрузили бы данные напрямую в D1.
Вывод: код, генерируемый нашим синтаксическим анализатором, менее эффективный, чем код, написанный вручную. Привыкните к этому. Это в известной мере относится ко всем компиляторам. Ученые посвятили целые жизни вопросу оптимизации кода и существуют методы, призванные улучшить качество генерируемого кода. Некоторые компиляторы выполняют оптимизацию достаточно хорошо, но за это приходится платить сложностью и в любом случае это проигранная битва… возможно никогда не придет время, когда хороший программист на ассемблере не смог бы превзойти компилятор. Прежде чем закончится этот урок, я кратко упомяну некоторые способы, которые мы можем применить для небольшой оптимизации, просто, чтобы показать вам, что мы на самом деле сможем сделать некоторые улучшения без излишних проблем. Но запомните, мы здесь для того, чтобы учиться, а не для того, чтобы узнать насколько компактным мы можем сделать код. А сейчас и на протяжении всей этой серии мы старательно будем игнорировать оптимизацию и сконцентрируемся на получении работающего кода.
Но наш код не работает! В коде есть ошибка! Команда вычитания вычитает D1 (первый аргумент) из D0 (второй аргумент). Но это неправильный способ, так как мы получаем неправильный знак результата. Поэтому исправим процедуру Subtract с помощью замены знака следующим образом:
{-------------------------------------------------------------}
{ Recognize and Translate a Subtract }
procedure Subtract;
begin
Match('-');
Term;
EmitLn('SUB D1,D0');
EmitLn('NEG D0');
end;
{-------------------------------------------------------------}
Теперь наш код даже еще менее эффективен, но по крайней мере выдает правильный ответ! К сожалению, правила, которые определяют значение математических выражений, требуют, чтобы условия в выражении следовали в неудобном для нас порядке. Опять, это только один из фактов жизни, с которыми вы учитесь жить. Все это возвратится снова, чтобы преследовать нас, когда мы примемся за деление
Итак, на данном этапе мы имеем синтаксический анализатор, который может распознавать сумму или разность двух цифр. Ранее мы могли распознавать только одиночные цифры. Но настоящие выражения могут иметь любую форму (или бесконечность других). Вернитесь и запустите программу с единственным входным символом “1”.
Не работает? А почему должен работать? Мы только указали анализатору, что единственным правильными видами выражений являются выражения с двумя термами. Мы должны переписать процедуру Expression так, чтобы она была намного более универсальной и с этого начать создание настоящего синтаксического анализатора.
ВЫЗОВ ПРОЦЕДУРЫ
Если вы удовлетворены работой программы, давайте обратимся ко второй половине уравнения... вызову.
Рассмотрим БНФ для вызова процедуры:
<proc_call> ::= <identifier>
с другой стороны БНФ для операции присваивания:
<assignment> ::= <identifier> '=' <expression>
Кажется у нас проблема. Оба БНФ утверждения с правой стороны начинаются с токена <identifier>. Как мы предполагаем узнать, когда мы видим идентификатор, имеем ли мы вызов процедуры или операцию присваивания? Это похоже на случай, когда наш синтаксический анализатор перестает быть предсказывающим и действительно это точно такой случай. Однако, оказывается эту проблему легко решить, так как все, что мы должны сделать - посмотреть на тип идентификатора, записанный в таблице идентификаторов. Как мы обнаружили раньше, небольшое локальное нарушение правила предсказывающего синтаксического анализа может быть легко обработано как специальный случай.
Вот как это делается:
{--------------------------------------------------------------}
{ Parse and Translate an Assignment Statement }
procedure Assignment(Name: char);
begin
Match('=');
Expression;
StoreVar(Name);
end;
{--------------------------------------------------------------}
{ Decide if a Statement is an Assignment or Procedure Call }
procedure AssignOrProc;
var Name: char;
begin
Name := GetName;
case TypeOf(Name) of
' ': Undefined(Name);
'v': Assignment(Name);
'p': CallProc(Name);
else Abort('Identifier ' + Name +
' Cannot Be Used Here');
end;
end;
{--------------------------------------------------------------}
{ Parse and Translate a Block of Statements }
procedure DoBlock;
begin
while not(Look in ['e']) do begin
AssignOrProc;
Fin;
end;
end;
{--------------------------------------------------------------}
Как вы можете видеть, процедура Block сейчас вызывает AssignOrProc вместо Assignment. Назначение этой новой процедуры просто считать идентификатор, определить его тип и затем вызвать процедуру, соответствующую этому типу. Так как имя уже прочитано, мы должны передать его в эти две процедуры и соответственно изменить Assignment. Процедура CallProc - это просто подпрограмма генерации кода:
{--------------------------------------------------------------}
{ Call a Procedure }
procedure CallProc(N: char);
begin
EmitLn('BSR ' + N);
end;
{--------------------------------------------------------------}
Хорошо, к этому моменту у нас есть компилятор, который может работать с процедурами. Стоить отметить, что процедуры могут вызывать процедуры с любой степенью вложенности. Так что, даже хотя мы и не разрешаем вложенные объявления, нет ничего, чтобы удерживало нас от вложенных вызовов, точно так, как мы ожидали бы на любом языке. Мы получили это и это было не слишком сложно, не так ли?
Конечно, пока мы можем работать только с процедурами, которые не имеют параметров. Процедуры могут оперировать глобальными переменными по их глобальным именам. Так что к этому моменту мы имеем эквивалент конструкции Бейсика GOSUB. Не слишком плохо... в конце концов масса серьезных программ была написана с применением GOSUBа., но мы можем добиться большего и добьемся. Это следующий шаг.
К этому моменту мы создали
К этому моменту мы создали ряд управляющих конструкций... в действительности более богатый набор чем предоставляет почти любой другой язык программирования. И, за исключением цикла FOR, это было довольно легко сделать. Но даже этот цикл был сложен только потому, что сложность заключалась в ассемблере.
Я завершаю на этом урок. Чтобы можно было обернуть наш продукт красной ленточкой, в действительности мы должны иметь настоящие ключевые слова вместо этих игрушечных одно-символьных. Вы уже видели, что расширить компилятор для поддержки много символьных слов не трудно, но в этом случае возникнут большие различия в представлении нашего входного кода. Я оставлю этот небольшой кусочек для следующей главы. В этой главе мы также рассмотрим логические выражения, так что мы сможем избавиться от фиктивной версии Condition, которую мы здесь использовали. Увидимся.
Для справочных целей привожу полный текст синтаксического анализатора для этого урока:
{--------------------------------------------------------------}
program Branch;
{--------------------------------------------------------------}
{ Constant Declarations }
const TAB = ^I;
CR = ^M;
{--------------------------------------------------------------}
{ Variable Declarations }
var Look : char; { Lookahead Character }
Lcount: integer; { Label Counter }
{--------------------------------------------------------------}
{ 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;
{--------------------------------------------------------------}
{ Match a Specific Input Character }
procedure Match(x: char);
begin
if Look = x then GetChar
else Expected('''' + x + '''');
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 Addop }
function IsAddop(c: char): boolean;
begin
IsAddop := 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;
{--------------------------------------------------------------}
{ Get an Identifier }
function GetName: char;
begin
if not IsAlpha(Look) then Expected('Name');
GetName := UpCase(Look);
GetChar;
end;
{--------------------------------------------------------------}
{ Get a Number }
function GetNum: char;
begin
if not IsDigit(Look) then Expected('Integer');
GetNum := Look;
GetChar;
end;
{--------------------------------------------------------------}
{ Generate a Unique Label }
function NewLabel: string;
var S: string;
begin
Str(LCount, S);
NewLabel := 'L' + S;
Inc(LCount);
end;
{--------------------------------------------------------------}
{ Post a Label To Output }
procedure PostLabel(L: string);
begin
WriteLn(L, ':');
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;
{--------------------------------------------------------------}
{ Parse and Translate a Boolean Condition }
procedure Condition;
begin
EmitLn('<condition>');
end;
{--------------------------------------------------------------}
{ Parse and Translate a Math Expression }
procedure Expression;
begin
EmitLn('<expr>');
end;
{--------------------------------------------------------------}
{ Recognize and Translate an IF Construct }
procedure Block(L: string); Forward;
procedure DoIf(L: string);
var L1, L2: string;
begin
Match('i');
Condition;
L1 := NewLabel;
L2 := L1;
EmitLn('BEQ ' + L1);
Block(L);
if Look = 'l' then begin
Match('l');
L2 := NewLabel;
EmitLn('BRA ' + L2);
PostLabel(L1);
Block(L);
end;
Match('e');
PostLabel(L2);
end;
{--------------------------------------------------------------}
{ Parse and Translate a WHILE Statement }
procedure DoWhile;
var L1, L2: string;
begin
Match('w');
L1 := NewLabel;
L2 := NewLabel;
PostLabel(L1);
Condition;
EmitLn('BEQ ' + L2);
Block(L2);
Match('e');
EmitLn('BRA ' + L1);
PostLabel(L2);
end;
{--------------------------------------------------------------}
{ Parse and Translate a LOOP Statement }
procedure DoLoop;
var L1, L2: string;
begin
Match('p');
L1 := NewLabel;
L2 := NewLabel;
PostLabel(L1);
Block(L2);
Match('e');
EmitLn('BRA ' + L1);
PostLabel(L2);
end;
{--------------------------------------------------------------}
{ Parse and Translate a REPEAT Statement }
procedure DoRepeat;
var L1, L2: string;
begin
Match('r');
L1 := NewLabel;
L2 := NewLabel;
PostLabel(L1);
Block(L2);
Match('u');
Condition;
EmitLn('BEQ ' + L1);
PostLabel(L2);
end;
{--------------------------------------------------------------}
{ Parse and Translate a FOR Statement }
procedure DoFor;
var L1, L2: string;
Name: char;
begin
Match('f');
L1 := NewLabel;
L2 := NewLabel;
Name := GetName;
Match('=');
Expression;
EmitLn('SUBQ #1,D0');
EmitLn('LEA ' + Name + '(PC),A0');
EmitLn('MOVE D0,(A0)');
Expression;
EmitLn('MOVE D0,-(SP)');
PostLabel(L1);
EmitLn('LEA ' + Name + '(PC),A0');
EmitLn('MOVE (A0),D0');
EmitLn('ADDQ #1,D0');
EmitLn('MOVE D0,(A0)');
EmitLn('CMP (SP),D0');
EmitLn('BGT ' + L2);
Block(L2);
Match('e');
EmitLn('BRA ' + L1);
PostLabel(L2);
EmitLn('ADDQ #2,SP');
end;
{--------------------------------------------------------------}
{ Parse and Translate a DO Statement }
procedure Dodo;
var L1, L2: string;
begin
Match('d');
L1 := NewLabel;
L2 := NewLabel;
Expression;
EmitLn('SUBQ #1,D0');
PostLabel(L1);
EmitLn('MOVE D0,-(SP)');
Block(L2);
EmitLn('MOVE (SP)+,D0');
EmitLn('DBRA D0,' + L1);
EmitLn('SUBQ #2,SP');
PostLabel(L2);
EmitLn('ADDQ #2,SP');
end;
{--------------------------------------------------------------}
{ Recognize and Translate a BREAK }
procedure DoBreak(L: string);
begin
Match('b');
EmitLn('BRA ' + L);
end;
{--------------------------------------------------------------}
{ Recognize and Translate an "Other" }
procedure Other;
begin
EmitLn(GetName);
end;
{--------------------------------------------------------------}
{ Recognize and Translate a Statement Block }
procedure Block(L: string);
begin
while not(Look in ['e', 'l', 'u']) do begin
case Look of
'i': DoIf(L);
'w': DoWhile;
'p': DoLoop;
'r': DoRepeat;
'f': DoFor;
'd': DoDo;
'b': DoBreak(L);
else Other;
end;
end;
end;
{--------------------------------------------------------------}
{ Parse and Translate a Program }
procedure DoProgram;
begin
Block('');
if Look <> 'e' then Expected('End');
EmitLn('END')
end;
{--------------------------------------------------------------}
{ Initialize }
procedure Init;
begin
LCount := 0;
GetChar;
end;
{--------------------------------------------------------------}
{ Main Program }
begin
Init;
DoProgram;
end.
{--------------------------------------------------------------}
{ Clear the Primary Register }
procedure Clear;
begin
EmitLn('CLR D0');
end;
{---------------------------------------------------------------}
{ Negate the Primary Register }
procedure Negate;
begin
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Complement the Primary Register }
procedure NotIt;
begin
EmitLn('NOT D0');
end;
{---------------------------------------------------------------}
{ Load a Constant Value to Primary Register }
procedure LoadConst(n: integer);
begin
Emit('MOVE #');
WriteLn(n, ',D0');
end;
{---------------------------------------------------------------}
{ Load a Variable to Primary Register }
procedure LoadVar(Name: string);
begin
if not InTable(Name) then Undefined(Name);
EmitLn('MOVE ' + Name + '(PC),D0');
end;
{---------------------------------------------------------------}
{ Push Primary onto Stack }
procedure Push;
begin
EmitLn('MOVE D0,-(SP)');
end;
{---------------------------------------------------------------}
{ Add Top of Stack to Primary }
procedure PopAdd;
begin
EmitLn('ADD (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Subtract Primary from Top of Stack }
procedure PopSub;
begin
EmitLn('SUB (SP)+,D0');
EmitLn('NEG D0');
end;
{---------------------------------------------------------------}
{ Multiply Top of Stack by Primary }
procedure PopMul;
begin
EmitLn('MULS (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Divide Top of Stack by Primary }
procedure PopDiv;
begin
EmitLn('MOVE (SP)+,D7');
EmitLn('EXT.L D7');
EmitLn('DIVS D0,D7');
EmitLn('MOVE D7,D0');
end;
{---------------------------------------------------------------}
{ AND Top of Stack with Primary }
procedure PopAnd;
begin
EmitLn('AND (SP)+,D0');
end;
{---------------------------------------------------------------}
{ OR Top of Stack with Primary }
procedure PopOr;
begin
EmitLn('OR (SP)+,D0');
end;
{---------------------------------------------------------------}
{ XOR Top of Stack with Primary }
procedure PopXor;
begin
EmitLn('EOR (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Compare Top of Stack with Primary }
procedure PopCompare;
begin
EmitLn('CMP (SP)+,D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was = }
procedure SetEqual;
begin
EmitLn('SEQ D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was != }
procedure SetNEqual;
begin
EmitLn('SNE D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was > }
procedure SetGreater;
begin
EmitLn('SLT D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was < }
procedure SetLess;
begin
EmitLn('SGT D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was <= }
procedure SetLessOrEqual;
begin
EmitLn('SGE D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Set D0 If Compare was >= }
procedure SetGreaterOrEqual;
begin
EmitLn('SLE D0');
EmitLn('EXT D0');
end;
{---------------------------------------------------------------}
{ Store Primary to Variable }
procedure Store(Name: string);
begin
if not InTable(Name) then Undefined(Name);
EmitLn('LEA ' + Name + '(PC),A0');
EmitLn('MOVE D0,(A0)')
end;
{---------------------------------------------------------------}
{ Branch Unconditional }
procedure Branch(L: string);
begin
EmitLn('BRA ' + L);
end;
{---------------------------------------------------------------}
{ Branch False }
procedure BranchFalse(L: string);
begin
EmitLn('TST D0');
EmitLn('BEQ ' + L);
end;
{---------------------------------------------------------------}
{ Read Variable to Primary Register }
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 }
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;
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;
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 }
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;
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
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] := '';
SType[i] := ' ';
end;
GetChar;
Scan;
end;
{--------------------------------------------------------------}
{ Main Program }
begin
Init;
Prog;
if Look <> CR then Abort('Unexpected data after ''.''');
end.
{--------------------------------------------------------------}
ЗАВЕРШЕНИЕ
Наконец-то, в этой главе мы узнали как работать с переменными (и литералами) различных типов. Как вы можете видеть, это не было слишком сложно. Фактически, в каком-то отношении большая часть кода выглядит даже еще проще, чем это было в более ранних программах. Только операторы умножения и деления требуют небольших размышлений и планирования.
Основная идея, которая облегчила нам жизнь, - идея преобразования процедур типа Expression в функции, возвращающие тип результата. Как только это было сделано, мы смогли сохранить ту же самую общую структуру компилятора.
Я не буду притворяться, что мы охватили каждый одиночный аспект этой проблемы. Я удобно проигнорировал без знаковую арифметику. Из того, что мы сделали, я думаю вы можете видеть, что их включение не добавляет никаких дополнительных проблем, просто дополнительные проверки.
Я так же игнорировал логические операторы And, Or и т.д. Оказывается, их довольно легко обрабатывать. Все логические операторы - побитовые операции, так что они симметричны и, следовательно, работают в том же самом режиме, что и PopAdd. Однако, имеется одно отличие: если необходимо расширить длину слова для логической переменной, расширение должно быть сделано как число без знака. Числа с плавающей точкой, снова, являются простыми для обработки... просто еще несколько процедур, которые будут добавлены в run-time библиотеку или, возможно, инструкции для математического сопроцессора.
Возможно более важно, что я также отделил проблему контроля соответствия типов, в противоположность преобразованию. Другими словами, мы разрешили операции между переменными всех комбинаций типов. Вообще, это не будет верным... конечно вы не захотите прибавить целое число, например, к строке. Большинство языков также не позволят вам смешивать символьные и целочисленные переменные.
Снова, в действительности в этом случае нет никаких новых проблем для рассмотрения. Мы уже проверяем типы двух операндов... в основном эти проверки выполняются в процедурах типа SameType. Довольно просто включить вызов обработчика ошибок если типы двух операндов несовместимы.
В общем случае мы можем рассматривать каждый одиночный оператор как обрабатываемый отдельной процедурой, в зависимости от типа двух операндов. Это просто, хотя и утомительно, реализовать просто создав таблицу переходов с типами операндов как индексами. В Паскале эквивалентная операция включала бы вложенные операторы Case. Некоторые из вызываемых процедур могли бы тогда быть простыми подпрограммами обработки ошибок, в то время как другие могли бы выполнять любые виды преобразований, необходимые нам. При добавлении нами типов, число процедур будет возрастать в геометрической прогрессии, но это все равно не неприемлемо большое число процедур.
Здесь же мы свернули такую таблицу переходов в гораздо меньшее количество процедур, просто используя симметрию и другие упрощающие правила.
ЗДЕСЬ НЕТ НИЧЕГО СЛОЖНОГО!
Затем я думал, что причина в том, что мы не генерировали очень хороший объектный код. Те из вас, кто следовали этой серии и пытались компилировать примеры, знают, что хотя код работает и достаточно отказоустойчив, его эффективность довольно ужасна. Я подчеркивал, что если бы мы сконцентрировались на получении компактного кода, то быстро бы получили всю недостающую сложность.
В какой то степени это так. В частности, мои первые небольшие усилия при попытке повысить эффективность подняли сложность до опасного уровня. Но с той поры когда я возился с некоторыми простыми методами оптимизацией и обнаружил некоторые, которые приводят к очень приличному качеству кода без добавления больших сложностей.
Наконец я подумал, что возможно причина была в "игрушечной" природе компилятора Я не претендовал на то, что мы когда-нибудь будем способны построить компилятор, конкурирующий с Borland и Microsoft. И однако снова, когда я забираюсь глубже в эти дела различия начинают стираться.
Просто чтобы удостовериться что до вас дошла эта мысль, позвольте мне ее высказать напрямую:
Используя методы, которые мы здесь применяли, возможно создать работающий, промышленного качества компилятор не добавляя много сложности к тому, что мы уже сделали.
С тех пор, как началась эта серия, я получил от вас некоторые комментарии. Большинство из них повторяют мои собственные мысли: "Это просто! Почему учебники представляют это настолько сложным?" Хороший вопрос.
Недавно я возвратился и взглянул на некоторые из этих текстов снова и даже купил и читаю некоторые новые. Каждый раз я возвращался с тем же чувством: эти ребята представляют это слишком сложным.
Что происходит? Почему все это кажется сложным в этих книгах, но легким для нас? Действительно ли мы умней чем Ахо, Ульман, Бринч Хансен и все остальные?
Едва ли. Но мы делаем некоторые вещи по-другому и все более и более я начинаю ценить значение нашего подхода и способ, которым он упрощает дело. Кроме очевидных сокращений, которые я выделил в первой части, типа одно-символьных токенов и консольного ввода/вывода, мы сделали некоторые неявные предположения и сделали некоторые вещи отличными от того, как разрабатывали компиляторы в прошлом. Как оказалось, наш метод делает жизнь намного проще.
Но почему все другие ребята не используют его?
Вы должны вспомнить контекст некоторых ранних разработок компиляторов. Эти люди работали на очень небольших компьютерах с ограниченными возможностями. Объемы памяти были очень ограничены, набор команд центрального процессора был минимален и программы чаще выполнялись в пакетном режиме, чем в интерактивном. Как оказалось, это повлияло на некоторые ключевые решения проекта, которые действительно усложнили проект. До недавнего времени я не понимал, насколько классический дизайн компилятора был обусловлен доступным оборудованием.
Даже в тех случаях, где эти ограничения больше не накладывались, люди предпочитали структурировать их программы тем же самым образом, так как это способ, которому они обучались.
В нашем случае мы начали с чистого листа бумаги. Имеется опасность, конечно, что вы попадетесь в ловушки, которые другие люди давно научились избегать. Но это также позволило нам использовать различные подходы, которые, частично из-за проекта, частично из-за чистой удачи, позволили нам добиться простоты.
Имеются области, которые, я думаю, в прошлом приводили к сложности:
·
Ограниченная оперативная память, вынуждающая выполнять множество проходов.
Я только что прочитал "Brinch Hansen on Pascal Compilers" (отличная книга, BTW). Он разработал компилятор Pascal для PC, но он начал в 1981 г. с систем с 64К памяти и поэтому почти каждое решение проекта который он делал, было нацелено на то, чтобы уместить компилятор в ОЗУ. Чтобы сделать это, его компилятор выполнял три прохода, один из которых - лексический анализ. Не было никакого способа, с помощью которого он мог бы, например, использовать распределенный сканер, который я представил в последней главе, потому что структура программы не позволяла этого. Ему также требовались не один а два промежуточных языка для обеспечения связи между фазами.
Все ранние создатели компиляторов были вынуждены иметь дело с такой проблемой: разбить компилятор на достаточные части так, чтобы они поместились в памяти. Когда у вас есть множество проходов, вы должны добавить структуры данных для поддержки информации которую каждый проход оставляет для следующего. Это добавляет сложность и завершает управление проектом. В книге Ли "The Anatomy of a Compiler" упоминается компилятор Fortran, разработанный для IBM 1401. Он имел не менее 63 отдельных проходов! Само собой разумеется, в компиляторе, подобном этому, разделение на фазы доминировало бы над дизайном.
Даже в ситуации, когда ОЗУ достаточно, люди предпочитали использовать те же самые методы, с которыми они хорошо знакомы. До тех пор, пока не появился Turbo Pascal, мы не знали насколько может быть простым компилятор если бы вы начали с других предположений.
· Пакетная обработка.
В ранние дни пакетная обработка была единственным выбором... не существовало никаких интерактивных вычислений. Даже сегодня компиляторы по существу выполняются в пакетном режиме.
В компиляторах для майн-фреймов, так же как и во многих микро компиляторах, значительные усилия расходуются на восстановление после ошибок... это может занять 30-40% компилятора и полностью управлять проектом. Идея состоит в том, чтобы избежать остановки на первой ошибке, а скорее идти любой ценой, так чтобы вы могли сказать программисту о как можно большем количестве ошибок во всей программе насколько возможно.
Все это возвращает нас к дням ранних майн-фреймов, где время выполнения измерялось в часах и днях и было важно выжать каждую последнюю унцию информации из каждого выполнения.
В этой серии я был очень осторожен и избежал проблемы восстановления после ошибок и вместо этого наш компилятор просто останавливается с сообщением на первой ошибке. Я откровенно признаюсь, что это было в основном потому, что я захотел использовать легкий путь и сохранить простоту. Но этот метод, заданный изначально Borland в Turbo Pascal также имеет много полезного в любом случае. Кроме сохранения простоты компилятора это также очень хорошо соответствует идее интерактивной системы. Когда компиляция происходит быстро и, особенно, когда вы имеете редактор типа Borland который будет правильно указывать вам на точку ошибки, тогда имеет смысл остановиться там и просто перезапустить компиляцию после того, как ошибка исправлена.
· Большие программы.
Ранние компиляторы были разработаны для поддержки больших программ... по существу бесконечных. В те дни существовал небольшой выбор; идея с библиотеками подпрограмм и раздельной компиляцией была еще в будущем. Снова, это предположение вело к многопроходному дизайну и промежуточным файлам для поддержки результатов раздельной обработки.
Поставленная Бринч Хансеном цель состояла в том, чтобы компилятор был способен компилировать сам себя. Снова, из-за ограничений оперативной памяти это приводило его к многопроходному дизайну. Он нуждался в таком маленьком резидентном коде компилятора, насколько возможно, так чтобы необходимые таблицы и другие структуры данных поместились в оперативную память.
Я не заявил об этом пока, потому что не было необходимости... мы всегда просто читали и записывали данные как потоки, в любом случае. Но, для заметки, мой план всегда был в том, чтобы в промышленном компиляторе исходные и объектные данные должны сосуществовать в ОЗУ с компилятором, а ля ранний Turbo Pascal. Вот почему я был осторожен и сохранил подпрограммы типа GetChar и Emit как отдельные подпрограммы, несмотря на их небольшой размер. Будет просто изменить их на чтение и запись из памяти.
· Акцент на эффективность.
Джон Бэкус заявил, что когда он и его коллеги разработали первоначальный компилятор Fortran они знали, что они должны получать компактный код. В те дни имелись сильные чувства против HOL в пользу ассемблера и причиной была эффективность. Если бы Fortran не производил очень хороший код по стандартам ассемблера, пользователи просто бы отказались использовать его. Заметьте, компилятор Fortran оказался одним из наиболее эффективных из когда либо созданных в терминах качества кода. Но он был сложным!
Сегодня мы имеем мощь ЦПУ и размер ОЗУ с запасом, так что эффективность кода не такая большая проблема. Старательно игнорируя эту проблему мы действительно были способны сохранить простоту. Как ни странно, тем не менее, как я сказал, я нашел некоторую оптимизацию которую мы можем добавить в базовую структуру компилятора не добавляя слишком много сложности. Так что в этом случае мы получим свой пирог и съедим его: мы в любом случае закончим с приемлемым качеством кода.
· Ограниченный набор инструкций.
Первые компьютеры имели примитивный набор команд. Вещи, которые мы считаем само собой разумеющимися, такие как операции со стеком и косвенная адресация появились с большими сложностями.
Пример: в большинстве компиляторов имеется структура данных, называемая литерный пул (literal pool). Компилятор обычно идентифицирует все литералы, используемые в программе, и собирает их в одиночную структуру данных. Все ссылки на литералы сделаны косвенно на этот пул. В конце компиляции компилятор выдает команды для выделения памяти и инициализации литерного пула.
Нам пока не нужно было обращаться к этой проблеме. Когда нам нужно загрузить литерал мы просто делаем это строкой:
MOVE #3,D0
Можно кое-что упомянуть об использования литерного пула особенно на машине типа 8086, где данные и код могут быть разделены. Однако все это добавляет довольно большое количество сложности с небольшим результатом.
Конечно, без стека мы бы потерялись. И вызовы подпрограмм и временная память сильно зависят от стека и мы использовали его даже больше, чем необходимо для облегчения синтаксического анализа выражений.
· Желание общности.
Многое из содержимого типичной книги по компиляторам акцентировано на вопросы, к которым мы совсем не обращались... вопросы типа автоматической трансляции грамматик или генерация таблиц LALR анализа. Это не просто, потому что авторы хотят впечатлить вас. Имеются хорошие практические причины, почему эти темы рассмотрены здесь.
Мы концентрировались на использовании синтаксического анализатора с рекурсивным спуском для анализа детерминированной грамматики, т.е. грамматики, которая однозначна и, следовательно, может быть проанализирована с одним уровнем предсказания. Я не сделал из этого большого ограничения, но факт то, что это представляет небольшое подмножество возможных грамматик. Фактически, существует бесконечное число грамматик, которые мы не можем анализировать используя наш метод. LR метод более мощный и может работать с теми грамматиками, с которыми мы не можем.
В теории компиляции важно знать, как работать с этими другими грамматиками и как преобразовать их в грамматики которые проще для работы с ними. К примеру многие (но не все) неоднозначные грамматики могут быть преобразованы в однозначные. Способ сделать это не всегда очевиден, все таки, и так много людей посвятили годы на разработку способа их автоматического преобразования.
На практике, эти проблемы оказываются значительно менее важными. Современные языки стараются разрабатывать так, чтобы они были простыми для анализа в любом случае. Это было ключевой мотивацией при разработке Pascal. Несомненно, имеются паталогические грамматики, для которых вы с большим трудом написали бы однозначную БНФ, но в реальном мире лучшим ответом возможно было бы избежание этих грамматик.
В нашем случае, конечно, мы трусливо позволили языку развиваться по ходу дела. Вы не можете всегда иметь такую роскошь. Однако, с небольшой заботой вы были бы способны сохранить синтаксический анализатор простым без необходимости прибегать к автоматическому переводу грамматик.
В этой серии мы приняли значительно отличающийся подход. Мы начали с чистого листа бумаги и разработали методы, которые работают в том контексте, в котором мы находимся: это однопользовательский персональный компьютер с вполне достаточно мощным ЦПУ и объемом ОЗУ. Мы ограничили сами себя приемлемыми грамматиками, которые легки для анализа, мы с успехом использовали систему команд ЦПУ, и мы не концентрировались на эффективности. Именно поэтому это было просто.
Означает ли это, что мы навсегда обречены создавать только игрушечные компиляторы? Нет, я так не думаю. Я уже сказал, что мы можем добавить некоторую оптимизацию без изменения структуры компилятора. Если мы захотим обрабатывать большие файлы, мы всегда можем добавить для этого буферизацию файлов. Эти вещи не оказывают влияния на общий дизайн компилятора.
И я думаю что это главный фактор. Начав с маленьких и ограниченных случаев мы были способны сконцентрироваться на структуре компилятора, которая естественна для работы. Так как структура естественным образом удовлетворяет работе, она почти обречена быть простой и прозрачной. Добавление возможностей не должно изменять основную структуру. Мы можем просто добавить расширения типа файловой структуры или добавить уровень оптимизации. Я считаю, что когда ресурсы были ограничены, структуры, которые люди получали, были искусственно искажены чтобы заставить их работать в этих условиях, и не были оптимальными структурами для имеющейся проблемы.
