Любопытный программист
0,0
рейтинг
8 января в 15:13

Разработка → Как я написал компилятор C за 40 дней перевод

Предлагаю вам перевод дневника Руи Уэяма (Rui Ueyama), программиста из Google, который он вел во время работы над реализацией компилятора языка C около трех с половиной лет назад (но опубликовал только в минувшем декабре).
Этот дневник не несет какой-то практической пользы и не является туториалом, но мне было очень интересно его прочитать, надеюсь и вам эта история тоже понравится :)


Я написал C компилятор за 40 дней, который назвал 8cc. Это дневник написанный мной в то время. Код и его историю можно посмотреть на GitHub.

День 8


Я пишу компилятор. Он начал работать после написания примерно 1000 строк кода. Вот несколько примеров, которые уже работают:

int a = 1;
a + 2;  // => 3

int a = 61;
int *b = &a;
*b;     // => 61

Массивы корректно преобразовываются в указатели, так что код ниже тоже работает. Также поддерживается вызов функций.

char *c = "ab" + 1;
printf("%c", *c); // => b

Реализовать это было не сложно, т.к. я делаю это уже второй раз. Я научился лучше управляться с массивами и указателями.

День 15


Я далеко продвинулся в реализации компилятора и он работает на удивление хорошо. Нетривиальные программы, например эта — решающая задачу о восьми ферзях, компилируются и запускаются.

Конечно ему не хватает многих функций. Эти примеры программ подобраны так, чтобы не использовать их.
Реализация довольно проста; нет даже распределения регистров (register allocation).
Он компилирует исходные программы в код стековой машины, которая использует системный стек в качестве стека. Каждая операция требует обращения к памяти. Но пока меня это устраивает.

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

Теперь он содержит около 2000 строк. Если посмотреть git, то кажется он развивался таким образом:
  • добавлены "+" и "-"
  • разделены фазы синтаксического анализа и генерации кода
  • добавлены "*" и "/"
  • добавлены переменные (неявно подразумевающие тип int)
  • добавлен вызов функций
  • добавлены строки
  • разделены генератор меток (tokenizer) и анализ синтаксиса
  • поддержка объявления базовых типов
  • добавлены указатели и массивы
  • поддержка выражений инициализации массивов
  • добавлен «if»
  • поддерживается объявление функций
  • добавлены «for» и «return»
  • поддерживается присвоение указателей
  • добавлено "=="
  • добавлены индексация массивов и арифметика указателей
  • добавлены "++", "--" и "!"

День 17


Я успешно реализовал структуры. Структура — это такой объект, который может занимать больше одного машинного слова. Их сложнее реализовать, чем примитивные типы, но это было легче чем я ожидал.

Кажется, это работает как надо; я могу определить структуру, содержащую структуру. Я могу определить указатель на структуру и разыменовать его. Структуры, содержащие массивы и массивы структур также работают. Хотя я уже знал, что код теоретически должен работать, я все равно обрадовался, когда он действительно заработал, даже в таком сложном случае.

Однако, я не чувствую, что я полностью понимаю, почему этот код работает правильно. Он ощущается немного магическим из-за его рекурсивной природы.

Я не могу передавать структуры в функции. В соглашении о вызовах для x86 структура копируется на стек и указатель на нее передается функции. Но в x86-64 вы должны разделить структуру на несколько частей данных и передать их через регистры. Это сложно, так что это я пока отложу. Передача структур по значению нужна реже, чем передача указателей на них.

День 18


Реализовать объединения было легче, т.к. это просто вариант структуры, в котором все поля имеют одинаковое смещение. Также реализован оператор "->". Проще простого.

Организовать поддержку чисел с плавающей точкой было тяжело. Похоже неявное преобразование типов между int и float работает, но числа с плавающей точкой не могут быть переданы в функции. В моем компиляторе все параметры функций сначала помещаются на стек, а затем записываются в регистры в порядке определенном в соглашении о вызовах x86-64. Но в этом процессе видимо есть баг. Он возвращает ошибку доступа к памяти (SIGSEGV). Его сложно отлаживать, рассматривая ассемблерный вывод, потому что мой компилятор не оптимизирует ассемблер для чтения. Я думал, что смогу закончить с этим за день, но я ошибался.

День 19


Я потратил время впустую, потому что забыл что в соответствии с соглашением о вызовах x86-64 кадр стека должен быть выровнен на 16 байт. Я обнаружил, что printf() падает с SEGV, если передать ей несколько чисел с плавающей точкой. Я попытался найти условия при которых это можно воспроизвести. Оказалось что имеет значение положение стекового кадра, что заставило меня вспомнить про требования ABI x86-64.

Я совсем не позаботился об этом, так что кадр стека был выровнен только по 8 байт, но print() не жаловалась пока принимала только целые числа. Эта проблема может быть легко исправлена корректировкой стекового кадра до вызова инструкции CALL. Но таких проблем не избежать если, тщательно не читать спецификацию перед написанием кода.

День 20


