Текст книги "Давайте создадим компилятор!"

Решения, решения

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

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

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

Оба подхода имеют свои преимущества. Так как мы выбираем число, метод, который немедленно приходит на ум – возвращать его как целое число. Но имейте ввиду, что возможно число будет использоваться в операторе вывода который возвращает его во внешний мир. Кто-то, или мы или код, скрытый внутри оператора вывода, окажется перед необходимостью снова преобразовывать число обратно в строку. Turbo Pascal включает такие подпрограммы преобразования строк, но зачем использовать их если мы не должны? Зачем преобразовывать число из строковой в целочисленную форму только для того, чтобы конвертировать его обратно в генераторе кода, всего несколько операторов спустя?

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

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

В конце концов обратно к строковому подходу меня склонило энергичное тестирование KISS, плюс напоминание самому себе, что мы тщательно избегаем проблем эффективности кода. Одна из вещей, которые заставляют нашу нехитрую схему синтаксического анализа работать, без сложностей «настоящего» компилятора, это то, что мы прямо сказали что мы не затрагиваем эффективность кода. Это дает нам массу свободы выполнять работу простейшим путем а не эффективнейшим, и эту свободу мы должны стремиться не потерять, не смотря на призывы к эффективности звучащие в наших ушах. В дополнение к тому, что я большой сторонник философии KISS я также защитник «ленивого программирования», что в этом контексте означает не программировать что-либо пока вы не нуждаетесь в этом. Как говорит П. Дж. Плоджер «никогда не откладывайте на завтра то, что вы можете отложить насовсем». Годами писался код, предоставлявший возможности, которые не были никогда использованы. Я научился этому сам на горьком опыте. Так что вывод таков: мы не будем конвертировать в целое число потому, что это нам не нужно.

Для тех из вас, что все еще думает, что нам может быть нужна целочисленная версия (и действительно она может нам понадобиться), вот она:

{–}

{ Get a Number (integer version) }

function GetNumber: longint;

var n: longint;

begin

n := 0;

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

while IsDigit(Look) do begin

n := 10 * n + (Ord(Look) – Ord('0'));

GetChar;

end;

GetNumber := n;

end;

{–}

Вы могли бы отложить ее, как я предполагаю, на черный день.

Синтаксический анализ

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

Помните самую первую главу этой серии? Мы считывали целочисленное значение, скажем n, и генерировали код для его загрузки в регистр D0 через move:

MOVE #n,D0

Немного погодя, мы повторили этот процесс для переменной,

MOVE X(PC),D0

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

{–}

unit Parser;

{–}

interface

uses Input, Scanner, Errors, CodeGen;

procedure Factor;

{–}

implementation

{–}

{ Parse and Translate a Factor }

procedure Factor;

begin

LoadConstant(GetNumber);

end;

end.

{–}

Как вы можете видеть, этот модуль вызывает процедуру LoadConstant, которая фактически выполняет вывод ассемблерного кода. Модуль также использует новый модуль CodeGen. Этот шаг представляет последнее главное изменение в нашей архитектуре с более ранних глав: перемещение машино-зависимого кода в отдельный модуль. Если я дойду до конца, вне CodeGen не будет ни одной строчки кода, которая указывала бы на то, что мы нацелены на процессор 68000. И это то место, которое показывает, что моя цель достижима.

Для тех из вас, кто желает, чтобы я использовал архитектуру 80x86 (или любую другую) вместо 68000, вот мой ответ: просто замените CodeGen на подходящий для вашего ЦПУ.

Пока наш генератор кода содержит только одну процедуру. Вот этот модуль:

{–}

unit CodeGen;

{–}

interface

uses Output;

procedure LoadConstant(n: string);

{–}

implementation

{–}

{ Load the Primary Register with a Constant }

procedure LoadConstant(n: string);

begin

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

end;

end.

{–}

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

{–}

program Main;

uses WinCRT, Input, Output, Errors, Scanner, Parser;

begin

Factor;

end.

{–}

Вот он, сгенерированный код, такой как мы и надеялись.

