АДДИТИВНЫЕ ВЫРАЖЕНИЯ

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

Хорошо, что мы уже имеем модель для работы с этими более сложными выражениями. Все, что мы должны сделать, это удостовериться, что все процедуры, вызываемые Expression, (Term, Factor и т.д.) всегда возвращают идентификатор типа. Если мы сделаем это, то структура программы едва ли вообще изменится.

Первый шаг прост: мы должны переименовать нашу существующую версию Expression в Term, как мы делали много раз раньше и создать новую версию Expression:

{---------------------------------------------------------------}

{ Parse and Translate an Expression }

function Expression: char;

var Typ: char;

begin

if IsAddop(Look) then

      Typ := Unop

   else

      Typ := Term;

   while IsAddop(Look) do begin

      Push(Typ);

      case Look of

       '+': Typ := Add(Typ);

       '-': Typ := Subtract(Typ);

      end;

   end;

   Expression := Typ;

end;

{--------------------------------------------------------------}

Обратите внимание, как в этой подпрограмме каждый вызов процедуры стал вызовом функции и как локальная переменная Typ модифицируется при каждом проходе.

Обратите внимание также на новый вызов функции Unop, которая позволяет нам работать с ведущим унарным минусом. Это изменение не является необходимым... мы все еще можем использовать форму более похожую на ту, что мы использовали ранее. Я решил представить Unop как отдельную подпрограмму потому что позднее это позволит производить несколько лучший код, чем мы делали. Другими словами, я смотрю вперед на проблему оптимизации.

Для этой версии, тем не менее, мы сохраним тот же самый примитивный старый код, который делает новую подпрограмму тривиальной:

{---------------------------------------------------------------}

{ Process a Term with Leading Unary Operator }

function Unop: char;

begin

   Clear;

   Unop := 'W';

end;

{---------------------------------------------------------------}

Процедура Push - это подпрограмма генерации кода, которая теперь имеет параметр, указывающий тип:

{---------------------------------------------------------------}

{ Push Primary onto Stack }

procedure Push(Size: char);

begin

   Move(Size, 'D0', '-(SP)');

end;

{---------------------------------------------------------------}

Теперь давайте взглянем на функции Add и Subtract. В более старых версиях этих подпрограмм мы позволяем им вызывать подпрограммы генерации кода PopAdd и PopSub. Мы продолжим делать это, что делает сами функции чрезвычайно простыми:

{---------------------------------------------------------------}

{ Recognize and Translate an Add }

function Add(T1: char): char;

begin

   Match('+');

   Add := PopAdd(T1, Term);

end;

{-------------------------------------------------------------}

{ Recognize and Translate a Subtract }

function Subtract(T1: char): char;

begin

   Match('-');

   Subtract := PopSub(T1, Term);

end;

{---------------------------------------------------------------}

Но простота обманчива, поскольку мы переложили всю логику на PopAdd и PopSub, которые больше не являются просто подпрограммами генерации кода. Они также должны теперь заботиться о необходимых преобразованиях типов.

Какие это преобразования? Простые: оба аргумента должны иметь тот же самый размер  и результат также такой размер. Меньший из двух параметров должен быть "приведен" до размера большего.

Но это представляет небольшую проблему. Если переводимый параметр - второй (т.е. в основном регистре D0) мы в отличной форме. Если же нет, мы в затруднении: мы не можем изменить размер данных, которые уже затолкнуты в стек.

Решение простое, но немного болезненное: мы должны отказаться от этих красивых инструкций "вытолкнуть данные и что-нибудь с ними сделать", заботливо предоставленных Motorola.



Альтернативой является назначение вторичного регистра, в качестве которого я выбрал R7. (Почему не R1? Потому, что для других регистров у меня есть планы на будущее.)

Первый шаг в этой новой структуре - представить процедуру Pop, аналогичную Push. Эта процедура будет всегда выталкивать верхний элемент стека в D7:

{---------------------------------------------------------------}

{ Pop Stack into Secondary Register }

procedure Pop(Size: char);

begin

   Move(Size, '(SP)+', 'D7');

end;

{---------------------------------------------------------------}

Общая идея состоит в том, что все "Pop-Op" подпрограммы могут вызывать ее. Когда это сделано, мы будем иметь оба операнда в регистрах, поэтому мы можем перевести любой нужный нам. Для работы процедуре Convert необходим другой аргумент, имя регистра:

{---------------------------------------------------------------}

{ Convert a Data Item from One Type to Another }

procedure Convert(Source, Dest: char; Reg: String);

begin

   if Source <> Dest then begin

      if Source  = 'B' then

         EmitLn('AND.W #$FF,' + Reg);

      if Dest = 'L' then

         EmitLn('EXT.L ' + Reg);

   end;

end;

{---------------------------------------------------------------}

Следующая функция выполняет преобразование, но только если текущий тип T1 меньше по размеру, чем желаемый тип T2. Это функция, возвращающая конечный тип, позволяющий нам знать, что она решила:

{---------------------------------------------------------------}

{ Promote the Size of a Register Value }

function Promote(T1, T2: char; Reg: string): char;

var Typ: char;

begin

   Typ := T1;

   if T1 <> T2 then

      if (T1 = 'B') or ((T1 = 'W') and (T2 = 'L')) then begin

         Convert(T1, T2, Reg);



         Typ := T2;

      end;

   Promote := Typ;

end;

{---------------------------------------------------------------}

Наконец, следующая функция приводит два регистра к одному типу:

{---------------------------------------------------------------}

{ Force both Arguments to Same Type }

function SameType(T1, T2: char): char;

begin

   T1 := Promote(T1, T2, 'D7');

   SameType := Promote(T2, T1, 'D0');

end;

{---------------------------------------------------------------}

Эти новые подпрограммы дают нам заряд, необходимы нам чтобы разложить PopAdd и PopSub:

{---------------------------------------------------------------}

{ Generate Code to Add Primary to the Stack }

function PopAdd(T1, T2: char): char;

begin

   Pop(T1);

   T2 := SameType(T1, T2);

   GenAdd(T2);

   PopAdd := T2;

end;

{---------------------------------------------------------------}

{ Generate Code to Subtract Primary from the Stack }

function PopSub(T1, T2: char): char;

begin

   Pop(T1);

   T2 := SameType(T1, T2);

   GenSub(T2);

   PopSub := T2;

end;

{---------------------------------------------------------------}

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

Обратите внимание на две новые подпрограммы генерации кода GenAdd и GenSub. Они являются остаточной формой оригинальных PopAdd и PopSub. Т.е. они являются чистыми генераторами кода, производящими сложение и вычитание регистров:

{---------------------------------------------------------------}

{ Add Top of Stack to Primary }

procedure GenAdd(Size: char);

begin

   EmitLn('ADD.' + Size + ' D7,D0');

end;



{---------------------------------------------------------------}

{ Subtract Primary from Top of Stack }

procedure GenSub(Size: char);

begin

   EmitLn('SUB.' + Size + ' D7,D0');

   EmitLn('NEG.' + Size + ' D0');

end;

{---------------------------------------------------------------}

ОК, я соглашусь с вами: я выдал вам множество подпрограмм с тех пор, как мы в последний раз протестировали код. Но вы должны признать, что каждая новая подпрограмма довольно проста и ясна. Если вам (как и мне) не нравится тестировать так много новых подпрограмм одновременно все в порядке. Вы можете заглушить подпрограммы типа Convert, Promote и SameType так как они не считывают входной поток. Вы не получите корректный код, конечно, но программа должна работать. Затем постепенно расширяйте их.

При тестировании программы не забудьте, что  вы сначала должны объявить некоторые переменные а затем начать "тело" программы с "B" в верхнем регистре (для BEGIN). Вы должны обнаружить, что синтаксический анализатор обрабатывает любые аддитивные выражения. Как только все подпрограммы преобразования будет введены, вы должны увидеть, что генерируется правильный код и код для преобразования типов вставляется в нужных местах. Попробуйте смешивать переменные различных размеров а также литералы. Удостоверьтесь, что все работает правильно. Как обычно, хорошо было бы попробовать некоторые ошибочные выражения и посмотреть, как компилятор обрабатывает их.

БОЛЕЕ ПРИЕМЛЕМОЕ РЕШЕНИЕ

Как мы видели, перевод каждой переменной в длинное слово пока она находится в памяти решает проблему, но это едва ли может быть названо эффективным и, возможно, не было бы приемлемым даже для тех из нас, кто требует не обращать внимания на эффективность. Это означает, что все арифметические операции будут выполняться с 32-битной точностью, что удвоит время выполнения для большинства операций и сделает его еще больше для умножения и деления. Для этих операций мы должны были бы вызывать подпрограммы, даже если данные были бы байтом или словом. Все это слишком походит на уловку, так как уводит нас от всех настоящих проблем.

ОК, значит это решение плохое. Есть ли еще относительно простой способ получить преобразование данных? Можем ли мы все еще сохранять простоту?

Да, действительно. Все, что нам нужно сделать - выполнить преобразование с другого конца... т.е. мы выполняем преобразование на выходе, когда данные сохраняются, а не на входе.

Но запомните, часть присваивания, отвечающая за хранение, в значительной степени независима от загрузки данных, о которой заботится процедура Expression.     Вообще, выражение может быть произвольно сложным, поэтому как может процедура Assignment знать, какой тип данных оставлен в регистре D0?

Снова, ответ прост: Мы просто спросим об этом процедуру Expression! Ответ может быть возвращен как значение функции.

Все это требует изменения некоторых процедур, но эти изменения, как и сам метод, совсем простые. Прежде всего, так как мы не требуем чтобы LoadVar выполнял всю работу по преобразованию, давайте возвратимся к простой версии:

{---------------------------------------------------------------}

{ Load a Variable to Primary Register }

procedure LoadVar(Name, Typ: char);

begin

   Move(Typ, Name + '(PC)', 'D0');

end;

{--------------------------------------------------------------}

Затем, давайте добавим новую процедуру, которая будет выполнять преобразование из одного типа в другой:

{---------------------------------------------------------------}

{ Convert a Data Item from One Type to Another }

procedure Convert(Source, Dest: char);

begin

   if Source <> Dest then begin

      if Source  = 'B' then

         EmitLn('AND.W #$FF,D0');

      if Dest = 'L' then

         EmitLn('EXT.L D0');

   end;

end;

{--------------------------------------------------------------}

Затем, мы должны реализовать логику, требуемую для загрузки и сохранения переменной любого типа. Вот подпрограммы для этого:

{---------------------------------------------------------------}

{ Load a Variable to the Primary Register }

function Load(Name: char): char;

var Typ : char;

begin

   Typ := VarType(Name);

   LoadVar(Name, Typ);

   Load := Typ;

end;

{--------------------------------------------------------------}

{ Store a Variable from the Primary Register }

procedure Store(Name, T1: char);

var T2: char;

begin

   T2 := VarType(Name);

   Convert(T1, T2);

   StoreVar(Name, T2);

end;

Обратите внимание, что Load является функцией, которая не только выдает код для загрузки, но также возвращает тип переменной. Таким образом, мы всегда знаем, с каким типом данных мы работаем. Когда мы выполняем Store, мы передаем ей текущий тип переменной в D0. Так как Store также знает тип переменной назначения, она может выполнить преобразование необходимым образом.

Вооруженная всеми этими новыми подпрограммами, реализация нашего элементарного присваивания по существу тривиальна. Процедура Expression теперь становится функцией возвращающей тип выражения в процедуру Assignment:

{---------------------------------------------------------------}

{ Parse and Translate an Expression }

function Expression: char;

begin

   Expression := Load(GetName);

end;

{--------------------------------------------------------------}