Я поменял отступы в коде компилятора с 2 на 4. Я больше привык к использованию 2-ух пробельных отступов, потому что такие используются на моей работе в Google. Но по некоторым причинам мне кажется отступы в 4 пробела больше подходят для «красивой программы с открытым исходным кодом».

Есть еще одно, более значимое, изменение. Я переписал тесты из shell скриптов на C. До этого изменения каждая тестовая функция компилируемая моим компилятором, связываллась с main() которая компилировалась GCC и затем запускалась shell скриптом. Это было медленно, т.к. порождало много процессов для каждого теста. У меня не было выбора когда я начинал проект, т.к. у моего компилятора не было многих функций. Например, он не мог сравнить результат с ожидаемым значением из-за отсутствия операторов сравнения. Теперь он достаточно мощный, чтобы компилировать код тестов. Так что я переписал их, чтобы сделать их быстрее.

Еще я реализовал большие типы, такие как long и double. Написание кода было веселым потому что я очень быстро преуспел в реализации этих функций.

День 21


Я почти закончил реализацию препроцессора C за один день. На самом деле это порт из моей предыдущей попытки написать компилятор.

Реализация препроцессора C не простая задача.

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

Насколько я знаю, PDF в этом блоге единственный и лучший ресурс о том как реализовать препроцессор языка C. Алгоритм описанный в документе (алгоритм Дейва Проссера) пытается развернуть столько токенов сколько возможно, избегая бесконечного разворачивания макроса. Каждый токен имеет свою историю разворачивания, так что токены не разворачиваются одним и тем же макросом более одного раза.

Препроцессор C сам по себе является независимым языком. У него много особенностей, и только матерые программисты C хорошо его понимают.

День 22


Пытался заставить компилятор читать системные заголовки, так что теперь он понимает #include. Пока я пытался, я получал много ошибок. Это выявило, что моему препроцессру до сих пор не хватает многих функций, например операторы которые можно использовать только в #if. Существует и много багов кроме этого. Я исправлял их, как только находил.

Системные заголовочные файлы большие и запутанные. Они требуют много функций от компилятора, таких как enum и typedef. Я реализовал их одну за другой, но иногда я срезал углы. Я пытаюсь прочитать stdio.h. Понятия не имею как много времени это может занять.

Компилятор сейчас состоит из 4000 строк. Небольшой компилятор LCC содержит 12000 строк. Используя его как гайд, я думаю, мой компилятор скоро сможет работать как настоящий компилятор C.

Я удивлен, что написал 500 строк кода сегодня. Я могу работать в потоке на протяжении 12 часов, но это может быть неэффективно, т.к. я устаю не замечая этого. В любом случае я должен признать, что я человек с большим количеством свободного времени.

День 24


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

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

Внешние штуки, такие как система заголовков, стали причиной многих проблем. Теперь я должен реализовать все функции которые ожидаются от «настоящего» компилятора C. Я сделал много грязных хаков, чтобы прочитать stdio.h. Например, я реализовал хак для игнорирования всех вхождений токена «const». Это расстраивает меня.

Вы можете спросить, почему бы не сделать это правильным способом с самого начала. Я бы сказал, что это не весело. Слишком. Например синтаксис объявления типов в C слишком запутанный без какой либо вменяемой причины и реализовывать его совсем не интересно.

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

День 25


Я застрял на два дня с реализацией синтаксиса определений и объявлений без какого-либо успеха. Почему я не могу закончить это? Я сделал указатели и структуры за один день работы. Я чувствую что недооценил это. Может быть мне нужен план?

День 26


В сложной ситуации как эта, я, вероятно, должен вспомнить тот факт что компилятор был всего в одном файле, чтобы увидеть как я продвинулся за месяц. Он просто считывал целое через scanf() и печатал его через printf(). Действительно, я очень серьезно продвинулся за один месяц. Да, я думаю могу сделать это.

День 28


Закончил писать парсер для объявлений и определений. Думаю причина по которой я терпел неудачи была в том, что я пытался написать слишком много деталей с самого начала, так что я написал псевдокод чтобы убедиться что правильно все понимаю и затем конвертировал его в реальный код.

Я пишу на C уже почти 15 лет, но только сегодня я почувствовал, что, наконец, понимаю синтаксис типов в С. Не удивительно, что я не мог писать работающий код. Это потому, что я просто не понимал его правильно.

Код, который я только что написал слишком сложен и хрупок, что даже я с трудом его понимаю. Я не верю, что Деннис Ритчи, создатель языка C, понимал последствия того, что он делал. Я подозреваю, что он придумав синтаксис, написал код, который оказался сложнее, чем он ожидал, и, в итоге, был стандартизирован комитетом ANSI. Трудно реализовать стандартизированный язык, потому что вы должны сделать все правильно. Скорее легче написать свой собственный игрушечный язык.

День 29


Реализовал еще много операторов и почистил код.

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

День 30


Я реализовал switch-case, continue, break и goto сегодня. Когда я писал тест кейсы для goto, код тестов быстро превратился спагетти код, который я не мог прочитать. Это меня рассмешило. Я убедился, почему goto считается вредным.

День 31


Реализовал функции для varargs, а именно va_start, va_arg и va_end. Они используются не часто, но я нуждался в них для компиляции функций, например printf.