Теперь, я надеюсь, вы можете начать видеть преимущества модульной архитектуры нашего нового проекта. Здесь мы имеем основную программу длиной всего пять строк. Это все, что нам нужно видеть, если мы не захотим видеть больше. И пока все эти модули сидят здесь терпеливо ожидая когда смогут послужить нам. Наше преимущество в том, что мы имеем простой и короткий код, но мощных союзников. Что остается сделать, это расширить модули до уровня возможностей более ранних глав. Мы сделаем это в следующей главе, но прежде, чем я закончу, давайте закончим синтаксический анализ показателя только для того, чтобы убедить себя, что мы знаем как. Конечная версия CodeGen включает новую процедуру LoadVariable:

{–}

unit CodeGen;

{–}

interface

uses Output;

procedure LoadConstant(n: string);

procedure LoadVariable(Name: string);

{–}

implementation

{–}

{ Load the Primary Register with a Constant }

procedure LoadConstant(n: string);

begin

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

end;

{–}

{ Load a Variable to the Primary Register }

procedure LoadVariable(Name: string);

begin

EmitLn('MOVE ' + Name + '(PC),D0');

end;

end.

{–}

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

{–}

{ Parse and Translate a Factor }

procedure Factor;

begin

if IsDigit(Look) then

LoadConstant(GetNumber)

else if IsAlpha(Look)then

LoadVariable(GetName)

else

Error('Unrecognized character ' + Look);

end;

{–}

Теперь, без изменений основной программы, вы должны обнаружить, что программа обрабатывает и переменный и постоянный показатель. К этому моменту наша архитектура почти завершена; у нас есть модули, выполняющие всю грязную работу и достаточно кода в синтаксическом анализаторе и генераторе кода чтобы продемонстрировать что все работает. Остается расширить модули которые мы определили, в особенности синтаксический анализатор и генератор кода, для поддержки более сложных синтаксических элементов, которые составляют настоящий язык. Так как мы делали это много раз прежде в предыдущих главах, не должно занять у нас много времени вернуться назад к тому месту, где мы были до долгого перерыва. Мы продолжим этот процесс в Главе 16, которая скоро появится. Увидимся.

Ссылки

Crenshaw, J.W., «Object-Oriented Design of Assemblers and Compilers,» Proc. Software Development '91 Conference, Miller Freeman, San Francisco, CA, February 1991, pp. 143-155.

Crenshaw, J.W., «A Perfect Marriage,» Computer Language, Volume 8, #6, June 1991, pp. 44-55.

Crenshaw, J.W., «Syntax-Driven Object-Oriented Design,» Proc. 1991 Embedded Systems Conference, Miller Freeman, San Francisco, CA, September 1991, pp. 45-60.

Конструирование модулей

Введение

Эта обучающая серия обещает стать возможно одной из самых долгоиграющих мини-серий в истории, конкурирующей только с задержкой на Томе IV Кнута. Начатая в 1988, эта серия вошла в четырехлетнюю паузу в 1990, когда «заботы мира сего», изменения в приоритетах и интересах и необходимость зарабатывать на жизнь казалось забросили ее после Главы 14. Долготерпевшие из вас были наконец вознаграждены весной прошлого года долгожданной Главой 15. В ней я начал попытку поставить серию обратно на рельсы и по ходу дела сделать ее проще для достижения цели, которая состоит в том, чтобы обеспечить вас не только достаточным пониманием трудных тем теории компиляции, но также достаточными инструментами в виде фиксированных подпрограмм и концепций, так чтобы вы были способны продолжать самостоятельно и стали достаточно опытными для того, чтобы создавать свои собственные синтаксические анализаторы и трансляторы. Из-за этой длинной паузы я подумал что следует вернуться назад и повторно рассмотреть концепции, которые мы до этого охватили а также заново сделать некоторые части программы. В прошлом мы никогда сильно не касались разработки программных инструментов промышленного качества… в конце концов я пытался обучать (и обучаться) концепциям, а не промышленной практике. Чтобы сделать это я старался давать вам не законченные компиляторы и анализаторы, а только те отрывки кода, которые иллюстрировали частные случаи, которые мы рассматривали в текущий момент.

Я все еще верю, что это хороший способ изучения любого вопроса; никто не захочет вносить в изменения в программу в 100,000 строк только для того чтобы попробовать новую идею. Но идея работы с обрывками кода а не полными программами также имеет свои недостатки из-за которых мы писали те же самые фрагменты кода много раз. Хотя было полностью доказано, что повторение является хорошим способом обучения новым идеям, также правда и то, что оно может быть не слишком хорошей вещью. Ко времени, когда я завершил Главу 14, я казалось достиг пределов своих способностей манипулировать множеством файлов и множественными версиями тех же самых программ. Кто знает, может быть это одна из причин, по которым я кажется выдохся в то время.

