В классической реализации «щелевого» оптимизатора, оптимизация выполняется как второй проход компилятора. Выходной код записывается на диск и затем оптимизатор считывает и обрабатывает этот файл снова. Фактически, оптимизатор может быть даже отдельной от компилятора программой. Так как оптимизатор только обрабатывает код в маленьком «окне» инструкций (отсюда и название), лучшей реализацией было бы буферизировать несколько срок выходного кода и сканировать буфер каждый раз после EmitLn.
Попытаться сразу генерировать лучший код.
В этом методе выполняется проверка дополнительных условий перед выводом кода. Как тривиальный пример, мы должны были бы идентифицировать нуль и выдать CLR вместо загрузки, или даже совсем ничего не делать, как в случае с прибавлением нуля, например. Конкретней, если мы решили распознавать унарный минус в процедуре Factor вместо Expression, то мы должны обрабатывать –1 как обычную константу, а не генерировать ее из положительных. Ни одна из этих вещей не является слишком сложной для реализации… просто они требуют включения дополнительных проверок в код, поэтому я не включил их в программу. Как только мы дойдем до получения работающего компилятора, генерирующего полезный выполнимый код, мы всегда сможем вернуться и доработать программу для получения более компактного кода. Именно поэтому в мире существует «Версия 2.0».
Существует еще один, достойный упоминания, способ оптимизации, обещающий достаточно компактный код без излишних хлопот. Это мое «изобретение», в том смысле, что я нигде не видел публикаций по этому методу, хотя я и не питаю иллюзий что это придумано мной.
Способ заключается в том, чтобы избежать частого использования стека, лучше используя регистры центрального процессора. Вспомните, когда мы выполняли только сложение и вычитание, то мы использовали регистры D0 и D1 а не стек? Это работало, потому для этих двух операций стек никогда не использовал более чем две ячейки.
Хорошо, процессор 68000 имеет восемь регистров данных. Почему бы не использовать их как стек? В любой момент своей работы синтаксический анализатор «знает» как много элементов в стеке, поэтому он может правильно ими манипулировать. Мы можем определить частный указатель стека, который следит, на каком уровне мы находимся и адресует соответствующий регистр. Процедура Factor, например, должна загружать данные не в регистр D0, а в тот, который является текущей вершиной стека.
Что мы получаем заменяя стек в RAM на локальный стек созданный из регистров. Для большинства выражений уровень стека никогда не превысит восьми, поэтому мы получаем достаточно хороший код. Конечно, мы должны предусмотреть те случаи, когда уровень стека превысит восемь, но это также не проблема. Мы просто позволим стеку перетекать в стек ЦПУ. Для уровней выше восьми код не хуже, чем тот, который мы генерируем сейчас, а для уровней ниже восьми он значительно лучше.
Я реализовал этот метод, просто для того, чтобы удостовериться в том, что он работает перед тем, как представить его вам. Он работает. На практике вы не можете в действительности использовать все восемь уровней... вам, как минимум, нужен один свободный регистр для изменения порядка операндов при делении. Для выражений, включающих вызовы функций, также необходимо зарезервировать регистр. Но все равно, существует возможность улучшения размера кода для большинства выражений.
Итак, вы видите, что получение лучшего кода не настолько трудно, но это усложняет наш транслятор... это сложность, без которой мы можем сейчас обойтись. По этой причине, я очень советую продолжать игнорировать вопросы эффективности в этой книге, усвоив, что мы действительно можем повысить качество кода не выбрасывая того, что уже сделано.
В следующей главе я покажу вам как работать с переменными и вызовами функций. Я также покажу вам как легко добавить поддержку многосимвольных токенов и пробелов.
Снова выражения
Введение
В последней главе мы изучили методы, используемые для синтаксического анализа и трансляции математических выражений в общей форме. Мы закончили созданием простого синтаксического анализатора, поддерживающего выражения произвольной сложности с двумя ограничениями:
Разрешены только числовые показатели
Числовые показатели ограничены одиночной цифрой.
В этой главе мы избавимся от этих ограничений. Мы также расширим то что сделали, добавив операции присваивания и вызовы функций. Запомните, однако, что второе ограничение было главным образом наложено нами самими... выбрано для удобства, чтобы облегчить себе жизнь и сконцентрироваться на фундаментальных принципах. Как вы увидите, от этого ограничения легко освободиться, так что не слишком задерживайтесь на этом. Мы будем использовать это прием пока он служит нам, уверенные в том, что сможем избавиться от него, когда будем готовы.
Переменные
Большинство выражений, который мы встречаем на практике, включают переменные, например:
b * b + 4 * a * c
Ни один компилятор нельзя считать достаточно хорошим, если он не работает с ними. К счастью, это тоже очень просто сделать.
Не забудьте, что в нашем синтаксическом анализаторе в настоящее время существуют два вида показателей: целочисленные константы и выражения в скобках. В нотации БНФ:
<factor> ::= <number> | (<expression>)
"|" заменяет «или», означая, что любая из этих форм является допустимой. Запомните, также, что у нас нет проблемы в определении каждой их них… предсказывающим символом в одном случае является левая скобка "(" и цифра – в другом.
Возможно, не вызовет слишком большого удивления то, что переменная – это просто еще один вид показателя. Так что расширим БНФ следующим образом:
<factor> ::= <number> | (<expression>) | <variable>
И снова, здесь нет неоднозначности: если предсказывающий символ – буква, то это переменная, если цифра то число. Когда мы транслируем число, мы просто генерируем код для загрузки числа, как промежуточных данных, в D0. Сейчас мы делаем то же самое, только для переменной.
Небольшое осложнение при генерации кода возникает из того факта, что большинство операционных систем для 68000, включая SK*DOS которую я использую, требуют чтобы код был написан в «переместимой» форме, что в основном означает что все должно быть PC-относительно. Формат для загрузки на этом языке будет следующим:
MOVE X(PC),D0
где X, конечно, имя переменной. Вооружившись этим, изменим текущую версию процедуры 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
EmitLn('MOVE ' + GetName + '(PC),D0')
else
EmitLn('MOVE #' + GetNum + ',D0');
end;
{–}
Я уже отмечал, как легко добавлять расширения в синтаксический анализатор благодаря способу его структурирования. Вы можете видеть, что это все еще остается действительным и сейчас. На этот раз это стоило нам всего двух дополнительных строк кода. Заметьте так же, как структура if-then-else точно соответствует синтаксическому уравнению БНФ.
ОК, откомпилируйте и протестируйте эту новую версию синтаксического анализатора. Это не слишком сильно повредило, не так ли?
Функции
Есть еще только один распространенный вид показателей, поддерживаемый большинством языков: вызов функции. В действительности, нам пока слишком рано иметь дела с функциями, потому что мы еще не обращались к вопросу передачи параметров. Более того, «настоящий» язык должен включать механизм поддержки более чем одного типа, одним из которых должен быть тип функции. Мы не имеем также и этого. Но все же я хотел бы работать с функциями сейчас по двум причинам. Во-первых, это позволит нам превратить компилятор во что-то очень близкое к конечному виду и, во вторых, это раскроет новую проблему, о которой очень стоит поговорить.