Спецификация vararg для C не очень хорошо продумана. Если вы передаете все аргументы функции через стек, va_start может быть реализован довольно легко, но на современных процессорах и в современных соглашениях о вызовах аргументы передаются через регистры, чтобы уменьшить накладные расходы на вызов функций. Поэтому спецификация не соответствует реальности.

Грубо говоря, ABI для x86-64, стандартизированное AMD, требует чтобы функции с переменным числом аргументов копировали все регистры в стек, чтобы подготовиться к последующему вызову va_start. Я понимаю, что у них не было другого выбора, но это все равно выглядит неуклюже.

Мне стало интересно как другие компиляторы обрабатывают функции с переменным числом аргументов. Я посмотрел на заголовки TCC и, похоже, они не совместимы с ABI x86-64. Если структура данных для varargs отличается, то функции передающие va_list (такие как vprintf) становятся несовместимыми. Или я ошибаюсь? [И я действительно ошибаюсь — они совместимы.] Я также посмотрел на Clang, но он выглядит запутанным. Я не стал читать его. Если я буду читать слишком много кода других компиляторов, это может испортить веселье от собственной реализации.

День 32


После исправления незначительных проблем и добавления управляющих последовательностей для строковых литералов (до сих пор не было '\0' и подобных вещей), получилось скомпилировать еще один файл. Я чувствую уверенный прогресс.

Я пытался реализовать поддержку функций, имеющих более шести параметров, но не смог закончить это за один день. В x86-64 первые 6 целочисленных параметров передаются через регистры, а оставшиеся через стек. Сейчас поддерживается передача только через регистры. Передачу через стек не сложно реализовать, но она требует слишком много времени для отладки. Я думаю в моем компиляторе нет функций, имеющих более шести параметров, так что я пока отложу их реализацию.

День 33


Еще три файла скомпилированы сегодня. Итого 6 из 11. Но если считать строки кода, то это около 10% от общего числа. Оставшиеся файлы намного больше, так как содержат код ядра компилятора.

Еще хуже то, что в файлах ядра я использую относительно новые особенности C, такие как составные литералы и назначенные инициализаторы. Они сильно усложняют самокомпиляцию. Я не должен был использовать их, но переписывать код на простом старом C будет не продуктивно, поэтому я хочу поддерживать их в своем компиляторе. Хотя на это потребуется время.

День 34


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

Во-первых, лексический анализатор запоминает свою позицию чтения и когда он прерывается по непредвиденным причинам, он возвращает эту позицию. Это позволяет легко найти баг, когда компилятор не принимает корректные входные данные.

Есть опция командной строки для печати внутреннего абстрактного синтаксического дерева. Если есть ошибка в синтаксическом анализаторе, я хочу посмотреть на синтаксическое дерево.

Генератор кода позволяет широко использовать рекурсию, потому что он генерирует фрагменты ассемблерного кода, когда обходит абстрактное синтаксическое дерево. Так я смог реализовать печать мини трассировки стека для каждой строки ассемблерного вывода. Я если я замечаю что-то неправильное, я могу проследить за генератором кода, посмотрев на его вывод.

Большинство внутренних структур данных имеют функции для преобразования в строку. Это полезно при использовании printf для отладки.

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

День 36


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

Думаю, единственная особенность, которой не хватает для самокомпиляции, это присваивание структур. Надеюсь все будет работать как задумано без особой отладки, когда она будет реализована.

День 37


Файл, содержащий токенайзер скомпилирован, но получившийся компилятор второго поколения по некоторым причинам не генерирует корректный ассемблерный код. Хотя код, генерируемый компилятором первого поколения проходит все тесты. Такой вот коварный баг.

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

Мне это напоминает фильм «Начало». Мы должны идти глубже, чтобы воспроизвести этот баг. Это забавная часть отладки самокомпилирующегося компилятора.

День 38


Я исправил проблему, возникавшую во втором поколении, если лексический анализатор был самоскомпилирован. Она вызывала баг при котором -1 > 0 иногда возвращало true (я забыл про знаковое расширение). Есть еще один баг в размещении структур (struct layout). Осталось только три файла.

День 39


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

Я исправил много проблем, вызванных плохим качеством кода, который я писал на ранней стадии этого проекта. Это утомило меня.

Я верил, что имел все возможности для самокомпиляции, но это не правда. Нет даже префиксных операторов инкремента/декремента. Для некоторых особенностей C99 я переписал часть компилятора, чтобы сделать его более удобным для компиляции. Так как я не ожидал добраться до возможности самокомпиляции так быстро, я использовал столько новых особенностей C, сколько хотел.

День 40


Ура! Мой компилятор теперь может полностью себя скомпилировать!

Это заняло около 40 дней. Это очень короткий промежуток времени, для написания самокомпилируемого компилятора C. Вы так не думаете? Я считаю, что мой подход — вначале сделать небольшой компилятор для очень ограниченного подмножества C, и затем преобразовать его в настоящий компилятор C очень хорошо сработал. В любом случае сегодня я очень счастлив.

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

