Джек Креншоу - Давайте создадим компилятор!

• Название: Давайте создадим компилятор!
• Автор: Джек Креншоу
• Жанр: Программирование

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

---

Используя этот принцип, в Главе 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». Откровенно говоря, я не вижу, что мы когда либо найдем потребность в таком подходе, но это связь, если вы решите следовать ему, между классическим и текущим подходами.

Расширение синтаксического анализатора

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