Реализация компилятора LLVM Micro C в Haskell

Реализациякомпилятораllvmmicrocвhaskell

В этой серии мы рассмотрим, как написать компилятор для небольшого подмножества C в LLVM в Haskell. Наш язык Micro C – это, по сути, небольшое подмножество реального C. У нас будут базовые числовые типы, реальный тип bool , указатели и структуры. В конце серии у нас будет красивый исполняемый файл, mcc (Micro C Compiler), который принимает один .mc исходный файл и создает исполняемый файл.

Почему другой Учебник по LLVM?

Перевод калейдоскопа Стивеном Дилем учебник представляет собой отличное введение в создание простого языка с использованием Haskell и LLVM. Однако он использует более старую версию LLVM, чем доступна в настоящее время. В частности, он был написан до того, как модуль IRBuilder был добавлен в привязки Haskell и потребовал, чтобы пользователи сами писали много сантехнических операций, которые теперь обрабатываются библиотекой. Кроме того, хотя kaleidescope является прекрасным языком обучения для построения компиляторов, наша версия C, хотя и урезанная, по-прежнему более обширна и позволит нам немного глубже погрузиться в особенности LLVM. Более того, в основном все уже знают C, и возможность сравнить вывод нашего компилятора с выводом clang – отличный ресурс для отладки.

Кто для чего это учебное пособие?

В этом учебном пособии предполагается некоторое знакомство с Haskell. Чтобы выучить язык, обратитесь к ресурсам, упомянутым в в этом превосходном ответе на Stackoverflow. Для справки, Haskell, используемый в этом проекте, находится где-то в том, что этот ответ счел бы ранней промежуточной категорией, поскольку существует много преобразователей Monad, но нет причудливых GADT, TypeFamilies, схем рекурсии или любого другого миллиарда расширений, которые GHC должен предложить. Хотя все эти расширенные языковые функции могут оказаться весьма полезными при написании компилятора, я оставил их в mcc, чтобы попытаться быть более дружелюбным к новичкам.

Подготовка к настройке

Среда разработки

Полный исходный код компилятора на Haskell находится по адресу https://github.com/jmorag/mcc.git. Настройка цепочки инструментов LLVM довольно сложна, поэтому вместо предоставления вам инструкций по сборке я рекомендую просто использовать nix . В корне репозитория находится файл shell.nix , который вы можете использовать для добавления в оболочку необходимых библиотек Haskell, cabal и лязг . Если запущен nix-shell --pure --run 'cabal new-clean; cabal new-test ' работает нормально, тогда все должно быть настроено правильно. Если нет, откройте вопрос.

Инструменты Haskell постоянно меняются. Когда я начал писать Micro C, я использовал vim и эль , но переключился на emacs и intero на полпути, оба со стеком. По состоянию на апрель 1012573, я Мы заменили интеро на данте и снова переключились на обычную клику, как лучше играет с nix. Я хотел изучить ghcide , но данте работает для меня достаточно хорошо, и я не нашел ни времени, ни мотивации для перехода. В случае, если эти инструменты не работают или их установка занимает слишком много времени, ghcid – отличный запасной вариант.

Зависимости и языковые расширения проекта

Следующие это отличное сообщение в блоге Алексиса Кинга, мы укажем информацию о нашем проекте в package.yaml . Первые несколько строк просто указывают название проекта и автора

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

   Параметры ghc : -Wall -fno-warn-name-shadowing -Wcompat -Wincomplete-uni-patterns  

Следующий , мы указываем наши зависимости.

   зависимости : - base> =  4.7   &&  < 5  - mtl - массив - контейнеры - текст - преобразования строк - каталог - pro  cess - unix - filepath - bytestring - prettyprinter - pretty-simple - llvm-hs-pure> =  9   &&  < 10  - llvm-hs-pretty> =  0,9   &&  < 1  - мегапарсек - синтаксические анализаторы-комбинаторы  библиотека :  исходные каталоги : src  исполняемый файл :  main : Main .hs  исходные каталоги : приложение  зависимости : - optparse-application - mcc  тесты :  testall : основной: Testall.hs  источник- каталоги : тесты  зависимости : - вкусно - вкусно-золотисто - вкусно-хунит - mcc  

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

OverloadedStrings - необходимое зло для борьбы с Haskell's печально известная проблема со строками и LambdaCase - крошечное синтаксическое расширение, которое позволяет нам создавать меньше имен переменных, тем самым решая сложная задача в области компьютерных наук.

Обзор проекта

Задача компилятора состоит в том, чтобы взять один или несколько исходных файлов, проанализировать их в абстрактное синтаксическое дерево (AST), проверить их на семантические ошибки, и если в них нет ни одной , понизьте их до среднего уровня sendation (IR), оптимизировать упомянутый IR и создать исполняемый файл для целевого ЦП.

Разные языки обрабатывают эти шаги по-разному. Синтаксис Лиспа настолько похож на AST, что синтаксический анализ практически невозможен, тогда как C имеет инфиксные операторы и блочные операторы, которые делают преобразование из последовательности байтов в AST нетривиальным. Многие динамические языки почти не проводят семантический анализ перед запуском, тогда как на другой стороне спектра языки с зависимой типизацией выполняют такой сложный анализ, что могут доказать, что их программы завершатся. Наш диалект C находится где-то посередине; мы будем отклонять программы во время компиляции, которые присваивают float переменной типа int , но мы не будем прилагать никаких усилий, чтобы делать любой вывод типа или проверку завершения. Мы также не будем беспокоиться о генерации целевого кода, оставив это LLVM. Базовая архитектура будет выглядеть примерно так:

http://blog.josephmorag.com/images/compiler-pipeline.png

Теперь, когда мы изложили предварительные сведения, мы можем начать кодирование в часть 1 !