Осталось много багов и нереализованных особенностей. Я, наверное, закончу с ними, а потом начну работу по улучшению выходного кода.

Исходный код находится здесь. Я не знаю, стоит ли это читать, но может быть интересно посмотреть его как образец кода на языке C, который может обработать простой компилятор в 5000 строк.

День 41


Вернулся к систематической разработке, так как была достигнута большая веха. Я изменил код, пытаясь читать его, как если бы я был третьим лицом, и, в итоге, удовлетворился качеством кода. Это напоминает подрезку дерева бонсай.

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

День 42


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

Например, мой компилятор интерпретирует "\n" (последовательность обратного слеша и символа «n») в строковый литерал "\n" (в данном случае символ новой строки). Если вы подумаете об этом, вы можете счесть это немного странным, потому что он не располагает информацией о реальном ASCII коде для "\n". Информация о коде символа не присутствует в исходном коде, но передается из компилятора, компилирующего компилятор. Символы новой строки моего компилятора могут быть прослежены до GCC.
Компиляторы могут передать гораздо больше информации, чем код символа.

Эта удивительная история была представлена Кеном Томпсоном в его лекции при получении премии Тьюринга. Информация, которую Кен добавил в раннюю версию Unix компилятора давала возможность программе для входа пользователей принимать некоторые особенные пароли, так что Кен мог войти в любую учетную запись Unix. Он также сделал так чтобы компилятор распознавал собственную компиляцию и передавал хак программы для входа дочернему компилятору, так что этот бэкдор (которого не было в исходном коде) передавался из поколения в поколение. Вы не могли удалить его, даже если бы тщательно осмотрели каждую строчку исходного кода компилятора и перекомпилировали его, поскольку компилятор, который обрабатывает исходный код был заражен. Это удивительная история, не правда ли?

День 43


Переписал реализацию парсера для операторов на метод рекурсивного спуска вместо использования первенства операторов (operator-precedence parser). Я думаю, что причина для того, чтобы выбрать парсер использующий приоритет операторов это простота и скорость, но грамматика используемая в для операторов в C слишком запутанная для обработки таким способом (например, индексы массивов или различные виды унарных операторов). Код теперь легче читать, чем раньше, потому что большие функции разбиваются на множество мелких. Также теперь должно быть легче добавить проверку ошибок в парсер.

Техники написания парсеров — это один из моих самых полезных навыков как программиста. Он помогал мне бесчисленное количество раз.

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

День 44


Входные данные сейчас преобразуются таким образом: строка символов → последовательность токенов → последовательность токенов после подстановки макросов → абстрактное синтаксическое дерево → x86-64 ассемблер. Последний переход, возможно делает слишком много и слишком запутан. Он выполняет различные виды операций, такие как неявные преобразования типов и разворачивание имен меток, пока производит ассемблерный код. Теоретически, я, вероятно, должен определить промежуточный язык между АСД и ассемблером.

Я снова читал Dragon Book по этой теме, не чувствуя, что я полностью ее понял. Книга слишком абстрактна, так что я не могу немедленно применить ее моем случае.

Мой компилятор в два раза медленнее чем GCC когда компилирует сам себя. Это не так плохо, как я думал. Мой компилятор генерирует жутко бесхитростный ассемблер, но такой код не медленнее на порядок.

День 45


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

День 46


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

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

Я стал лучше понимать оптимизацию компилятора, после того как прочитал еще несколько страниц из Dragon Book. Я мог бы начать писать код, если разберусь в этом еще чуть-чуть лучше.

День 52


Я искал таинственный баг в течение трех дней: если вы округлите вверх или вниз указатель стека для выравнивания к 16-байтовой границе, компилятор второго поколения выводит сообщение об ошибке для корректных входных данных. Такого рода ошибки отлаживать труднее, чем обычные фатальные ошибки.

Моим первым предположением было: неправильное выравнивание указателя стека. Но это не так, потому что указатель стека был уже правильно выровнен по 16-байтовой границе. Я не мог найти баги в ассемблерном выводе. Я решил разделить пополам.

Я пытался компилировать каждый файл через мой компилятор, а остальное через GCC чтобы определить функцию, с которой я могу воспроизвести проблему. Но казалось, что функция не содержит ошибок. Это не функция, которая выводит сообщение об ошибке — они даже не в одном файле. Теория заключается в том, что одна функция создает неверные данные которые вызывают ошибки в других функциях.

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

В итоге, после трехдневной отладки была исправлена всего одна строка. Хотелось бы иметь какие-то средства чтобы упростить подобную отладку.

День 53


Исправлена еще одна загадочная ошибка. Если компилировать некоторые файлы с помощью GCC, а остальные — моим компилятором, то полученный компилятор сообщает о синтаксических ошибках при корректных входных данных. Такие проблемы должны быть связаны с совместимостью ABI. Моим первым предположением было, что проблема может быть связана с разметкой структур или тем как аргументы передаются в функции, но ассемблерный выход для них кажется правильными.

