Как я писал компилятор С++. Пересказ спустя 15 лет

15 лет назад не было Хабрахабра, не было фейсбука, и что характерно, не было компилятора С++, с выводом диагностических сообщений на русском. С тех пор, вышло несколько новых стандартов С++, технологии разработки сделали гигантский скачек, а для написания своего языка программирования или анализатора кода может потребоваться в разы меньше времени, используя существующие фреймворки. Пост о том, как я начинал свою карьеру и путем самообразования и написания компилятора С++, пришел к экспертному уровню. Общие детали реализации, сколько времени это заняло, что получилось в итоге и смысл затеи — тоже внутри.

С чего все начиналось

В далеком 2001-ом году, когда мне купили первый компьютер Duron 800mhz/128mb ram/40gb hdd, я стремительно взялся за изучение программирования. Хотя нет, сначала меня постоянно мучил вопрос, что же поставить Red Hat Linux, FreeBSD или Windows 98/Me? Ориентиром в этом бесконечном мире технологий для меня служил журнал Хакер.
Старый такой, стебный журнал. К слову, с тех пор, стиль изложения в этом издании почти не поменялся.
Виндузятники, ламеры, трояны, элита, линух — вот это все сносило крышу. Реально хотелось
поскорей освоить этот весь стек, которые они там печатали и хакнуть Пентагон (без интернета).
Внутренняя борьба за то, становиться ли Линуксоидом или рубится в игры на винде продолжалась до тех пор, пока в дом не провели интернет. Модемный, скрежечащий 56kb/s интернет, который занимал телефон на время подключения, и качал mp3-песню в районе получаса. При цене порядка 0.1$/mb, одна песня вытягивала на 40-50 центов. Это днем.

А вот ночью, были совсем другие расценки. Можно было с 23.00 до 6.00 залипать во все сайты не отключая изображения в браузере! Поэтому все что можно было скачать из сети за ночь, качалось на винт, и далее прочитывалось уже днем.
В первый день, когда мне домой провели и настроили сеть, админ передо мной открыл IE 5 и Яндекс. И быстро ретировался. Думая, что же первым делом искать в сети, я набрал что-то вроде «сайт для программистов». На что первой ссылкой в выдаче выпал совсем недавно открывшийся rsdn.ru ^[1]. И на нем я стал зависать продолжительное время, испытывая чувство неудовлетворенности, от того, что мало что понимаю. На то время флагманом и самым популярным языком на форуме (да и вообще) был С++. Поэтому вызов был брошен, и ничего не оставалось, как догонять бородатых дядек в их знаниях по С++.
А еще был не менее интересный сайт на то время — firststeps.ru ^[2]. Я до сих пор считаю их метод подачи материала наилучшим. Маленькими порциями (шагами), с небольшими результатами конечными результатами. Тем не менее все получалось!

Активно скупая книги на барахолке, я стремился постичь все азы программирования. Одной из первых купленных книг было «Искусство программирования» — Д. Кнут. Не помню точную мотивацию купить именно эту книгу, а не какой-нибудь С++ для кофейников, наверное продавец порекомендовал, но я со всем своим усердием школьника взялся за изучение первого тома, с обязательным выполнением задач в конце каждой главы. Это была самая мякотка,
и хотя с математикой у меня в школе не ладилось, но зато с мат.аном Кнута прогресс был, потому что было огромное желание и мотивация писать программы и делать это правильно. Осилив алгоритмы и структуры данных, я купил уже 3-ий том «Искусства программирования» Сортировка и поиск. Это была бомба. Пирамидальная сортировка, быстрая сортировка, бинарный поиск, деревья и списки, стеки и очереди. Все это я записывал на листочке, интерпретируя результат в своей голове. Читал дома, читал когда был на море, читал везде. Одна сплошная теория, без реализации. При этом я даже не догадывался, какую огромную пользу принесут эти базовые знания в будущем.
Сейчас, проводя собеседования с разработчиками, мне еще не встретился человек, который смог бы написать реализацию бинарного поиска или быстрой сортировки на листочке. Жаль.

Но вернемся к теме поста. Осилив Кнута, надо было двигаться дальше. Попутно я сходил на курсы Turbo Pascal, прочитал Кернигана и Ритчи, а за ними С++ за 21 день. Из С и С++, мне было не все понятно, я просто брал и переписывал тексты из книг. Загуглить или спросить было не у кого, но зато времени было вагон, так как школу я забросил и перешел в вечернюю, в которую можно было практически не ходить, или появляться на 3-4 урока в неделю.
В итоге с утра до ночи, я фанатично развивался, познавая все новые и новые темы. Мог написать калькулятор, мог написать простое приложение на WinApi. На Delphi 6 тоже получалось что-то нашлепать. В итоге, получив диплом о среднем образовании, я уже был подготовлен на уровне 3-4 курса университета, и разумеется на какую специальность идти учится вопроса не стояло.

Поступив на кафедру Компьютерных систем и сетей, я уже свободно писал на С и С++ задачи любого уровня сложности университета. Хотя, зайдя на тот же rsdn.ru,
понимал, как много еще нужно изучить и насколько бывалые форумчане прокаченней меня в плюсах. Это задевало, непонимание и вместе с тем жгучее желание знать все, привело меня к книге «Компиляторы. Инструменты. Методы. Технологии» — А.Ахо, Рави Сети. В простонародье именуемой книгой Дракона. Вот тут и началось самое интересное. Перед этой книгой, был прочитан
Герберт Шилдт, Теория и практика С++ ^[3], в которой он раскрывал продвинутые темы разработки, такие как
шифрование, сжатие данных, и самое интересное — написание собственного парсера.

Начав скрупулезно изучать книгу дракона, двигаясь от лексического анализа, затем к синтаксическому и наконец к проверке семантики и генерации кода, ко мне пришло судьбоносное решение — написать свой компилятор С++.
— А почему бы и нет, спросил себя?
— А давай, ответила та часть мозга ^[4], которая с возрастом становится все скептичней ко всему
новому. И разработка компилятора началась.

Подготовка

Модемный интернет к тому времени мне перекрыли, в силу смены телефонных линий на цифровые, поэтому для ориентира был скачан стандарт ISO C++ редакции 1998 года ^[5]. Уже полюбившимся и привычным инструментом стала Visual C++ 6.0.
И по сути задача свелась к тому, чтобы реализовать то, что написано в стандарте С++. Подспорьем в разработке компилятора была книга дракона. А отправной точкой, был парсер-калькулятор из книги Шилдта. Все части пазла собрались воедино и разработка началась.

Препроцессор

nrcppKPP_1.1 ^[6]
Во 2-ой главе в стандарте ISO C++ 98 идут требования к препроцессору и лексические конвенции (lexical conventions). Вот и славно, подумал я, ведь это наиболее простая часть и может реализоваться отдельно от самого компилятора. Другими словами, сначала запускается препроцессинг файла, на вход которому поступает С++ файл в том виде, котором вы привыкли его видеть. А после препроцессинга, на выходе мы имеем преобразованный С++ файл, но уже без комментариев, подставленными файлами из #include, подставленными макросами из #define, сохраненными #pragma и обработанной условной компиляцией #if/#ifdef/#endif.

#define MAX(a, b) 
	((a) > (b) ? a : b)
#define STR(s)  #s

/*
 This is the entry point of program
 */
int main()
{
	printf("%s: %d", STR(This is a string), MAX(4, 5));
}

int main()
{
          printf("%s: %d", "This is a string", ((4) > (5) ? 4 : 5));
}

В довесок, препроцессор ^[7] делал еще много полезной работы, вроде вычисления константных выражений, конкатенации строковых литералов, вывода #warning и #error. Ах да, вы когда нибудь видели в С-коде Диграфы и триграфы? Если нет, знайте — они существуют!

Разумеется, основной пользой от препроцессора С++, является подстановка макросов и вставка файлов обозначенных в #include.
Чему я научился в процессе написания препроссора С++?

• Как устроена лексика и синтаксис языка
• Приоритеты операторов С++. И в целом как вычисляются выражения
• Строки, символы, контанты, постфиксы констант
• Структура кода

В целом, на написание препроцессора ушло порядка месяца. Не слишком сложно, но и нетривиальная задача, тем не менее.
В это время, мои одногруппники пытались написать первый «Hello, world!», да хотя бы собрать его. Далеко не у всех получалось. А меня ждали следующие разделы стандарта С++, с уже непосредственной реализацией компилятора языка.

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

nrcpp/LexicalAnalyzer.cpp ^[9]
Тут все просто, основную часть анализа лексики я уже написал в препроцессоре. Задача лексического анализатора — разобрать код на лексемы или токены, которые уже будет анализироваться синтаксическим анализатором.
Что было написано на этом этапе?

• Конечный автомат для анализа целочисленных, вещественных и символьных констант. Думаете это просто? Впрочем просто, когда ты это прошел.
• Конечный автомат для анализа строковых литеров
• Разбор имен переменных и ключевых слов С++
• Что-то еще, как пить дать. Вспомню допишу

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