{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

   Name := GetName;

   Match('=');

   Store(Name, Expression);

end;

{--------------------------------------------------------------}

Снова, заметьте как невероятно просты эти две подпрограммы. Мы изолировали всю логику типа в Load и Store и хитрость с передачей типа делает остальную работу чрезвычайно простой. Конечно, все это для нашего специального, тривиального случая с Expression. Естественно, для общего случая это будет более сложно. Но теперь вы смотрите на финальную версию процедуры Assignment!

Все это выглядит как очень простое и ясное решение, и действительно это так. Откомпилируйте эту программу и выполните те же самые тесты, что и ранее. Вы увидите, что все типы данных преобразованы правильно и здесь немного, если вообще есть, зря потраченных инструкций. Только преобразование "байт длинное слово" использует две инструкции когда можно было бы использовать одну, и мы могли бы легко изменить Convert для обработки этого случая.

Хотя мы в этом случае не рассматривали переменные без знака, я думаю вы можете видеть, что мы могли бы легко исправить процедуру Convert для работы и с этими типами. Это "оставлено как упражнение для студента".

БУЛЕВА АЛГЕБРА

Следующий шаг, как мы изучили несколько раз до этого, это добавление булевой алгебры. В прошлом этот шаг по крайней мере удваивал количество кода, который мы должны были написать. Когда я прошел эти шаги в своем уме, я обнаружил, что отклоняюсь все больше и больше от того, что мы делали в предыдущих главах. Чтобы освежить вашу память, я отметил, что Паскаль обрабатывает булевы операторы в значительной степени идентично способу, которым он обрабатывает арифметические операторы.     Булево "and" имеет тот же самый уровень приоритета, что и умножение, а "or" то же что сложение. Си, с другой стороны, устанавливает их на различных уровнях приоритета, которые занимают 17 уровней.  В нашей более ранней работе я выбрал что-то среднее, с семью уровнями. В результате, мы закончили на чем-то называющемся булевыми выражениями, соответствующим в большинстве деталей арифметическим выражениям, но на другом уровне приоритета. Все это, как оказалось, возникло потому, что мне не хотелось помещать скобки вокруг булевых выражений в утверждениях типа:

    IF (c >= 'A') and (c <= 'Z') then ...

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

Чтобы оттолкнуться, давайте начнем заново, применяя более Паскаль подобный подход  и просто обрабатывая булевы операторы на том же самом уровне приоритетов что и арифметические. Мы увидим, куда это нас приведет. Если это окажется тупиком, мы всегда сможем возвратиться к предыдущему подходу.

С начала, мы добавим в Expression операторы "уровня сложения". Это легко сделать; во-первых, измените функцию IsAddop в модуле Scanner чтобы включить два дополнительных оператора: '|' для "или" и "~" для "исключающее или":

{--------------------------------------------------------------}

function IsAddop(c: char): boolean;

begin

 IsAddop := c in ['+','-', '|', '~'];

end;

{--------------------------------------------------------------}

Затем, мы должны включить анализ операторов в процедуру Expression:

{--------------------------------------------------------------}

procedure Expression;

begin

 SignedTerm;

 while IsAddop(Look) do

  case Look of

   '+': Add;

   '-': Subtract;

   '|': _Or;

   '~': _Xor;

  end;

end;

{--------------------------------------------------------------}

(Символы подчеркивания необходимы, конечно, потому что "or" and "xor" являются зарезервированными словами Turbo Pascal).

Затем процедуры _Or and _Xor:

{--------------------------------------------------------------}

{ Parse and Translate a Subtraction Operation }

procedure _Or;

begin

 Match('|');

 Push;

 Term;

 PopOr;

end;

{--------------------------------------------------------------}

{ Parse and Translate a Subtraction Operation }

procedure _Xor;

begin

 Match('~');

 Push;

 Term;

 PopXor;

end;

{--------------------------------------------------------------}

И, наконец, новые процедуры генерации кода:

{--------------------------------------------------------------}

{ Or TOS with Primary }

procedure PopOr;

begin

 EmitLn('OR (SP)+,D0');

end;

{--------------------------------------------------------------}

{ Exclusive-Or TOS with Primary }

procedure PopXor;

begin

 EmitLn('EOR (SP)+,D0');

end;

{--------------------------------------------------------------}

Теперь давайте протестируем транслятор (вы возможно захотите изменить вызов в Main обратно на вызов Expression просто чтобы избежать необходимости набирать каждый раз "x=" для присваивания).

Пока все хорошо. Синтаксический анализатор четко обрабатывает выражения вида:

    x|y~z

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



    (a+b)*(c~d)

Мы говорили об этом немного в прошлом. Вообще, правила какие операции допустимы а какие нет не могут быть применены самим синтаксическим анализатором, потому что они не являются частью синтаксиса языка, а скорее его семантики. Компилятор, который не разрешает смешанные выражения такого вида должен распознать, что c и d являются булевыми переменными а не числовыми и передумать об их умножении на следующем шаге. Но такая "охрана" не может быть выполнена синтаксическим анализатором; она должна быть обработана где-то между синтаксическим анализатором и генератором кода. Мы пока не в таком положении, чтобы устанавливать такие правила, потом что у нас нет способа ни объявления типов, ни таблицы идентификаторов для сохранения в ней типов. Так что, для того что у нас на данный момент работает, синтаксический анализатор делает точно то, что он предназначен делать.

В любом случае, уверены ли мы, что не хотим разрешить операции над смешанными типами? Некоторое время назад мы приняли решение (или по крайней мере я принял) чтобы принимать значение 0000 как логическую "ложь" и -1 или FFFFh как логическую "истину". Хорошо в этом выборе то, что побитовые операции работают точно таким же способом, что и логические. Другими словами, когда мы выполняем операцию с одним битом логической переменной, мы делаем это над всеми из них. Это означает, что мы не должны делать различия между логическими и поразрядными операциями, как это сделано в C операторами & и &&, и | и ||. Уменьшение числа операторов наполовину конечно не выглядит совсем плохим.

С точки зрения данных в памяти, конечно, компьютер и компилятор не слишком интересуются, представляет ли число FFFFh логическую истину или число -1. Должны ли мы? Я думаю что нет. Я могу придумать множество примеров (хотя они могут быть рассмотрены как "мудреный" код) где возможность смешивать типы могла бы пригодиться. Пример, функция дельты Дирака, которая могла бы быть закодирована в одной простой строке:



    -(x=0)

или функция абсолютного значения (определенно сложный код!):

    x*(1+2*(x<0))

Пожалуйста, заметьте, что я не защищаю программирование подобным образом как стиль жизни. Я почти обязательно написал бы эти функции в более читаемой форме, используя IF, только для того, чтобы защитить от запутывания того, кто будет сопровождать программу в будущем. Все же возникает моральный вопрос: Имеем ли мы право осуществлять наши идеи о хорошей практике кодирования на программисте, написав язык так, чтобы он не смог сделать что-нибудь не так? Это то, что сделал Никлаус Вирт во многих местах Паскаля и Паскаль критиковался за это - как не такой "прощающий" как Си.

Интересная параллель представлена в примере дизайна Motorola 68000. Хотя Motorola громко хвастается об ортогональности их набора инструкций, факт то, что он является далеко не ортогональным. К примеру, вы можете считать переменную по ее адресу:

    MOVE X,D0 (где X это имя переменной)

но вы не можете записать ее таким же образом. Для записи вы должны загрузить в регистр адреса адрес X. То же самое остается истиной и для PC-относительной адресации.

    MOVE X(PC),DO (допустимо)

    MOVE

D0,X(PC) (недопустимо)

Когда вы начинаете спрашивать, как возникло такое не ортогональное поведение, вы находите, что кто-то в Motorola имел некоторые теории о том, как должно писаться программное обеспечение. В частности, в этом случае они решили, что самомодифицирующийся код, который вы можете реализовать, используя PC-относительные записи - Плохая Вещь. Следовательно, они разработали процессор, запрещающий это. К сожалению, по ходу дела они также запретили все записи в форме, показанной выше, даже полезные. Заметьте, что это было не что-то, сделанное по умолчанию. Должна была быть сделана дополнительная дизайнерская работа, добавлены дополнительные ограничения для уничтожения естественной ортогональности набора инструкций.

Один из уроков, которым я научился в жизни: Если у вас есть два выбора и вы не можете решить которому их них последовать, иногда самое лучшее - не делать ничего. Зачем добавлять дополнительные ограничители в процессор, чтобы осуществить чужие представления о хорошей практике программирования? Оставьте эти инструкции и позвольте программистам поспорить что такое хорошая практика программирования. Точно так же, почему мы должны добавлять дополнительный код в наш синтаксический анализатор для проверки и предупреждения условий, которые пользователь мог бы предпочесть использовать? Я предпочел бы оставить компилятор простым и позволить программным экспертам спорить, должна ли такая практика использоваться или нет.



Все это служит как объяснение моего решения как избежать смешанной арифметики: я не буду ее избегать. Для языка, предназначенного для системного программирования, чем меньше правил, тем лучше. Если вы не согласны, и хотите выполнять проверку на такие условия, мы сможем сделать это, когда у нас будет таблица идентификаторов.

    БУЛЕВО "AND"

С это небольшой философией, мы можем приступить к оператору "and", который пойдет в процедуру Term. К настоящему времени вы возможно сможете сделать это без меня, но в любом случае вот код:

В Scanner:

{--------------------------------------------------------------}

function IsMulop(c: char): boolean;

begin

 IsMulop := c in ['*','/', '&'];

end;

{--------------------------------------------------------------}

в Parser:

{--------------------------------------------------------------}

procedure Term;

begin

 Factor;

 while IsMulop(Look) do

  case Look of

   '*': Multiply;

   '/': Divide;

   '&': _And;

  end;

end;

{--------------------------------------------------------------}

{ Parse and Translate a Boolean And Operation }

procedure _And;

begin

 Match('&');

 Push;

 Factor;

 PopAnd;

end;

{--------------------------------------------------------------}

и в CodeGen:

{--------------------------------------------------------------}

{ And Primary with TOS }

procedure PopAnd;

begin

 EmitLn('AND (SP)+,D0');

end;

{--------------------------------------------------------------}

Ваш синтаксический анализатор теперь должен быть способен обрабатывать почти любые виды логических выражений а также (если вы хотите) и смешанные выражения.

Почему не "все виды логических выражений"? Потому что пока мы не имели дела с логическим оператором "not" и с ним все становится сложнее. Логический оператор "not" кажется на первый взгляд идентичным в своем поведении унарному минусу, поэтому моей первой мыслью было позволить оператору исключающего или, '~', дублировать унарный "not". Это не работало. При моей первой попытке процедура SignedTerm просто съедала мой '~' потому что символ проходил проверку на addop но SignedTerm игнорировал все addop за исключением "-". Было бы достаточно просто добавить другую строку в SignedTerm, но это все равно не решит проблему, потому что, заметьте, Expression принимает терм со знаком только для первого аргумента.



Математически, выражение типа:

    -a * -b

имеет небольшой или совсем никакого смысла и синтаксический анализатор должен отметить его как ошибку. Но то же самое выражение, использующее логическое "not",  имеет точный смысл:

    not a and not b

В случае с этими унарными операторами выбор заставить их работать таким же самым способом кажется искусственным принуждением, жертвованием приемлемым поведением на алтаре простоты реализуемости. Хотя я полностью за сохранение реализации настолько простой, насколько возможно, я не думаю, что мы должны делать это за счет приемлемости. Исправления подобные этому, приведут к потере основной детали, которая заключается в том, чтобы логическое "not" просто не является тем же самым что унарный минус. Рассмотрим исключающее "or", которое обычно записывается так:

    a~b ::= (a and not b) or (not a and b)

Если мы разрешим "not" изменять весь терм, последний терм в круглых скобках интерпретировался бы как:

    not(a and b)

что совсем не то же самое. Так что ясно, что о логическом "not" нужно думать как о связанном с показателем а не термом.

Идея перегрузки оператор '~' не имеет смысла и с математической точки зрения. Применение унарного минуса эквивалентно вычитанию из нуля:

    -x <=> 0-x

Фактически, в одной из моих более простых версий Expression я реагировал на ведущий addop просто предзагружая нуль, затем обрабатывая оператор как если бы это был двоичный оператор. Но "not" это не эквивалент исключающему или с нулем... которое просто возвратит исходное число. Вместо этого, это исключающее или с FFFFh или -1.

Короче говоря, кажущаяся близость между унарным "not" и унарным минусом разваливается при более близком исследовании. "not" изменяет показатель а не терм и он не имеет отношения ни к унарному минусу, ни исключающему или. Следовательно, он заслуживает своего собственного символа для вызова. Какой символ лучше, чем очевидный, также используемый в Си символ "!"? Используя правила того как мы думаем должен вести себя "not", мы должны быть способны закодировать исключающее или (предполагая что это нам когда-нибудь понадобится) в очень естественной форме:



    a & !b | !a & b

Обратите внимание, что никаких круглых скобок не требуется - выбранные нам уровни приоритета автоматически заботятся обо всем.

Если вы продолжаете учитывать уровни приоритета, это определение помещает '!' на вершину кучи. Уровни становятся:

1.      !

2.      (унарный)

3.      *, /, &

4.      +, -, |, ~

Рассматривая этот список, конечно не трудно увидеть, почему мы имели проблему при использовании '~' как символа "not"!

Так, как мы механизируем эти правила? Таким же самым способом, как мы сделали с SignedTerm, но на уровне показателя. Мы определим процедуру NotFactor:

{--------------------------------------------------------------}

{ Parse and Translate a Factor with Optional "Not" }

procedure NotFactor;

begin

 if Look ='!' then begin

  Match('!');

  Factor;

  Notit;

  end

 else

  Factor;

end;

{--------------------------------------------------------------}

и вызовем ее из всех мест, где мы прежде вызывали Factor, т.е. из Term, Multiply, Divide и _And. Обратите внимание на новую процедуру генерации кода:

{--------------------------------------------------------------}

{ Bitwise Not Primary }

procedure NotIt;

begin

 EmitLn('EOR #-1,D0');

end;

{--------------------------------------------------------------}

Испытайте ее сейчас с несколькими простыми случаями. Фактически, попробуйте пример с исключающим или:

    a&!b|!a&b

Вы должны получить код (без комментариев, конечно):

     MOVE A(PC),DO  ; load a

     MOVE D0,-(SP)  ; push it

     MOVE B(PC),DO  ; load b

     EOR #-1,D0     ; not it

     AND (SP)+,D0   ; and with a

     MOVE D0,-(SP)  ; push result



     MOVE A(PC),DO  ; load a

     EOR #-1,D0     ; not it

     MOVE D0,-(SP)  ; push it

     MOVE B(PC),DO  ; load b

     AND (SP)+,D0   ; and with !a

     OR (SP)+,D0    ; or with first term

Это точно то, что мы хотели получить. Так что, по крайней мере, и для арифметических и для логических операторов наш новый приоритет и новый, более тонкий синтаксис, поддерживают друг друга. Даже специфическое, но допустимое выражение с ведущим addop:

    ~x

имеет смысл. SignedTerm игнорирует ведущий '~' как и должно быть, так как выражение эквивалентно:

    0~x,

что эквивалентно x.

Когда мы взглянем на созданные нами БНФ, мы обнаружим, что наша булева алгебра добавляет теперь только одну дополнительную строку:

    <not_factor>   ::= [!] <factor>

    <factor>       ::= <variable> | <constant> | '(' <expression> ')'

    <signed_term>  ::= [<addop>] <term>

    <term>         ::= <not_factor> (<mulop> <not_factor>)*

    <expression>   ::= <signed_term> (<addop> <term>)*

    <assignment>   ::= <variable> '=' <expression>

Это большое улучшение предыдущих достижений. Будет ли сохраняться наша удача когда мы примемся за операторы отношений? Мы выясним это скоро, но мы должны будем дождаться следующей главы. У нас выдалась подходящая пауза и я хочу выдать эту главу в ваши руки. Уже прошел год с выпуска Главы 15. Я боюсь признаться, что вся эта текущая глава была готова уже давно, за исключением операторов отношений. Но эта информация совсем не дает вам ничего хорошего, сидя на моем жестком диске, и удерживая ее пока операторы отношений не будут сделаны, я не давал ее в ваши руки все это время. Пришло время выдать ее чтобы вы смогли получить из нее что-нибудь ценное. Кроме того, имеется большое количество серьезных философских вопросов, связанных с операторами отношений, и я предпочел бы сохранить их для отдельной главы, где я смог бы сделать это корректно.

Развлекайтесь с новой более тонкой арифметикой и логическим анализом а я скоро увижу вас с отношениями.

 

БУЛЕВА ЛОГИКА

Следующий шаг также должен быть вам знаком. Мы должны добавить булевы выражения и операторы отношений. Снова, так как мы работали с ними не один раз, я не буду подробно разбирать их за исключением моментов, в которых они отличаются от того, что мы делали прежде. Снова, мы не будем просто копировать их из других файлов потому что я немного изменил некоторые вещи. Большинство изменений просто включают изоляцию машинно-зависимых частей как мы делали для арифметических операций. Я также несколько изменил процедуру NotFactor для соответствия структуре FirstFactor. Наконец я исправил ошибку в объектном коде для операторов отношений: в инструкции Scc я использовал только младшие 8 бит D0. Нам нужно установить логическую истину для всех 16 битов поэтому я добавил инструкцию для  изменения младшего байта.

Для начала нам понадобятся несколько подпрограмм распознавания:

{--------------------------------------------------------------}

{ 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;

{--------------------------------------------------------------}

Также нам понадобятся несколько подпрограмм генерации кода:

{---------------------------------------------------------------}

{ Complement the Primary Register }

procedure NotIt;

begin

   EmitLn('NOT 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;

{---------------------------------------------------------------}

Все это дает нам необходимые инструменты. БНФ для булевых выражений такая:

     <bool-expr> ::= <bool-term> ( <orop> <bool-term> )*

     <bool-term> ::= <not-factor> ( <andop> <not-factor> )*

     <not-factor> ::= [ '!' ] <relation>

     <relation> ::= <expression> [ <relop> <expression> ]

Зоркие читатели могли бы заметить, что этот синтаксис не включает нетерминал "bool-factor" используемый в ранних версиях. Тогда он был необходим потому, что я также разрешал булевы константы TRUE и FALSE. Но не забудьте, что в TINY нет никакого различия между булевыми и арифметическими типами... они могут свободно смешиваться. Так что нет нужды в этих предопределенных значениях... мы можем просто использовать -1 и 0 соответственно.



В терминологии C мы могли бы всегда использовать определения:

     #define TRUE -1

     #define FALSE 0

 (Так было бы, если бы TINY имел препроцессор.)  Позднее, когда мы разрешим объявление констант, эти два значения будут предопределены языком.

Причина того, что я заостряю на этом ваше внимание, в том что я пытался использовать альтернативный путь, который заключался в использовании TRUE и FALSE как ключевых слов. Проблема с этим подходом в том, что он требует лексического анализа каждого имени переменной в каждом выражении. Как вы помните, я указал в главе 7, что это значительно замедляет компилятор. Пока ключевые слова не могут быть в выражениях нам нужно выполнять сканирование только в начале каждого нового оператора... значительное улучшение. Так что использование вышеуказанного синтаксиса не только упрощает синтаксический анализ, но также ускоряет сканирование.

Итак, если мы удовлетворены синтаксисом, представленным выше, то соответствующий код показан ниже:

{---------------------------------------------------------------}

{ Recognize and Translate a Relational "Equals" }

procedure Equals;

begin

   Match('=');

   Expression;

   PopCompare;

   SetEqual;

end;

{---------------------------------------------------------------}

{ Recognize and Translate a Relational "Not Equals" }

procedure NotEquals;

begin

   Match('#');

   Expression;

   PopCompare;

   SetNEqual;

end;

{---------------------------------------------------------------}

{ Recognize and Translate a Relational "Less Than" }

procedure Less;

begin

   Match('<');

   Expression;

   PopCompare;

   SetLess;

end;

{---------------------------------------------------------------}

{ Recognize and Translate a Relational "Greater Than" }

procedure Greater;

begin

   Match('>');



   Expression;

   PopCompare;

   SetGreater;

end;

{---------------------------------------------------------------}

{ Parse and Translate a Relation }

procedure Relation;

begin

   Expression;

   if IsRelop(Look) then begin

      Push;

      case Look of

       '=': Equals;

       '#': NotEquals;

       '<': 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;

{--------------------------------------------------------------}

Чтобы связать все это вместе не забудьте изменить обращение к Expression в процедурах Factor и Assignment на вызов BoolExpression.

Хорошо, если вы набрали все это, откомпилируйте и погоняйте эту версию. Сначала удостоверьтесь, что вы все еще можете анализировать обычные арифметические выражения. Затем попробуйте булевские. Наконец удостоверьтесь, что вы можете присваивать результат сравнения. Попробуйте к примеру:

     pvx,y,zbx=z>ye.

что означает

     PROGRAM

     VAR X,Y,Z

     BEGIN

     X = Z > Y

     END.

Видите как происходит присваивание булевского значения X?

ЧТО БУДЕТ ДАЛЬШЕ?

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

Тем временем я не бездействовал. Я разбил компилятор на модули. Одна из проблем, с которыми я столкнулся, в том, что так как мы охватывали новые области и вследствие этого расширяли возможности компилятора TINY, он становился все больше и больше. Я понял пару глав назад, что это приводило к затруднениям и именно поэтому я возвратился к использованию только фрагментов компилятора в последней и этой главах. Кажется просто глупо заново воспроизводить код для, скажем, обработки булевых исключающих ИЛИ, когда тема дискуссии - передача параметров.

Очевидным способом получит свой пирог и съесть его также является разбиение компилятора на раздельно компилируемые модули и, конечно, модули Turbo Pascal являются для этого идеальным средством. Это позволит нам скрыть некоторый довольно сложный код (такой как полный синтаксический анализ арифметических и булевых выражений) в одиночный модуль и просто вытаскивать его всякий раз когда он необходим. При таком способе единственным кодом, который я должен буду воспроизводить в этих главах, будет код который непосредственно касается обсуждаемого вопроса.

Я также игрался с Turbo 5.5 который, конечно, включает Борландовские объектно-ориентированные расширения Паскаля. Я не решил, использовать ли эти возможности, по двум причинам. Прежде всего, многие из вас, кто следовал за этой серией, могут все еще не иметь 5.5 и я конечно не хочу вынуждать кого-либо пойти и купить новый компилятор только для того, чтобы завершить эту серию. Во-вторых, я не убежден, что ОО расширения имеют такое большое значение для этого приложения. Мы обсуждали кое-что из этого на форуме CLM  на CompuServe, и пока что мы не нашли никакой убедительной причины для использования ОО конструкции. Это одна из тех областей, где я мог бы использовать некоторую обратную связь с читателями. Кто-нибудь хочет проголосовать за  Turbo 5.5 и ООП?

    В любом случае после следующих нескольких глав этой серии я планирую предоставить вам законченный набор модулей а также законченные функционирующие компиляторы. Планом фактически предусмотрено три компилятора: один для одно-символьной версии TINY (для использования в наших экспериментах), один для TINY и один для KISS. Я достаточно четко выделил различия между TINY и KISS:

·         TINY будет поддерживать только два типа данных: символьный и 16-разрядное целое число. Я могу также попробовать сделать что-нибудь со строками, так как без них компилятор был бы довольно бесполезным. KISS будет поддерживать все обычные простые типы, включая массивы и даже числа с плавающей точкой.

·         TINY будет иметь только две управляющие конструкции IF и WHILE. KISS будет поддерживать очень богатый набор конструкций включая одну, которую мы не обсуждали здесь ранее... CASE.

·         KISS будет поддерживать раздельно компилируемые модули.

    Одно предостережение: так как я все еще не знаю достаточно об ассемблере для 80x86, все эти модули компилятора все еще будут написаны для поддержки кода 68000. Однако в программах, которые я планирую вам представить, вся генерация кода была тщательно изолирована в отдельном модуле, так что любой предприимчивый студент смог бы перенастроить их на любой другой процессор. Эта задача "оставлена как упражнение для студента". Я сделаю предложение прямо здесь и сейчас: с человеком, который предоставит нам первый надежный перевод для 80x86, я буду счастлив обсудить коллективные авторские права и авторские отчисления от предстоящей книги.

Но хватит говорить. Давайте приступим к изучению типов. Как я сказал ранее, мы будем делать это как и в последней главе: выполняя эксперименты с использованием одно-символьных токенов.

ЧТО НЕПРАВИЛЬНО?

Тут вы могли бы подумать: Уверен, здесь должно быть что-то большее чем несколько сохранений и восстановлений из стека. Для передачи параметров здесь должно быть что-то большее чем тут есть.

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

Самая явная оплошность в том, что он неправильный! Если вы оглянетесь на код для вызова процедур, вы увидите, что вызывающая подпрограмма помещает каждый фактический параметр в стек перед тем, как она вызывает процедуру. Процедура использует эту информацию, но она не изменяет указатель стека. Это означает, что содержимое все еще остается там когда мы возвращаемся. Кто-то должен очистить стек или мы скоро окажемся в очень трудной ситуации!

К счастью, это легко исправить. Все, что мы должны сделать - это увеличить указатель стека когда мы закончим.

Должны ли мы делать это в вызывающей программе или в вызываемой процедуре? Некоторые люди позволяют вызываемой процедуре очищать стек, так как требуется генерировать меньше кода на вызов и так как процедура, в конце концов, знает сколько параметров она получила. Но это означает, что она должна что-то делать с адресом возврата чтобы не потерять его.

Я предпочитаю разрешить очистку в вызывающей программе, так что вызываемая процедура должна только выполнить возврат. Также это кажется немного более сбалансированным так как именно вызывающая программа первой "засорила" стек. Но это означает, что вызывающая программа должна запоминать сколько элементов помещено в стек. Чтобы сделать проще, я изменил процедуру ParamList на функцию, возвращающую количество помещенных байт:

{--------------------------------------------------------------}

{ Process the Parameter List for a Procedure Call }

function ParamList: integer;

var N: integer;

begin

     N := 0;

     Match('(');

     if Look <> ')' then begin

          Param;

          inc(N);

          while Look = ',' do begin

               Match(',');

               Param;

               inc(N);

          end;

     end;

     Match(')');

     ParamList := 2 * N;

end;

{--------------------------------------------------------------}

Процедура CallProc затем использует его для очистки стека:

{--------------------------------------------------------------}

{ Process a Procedure Call }

procedure CallProc(Name: char);

var N: integer;

begin

     N := ParamList;

     Call(Name);

     CleanStack(N);

end;

{--------------------------------------------------------------}

Здесь я создал еще одну подпрограмму генерации кода:

{--------------------------------------------------------------}

{ Adjust the Stack Pointer Upwards by N Bytes }

procedure CleanStack(N: integer);

begin

     if N > 0 then begin

          Emit('ADD #');

          WriteLn(N, ',SP');

     end;

end;

{--------------------------------------------------------------}

ОК, если вы добавили этот код в ваш компилятор, я думаю вы убедитесь, что стек теперь под контролем.

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

    PROCEDURE FOO(A, B)



    BEGIN

         A = A + B

    END

Код, сгенерированный нехитрым синтаксическим анализатором, мог бы быть:

    FOO: MOVE 6(SP),D0       ; Извлечь A

         MOVE D0,-(SP)       ; Сохранить его

         MOVE 4(SP),D0       ; Извлечь B

         ADD (SP)+,D0        ; Добавить A

         MOVE D0,6(SP)       : Сохранить A

         RTS

Это было бы неправильно. Когда мы помещаем первый аргумент в стек, смещения для двух формальных параметров больше не 4 и 6, я 6 и 8. Поэтому вторая выборка вернула бы снова A а не B.

Но это не конец света. Я думаю, вы можете видеть, что все, что мы должны делать - изменять смещение каждый раз, когда мы помещаем в стек и что фактически и делается если ЦПУ не имеет поддержки других методов.

К счастью, все же, 68000 имеет такую поддержку. Поняв, что этот ЦПУ мог бы использоваться со многими компиляторами языков высокого уровня, Motorola решила добавить прямую поддержку таких вещей.

Проблема, как вы можете видеть в том, что когда процедура выполняется, указатель стека скачет вверх и вниз, и поэтому использование его как ссылки для доступа к формальным параметрам становится неудобным. Решение состоит в том, чтобы вместо него определить и использовать какой-то другой регистр. Этот регистр обычно устанавливается равным подлинному указателю стека и называется указателем кадра.

Команда LINK из набора инструкций 68000 позволяет вам объявить такой указатель кадра и установить его равным указателю стека и все это в одной команде.     Фактически, она делает даже больше чем это. Так как этот регистр может использоваться для чего-то еще в вызывающей процедуре, LINK также помещает текущее значение регистра в стек. Вы можете также добавить значение к указателю стека чтобы создать место для локальных переменных.



В дополнение к LINK есть UNLK, которая просто восстанавливает указатель стека и выталкивает старое значение обратно в регистр.

С использованием этих двух команд код для предыдущего примера станет:

    FOO: LINK A6,#0

         MOVE 10(A6),D0      ; Извлечь A

         MOVE D0,-(SP)       ; Сохранить его

         MOVE 8(A6),D0       ; Извлечь B

         ADD (SP)+,D0        ; Добавить A

         MOVE D0,10(A6)      : Сохранить A

         UNLK A6

         RTS

Исправить компилятор для генерации этого кода намного проще чем объяснить. Все, что нам нужно сделать - изменить генерацию кода в DoProc. Так как из-за этого код становится немного больше одной строки, я создал новые процедуры, схожие с процедурами Prolog и Epilog, вызываемыми DoMain:

{--------------------------------------------------------------}

{ Write the Prolog for a Procedure }

procedure ProcProlog(N: char);

begin

     PostLabel(N);

     EmitLn('LINK A6,#0');

end;

{--------------------------------------------------------------}

{ Write the Epilog for a Procedure }

procedure ProcEpilog;

begin

     EmitLn('UNLK A6');

     EmitLn('RTS');

end;

{--------------------------------------------------------------}

Процедура DoProc теперь просто вызывает их:

{--------------------------------------------------------------}

{ Parse and Translate a Procedure Declaration }

procedure DoProc;

var N: char;

begin

     Match('p');

     N := GetName;



     FormalList;

     Fin;

     if InTable(N) then Duplicate(N);

     ST[N] := 'p';

     ProcProlog(N);

     BeginBlock;

     ProcEpilog;

     ClearParams;

end;

{--------------------------------------------------------------}

В заключение, мы должны изменить ссылки на SP в процедурах LoadParam и StoreParam:

{--------------------------------------------------------------}

{ Load a Parameter to the Primary Register }

procedure LoadParam(N: integer);

var Offset: integer;

begin

     Offset := 8 + 2 * (NumParams - N);

     Emit('MOVE ');

     WriteLn(Offset, '(A6),D0');

end;

{--------------------------------------------------------------}

{ Store a Parameter from the Primary Register }

procedure StoreParam(N: integer);

var Offset: integer;

begin

     Offset := 8 + 2 * (NumParams - N);

     Emit('MOVE D0,');

     WriteLn(Offset, '(A6)');

end;

{--------------------------------------------------------------}

 (Заметьте, что вычисление Offset изменяется чтобы учесть дополнительное сохранение A6.)

Это все что требуется.  Попробуйте и посмотрите как вам это нравится.

К этому моменту мы генерируем некоторый относительно хороший код для процедур и вызовов процедур. С ограничениями, что нет никаких локальных переменных (пока) и не разрешено вложение процедур этот код именно то что нам нужно.

Все еще остается только одна небольшая проблема:

У нас нет способа возвратить результат в вызывающую программу!

Но это, конечно, не ограничение генерируемого нами кода, а ограничение, свойственное протоколу передачи по значению. Обратите внимание, что мы можем использовать формальные параметры любым способом внутри процедуры. Мы можем вычислять для них новое значение, использовать их как счетчики циклов (если бы мы имели циклы!) и т.д. Так что код делает то, что предполагается. Чтобы решить эту последнюю проблему мы должны рассмотреть альтернативный протокол.

ЦИКЛ FOR

Цикл FOR очень удобен, но он тяжел для трансляции. Не столько потому, что сама конструкция трудна... в конце концов это всего лишь цикл... но просто потому, что она трудна для реализации на ассемблере. Как только код придуман, трансляция достаточно проста.

Фаны Си любят цикл FOR этого языка (фактически он проще для кодирования), но вместо него я выбрал синтаксис очень похожий на синтаксис из старого доброго Бейсика:

     FOR <ident> = <expr1> TO <expr2> <block> ENDFOR

Сложность трансляции цикла "FOR" зависит от выбранного вами способа его реализации, от пути, которым вы решили определять правила обработки ограничений. Рассчитывается ли expr2 каждый раз при прохождении цикла, например, или оно обрабатывается как постоянное ограничение? Всегда ли вы проходите цикл хотя бы раз, как в Fortran, или нет. Все становится проще, если вы приверженец точки зрения что эта конструкция эквивалентна:

     <ident> = <expr1>

     TEMP = <expr2>

     WHILE <ident> <= TEMP

     <block>

     ENDWHILE

Заметьте, что с этим определением цикла <block> не будет выполнен вообще если <expr1> изначально больше чем <expr2>.

Код 68000, необходимый для этого, сложней чем все что мы делали до сих пор. Я сделал несколько попыток,  помещая и счетчик и верхний предел в стек, в регистры и т.д. В конечном итоге я остановился на гибридном варианте размещения, при котором счетчик помещается в памяти (поэтому он может быть доступен внутри цикла) а верхний предел - в стеке. Оттранслированный код получился следующий:

         

<ident>   ; получить имя счетчика цикла

         

<expr1>   ; получить начальное значение

          LEA <ident>(PC),A0 ; обратиться к счетчику цикла

          SUBQ #1,D0  ; предварительно уменьшить его

          MOVE D0,(A0)  ; сохранить его

         

<expr1>   ; получить верхний предел

          MOVE D0,-(SP)  ; сохранить его в стеке

      L1: LEA <ident>(PC),A0 ; обратиться к счетчику цикла

          MOVE (A0),D0  ; извлечь его в D0

          ADDQ #1,D0  ; увеличить счетчик

          MOVE D0,(A0)  ; сохранить новое значение

          CMP (SP),D0  ; проверить диапазон

          BLE L2   ; пропустить если D0 > (SP)

         

<block>

          BRA L1   ; цикл для следующего прохода

      L2: ADDQ #2,SP  ; очистить стек

Ничего себе! Это же куча кода... строка, содержащая <block>, кажется совсем потерявшейся. Но это лучшее из того, что я смог придумать. Я полагаю, чтобы вам помочь, вы должны иметь в виду что в действительности это всего лишь шестнадцать слов, в конце концов. Если кто-нибудь сможет оптимизировать это лучше, пожалуйста дайте мне знать.

Однако, подпрограмма анализа довольно проста теперь, когда у нас есть код:

{--------------------------------------------------------------}

{ 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;

   Match('e');

   EmitLn('BRA ' + L1);

   PostLabel(L2);

   EmitLn('ADDQ #2,SP');

end;

{--------------------------------------------------------------}

Так как в этой версии синтаксического анализатора у нас нет выражений, я использовал тот же самый прием что и для Condition и написал подпрограмму:

{--------------------------------------------------------------}

{ Parse and Translate an Expression }

{ This version is a dummy }

Procedure Expression;

begin

   EmitLn('<expr>');

end;

{--------------------------------------------------------------}

Испытайте его. Снова, не забудьте добавить вызов в Block. Так как у нас нет возможности ввода для фиктивной версии Expression, типичная входная строка будет выглядеть так:

     afi=bece

Хорошо, генерируется много кода, не так ли? Но, по крайней мере, это правильный код.

ДЕЛЕНИЕ

Случай с делением совсем не так симметричен. У меня также есть для вас некоторые плохие новости:

Все современные 16-разрядные процессоры поддерживают целочисленное деление. Спецификации изготовителей описывают эту операцию как 32 x 16 бит деление, означающее, что вы можете разделить 32-разрядное делимое на 16-разрядный делитель. Вот плохая новость:

Они вам лгут!!!

Если вы не верите в это, попробуйте разделить любое большое 32-разрядное число (это означает, что оно имеет ненулевые биты в старших 16 разрядах) на целое число 1. Вы гарантированно получите исключение переполнения.

Проблема состоит в том, что эта команда в действительности требует, чтобы получаемое частное вписывалось в 16-разрядный результат. Этого не случится, если делитель достаточно большой. Когда любое число делится на единицу, частное будет конечно тем же самым, что и делимое.

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

Подразумевает следующее:

·

Тип частного всегда должен быть того же самого типа, что и делимое. Он независим от делителя.

·         Несмотря на то, что ЦПУ поддерживает деление длинного слова, аппаратно предоставленной инструкции можно доверить только делимые байт и слово. Для делимых типа длинное слово нам необходима другая библиотечная подпрограмма, которая может возвращать длинный результат.

Это похоже на работу для другой таблицы, для суммирования требуемых действий:

T1 T2		B		W		L
B		Преобразовать D0 в W Преобразовать D7 в L DIVS Result = B		Преобразовать D0 в W Преобразовать D7 в L DIVS Result = W		Преобразовать D0 в L JSR DIV32 Result = L
W		Преобразовать D7 в L DIVS Result = B		Преобразовать D7 в L DIVS Result = W		Преобразовать D0 в L JSR DIV32 Result = L
L		Преобразовать D7 в L JSR DIV32 Result = B		Преобразовать D7 в L JSR DIV32 Result = W		JSR DIV32 Result = L

<
    ( Вы можете задаться вопросом, почему необходимо выполнять 32-разрядное деление, когда делимое, скажем, всего лишь байт. Так как число битов в результате может быть только столько, сколько и в делимом, зачем беспокоиться? Причина в том, что если делитель - длинное слово и в нем есть какие-либо установленные старшие разряды,  результат деления должен быть равен нулю. Мы не смогли бы получить его, если мы используем только младшее слово делителя)

Следующий код предоставляет корректную функцию для PopDiv:

{---------------------------------------------------------------}

{ Generate Code to Divide Stack by the Primary }

function PopDiv(T1, T2: char): char;

begin

   Pop(T1);

   Convert(T1, 'L', 'D7');

   if (T1 = 'L') or (T2 = 'L') then begin

      Convert(T2, 'L', 'D0');

      GenLongDiv;

      PopDiv := 'L';

      end

   else begin

      Convert(T2, 'W', 'D0');

      GenDiv;

      PopDiv := T1;

   end;

end;

{---------------------------------------------------------------}

    Две подпрограммы генерации кода:

{---------------------------------------------------------------}

{ Divide Top of Stack by Primary  (Word) }

procedure GenDiv;

begin

   EmitLn('DIVS D0,D7');

   Move('W', 'D7', 'D0');

end;

{---------------------------------------------------------------}

{ Divide Top of Stack by Primary (Long) }

procedure GenLongDiv;

begin

   EmitLn('JSR DIV32');

end;

{---------------------------------------------------------------}

Обратите внимание, мы предполагаем, что DIV32 оставляет результат (длинное слово) в D0.

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

ДОБАВЛЕНИЕ ПРИСВАИВАНИЙ

Раз у нас уже есть подпрограммы для выражений, мы могли бы также заменить "блоки" настоящими операциями присваивания. Мы уже делали это прежде, поэтому это не будет слишком трудно. Прежде, чем сделать этот шаг, однако,  мы должны исправить кое-что еще.

Скоро мы обнаружим, что наши однострочные "программы", которые мы здесь пишем, будут ограничивать наш стиль. В настоящее время у нас нет способа вылечить это, потому что наш компилятор не распознает символы конца строки, возврат каретки (CR) и перевод строки (LF). Поэтому перед продвижением дальше давайте заткнем эту дыру.

Существует пара способов для работы с CR/LF. Один (подход C/Unix) просто рассматривает их как дополнительные символы пробела и игнорирует их. Фактически это не такой плохой подход, но он приводит к странным результатам для нашего анализатора в его текущем состоянии. Если бы он считывал входной поток из исходного файла как любой уважающий себя настоящий компилятор, не было бы никаких проблем. Но мы считываем входной поток с клавиатуры и ожидаем, что должно что-то произойти, когда мы нажимаем клавишу Return. Этого не произойдет, если мы просто перескакиваем CR и LF (попробуйте это). Поэтому я собираюсь использовать здесь другой метод, который в конечном счете не обязательно является лучшим методом. Рассматривайте его как временную замену до тех пор, пока мы не двинемся дальше.

Вместо того, чтобы пропускать CR/LF, мы позволим синтаксическому анализатору двигаться вперед и отлавливать их, затем предоставлять их специальной процедуре, аналогичной SkipWhite, которая пропускает их только в определенных "допустимых" местах.

Вот эта процедура:

{--------------------------------------------------------------}

{ Skip a CRLF }

procedure Fin;

begin

   if Look = CR then GetChar;

   if Look = LF then GetChar;

end;

{--------------------------------------------------------------}

     Теперь добавьте два вызова Fin в процедуру Block следующим образом:

{--------------------------------------------------------------}

{ Recognize and Translate a Statement Block }

procedure Block(L: string);

begin

   while not(Look in ['e', 'l', 'u']) do begin

      Fin;

      case Look of

       'i': DoIf(L);

       'w': DoWhile;

       'p': DoLoop;

       'r': DoRepeat;

       'f': DoFor;

       'd': DoDo;

       'b': DoBreak(L);

       else Other;

      end;

      Fin;

 end;

end;

{--------------------------------------------------------------}

Теперь вы обнаружите, что можете использовать многострочные "программы". Единственное ограничение в том, что вы не можете отделять токены IF или WHILE от их предикатов.

Теперь мы готовы включить операторы присваивания. Просто замените вызов Other в процедуре Block на вызов Assignment и добавьте следующую процедуру, скопированную из одной нашей более ранней программы. Обратите внимание, что сейчас Assignment вызывает BoolExpression, поэтому мы можем присваивать логические переменные.

{--------------------------------------------------------------}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

   Name := GetName;

   Match('=');

   BoolExpression;

   EmitLn('LEA ' + Name + '(PC),A0');

   EmitLn('MOVE D0,(A0)');

end;

{--------------------------------------------------------------}

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

Эта глава и так получилась довольно длинной и она содержит довольно тяжелый материал, поэтому я решил оставить этот шаг до следующего раза, чтобы у вас было немного времени усвоить то, что мы сделали и вы были готовы начать на свежую голову.

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

ДОБАВЛЕНИЕ ЗАПИСЕЙ

Конечно, заполнение таблицы напрямую - довольно плохая практика и она не сможет хорошо нам послужить в будущем. То, что нам нужно, это процедура, добавляющая записи в таблицу. В то же самое время мы знаем, что нам будет необходимо тестировать таблицу для проверки, что мы не объявляем повторно переменную, которая уже используется (что легко может случиться при наличии всего 26 вариантов!). Для поддержки всего это введите следующие новые процедуры:

{--------------------------------------------------------------}

{ Report Type of a Variable }

function TypeOf(N: char): char;

begin

   TypeOf := ST[N];

end;

{--------------------------------------------------------------}

{ Report if a Variable is in the Table }

function InTable(N: char): boolean;

begin

   InTable := TypeOf(N) <> '?';

end;

{--------------------------------------------------------------}

{ Check for a Duplicate Variable Name }

procedure CheckDup(N: char);

begin

   if InTable(N) then Abort('Duplicate Name ' + N);

end;

{--------------------------------------------------------------}

{ Add Entry to Table }

procedure AddEntry(N, T: char);

begin

   CheckDup(N);

   ST[N] := T;

end;

{--------------------------------------------------------------}

Теперь измените три строки в основной программе следующим образом:

    AddEntry('A', 'a');

    AddEntry('P', 'b');

    AddEntry('X', 'c');

и запустите программу снова. Работает? Тогда у нас есть подпрограммы таблицы идентификаторов, необходимые для поддержки нашей работы с типами. В следующем разделе мы начнем их использовать на практике.

ДОРОГА ДОМОЙ

Пока что мы охватили синтаксический анализ и трансляцию арифметических выражений, булевых выражений и их комбинаций, связанных операторами отношений. Мы также сделали то же самое для управляющих конструкций. Во всем этом мы склонялись в основном к использованию нисходящего синтаксического анализа методом рекурсивного спуска, определение синтаксиса в БНФ и непосредственной генерации ассемблерного кода. Мы также изучили значение такого приема как одно-символьные токены. В последней главе мы работали с лексическим анализом и я показал вам простой но мощный способ преодоления одно-символьного барьера.

В течение всех этих исследований, я особенно выделял философию KISS... Keep It Simple, Sidney... и я надеюсь, что к настоящему времени вы поняли, насколько простыми могут в действительности быть эти вещи. Хотя наверняка имеются области в теории компиляции которые являются по настоящему пугающими, основной мыслью этой серии является то, что на практике вы можете просто вежливо обойти многие из этих областей. Если определение языка способствует этому или, как в этой серии, если вы можете определить язык по ходу дела, то возможно записать определение языка в БНФ с достаточным удобством. И, как мы видели, вы можете вывести процедуры синтаксического анализа из БНФ почти также быстро, как вы можете набирать на клавиатуре.

По мере того, как наш компилятор принимал некоторую форму, он приобретал больше частей, но каждая часть довольно мала и проста и очень похожа на все другие.

К этому моменту у нас есть многое из того, что составляет настоящий практический компилятор. Фактически, мы уже имеем все что нам нужно для создания игрушечного языка столь же мощного, как, скажем, Tiny Basic. В следующих двух главах мы пойдем вперед и определим этот язык.

Для завершения этой серии, у нас все еще есть несколько тем для раскрытия. Они включают:

·

Вызовы процедур, с параметрами и без.

·         Локальные и глобальные переменные.

·         Базовые типы, такие как символьные и целочисленные типы.

·         Массивы.

·         Строки.

·         Типы и структуры, определяемые пользователем.

·         Синтаксические анализаторы с деревьями и промежуточные языки.

·         Оптимизация.

Все это будет рассмотрено в будущих главах. Когда мы закончим, вы будете иметь все инструменты, необходимые для разработки и создания своего собственного языка и компиляторов для его трансляции.

Я не могу спроектировать эти языки для вас, но я могу дать некоторые комментарии и рекомендации. Я уже высказал некоторые из них в прошлых главах. Вы видели, например, какие управляющие структуры я предпочитаю.

Эти конструкции будут частью создаваемых мной языков. К этому моменту я представляю три языка, два из которых вы увидите в очередных главах:

TINY - минимальный, но пригодный для использования язык уровня Tiny Basic или Tiny C. Он не будет очень практичным, но будет достаточно мощным, чтобы позволить вам писать и запускать настоящие программы которые делают что-нибудь заслуживающее внимание.

KISS - язык, который я создаю для своего собственного использования. KISS предназначен быть языком системного программирования. Он не будет иметь строгого контроля типов или причудливых структур данных, но он будет поддерживать большинство вещей, которые я хочу делать с языком более высокого уровня (HOL), за исключением возможно написания компиляторов.

Я также играл в течение нескольких лет с идеей HOL-подобного ассемблера со структурными управляющими конструкциями и HOL-подобными операциями присваивания. Это фактически было стимулом для моего первоначального углубления в джунгли теории компиляции. Этот язык возможно никогда не будет создан просто потому, что я узнал, что проще реализовать язык типа KISS, который использует только подмножество инструкций ЦПУ. Как вы знаете, ассемблер может быть предельно причудливым и нерегулярным, и язык, который отображается в него один к одному, может быть настоящим вызовом. Однако я всегда чувствовал, что синтаксис, используемый в стандартных ассемблерах тупой... почему



      MOVE.L A,B

лучше или проще для трансляции, чем

      B=A?

Я думаю, было бы интересным упражнением разработка "компилятора" который дал бы программисту полный доступ и к контролю над полным набором инструкций ЦПУ, и позволил бы вам генерировать программы настолько же эффективные как язык ассемблер без болезненного изучения набора мнемоник. Это может быть сделано? Я не знаю. Настоящим вопросом может быть вопрос "будет ли полученный язык проще, чем ассемблер?" Если нет, то в нем нет никакого смысла. Я думаю, что это может быть сделано, но я полностью еще не уверен в том, как должен выглядеть синтаксис.

Возможно у вас есть некоторые комментарии  или предложения об этом. Буду рад услышать их.

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

ФУНКЦИИ

Есть еще только один распространенный вид показателей, поддерживаемый большинством языков: вызов функции. В действительности, нам пока слишком рано иметь дела с функциями, потому что мы еще не обращались к вопросу передачи параметров. Более того, "настоящий" язык должен включать механизм поддержки более чем одного типа, одним из которых должен быть тип функции. Мы не имеем также и этого. Но все же я хотел бы работать с функциями сейчас по двум причинам. Во-первых, это позволит нам превратить компилятор во что-то очень близкое к конечному виду и, во вторых, это раскроет новую проблему, о которой очень стоит поговорить.

До этого момента мы создавали то, что называется "предсказывающим синтаксическим анализатором". Это означает, что в любой точке мы можем, смотря на текущий предсказывающий символ, точно знать, что будет дальше. Но не в том случае когда мы добавляем функции. В каждом языке имеются некоторые правила присваивания имен, по которым составляется допустимый идентификатор. Наши правила пока просты, так как идентификатором является одна из букв "a"…"z". Проблема состоит в том, что имена переменных и имена функций подчиняются одним и тем же правилам. Поэтому как мы можем сказать кто из них кто? Один из способов требует, чтобы каждое из них было объявлено перед тем, как оно используется. Этот метод использует Pascal. Другой способ состоит в том, чтобы функция сопровождалась списком параметров (возможно пустым). Это правило, используемое в C.

Пока у нас нет механизма описания типов, давайте использовать правила C. Так как у нас также нет и механизма для работы с параметрами, мы можем поддерживать только пустые списки параметров, так что вызовы функций будут иметь следующую форму:

X().

Так как мы пока не работаем со списками параметров, для вызова функций не нужно ничего дополнительно, и необходимо только выдавать BSR (вызов) вместо MOVE.

Сейчас существуют две варианта для ветки "If IsAlpha" при проверке в процедуре Factor. Давайте обработаем их в отдельной процедуре. Изменим процедуру Factor следующим образом:

{---------------------------------------------------------------}

{ 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 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;

{---------------------------------------------------------------}

Откомпилируйте и протестируйте эту версию. Обрабатывает ли она все правильные выражения и корректно отмечает неправильные?

Важно отметить, что хотя наш анализатор больше не является предсказывающим анализаторов,  это немного или совсем не добавляет сложностей при использовании нами метода рекурсивного спуска. В том месте, где процедура Factor находит идентификатор (букву), она не знает, является ли он именем переменной или именем функции, ни выполняет ее обработку. Она просто передает его в Ident и оставляет этой процедуре на рассмотрение. Ident, в свою очередь, просто прячет идентификатор и затем считывает еще один символ для того, чтобы решить с каким типом идентификатора он имеет дело.

Запомните этот способ. Это очень мощное понятие и оно должно быть использовано всегда, когда вы встречаетесь с неоднозначной ситуацией,  требующей заглядывания вперед. Даже если вам нужно рассмотреть несколько символов вперед, принцип все еще будет работать.

ГРАММАТИКА

Некоторое время назад мы реализовали синтаксические уравнения БНФ для арифметических выражений фактически даже не записав их все в одном месте. Пришло время сделать это. Вот они:

<expression> ::= <unary op> <term> [<addop> <term>]*

     <term>       ::= <factor> [<mulop> factor]*

     <factor>     ::= <integer> | <variable> | ( <expression> )

(Запомните, преимущества этой грамматики в том, что она осуществляет такую иерархию приоритетов операторов, которую мы обычно ожидаем для алгебры.)

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

     <expression>    ::= <term> [<addop> <term>]*

     <term>          ::= <signed factor> [<mulop> factor]*

     <signed factor> ::= [<addop>] <factor>

     <factor>        ::= <integer> | <variable> | (<expression>)

Это возлагает обработку унарного минуса на Factor, которому он в действительности и принадлежит.

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

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

     <b-expression>::= <b-term> [<orop> <b-term>]*

     <b-term>      ::= <not-factor> [AND <not-factor>]*

     <not-factor>  ::= [NOT] <b-factor>

     <b-factor>    ::= <b-literal> | <b-variable> | (<b-expression>)

Заметьте, что в этой грамматике оператор AND аналогичен "*", а OR (и исключающее OR) - "+". Оператор NOT аналогичен унарному минусу. Эта иерархия не является абсолютным стандартом... некоторые языки, особенно Ada, обрабатывают все логические операторы как имеющие одинаковый уровень приоритета... но это кажется естественным.

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

     a * -b

или еще хуже:

     a - -b

не разрешены. В булевой алгебре наоборот, выражение

     a AND NOT b

имеет точный смысл и показанный синтаксис учитывает это.

ИНИЦИАЛИЗАТОРЫ

Пока мы работали с объявлениями данных, меня беспокоила одна вещь - то, что Pascal не позволяет инициализировать данные в объявлении. Эта возможность по общему признанию является своего рода излишеством, и ее может не быть в языке, который считается минимальным языком. Но ее также настолько просто добавить, что было бы позором не сделать этого. БНФ становится:

     <var-list> ::= <var> ( <var> )*

     <var> ::= <ident> [ = <integer> ]

Измените Alloc как показано ниже:

{--------------------------------------------------------------}

{ Allocate Storage for a Variable }

procedure Alloc(N: char);

begin

   Write(N, ':', TAB, 'DC ');

   if Look = '=' then begin

      Match('=');

      WriteLn(GetNum);

      end

   else

      WriteLn('0');

end;

{--------------------------------------------------------------}

Вот оно: инициализатор в шесть дополнительных строк Pascal.

Испытайте эту версию TINY и проверьте, что вы действительно можете задавать начальное значение переменных.

Ей богу, он начинает походить на настоящий компилятор! Конечно, он все еще ничего не делает, но выглядит хорошо, не так ли?

Перед тем как оставить этот раздел я должен подчеркнуть, что мы использовали две версии GetNum. Одна, более ранняя, возвращала символьное значение, одиночную цифру. Другая принимала многозначное целое число и возвращала целочисленное значение. Любая из них будет работать здесь, так как WriteLn поддерживает оба типа. Но нет никакой причины ограничивать себя одноразрядными значениями, так что правильной версией для использования будет та, которая возвращает целое число. Вот она:

{--------------------------------------------------------------}

{ Get a Number }

function GetNum: integer;

var Val: integer;

begin

   Val := 0;

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

   while IsDigit(Look) do begin

      Val := 10 * Val + Ord(Look) - Ord('0');

      GetChar;

   end;

   GetNum := Val;

end;

{--------------------------------------------------------------}

Строго говоря, мы должны разрешить выражения в поле данных инициализатора, или, по крайней мере, отрицательные значения. Сейчас давайте просто разрешим отрицательные значения изменив код для Alloc следующим образом:

{--------------------------------------------------------------}

{ Allocate Storage for a Variable }

procedure Alloc(N: char);

begin

   if InTable(N) then Abort('Duplicate Variable Name ' + N);

   ST[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;

{--------------------------------------------------------------}

Теперь у вас есть возможность инициализировать переменные отрицательными и/или многозначными значениями.

ИНТЕРПРЕТАТОР

Итак, теперь, когда вы знаете почему мы принялись за все это, давайте начнем.  Просто для того, чтобы дать вам практику, мы начнем с пустого Cradle и создадим транслятор заново. На этот раз, конечно, мы сможем двигаться немного быстрее.

Так как сейчас мы собираемся выполнять арифметические действия, то первое, что мы должны сделать – изменить функцию GetNum, которая до настоящего момента всегда возвращала символ (или строку). Лучше если сейчас она будет возвращать целое число. Сделайте копию Cradle (на всякий случай не изменяйте сам Cradle!!) и модифицируйте GetNum следующим образом:

{--------------------------------------------------------------}

{ Get a Number }

function GetNum: integer;

begin

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

   GetNum := Ord(Look) - Ord('0');

   GetChar;

end;

{--------------------------------------------------------------}

Затем напишите следующую версию Expression:

{---------------------------------------------------------------}

{ Parse and Translate an Expression }

function Expression: integer;

begin

   Expression := GetNum;

end;

{--------------------------------------------------------------}

И, наконец, вставьте

     Writeln(Expression);

в конец основной программы. Теперь откомпилируйте и протестируйте.

Все, что эта программа делает - это "анализ" и трансляция "выражения", состоящего из одиночного целого числа. Как обычно, вы должны удостовериться, что она обрабатывает числа от 0 до 9 и выдает сообщение об ошибке для чего-либо другого. Это не должно занять у вас много времени!

Теперь давайте расширим ее, включив поддержку операций сложения. Измените Expression так:

{---------------------------------------------------------------}

{ Parse and Translate an Expression }

function Expression: integer;

var Value: integer;

begin

   if IsAddop(Look) then

      Value := 0

   else

      Value := GetNum;

   while IsAddop(Look) do begin

      case Look of

       '+': begin

               Match('+');

               Value := Value + GetNum;

            end;

       '-': begin

               Match('-');

               Value := Value - GetNum;

            end;

      end;

   end;

   Expression := Value;

end;

{--------------------------------------------------------------}

Структура Expression, конечно, схожа с тем, что мы делали ранее, так что мы не будем иметь слишком много проблем при ее отладке. Тем не менее это была серьезная разработка, не так ли? Процедуры Add и Subtract исчезли! Причина в том, что для выполнения необходимых действий нужны оба аргумента операции. Я мог бы сохранить эти процедуры и передавать в них значение выражения на данный момент, содержащееся в Value. Но мне показалось более правильным оставить Value как строго локальную переменную, что означает, что код для Add и Subtract должен быть помещен вместе. Этот результат наводит на мысль, что хотя разработанная нами структура была хорошей и проверенной для нашей бесхитростной схемы трансляции, она возможно не могла бы использоваться с ленивой оценкой. Эту небольшую интересную новость нам возможно необходимо иметь в виду в будущем.

Итак, транслятор работает? Тогда давайте сделаем следующий шаг. Несложно понять, что процедура Term должна выглядеть также. Замените каждый вызов GetNum в функции Expression на вызов Term и затем наберите следующую версию Term:



{---------------------------------------------------------------}

{ Parse and Translate a Math Term }

function Term: integer;

var Value: integer;

begin

   Value := GetNum;

   while Look in ['*', '/'] do begin

      case Look of

       '*': begin

               Match('*');

               Value := Value * GetNum;

            end;

       '/': begin

               Match('/');

               Value := Value div GetNum;

            end;

      end;

   end;

   Term := Value;

end;

{--------------------------------------------------------------}

Теперь испробуйте. Не забудьте двух вещей: во-первых мы имеем дело с целочисленным делением, поэтому, например, 1/3 выдаст ноль. Во-вторых, даже если мы можем получать на выходе многозначные числа, входные числа все еще ограничены одиночной цифрой.

Сейчас это выглядит как глупое ограничение, так как мы уже видели как легко может быть расширена функция GetNum. Так что давайте исправим ее прямо сейчас. Вот новая версия:

{--------------------------------------------------------------}

{ Get a Number }

function GetNum: integer;

var Value: integer;

begin

   Value := 0;

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

   while IsDigit(Look) do begin

      Value := 10 * Value + Ord(Look) - Ord('0');

      GetChar;

   end;

   GetNum := Value;

end;

{--------------------------------------------------------------}



Если вы откомпилировали и протестировали эту версию интерпретатора, следующим шагом должна быть установка функции Factor, поддерживающей выражения в скобках. Мы задержимся немного дольше на именах переменных. Сначала измените ссылку на GetNum в функции Term, чтобы вместо нее вызывалась функция Factor. Теперь наберите следующую версию Factor:

{---------------------------------------------------------------}

{ Parse and Translate a Math Factor }

function Expression: integer; Forward;

function Factor: integer;

begin

   if Look = '(' then begin

      Match('(');

      Factor := Expression;

      Match(')');

      end

   else

       Factor := GetNum;

end;

{---------------------------------------------------------------}

Это было довольно легко, а? Мы быстро пришли к полезному интерпретатору.

ИСПОЛЬЗОВАНИЕ СТЕКА

В этом месте я собираюсь нарушить свое правило, что я не представлю что-либо сложное, пока это не будет абсолютно необходимо. Прошло достаточно много времени, чтобы не отметить проблему с генерируемым кодом. В настоящее время синтаксический анализатор использует D0 как «основной» регистр, и D1 для хранения частичной суммы. Эта схема работает отлично потому что мы имеем дело только с "addops" (“+” и “-”) и новое число прибавляется по мере появления. Но в общем форме  это не так. Рассмотрим, например выражение

     1+(2-(3+(4-5)))

Если мы поместим «1» в D1, то где мы разместим «2»? Так как выражение в общей форме может иметь любую степень сложности, то мы очень быстро используем все регистры!

К счастью есть простое решение. Как и все современные микропроцессоры, 68000 имеет стек, который является отличным местом для хранения переменного числа элементов. Поэтому вместо того, чтобы помещать термы в D0 и D1 давайте затолкнем их в стек. Для тех кто незнаком с ассемблером 68000 – помещение в стек пишется как

-(SP)

и извлечение  (SP)+.

Итак, изменим  EmitLn  в процедуре Expression на

EmitLn('MOVE D0,-(SP)');

и  две строки в Add и Subtract:

EmitLn('ADD (SP)+,D0') 

и

EmitLn('SUB (SP)+,D0')

соответственно. Теперь испытаем компилятор снова и удостоверимся что он работает.

И снова, полученный код менее эффективен, чем был до этого, но это необходимый шаг, как вы увидите.

ИСПРАВЛЕНИЕ ГРАММАТИКИ

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

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

Когда Никлаус Вирт разработал Паскаль, его желанием было ограничить количество уровней приоритета (меньше подпрограмм синтаксического анализа, в конце концов). Так операторы OR и исключающее OR рассматриваются просто как Addop и обрабатываются на уровне математического выражения. Аналогично AND рассматривается подобно Mulop и обрабатывается с Term. Уровни приоритета:

Уровень		Синтаксический элемент		Оператор
0		factor		literal, variable
1		signed factor		unary minus, NOT
2		term		*, /, AND
3		expression		+, -, OR

Заметьте, что имеется только один набор синтаксических правил, применимый к обоим видам операторов. Тогда согласно этой грамматике выражения типа:

x + (y AND NOT z) DIV 3

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

Авторы C взяли диаметрально противоположный метод: они обрабатывают операторы как разные и C имеет что-то гораздо более похожее на наши семь уровней приоритета. Фактически, в C имеется не менее 17 уровней! Дело в том, что C имеет также операторы '=', '+=' и их родственников '<<', '>>', '++', '--' и т.д. Как ни странно, хотя в C арифметические и булевы операторы обрабатываются раздельно, то переменные нет... в C нет никаких булевых или логических переменных, так что логическая проверка может быть сделана на любом целочисленном значении.

Мы сделаем нечто среднее. Я склонен обычно придерживаться Паскалевского подхода, так как он кажется самым простым с точки зрения реализации, но это приводит к некоторым странностям, которые я никогда очень сильно не любил, как например в выражении:

     IF (c >= 'A') and (c <= 'Z') then ...

скобки обязательны. Я никогда не мог понять раньше почему, и ни мой компилятор, ни любой человек также не объясняли этого достаточно хорошо. Но сейчас мы все можем видеть, что оператор "and", имеющий приоритет как у оператора умножения, имеет более высокий приоритет, чем у операторов отношения, поэтому без скобок выражение эквивалентно:

     IF c >= ('A' and c) <= 'Z' then

что не имеет смысла.

В любом случае, я решил разделить операторы на различные уровни, хотя и не столько много как в C.

     <b-expression> ::= <b-term> [<orop> <b-term>]*

     <b-term>       ::= <not-factor> [AND <not-factor>]*

     <not-factor>   ::= [NOT] <b-factor>

     <b-factor>     ::= <b-literal> | <b-variable> | <relation>

     <relation>     ::= | <expression> [<relop> <expression]

     <expression>   ::= <term> [<addop> <term>]*

     <term>         ::= <signed factor> [<mulop> factor]*

     <signed factor>::= [<addop>] <factor>

     <factor>       ::= <integer> | <variable> | (<b-expression>)

Эта грамматика приводит к тому же самому набору семи уровней, которые я показал ранее. Действительно, это почти та же самая грамматика... я просто исключил заключенное в скобки b-выражение как возможный b-показатель и добавил отношение как допустимую форму b-показателя.

Есть одно тонкое, но определяющее различие, которое заставляет все это работать. Обратите внимание на квадратные скобки в определении отношения. Это означает, что relop и второе выражение являются необязательными.

Странным последствием этой грамматики (которое присутствует и в C) является то, что каждое выражения потенциально является булевым выражение. Синтаксический анализатор всегда будет искать булевское выражение, но "уладит" все до арифметического. Честно говоря, это будет замедлять синтаксический анализатор потому что он должен пройти через большее количество вызовов процедур. Это одна из причин, почему компиляторы Паскаля обычно быстрее выполняют компиляцию, чем компиляторы C. Если скорость для вас - больное место, придерживайтесь синтаксиса Паскаля.

ИСПРАВЛЕНИЕ КОМПИЛЯТОРА

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

Прежде всего, код процедуры 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;

{--------------------------------------------------------------}

Не забудьте, что новая версия Scan не продвигает входной поток, она только сканирует ключевые слова. Входной поток должен продвигаться каждой процедурой, которую вызывает Block.

В общих чертах, мы должны заменить каждую проверку Look на аналогичную проверку Token. Например:

{---------------------------------------------------------------}

{ Parse and Translate a Boolean Expression }

procedure BoolExpression;

begin

   BoolTerm;

   while IsOrOp(Token) do begin

      Push;

      case Token of

       '|': BoolOr;

       '~': BoolXor;

      end;

   end;

end;

{--------------------------------------------------------------}

В процедурах типа Add мы больше не должны использовать Match. Нам необходимо только вызывать Next для продвижения входного потока:

{--------------------------------------------------------------}

{ Recognize and Translate an Add }

procedure Add;

begin

   Next;

   Term;

   PopAdd;

end;

{-------------------------------------------------------------}

Управляющие структуры фактически более простые. Мы просто вызываем Next для продвижения через ключевые слова управляющих конструкций:

{---------------------------------------------------------------}

{ 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;

{--------------------------------------------------------------}

Это все необходимые изменения. В листинге Tiny Version 1.1, данном ниже, я также сделал ряд других "усовершенствований", которые в действительности не нужны.       Позвольте мне кратко разъяснить их:

1.      Я удалил две процедуры Prog и Main и объединил их функции в основной программе. Они кажется не добавляли ясности... фактически они просто немного загрязняли программу.

2.      Я удалил ключевые слова PROGRAM и BEGIN из списка ключевых слов. Каждое из них появляется в одном месте, так что нет необходимости искать его.

3.      Обжегшись однажды на чрезмерной дозе сообразительности, я напомнил себе, что TINY  предназначен быть минималистским языком. Поэтому я заменил причудливую обработку унарного минуса на самую простую какую мог придумать. Гигантский шаг назад в качестве кода, но огромное упрощение компилятора. Для использования другой версии правильным местом был бы KISS.



4.      Я добавил несколько подпрограмм проверок ошибок типа CheckTable и CheckDup и заменил встроенный код на их вызовы. Это навело порядок во многих подпрограммах.

5.      Я убрал проверку ошибок из подпрограмм генерации кода типа Store и поместил их в подпрограммы анализа, к которым они относятся. Смотрите например Assignment.

6.      Существовала ошибка в InTable и Locate которая заставляла их проверять все позиции вместо позиций только с достоверными данными. Теперь они проверяют только допустимые ячейки. Это позволяет нам устранить необходимость инициализации таблицы идентификаторов, которая была в Init.

7.      Процедура AddEntry теперь имеет два параметра, что помогает сделать программу немного более модульной.

8.      Я подчистил код для операторов отношений добавив новые процедуры CompareExpression и  NextExpression.

9.      Я устранил ошибку в подпрограмме Read... старая версия не выполняла проверку на правильность имени переменной.

ЭКСПЕРИМЕНТЫ ПО СКАНИРОВАНИЮ

Прежде чем возвратиться к нашему компилятору, было бы полезно немного поэкспериментировать с общими понятиями.

Давайте начнем с двух определений, наиболее часто встречающихся в настоящих языках программирования:

<ident> ::= <letter> [ <letter> | <digit> ]*

     <number ::= [<digit>]+

 (Не забудьте, что "*" указывает на ноль или более повторений условия в квадратных скобках, а "+" на одно и более.)

Мы уже работали с подобными элементами в третьей главе. Давайте начнем (как обычно) с пустого Cradle. Не удивительно, что нам понадобится новая процедура распознавания:

{--------------------------------------------------------------}

{ Recognize an Alphanumeric Character }

function IsAlNum(c: char): boolean;

begin

   IsAlNum := IsAlpha(c) or IsDigit(c);

end;

{--------------------------------------------------------------}

Используя ее, давайте напишем следующие две подпрограммы, которые очень похожи на те, которые мы использовали раньше:

{--------------------------------------------------------------}

{ Get an Identifier }

function GetName: string;

var x: string[8];

begin

   x := '';

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

   while IsAlNum(Look) do begin

     x := x + UpCase(Look);

     GetChar;

   end;

   GetName := x;

end;

{--------------------------------------------------------------}

{ Get a Number }

function GetNum: string;

var x: string[16];

begin

   x := '';

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

   while IsDigit(Look) do begin

     x := x + Look;

     GetChar;

   end;

   GetNum := x;

end;

{--------------------------------------------------------------}

(Заметьте, что эта версия GetNum возвращает строку, а не целое число, как прежде).

Вы можете легко проверить что эти подпрограммы работают, вызвав их из основной программы:

     WriteLn(GetName);

Эта программа выведет любое допустимое набранное имя (максимум восемь знаков, потому что мы так сказали GetName). Она отвергнет что-либо другое.

Аналогично проверьте другую подпрограмму.

я тщательно избегал темы комментариев.

Вплоть до этого времени я тщательно избегал темы комментариев. Вы могли бы подумать, что это будет простая тема... в конце концов компилятор совсем не должен иметь дела с комментариями; он просто должен игнорировать их. Что ж, иногда это так.
Насколько простыми или насколько трудными могут быть комментарии, зависит от выбранного вами способа их реализации. В одном случае, мы можем сделать так, чтобы эти комментарии перехватывались как только они поступят в компилятор. В другом, мы можем обрабатывать их как лексические элементы. Станет интереснее когда вы рассмотрите вещи, типа разделителей комментариев, содержащихся в строках в кавычках.

КОМПРОМИСС

Теперь, когда мы знаем как работать с точками с запятой, означает ли это, что я собираюсь поместить их в KISS/TINY? И да и нет. Мне нравится дополнительный сахар и защита, которые приходят с уверенным знанием, где заканчиваются утверждения. Но я не изменил своей антипатии к ошибкам компиляции, связанным с точками с запятой.

Так что я придумал хороший компромисс: сделаем их необязательными!

Рассмотрите следующую версию Semi:

{--------------------------------------------------------------}

{ Match a Semicolon }

procedure Semi;

begin

   if Token = ';' then Next;

end;

{--------------------------------------------------------------}

Эта процедура будет принимать точку с запятой всякий раз, когда вызвана, но не будет настаивать на ней. Это означает, что когда вы решите использовать точки с запятой, компилятор будет использовать дополнительную информацию чтобы удержаться на правильном пути. Но если вы пропустите одну (или пропустите их всех) компилятор не будет жаловаться. Лучший из обоих миров.

Поместите эту процедуру на место в первую версию вашей программы (с синтаксисом для C/Ada)  и вы получите TINY Version 1.2.

КОНЕЧНЫЕ АВТОМАТЫ

Подпрограмма анализа типа GetName действительно реализует конечный автомат. Состояние неявно в текущей позиции в коде. Очень полезным приемом для визуализации того, что происходит, является синтаксическая диаграмма или "railroad-track" диаграмма. Немного трудно нарисовать их в этой среде, поэтому я буду использовать их очень экономно, но фигура ниже должна дать вам идею:

Как вы можете видеть, эта диаграмма показывает логические потоки по мере чтения символов. Начинается все, конечно, с состояния "start" и заканчивается когда найден символ, отличный от алфавитно-цифрового. Если первый символ не буква, происходит ошибка. Иначе автомат продолжит выполнение цикла до тех пор, пока не будет найден конечный разделитель.

Заметьте, что в любой точке потока наша позиция полностью зависит от предыдущей истории входных символов. В этой точке предпринимаемые действия зависят только от текущего состояния плюс текущий входной символ. Это и есть то, что образует конечный автомат.

Из-за сложностей представления "railroad-track" диаграмм в этой среде я буду продолжать придерживаться с этого времени синтаксических уравнений. Но я настоятельно рекомендую вам диаграммы для всего, что включает синтаксический анализ. После небольшой практики вы можете начать видеть, как написать синтаксический анализатор непосредственно из диаграммы. Параллельные пути кодируются в контролирующие действия (с помощью операторов IF или CASE),  последовательные пути - в последовательные вызовы.  Это почти как работа по схеме.

Мы даже не обсудили SkipWhite, которая была представлена раньше, но это также простой конечный автомат, как и GetNum. Так же как и их родительская процедура Scan. Маленькие автоматы образуют большие автоматы.

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

КОНЕЧНЫЕ АВТОМАТЫ И АЛЬТЕРНАТИВЫ

Я упомянул, что регулярные выражения могут анализироваться с использованием конечного автомата. В большинстве книг по компиляторам а также в большинстве компиляторов, вы обнаружите, что это применяется буквально. Обычно они имеют настоящую реализацию конечного автомата с целыми числами, используемыми для определения текущего состояния и таблицей действий, выполняемых для каждой комбинации текущего состояния и входного символа. Если вы пишите "front end" для компилятора, используя популярные Unix инструменты LEX и YACC, это то, что вы получите. Выход LEX - конечный автомат, реализованный на C плюс таблица действий, соответствующая входной грамматике данной LEX. Вывод YACC аналогичен... искусственный таблично управляемый синтаксический анализатор плюс таблица, соответствующая синтаксису языка.

Однако это не единственный вариант. В наших предыдущих главах вы много раз видели, что возможно реализовать синтаксические анализаторы специально не имея дела с таблицами, стеками и переменными состояния. Фактически в пятой главе я предупредил вас, что если вы считает себя нуждающимся в этих вещах, возможно вы делаете что-то неправильно и не используете возможности Паскаля. Существует в основном два способа определить состояние конечного автомата: явно, с номером или кодом состояния и неявно, просто на основании того факта, что я нахожусь в каком-то определенном месте кода (если сегодня вторник, то это должно быть Бельгия). Ранее мы полагались в основном на неявные методы, и я думаю вы согласитесь, что они работают здесь хорошо.

На практике может быть даже не обязательно иметь четко определенный лексический анализатор. Это не первый наш опыт работы с много символьными токенами. В третьей главе мы расширили наш синтаксический анализатор для их поддержки и нам даже не был нужен лексический анализатор. Причиной было то, что в узком контексте мы всегда могли сказать просто рассматривая единственный предсказывающий символ, имеем ли мы дело с цифрой, переменной или оператором. В действительности мы построили распределенный лексический анализатор, используя процедуры GetName и GetNum.

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

КРУГЛЫЕ СКОБКИ

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

     2*(3+4) ,

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

    

(1+2)/((3+4)+(5-6))

Ключом к встраиванию скобок в наш синтаксический анализатор является понимание того, что не зависимо от того, как сложно выражение,  заключенное в скобки, для остальной части мира оно выглядит как простой показатель. Это одна из форм для показателя:

     <factor> ::= (<expression>)

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

Сложно это или нет, мы должны позаботиться об этом, добавив несколько строчек в процедуру Factor:

{---------------------------------------------------------------}

{ Parse and Translate a Math Factor }

procedure Expression; Forward;

procedure Factor;

begin

   if Look = '(' then begin

      Match('(');

      Expression;

      Match(')');

      end

   else

      EmitLn('MOVE #' + GetNum + ',D0');

end;

{--------------------------------------------------------------}

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

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

ЛЕКСИЧЕСКИЙ АНАЛИЗ

Лексический анализ - это процесс сканирования потока входных символов и разделения его на строки, называемые лексемами. Большинство книг по компиляторам начинаются с этого и посвящают несколько глав обсуждению различных методов построения сканеров. Такой подход имеет свое место, но, как вы уже видели, существуют множество вещей, которые вы можете сделать даже никогда не обращавшись к этому вопросу, и, фактически, сканер, который мы здесь закончим, не очень будет напоминать то, что эти тексты описывают. Причина? Теория компиляторов и, следовательно, программы, следующие из нее, должны работать с большинством общих правил синтаксического анализа. Мы же не делаем этого. В реальном мире возможно определить синтаксис языка таким образом, что будет достаточно довольно простого сканера. И как всегда KISS - наш девиз.

Как правило, лексический анализатор создается как отдельная часть компилятора, так что синтаксический анализатор по существу видит только поток входных лексем. Теоретически нет необходимости отделять эту функцию от остальной части синтаксического анализатора. Имеется только один набор синтаксических уравнений, который определяет весь язык, поэтому теоретически мы могли бы написать весь анализатор в одном модуле.

Зачем необходимо разделение? Ответ имеет и теоретическую и практическую основы.

В 1956 Ноам Хомский определил "Иерархию Хомского" для грамматик. Вот они:

·         Тип 0. Неограниченные (например Английский язык)

·         Тип 1. Контекстно-зависимые

·         Тип 2. Контекстно-свободные

·         Тип 3. Регулярные.

Некоторые характеристики типичных языков программирования (особенно старых, таких как Фортран) относят их к Типу 1, но большая часть всех современных языков программирования может быть описана с использованием только двух последних типов и с ними мы и будем здесь работать.

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

Аналогично грамматики Типа 2 (контекстно-свободные) всегда могут быть анализированы с использованием магазинного автомата (конечный автомат, дополненный стеком). Мы также реализовывали эти машины. Вместо реализации явного стека для выполнения работы мы положились на встроенный стек связанный с рекурсивным кодированием и это фактически является предпочтительным способом для нисходящего синтаксического анализа.

Случается что в реальных, практических грамматиках части, которые квалифицируются как регулярные выражения, имеют склонность быть низкоуровневыми частями, как определение идентификатора:

     <ident> ::= <letter> [ <letter> | <digit> ]*

Так как требуется различные виды абстрактных машин для анализа этих двух типов грамматик, есть смысл отделить эти низкоуровневые функции в отдельный модуль, лексический анализатор, который строится на идее конечного автомата. Идея состоит в том, чтобы использовать самый простой метод синтаксического анализа, необходимый для работы.

Имеется другая, более практическая причина для отделения сканера от синтаксического анализатора. Мы хотим думать о входном исходном файле как потоке символов, которые мы обрабатываем справа налево без возвратов. На практике это невозможно. Почти каждый язык имеет некоторые ключевые слова типа IF, WHILE и END. Как я упомянул ранее, в действительности мы не можем знать является ли данная строка ключевым словом до тех пор пока мы не достигнем ее конца, что определено пробелом или другим разделителем. Так что мы должны хранить строку достаточно долго для того, чтобы выяснить имеем мы ключевое слово или нет. Это ограниченная форма перебора с возвратом.

Поэтому структура стандартного компилятора включает разбиение функций низкоуровневого и высокоуровневого синтаксического анализа. Лексический анализатор работает на символьном уровне собирая символы в строки и т.п., и передавая их синтаксическому анализатору как неделимые лексемы. Также считается нормальным позволить сканеру выполнять работу по идентификации ключевых слов.



         found := true

      else

         dec(i);

   Lookup := i;

end;

{--------------------------------------------------------------}

.

.

{--------------------------------------------------------------}

{ Get an Identifier and Scan it for Keywords }

procedure Scan;

begin

   GetName;

   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 + '''');

end;

{--------------------------------------------------------------}

Теперь мы должны сделать довольно много тонких изменений в оставшихся процедурах. Сначала мы должны изменить функцию GetName на процедуру, снова как в главе 7:

{--------------------------------------------------------------}

{ Get an Identifier }

procedure GetName;

begin

   NewLine;

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

   Value := '';

   while IsAlNum(Look) do begin

      Value := Value + UpCase(Look);

      GetChar;

   end;

   SkipWhite;

end;

{--------------------------------------------------------------}

Обратите внимание, что эта процедура оставляет свой результат в глобальной строковой переменной Value.

Затем, мы должны изменить каждую обращение к GetName чтобы отразить ее новую форму. Они происходят в Factor, Assignment и Decl:

{---------------------------------------------------------------}

{ 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[1]);

      end

   else

      LoadConst(GetNum);

end;

{--------------------------------------------------------------}

.

.

{--------------------------------------------------------------}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

   Name := Value[1];

   Match('=');

   BoolExpression;

   Store(Name);

end;

{---------------------------------------------------------------}

.

.

{--------------------------------------------------------------}

{ Parse and Translate a Data Declaration }

procedure Decl;

begin

   GetName;

   Alloc(Value[1]);

   while Look = ',' do begin

      Match(',');

      GetName;

      Alloc(Value[1]);

   end;

end;

{--------------------------------------------------------------}

 (Заметьте, что мы все еще разрешаем только одно-символьные имена переменных поэтому мы используем здесь простое решение и просто используем первый символ строки.)

Наконец, мы должны внести изменения, позволяющие использовать Token вместо Look как символа для проверки и вызывать Scan в подходящих местах. По большей части это включает удаление вызовов Match, редкие замены вызовов Match  на вызовы MatchString, и замену вызовов NewLine  на вызовы Scan.  Вот затронутые подпрограммы:

{---------------------------------------------------------------}

{ 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;

{--------------------------------------------------------------}

{ 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;

      else Assignment;

      end;

      Scan;

   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: char;

begin

   for i := 'A' to 'Z' do

      ST[i] := ' ';

   GetChar;

   Scan;

end;

{--------------------------------------------------------------}

Это должно работать. Если все изменения сделаны правильно, вы должны теперь анализировать программы, которые выглядят как программы. (Если вы не сделали всех изменений, не отчаивайтесь.  Полный листинг конечной формы дан ниже.)

Работает? Если да, то мы почти дома. Фактически, с несколькими небольшими исключениями, мы уже получили компилятор, пригодный для использования. Имеются еще несколько областей, требующих усовершенствования.

ЛЕКСИЧЕСКИЙ И СИНТАКСИЧЕСКИЙ АНАЛИЗ

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

Но даже хотя здесь и нет функциональной процедуры, названной "Scanner", все еще имеет смысл отделить функции лексического анализа от функций синтаксического анализа. Так что я создал еще два модуля, названных, достаточно удивительно, Scanner и Parser. Модуль Scanner содержит все подпрограммы, известные как распознаватели. Некоторые из них, такие как IsAlpha, являются чисто булевыми подпрограммами, которые оперируют только предсказывающим символом. Другие подпрограммы собирают токены, такие как идентификаторы и числовые константы. Модуль Parser будет содержать все подпрограммы, составляющие синтаксический анализатор с рекурсивным спуском. Общим правилом должно быть то, что модуль Parser содержит всю специфическую для языка информацию; другими словами, синтаксис языка должен полностью содержаться в Parser. В идеальном мире это правило должно быть верным в той степени, что мы можем изменять компилятор для компиляции различных языков просто заменяя единственный модуль Parser.

На практике, дела почти никогда не бывают такими чистыми. Все есть небольшая "утечка" синтаксических правил также и в сканер. К примеру, правила составления допустимого идентификатора или константы могут меняться от языка к языку. В некоторых языках правила о комментариях разрешают им быть отфильтрованными в сканере, в то время как другие не разрешают. Так что на практике оба модуля вероятно придут к тому, что будут иметь языко зависимые компоненты, но изменения, необходимые для сканнера, должны быть относительно тривиальными.

Теперь вспомните, что мы использовали две версии подпрограмм лексического анализатора: одна, которая поддерживала только одно-символьные токены, которую мы использовали в ряде наших тестов, и другая, которая предоставляет полную поддержку много символьных токенов. Теперь, когда мы разделяем нашу программу на модули, я не ожидаю многого от использования одно-символьной версии, но не потребуется многого, чтобы предусмотреть их обе. Я создал две версии модуля Scanner. Первая, названная Scanner1, содержит одно-символьную версию подпрограмм распознавания:

{--------------------------------------------------------------}

unit Scanner1;

{--------------------------------------------------------------}

interface

uses Input, Errors;

function IsAlpha(c: char): boolean;

function IsDigit(c: char): boolean;

function IsAlNum(c: char): boolean;

function IsAddop(c: char): boolean;

function IsMulop(c: char): boolean;

procedure Match(x: char);

function GetName: char;

function GetNumber: char;

{--------------------------------------------------------------}

implementation

{--------------------------------------------------------------}

{ Recognize an Alpha Character }

function IsAlpha(c: char): boolean;

begin

 IsAlpha := UpCase(c) in ['A'..'Z'];

end;

{--------------------------------------------------------------}

{ Recognize a Numeric Character }

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 Addition Operator }

function IsAddop(c: char): boolean;

begin

 IsAddop := c in ['+','-'];

end;

{--------------------------------------------------------------}

{ Recognize a Multiplication Operator }

function IsMulop(c: char): boolean;

begin



 IsMulop := c in ['*','/'];

end;

{--------------------------------------------------------------}

{ Match One Character }

procedure Match(x: char);

begin

 if Look = x then GetChar

 else Expected('''' + x + '''');

end;

{--------------------------------------------------------------}

{ Get an Identifier }

function GetName: char;

begin

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

 GetName := UpCase(Look);

 GetChar;

end;

{--------------------------------------------------------------}

{ Get a Number }

function GetNumber: char;

begin

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

 GetNumber := Look;

 GetChar;

end;

end.

{--------------------------------------------------------------}

Следующий фрагмент кода основной программы обеспечивает хорошую проверку лексического анализатора. Для краткости я включил здесь только выполнимый код; остальное тоже самое. Не забудьте, тем не менее, добавить имя Scanner1 в раздел "uses":

    Write(GetName);

    Match('=');

    Write(GetNumber);

    Match('+');

    WriteLn(GetName);

Этот код распознает все предложения вида:

    x=0+y

где x и y могут быть любыми одно-символьными именами переменных и 0 любой цифрой. Код должен отбросить все другие предложения и выдать осмысленное сообщение об ошибке. Если это произошло, тогда вы в хорошей форме и мы можем продолжать.

ЛИТЕРАЛЬНЫЕ АРГУМЕНТЫ

Зоркие читатели могли бы отметить, однако, что мы еще даже не имеем правильной формы простого показателя, потому что мы не разрешаем загрузку литеральных констант, только переменных. Давайте исправим это сейчас.

Для начала нам понадобится функция GetNum. Мы уже видели ее несколько версий, некоторые возвращают только одиночный символ, некоторые строку, а некоторые целое число. Та, которая нам здесь нужна будет возвращать длинное целое, так что она может обрабатывать все, что мы ей подбросим. Обратите внимание, что здесь не возвращается никакой информации о типах: GetNum не интересуется тем, как будет использоваться число:

{--------------------------------------------------------------}

{ Get a Number }

function GetNum: LongInt;

var Val: LongInt;

begin

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

   Val := 0;

   while IsDigit(Look) do begin

      Val := 10 * Val + Ord(Look) - Ord('0');

      GetChar;

   end;

   GetNum := Val;

   SkipWhite;

end;

{---------------------------------------------------------------}

Теперь, когда работаем с литералами, мы имеем одну небольшую проблему. С переменными мы знаем какого типа они должны быть потому что они были объявлены с таким типом. Мы не имеем такой информации о типе для литералов. Когда программист говорит "-1", означает ли это байт, слово или длинное слово? Мы не имеем никаких сведений. Очевидным способом было бы использование наиболее возможного типа, т.е. длинного слова. Но это плохая идея, потому что когда мы примемся за более сложные выражения, мы обнаружим, что это заставит каждое выражение, включающее литералы, также переводить в длинное.

Лучшим подходом было бы выбрать тип, основанный на значении литерала, как показано далее:

{--------------------------------------------------------------}

{ Load a Constant to the Primary Register }

function LoadNum(N: LongInt): char;

var Typ : char;

begin

   if abs(N) <= 127 then

      Typ := 'B'

   else if abs(N) <= 32767 then

      Typ := 'W'

   else Typ := 'L';

   LoadConst(N, Typ);

   LoadNum := Typ;

end;

{---------------------------------------------------------------}

 ( Я знаю, знаю, база числа не является в действительности симметричной. Вы можете хранить -128 в одиночном байте и -32768 в слове. Но это легко исправить и не стоит затраченного времени или дополнительной сложности возиться с этим сейчас. Стоящая мысль.)

Заметьте, что LoadNum вызывает новую версию подпрограммы генерации кода LoadConst, которая имеет дополнительный параметр для определения типа:

{---------------------------------------------------------------}

{ Load a Constant to the Primary Register }

procedure LoadConst(N: LongInt; Typ: char);

var temp:string;

begin

   Str(N, temp);

   Move(Typ, '#' + temp, 'D0');

end;

{--------------------------------------------------------------}

Теперь мы можем изменить процедуру Expression для использования двух возможных видов показателей:

{---------------------------------------------------------------}

{ Parse and Translate an Expression }

function Expression: char;

begin

   if IsAlpha(Look) then

      Expression := Load(GetName)

   else

      Expression := LoadNum(GetNum);

end;

{--------------------------------------------------------------}

 (Вау, это, уверен, не причинило слишком большого вреда! Всего несколько дополнительных строк  делают всю работу.)

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

ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ

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

И снова здесь мы стоим перед выбором: статическое или динамическое хранение?

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

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

Характерная особенность статического хранения в том, что данные выживают при вызове процедуры и возврате. Когда процедура вызывается снова, данные все еще будут здесь. Это может быть преимуществом в некоторых приложениях. Во времена FORTRAN мы применяли такой прием как инициализация флажка, чтобы вы могли сказать когда мы входим в процедуру первый раз и могли бы выполнить любую первоначальную инициализацию, которую необходимо выполнить.

Конечно, эта же "особенность" статического хранения делает рекурсию невозможной. Любое новое обращение к процедуре перепишет данные уже находящиеся в локальных переменных.

Альтернативой является динамическое хранение, при котором память распределяется в стеке точно также как и для переданных параметров. Для это мы уже имеем готовый механизм. Фактически, те же самые подпрограммы, которые работают с переданными (по значению) параметрами в стеке, могут так же легко работать и с локальными переменными... генерируемый код тот же самый. Назначение смещения в инструкции 68000 LINK сейчас такое: мы можем использовать его для регулировки указателя стека при выделении места для локальных переменных. Динамическое хранение, конечно, по существу поддерживает рекурсию.

Когда я впервые начал планировать TINY, я должен признаться имел предубеждение в пользу статического хранения. Просто потому, что старые FORTRAN программы были чрезвычайно эффективны... ранние компиляторы FORTRAN производили качественный код, который и сейчас редко сопоставим с современными компиляторами. Даже сегодня данная программа, написанная на FORTRAN, вероятно превзойдет, ту же самую программу, написанную на C или Pascal, иногда с большим отрывом. (Вот так! Что вы скажете на это заявление!)

Я всегда полагал, что причина имела отношение к двум основным различиям между реализациями Фортрана и другими языками: статическое хранение и передача по ссылке. Я знаю, что динамическое хранение поддерживает рекурсию, но мне всегда казалось немного странным желание мириться с более медленным кодом, который в 95% случаев не нуждается в рекурсии, только для того чтобы получить эту возможность когда она понадобится. Идея состоит в том, что со статическим хранением вы можете использовать не косвенную а абсолютную адресацию, которая должна привести к более быстрому коду. \

Позднее, однако, некоторые люди указали мне, что в действительности нет никаких падений производительности связанной с динамическим хранением. Для 68000, к примеру, вы в любом случае не должны использовать абсолютную адресацию... большинство операционных систем требуют переместимый код. И команда 68000

    MOVE 8(A6),D0

имеет тоже самое время выполнения, что и

    MOVE X(PC),D0.

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

Так как такое использование локальных переменных так хорошо соответствует схеме передачи параметров по значению, мы будем использовать эту версию транслятора для иллюстрации (я надеюсь вы сохранили копию!).

Основная идея состоит в том, чтобы отслеживать количество локальных параметров. Затем мы используем это число в инструкции LINK для корректировки указателя стека при выделения для них места. Формальные параметры адресуются как положительные смещения от указателя кадра а локальные как отрицательные смещения. С небольшой доработкой те же самые процедуры, которые мы уже создали, могут позаботиться обо всем этом.

Давайте начнем с создания новой переменной Base:

    var Base: integer;

Мы будем использовать эту переменную вместо NumParams для вычисления смещения стека. Это подразумевает изменение двух ссылок на NumParams в LoadParam и StoreParam:

{--------------------------------------------------------------}



{ Load a Parameter to the Primary Register }

procedure LoadParam(N: integer);

var Offset: integer;

begin

     Offset := 8 + 2 * (Base - N);

     Emit('MOVE ');

     WriteLn(Offset, '(A6),D0');

end;

{--------------------------------------------------------------}

{ Store a Parameter from the Primary Register }

procedure StoreParam(N: integer);

var Offset: integer;

begin

     Offset := 8 + 2 * (Base - N);

     Emit('MOVE D0,');

     WriteLn(Offset, '(A6)');

end;

{--------------------------------------------------------------}

Идея состоит в том, что значение Base будет заморожено после того, как мы обработаем формальные параметры и не будет увеличиваться дальше когда новые, локальные, переменные будут вставлены в таблицу идентификаторов.  Об этом позаботится код в конце FormalList:

{--------------------------------------------------------------}

{ Process the Formal Parameter List of a Procedure }

procedure FormalList;

begin

     Match('(');

     if Look <> ')' then begin

          FormalParam;

          while Look = ',' do begin

               Match(',');

               FormalParam;

          end;

     end;

     Match(')');

     Fin;

     Base := NumParams;

     NumParams := NumParams + 4;

end;

{--------------------------------------------------------------}

(Мы добавили четыре слова чтобы учесть адрес возврата и старый указатель кадра, который заканчивается между формальными параметрами и локальными переменными.)



Все что мы должны сделать дальше - это установить семантику объявления локальных переменных в синтаксическом анализаторе. Подпрограммы очень похожи на Decl и TopDecls:

{--------------------------------------------------------------}

{ Parse and Translate a Local Data Declaration }

procedure LocDecl;

var Name: char;

begin

   Match('v');

     AddParam(GetName);

     Fin;

end;

{--------------------------------------------------------------}

{ Parse and Translate Local Declarations }

function LocDecls: integer;

var n: integer;

begin

     n := 0;

     while Look = 'v' do begin

          LocDecl;

          inc(n);

     end;

     LocDecls := n;

end;

{--------------------------------------------------------------}

Заметьте, что LocDecls является функцией, возвращающей число локальных переменных в DoProc.

Затем мы изменим DoProc для использования этой информации:

{--------------------------------------------------------------}

{ Parse and Translate a Procedure Declaration }

procedure DoProc;

var N: char;

      k: integer;

begin

     Match('p');

     N := GetName;

     if InTable(N) then Duplicate(N);

     ST[N] := 'p';

     FormalList;

     k := LocDecls;

     ProcProlog(N, k);

     BeginBlock;

     ProcEpilog;

     ClearParams;

end;

{--------------------------------------------------------------}

 (Я сделал пару изменений, которые не были в действительности необходимы. Кроме небольшой реорганизации я переместил вызов Fin в FormalList а также в LocDecls. Не забудьте поместить его в конец FormalList.)

Обратите внимание на изменения при вызове ProcProlog. Новый параметр - это число слов (не байт) для распределения памяти. Вот новая версия ProcProlog:

{--------------------------------------------------------------}

{ Write the Prolog for a Procedure }

procedure ProcProlog(N: char; k: integer);

begin

     PostLabel(N);

     Emit('LINK A6,#');

     WriteLn(-2 * k)

end;

{--------------------------------------------------------------}

Сейчас должно работать. Добавьте эти изменения и посмотрите как они работают.

МНОГОСИМВОЛЬНЫЕ ИМЕНА ПЕРЕМЕННЫХ

Одна из них - ограничение, требующее использования одно-символьных имен переменных. Теперь, когда мы можем обрабатывать много символьные ключевые слова, это ограничение начинает казаться произвольным и ненужным. И действительно это так. В основном, единственное его достоинство в том, что он позволяет получить тривиально простую реализацию таблицы идентификаторов. Но это просто удобство для создателей компиляторов и оно должно быть уничтожено.

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

Естественным путем реализации таблицы идентификаторов на Pascal является объявление переменной типа запись и создание таблицы идентификаторов как массива таких записей. Здесь, однако, нам в действительности пока не нужно поле типа (существует пока что только один разрешенный тип), так что нам нужен только массив символов. Это имеет свое преимущество, потому что мы можем использовать существующую процедуру Lookup для поиска в таблице идентификаторов также как и в списке ключевых слов. Оказывается, даже когда нам нужны больше полей, мы все равно можем использовать тот же самый подход, просто сохраняя другие поля в отдельных массивах.

Вот изменения, которые необходимо сделать. С начала добавьте новую типизированную константу:

NEntry: integer = 0;

Затем измените определение таблицы идентификаторов как показано ниже:

const MaxEntry = 100;

var ST   : array[1..MaxEntry] of Symbol;

 (Обратите внимание, что ST не объявлен как SymTab. Это объявление липовое, чтобы заставить Lookup работать. SymTab заняли бы слишком много памяти и поэтому фактически никогда не объявляется).

Затем мы должны заменить InTable.

{--------------------------------------------------------------}

{ Look for Symbol in Table }

function InTable(n: Symbol): Boolean;

begin

   InTable := Lookup(@ST, n, MaxEntry) <> 0;

end;

{--------------------------------------------------------------}

Нам также необходима новая процедура AddEntry, которая добавляет новый элемент в таблицу:

{--------------------------------------------------------------}

{ Add a New Entry to Symbol Table }

procedure AddEntry(N: Symbol; T: char);

begin

   if InTable(N) then Abort('Duplicate Identifier ' + N);

   if NEntry = MaxEntry then Abort('Symbol Table Full');

   Inc(NEntry);

   ST[NEntry] := N;

   SType[NEntry] := T;

end;

{--------------------------------------------------------------}

Эта процедура вызывается из Alloc:

{--------------------------------------------------------------}

{ Allocate Storage for a Variable }

procedure Alloc(N: Symbol);

begin

   if InTable(N) then Abort('Duplicate Variable Name ' + N);

   AddEntry(N, 'v');

.

.

.

{--------------------------------------------------------------}

Наконец, мы должны изменить все подпрограммы, которые в настоящее время обрабатывают имена переменных как одиночный символ. Они включают LoadVar и Store (просто измените тип с char на string) и Factor, Assignment и Decl (просто измените Value[1] на Value).

Последняя вещь: измените процедуру Init для очистки массива как показано ниже:

{--------------------------------------------------------------}

{ Initialize }

procedure Init;

var i: integer;

begin

   for i := 1 to MaxEntry do begin

      ST[i] := '';

      SType[i] := ' ';

   end;

   GetChar;

   Scan;

end;

{--------------------------------------------------------------}

Это должно работать. Испытайте ее и проверьте, что вы действительно можете использовать много символьные имена переменных.

МНОГОСИМВОЛЬНЫЕ РАЗДЕЛИТЕЛИ

Все это хорошо для случаев, когда комментарии ограничены одиночными символами, но как быть с такими случаями как C или стандартный Pascal, где требуются два символа? Хорошо, принцип все еще тот же самый, но мы должны совсем немного изменить наш подход. Я уверен, что вы не удивитесь узнав, что это более сложный случай.

Для много символьной ситуации проще всего перехватывать левый ограничитель в GetChar.  Мы можем "токенизировать" его прямо здесь, заменяя его одиночным символом.

Давайте условимся, что мы используем ограничители C '/*' и '*/'. Сначала мы должны возвратиться к методу 'GetCharX'. В еще одной копии вашего компилятора переименуйте GetChar в GetCharX и затем введите следующую новую процедуру GetChar:

{--------------------------------------------------------------}

{ Read New Character.  Intercept '/*' }

procedure GetChar;

begin

   if TempChar <> ' ' then begin

      Look := TempChar;

      TempChar := ' ';

      end

   else begin

      GetCharX;

      if Look = '/' then begin

         Read(TempChar);

         if TempChar = '*' then begin

            Look := '{';

            TempChar := ' ';

         end;

      end;

   end;

end;

{--------------------------------------------------------------}

Как вы можете видеть эта процедура перехватывает каждое появление '/'. Затем она исследует следующий символ в потоке. Если это символ '*', то мы нашли начало комментария и GetChar возвратит его одно-символьный заменитель. (Для простоты я использую тот же самый символ '{' как я делал для Паскаля. Если бы вы писали компилятор C, вы без сомнения захотели бы использовать какой-то другой символ, не используемый где-то еще в C. Выберите что вам нравится... даже $FF, что-нибудь  уникальное).

Если символ, следующий за '/' не '*', тогда GetChar прячет его в новой глобальной переменной TempChar и возвращает '/'.

Обратите внимание, что вы должны объявить эту новую переменную и присвоить ей значение ' '. Мне нравится делать подобные вещи с использование конструкции "типизированная константа" в Turbo Pascal:

     const TempChar: char = ' ';

Теперь нам нужна новая версия SkipComment:

{--------------------------------------------------------------}

{ Skip A Comment Field }

procedure SkipComment;

begin

   repeat

      repeat

         GetCharX;

      until Look = '*';

      GetCharX;

   until Look = '/';

   GetChar;

end;

{--------------------------------------------------------------}

Обратите внимание на несколько вещей: прежде всего нет необходимости изменять функцию IsWhite и процедуру SkipWhite так как GetChar возвращает токен '{'. Если вы измените этот символ токена, тогда конечно вы также должны будете изменить символ в этих двух подпрограммах.

Во-вторых, заметьте, что SkipComment вызывает в своем цикле не GetChar а GetCharX. Это означает, что завершающий '/' не перехватывается и обрабатывается SkipComment. В-третьих, хотя работу выполняет процедура GetChar, мы все же можем работать с символами комментариев, вложенными в строки в кавычках,  вызывая GetCharX  вместо GetChar  пока мы находимся внутри строки. Наконец, заметьте, что мы можем снова обеспечить вложенные комментарии добавив одиночное утверждение в SkipComment, точно также как мы делали прежде.

МНОГОСИМВОЛЬНЫЕ ТОКЕНЫ.

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

Большинство компиляторов выделяют обработку входного потока в отдельный модуль, называемый лексическим анализатором (сканером).  Идея состоит в том, что сканер работает со всей последовательностью символов во входном потоке и возвращает отдельные единицы (лексемы) потока. Возможно придет время, когда мы также захотим сделать что-то вроде этого,  но сейчас в этом нет необходимости. Мы можем обрабатывать много символьные токены, которые нам нужны, с помощью небольших локальных изменений в GetName и GetNum.

Обычно признаком идентификатора является то, что первый символ должен быть буквой, но остальная часть может быть алфавитно-цифровой (буквы и цифры). Для работы с ними нам нужна другая функция:

{--------------------------------------------------------------}

{ Recognize an Alphanumeric }

function IsAlNum(c: char): boolean;

begin

   IsAlNum := IsAlpha(c) or IsDigit(c);

end;

{--------------------------------------------------------------}

Добавьте эту функцию в анализатор. Я поместил ее сразу после IsDigit. Вы можете также включить ее как постоянного члена в Cradle.

Теперь нам необходимо изменить функцию GetName так, чтобы она возвращала строку вместо символа:

{--------------------------------------------------------------}

{ Get an Identifier }

function GetName: string;

var Token: string;

begin

   Token := '';

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

   while IsAlNum(Look) do begin

      Token := Token + UpCase(Look);

      GetChar;

   end;

   GetName := Token;

end;

{--------------------------------------------------------------}

Аналогично измените GetNum следующим образом:

{--------------------------------------------------------------}

{ Get a Number }

function GetNum: string;

var Value: string;

begin

   Value := '';

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

   while IsDigit(Look) do begin

      Value := Value + Look;

      GetChar;

   end;

   GetNum := Value;

end;

{--------------------------------------------------------------}

Достаточно удивительно, что это фактически все необходимые изменения! Локальная переменная Name в процедурах Ident и Assignment были первоначально объявлены как "char" и теперь должны быть объявлены как string[8]. (Ясно, что мы могли бы сделать длину строки больше, если бы захотели, но большинство ассемблеров в любом случае ограничивают длину.) Внесите эти изменения и затем откомпилируйте и протестируйте. Сейчас вы верите, что это просто?

МОДУЛЬ ERROR

Наш следующий набор подпрограмм обрабатывает ошибки. Чтобы освежить вашу память мы возьмем подход, заданный Borland в Turbo Pascal - останавливаться на первой ошибке. Это не только значительно упрощает наш код, полностью устраняя назойливую проблему восстановления после ошибок, но это также имеет намного больший смысл, по моему мнению, в интерактивной среде. Я знаю, что это может быть крайней позицией, но я считаю практику сообщать обо всех ошибках в программе анахронизмом, пережитком со времен пакетной обработки. Пришло время прекратить такую практику. Так вот.

В нашем оригинальном Cradle мы имели две процедуры обработки ошибок: Error, которая не останавливалась, и Abort, которая останавливалась. Но я не думаю, что мы когда-либо найдем применение процедуре, которая не останавливается, так что в новом, тощем и скромном модуле Errors, показанном ниже, процедура Error занимает место Abort.

{--------------------------------------------------------------}

unit Errors;

{--------------------------------------------------------------}

interface

procedure Error(s: string);

procedure Expected(s: string);

{--------------------------------------------------------------}

implementation

{--------------------------------------------------------------}

{ Write error Message and Halt }

procedure Error(s: string);

begin

 WriteLn;

 WriteLn(^G, 'Error: ', s, '.');

 Halt;

end;

{--------------------------------------------------------------}

{ Write "<something> Expected" }

procedure Expected(s: string);

begin

 Error(s + ' Expected');

end;

end.

{--------------------------------------------------------------}

Как обычно, вот программа для проверки:

{--------------------------------------------------------------}

program Test;

uses WinCRT, Input, Output, Errors;

begin

 Expected('Integer');

end.

{--------------------------------------------------------------}

Вы заметили, что строка "uses" в нашей основной программе становится длиннее? Это нормально. В конечной версии основная программа будет вызывать процедуры только из нашего синтаксического анализатора, так что раздел uses будет иметь только пару записей. Но сейчас возможно самое лучшее включить все модули, чтобы мы могли протестировать процедуры в них.

МОДУЛЬ INPUT

Ключевой концепцией, которую мы использовали начиная с первого дня, была идея входного потока с одним предсказывающим символом. Все подпрограммы синтаксического анализа проверяют этот символ, не изменяя его, чтобы решить, что они должны делать дальше. (Сравните этот подход с подходом C/Unix, использующим getchar и unget, и я думаю вы согласитесь, что наш подход проще). Мы начнем нашу экскурсию в будущее перенеся эту концепцию в нашу новую модульную организацию.Первый модуль, соответствующе названный Input, показан ниже:

{--------------------------------------------------------------}

unit Input;

{--------------------------------------------------------------}

interface

var Look: char;               { Lookahead character }

procedure GetChar;            { Read new character  }

{--------------------------------------------------------------}

implementation

{--------------------------------------------------------------}

{ Read New Character From Input Stream }

procedure GetChar;

begin

 Read(Look);

end;

{--------------------------------------------------------------}

{ Unit Initialization }

begin

 GetChar;

end.

{--------------------------------------------------------------}

Как вы можете видеть, здесь нет ничего очень заумного и конечно ничего сложного, так как он состоит только из одной процедуры. Но мы уже можем видеть как использование модулей дает нам преимущества. Обратите внимание на выполнимый код в блоке инициализации. Этот код "запускает помпу" входного потока для нас, нечто такое мы всегда делали раньше вставляя вызовы  GetChar в процедуру Init. На этот раз вызов происходит без каких-либо специальных обращений к ней с нашей стороны, за исключением самого модуля. Как я предсказывал ранее, этот механизм сделает нашу жизнь в будущем значительно проще. Я полагаю это одна из наиболее полезных возможностей Turbo Pascal и я буду сильно на нее полагаться.

Скопируйте этот модуль в IDE вашего компилятора и откомпилируйте его. Чтобы проверить программу, конечно, нам всегда нужна основная программа. Я использовал следующую, действительно сложную тестовую программу, которую позже мы разовьем в главную для нашего компилятора:

{--------------------------------------------------------------}

program Main;

uses WinCRT, Input;

begin

 WriteLn(Look);

end.

{--------------------------------------------------------------}

Обратите внимание на использование предоставляемого Borland модуля WinCRT. Этот модуль необходим, если вы предполагаете использовать стандартные подпрограммы ввода/вывода Паскаля Read, ReadLn, Write и WriteLn, которые мы конечно предполагаем использовать. Если вы забудете включить этот модуль в раздел "uses" вы получите действительно причудливое и непонятное сообщение во время выполнения.

Заметьте также, что мы можем обращаться к предсказывающему символу даже при том, что он не объявлен в основной программе. Все переменные, объявленные в разделе interface модуля, являются глобальными, но они скрыты от любопытных глаз; в какой-то степени мы получаем чуточку сокрытия информации. Конечно, если бы мы писали в объектно-ориентированном стиле, мы не должны были бы позволять обращаться к внутренним переменным модуля снаружи. Но хотя модули Turbo имеют много общего с объектами, мы не собираемся здесь реализовывать объектно-ориентированный дизайн или код, так что мы используем Look соответствующее.

Продолжим и сохраним тестовую программу как Main.pas. Чтобы сделать жизнь проще когда файлов будет становиться все больше и больше, вам возможно захотелось бы использовать возможность объявить этот файл как Primary файл компилятора. Таким способом вы можете выполнять программу из любого файла. Иначе, если вы нажмете Cntl-F9 для компиляции и выполнения одного из модулей, вы получите сообщение об ошибке. Вы устанавливаете primary-файл используя главное подменю "Compile" в Turbo IDE.

Я тороплюсь отметить, как я делал раньше, что функционально модуль Input является, и всегда был, макетом настоящей версии. В серийной версии компилятора входной поток будет, конечно, скорее исходить из файла, а не клавиатуры. И это почти обязательно включает буферизацию строки, по крайней мере, и более вероятно, довольно большой текстовый буфер для поддержки эффективного дискового ввода/вывода. Хорошая сторона модулей в том, что как и с объектами, мы можем делать код модуля таким простым или таким сложным как нам угодно. До тех пор, пока интерфейс, встроенный в общедоступные процедуры и предсказывающий символ не изменяются, остальная часть программы абсолютно не затрагивается. И так как модули компилируются, а не просто включаются, время необходимое для связывания их вместе практически равно нулю. Снова, результат таков, что мы можем получить все преимущества сложной реализации без необходимости возиться с кодом как лишним багажом.

В следующих главах я предполагаю предоставить полноценный IDE для компилятора KISS используя настоящее Windows приложение, сгенерированное с помощью среды разработки Borland OWL. Сейчас, тем не менее, мы удовлетворим мое первое правило: Делать Это Проще.

МОДУЛЬ OUTPUT

Конечно, каждая приличная программа должна выводить результат и наша не исключение. Наши подпрограммы вывода включают функции Emit. Код для соответствующего модуля показан дальше:

{--------------------------------------------------------------}

unit Output;

{--------------------------------------------------------------}

interface

procedure Emit(s: string);   { Emit an instruction  }

procedure EmitLn(s: string);  { Emit an instruction line }

{--------------------------------------------------------------}

implementation

const TAB = ^I;

{--------------------------------------------------------------}

{ Emit an Instruction }

procedure Emit(s: string);

begin

 Write(TAB, s);

end;

{--------------------------------------------------------------}

{ Emit an Instruction, Followed By a Newline }

procedure EmitLn(s: string);

begin

 Emit(s);

 WriteLn;

end;

end.

{--------------------------------------------------------------}

(Заметьте, что этот модуль не имеет раздела инициализации, так что он не требует блока begin.)

Проверьте этот модуль с помощью следующей основной программы:

{--------------------------------------------------------------}

program Test;

uses WinCRT, Input, Output, Scanner, Parser;

begin

 WriteLn('MAIN:");

 EmitLn('Hello, world!');

end.

{--------------------------------------------------------------}

Увидели ли вы что-либо, что удивило вас? Вы возможно были удивлены видеть, что вам было необходимо что-то набрать даже хотя основная программа не требует никакого ввода. Дело в разделе инициализации модуля Input, который все еще требует поместить что-либо в предсказывающий символ. Жаль, нет никакого способа выйти из этого, или скорее, мы не хотим выходить. За исключением простых тестовых случаев, как этот, нам всегда будет необходим допустимый предсказывающий символ, так что самое лучшее, что мы можем сделать с этой "проблемой" это... ничего.

Возможно более удивительно то что символ TAB не имеет никакого эффекта; наша строка "инструкций" начинается с первой колонки, так же как и фальшивая метка... Правильно: WinCRT не поддерживает табуляцию. У нас проблема.

Есть несколько способов, с помощью которых мы можем решить эту проблему. Один из вариантов того что мы можем сделать - просто игнорировать ее. Каждый ассемблер, который я когда либо использовал, резервируют колонку 1 для меток и взбунтуется когда увидит, что в ней начинаются инструкции. Так что, по крайней мере, мы должны сдвинуть инструкции на одну колонку чтобы сделать ассемблер счастливым. Это достаточно просто сделать: просто измените в процедуре Emit строку:

    Write(TAB, s);

на

    Write(' ', s);

Я должен признать что сталкивался с этой проблемой раньше и находил себя меняющим свое мнение так часто как хамелеон меняет цвет. Для наших целей, 99% которых будет проверка выходного кода при выводе на CRT, было бы хорошо видеть аккуратно сгруппированный "объектный" код. Строка:

    SUB1:  MOVE #4,D0

просто выглядит более опрятно, чем отличающийся, но функционально идентичный код:

    SUB1:

     MOVE #4,D0

В тестовой версии моего кода я включил более сложную версию процедуры PostLabel, которая позволяет избежать размещения меток на раздельных строках, задерживая печать метки чтобы она оказалась на той же самой строке, что и связанная инструкция. Не позднее чем час назад, моя версия модуля Output предоставляла полную поддержку табуляции с использованием внутренней переменной счетчика столбцов и подпрограммы для ее управления. Я имел некоторый довольно изящный код для поддержки механизма табуляции с минимальным увеличением кода. Было ужасное искушение показать вам эту "красивую" версию, единственно чтобы покрасоваться элегантностью.

Однако, код "элегантной" версии был значительно более сложным и большим. После этого у меня появилась вторая мысль. Несмотря на наше желание видеть красивый вывод, неизбежный факт то, что две версии MAIN: фрагменты кода, показанные выше функционально идентичны; ассемблер, который является конечной целью кода, не интересует какую версию он получает, за исключением того, что красивая версия будет содержать больше символов, следовательно будет использовать больше дискового пространства и дольше ассемблироваться. Но красивая версия не только генерирует больше кода, но дает больший выходной файл, с гораздо большим количество пустых символов чем минимально необходимо.  Когда вы посмотрите на это с такой стороны, то не трудно будет решить какой подход использовать, не так ли?

То что наконец решило для меня этот вопрос было напоминанием считаться с моей первой заповедью: KISS. Хотя я был довольно горд всеми своими изящными приемчиками для реализации табуляции, я напомнил себе, что перефразируя сенатора Барри Голдватера, элегантность в поисках сложности не является достоинством. Другой мудрый человек однажды написал: "Любой идиот может разработать Роллс-Ройс. Требуется гений, чтобы разработать VW". Так что изящная, дружественная табуляции версия Output в прошлом, и то, что вы видите, это простая компактная VW версия.

МОДУЛЬ SCANNER

Следующая, и намного более важная, версия лексического анализатора, та которая обрабатывает много символьные токены, которые должны иметь все настоящие языки. Только две функции, GetName и GetNumber отличаются в этих двух модулях, но только чтобы убедиться, что здесь нет никаких ошибок, я воспроизвел здесь весь модуль. Это модуль Scanner:

{--------------------------------------------------------------}

unit Scanner;

{--------------------------------------------------------------}

interface

uses Input, Errors;

function IsAlpha(c: char): boolean;

function IsDigit(c: char): boolean;

function IsAlNum(c: char): boolean;

function IsAddop(c: char): boolean;

function IsMulop(c: char): boolean;

procedure Match(x: char);

function GetName: string;

function GetNumber: longint;

{--------------------------------------------------------------}

implementation

{--------------------------------------------------------------}

{ Recognize an Alpha Character }

function IsAlpha(c: char): boolean;

begin

 

 IsAlpha := UpCase(c) in ['A'..'Z'];

end;

{--------------------------------------------------------------}

{ Recognize a Numeric Character }

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 Addition Operator }

function IsAddop(c: char): boolean;

begin

 

 IsAddop := c in ['+','-'];

end;

{--------------------------------------------------------------}

{ Recognize a Multiplication Operator }

function IsMulop(c: char): boolean;

begin

  IsMulop := c in ['*','/'];

end;

{--------------------------------------------------------------}

{ Match One Character }

procedure Match(x: char);

begin

 

 if Look = x then GetChar

  else Expected('''' + x + '''');

end;

{--------------------------------------------------------------}

{ Get an Identifier }

function GetName: string;

var n: string;

begin

  n := '';

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

  while IsAlnum(Look) do begin

    n := n + Look;

    GetChar;

  end;

  GetName := n;

end;

{--------------------------------------------------------------}

{ Get a Number }

function GetNumber: string;

var n: string;

begin

  n := '';

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

  while IsDigit(Look) do begin

    n := n + Look;

    GetChar;

  end;

  GetNumber := n;

end;

end.

{--------------------------------------------------------------}

Та же самая тестовая программа проверит также и этот сканер. Просто измените раздел "uses" для использования Scanner вместо Scanner1. Теперь у вас должна быть возможность набирать много символьные имена и числа.

МУЛЬТИПЛИКАТИВНЫЕ ВЫРАЖЕНИЯ

Процедуры для работы с мультипликативными операторами почти такие же. Фактически, на первом уровне они почти идентичны, так что я просто покажу их здесь без особых фанфар. Первая - наша общая форма для Factor, которая включает подвыражения в скобках:

{---------------------------------------------------------------}

{ Parse and Translate a Factor }

function Expression: char; Forward;

function Factor: char;

begin

if Look = '(' then begin

      Match('(');

      Factor := Expression;

      Match(')');

      end

   else if IsAlpha(Look) then

      Factor := Load(GetName)

   else

      Factor := LoadNum(GetNum);

end;

{--------------------------------------------------------------}

{ Recognize and Translate a Multiply }

Function Multiply(T1: char): char;

begin

   Match('*');

   Multiply := PopMul(T1, Factor);

end;

{--------------------------------------------------------------}

{ Recognize and Translate a Divide }

function Divide(T1: char): char;

begin

   Match('/');

   DIvide := PopDiv(T1, Factor);

end;

{---------------------------------------------------------------}

{ Parse and Translate a Math Term }

function Term: char;

var Typ: char;

begin

   Typ := Factor;

   while IsMulop(Look) do begin

      Push(Typ);

      case Look of

       '*': Typ := Multiply(Typ);

       '/': Typ := Divide(Typ);

      end;

   end;

   Term := Typ;

end;

{---------------------------------------------------------------}

Эти подпрограммы соответствуют аддитивным почти полностью. Как и прежде, сложность изолирована в PopMul и PopDiv. Если вам захочется протестировать программу прежде чем мы займемся ими, вы можете написать их пустые версии, аналогичные PopAdd и PopSub. И снова, код не будет корректным в данный момент, но синтаксический анализатор должен обрабатывать выражения произвольной сложности.

Лекции по построению компилятора на Pascal

Если вы прочитали введение, то вы уже в курсе дела. Вы также скопировали программу Cradle в Turbo Pascal и откомпилировали ее. Итак, вы готовы.

Целью этой главы является обучение синтаксическому анализу и трансляции математических выражений. В результате мы хотели бы видеть серию команд на ассемблере, выполняющую необходимые действия. Выражение – правая сторона уравнения, например:

     x = 2*y + 3/(4*z)

В самом начале я буду двигаться очень маленькими шагами для того, чтобы начинающие из вас совсем не заблудились. Вы также получите несколько хороших уроков, которые хорошо послужат нам позднее. Для более опытных читателей: потерпите. Скоро мы двинемся вперед.

НАЧИНАЕМ ЗАНОВО?

Четыре года назад, в Главе 14, я обещал вам, что наши дни повторного изобретения колеса и написания одних и тех же программ на каждом уроке, прошли и что с этого момента мы будем придерживаться более завершенных программ, к которым мы должны просто добавлять новые возможности. Я все еще собираюсь сдержать это обещание; это одна из основных целей использования модулей. Однако, из-за прошествия длительного времени с главы 14, естественно хотелось бы сделать по крайней мере небольшой обзор и в любом случае мы окажемся перед необходимостью сделать довольно обширные изменения кода, чтобы выполнить переход к модулям. Кроме того, если откровенно, после всего этого времени я не могу помнить всех хороших идей, которые я имел в моей голове четыре года назад. Для меня лучший способ вспомнить их - заново пройти некоторые шаги, которые привели нас к Главе 14. Так что я надеюсь, что вы поймете и смиритесь со мной когда мы возвратимся к своим корням, в некотором смысле, и перестроим ядро программы, распределяя подпрограммы по различным модулям, и вытащим сами себя назад к точке где мы были многие луны тому назад. Как всегда бывало, вы увидите все мои ошибки и смены направлений в реальном режиме времени. Пожалуйста, будьте терпеливы... мы доберемся до новых вещей раньше чем вы успеете оглянуться.

Так как в нашем новом подходе мы собираемся использовать множественные модули, мы должны обратиться к проблеме управления файлами. Если вы проследовали через все другие разделы этой обучающей серии, вы знаете, что поскольку наша программа развивается, мы заменяем старые, более простые модули на более совершенные. Это приводит нас к проблеме контроля версий. Почти обязательно будут возникать ситуации, когда мы будем перекрывать простой файл (модуль), но позднее захотим иметь его снова. Данный случай воплощен в нашей склонности к использованию одно-символьных имен переменных, ключевых слов и т.д. для проверки основных понятий не захлебываясь в деталях лексического анализатора. Благодаря использованию модулей мы будем намного меньше делать это в будущем. Однако, я не только предполагаю, но я уверен, что мы будем должны сохранять некоторые старые версии файлов для специальных целей, даже при том, что они заменяются более новыми, более совершенными.

Для решения этой проблемы я предлагаю, чтобы вы создали различные каталоги с различными версиями модулей. Если мы сделаем это правильно, код в каждом каталоге останется само непротиворечивым. Я в порядке эксперимента создал четыре каталога: SINGLE (для одно-символьных экспериментов), MULTI (для, конечно, много символьной версии), TINY и KISS.

Достаточно сказано о философии и деталях. Давайте продолжим восстановление программы.

НЕМНОГО ФИЛОСОФИИ

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

В ранние дни технологии компиляции люди тратили ужасно много времени на выяснение того, как работать с такими вещами как приоритет операторов… способа, который определяет приоритет операторов умножения и деления над сложением и вычитанием и т.п. Я помню одного своего коллегу лет тридцать назад и как возбужденно он выяснял как это делается. Используемый им метод предусматривал создание двух стеков, в которые вы помещали оператор или операнд. С каждым оператором был связан уровень приоритета и правила требовали, чтобы вы фактически выполняли операцию ("уменьшающую" стек) если уровень приоритета на вершине стека был корректным. Чтобы сделать жизнь более интересной оператор типа ")" имел различные приоритеты в зависимости от того, был он уже в стеке или нет. Вы должны были дать ему одно значение перед тем как поместите в стек и другое, когда решите извлечь из стека. Просто для эксперимента я самостоятельно поработал со всем этим несколько лет назад и могу сказать вам, что это очень сложно.

Мы не делали что-либо подобное. Фактически, к настоящему времени синтаксический анализ арифметических выражений должен походить на детскую игру. Как мы оказались настолько удачными? И куда делся стек приоритетов?

Подобная вещь происходит в нашем интерпретаторе выше. Вы просто знаете, что для того, чтобы выполнить вычисления арифметических выражений (в противоположность их анализу), должны иметься числа, помещенные в стек. Но где стек?

Наконец, в учебниках по компиляторам имеются разделы, где обсуждены стеки и другие структуры. В другом передовом методе синтаксического анализа (LR) используется явный стек. Фактически этот метод очень похож на старый способ вычисления арифметических выражений. Другая концепция – это синтаксическое дерево. Авторы любят рисовать диаграммы из токенов в выражении объединенные в дерево с операторами во внутренних узлах. И снова, где в нашем методе деревья и стеки? Мы не видели ничего такого. Во всех случаях ответ в том, что эти структуры не явные а неявные. В любом машинном языке имеется стек, используемый каждый раз, когда вы вызываете подпрограмму. Каждый раз, когда вызывается подпрограмма, адрес возврата помещается в стек ЦПУ. В конце подпрограммы адрес выталкивается из стека и управление передается на этот адрес. В рекурсивном языке, таком как Pascal, могут также иметься локальные данные, помещенные в стек, и они также возвращаются когда это необходимо.

Например функция Expression содержит локальный параметр, названный Value, которому присваивается значение при вызове Term. Предположим, при следующем вызове Term для второго аргумента, что Term вызывает Factor, который рекурсивно вызывает Expression снова. Этот "экземпляр" Expression получает другое значение для его копии Value. Что случится с первым значением Value? Ответ: он все еще в стеке и будет здесь снова, когда мы возвратимся из нашей последовательности вызовов.

Другими словами, причина, по которой это выглядит так просто в том, что мы максимально использовали ресурсы языка. Уровни иерархии и синтаксические деревья присутствуют здесь, все правильно, но они скрыты внутри структуры синтаксического анализатора и о них заботится порядок в котором вызываются различные процедуры. Теперь, когда вы увидели, как мы делаем  это, возможно трудно будет придумать как сделать это каким-либо другим способом. Но я могу сказать вам, что это заняло много лет для создателей компиляторов. Первые компиляторы были слишком сложными. Забавно, как работа становится легче с небольшой практикой.

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

Следующий шаг – добавление имен переменных. Сейчас, однако, мы имеем небольшую проблему. В случае с компилятором мы не имели проблем при работе с именами переменных… мы просто выдавали эти имена ассемблеру и позволяли остальной части программы заботиться о распределении для них памяти. Здесь же, напротив, у нас должна быть возможность извлекать значения переменных и возвращать их как значение функции Factor. Нам необходим механизм хранения этих переменных.



В ранние дни персональных компьютеров существовал Tiny Basic. Он имел в общей сложности 26 возможных переменных: одна на каждую букву алфавита. Это хорошо соответствует нашей концепции одно-символьных токенов, так что мы испробуем этот же прием. В начале интерпретатора, сразу после объявления переменной Look, вставьте строку:

     Table: Array['A'..'Z'] of integer;

Мы также должны инициализировать массив, поэтому  добавьте следующую процедуру:

{---------------------------------------------------------------}

{ Initialize the Variable Area }

procedure InitTable;

var i: char;

begin

   for i := 'A' to 'Z' do

      Table[i] := 0;

end;

{---------------------------------------------------------------}

Вы также должны вставить вызов InitTable в процедуру Init. Не забудьте сделать это, иначе результат может удивить вас!

Теперь, когда у нас есть массив переменных, мы можем модифицировать Factor так, чтобы он их использовал. Так как мы не имеем (пока) способа для установки значения переменной, Factor будет всегда возвращать для них нулевые значения, но давайте двинемся дальше и расширим его. Вот новая версия:

{---------------------------------------------------------------}

{ Parse and Translate a Math Factor }

function Expression: integer; Forward;

function Factor: integer;

begin

   if Look = '(' then begin

      Match('(');

      Factor := Expression;

      Match(')');

      end

   else if IsAlpha(Look) then

      Factor := Table[GetName]

   else

       Factor := GetNum;

end;

{---------------------------------------------------------------}

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



Я предполагаю вы уже знаете следующий шаг: мы должны добавить операции присваивания, чтобы мы могли помещать что-нибудь в переменные. Сейчас давайте будем "однострочниками", хотя скоро мы сможем обрабатывать множество операторов.

Операция присваивания похожа на то, что мы делали раньше:

{--------------------------------------------------------------}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

   Name := GetName;

   Match('=');

   Table[Name] := Expression;

end;

{--------------------------------------------------------------}

Чтобы протестировать ее, я добавил временный оператор write в основную программу для вывода значения A. Затем я протестировал ее с различными присваиваниями.

Конечно, интерпретируемый язык, который может воспринимать только одну строку программы не имеет большой ценности. Поэтому нам нужно обрабатывать множество утверждений. Это просто означает что необходимо поместить цикл вокруг вызова Assignment. Давайте сделаем это сейчас. Но что должно быть критерием выхода из цикла? Рад, что вы спросили, потому что это поднимает вопрос, который мы были способны игнорировать до сих пор.

Одной из наиболее сложных вещей в любом трансляторе является определение момента когда необходимо выйти из данной конструкции и продолжить выполнение. Пока это не было для нас проблемой, потому что мы допускали только одну конструкцию… или выражение или операцию присваивания. Когда мы начинаем добавлять циклы и различные виды операторов,  вы найдете, что мы должны быть очень осторожны, чтобы они завершались правильно. Если мы помещаем наш интерпретатор в цикл, то нам нужен способ для выхода из него. В прерывании по концу строки нет ничего хорошего, поскольку с его помощью мы переходим к следующей строке. Мы всегда могли позволить нераспознаваемым символам прерывать выполнение, но это приводило бы к завершению каждой программы сообщением об ошибке, что конечно выглядит несерьезно.



Нам нужен завершающий символ. Я выступаю за завершающую точку в Pascal ("."). Небольшое осложнение состоит в том, что Turbo Pascal завершает каждую нормальную строку двумя символами: возврат каретки (CR) и перевод строки (LF). В конце каждой строки мы должны "съедать" эти символы перед обработкой следующей.  Естественным способом было бы сделать это в процедуре Match за исключением того, что сообщение об ошибке Match выводит ожидаемые символы, что для CR и LF не будет выглядеть так хорошо. Для этого нам нужна специальная процедура, которую мы, без сомнения, будем использовать много раз. Вот она:

{--------------------------------------------------------------}

{ Recognize and Skip Over a Newline }

procedure NewLine;

begin

   if Look = CR then begin

      GetChar;

      if Look = LF then

         GetChar;

   end;

end;

{--------------------------------------------------------------}

Вставьте эту процедуру в любом удобном месте… я поместил ее сразу после Match. Теперь перепишите основную программу, чтобы она выглядела следующим образом:

{--------------------------------------------------------------}

{ Main Program }

begin

   Init;

   repeat

      Assignment;

      NewLine;

   until Look = '.';

end.

{--------------------------------------------------------------}

Обратите внимание, что проверка на CR теперь исчезла и что также нет проверки на ошибку непосредственно внутри NewLine. Это нормально… все оставшиеся фиктивные символы будут отловлены в начале следующей операции присваивания.

Хорошо, сейчас мы имеем функционирующий интерпретатор. Однако, это не дает нам много хорошего, так как у нас нет никакого способа для ввода или вывода данных. Уверен что нам помогут несколько подпрограмм ввода/вывода!

Тогда давайте завершим этот урок добавив подпрограммы ввода/вывода. Так как мы придерживаемся одно-символьных токенов, я буду использовать знак "?" для замены операции чтения,  знак "!" для операции записи и символ, немедленно следующий после них, который будет использоваться как одно-символьный "список параметров". Вот эти подпрограммы:



{--------------------------------------------------------------}

{ Input Routine }

procedure Input;

begin

   Match('?');

   Read(Table[GetName]);

end;

{--------------------------------------------------------------}

{ Output Routine }

procedure Output;

begin

   Match('!');

   WriteLn(Table[GetName]);

end;

{--------------------------------------------------------------}

Я полагаю они не очень причудливы… например нет никакого символа приглашения при вводе… но они делают свою работу.

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

{--------------------------------------------------------------}

{ Main Program }

begin

   Init;

   repeat

      case Look of

       '?': Input;

       '!': Output;

       else Assignment;

      end;

      NewLine;

   until Look = '.';

end.

{--------------------------------------------------------------}

Теперь вы закончили создание настоящего, работающего интерпретатора. Он довольно скудный, но работает совсем как "большой мальчик". Он включает три вида операторов (и может различить их!), 26 переменных и операторы ввода/вывода. Единственное, в чем он действительно испытывает недостаток - это  операторы управления, подпрограммы и некоторые виды функций для редактирования программы. Функции редактирования программ я собираюсь пропустить. В конце концов, мы здесь не для того, чтобы создать готовый продукт, а чтобы учиться. Управляющие операторы мы раскроем в следующей главе, а подпрограммы вскоре после нее. Я стремлюсь продолжать дальше, поэтому мы оставим интерпретатор в его текущем состоянии.

Я надеюсь, к настоящему времени вы убедились, что ограничение имен одним символом и обработка пробелов это вещи о которых легко позаботиться, как мы сделали это на последнем уроке. На этот раз, если вам захотелось поиграть с этими расширениями, будьте моим гостем… они  "оставлены как упражнение для студента". Увидимся в следующий раз.

НЕМНОГО ОСНОВ

Прежде чем мы начнем определять различные управляющие конструкции, мы должны положить немного более прочное основание. Во-первых, предупреждаю: я не буду использовать для этих конструкций тот же самый синтаксис с которым вы знакомы по Паскалю или Си. К примеру синтаксис Паскаль для IF такой:

IF <condition> THEN <statement>

(где <statement>, конечно, может быть составным.)

Синтаксис C аналогичен этому:

     IF ( <condition> ) <statement>

Вместо этого я буду использовать нечто более похожее на Ada:

     IF <condition> <block> ENDIF

Другими словами, конструкция IF имеет специфический символ завершения. Это позволит избежать висячих else Паскаля и Си и также предотвращает необходимость использовать скобки {} или begin-end. Синтаксис, который я вам здесь показываю, фактически является синтаксисом языка KISS, который я буду детализировать в следующих главах. Другие конструкции также будут немного отличаться. Это не должно быть для вас большой проблемой. Как только вы увидите, как это делается, вы поймете, что в действительности не имеет большого значения, какой конкретный синтаксис используется. Как только синтаксис определен, включить его в код достаточно просто.

Теперь, все конструкции, с которыми мы будем иметь дело, включают передачу управления, что на уровне ассемблера означает условные и/или безусловные переходы. К примеру простой оператор IF:

     IF <condition> A ENDIF B...

должен быть переведен в:

Если условие не выполнено то переход на L

        A

     L: B

          ...

Ясно, что нам понадобятся несколько процедур, которые помогут нам работать с этими переходами. Ниже я определил две из них. Процедура NewLabel генерирует уникальные метки. Это сделано с помощью простого способа называть каждую метку 'Lnn', где nn - это номер метки, начинающийся с нуля. Процедура PostLabel просто выводит метки в соответствующем месте.

Вот эти две подпрограммы:

{--------------------------------------------------------------}

{ 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;

{--------------------------------------------------------------}

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

     var Look  : char;              { Lookahead Character }

         Lcount: integer;           { Label Counter }

Также добавьте следующий дополнительный инициализирующий код в Init:

     LCount := 0;

(Не забудьте сделать это, иначе ваши метки будут выглядеть действительно странными!).

В этом месте я также хотел бы показать вам новый вид нотации. Если вы сравните форму оператора IF, указанную выше, с ассемблерным кодом, который должен быть получен, то вы можете увидеть, что существуют некоторые определенные действия, связанные с каждым ключевым словом в операторе:

     IF: Сначала получить условие и выдать код для него. Затем создать уникальную метку и выдать переход если условие ложно.

     ENDIF: Выдать метку.

Эти действия могут быть показаны очень кратко, если мы запишем синтаксис таким образом:

     IF

     <condition> { Condition;

                            L = NewLabel;

                            Emit(Branch False to L); }



       <block>

     ENDIF       { PostLabel(L) }

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

Почти единственное, что осталось сделать - конкретизировать то, что мы подразумеваем под "Переход если условие ложно".

Я полагаю, что должен быть код, выполняющийся для <condition>, который будет выполнять булеву алгебру и вычислять некоторый результат. Он также должен установить флажки условий, соответствующие этому результату. Теперь, обычным соглашением для булевых переменных является использование 0000 для представления значения "ложь" и какого-либо другого значения (кто-то использует FFFF, кто-то 0001) для представления "истины".

Процессор 68000 устанавливает флажки условий всякий раз, когда любые данные перемещаются или рассчитываются. Если данные равны 0000 (что соответствует условию ложь, запомните) будет установлен флажок ноль. Код для "перехода по нулю" - BEQ. Таким образом

     BEQ  <=> Переход если ложь

     BNE  <=> Переход если истина

По природе вещей большинство ветвлений, которые мы увидим, будут BEQ...  мы будем обходить вокруг кода, который должен выполняться когда условие истинно.

НОВОЕ НАЧАЛО, СТАРОЕ НАПРАВЛЕНИЕ

Подобно многим другим вещам, языки программирования и стили программирования изменяются со временем. В 1994 году кажется немного анахроничным программировать на Turbo Pascal, когда остальной мир кажется сходит с ума по C++. Также кажется немного странным программировать в классическом стиле, когда остальной мир переключился на объектно-ориентированные методы. Однако, несмотря на четырехлетнюю паузу, было бы слишком тяжело сейчас переключиться, скажем, на C++ с объектной ориентацией. Во всяком случае, Pascal все еще не только мощный язык программирования (фактически больше, чем когда либо), но это и замечательная среда для обучения. Си - известно трудный для чтения язык... он часто был обвиняем, наряду с Forth, как "язык только для записи". Когда я программирую на C++ я трачу по крайней мере 50% своего времени на борьбу с синтаксисом языка а не с концепциями. Сбивающие с толку "&" или "*" могут не только изменить функционирование программы, но также и ее правильность. Наоборот, код Паскаля обычно совершенно ясен и прост для чтения даже если вы не знаете языка. Что вы видите, то вы почти всегда и получите, и мы можем сконцентрироваться на концепциях, а не тонкостях реализации. Я сказал в начале, что целью этой обучающей серии была не генерация самого быстрого в мире компилятора, а изучение основ технологии компиляции, с наименьшими затратами времени на борьбу с синтаксисом языка или другими аспектами реализации программного обеспечения. Наконец, так как многое из того, что мы делаем в этом курсе, составляет программное экспериментирование, важно иметь компилятор и связанную с ним среду, который компилирует быстро и без суеты. По моему мнению наиболее значимым мерилом времени при разработке программного обеспечения является скорость цикла редактирование/компиляция/тестирование. В этом отделе Turbo Pascal - король. Скорость компиляции блестяще быстрая, и продолжает становиться быстрее с каждым выпуском (как им это удается?). Несмотря на крупные усовершенствования в быстродействии компиляции C за последние годы, даже Borland-овский самый быстрый компилятор C/C++ все еще не сравним с Turbo Pascal. Далее, редактор, встроенный в его IDE, средство make, и даже их превосходный умный компоновщик, все дополняют друг друга чтобы получить замечательную среду для быстрой разработки. По всем этим причинам, я собираюсь придерживаться Паскаля в продолжение этой серии. Мы будем использовать Turbo Pascal for Windows, один из компиляторов, предоставляемый Borland Pascal with Objects, версия 7.0. Если у вас нет этого компилятора не волнуйтесь... ничего из того, что мы делаем здесь не будет рассчитано на то, что вы имеете последнюю версию. Использование Windows версии сильно помогает мне, позволяя использовать Clipboard для копирования кода из редактора компилятора в эти документы. Она также должна помочь вам по крайней мере копировать код в обратном направлении.

Я думал долго и трудно о том, надо ли представить нашему обсуждению объекты. Я большой защитник объектно-ориентированных методов для всех применений и такие методы определенно имеют свое место в технологии компиляции. Фактически, я написал несколько статей только на эти темы (ссылки 1-3). Но архитектура компилятора, основанного на объектно-ориентированных подходах, значительно отличается от архитектуры более классического компилятора, который мы строим. Кроме того, коней на переправе не меняют. Как я сказал, изменяются стили программирования. Кто знает, может быть пройдут еще шесть лет прежде чем мы закончим эти дела, и если мы будем изменять код каждый раз при изменении стиля программирования мы можем никогда не закончить.

Так что теперь, по крайней мере, я определился продолжать классический стиль в Pascal, хотя мы действительно могли бы обсуждать объекты и объектную ориентацию по ходу дела. Аналогично, целевой машиной останется семейство Motorola 68000. Из всех решений, которые буду приняты здесь, это было самым простым. Хотя я знаю, что многие из вас хотели бы видеть код для 80x86, 68000 является, вообще-то, даже более популярным как платформа для встроенных систем, и это то применение ради которого это все изначально и начиналось. Компилируя для PC, платформы MSDOS, мы должны были бы иметь дело со всеми проблемами системных вызовов DOS, форматов компоновщика DOS, файловой системы PC и аппаратными средствами и всеми другие осложнениями среды DOS. Встроенная система, с другой стороны, должна выполняться автономно и я всегда представлял, что для такого вида применений, как альтернатива ассемблеру, язык подобный KISS процветал бы. В любом случае, кто хочет иметь дело с архитектурой 80x86 если они не должны?

Одна из возможностей Turbo Pascal которую я собираюсь серьезно использовать это модули. В прошлом мы должны были делать компромиссы между размером кода, сложностью и функциональными возможностями программы. Многое из нашей работы было по природе компьютерным экспериментированием, рассматриванием только одного аспекта технологии компиляции в один момент времени. Мы делали это чтобы избежать возни с большими программами, исследуя только простые понятия. В процессе, мы заново изобретали колесо и заново программировали те же самые функции больше раз, чем я могу сосчитать. Модули Turbo предоставляют замечательный способ получить функциональность и простоту одновременно: вы пишете многократно используемый код и вызываете его в одной строке. Ваша тестовая программа остается маленькой, но она может делать мощные вещи.



Одна из возможностей модулей Turbo Pascal - их блок инициализации. Как в пакете Ada, любой код в основном блоке begin-end модуля выполняется когда программа инициализирована. Как вы увидите позже, это иногда дает нам хорошее упрощение кода. Наша процедура Init, которая была с нами начиная с Главы 1, полностью исчезает когда мы используем модули. Различные подпрограммы в Cradle, другие ключевые возможности нашего подхода, будут распределены по модулям.

Концепция модулей, конечно, ничем не отличается от модулей Си. Однако в C (и C++) интерфейс между модулями происходит через операторы include препроцессора и заголовочные файлы. Как кто-то, кто читал множество программ других людей на C, я всегда находил это довольно сбивающим с толку. Всегда кажется, что любая структура данных, о который вы бы хотели знать, находится в каком-то другом файле. Модули Turbo проще по той причине, за которую они критикуются некоторыми: интерфейсы функций и их реализации включены в тот же самый файл. В то время, когда эта организация может создать проблемы с защитой кода, она также уменьшает количество файлов наполовину, что не в два раза хуже. Связывание объектных файлов также просто, потому что компилятор Turbo заботится об этом без необходимости в файлах типа make или других механизмах.

НОВЫЕ СТРОКИ

Продвигаясь прямо вперед, давайте модифицируем наш сканер для поддержки более чем одной строки. Как я упомянул последний раз, наиболее простой способ сделать это - просто обработать символы новой строки, возврат каретки и перевод строки, как незаполненное пространство. Фактически это способ, используемый подпрограммой iswhite из стандартной библиотеки C. Прежде мы не этого делали. Я хотел бы сделать это теперь, чтобы вы могли почувствовать результат.

Чтобы сделать это просто измените единственную выполнимую строку в IsWhite:

     IsWhite := c in [' ', TAB, CR, LF];

Мы должны дать основной программы новое условие останова, так как она никогда не увидит CR. Давайте просто используем:

     until Token = '.';

ОК, откомпилируйте эту программу и запустите ее. Попробуйте пару строк, завершаемых точкой. Я использовал:

     now is the time

     for all good men.

Эй, что случилось? Когда я набрал это, я не получил последний токен, точку. Программа не остановилась. Более того, когда я нажал клавишу 'enter' несколько раз, я все равно не получил точку.

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

Что здесь происходит? Ответ в том, что мы зависаем в SkipWhite. Короткий осмотр этой подпрограммы покажет, что пока мы печатаем пустые строки, мы просто продолжаем выполнение цикла. После того, как SkipWhite встречает LF, он пытается выполнить GetChar. Но так как входной буфер теперь пуст, оператор чтения в GetChar настаивает на наличии другой строки. Процедура Scan получает завершающую точку, все правильно, но она вызывает SkipWhite и SkipWhite не возвращается до тех пор, пока не получит непустую строку.

Такое поведение не настолько плохое, как кажется. В настоящем компиляторе мы читали бы символы из входного файла вместо консоли и пока мы имеем какую-то процедуру для работы с концом файла, все получится ОК. Но для чтения данных с консоли такое поведение слишком причудливое. Суть в том, что соглашение C/Unix  просто не совместимо со структурой нашего анализатора, который запрашивает предсказывающий символ. Код, который мастера из Bell реализовали, не использует это соглашение, поэтому они нуждаются в  'ungetc'.

ОК, давайте исправим проблему. Чтобы сделать это, мы должны возвратиться к старому определению IsWhite (удалите символы CR и LF) и используйте процедуру Fin, которую я представил в последний раз. Если ее нет в вашей текущей версии Cradle, поместите ее там.

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

{--------------------------------------------------------------}

{ Main Program }

begin

   Init;

   repeat

      Token := Scan;

      writeln(Token);

      if Token = CR then Fin;

   until Token = '.';

end.

{--------------------------------------------------------------}

Обратите внимание на "охраняющую" проверку, предшествующую вызову Fin. Это то, что заставляет все это работать, и проверяет, то мы не пытаемся прочитать строку дальше.

Сейчас испытайте этот код. Я думаю он понравится вам больше.

Если вы обратитесь к коду, который мы написали в последней главе, вы обнаружите, что я расставил вызовы Fin по всему коду, где прерывание строки было бы уместным. Это одна из тех областей, которые действительно влияют на восприятие, о котором я упомянул. В этой точке я должен убедить вас поэкспериментировать с различными способами организациями и посмотреть, как вам это понравится. Если вы хотите, чтобы ваш язык был по настоящему свободного стиля, тогда новые строки должны быть прозрачны. В этом случае наилучшим подходом было бы поместить следующие строки в начале Scan:

     while Look = CR do

        Fin;

Если, с другой стороны, вам нужен строчно-ориентированный язык подобный Ассемблеру, BASIC или FORTRAN (или даже Ada... заметьте, что он имеет комментарии, завершаемые новой строкой), тогда вам необходимо, чтобы Scan возвращал CR как токены. Он также должен съедать завершающие LF. Лучший способ сделать - использовать эту строку в самом начале Scan:

     if Look = LF then Fin;

Для других соглашений вы будете должны использовать другие способы организации. В моем примере на последнем уроке я разрешил новые строки только в определенных местах, поэтому я занял какое-то промежуточное положение. В остальных частях этих занятий я буду выбирать такие способы обработки новых строк какие мне понравятся, но я хочу, чтобы вы знали, как выбрать для себя другой путь.

---

---