Я снова сузил поиск до конкретного файла, разделяемого пополам. Я переносил функции по очереди из одного файла в другой, чтобы найти функцию, которая была причиной проблемы. Эта функция была не маленькой, поэтому я разделял ее и переносил код в другой файл. Наконец я получил несколько строк кода. Я скомпилировал их, с помощью GCC и моего компилятора и сравнил.

Единственная разница заключалась в этом: мой компилятор проверяет все биты в регистре, чтобы определить содержит ли он булево значение true, тогда как GCC проверяет только младшие 8 бит. Таким образом, например, если значение в регистре 512 (= 29 или 0x100), то мой компилятор воспринимает его как true, тогда как GCC считает по-другому. GCC на самом деле возвращает некоторое очень большое число с нулями в наименее значимых 8 битах, что воспринимается как false.

Из-за этой несовместимости, цикл, который использует для проверки условия выхода функцию, скомпилированную с помощью GCC (при этом сам цикл компилируется моим компилятором) прекращается сразу же на первой итерации. В результате, макросы препроцессора не определяются. И какие-то из токенов оставались неопределенными и поэтому парсер сообщал о синтаксических ошибках при некоторых входных данных. Причина была далеко от того места, где сообщалось об ошибке, но я, наконец, отловил ее.

Спецификация x86-64 ABI имеет небольшую заметку о том, что только младшие 8 бит являются значимыми для логических возвращаемых значений. Я читал это, но в первый раз не понял что это значит, так что я даже не помнил, что такое указание существовало. Но теперь для меня это предельно ясно. У меня смешанные чувства — я узнал новые вещи, но я мог бы их узнать, не тратя на это столько времени.

День 55


Реализованы битовые поля.

Вы можете упаковать несколько переменных в небольшой области с использованием битовых полей, но компилятор все равно должен создавать пространство между ними в зависимости от их типов. Мое быстрое исследование вывода GCC выявило такие правила (конечно, без гарантии, что они правильны):

  • Выравнивание первого битового поля подчиняется выравниванию типа. Например, для «int x:5», x выравнивается по 4-байтовой границе (предполагается, что int — это 32 бита).
  • Любая переменная не должна пересекать свои естественные границы. Например, для «int x:10», x не должен пересекать 4-байтовую границу. Если оставшееся число битов слишком мало, чтобы удовлетворить этому условию, они остаются неиспользованными и следующее битовое поле начинается в следующих границах.

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

День 56


Реализованы вычисляемые goto (computed goto). Обычный goto может ссылаться только на одну метку, но вычисляемый goto может принимать указатель и передавать управление на этот адрес. Этого нет в стандарте C и существует как расширение для GCC. Если вы когда-либо писали виртуальную машину с очень большим switch-case, вы, скорее всего, знаете об этой возможности. Эта функция часто используется, чтобы заменить большой переключатель switch-case на таблицу преобразований и вычисляемый goto.

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

День 57


Реализовал C11 _Generic, потому что я хотел использовать его в своем компиляторе. Но после реализации, я заметил, что GCC 4.6.1 не поддерживает _Generic. Я не могу использовать эту функцию так как если я использую ее, то GCC не сможет компилировать мой компилятор.

Я также реализовал функцию typeof(), которая также является расширением GCC. Обе эти функции не используются в данный момент, но это нормально, так как для их реализации потребовалось очень мало кода.

День 58


Добавил диграфы из C99. Диграф — это необычная функция для специфичных окружений, в которых невозможно использовать некоторые символы. Например, "<:" определяется как псевдоним для "[". Диграфы могут быть преобразованы в обычные символы при токенизации, так что это бесполезно, но и безвредно.

В С89 есть триграфы, которые очевидно вредны. Триграфы — трехбуквенные последовательности символов, которые преобразуются в один символов везде, где они появляются в исходном коде. Например, printf(«huh??!») выведет не «huh??!», а «huh|» потому что "??!" это триграф для "|". Это сильно сбивает с толку. У меня нет планов, поддерживать триграфы.

День 62


Я пытаюсь скомпилировать TCC. Но пока я далек от успеха из-за нереализованных функций и ошибок.

TCC — это маленький компилятор C, размер которого составляет от 20К до 30к строк кода. Если вы удалите поддержку архитектур кроме x86-64, количество строк, вероятно, будет около 10К-20К. Удивительно видеть, что такой маленький компилятор поддерживает такое множество функций. Фабрис Беллар, создатель ТСС, — гений.

Я несколько раз попытался прочитать исходный код TCC, но все еще не понимаю всю картину. Компиляторы это сложные программы, поэтому вы обычно хотите разбить их на небольшие управляемые части, но исходный код ТСС ощущается, как монолитный компилятор. Я не могу писать такой великолепный код. Я не знаю, хочу ли я подражать, но то что в мире есть кто-то, кто может писать такой код, действительно производит на меня впечатление.

День 73


