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

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

Заключение

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

Назад в будущее

Введение

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

Новое начало, старое направление

   Подобно многим другим вещам, языки программирования и стили програмирования изменяются со временем. В 1994 году кажется немного анахроничным программировать на Turbo Pascal, когда остальной мир кажется сходит с ума по C++. Также кажется немного странным программировать в классическом стиле, когда остальной мир переключился на объектно-ориентированные методы. Однако, несмотря на четырехлетнюю паузу, было бы слишком тяжело сейчас переключиться, скажем, на C++ с объектной ориентацией. Во всяком случае, Pascal все еще не только мощный язык программирования (фактически больше, чем когда либо), но это и замечательная среда для обучения. Си – известно трудный для чтения язык... он часто был обвиняем, наряду с Forth, как «язык только для записи». Когда я программирую на C++ я трачу по крайней мере 50% своего времени на борьбу с синтаксисом языка а не с концепциями. Сбивающие с толку «&» или "*" могут не только изменить функционирование программы, но также и ее правильность. Наоборот, код Паскаля обычно совершенно ясен и прост для чтения даже если вы не знаете языка. Что вы видите, то вы почти всегда и получите, и мы можем сконцентрироваться на концепциях, а не тонкостях реализации. Я сказал в начале, что целью этой обучающей серии была не генерация самого быстрого в мире компилятора, а изучение основ технологии компиляции, с наименьшими затратами времени на борьбу с синтаксисом языка или другими аспектами реализации программного обеспечения. Наконец, так как многое из того, что мы делаем в этом курсе, составляет программное экспериментирование, важно иметь компилятор и связанную с ним среду, который компилирует быстро и без суеты. По моему мнению наиболее значимым мерилом времени при разработке программного обеспечения является скорость цикла редактирование/компиляция/тестирование. В этом отделе Turbo Pascal – король. Скорость компиляции блестяще быстрая, и продолжает становиться быстрее с каждым выпуском (как им это удается?). Несмотря на крупные усовершенствования в быстродействии компиляции C за последние годы, даже Borland-овский самый быстрый компилятор C/C++ все еще не сравним с Turbo Pascal. Далее, редактор, встроенный в его IDE, средство make, и даже их превосходный умный компоновщик, все дополняют друг друга чтобы получить замечательную среду для быстрой разработки. По всем этим причинам, я собираюсь придерживаться Паскаля в продолжении этой серии. Мы будем использовать Turbo Pascal for Windows, один из компиляторов, предоставляемый Borland Pascal with Objects, версия 7.0. Если у вас нет этого компилятора не волнуйтесь... ничего из того, что мы делаем здесь не будет рассчитано на то, что вы имеете последнюю версию. Использование Windows версии сильно помогает мне, позволяя использовать Clipboard для копирования кода из редактора компилятора в эти документы. Она также должна помочь вам по крайней мере копировать код в обратном направлении.
   Я думал долго и трудно о том, надо ли представить нашему обсуждению объекты. Я большой защитник объектно-ориентированных методов для всех применений и такие методы определенно имеют свое место в технологии компиляции. Фактически, я написал несколько статей только на эти темы (ссылки 1-3). Но архитектура компилятора, основанного на объектно-ориентированных подходах, значительно отличается от архитектуры более классического компилятора, который мы строим. Кроме того, коней на переправе не меняют. Как я сказал, изменяются стили программирования. Кто знает, может быть пройдут еще шесть лет прежде чем мы закончим эти дела, и если мы будем изменять код каждый раз при изменении стиля программирования мы можем никогда не закончить.
   Так что теперь, по крайней мере, я определился продолжать классический стиль в Pascal, хотя мы действительно могли бы обсуждать объекты и объектную ориентацию по ходу дела. Аналогично, целевой машиной останется семейство Motorola 68000. Из всех решений, которые буду приняты здесь, это было самым простым. Хотя я знаю, что многие из вас хотели бы видеть код для 80x86, 68000 является, вообще-то, даже более популярным как платформа для встроенных систем, и это то применение ради которого это все изначально и начиналось. Компилируя для PC, платформы MSDOS, мы должны были бы иметь дело со всеми проблемами системных вызовов DOS, форматов компоновщика DOS, файловой системы PC и аппаратными средствами и всеми другие осложнениями среды DOS. Встроенная система, с другой стороны, должна выполняться автономно и я всегда представлял, что для такого вида применений, как альтернатива ассемблеру, язык подобный KISS процветал бы. В любом случае, кто хочет иметь дело с архитектурой 80x86 если они не должны?
   Одна из возможностей Turbo Pascal которую я собираюсь серьезно использовать это модули. В прошлом мы должны были делать компромиссы между размером кода, сложностью и функциональными возможностями программы. Многое из нашей работы было по природе компьютерным экспериментированием, рассматриванием только одного аспекта технологии компиляции в один момент времени. Мы делали это чтобы избежать возни с большими программами, исследуя только простые понятия. В процессе, мы заново изобретали колесо и заново программировали те же самые функции больше раз, чем я могу сосчитать. Модули Turbo предоставляют замечательный способ получить функциональность и простоту одновременно: вы пишете многократно используемый код и вызываете его в одной строке. Ваша тестовая программа остается маленькой, но она может делать мощные вещи.
   Одна из возможностей модулей Turbo Pascal – их блок инициализации. Как в пакете Ada, любой код в основном блоке begin-end модуля выполняется когда программа инициализирована. Как вы увидите позже, это иногда дает нам хорошее упрощение кода. Наша процедура Init, которая была с нами начиная с Главы 1, полностью исчезает когда мы используем модули. Различные подпрограммы в Cradle, другие ключевые возможности нашего подхода, будут распределены по модулям.
   Концепция модулей, конечно, ничем не отличается от модулей Си. Однако в C (и C++) интерфейс между модулями происходит через операторы include препроцессора и заголовочные файлы. Как кто-то, кто читал множество прогрограмм других людей на C, я всегда находил это довольно сбивающим с толку. Всегда кажется, что любая структура данных, о который вы бы хотели знать, находится в каком-то другом файле. Модули Turbo проще по той причине, за которую они критикуются некоторыми: интерфейсы функций и их реализации включены в тот же самый файл. В то время, когда эта организация может создать проблемы с защитой кода, она также уменьшает количество файлов наполовину, что не в два раза хуже. Связывание объектных файлов также просто, потому что компилятор Turbo заботится об этом без необходимости в файлах типа make или других механизмах.