К счастью, более поздние версии Borland Turbo Pascal позволяют нам получить и съесть свой кусок пирога. Используя их концепцию раздельно компилируемых модулей мы все еще можем писать маленькие подпрограммы и функции и сохранять наши основные и тестовые программы маленькими и простыми. Но, однажды написанный, код в модулях Паскаля будет всегда там для нашего использования и его связывание абсолютно безболезненно и прозрачно.

Так как к настоящему времени большинство из вас программируют на C или C++, я знаю, что вы подумаете: Borland с их Turbo Pascal конечно не изобретали понятие раздельно компилируемых модулей. И, конечно, вы правы. Но если вы не использовали TP в последнее время или когда либо, вы можете не понять насколько безболезненный весь этот процесс. Даже в C или C++ вы все еще должны формировать make файл, или вручную, или сообщая компилятору как это сделать. Вы должны также перечислить, используя утверждение «extern» или заголовочные файлы, функции, которые вы хотите импортировать. В TP вы не должны даже делать этого. Вам необходимы только имена модулей, которые вы желаете использовать, и все их процедуры автоматически становятся доступны.

У меня нет намерения заниматься здесь дебатами на тему войн языков, так что я не буду затрагивать эту тему в дальнейшем. Даже я больше не использую Pascal в своей работе… я использую C на работе и С++ для своих статей в Embedded Systems Programming и других журналах. Поверьте мне, когда я намеревался возродить эту серию, я думал долго и интенсивно о переключении и языка и целевой системы на те, которые мы все используем в эти дни, C/C++ и архитектуру PC и возможно также и объектно-ориентированные методы. В конце концов я понял, что это вызовет больше беспорядка, чем сам перерыв. И в конце концов, Pascal все еще остается одним из лучших возможных языков для обучения, не говоря о промышленном программировании. Наконец, TP все еще компилирует на скорости света, гораздо быстрее чем конкурирующие C/C++ компиляторы. А интеллектуальный компоновщик Borland, использованный в TP но не в их продуктах C++ не имеет аналогов. Кроме того, что он намного быстрее, чем Microsoft-совместимые компоновщики, Borland-овский интеллектульный компоновщик отберет неиспользуемые процедуры и элементы данных даже вплоть до вырезания их из определенных объектов если они не нужны. Один из редких моментов нашей жизни, когда мы не должны идти на компромисс между полнотой и эффективностью. Когда мы пишем модуль TP мы можем сделать его настолько полным как нам нравится, включая любые функции и элементы данных которые, как мы думаем, могут нам когда-либо понадобиться, уверенные, что это не будет создавать ненужного раздутия кода в откомпилированной выполнимой программе.

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

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

Input

Output

Errors

Scanner

Parser

CodeGen

Каждый из этих модулей обслуживает разные функции и изолирует специфические области функциональных возможностей. Модули Input и Output, как подразумевают их имена, обеспечивают ввод/вывод символьного потока и важнейший предсказывающий символ, на котором основан наш предсказывающий синтаксический анализатор. Модуль Errors конечно обеспечивает стандартную обработку ошибок. Модуль Scanner содержит все наши булевы функции типа IsAlpha и подпрограммы GetName и GetNumber, которые обрабатывают многосимвольные токены.

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

Совсем как классический?

Прежде чем мы продолжим, однако, я думаю что должен разъяснить связи между модулями и функциональные возможности этих модулей. Те из вас, кто знаком с теорией компиляции как обучавшиеся в университетах, конечно распознают имена Scanner, Parser и CodeGen, все из которых являются компонентами классической реализации компилятора. Вы можете думать, что я отказался от своих обязательств по отношению к философии KISS и отдрейфовал к более стандартной архитектуре чем мы имели. Более пристальный взгляд, однако, должен убедить вас, что хотя имена схожи, функциональность совершенно различна.

Вместе, сканер и парсер классической реализации составляют так называемый «front end», а генератор кода «back end». Подпрограммы «front end» обрабатывают языкозависимые, связанные с синтаксисом аспекты исходного языка, в то время как генератор кода, или «back end», работает с зависимыми от целевой машины частями проблемы. В классических компиляторах два конца (ends) сообщаются через файл инструкций, написанный на промежуточном языке (IL).