Безуспешно продолжал работать над компиляцией TCC. Конечно это тяжело, потому что если она пройдет, это значит мой компилятор имеет те же функции что и TCC. Компиляция других компиляторов полезна для отладки, но по своей природе она придираеся к каждой детали спецификации языка.
Перевод: Rui Ueyama
Сергей Кондрашев @DuDDiTs
карма
38,0
рейтинг 0,0
Любопытный программист
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (55)

  • +18
    Меня побьют если я напомню про картинку с совой?
    • 0
      Напомните, я точно не побью :)
      ну и не в курсе такой каринки
      • +21
        image
        • +3
          Я предупреждал, что это не туториал :)
          • +2
            Да я читал ваше предупреждение. Просто статью можно сократить и привести к виду:
            писал > писал > писал >… > написал
            Никаких подробностей и откровений не замечено)
            • +4
              Вы ничем подобным не занимались, поэтому от текста ничего в вас не «ёкнуло».
              • –1
                Откуда в вас уверенность в том, чем я занимался когда-либо в жизни?
                • 0
                  Прошу прощения, если сделал неверный вывод.
      • 0
        deleted
        • +2
          Если уж пошла шара с вопросами, за которые обычно бьют… Можете объяснить что означают эти «delete» и «del» в комментариях к постам?
          • +3
            Насколько я понимаю, автор комментария передумал оставлять оригинальный комментарий и успел заменить текст на del/deleted
            • 0
              Я понял. Спасибо. Не замечал, что на хабре нет возможности удалять комментарии к постам.
  • +4
    День 15. Я далеко продвинулся в реализации компилятора и он работает на удивление хорошо. Нетривиальные программы, например эта — решающая задачу о восьми ферзях, компилируются и запускаются.


    За пятнадцать дней. Воистину суровые люди работают в google. Впрочем, судя по записям, автор использовал готовые решения.
    Буду утешать себя тем, что автор, скорее всего, использовал уже готовый компилятор…
    • +1
      И при этом он все рано пишет, что «Фабрис Беллар, создатель ТСС, — гений», а он, значит, так — балуется просто)

      что касается готового компилятора, то как минимум парсер он писал сам. В комментарии к этому дневнику он пишет что сейчас не стал бы заморачиваться и использовал бы yacc
      • 0
        Почитал немного код на гите. Он делает разбор с закосом под функциональные языки… Между прочим, я вот подумал — не так уж это и страшно, если в соответствие каждому из элементов языка ставится функция, выполняющая разбор этого элемента и через все эти вызовы пробрасывается структура для генерации AST.
        • +3
          Прочитал ваш комментарий и задумался: а как иначе-то можно? Я только с «закосом под функциональные языки» парсеры и пишу.

          Я думаю, что автор просто пишет компилятор не первый раз в жизни, и видимо неплохо знаком с ассемблером. Написать компилятор для примитивного языка похожего на C не так уж сложно – всего-то нужно реализовать токенизатор+парсер и транслятор без каких-либо оптимизаций. Если вы уже знакомы с принципами реализации парсеров и неплохо знаете ассемблер, то это будет скорее монотонная работа. Таинством это воспринимается только до первого раза. :)
          • +1
            Прочитал ваш комментарий и задумался: а как иначе-то можно?


            Я написал генератор парсеров на основе недетерменированного конечного автомата (на самом деле даже нечто ещё более навороченное — уже третий месяц никак не добью статью на хабру по этой тему). На эту тему много публикаций на хабре есть.

            На самом деле, функциональный подход к разбору, как я понимаю, сводится к записи структуры всё того же автомата, просто в виде вызовов функций.
          • +1
            это будет скорее монотонная работа

            Да, монотонность работы часто наблюдается пока идет описание грамматики и начальное её покрытие реализацией парсера\компилятора\интерпретатора\генератора\….
            Типа, как в этом дневнике — скукотища: вот первая 1000 строк, вот вторая… ага, вот свет в конце тоннеля уже виден… и, наконец, 100% покрытие спецификации языка.

            Но, когда такая рутинная работа завершена и наступает фаза полномасштабных испытаний, неожиданно начинают выявляться «чудеса-чудесные».
            И вроде грамматику описал в точном соответствии со спецификацией языка и кусочки реализации четко подгонял, чтобы они правильно отрабатывали в любом порядке для любого исходного текста на входе…
            но, нет… и в описании грамматики и в реализации начинают проявляться самые неожиданные блохи…
            и вот тут начинается настоящее творчество…
            А, реализация хорошей обработки некорректного исходного текста это вообще всегда очень нетривиальная задача.

            Разработчику попроще, если разрабатывается реализация для какго-нибудь «известного и стабильного» языка, а если ещё и язык новый, то точно о монотонности и не вспомните даже на начальном этапе. Особенно на фоне «живой» спецификации языка.
    • +1
      Не преувеличивайте. Где суровость-то? Времени у него много, вот что. :-)
  • +5
    читается как роман
    • 0
      я тоже почему-то вспомнил книгу «Марсианин».
  • –1
    Я не уловил мотивов движущих этой разработкой. Известно, что настоящий программист должен написать себе редактор, даже мой редактор правлен под меня на уровне ядра кода. А что, настоящий_настоящий программист должен раз в жизни написать себе компилятор?
    • +4
      Простите, а можно где-то посмотреть список вещей, которые должен сделать настоящий программист?)
      • +1
        Разумеется можно))
        • Посадить дерево
        • ...etc
        • 0
          • написать свой фреймворк (или хотя бы CMS)
          • начать и завалить минимум один стартап :)
      • +1
        Не удержусь… здесь
        И эта ссылка есть в статье
    • 0
      Во-первых это интересно, какие ещё мотивы вам нужны?
      • 0
        Интересно — это веский мотив, но он не приведен ни в дневнике, ни в Readme на github. Отсюда освистанный вопрос.
        • 0
          Есть в HACKING.md:
          I accept small patches, but because this is my hobby project to learn about compilers, it's unlikely to accept large patches.
    • +1
      А что, настоящий_настоящий программист должен раз в жизни написать себе компилятор?

      Это обычное задание ВУЗовского курса «теория языков программирования и трансляции». Реализация компилятора/транслятора для некоего простого языка программирования.
      • 0
        Какие-то у вас другие ВУЗы.
        • +2
          В ВУЗах РФ на специальности 230105 изучается предмет «Теория ЯП и методов трансляции», у нас одной из работ было создание транслятора для ЯП. Не общеупотребимого, синтетического, но вполне полноценного.
  • +2
    Тут явно что-то не так:
    Он компилирует программы на стеке, используя стек машины как стек

    в оригинале:
    It compiles source programs onto a stack machine that uses the machine stack as the stack

    Тут используется понятие «стековая машина» (stack machine), про которые пишут немного тут, например. Виртуальная машина Java, например, стековая машина. Поэтому фразу лучше перевести как "Он компилирует исходные программы в код стековой машины, которая использует системный стек в качестве стека" (или вроде того).
    • +1
      Спасибо, поправил. Признаться, подзавис над этой фразой во время перевода.
  • +5
    По законам жанра Andrey2008 должен написать про это статью ;)
  • –3
    Фабрис Беллар — голова, это да. За формат BPG по крайней мере. За 40 дней соорудить компилирующий сам себя код — достижение разве что для студента.
    • 0
      А вы, видимо, можете похвастаться и не такими успехами в области компиляторов и программирования? Если для вас компилятор для С за 40+ дней это «достижение для студента», то можно ли увидеть ваши достижения?
      • +1
        Лет 20 назад мог бы аналогичный «дневник» опубликовать, «как я написал yacc за 40 дней». К сожалению не мог тогда предвидеть, что вдруг потребуется предъявлять доказательства крутизны, поэтому сырцы для вас не сохранил. :)
        Подобные парсеры это реально студенческий уровень, вот вам весь Си на 2х страницах: http://www.quut.com/c/ANSI-C-grammar-y.html
        • 0
          вот вам весь Си на 2х страницах

          Так там только грамматика — без собственно компилятора.
          • 0
            О том и речь — грамматика мала. Например, в БНФ нотации ANSI C занимает 300 строк, Паскаль — 192, Delphi 7(Object Pascal) — 1006.
            • +1
              Язык — это не только грамматика. Надо ещё реализовать семантику, добавить оптимизации, добавить генерацию кода. В общем, работы много и эта работа требует довольно обширных знаний: надо знать ABI, знать алгоритмы оптимизации. Да хотя бы ту же спецификацию C надо знать, а она побольше двух страниц. Может, эта работа и не сильно сложная, если знать, как её сделать, но довольно объёмная. И то, что автор уложился в 40 дней характеризует его как человека, который может быстро писать много кода и потом не утонуть в нём.
              • +2
                Надо ещё реализовать семантику, добавить оптимизации, добавить генерацию кода

                Вы почитайте, как это сделано в данном компиляторе — на самом простом уровне.

                И то, что автор уложился в 40 дней характеризует его как человека, который может быстро писать много кода и потом не утонуть в нём.

                Автор уложился в 40 дней реализуя подмножество без оптимизации.
                • 0
                  Да, я знаю, что оптимизации там нет, это я в общем написал. Но автор всё равно молодец, что реализовал хотя бы подмножество. В конце концов, это же проект для развлечения. :)
              • –1
                Надо ещё реализовать семантику, добавить оптимизации, добавить генерацию кода.
                Вы статью-то вообще читали? Там нет никаких оптимизация, а семантика и кодогенерация слиты в одну сущность. Нечто вроде Turbo Pascal'я, хотя, скорее всего, ещё примитивнее.

                надо знать ABI,
                Какой ABI? Вы о чём?

                знать алгоритмы оптимизации.
                Нет там оптимизации. От слова «совсем». Даже структур, которые обычно используются оптимизаторами нет. Совсем.

                Да хотя бы ту же спецификацию C надо знать, а она побольше двух страниц.
                Для чего её нужно знать? Чтобы потом не реализоывать? На 40й день компилятор компилировал только сам себя! На 73й он отказался от идеи довести компилятор «до ума» и научить его компилировать хотя бы TCC!

                Прочитайте же наконец статью!
                • +2
                  А вы прочитайте мой комментарий. Я пишу о том, что язык — это не только грамматика и далее по тексту. То есть о том, что по объёму грамматики судить о сложности языка некорректно. А также о том, что нужно всё же иметь какие-то знания, чтобы писать трансляторы.

                  Там нет никаких оптимизация, а семантика и кодогенерация слиты в одну сущность. Нечто вроде Turbo Pascal'я, хотя, скорее всего, ещё примитивнее.


                  Да, я знаю, что там нет оптимизаций, так как об этом написано на страничке его проекта на GitHub. Я упомянул оптимизации как пример элемента, не относящегося к грамматике, для иллюстрации сложностей, скрывающихся за её пределами.

                  Какой ABI? Вы о чём?


                  Я о двоичном интерфейсе приложений. Конечно, если реализовывать сферический язык в вакууме, то он не нужен. В частности, автор упоминает AMD64 ABI в дневнике и ссылается на него на страничке на GitHub.

                  Нет там оптимизации. От слова «совсем». Даже структур, которые обычно используются оптимизаторами нет. Совсем.


                  Верно, нет. Я и не пишу, что она там есть. Я лишь пишу, что для реализации языка программирования она пригодилась бы. Согласны?

                  Для чего её нужно знать? Чтобы потом не реализоывать?


                  Чтобы реализовать какой-то язык, нужно знать спецификацию. Не так ли? Ещё раз напомню, что в первых предложениях говорится о трансляции вообще, так как комментарий, на который я отвечал, расширил контекст обсуждения.

                  На 40й день компилятор компилировал только сам себя! На 73й он отказался от идеи довести компилятор «до ума» и научить его компилировать хотя бы TCC!


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

                  Может, конечно, я и непонятно выразился в чём-то, но к чему такой эмоциональный ответ?
      • +3
        Это действительно не так сложно. Я сам писал транслятор (на прямых методах) и виртуальную полу-стековую машину для языка программирования, который используется у нас внутри компании. Не 40 дней, что-то около 45-50. С возможжностью подстройки под разные платформы, встраивание, разрешение связей при загрузке.
        • +3
          Но согласитесь, что это объёмная работа. Я тоже писал компилятор (вернее транслятор в язык ассемблера для x86). Когда знаешь алгоритмы и под рукой есть книжка с драконом, это в самом деле не rocket science, но я помню, убил на него много времени. Точно не помню, но тоже месяца полтора, если не ошибаюсь. При этом язык был проще C.
          • +2
            Работа большая, но если учитывать, что уровень реализации — простой (без оптимизаций, все в одном модуле, без промежуточных представлений и т.д.), то ореол серьезности, который окружает написание транслятора, несколько ярче, чем сама работа. Особенно для тех, кто никогда подобного не делал. Если есть хорошая спецификация языка, и ты его знаешь, то алгоритмы разрабатываются быстро. Если задаться целью строить не академический табличный транслятор, то и того проще.

            Когда знаешь алгоритмы и под рукой есть книжка с драконом, это в самом деле не rocket science, но я помню, убил на него много времени

            И без такой книжки можно обойтись. В свое время мне хватило «Трансляции ЯП» Вайнгартена лохматого 77 года.
            • 0
              ореол серьезности, который окружает написание транслятора, несколько ярче, чем сама работа

              Это да. «Ты придумал свой язык?! Круто!»

              Если задаться целью строить не академический табличный транслятор, то и того проще.

              Ну да, скормил тому же ANTLR описание своего DSL, и всего делов. Полчаса на что-то не сильно сложное, если грамматика готовая есть. Но тогда и статьи не получилось бы. :)

              Не знаю, как вам, а мне этот дневник было интересно читать, так как я когда-то сам через что-то похожее проходил.
              • 0
                Не знаю, как вам, а мне этот дневник было интересно читать, так как я когда-то сам через что-то похожее проходил.

                Мне тоже. Когда-то мой транслятор вырос из expression evaluator'а, который был необходим, чтобы на лету делать кое-какие вычисления. Потом возникла мысль дописать и остальное поверх той же ВМ, которая реализовала выполненный парсинг выражений, потому что после разборки выражений последовательное выполнение операторов реализовывалось легко, не считая мелочей вида непредопределенных на данный момент меток/функций, которые появятся только там, внизу.
    • 0
      Только если это суровый челябинский студент.
      • 0
        Или финский. Не забывайте чем себя небезызвестный Линус развлекал.

        А компиляторы… какой-нибудь Форт примитивный пишется за неделю (как и здесь: некоторое самокомпилирующееся подмножество, не полный ANS FORTH, конечно), а данный компилятор не сильно далеко от него ушёл: та же самая стековая машина, прямая компиляция без промежуточных представлений… когда-то подобные вещи люди вообще на бумажке писали и сразу в машинный код переводили… конечно это было до появления таких сложных языков как C…
        • +1
          Еще стоит учесть, что не полноценный (с полным покрытием синтаксиса) компилятор за 40 дней был написан, а такой, который мог сам себя транслировать. Т.е. если мы используем некоторый ограниченный набор инструкций при кодировании компилятора (не считая ряда заголовочных файлов), то задача упрощается.
  • –1
    захватывающее повествование, даже интересней чем про катю криптовалютчика.
  • 0
    Судя по фразе «В любом случае я должен признать, что я человек с большим количеством свободного времени», это рассказ из серии «как я провёл отпуск».

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