Начинаем заново?

   Четыре года назад, в Главе 14, я обещал вам, что наши дни повторного изобретения колеса и написания одних и тех же программ на каждом уроке, прошли и что с этого момента мы будем придерживаться более завершенных программ, к которым мы должны просто добавлять новые возможности. Я все еще собираюсь сдержать это обещание; это одна из основных целей использования модулей. Однако, из-за прошествия длительного времени с главы 14, естественно хотелось бы сделать по крайней мере небольшой обзор и в любом случае мы окажемся перед необходимостью сделать довольно обширные изменения кода, чтобы выполнить переход к модулям. Кроме того, если откровенно, после всего этого времени я не могу помнить всех хороших идей, которые я имел в моей голове четыре года назад. Для меня лучший способ вспомнить их – заново пройти некоторые шаги, которые привели нас к Главе 14. Так что я надеюсь, что вы поймете и смиритесь со мной когда мы возвратимся к своим корням, в некотором смысле, и перестроим ядро программы, распределяя подпрограммы по различным модулям, и вытащим сами себя назад к точке где мы были многие луны тому назад. Как всегда бывало, вы увидите все мои ошибки и смены направлений в реальном режиме времени. Пожалуйста, будьте терпеливы... мы доберемся до новых вещей раньше чем вы успеете оглянуться.
   Так как в нашем новом подходе мы собираемся использовать множественные модули, мы должны обратиться к проблеме управления файлами. Если вы проследовали через все другие разделы этой обучающей серии, вы знаете, что поскольку наша программа развивается, мы заменяем старые, более простые модули на более совершенные. Это приводит нас к проблеме контроля версий. Почти обязательно будут возникать ситуации, когда мы будем перекрывать простой файл (модуль), но позднее захотим иметь его снова. Данный случай воплощен в нашей склонности к использованию односимвольных имен переменных, ключевых слов и т.д. для проверки основных понятий не захлебываясь в деталях лексического анализатора. Благодаря использованию модулей мы будем намного меньше делать это в будущем. Однако, я не только предполагаю, но я уверен, что мы будем должны сохранять некоторые старые версии файлов для специальных целей, даже при том, что они заменяются более новыми, более совершенными.
   Для решения этой проблемы я предлагаю, чтобы вы создали различные каталоги с различными версиями модулей. Если мы сделаем это правильно, код в каждом каталоге останется само-непротиворечивым. Я в порядке эксперимента создал четыре каталога: SINGLE (для односимвольных экспериментов), MULTI (для, конечно, многосимвольной версии), TINY и KISS.
   Достаточно сказано о философии и деталях. Давайте продолжим восстановление программы.