Как правило, классический сканер это одиночная процедура, оперирующая как сопроцедура с синтаксическим анализатором. Она «токенизирует» исходный файл, считывая его символ за символом, распознавая элементы языка, транслируя их в токены и передавая их синтаксическому анализатору. Вы можете думать о синтаксическом анализаторе как об абстрактной машине, выполняющей «op кода», которыми являются токены. Точно также, синтаксический анализатор генерирует «op кода» второй абстрактной машины, которая механизирует IL. Как правило, IL файл записывается на диск синтаксическим анализатором и считывается снова генератором кода.

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

Аналогично, классический генератор кода, «back end», в своем роде тоже транслятор, считывающий «исходный» IL файл и выдающий объектный файл. Наш генератор кода не работает таким способом. В нашем компиляторе нет никакого промежуточного языка; каждая конструкция в синтаксисе исходного языка преобразуется в ассемблер как только она распознана синтаксическим анализатором. Подобно Scanner, модуль CodeGen состоит из индивидуальных процедур, которые вызываются синтаксическим анализатором когда необходимо.

Философия «кодируй как только найдешь» не может производить самый эффективный код в мире – например, мы не обеспечили (пока!) удобное место для оптимизатора – но она несомненно упрощает компилятор, не правда ли?

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

• Философия KISS – никогда не делай сложные вещи без причины.

• Ленивое кодирование – Никогда не откладывай на завтра то, что можешь отложить навсегда. (П. Дж. Плоджер).

• Скептицизм – упрамо отказывайтесь делать что-либо только потому, что это всегда делалось таким способом.

• Принятие неэффективного кода.

• Отклонение произвольных ограничений.

Когда я сделал обзор истории конструирования компиляторов, я узнал, что практически каждый промышленный компилятор в истории страдал из-за предналоженных условий, которые сильно влияли на его дизайн. Первоначальный компилятор Fortran Джона Бэкуса должен был конкурировать с ассемблером и следовательно был вынужден производить чрезвычайно эффективный код. Компиляторы IBM для мини ЭВМ 70-х должны были выполняться в очень небольших объемах ОЗУ тогда доступных – таких небольших как 4k. Ранние компиляторы Ada должны были компилировать себя. Бринч Хансен решил, что его компилятор Паскаля, разработанный для IBM PC должен выполняться на 64k машинах. Компиляторы, разработанные на курсах Computer Science должны были компилировать широкий диапазон языков и следовательно требовали LALR синтаксических анализаторов.

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

Хороший пример – компилятор Бринч Хансена, описанный в его превосходной книге «Brinch Hansen on Pascal Compilers» (строго рекомендую). Хотя его компилятор один из самых ясных и незатемненных реализаций компилятора, что я видел, одно решение, компилировать большие файлы в небольшом ОЗУ, полностью управляло дизайном и он закончил не на одном а многих промежуточных файлах, как и управляющими ими программах для их записи и считывания.

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

В этой обучающей серии мы следовали по шагам таких пионеров в мире маленьких компиляторов для PC как Леор Золман, Рон Каин и Джеймс Хендрих, тех кто не знал достаточно теорию компиляции чтобы знать, что они «не могли делать это таким способом». Мы решительно отказались принимать произвольные ограничения, а скорее делали так, как было проще В результате мы развили архитектуру, которая, хотя и совершенно отлична от классической, делает работу простым и прямым способом.

Я закончу эти философствования обзором понятия промежуточного языка. Хотя я отметил перед этим, что мы не имеем его в нашем компиляторе, это не совсем точно; у нас он есть, или по крайней мере мы развиваем его, в том смысле, что мы определяем функции генерации кода для вызова из парсера. В сущности, каждый вызов процедуры генерации кода можно рассматривать как инструкцию на промежуточном языке. Если мы когда либо найдем необходимым формализировать промежуточный язык, вот способ, которым бы мы сделали это: выдать кода из синтаксического анализатора, представляющие собой вызовы процедур генератора кода, а затем обработать каждый код вызывая эти процедуры в отдельном проходе, реализованном в «back end». Откровенно говоря, я не вижу, что мы когда либо найдем потребность в таком подходе, но это связь, если вы решите следовать ему, между классическим и текущим подходами.