ВВЕДЕНИЕ
В последней главе (Часть 13, Процедуры) я упомянул, что в ней и в следующей главе мы рассмотрим две возможности, которые помогут отделить игрушечный язык от настоящего, пригодного к использованию. В ней мы рассмотрели вызовы процедур. Многие из вас терпеливо ждали, начиная с Августа'89 когда я выдам вторую. Хорошо, вот она.
В этой главе мы поговорим о том, как работать с различными типами данных. Как и в последней главе, я не буду сейчас включать эти возможности непосредственно в компилятор TINY. Вместо этого я буду использовать тот же самый подход, который так хорошо служил нам в прошлом: использование только фрагментов синтаксического анализатора и одно-символьных токенов. Как обычно, это позволит нам добраться непосредственно до сути вопроса не продираясь сквозь массу ненужного кода. Так как основные проблемы при работе с множественными типами данных возникают в арифметических операциях, на них мы и сконцентрируем свое внимание.
Несколько предупреждений: Во-первых, есть некоторые типы, которые я не буду охватывать в этой главе. Здесь мы будем говорить только о простых, встроенных типах. Мы даже не будем работать с массивами, указателями или строками, я охвачу их в следующих нескольких главах.
Во-вторых, мы также не будем обсуждать и типы, определяемые пользователем. Это будет значительно позже, по той простой причине, что я все еще не убедил себя, что эти определяемые пользователем типы должны быть в языке KISS. В более поздних главах я собираюсь охватить по крайней мере основные концепции определяемых пользователем типов, записей и т.д., просто для того, чтобы серия была полной. Но действительно ли они будут включены как часть KISS - все еще открытый вопрос. Я открыт для комментариев и предложений по этой теме.
Наконец, я должен предупредить вас: то, что мы собираемся сделать может добавить массу дополнительных сложностей и в синтаксический анализатор и в генерируемый код. Поддерживать различные типы достаточно просто. Сложность возникает когда вы добавляете правила преобразования между типами. Вообще-то, будет ли ваш компилятор простым или сложным зависит от способа, выбранного вами для определения правил преобразования типов. Даже если вы решите запретить любые преобразования типов (как в Ada, например) проблема все еще остается, и она встроена в математику. Когда вы умножаете два коротких числа, к примеру, вы можете получить длинный результат.
Я подошел к этой проблеме очень осторожно, пытаясь сохранить простоту. Но мы не можем полностью избежать сложности. Как обычно случается, мы оказываемся перед необходимостью выбирать между качеством кода и сложностью и, как обычно, я предпочитаю выбрать самый простой подход.
ЧТО БУДЕТ ДАЛЬШЕ?
Прежде чем мы погрузимся в это занятие, я думаю вам бы хотелось знать что мы сейчас собираемся делать... особенно после того, как прошло столько много времени с прошлой главы.
Тем временем я не бездействовал. Я разбил компилятор на модули. Одна из проблем, с которыми я столкнулся, в том, что так как мы охватывали новые области и вследствие этого расширяли возможности компилятора 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, я буду счастлив обсудить коллективные авторские права и авторские отчисления от предстоящей книги.
Но хватит говорить. Давайте приступим к изучению типов. Как я сказал ранее, мы будем делать это как и в последней главе: выполняя эксперименты с использованием одно-символьных токенов.
ТАБЛИЦА ИДЕНТИФИКАТОРОВ
Должно быть очевидным, что если мы собираемся работать с переменными различных типов, нам понадобится какое-то место для записи их типов. Очевидным средством для этого является таблица идентификаторов и мы уже использовали ее например для различия между локальными и глобальными переменными и между переменными и процедурами.
Структура таблицы идентификаторов для одно-символьных токенов особенно проста и мы использовали ее прежде несколько раз. Для работы с ней, мы возьмем некоторые процедуры, которые мы использовали раньше.
Сначала, нам необходимо объявить саму таблицу идентификаторов:
|
Code: |
|
{ Variable Declarations } var Look: char; { Lookahead Character } ST: Array['A'..'Z'] of char; { *** ДОБАВЬТЕ ЭТУ СТРОКУ ***} |
Затем мы должны удостовериться, что она инициализируется в процедуре Init:
|
Code: |
|
{ Initialize } procedure Init; var i: char; begin for i := 'A' to 'Z' do ST[i] := '?'; GetChar; end; |
Следующая процедура в действительности нам не нужна, но она будет полезна для отладки. Все, что она делает, это формирует дамп содержимого таблицы идентификаторов:
|
Code: |
|
{ Dump the Symbol Table } procedure DumpTable; var i: char; begin for i := 'A' to 'Z' do WriteLn(i, ' ', ST[i]); end; |
В действительности не имеет значения, где вы поместите эту процедуру... я планирую группировать все подпрограммы таблицы идентификаторов вместе, так что я поместил ее сразу после процедур сообщений об ошибках.
Если вы осторожный тип (как я), вам возможно захотелось бы начать с тестовой программы, которая ничего не делает а просто инициализирует таблицу и затем создает ее дамп. Только для того, чтобы быть уверенным, что все мы находимся на одной волне, ниже я воспроизвожу всю программу, дополненную новыми процедурами. Заметьте, что эта версия включает поддержку пробелов:
|
Code: |
|
program Types;
{ Constant Declarations } const TAB = ^I; CR = ^M; LF = ^J;
{ Variable Declarations } var Look: char; { Lookahead Character } ST: Array['A'..'Z'] of char;
{ Read New Character From Input Stream } procedure GetChar; begin Read(Look); end;
{ Report an Error } procedure Error(s: string); begin WriteLn; WriteLn(^G, 'Error: ', s, '.'); end;
{ Report Error and Halt } procedure Abort(s: string); begin Error(s); Halt; end;
{ Report What Was Expected } procedure Expected(s: string); begin Abort(s + ' Expected'); end;
{ Dump the Symbol Table } procedure DumpTable; var i: char; begin for i := 'A' to 'Z' do WriteLn(i, ' ', ST[i]); end;
{ Recognize an Alpha Character } function IsAlpha(c: char): boolean; begin IsAlpha := UpCase(c) in ['A'..'Z']; end;
{ Recognize a Decimal Digit } function IsDigit(c: char): boolean; begin IsDigit := c in ['0'..'9']; end;
{ Recognize an AlphaNumeric Character } function IsAlNum(c: char): boolean; begin IsAlNum := IsAlpha(c) or IsDigit(c); end;
{ Recognize an Addop } function IsAddop(c: char): boolean; begin IsAddop := c in ['+', '-']; end;
{ Recognize a Mulop } function IsMulop(c: char): boolean; begin IsMulop := c in ['*', '/']; end;
{ Recognize a Boolean Orop } function IsOrop(c: char): boolean; begin IsOrop := c in ['|', '~']; end;
{ Recognize a Relop } function IsRelop(c: char): boolean; begin IsRelop := c in ['=', '#', '<', '>']; end;
{ Recognize White Space } function IsWhite(c: char): boolean; begin IsWhite := c in [' ', TAB]; end;
{ Skip Over Leading White Space } procedure SkipWhite; begin while IsWhite(Look) do GetChar; end;
{ Skip Over an End-of-Line } procedure Fin; begin if Look = CR then begin GetChar; if Look = LF then GetChar; end; end;
{ Match a Specific Input Character } procedure Match(x: char); begin if Look = x then GetChar else Expected('''' + x + ''''); SkipWhite; end;
{ Get an Identifier } function GetName: char; begin if not IsAlpha(Look) then Expected('Name'); GetName := UpCase(Look); GetChar; SkipWhite; end;
{ Get a Number } function GetNum: char; begin if not IsDigit(Look) then Expected('Integer'); GetNum := Look; GetChar; SkipWhite; end;
{ Output a String with Tab } procedure Emit(s: string); begin Write(TAB, s); end;
{ Output a String with Tab and CRLF } procedure EmitLn(s: string); begin Emit(s); WriteLn; end;
{ Initialize } procedure Init; var i: char; begin for i := 'A' to 'Z' do ST[i] := '?'; GetChar; SkipWhite; end;
{ Main Program } begin Init; DumpTable; end. |
ОК, запустите эту программу. Вы должны получить (очень быстро) распечатку всех букв алфавита (потенциальных идентификаторов) сопровождаемых вопросительным знаком. Не очень захватывающе, но это только начало.
Конечно, вообще-то мы хотим видеть типы только тех переменных, которые были определены. Мы можем устранить другие добавив в DumpTable условие IF. Измените цикл следующим образом:
for i := 'A' to 'Z' do
if ST[i] <> '?' then
WriteLn(i, ' ', ST[i]);
Теперь запустите программу снова. Что вы получили?
Хорошо, это даже более скучно чем раньше! Сейчас вообще ничего не выводится, так как в данный момент ни одно из имен не было объявлено. Мы можем немного приправить результат вставив в основную программу несколько операторов, объявляющих несколько записей. Попробуйте такие:
ST['A'] := 'a';
ST['P'] := 'b';
ST['X'] := 'c';
На этот раз, когда вы запустите программу, вы должны получить распечатку, показывающую, что таблица идентификаторов работает правильно.
ДОБАВЛЕНИЕ ЗАПИСЕЙ
Конечно, заполнение таблицы напрямую - довольно плохая практика и она не сможет хорошо нам послужить в будущем. То, что нам нужно, это процедура, добавляющая записи в таблицу. В то же самое время мы знаем, что нам будет необходимо тестировать таблицу для проверки, что мы не объявляем повторно переменную, которая уже используется (что легко может случиться при наличии всего 26 вариантов!). Для поддержки всего это введите следующие новые процедуры:
|
Code: |
|
{ Report Type of a Variable } function TypeOf(N: char): char; begin TypeOf := ST[N]; end;
{ Report if a Variable is in the Table } function InTable(N: char): boolean; begin InTable := TypeOf(N) <> '?'; end;
{ Check for a Duplicate Variable Name } procedure CheckDup(N: char); begin if InTable(N) then Abort('Duplicate Name ' + N); end;
{ Add Entry to Table } procedure AddEntry(N, T: char); begin CheckDup(N); ST[N] := T; end;
|
Теперь измените три строки в основной программе следующим образом:
AddEntry('A', 'a');
AddEntry('P', 'b');
AddEntry('X', 'c');
и запустите программу снова. Работает? Тогда у нас есть подпрограммы таблицы идентификаторов, необходимые для поддержки нашей работы с типами. В следующем разделе мы начнем их использовать на практике.
РАСПРЕДЕЛЕНИЕ ПАМЯТИ
В других программах, подобных этой, включая сам компилятор TINY, мы уже обращались к вопросу объявления глобальных переменных и кода, генерируемого для них. Давайте создадим здесь урезанную версию "компилятора", чья единственная функция - позволить нам объявлять переменные. Помните, синтаксис для объявления:
<data decl> ::= VAR <identifier>
Снова, мы можем вытащить массу кода из предыдущих программ. Следующий код - это урезанные версии тех процедур. Они значительно упрощены, так как я удалил такие тонкости как списки переменных и инициализаторы. Обратите внимание, что в процедуре Alloc новый вызов AddEntry будет также заботиться о проверке двойных объявлений:
|
Code: |
|
{ Allocate Storage for a Variable } procedure Alloc(N: char); begin AddEntry(N, 'v'); WriteLn(N, ':', TAB, 'DC 0'); end;
{ Parse and Translate a Data Declaration } procedure Decl; var Name: char; begin Match('v'); Alloc(GetName); end;
{ Parse and Translate Global Declarations } procedure TopDecls; begin while Look <> '.' do begin case Look of 'v': Decl; else Abort('Unrecognized Keyword ' + Look); end; Fin; end; end; |
Теперь, в основной программе добавьте вызов TopDecl и запустите программу. Попробуйте распределить несколько переменных и обратите внимание на полученный сгенерированный код. Для вас это пройденный этап, поэтому результат должен выглядеть знакомым. Заметьте из кода для TopDecls что программа завершается точкой.
Пока вы здесь, попробуйте объявить две переменные с одинаковыми именами и проверьте что синтаксический анализатор отлавливает ошибку.
ОБЪЯВЛЕНИЕ ТИПОВ
Распределение памяти различных размеров не сложнее чем изменение процедуры TopDecl для распознавания более чем одного ключевого слова. Здесь необходимо принять ряд решений, с точки зрения того, каков должен быть синтаксис и т.п., но сейчас я собираюсь отложить все эти вопросы и просто объявить не подлежащий утверждению указ что наш синтаксис будет таким:
<data decl> ::= <typename> <identifier>
где:
<typename> ::= BYTE | WORD | LONG
(По удивительному совпадению, первые буквы этих наименований оказались те же самыми что и спецификации длины ассемблерного кода 68000, так что такой выбор сэкономит нам немного работы.)
Мы можем создать код, который позаботится об этих объявлениях, внеся всего лишь небольшие изменения. Обратите внимание, что в подпрограммах, показанных ниже, я отделил генерацию код в Alloc от логической части. Это соответствует нашему желанию изолировать машинно-зависимую часть компилятора.
|
Code: |
|
{ Generate Code for Allocation of a Variable } procedure AllocVar(N, T: char); begin WriteLn(N, ':', TAB, 'DC.', T, ' 0'); end;
{ Allocate Storage for a Variable } procedure Alloc(N, T: char); begin AddEntry(N, T); AllocVar(N, T); end;
{ Parse and Translate a Data Declaration } procedure Decl; var Typ: char; begin Typ := GetName; Alloc(GetName, Typ); end;
{ Parse and Translate Global Declarations } procedure TopDecls; begin while Look <> '.' do begin case Look of 'b', 'w', 'l': Decl; else Abort('Unrecognized Keyword ' + Look); end; Fin; end; end; |
Внесите показанные изменения в эти процедуры и испытайте программу. Используйте одиночные символы "b", "w" и "l" как ключевые слова (сейчас они должны быть в нижнем регистре). Вы увидите, что в каждом случае мы выделяем память соответствующего объема. Обратите внимание, глядя на дамп таблицы идентификаторов, что размеры также сохранены для использования позже. Какого использования? Хорошо, это тема остальной части этой главы.
ПРИСВАИВАНИЯ
Теперь, когда мы можем объявлять переменные различных размеров, очевидно что мы должны иметь возможность что-то с ними делать. На первый раз, давайте просто попробуем загружать их в наш рабочий регистр D0. Имеет смысл использовать ту же самую идею, которую мы использовали для Alloc, т.е. сделаем процедуру загрузки, которая может загружать переменные нескольких размеров. Нам также необходимо продолжать изолировать машинно-зависимое содержимое. Процедура загрузки выглядит так:
|
Code: |
|
{ Load a Variable to Primary Register } procedure LoadVar(Name, Typ: char); begin Move(Typ, Name + '(PC)', 'D0'); end; |
По крайней мере для 68000, многие команды оказываются командами MOVE. Было бы полезно создать отдельный генератор кода только для этих инструкций и затем вызывать его когда необходимо:
|
Code: |
|
{ Generate a Move Instruction } procedure Move(Size: char; Source, Dest: String); |
Обратите внимание, что эти две подпрограммы - строго генераторы кода; они не имеют проверки ошибок и другой логики. Чтобы завершить картинку, нам необходим еще один программный уровень, который предоставляет эти функции.
Прежде всего, мы должны удостовериться, что типы, с которыми мы работаем - загружаемого типа. Это звучит как работа для другого распознавателя:
|
Code: |
|
{ Recognize a Legal Variable Type } function IsVarType(c: char): boolean; begin IsVarType := c in ['B', 'W', 'L']; end; |
Затем, было бы хорошо иметь подпрограмму, которая извлечет тип переменной из таблицы идентификаторов в то же время проверяя его на допустимость:
|
Code: |
|
{ Get a Variable Type from the Symbol Table } function VarType(Name: char): char; var Typ: char; begin Typ := TypeOf(Name); if not IsVarType(Typ) then Abort('Identifier ' + Name + ' is not a variable'); VarType := Typ; end; |
Вооруженная этими инструментами, процедура, выполняющая загрузку переменной, становится тривиальной:
{ Load a Variable to the Primary Register }
procedure Load(Name: char);
begin
LoadVar(Name, VarType(Name));
end;
(Примечание для обеспокоившихся: я знаю, знаю, все это очень неэффективно. В промышленной программы мы, возможно, предприняли бы шаги чтобы избежать такого глубокого вложения вызовов процедур. Не волнуйтесь об этом. Это упражнение, помните? Более важно сделать его правильно и понять его, чем получить неправильный ответ но быстро. Если вы закончите свой компилятор и обнаружите, что вы несчастны от его быстродействия, вы вольны вернуться и доработать код для более быстрой работы).
Было бы хорошей идеей протестировать программу сейчас. Так как мы пока не имеем процедуры для работы с операциями присваивания, я просто добавил строки:
Load('A');
Load('B');
Load('C');
Load('X');
в основную программу. Таким образом, после того, как раздел объявления завершен, они будут выполнены чтобы генерировать код для загрузки. Вы можете поиграть с различными комбинациями объявлений чтобы посмотреть как обрабатываются ошибки.
Я уверен, что вы не будете удивлены, узнав, что сохранение переменных во многом подобно их загрузке. Необходимые процедуры показаны дальше:
|
Code: |
|
{ Store Primary to Variable } procedure StoreVar(Name, Typ: char); begin EmitLn('LEA ' + Name + '(PC),A0'); Move(Typ, 'D0', '(A0)'); end;
{ Store a Variable from the Primary Register } procedure Store(Name: char); begin StoreVar(Name, VarType(Name)); end; |
Вы можете проверить их таким же образом, что и загрузку.
Теперь, конечно, достаточно легко использовать их для обработки операций присваивания. Что мы сделаем - создадим специальную версию процедуры Block, которая поддерживает только операции присваивания, а также специальную версию Expression, которая поддерживает в качестве допустимых выражений только одиночные переменные. Вот они:
|
Code: |
|
{ Parse and Translate an Expression } procedure Expression; var Name: char; begin Load(GetName); end;
{ Parse and Translate an Assignment Statement } procedure Assignment; var Name: char; begin Name := GetName; Match('='); Expression; Store(Name); end;
{ Parse and Translate a Block of Statements } procedure Block; begin while Look <> '.' do begin Assignment; Fin; end; end; |
(Стоит заметить, что новые процедуры, которые позволяют нам манипулировать типами, даже проще и яснее чем те, что мы видели ранее. Это в основном благодаря нашим усилиям по изоляции подпрограмм генерации кода.)
Есть одна небольшая назойливая проблема. Прежде мы использовали завершающую точку Паскаля чтобы выбраться из процедуры TopDecl. Теперь это неправильный символ... он использован для завершения Block. В предыдущих программах мы использовали для выхода символ BEGIN (сокращенно "b"). Но он теперь используется как символ типа.
Решение, хотя и является отчасти клуджем, достаточно простое. Для обозначения BEGIN мы будем использовать 'B' в верхнем регистре. Так что измените символ в цикле WHILE внутри TopDecl с "." на "B" и все будет прекрасно.
Теперь мы можем завершить задачу, изменив основную программу следующим образом:
|
Code: |
|
{ Main Program } begin Init; TopDecls; Match('B'); Fin; Block; DumpTable; end. |
(Обратите внимание, что я должен был расставить несколько обращений к Fin чтобы избежать проблем переносов строк.)
ОК, запустите эту программу. Попробуйте ввести:
ba { byte a } *** НЕ НАБИРАЙТЕ КОММЕНТАРИИ!!! ***
wb { word b }
lc { long c }
B { begin }
a=a
a=b
a=c
b=a
b=b
b=c
c=a
c=b
c=c
.
Для каждого объявления вы должны получить сгенерированный код, распределяющий память. Для каждого присваивания вы должны получить код который загружает переменную корректного размера и сохраняет ее, также корректного размера.
Есть только одна небольшая проблема: сгенерированный код неправильный!
Взгляните на код для a=c:
MOVE.L C(PC),D0
LEA A(PC),A0
MOVE.B D0,(A0)
Этот код корректный. Он приведет к сохранению младших восьми бит C в A, что является приемлемым поведением. Это почти все, что мы можем ожидать.
Но теперь, взгляните на противоположный случай. Для c=a генерируется такой код:
MOVE.B A(PC),D0
LEA C(PC),A0
MOVE.L D0,(A0)
Это не правильно. Он приведет к сохранению байтовой переменной A в младших восьми битах D0. Согласно правилам для процессора 68000 старшие 24 бита останутся неизменными. Это означаем, что когда мы сохраняем все 32 бита в C, любой мусор, который был в этих старших разрядах, также будет сохранен. Нехорошо.
То, с чем мы сейчас столкнулись, называется проблемой преобразования типов или приведением.
Прежде, чем мы сделаем что-либо с переменными различных типов, даже если это просто их копирование, мы должны быть готовы встретиться с этой проблемой. Это не самая простая часть компилятора. Большинство ошибок, которые я видел в промышленных компиляторах, имели отношение к ошибкам преобразования типов для некоторой неизвестной комбинации аргументов. Как обычно, существует компромисс между сложностью компилятора и потенциальным качеством сгенерированного кода, и, как обычно, мы выберем путь, который сохранит компилятор простым. Я думаю вы найдете, что с таким подходом мы можем удерживать потенциальную сложность под достаточным контролем.
ТРУСЛИВЫЙ ВЫХОД
Прежде, чем мы заберемся в детали (и потенциальную сложность) преобразования типов, я хотел бы, чтобы вы видели, что существует один супер простой способ решения проблемы: просто переводить каждую переменную в длинное целое во время загрузки!
Для этого достаточно добавить всего одну строку в LoadVar, хотя, если мы не собираемся полностью игнорировать эффективность, она должна ограничиваться проверкой IF. Вот измененная версия:
|
Code: |
|
{ Load a Variable to Primary Register } procedure LoadVar(Name, Typ: char); begin if Typ <> 'L' then EmitLn('CLR.L D0'); Move(Typ, Name + '(PC)', 'D0'); end; |
(Обратите внимание, что StoreVar не нуждается в подобном изменении).
Если вы выполните некоторые тесты с этой новой версией, вы обнаружите, что теперь все работает правильно, хотя иногда неэффективно. К примеру, рассмотрим случай a=b (для тех же самых объявлений, что показаны выше). Теперь сгенерированный код становится:
CLR.L D0
MOVE.W B(PC),D0
LEA A(PC),A0
MOVE.B D0,(A0)
В этом случае CLR оказывается ненужной, так как результат помещается в байтовую переменную. Небольшая доработка помогла бы нам улучшить его. Однако, все это не так уж плохо, и это типичного рода неэффективность, которую мы видели прежде в нехитрых компиляторах.
Я должен подчеркнуть, что устанавливая старшие разряды в нуль, мы фактически обрабатываем числа как целые числа без знака. Если вместо этого мы хотим обрабатывать их как целые числа со знаком (более вероятный случай) мы должны делать расширение знака после загрузки. Просто для того, чтобы обернуть эту часть дискуссии милой красной ленточкой, давайте изменим LoadVar как показано ниже:
|
Code: |
|
{ Load a Variable to Primary Register } procedure LoadVar(Name, Typ: char); begin if Typ = 'B' then EmitLn('CLR.L D0'); Move(Typ, Name + '(PC)', 'D0'); if Typ = 'W' then EmitLn('EXT.L D0'); end; |
В этой версии байт обрабатывается как без-знаковое число (как в Паскале и Си) в то время как слово обрабатывается как знаковое.
БОЛЕЕ ПРИЕМЛЕМОЕ РЕШЕНИЕ
Как мы видели, перевод каждой переменной в длинное слово пока она находится в памяти решает проблему, но это едва ли может быть названо эффективным и, возможно, не было бы приемлемым даже для тех из нас, кто требует не обращать внимания на эффективность. Это означает, что все арифметические операции будут выполняться с 32-битной точностью, что удвоит время выполнения для большинства операций и сделает его еще больше для умножения и деления. Для этих операций мы должны были бы вызывать подпрограммы, даже если данные были бы байтом или словом. Все это слишком походит на уловку, так как уводит нас от всех настоящих проблем.
ОК, значит это решение плохое. Есть ли еще относительно простой способ получить преобразование данных? Можем ли мы все еще сохранять простоту?
Да, действительно. Все, что нам нужно сделать - выполнить преобразование с другого конца... т.е. мы выполняем преобразование на выходе, когда данные сохраняются, а не на входе.
Но запомните, часть присваивания, отвечающая за хранение, в значительной степени независима от загрузки данных, о которой заботится процедура Expression. Вообще, выражение может быть произвольно сложным, поэтому как может процедура Assignment знать, какой тип данных оставлен в регистре D0?
Снова, ответ прост: Мы просто спросим об этом процедуру Expression! Ответ может быть возвращен как значение функции.
Все это требует изменения некоторых процедур, но эти изменения, как и сам метод, совсем простые. Прежде всего, так как мы не требуем чтобы LoadVar выполнял всю работу по преобразованию, давайте возвратимся к простой версии:
|
Code: |
|
{ Load a Variable to Primary Register } procedure LoadVar(Name, Typ: char); begin Move(Typ, Name + '(PC)', 'D0'); end; |
Затем, давайте добавим новую процедуру, которая будет выполнять преобразование из одного типа в другой:
|
Code: |
|
{ 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; |
Затем, мы должны реализовать логику, требуемую для загрузки и сохранения переменной любого типа. Вот подпрограммы для этого:
|
Code: |
|
{ 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:
|
Code: |
|
{ 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 для работы и с этими типами. Это "оставлено как упражнение для студента".
ЛИТЕРАЛЬНЫЕ АРГУМЕНТЫ
Зоркие читатели могли бы отметить, однако, что мы еще даже не имеем правильной формы простого показателя, потому что мы не разрешаем загрузку литеральных констант, только переменных. Давайте исправим это сейчас.
Для начала нам понадобится функция GetNum. Мы уже видели ее несколько версий, некоторые возвращают только одиночный символ, некоторые строку, а некоторые целое число. Та, которая нам здесь нужна будет возвращать длинное целое, так что она может обрабатывать все, что мы ей подбросим. Обратите внимание, что здесь не возвращается никакой информации о типах: GetNum не интересуется тем, как будет использоваться число:
|
Code: |
|
{ 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", означает ли это байт, слово или длинное слово? Мы не имеем никаких сведений. Очевидным способом было бы использование наиболее возможного типа, т.е. длинного слова. Но это плохая идея, потому что когда мы примемся за более сложные выражения, мы обнаружим, что это заставит каждое выражение, включающее литералы, также переводить в длинное.
Лучшим подходом было бы выбрать тип, основанный на значении литерала, как показано далее:
|
Code: |
|
{ 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, которая имеет дополнительный параметр для определения типа:
|
Code: |
|
{ 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 для использования двух возможных видов показателей:
|
Code: |
|
{ Parse and Translate an Expression } function Expression: char; begin if IsAlpha(Look) then Expression := Load(GetName) else Expression := LoadNum(GetNum); end; |
(Вау, это, уверен, не причинило слишком большого вреда! Всего несколько дополнительных строк делают всю работу.)
ОК, соберите этот код в вашу программу и испытайте ее. Вы увидите, что она теперь работает и для переменных и для констант как допустимых выражений.
АДДИТИВНЫЕ ВЫРАЖЕНИЯ
Если вы следовали за этой серией с самого начала, я уверен вы знаете, что будет дальше. Мы расширим форму выражения для поддержки сначала аддитивных выражений, затем мультипликативных, а затем общих выражений со скобками.
Хорошо, что мы уже имеем модель для работы с этими более сложными выражениями. Все, что мы должны сделать, это удостовериться, что все процедуры, вызываемые Expression, (Term, Factor и т.д.) всегда возвращают идентификатор типа. Если мы сделаем это, то структура программы едва ли вообще изменится.
Первый шаг прост: мы должны переименовать нашу существующую версию Expression в Term, как мы делали много раз раньше и создать новую версию Expression:
|
Code: |
|
{ 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 как отдельную подпрограмму потому что позднее это позволит производить несколько лучший код, чем мы делали. Другими словами, я смотрю вперед на проблему оптимизации.
Для этой версии, тем не менее, мы сохраним тот же самый примитивный старый код, который делает новую подпрограмму тривиальной:
|
Code: |
|
{ Process a Term with Leading Unary Operator } function Unop: char; begin Clear; Unop := 'W'; end; |
Процедура Push - это подпрограмма генерации кода, которая теперь имеет параметр, указывающий тип:
|
Code: |
|
{ Push Primary onto Stack } procedure Push(Size: char); begin Move(Size, 'D0', '-(SP)'); end; |
Теперь давайте взглянем на функции Add и Subtract. В более старых версиях этих подпрограмм мы позволяем им вызывать подпрограммы генерации кода PopAdd и PopSub. Мы продолжим делать это, что делает сами функции чрезвычайно простыми:
|
Code: |
|
{ 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:
|
Code: |
|
{ Pop Stack into Secondary Register } procedure Pop(Size: char); begin Move(Size, '(SP)+', 'D7'); end; |
Общая идея состоит в том, что все "Pop-Op" подпрограммы могут вызывать ее. Когда это сделано, мы будем иметь оба операнда в регистрах, поэтому мы можем перевести любой нужный нам. Для работы процедуре Convert необходим другой аргумент, имя регистра:
|
Code: |
|
{ 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. Это функция, возвращающая конечный тип, позволяющий нам знать, что она решила:
|
Code: |
|
{ 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; |
Наконец, следующая функция приводит два регистра к одному типу:
|
Code: |
|
{ 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:
|
Code: |
|
{---------------------------------------------------------------} { 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. Т.е. они являются чистыми генераторами кода, производящими сложение и вычитание регистров:
|
Code: |
|
{ 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). Вы должны обнаружить, что синтаксический анализатор обрабатывает любые аддитивные выражения. Как только все подпрограммы преобразования будет введены, вы должны увидеть, что генерируется правильный код и код для преобразования типов вставляется в нужных местах. Попробуйте смешивать переменные различных размеров а также литералы. Удостоверьтесь, что все работает правильно. Как обычно, хорошо было бы попробовать некоторые ошибочные выражения и посмотреть, как компилятор обрабатывает их.
ПОЧЕМУ ТАК МНОГО ПРОЦЕДУР?
К этому моменту вы можете подумать, что я зашел слишком далеко в смысле глубоко вложенных процедур. В этом несомненно есть большие накладные расходы. Но в моем безумии есть смысл. Как в случае с UnOp, я заглядываю вперед на время, когда мы захотим генерировать лучший код. С таким способом организации кода мы можем достичь этого без значительных изменений в программе Например, в случаях, где значение, помещенное в стек не должно преобразовываться, все же лучше использовать инструкцию "вытолкнуть и сложить". Если мы решим проверять такие случаи, мы можем включить дополнительные тесты в PopAdd и PopSub не изменяя что-либо еще.
МУЛЬТИПЛИКАТИВНЫЕ ВЫРАЖЕНИЯ
Процедуры для работы с мультипликативными операторами почти такие же. Фактически, на первом уровне они почти идентичны, так что я просто покажу их здесь без особых фанфар. Первая - наша общая форма для Factor, которая включает подвыражения в скобках:
|
Code: |
|
{ 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. И снова, код не будет корректным в данный момент, но синтаксический анализатор должен обрабатывать выражения произвольной сложности.
УМНОЖЕНИЕ
Если вы убедились, что сам синтаксический анализатор работает правильно, мы должны выяснить, что необходимо сделать для генерации правильного кода. С этого места дела становятся немного труднее так как правила более сложные.
Давайте с начала возьмем случай умножения. Эта операция аналогична "addops" в том, что оба операнда должны быть одного и того же размера. Она отличается в трех важных отношениях:
| · | Тип произведения обычно не такой же как тип двух операндов. Для произведения двух слов мы получаем в результате длинное слово. |
| · | 68000 не поддерживает умножение 32 x 32, так что необходим вызов подпрограммы для программного умножения. |
| · | Он также не поддерживает умножение 8 x 8, поэтому байтовые операнды должны быть переведены до слова. |
Действия, которые мы должны выполнить, лучше всего показывает следующая таблица:
|
T1 T2 |
B |
W |
L |
|
B |
Преобразовать D0 в W Преобразовать D7 в W MULS Result = W |
Преобразовать D0 в W MULS Result = L |
Преобразовать D0 в L JSR MUL32 Result = L |
|
W |
Преобразовать D7 в W MULS Result = L |
MULS Result = L |
Преобразовать D0 в L JSR MUL32 Result = L |
|
L |
Преобразовать D7 в L JSR MUL32 Result = L |
Преобразовать D7 в L JSR MUL32 Result = L |
JSR MUL32 Result = L |
Эта таблица показывает действия, предпринимаемые для каждой комбинации типов операндов. Есть три вещи, на которые необходимо обратить внимание: во-первых, мы предполагаем, что существует библиотечная подпрограмма MUL32, которая выполняет 32 x 32 умножение, оставляя 32-битное (не 64) произведение. Если в процессе этого происходит переполнение мы игнорируем его и возвращаем только младшие 32 бита.
Во-вторых, заметьте, что таблица симметрична. Наконец, обратите внимание, что произведение это всегда длинное слово, за исключением случая когда оба операнда байты. (Стоит заметить, между прочим, что это означает что результатом многих выражений будет длинное слово, нравится нам это или нет. Возможно идея перевода всех их заранее не была уж такой возмутительной, в конце концов!)
Теперь ясно, что мы должны будем генерировать различный код для 16-разрядного и 32-разрядного умножения. Для этого лучше всего иметь отдельные подпрограммы генерации кода для этих двух случаев:
|
Code: |
|
{---------------------------------------------------------------} { Multiply Top of Stack by Primary (Word) } procedure GenMult; begin EmitLn('MULS D7,D0') end; {---------------------------------------------------------------} { Multiply Top of Stack by Primary (Long) } procedure GenLongMult; begin EmitLn('JSR MUL32'); end; {---------------------------------------------------------------} |
Исследование кода ниже для PopMul должно убедить вас, что условия в таблице выполнены:
|
Code: |
|
{ Generate Code to Multiply Primary by Stack } function PopMul(T1, T2: char): char; var T: char; begin Pop(T1); T := SameType(T1, T2); Convert(T, 'W', 'D7'); Convert(T, 'W', 'D0'); if T = 'L' then GenLongMult else GenMult; if T = 'B' then PopMul := 'W' else PopMul:= 'L'; end; |
Как вы можете видеть, подпрограмма начинается совсем как PopAdd. Два аргумента приводятся к тому же самому типу. Два вызова Convert заботятся о случаях, когда оба операнда - байты. Сами данные переводятся до слова, но подпрограмма помнит тип чтобы назначать корректный тип результату. В заключение мы вызываем одну из двух подпрограмм генерации кода и затем назначаем тип результата. Не слишком сложно, действительно.
Я полагаю, что сейчас вы уже тестируете программу. Попробуйте все комбинации размеров операндов.
ДЕЛЕНИЕ
Случай с делением совсем не так симметричен. У меня также есть для вас некоторые плохие новости:
Все современные 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:
|
Code: |
|
{ 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.
ОК, установите новые процедуры деления. Сейчас у вас должна быть возможность генерировать код для любого вида арифметических выражений. Погоняйте ее!
ЗАВЕРШЕНИЕ
Наконец-то, в этой главе мы узнали как работать с переменными (и литералами) различных типов. Как вы можете видеть, это не было слишком сложно. Фактически, в каком-то отношении большая часть кода выглядит даже еще проще, чем это было в более ранних программах. Только операторы умножения и деления требуют небольших размышлений и планирования.
Основная идея, которая облегчила нам жизнь, - идея преобразования процедур типа Expression в функции, возвращающие тип результата. Как только это было сделано, мы смогли сохранить ту же самую общую структуру компилятора.
Я не буду притворяться, что мы охватили каждый одиночный аспект этой проблемы. Я удобно проигнорировал без знаковую арифметику. Из того, что мы сделали, я думаю вы можете видеть, что их включение не добавляет никаких дополнительных проблем, просто дополнительные проверки.
Я так же игнорировал логические операторы And, Or и т.д. Оказывается, их довольно легко обрабатывать. Все логические операторы - побитовые операции, так что они симметричны и, следовательно, работают в том же самом режиме, что и PopAdd. Однако, имеется одно отличие: если необходимо расширить длину слова для логической переменной, расширение должно быть сделано как число без знака. Числа с плавающей точкой, снова, являются простыми для обработки... просто еще несколько процедур, которые будут добавлены в run-time библиотеку или, возможно, инструкции для математического сопроцессора.
Возможно более важно, что я также отделил проблему контроля соответствия типов, в противоположность преобразованию. Другими словами, мы разрешили операции между переменными всех комбинаций типов. Вообще, это не будет верным... конечно вы не захотите прибавить целое число, например, к строке. Большинство языков также не позволят вам смешивать символьные и целочисленные переменные.
Снова, в действительности в этом случае нет никаких новых проблем для рассмотрения. Мы уже проверяем типы двух операндов... в основном эти проверки выполняются в процедурах типа SameType. Довольно просто включить вызов обработчика ошибок если типы двух операндов несовместимы.
В общем случае мы можем рассматривать каждый одиночный оператор как обрабатываемый отдельной процедурой, в зависимости от типа двух операндов. Это просто, хотя и утомительно, реализовать просто создав таблицу переходов с типами операндов как индексами. В Паскале эквивалентная операция включала бы вложенные операторы Case. Некоторые из вызываемых процедур могли бы тогда быть простыми подпрограммами обработки ошибок, в то время как другие могли бы выполнять любые виды преобразований, необходимые нам. При добавлении нами типов, число процедур будет возрастать в геометрической прогрессии, но это все равно не неприемлемо большое число процедур.
Здесь же мы свернули такую таблицу переходов в гораздо меньшее количество процедур, просто используя симметрию и другие упрощающие правила.
ПРИВОДИТЬ ИЛИ НЕ ПРИВОДИТЬ
В случае, если до вас еще не дошло, уверен дойдет, что TINY и KISS возможно не будут строго типизированными языками, так как я разрешил автоматическое смешивание и преобразование почти любых типов. Что поднимает следующий вопрос:
Это действительно то, что мы хотим сделать?
Ответ зависит от того, какого рода язык вам нужен и как вы хотели чтобы он себя вел. Мы не обращались к проблеме того, когда разрешить или когда запретить использование операций, включающих различные типы данных. Другими словами, какова должна быть семантика нашего компилятора? Хотим ли мы выполнять автоматическое преобразование типов для всех случаев, в некоторых случаях или не выполнять совсем?
Давайте приостановимся здесь, чтобы подумать об этом немного больше. В этом нам поможет небольшой исторический обзор.
Fortran II поддерживал только два простых типа данных: Integer и Real. Он разрешал неявное преобразование типов между real и integer типами во время присваивания, но не в выражениях. Все элементы данных (включая литеральные константы) справа оператора присваивания должны были быть одинакового типа. Это довольно сильно облегчало дела... гораздо проще, чем то, что мы делали здесь.
Это было изменено в Fortran IV для поддержки "смешанной" арифметики. Если выражение имело любые real элементы, все они преобразовывались в real и само выражение было real. Для полноты, предоставлялись функции для явного преобразования из одного типа в другой, чтобы вы могли привести выражение в любой тип.
Это вело к двум вещам: код, который был проще для написания и код, который был менее эффективен. Из-за это неаккуратные программисты должны были писать выражения с простыми константами типа 0 и 1, которые компилятор должен был покорно компилировать для преобразования во время выполнения. Однако, система работала довольно хорошо, что показывало что неявное преобразование типов - Хорошая Вещь.
Си - также слабо типизированный язык, хотя он поддерживает большее количество типов. C не будет жаловаться, если вы например попытаетесь прибавить символ к целому числу. Частично, в этом помогает соглашение Си о переводе каждого символа в число когда оно загружается или передается в списке параметров. Это совсем немного упрощает преобразование. Фактически, в подмножестве компиляторов Си, которые не поддерживают длинные или с плавающей точкой числа мы возвращаемся к нашей первой нехитрой попытке: каждая переменная получает одинаковое представление как только загружается в регистр. Жизнь становится значительно проще!
Предельным языком в направлении автоматического преобразования типов является PL/I. Этот язык поддерживает большое количество типов данных, и вы можете свободно смешивать их все. Если неявное преобразование Fortran казалось хорошим, то таковое в PL/I было бы Небесами, но оно скорее оказалось Адом! Проблема состояла в том, что с таким большим количеством типов данных должно существовать большое количество различных преобразований и, соответственно, большое количество правил того, как смешиваемые операнды должны преобразовываться. Эти правила стали настолько сложными, что никто не мог запомнить какие они! Множество ошибок в программах на PL/I имели отношение к непредвиденным и нежелательным преобразованиям типов. Слишком хорошо тоже нехорошо!
Паскаль, с другой стороны, является языком, который "строго типизирован", что означает, что вы вообще не можете смешивать типы даже если они отличаются только именем, хотя они и имеют тот же самый базовый тип! Никлаус Вирт сделал Паскаль строго типизированным чтобы помочь программисту избежать проблем и эти ограничения действительно защитили многих программистов от самих себя, потому что компилятор предохранял его от глупых ошибок. Лучше находить ошибки при компиляции, чем на этапе отладки. Те же самые ограничения могут также вызвать расстройства когда вам действительно нужно смешивать типы и они заставляют бывших C-программистов лезть на стену.
Даже в этом случае, Паскаль разрешает некоторые неявные преобразования. Вы можете присвоить целое значение вещественному. Вы можете также смешивать целые и вещественные типы в выражениях типа Real. Целые числа будут автоматически приведены к вещественным, как и в Fortran. (и с теми же самыми скрытыми накладными расходами во время выполнения).
Вы не можете, однако, преобразовывать наоборот из вещественного в целое без применения явной функции преобразования Trunc. Теория здесь в том, что так как числовое значение вещественного числа обязательно будет изменено при преобразовании (дробная часть будет потеряна), это не должно быть сделано в "секрете" от вас.
В духе строгого контроля типов Паскаль не позволит вам смешивать Char и Integer переменные без применения явных функций приведения Chr и Ord.
Turbo Pascal также включает типы Byte, Word и LongInt. Первые два в основном то же самое, что и без знаковое целое. В Turbo они могут быть свободно смешаны с переменными типа Integer и Turbo автоматически выполнит преобразование. Однако существуют проверки времени выполнения, предохраняющие вас от переполнения или иного способа получения неправильного ответа. Заметьте, что вы все еще не можете смешивать типы Byte и Char, даже при том, что они имеют то же самое внутреннее представление.
Пределом среди строго типизированных языков является Ada, который не разрешает никаких неявных преобразований типов вообще, и также не разрешает смешанную арифметику. Позиция Jean Ichbiah в том, что преобразования стоят времени выполнения и вам нельзя позволить платить такую цену на скрытый манер. Вынуждая программиста явно запрашивать преобразование типов вы делаете более очевидным то, что здесь могут быть вовлечены затраты.
Я использовал другой язык со строгим контролем типов, небольшой восхитительный язык, названный Whimsical, от Джона Спрея. Хотя Whimsical предназначен быть языком системного программирования, он также требует каждый раз явного преобразования. В нем никогда не выполняются никакие автоматические преобразования, даже те, которые поддерживаются в Паскале.
Такой подход имеет некоторые преимущества: компилятор никогда не должен предполагать, что делать: программист всегда говорит ему точно, что он хочет. В результате, появляется почти однозначное соответствие между исходным кодом и компилированным кодом, и компилятор Джона производил очень компактный код.
С другой стороны, я иногда находил явные преобразования болезненными. Если я хочу, например, прибавить единицу к символу, или сложить ее с маской, необходимо выполнить массу преобразований. Если я сделаю это неправильно единственным сообщением об ошибке будет "Типы не совместимы". Как это случается, специфическая реализация Джоном этого языка в его компиляторе не сообщает вам точно, какие типы несовместимы... он только сообщает вам, в какой строке произошла ошибка.
Я должен признать, что большинство моих ошибок с этим компилятором были ошибками такого типа, и я потратил много времени с компилятором Whimsical, пытаясь всего лишь выяснить в каком месте строки я ее допустил. Единственный реальный способ исправить ошибку это продолжать исправления до тех пор, пока что-нибудь не заработает.
Так что мы должны сделать в TINY и KISS? Для первого я имею ответ: TINY будет поддерживать только типы Char и Integer и мы будем использовать прием C непосредственно переводя Char в Integer. Это означает, что компилятор TINY будет значительно проще, чем то, что мы уже сделали. Необходимость преобразования типов в выражении спорна, так как ни одно из них не требуется! Так как длинное слово не будет поддерживаться, нам также будут не нужны подпрограммы MUL32 и DIV32, ни логики для выяснения когда их вызывать. Мне это нравится!
KISS, с другой стороны будет поддерживать тип Long.
Должен ли он поддерживать и знаковую и без знаковую арифметику? Ради простоты я предпочел бы нет. Это добавляет совсем немного сложности в преобразования типов. Даже Никлаус Вирт удалили без знаковые числа (Cardinal) из его нового языка Оберон, с тем аргументом, что 32-разрядного целого числа в любом случае должно быть достаточно всем.
Но KISS предполагается быть языком системного программирования, что означает, что у нас должна быть возможность выполнять любые действия, которые могут быть выполнены на ассемблере. Так как 68000 поддерживает обе разновидности целых чисел, я полагаю что KISS тоже должен. Мы видели, что логические операции должны быть способны расширять целые числа без знаковым способом, поэтому процедуры без знакового преобразования нужны в любом случае.
ЗАКЛЮЧЕНИЕ
На этом завершается наш урок по преобразованиям типов. Жаль, что вы должны были так долго ждать его, но, надеюсь, вы чувствуете, что он того стоил.
В нескольких следующих главах мы расширим простые типы, включив поддержку массивов и указателей и посмотрим, что делать со строками. Это позволит довольно успешно завершить основную часть этой серии. После этого я дам вам новые версии компиляторов TINY и KISS, а затем мы начнем рассматривать вопросы оптимизации.
Просьба писать ваши замечания, наблюдения и все остальное,
что поможет улучшить предоставляемую информацию на этом сайте.
ВСЕ КОММЕНТАРИИ МОДЕРИРУЮТСЯ ВРУЧНУЮ, ТАК ЧТО СПАМИТЬ БЕСПОЛЕЗНО!