Модуль INPUT

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

   {–}
   unit Input;
   {–}
   interface
   var Look: char; { Lookahead character }
   procedure GetChar; { Read new character }
   {–}
   implementation
   {–}
   { Read New Character From Input Stream }
   procedure GetChar;
   begin
   Read(Look);
   end;
   {–}
   { Unit Initialization }
   begin
   GetChar;
   end.
   {–}

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

   {–}
   program Main;
   uses WinCRT, Input;
   begin
   WriteLn(Look);
   end.
   {–}

   Обратите внимание на использование предоставляемого Borland модуля WinCRT. Этот модуль необходим, если вы предполагаете использовать стандартные подпрограммы ввода/вывода Паскаля Read, ReadLn, Write и WriteLn, которые мы конечно предполагаем использовать. Если вы забудете включить этот модуль в раздел «uses» вы получите действительно причудливое и непонятное сообщение во время выполнения.
   Заметьте также, что мы можем обращаться к предсказывающему символу даже при том, что он не объявлен в основной программе. Все переменные, объявленные в разделе interface модуля, являются глобальными, но они скрыты от любопытных глаз; в какой-то степени мы получаем чуточку сокрытия информации. Конечно, если бы мы писали в объектно-ориентированном стиле, мы не должны были бы позволять обращаться к внутренним переменным модуля снаружи. Но хотя модули Turbo имеют много общего с объектами, мы не собираемся здесь реализовывать объектно ориентированный дизайн или код, так что мы используем Look соответствующее.
   Продолжим и сохраним тестовую программу как Main.pas. Чтобы сделать жизнь проще когда файлов будет становиться все больше и больше, вам возможно захотелось бы использовать возможность объявить этот файл как Primary файл компилятора. Таким способом вы можете выполнять программу из любого файла. Иначе, если вы нажимете Cntl-F9 для компиляции и выполнения одного из модулей, вы получите сообщение об ошибке. Вы устанавливаете primary-файл используя главное подменю «Compile» в Turbo IDE.
   Я тороплюсь отметить, как я делал раньше, что функционально модуль Input является, и всегда был, макетом настоящей версии. В серийной версии компилятора входной поток будет, конечно, скорее исходить из файла, а не клавиатуры. И это почти обязательно включает буферизацию строки, по крайней мере, и более вероятно, довольно большой текстовый буфер для поддержки эффективного дискового ввода/вывода. Хорошая сторона модулей в том, что как и с объектами мы можем делать код модуля таким простым или таким сложным как нам угодно. До тех пор, пока интерфейс, встроенный в общедоступные процедуры и предсказывающий символ не изменяются, остальная часть программы абсолютно незатрагивается. И так как модули компилируются, а не просто включаются, время необходимое для связывания их вместе практически равно нулю. Снова, результат таков, что мы можем получить все преимущества сложной реализации без необходимости возиться с кодом как лишним багажом.
   В следующих главах я предполагаю предоставить полноценный IDE для компилятора KISS используя настоящее Windows приложение, сгенерированное с помощью среды разработки Borland OWL. Сейчас, тем не менее, мы удовлетворим мое первое правило: Делать Это Проще.

