Компилятор домашнего приготовления. Часть 1
Почему мне пришла в голову идея разработать собственный компилятор? Однажды мне на глаза попалась книга, где описывались примеры проектирования в AutoCAD на встроенном в него языке AutoLISP. Я захотел c ними разобраться, но прежде меня заинтересовал сам ЛИСП. “Неплохо бы поближе познакомиться с ним”, – подумал я и начал подыскивать литературу и среду разработки. С литературой все оказалось просто – по ЛИСПу ее море в Интернете. Достаточно зайти на портал [1]. Дело оставалось за малым – найти хорошую среду программирования, и вот тут-то начались трудности. Компиляторов под ЛИСП тоже немало, но все они оказались мне малопонятны. Ни один пример из Вики, по разным причинам, не отработал нормально в скачанных мною компиляторах. Собственно, серьезно я с ними не разбирался, но, увы, во многих не нашел как скомпилировать EXE-файл. Самое интересное, что компиляторы эти были собраны разными людьми практически в домашних условиях…
И мне пришла в голову мысль: а почему бы не попробовать самому написать свой компилятор или, основываясь на каком-либо диалекте какого-либо языка, свой собственный язык программирования? К тому же на форумах я часто видел темы, где слезно жаловались на тиранов-преподавателей, поставивших задачу написания курсовой – компилятора или эвалюатора (программы, вычисляющей введенное в виде строки выражение). Мне стало еще интереснее: а что если простому студенту, не искушенному книгами Вирта или Страуструпа, написать такую программу? Появился мотив.
In the Beginning
Итак, начнем. Прежде всего, нужно поставить задачу хотя бы на первом этапе. Задача будет банальная: доказать самому себе, что написание компилятора не такой уж сложный и страшный процесс. И что мы, хитрые и смекалистые, способны родить в муках собственного творчества шедевр, который, возможно, полюбится массам. Да и вообще: приятно писать программы на собственном языке, не так ли?
Что ж, цель поставлена. Теперь самое время определиться со следующими пунктами:
- Под какую платформу будет компилировать код программа?
- На каком языке будет код, переводимый в машинный язык?
- На чем будем писать сам компилятор?
Первый пункт достаточно важен, ибо широкое разнообразие операционных систем (даже три монстра – Windows, Linux и MacOS) уже путают все карты. Их исполняемые файлы по-разному устроены, так что нам, простым смертным, придется выбрать из этой “кагалы” одну операционную систему и, соответственно, ее формат исполняемых файлов. Я предлагаю начать с Windows, просто потому, что мне нравится эта операционная система более других. Это не значит, что я терпеть не могу Linux, просто я его не очень хорошо знаю, а такие начинания лучше делать по максимуму, зная систему, для которой проектируешь.
Два остальных пункта уже не так важны. В конце концов, можно придумать свой собственный диалект языка. Я предлагаю взять один из старейших языков программирования – LISP. Из всех языков, что я знаю, он мне кажется более простым по синтаксису, более атомарным, ибо в нем каждая операция берется в скобочки; таким образом, к нему проще написать анализатор. С выбором, на чем писать, еще проще: писать нужно на том языке, который лучше всего знаешь. Мне ближе паскалевидные языки, я хорошо знаю Delphi, поэтому в своей разработке я избираю именно его, хотя никто не мешает сделать то же самое на Си. Оба языка прекрасно подходят для написания такого рода программ. Я не беру в расчет Ассемблер потому, что его диалект приближен к машинному языку, а не к человеческому.
To Shopping
Выяснив платформу, для которой будем писать компилятор (я имею в виду Win32), подберем все необходимое для комфортной работы. Давайте составим список, что же нам пригодится в наших изысканиях.
Для начала нам просто крайне необходимо выяснить, как же все-таки компиляторы генерируют исполняемые EXE-файлы под Windows. Для этого стоит почитать немного об устройстве этих “экзэшек”, как их часто называют, покопаться в их “кишках”. В этом могут помочь современные отладчики и дизассемблеры, способные показать, из чего состоит “экзэшка”. Я знаю два, на мой взгляд, лучших инструмента: OllyDebugger (он же “Оля”) и The Interactive Disassembler (в простонародье зовущийся IDA).
Оба инструмента можно достать на их официальных сайтах http://www.ollydbg.de/ и http://www.hex-rays.com/idapro. Они помогут нам заглянуть в святая святых – храм, почитаемый загрузчиком исполнимых файлов, – и посмотреть, каков интерьер этого храма, дабы загрузчик наших экзэшек чувствовал себя в нем так же комфортно, как “ковбой в подгузниках Хаггис”.
Также нам понадобится какая-нибудь экзэшка в качестве жертвы, которую мы будем препарировать этими скальпелями-дизассемблерами. Здесь все сложнее. Дело в том, что благородные компиляторы имеют дурную привычку пихать в экзэшник, помимо необходимого для работы кода, всякую всячину, зачастую ненужную. Это, конечно, не мусор, но без него вполне можно обойтись, а вот для нашего исследования внутренностей экзэшек он может стать серьезной помехой. Мы ведь не Ричарды Столлманы и искусством реверсинга в совершенстве не владеем. Поэтому нам лучше было бы найти такую программу, которая содержала бы в себе как можно меньше откомпилированного кода, дабы не отвлекаться на него. В этом нам может помочь компилятор Ассемблера для Windows. Я знаю два неплохих компилятора: Macro Assembler (он же MASM) и Flat Assembler (он же FASM). Я лично предпочитаю второй – у него меньше мороки при компилировании программы, есть собственный редактор, в отличие от MASM компиляция проходит нажатием одной-единственной кнопки. Для MASM разработаны среды проектирования, например MASM Builder. Это достаточно неплохой визуальный инструмент, где на форму можно кидать компоненты по типу Delphi или Visual Studio, но, увы, не лишенный багов. Поэтому воспользуемся FASM. Скачать его можно везде, это свободно распространяемый инструмент. Ну и, конечно, не забудем о среде, на которой и будет написан наш компилятор. Я уже сказал, что это будет Delphi. Если хотите конкретнее – Delphi 6.
The Theory and Researching
Прежде чем приступить к написанию компилятора, неплохо бы узнать, что это за формат “экзэшка” такой. Согласно [2], Windows использует некий PE-формат. Это расширение ранее применявшегося в MS-DOS, так называемого MZ формата [3]. Сам чистый MZ-формат простой и незатейливый – это 32 байта (в минимальном виде, если верить FASM; Турбо Паскаль может побольше запросить), где содержится описание для DOS-загрузчика. В Windows его решили оставить, видимо, для совместимости со старыми программами. Вообще, если честно, размер DOS-заголовка может варьироваться в зависимости от того, что после этих 28 байт напихает компилятор. Это может быть самая разнообразная информация, например для операционок, которые не смогли бы использовать скомпилированный DOS или Windows-экзэшник, представленная в качестве машинного кода, который прерываниями BIOS выводит на экран надпись типа “Эта программа не может быть запущена…”. Кстати, сегодняшние компиляторы поступают так же.
Давайте посмотрим на это чудо техники, воспользовавшись простенькой программой, написанной на чистом Ассемблере FASM (см. Рис. 1):
Рис. 1. Исходник для препарирования
Сохраним файл под неким именем, например Dumpy. Нажмем F9 или выберем в меню пункт RUN. В той же папке будет создан EXE-файл. Это и будет наша жертва, которую мы будем препарировать. Теперь ничто не мешает нам посмотреть: “из чего же, из чего же сделаны наши девчонки?”.
Запустим OllyDebuger. Откроем в “Оле” наш экзэшник. Поскольку фактически кода в нем нет, нас будет интересовать его устройство, его структура. В меню View есть пункт Memory, после выбора которого “Оля” любезно покажет структуру загруженного файла (см. Рис. 2):
Рис. 2. Карта памяти Dumpy
Это не только сам файл, но и все, что было загружено и применено вместе с ним, библиотеки, ресурсы программы и библиотек, стек и прочее, разбитое на блоки, называемые секциями. Из всего этого нас будут интересовать три секции, владелец которых Dumpy, – это непосредственно содержимое загруженного файла.
Собственно, эти секции были описаны нами в исходнике, я не зря назвал их по-русски (ведь операционной системе все равно, как названы секции, главное – их имена должны укладываться точь-в-точь в 8 байт. Это придется учесть обязательно).
Заглянем в первую секцию PE Header. Сразу же можем увидеть (см. Рис. 3), что умная “Оля” подсказывает нам, какие поля* у этой структуры:
Рис. 3. MZ-заголовок
Последнее поле, которое для нас важно, находится по смещению 3Ch от начала файла (см. Рис. 4):
Рис. 4. Смещение на PE-заголовок
Это поле – точка начала РЕ-заголовка. В Windows, в отличие от MS-DOS, MZ-заголовок заканчивается именно на отметке 40**, что соответствует 64 байтам. При написании компилятора будем соблюдать это правило неукоснительно.
Что ж, перейдем непосредственно к PE-заголовку (см. Рис. 5). Как показывает “Оля”, нам нужно перейти на 80-й байт. Да, чуть не забыл. Все числа адресации указываются в 16-тиричной системе счисления. Для этого после чисел ставится латинская буква “H”. “Оля” не показывает ее, принимая эту систему по умолчанию для адресации. Это нужно учесть, чтобы не запутаться в исследованиях. Фактически 80h – это 128-й байт.
Рис. 5. Начало РЕ-заголовка
Вот она, святая обитель характеристик экзэшника. Именно этой информацией пользуется загрузчик Windows, чтобы расположить файл в памяти и выделить ему необходимую память для нужд. Вообще, считается, что этот формат хорошо описан в литературе. Достаточно выйти через Википедию по ссылкам в ее статьях [4] или банально забить в поисковик фразу вроде “ФОРМАТ ИСПОЛНЯЕМЫХ ФАЙЛОВ PortableExecutables (PE)”, как сразу же можно найти кучу описаний. Поэтому я поясню только основные его поля, которые нам понадобятся непосредственно для написания компилятора…
Прежде всего, это PE Signature – 4-хбайтовое поле. В разной литературе оно воспринимается по-разному. Иногда к нему приплюсовывают еще поле Machine, оговариваясь, чтобы выравнять до 8 байт. Мы же, как любители исследовать, доверимся “Оле” с “Идой” и будем разбирать поля непосредственно по их подсказкам. Это поле содержит две латинские буквы верхнего регистра “PE”, как бы намекая нам, что это Portable Executable-формат.
Следующее за ним поле указывает, для какого семейства процессоров пригоден данный код. Всего их, как показывает литература, 7 видов:
Думаю, нам стоит выбрать из всего этого второй вид – 80386. Кстати, наблюдательные личности могли заметить, что в компиляторах Ассемблера есть директива, указывающая, какое семейство процессора использовать, как, например, в MASM (см. Рис. 6):
Рис. 6. Указание семейства процессоров в МАСМ
386 как раз и говорит о том, что в этом поле будет стоять значение 014Ch***.
Следующее важное для нас поле – NumberOfSections. Это количество секций без учета PE-секции. Имеются в виду только те секции, которые принадлежат файлу (в карте памяти их владелец – Dumpy). В нашем случае это “Данные” и “код”.
Следующее поле хоть и не столь важно, но я его опишу. Это TimeDateStamp – поле, где хранится дата и время компиляции. Вообще, я его проигнорирую, не суть важно сейчас, когда был скомпилирован файл. Впрочем, если кому захочется помещать туда время, то флаг в руки.
Сразу хочу предупредить, что меня как исследователя не интересовали поля с нулевыми значениями. На данном этапе они действительно неважны, поэтому в компиляторе их и нужно будет занулить.
Следующее важное поле – SizeOfOptionalHeader. Оно содержит число, указывающее, сколько байт осталось до начала описания секций. В принципе, нас будет устраивать число 0Eh (224 байта).
Далее идет поле “характеристики экзэшника”. Мы и его будем считать константным:
И равно оно 010Eh. На этом поле заканчивается так называемый “файловый заголовок” и начинается “Опциональный”.
Следующее поле – MagicNumber. Это тоже константа. Так называемое магическое число. Если честно, я не очень понял, для чего оно служит, в разных источниках это поле преподносится по-разному, но все хором ссылаются на знаменитый дизассемблер HIEW, в котором якобы впервые появилось описание этого поля именно в таком виде. Примем на веру.
Следующие два поля, хоть и не нулевые, но нам малоинтересны. Это: MajorLinkerVersion и MinorLinkerVersion. Это два байта версии компилятора. Угадайте, что я туда поставил?
Следующее важное поле – AddressOfEntryPoint. Важность этого поля в том, что оно указывает на адрес, с которого начинается первая команда, – с нее процессор начнет выполнение. Дело в том, что на этапе компиляции значение этого поля не сразу известно. Ее формула достаточно проста. Сначала указывается адрес первой секции плюс ее размер. К ней плюсуются размеры остальных секций до секции, считаемой секцией кода. Например, в нашей жертве это выглядит так (см. Рис. 7):
Рис. 7. Расчет точки входа
Здесь секция кода вторая по счету, значит, Адрес точки входа равен размеру секции “Данные” плюс ее начало и равен 2000. К этому еще пририсовывается базовый адрес, в который загрузчик “сажает” файл, но он в вычислении для нашего компилятора не участвует. Поэтому в жертве точка входа имеет значение 2000.
Следующее поле – ImageBase. Это поле я приму как константу, хотя и не оговаривается ее однозначное значение. Это значение указывает адрес, с которого загрузчик поместит файл в память. Оно должно нацело делиться на 64000. В общем, необязательно указывать именно 400000h, можно и другой адрес. Уже не помню, где я слышал, что загрузчик может на свое усмотрение поменять это число, если вдруг в тот участок памяти нельзя будет загружать, но не будем это проверять, а примем на веру как константу =400000h.
Следующая важная константа – SectionAlignment. Это значение говорит о размере секций после загрузки. Принцип прост: каждая секция (имеется в виду ее реализация) дополняется загрузчиком пустыми байтами до числа, указанного в этом поле. Это так называемое выравнивание секций. Тут уж хороший компилятор должен думать самостоятельно, какой размер секций ему взять, чтобы все переменные (или сам код), которые в коде используются, поместились без проблем. Согласно спецификации, это число должно быть степенью двойки в пределах от 200h (512 байт) до 10000h (64 000 байт). В принципе, пока что для простенького компилятора можно принять это значение как константу. Нас вполне устроит среднее значение 1000h (4096 байт – не правда ли, расточительный мусор? На этом весь Windows построен – живет на широкую ногу, память экономить не умеет).
Далее следует поле FileAlignment. Это тоже хитрое поле. Оно содержит значение, сколько байт нужно дописать в конец каждой секции в сам файл, т. е. выравнивание секции, но уже в файле. Это значение тоже должно быть степенью двойки в пределах от 200h (512 байт) до 10000h (64 000 байт). Неплохо бы рассчитывать функцией это поле в зависимости от размеров, данных в секции.
Следующие поля – MajorSubsystemVersion и MinorSubsystemVersion – примем на веру как константы. 3h и Аh соответственно. Это версия операционной системы, под которую рассчитывается данная компиляция****.
Далее из значимых следует SizeOfImage. Это размер всего заголовка, включая размер описания всех секций. Фактически это сумма PE-заголовка плюс его выравнивание, плюс сумма всех секций, учитывая их выравнивание. Ее тоже придется рассчитывать.
Следующее поле – SizeOfHeaders (pазмеp файла минус суммарный pазмеp описания всех секций в файле). В нашем случае это 1536-512 * 2=200h (512 байт). Однако РЕ тоже выравнен! Это поле тоже нужно будет рассчитывать.
Далее следует не менее коварное поле – CheckSum. Это CRC сумма файла. Ужас… Мы еще файл не создали, а нам уже нужно ее посчитать (опять-таки вспоминается Микрософт злым громким словом). Впрочем, и тут можно вывернуться. В Win API предусмотрена функция расчета CRC для области данных в памяти, проще говоря, массива байт – CheckSumMappedFile. Можно ей скормить наш эмбрион файла. Причем веселье в том, что эта операция должна быть самой последней до непосредственной записи в файл. Однако, как показывает практика, Windows глубоко наплевать на это поле, так что мы вполне можем не морочить себе голову этим расчетом (согласитесь, держать в файле поле, которое никому не нужно, да еще и напрягать нас лишним расчетом – это глупо, но, увы, в этом изюминка политики Микрософта. Складывается впечатление, что программисты, писавшие Windows, никак не согласовывали между собой стратегию. Спонтанно писали. Импровизировали).
Следующее поле – Subsystem. Может иметь следующие значения*****:
- IMAGE_SUBSYSTEM_WINDOWS_CUI=3. Это говорит о том, что наш откомпилированный экзэшник является консольной программой.
- IMAGE_SUBSYSTEM_WINDOWS_GUI=4. Это говорит о том, что экзэшник может создавать окна и оперировать сообщениями.
Вот, собственно, и все важные для нас параметры. Остальные можно оставить константно, как показывает “Оля”:
И остаток забить нулями (посмотрите в “Оле” до начала секций, какие там еще параметры). О них можно почитать подробнее по ссылкам, которые я привел.
После идет описание секций. Каждое описание занимает 32 байта. Давайте взглянем на них (Рис. 8):
Рис. 8. Описание секций
В начале секции идет ее имя (8 байт), после этого поле – VirtualSize, описывает (я процитирую из уроков Iczeliona) “RVA-секции. PE-загpузчик использует значение в этом поле, когда мэппиpует секцию в память. То есть, если значение в этом поле pавняется 1000h и файл загpужен в 400000h, секция будет загpужена в 401000h”.
Однако “Оля” почему-то показывает для обеих секций одно и то же значение 9. Что это? Я не понял, почему так. Пока оставим это как данное. Вдруг в будущем разберемся.
Далее следует VirtualAddres, который указывает, с какого адреса плюс ImageBase будет начинаться в памяти секция – это важное поле, именно оно станет для нашего компилятора базой для расчета адреса к переменной. Собственно, адрес этот напрямую зависит от размера секции. Следующий параметр PointerToRawData – это смещение на начало секции в скомпилированном файле. Как я понял, этот параметр компиляторы любят подводить под FileAlignment. И последнее – поле Characteristics. Сюда прописывается доступ к секции. В нашем случае для секции кода оно будет равным 60000020=CODE|EXECUTE|READ, а для секции данных C0000040=INITIALIZED_DATA |READ|WRITE.
Вот и все. Закончилось описание заголовка. Далее он выравнивается нулями до 4095 байт (с этим числом связан один прикол). В файле мы его будем дополнять до FileAlignment (в нашем случае до 200h).
Hello world. Hey! Is There Anybody Out There?
Вот мы и прошлись по кишкам нашей жертвы – экзэшника. Напоследок попробуем на скорую руку закрутить простейший компилятор для DOS-системы без PE-заголовка. Для этого подойдут инструменты, которые так почему-то любят преподавать до сих пор.
Я говорю о классическом Паскале. Итак, предположим, злобный преподаватель поставил задачу: написать компилятор программы вывода на экран некой строки, которую мы опишем для компилятора, введя ее ручками (см. листинг 1):
<Это MZ-заголовок>
header:=# $4D # $5A # $3E # $ 00 # $ 01 # $ 00 # $
00 # $ 00 # $ 02 # $ 00 # $ 00 # $ 01 # $FF # $FF # $ 02 # $ 00 # $ 00 ;
header:=header+# $ 10 # $ 00 # $ 00 #
$ 00 # $ 00 # $ 00 # $ 00 # $1C # $ 00 # $ 00 # $ 00 # $ 00 # $ 00 # $ 00 # $ 00 ;
BlockWrite ( f,commands [ 1 ] , length ( commands ) , e ) ;
Close ( f ) ;
end .
Не удивляет, что программа получилась небольшой? Почему-то преподаватели, дающие такое задание, уверены, что студент завалится. Думаю, такие преподаватели сами не смогли бы написать компилятор. А студенты смогут, ибо, как видим, самая большая сложность – это найти нужные машинные коды для решения задачи. А уж скомпилировать их в код, подкорректировать заголовок и расставить адреса переменных – задача второстепенной сложности. В изучении ассемблерных команд поможет любая книга по Ассемблеру. Например, книга Абеля “Ассемблер для IBM PC”. Еще неплохая книга есть у Питера Нортона, где он приводит список функций DOS и BIOS.
Впрочем, можно и банальнее. Наберите в поисковике фразу “команды ассемблера описание”. Первая же ссылка выведет нас на что-нибудь вроде [5] или [6], где описаны команды Ассемблера. Например, если преподаватель задал задачку написать компилятор сложения двух чисел, то наши действия будут следующими:
-
Выясняем, какая команда складывает числа. Для этого заглянем в книгу того же Абеля, где дается такой пример:
Рис. 9. Опкоды MOV
Видим (см. Рис. 9), что его опкод A1 (тут тоже любят 16-тиричность). Таким образом, выяснив все коды, можно написать компилятор что-то вроде этого (см. листинг 2):
Commands:= Commands+# $A1 # $ 00 # $ 00 ; < mov [Из памяти] в AX>
aPos:= Length ( Commands ) -1 ; <Запомним позицию для корректировки переменной a>
Commands:= Commands+# $ 03 # $ 06 # $ 00 # $ 00 ;
А далее, в конце, скорректируем эти позиции (см. листинг 3):
Запустим компилятор, он скомпилирует экзэшник, который посмотрим в “Иде” (см. Рис. 10):
Рис. 10. Реверсинг нашего кода
Post Scriptum
Ну как, студенты, воспряли духом? Теперь понятен смысл, куда двигаться в случае столкновения с такими задачами? Это вряд ли потянет на курсовую, но вполне подойдет для простенькой контрольной. А вот следующая задача – написать транслятор – уже действительно тянет даже на хороший диплом, так что пока переварим все то, что выше, а в следующий раз попробуем приготовить основное ядро компилятора, дабы потом уже делать упор на сам код программы.
Пишем примитивный и никому не нужный компилятор
Я считаю, что каждый программист должен написать свой компилятор.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.
В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник.
Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.
Да, компилятор совершенно нагло основан на Tiny-С.
Грамматика
Прежде чем начать, давайте определимся, что именно будет уметь наш язык.
Уметь он будет очень мало:
— единственный тип данных — int
— все переменные — глобальные. Всего есть 26 переменных (a-z)
— из математических операций поддерживаются только «+» и «-»
— единственный оператор сравнения — это «<»
— из конструкций языка — условные операторы if, if/else, while, do/while
Все. Никаких массивов, функций, структур. Вот какая грамматика получается у нашего языка:
Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.
Программа — это один оператор (statement).
Операторы бывают условными (if..else. ), циклическими (while. ) и просто операторами (напр., «a=2+3»).
Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор.
Выражения — это либо сумма, либо присваивание переменной значения.
Здесь сумма — это последовательность сложений-вычитаний термов.
Терм — это число, переменная или выражение в скобках.
Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.
Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.
Лексический анализатор
На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.
Итак, наш лексический анализатор должен узнавать следующие токены:
— числа
— идентификаторы-переменные
— ключевые слова: if, else, while, do
— символы +, -, <, =, <, >, (, ),;
— конец файла
Вот как выглядит его исходный код:
В методе next_tok() анализатор получает следующий токен. Тип токена можно получить из атрибута sym, а его значение (если это переменная или число) — из атрибута value.
Анализатор игнорирует пробелы, проверяет, является ли текущий символ специальным символом языка, если нет — проверяет, является ли он числом или идентификатором. Т.е. встретив цифру 1, анализатор продолжит вычитывать символы, пока не встретит не-числовой символ. Аналогично проверяются идентификаторы (там вместо чисел буквы).
Парсер
Это, наверное, самый сложный компонент нашего компилятора. Его задача, используя токены, полученные от лексического анализатора, сформировать своего рода дерево, в котором иерархия и связи отображают структуру кода. Например:
Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR. ), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.
Для описания узлов введем класс Node. Вот код класса парсера и класса Node:
Этот парсер работает рекурсивно, начиная с метода parse().
Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.
Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.
При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.
Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.
Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.
На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.
Машинный код
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины. Виртуальная машина будет стековой, т.к. они значительно проще регистровых. Вот ее возможные инструкции:
Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:
Код виртуальной машины очень простой. Он весь описывается в методе run:
Осталось написать собственно компилятор — генератор кода.
Компилятор
Венец нашего творения. Вот его исходный код:
Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт).
В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.
Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.
Тестируем
Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):
Введение
В большинстве современных компиляторов (вроде gcc и clang) последние два пункта повторяются еще раз. Для начальной генерации кода они используют не совсем низкоуровневый, но платформонезависимый язык. Потом этот промежуточный код переводится в зависящий от архитектуры (x86, ARM и так далее).
После этого объектный код готов к линковке. Большая часть нативных компиляторов автоматически вызывает линковщик, создающий исполняемый код, но это еще не компиляция. В языках вроде Java или C# линковка может быть полностью динамической и выполняться в виртуальной машине в момент загрузки.
Запомните основные моменты
Компилятор должен быть:
- работающим
- красивым
- эффективным
Эта классическая последовательность применима ко всей сфере разработки ПО. Сконцентрируйтесь на первом пункте. Сделайте простейшую вещь и заставьте ее работать.
Читайте книги!
Прочтите книгу «Компиляторы: принципы, технологии и инструменты». Эта бессмертная классика до сегодняшнего дня не потеряла актуальности. «Дизайн современных компиляторов» — также стоящая вещь.
Если на данном этапе это кажется вам слишком сложным, почитайте для начала какие-нибудь введения в парсинг.
Убедитесь, что вам комфортно работать с графами, особенно с деревьями. Это основа построения программ на логическом уровне.
Хорошо определите свой язык
Вы можете использовать любую нотацию, но будьте уверены, что имеете полное и последовательное описание языка. Оно включает в себя как синтаксис, так и семантику.
Используйте свой любимый язык
Это совершенно нормально — писать компилятор на Pyhton, Ruby или любом другом языке, который вам нравится. Используйте простые алгоритмы, принцип которых вы хорошо понимаете. Первый ваш компилятор вовсе не обязан быть быстрым, или эффективным, или обладать кучей фич. Все, что от него требуется — работать достаточно правильно и легко поддаваться переработкам.
Также нормально писать разные стадии развития компилятора на разных языках, если это требуется.
Приготовьтесь к написанию множества тестов
Весь ваш язык должен быть стопроцентно покрыт тестами, эффективнее всего, если он будет определен ими. Будьте на ты с выбранным тестовым фреймворком. Пишите тесты с первого дня. Рационально отдавать предпочтение «позитивным» тестам, которые предполагают корректную работу кода.
Регулярно прогоняйте все тесты. Чините некорректные тесты. Будет очень обидно остаться у разбитого корыта с плохо определенным языком, который не способен принять валидный код.
Сделайте хороший парсер
Парсеров существует огромное количество, выбирайте любой. Можно написать свой собственный, но это сработает только в том случае, если синтаксис вашего языка примитивен до маразма.
Парсер должен выявлять синтаксически ошибки и сообщать о них. Пишите много тестов, как позитивных, так и негативных. Переиспользуйте написанный код для определения языка.
На выходе ваш парсер должен генерировать абстрактное синтаксическое дерево. Если ваш язык использует модули, то результатом работы парсера может быть простейшее представление генерируемого «объектного кода».
Напишите семантический валидатор
Вполне вероятно, что ваш язык допускает синтаксически правильные конструкции, не имеющие смысла в некоторых контекстах. Примером может служить повторное объявление одной и той же переменной или пропуск параметра неправильного типа. Валидатор призван выявлять ошибки такого рода.
Также зона его ответственности охватывает разрешение зависимостей с другими модулями, написанными на вашем языке, загрузкой этих модулей и использовании их в процессе валидации. Например, именно на этом этапе проверяется соответствие количества параметров, поступающих на вход функции из подключаемого модуля.
Еще раз, пишите и запускайте много тестов. Тривиальные случаи также обязательны к рассмотрению, как и сложные.
Генерируйте код
Воспользуйтесь простейшими техниками, которые вы знаете. Чаще всего допустимо непосредственно переводить языковую конструкцию (например, условны й оператор) в слабо параметризированный шаблон кода.
Забудьте об эффективности и сосредоточьтесь только на правильности.
Настройте платформо-независимую низкоуровневую виртуальную машину
Вероятнее всего, вас не очень интересуют низкоуровневые аспекты, если только вы не страстный поклонник всего, что связано с архитектурой.
Варианты для вас:
- LLVM: позволяет эффективно генерировать машинный код, чаще всего для х86 и ARM.
- CLR: ориентирована на .NET.
- JVM: нацелена на мир Java, мультиплатформенна.
Забудьте об оптимизации
Оптимизация — это сложно. И почти всегда она бывает преждевременной. Генерируйте неэффективный, но рабочий код. Реализуйте весь язык прежде чем приступите к оптимизации.
Конечно, некоторая простая оптимизация вполне уместна на начальном этапе. Но старайтесь избегать излишних хитростей, пока ваш компилятор не будет достаточно стабилен.