nrcpp/Parser.cpp ^[10]
Задача синтаксического анализатора — проверить правильность расстановки лексем, который были получены на этапы лексического анализа.
За основу синтаксического анализатора были взяты опять же простенький парсер из Шилдта, прокаченный до уровня синтаксиса С++, с проверкой переполнения стека. Если мы например напишем:

(((((((((((((((((((((((((((((0))))))))))))))))))))))))))))))))); // кол-во скобок может быть больше

То мой рекурсивный анализатор съест стэк, и выдаст, что выражение слишком сложное.
У внимательного читателя, может возникнуть вопрос. А зачем изобретать велосипед, ведь был же yacc и lex. Да, был. Но на том этапе, хотелся велосипед с полным контролем над кодом. Разумеется в производительности он уступал сгенерированному этими утилитами коду. Но не в этом была цель — техническое совершенство. Цель была — понять все.

Семантика

nrcpp/Checker.cpp ^[11]
nrcpp/Coordinator.cpp ^[12]
nrcpp/Overload.cpp ^[13]

Занимает соотвественно главы с 3-ей по 14-ую стандарта ISO C++ 98. Эта наиболее сложная часть, и я уверен, что >90% С++ разработчиков не знает всех правил описанных в этих разделах. Например:
Знали ли вы, что функцию можно объявлять дважды, таким образом:

void f(int x, int y = 7);
void f(int x = 5, int y);

Есть такие конструкции для указателей:

const volatile int *const volatile *const p;

А это указатель на функцию-член класса X:

void (X::*mf)(int &)

Это первое, что пришло в голову. Стоит ли говорить, что при тестировании кода из стандарта в Visual C++ 6, я не редко получал Internal Compiler Error.

Разработка анализатора семантики языка заняла у меня 1.5 года, или полтора курса универа. За это время меня чуть не выгнали, по другим предметам кроме программирования, за счастье получалась тройка (ну, ок четверка), а компилятор тем временем разрабатывался и обрастал функционалом.

Генератор кода

nrcpp/Translator.cpp ^[14]
На этом этапе, когда энтузиазм немного начал угасать, уже имеем вполне рабочую версию фронт-енд компилятора. Что дальше делать с этим фронт-ендом, разработчик решает сам. Можно распространять его в таком виде, можно использовать для написания анализатора кода, можно использовать для создания своего конвертера вроде С++ -> C#, или C++ -> C. На этом этапе у нас есть провалидированное синтаксически и семантически AST (abstract syntax tree).
И на этом этапе разработчик компилятора понимает, что он постиг дзен, достиг просветления, может неглядя понять почему код работает именно таким образом. Для добивания своей цели, создания компилятора С++, я решил закончить на генерации С-кода, который затем можно было бы конвертировать в любой существующий ассемблерный язык или подавать на вход существующим Сишным компиляторам (как делал Страуструп в первых версиях «С с классами»).

Чего нет в nrcpp?

• Шаблоны (templates). Шаблоны С++, эта такая хитровымудренная система с точки зрения реализации, что мне пришлось признать, без вмешательства в синтаксический анализатор и смешивания его с семантикой — шаблоны должным образом работать не будут.
• namespace std. Стандартную библиотеку без шаблонов не напишешь. Да впрочем и заняло бы это еще много-много месяцев, так как занимает львиную долю стандарта.
• Внутренние ошибки компилятора. Если вы будете играться с кодом, то сможете увидеть сообщения вроде:
  внутренняя ошибка компилятора: in.txt(20, 14): «theApp.IsDiagnostic()» --> (Translator.h, 484)
  Это либо не реализованный функционал, либо не учтенные семантические правила.

Зачем писать свой велосипед?

А в заключении хочу отметить то, ради чего писалась этот пост. Написание своего велосипеда, даже если на это потрачено 2 с лишним года, кормит меня до сих пор. Это бесценные знания, база, которая будет с Вами на протяжении всей карьеры разработчика. Будут меняться технологии, фреймворки, выходить новые языки — но фундамент в них будет заложен из прошлого. И на их понимание и освоение уйдет совсем немного времени.

github.com/nrcpp/nrcpp ^[15] — исходники компилятора. Можно играться правя файл in.txt и смотреть вывод в out.txt.
github.com/nrcpp/nrcpp/tree/master/KPP_1.1 ^[6] — исходники препроцессора. Собирается с помощью Visual C++ 6.

Автор: nrcpp

Источник ^[16]