Модуль OUTPUT

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

   {–}
   unit Output;
   {–}
   interface
   procedure Emit(s: string); { Emit an instruction }
   procedure EmitLn(s: string); { Emit an instruction line }
   {–}
   implementation
   const TAB = ^I;
   {–}
   { Emit an Instruction }
   procedure Emit(s: string);
   begin
   Write(TAB, s);
   end;
   {–}
   { Emit an Instruction, Followed By a Newline }
   procedure EmitLn(s: string);
   begin
   Emit(s);
   WriteLn;
   end;
   end.
   {–}

   (Заметьте, что этот модуль не имеет раздела инициализации, так что он не требует блока begin.)
   Проверьте этот модуль с помощью следующей основной программы:

   {–}
   program Test;
   uses WinCRT, Input, Output, Scanner, Parser;
   begin
   WriteLn('MAIN:");
   EmitLn('Hello, world!');
   end.
   {–}

   Увидели ли вы что-либо, что удивило вас? Вы возможно были удивлены видеть, что вам было необходимо что-то набрать даже хотя основная программа не требует никакого ввода. Дело в разделе инициализации модуля Input, который все еще требует поместить что-либо в предсказывающий символ. Жаль, нет никакого способа выйти из этого, или скорее, мы не хотим выходить. За исключением простых тестовых случаев, как этот, нам всегда будет необходим допустимый предсказывающий символ, так что самое лучшее, что мы можем сделать с этой «проблемой» это... ничего.
   Возможно более удивительно то что символ TAB не имеет никакого эффекта; наша строка «инструкций» начинается с первой колонки так же как и фальшивая метка... Правильно: WinCRT не поддерживает табуляцию. У нас проблема.
   Есть несколько способов, с помощью которых мы можем решить эту проблему. Один из вариантов того что мы можем сделать – просто игнорировать ее. Каждый ассемблер, который я когда либо использовал, резервируют колонку 1 для меток и взбунтуется когда увидит, что в ней начинаются инструкции. Так что, по крайней мере, мы должны сдвинуть инструкции на одну колонку чтобы сделать ассемблер счастливым. Это достаточно просто сделать: просто измените в процедуре Emit строку:
   Write(TAB, s);
   на
   Write(' ', s);
   Я должен признать что сталкивался с этой проблемой раньше и находил себя меняющим свое мнение так часто как хамелеон меняет цвет. Для наших целей, 99% которых будет проверка выходного кода при выводе на CRT, было бы хорошо видеть аккуратно сгруппированный «объектный» код. Строка:
   SUB1: MOVE #4,D0
   просто выглядит более опрятно, чем отличающийся, но функционально идентичный код:
   SUB1: 
   MOVE #4,D0
   В тестовой версии моего кода я включил более сложную версию процедуры PostLabel, которая позволяет избежать размещения меток на раздельных строках, задерживая печать метки чтобы она оказалась на той же самой строке, что и связанная инструкция. Не позднее чем час назад, моя версия модуля Output предоставляла полную поддержку табуляции с использованием внутренней переменной счетчика столбцов и подпрограммы для ее управления. Я имел некоторый довольно изящный код для поддержки механизма табуляции с минимальным увеличением кода. Было ужасное искушение показать вам эту «красивую» версию, единственно чтобы покрасоваться элегантностью.
   Однако, код «элегантной» версии был значительно более сложным и большим. После этого у меня появилась вторая мысль. Несмотря на наше желание видеть красивый вывод, неизбежный факт то, что две версии MAIN: фрагменты кода, показанные выше функционально идентичны; ассемблер, который является конечной целью кода, не интересует какую версию он получает, за исключением того, что красивая версия будет содержать больше символов, следовательно будет использовать больше дискового пространства и дольше ассемблироваться. Но красивая версия не только генерирует больше кода, но дает больший выходной файл, с гораздо большим количество пустых символов чем минимально необходимо. Когда вы посмотрите на это с такой стороны, то не трудно будет решить какой подход использовать, не так ли?
   То что наконец решило для меня этот вопрос было напоминанием считаться с моей первой заповедью: KISS. Хотя я был довольно горд всеми своими изящными приемчиками для реализации табуляции, я напомнил себе, что перефразируя сенатора Барри Голдватера, элегантность в поисках сложности не является достоинством. Другой мудрый человек однажды написал: «Любой идиот может разработать Роллс-Ройс. Требуется гений, чтобы разработать VW». Так что изящная, дружественная табуляции версия Output в прошлом, и то, что вы видите, это простая компактная VW версия.

Модуль ERROR

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

   {–}
   unit Errors;
   {–}
   interface
   procedure Error(s: string);
   procedure Expected(s: string);
   {–}
   implementation
   {–}
   { Write error Message and Halt }
   procedure Error(s: string);
   begin
   WriteLn;
   WriteLn(^G, 'Error: ', s, '.');
   Halt;
   end;
   {–}
   { Write «<something> Expected» }
   procedure Expected(s: string);
   begin
   Error(s + ' Expected');
   end;
   end.
   {–}
   Как обычно, вот программа для проверки:
   {–}
   program Test;
   uses WinCRT, Input, Output, Errors;
   begin
   Expected('Integer');
   end.
   {–}

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

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

   Классическая архитектура компилятора основана на отдельных модулях для лексического анализатора, который предоставляет лексемы языка, и синтаксического анализатора, который пытается определить смысл токенов как синтаксических элементов. Если вы еще не забыли что мы делали в более ранних главах, вы вспомните, что мы не делали ничего подобного. Поскольку мы используем предсказывающий синтаксический анализатор, мы можем почти всегда сказать, какой элемент языка следует дальше, всего-лишь исследуя предсказывающий символ. Следовательно, нам не нужно предварительно выбирать токен, как делал бы сканер.
   Но даже хотя здесь и нет функциональной процедуры, названной «Scanner», все еще имеет смысл отделить функции лексического анализа от функций синтаксического анализа. Так что я создал еще два модуля, названных, достаточно удивительно, Scanner и Parser. Модуль Scanner содержит все подпрограммы, известные как распознаватели. Некоторые из них, такие как IsAlpha, являются чисто булевыми подпрограммами, которые оперируют только предсказывающим символом. Другие подпрограммы собирают токены, такие как идентификаторы и числовые константы. Модуль Parser будет содержать все подпрограммы, составляющие синтаксический анализатор с рекурсивным спуском. Общим правилом должно быть то, что модуль Parser содержит всю специфическую для языка информацию; другими словами, синтаксис языка должен полностью содержаться в Parser. В идеальном мире это правило должно быть верным в той степени, что мы можем изменять компилятор для компиляции различных языков просто заменяя единственный модуль Parser.
   На практике, дела почти никогда не бывают такими чистыми. Все есть небольшая «утечка» синтаксических правил также и в сканер. К примеру, правила составления допустимого идентификатора или константы могут меняться от языка к языку. В некоторых языках правила о комментариях разрешают им быть отфильтрованными в сканере, в то время как другие не разрешают. Так что на практике оба модуля вероятно придут к тому, что будут иметь языко-зависимые компоненты, но изменения, необходимые для сканнера, должны быть относительно тривиальными.
   Теперь вспомните, что мы использовали две версии подпрограмм лексического анализатора: одна, которая поддерживала только односимвольные токены, которую мы использовали в ряде наших тестов, и другая, которая предоставляет полную поддержку многосимвольных токенов. Теперь, когда мы разделяем нашу программу на модули, я не ожидаю многого от использования односимвольной версии, но не потребуется многого, чтобы предусмотреть их обе. Я создал две версии модуля Scanner. Первая, названная Scanner1, содержит односимвольную версию подпрограмм распознавания: