Как написать простейший компилятор

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

Стандартный компилятор осуществляет следующие шаги:

  • Парсинг: исходный текст конвертируется в абстрактное синтаксическое дерево (Abstract Syntax Tree, AST).
  • Разрешение зависимостей с другими модулями (С откладывает этот этап на шаг линковки).
  • Семантическая валидация: исключение синтаксически корректных, но бессмысленных выражений, например, повторного объявления переменных.
  • Эквивалентные преобразования и высокоуровневая оптимизация: AST преобразуется для осуществления более эффективных вычислений при той же семантике.
  • Генерация кода: AST трансформируется в линейный код низкого уровня с переходами, распределением регистров и тому подобным.
  • Локальная оптимизация: низкоуровневый код проверяется на простые локальные недостатки.

В большинстве современных компиляторов (вроде gcc и clang) последние два пункта повторяются еще раз.

Для начальной генерации кода они используют не совсем низкоуровневый, но платформонезависимый язык. Потом этот промежуточный код переводится в зависящий от архитектуры (x86, ARM и так далее).

После этого объектный код готов к линковке. Большая часть нативных компиляторов автоматически вызывает линковщик, создающий исполняемый код, но это еще не компиляция. В языках вроде Java или C# линковка может быть полностью динамической и выполняться в виртуальной машине в момент загрузки.

Компилятор должен быть:

  • работающим
  • красивым
  • эффективным

Эта классическая последовательность применима ко всей сфере разработки ПО. Сконцентрируйтесь на первом пункте. Сделайте простейшую вещь и заставьте ее работать.

Прочтите книгу «Компиляторы: принципы, технологии и инструменты». Эта бессмертная классика до сегодняшнего дня не потеряла актуальности. «Дизайн современных компиляторов» — также стоящая вещь.

Если на данном этапе это кажется вам слишком сложным, почитайте для начала какие-нибудь введения в парсинг.

Убедитесь, что вам комфортно работать с графами, особенно с деревьями. Это основа построения программ на логическом уровне.

Хорошо определите свой язык

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

Используйте свой любимый язык

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

Также нормально писать разные стадии развития компилятора на разных языках, если это требуется.

Приготовьтесь к написанию множества тестов

Весь ваш язык должен быть стопроцентно покрыт тестами, эффективнее всего, если он будет определен ими. Будьте на ты с выбранным тестовым фреймворком. Пишите тесты с первого дня. Рационально отдавать предпочтение «позитивным» тестам, которые предполагают корректную работу кода.

Регулярно прогоняйте все тесты. Чините некорректные тесты. Будет очень обидно остаться у разбитого корыта с плохо определенным языком, который не способен принять валидный код.

Сделайте хороший парсер

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

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

На выходе ваш парсер должен генерировать абстрактное синтаксическое дерево. Если ваш язык использует модули, то результатом работы парсера может быть простейшее представление генерируемого «объектного кода».

Напишите семантический валидатор

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

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

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

Генерируйте код

Воспользуйтесь простейшими техниками, которые вы знаете. Чаще всего допустимо непосредственно переводить языковую конструкцию (например, условный оператор) в слабо параметризированный шаблон кода.

Забудьте об эффективности и сосредоточьтесь только на правильности.

Настройте платформо-независимую низкоуровневую виртуальную машину

Вероятнее всего, вас не очень интересуют низкоуровневые аспекты, если только вы не страстный поклонник всего, что связано с архитектурой.

Варианты для вас:

  • LLVM: позволяет эффективно генерировать машинный код, чаще всего для х86 и ARM.
  • CLR: ориентирована на .NET.
  • JVM: нацелена на мир Java, мультиплатформенна.

Забудьте об оптимизации

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

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

6 книг по компиляторам

Книги по программированию: как читать и что именно

c++ — Как создать простой компилятор для простого языка (например, brainfuck)?

Вопрос задан

Изменён 1 год 4 месяца назад

Просмотрен 11k раз

В общем хочу написать компилятор brainfuck или своего собственного языка (простого). Как это сделать?
P.S.
Интерпретатор (для brainfuck) я осилил сам, как сделать компилятор я даже не догадываюсь.
Желательно найти литературу.

  • c++
  • компилятор
  • brainfuck

для brainfuck я когда то сам писал компилятор. Лучше для начала написать траслятор, который переведет код в с/с++/java/любой другой любимый язык. Это очень просто. Вот пример траслятора в Java. После того, как получится написать такое, никто не мешает написать похожее для ассеблера (для fasm или masm). Последней ступенькой будет генерирование сразу исполнимого файла. О том, что нужно знать ассемблер, я думаю вопросов нет.

И ещё немного интересного материала — http://habrahabr.ru/blogs/development/113339/

Есть такая книжка, Marc-André Cournoyer, «How To Create Your Own Freaking Awesome Programming Language» (по ссылке — продается, но ищущий название и слово «pdf» всегда найдет и где взять менее цивлизованно, ЕВПОЧЯ). Показывают основы на пальцах, этакая «Драконья Книга для самых маленьких».

Начинают с лексера и парсера, затем интерпретатор, и затем — компилятор под LLVM и, на всякий случай, собственную игрушечную виртуальную машину. Все, правда, на Ruby, но общие идеи от языка не зависят. Так что если есть интерес — можете поискать и посмотреть, рекомендую.

Было уже.

Давайте создадим компилятор

3

Зарегистрируйтесь или войдите

Регистрация через Google

Регистрация через Facebook

Регистрация через почту

Отправить без регистрации

Почта

Необходима, но никому не показывается

Отправить без регистрации

Почта

Необходима, но никому не показывается

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Запустить простой (возможно, самый простой) компилятор C?

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

Вместо того, чтобы писать полный или совместимый со стандартами компилятор языка C (по крайней мере, в начале), я бы предложил ограничиться базовым подмножеством языка, таким как общие операторы, поддержка только целых чисел и основные функции и указатели. Одним из классических примеров этого был Small-C Рона Кейна, ставший популярным благодаря серии статей, написанных в Dr. Dobbs Journal в 19 веке.80-е годы. Они издают компакт-диск с вышедшей из печати книгой Джеймса Хендрикса «Компилятор Small-C».

Я бы предложил следовать учебнику Crenshaw, но написать его для компилятора C-подобного языка и любого целевого процессора (Crenshaw нацелен на процессор Motorola 68000), который вы хотите настроить. Чтобы сделать это, вам нужно знать базовую сборку того, на какой цели вы хотите запускать скомпилированные программы. Это может включать эмулятор для 68000 или MIPS, которые, возможно, на лучше, чем набор инструкций сборки, чем почтенный набор инструкций CISC Intel x86 (16/32-бит).

Существует множество потенциальных книг, которые можно использовать в качестве отправной точки для изучения теории (и практики) компилятора/транслятора. Прочтите часто задаваемые вопросы о comp.compilers и обзоры различных интернет-магазинов книг. Большинство вводных книг написаны как учебники для второкурсников и старших курсов бакалавриата по компьютерным наукам, поэтому их чтение может быть медленным без опыта работы с компьютерными науками. Одна старая книга, которая может быть более вводной, но ее легче читать, чем «Книга дракона» , это Введение в построение компилятора Томаса Парсонса. Она старше, поэтому вы сможете найти подержанную копию в интернет-магазинах книг по разумной цене.

Итак, я бы сказал, попробуйте начать с учебника Джека Креншоу «Давайте создадим компилятор», напишите свой собственный, следуя его примерам в качестве руководства, и создайте основы простого компилятора . Как только вы это заработаете, вы сможете лучше решить, что вы хотите сделать с этой точки зрения.

Добавлено:

Что касается процесса начальной загрузки. Поскольку существующие компиляторы C существуют в свободном доступе, вам не нужно беспокоиться о начальной загрузке. Напишите свой компилятор с помощью отдельных существующих инструментов (GCC, Visual C++ Express, Mingw/djgpp, tcc), и вы можете беспокоиться о самостоятельной компиляции вашего проекта на гораздо более позднем этапе. Я был удивлен этой частью вопроса, пока не понял, что вы пришли к идее написания собственного компилятора, прочитав речь Кена Томаса о награде ACM Turing, Reflections on Trusting Trust, которая действительно входит в процесс начальной загрузки компилятора. Это модерируемая продвинутая тема, а также просто много хлопот. Я нахожу даже загрузку компилятора GCC C в более старых системах Unix (Digital OSF/1 на 64-битной версии Alpha), которые включали компилятор C, медленным и трудоемким процессом, подверженным ошибкам.

Еще один вопрос касался того, что на самом деле делает такой компилятор, как Yacc. Yacc (Yet Another Compiler Compiler или Bison от GNU) — это инструмент, разработанный для облегчения написания синтаксического анализатора компилятора (или транслятора). На основе формальной грамматики для вашего целевого языка, которую вы вводите в yacc, он генерирует анализатор , который является частью общей конструкции компилятора. Далее идет Lex (или flex от GNU), который используется для генерации лексического анализатора или сканера, который часто используется в сочетании с парсером, сгенерированным yacc, для формирования скелета внешнего интерфейса компилятора. Эти инструменты значительно упрощают написание внешнего интерфейса по сравнению с написанием лексического анализатора и синтаксического анализатора самостоятельно. В учебнике Crenshaw эти инструменты не используются, да и вам они не нужны, многие разработчики компиляторов не всегда их используют. Конечно, Креншоу признает, что синтаксический анализатор учебника довольно прост.

Учебник Crenshaw также пропускает создание AST (абстрактного синтаксического дерева), что упрощает, но также ограничивает компилятор учебника. В нем отсутствует большая часть, если не вся оптимизация, и он очень привязан к конкретному языку программирования и конкретному языку ассемблера, испускаемому «внутренней частью» компилятора. Обычно AST — это промежуточная часть, в которой может быть выполнена некоторая оптимизация, и служит для разделения внешнего и внутреннего интерфейса компилятора в дизайне. Для новичка без опыта в области компьютерных наук я бы посоветовал не беспокоиться о том, что у вас нет AST для вашего первого компилятора (или, по крайней мере, его первой версии). Я думаю, что если он будет небольшим и простым, это поможет вам закончить написание компилятора в его первой версии, и вы сможете решить, как вы хотите действовать дальше.

Как компилятор C может быть написан на C?

Задавать вопрос

спросил

Изменено 7 лет, 9 месяцев назад

Просмотрено 61к раз

Этот вопрос может возникнуть из-за непонимания компиляторов с моей стороны, но вот…

В предисловии к первому изданию K&R (стр. xi) можно найти следующее утверждение:

Операционная система, компилятор C и практически все прикладные программы UNIX (включая все программное обеспечение, использованное для подготовки этой книги) написаны на C.

(курсив мой)

Вот чего я не понимаю: разве этот компилятор C не должен быть скомпилирован сам, прежде чем он сможет скомпилировать какой-либо код C? И если этот компилятор C написан на C, разве для его компиляции не потребуется уже существующий компилятор C?!

Единственный выход из этой загадки бесконечной регрессии (или проблемы курицы и яйца) заключается в том, что компилятор C, написанный на C, на который ссылается K&R, был на самом деле скомпилирован с помощью уже существующего компилятора C, написанного на другом языке.

чем C. Компилятор C, написанный на C, затем заменил последний.

Или я совсем туплю?

  • c
  • конструкция компилятора
  • Керниган-и-Ритчи
2

Это называется Bootstrapping, цитата из Википедии:

Если кому-то нужен компилятор для языка X, чтобы получить компилятор для языка X (который написан на языке X), как был написан первый компилятор? Возможные методы решения этой проблемы с курицей или яйцом включают:

  1. Реализация интерпретатора или компилятора для языка X в языке Ю. Никлаус Вирт сообщил, что он написал первый компилятор Паскаля в Фортран.
  2. Другой интерпретатор или компилятор для X уже написан в другой язык Y; именно так Scheme часто загружается.
  3. Более ранние версии компилятора были написаны в подмножестве X для что существовал какой-то другой компилятор; вот как некоторые суперсеты Java, Haskell и первый компилятор Free Pascal загружен.
  4. Компилятор для X перекрестно скомпилирован из другой архитектуры, где существует компилятор для X; вот как компиляторы для C обычно портируется на другие платформы. Также этот метод используется для Free Pascal после начальной загрузки.
  5. Написание компилятора на X; затем вручную скомпилировать его из исходного кода (большинство вероятно, неоптимизированным способом) и запустив его в коде, чтобы получить оптимизированный компилятор. Дональд Кнут использовал это для своей веб-грамотности. система программирования.

И если вам интересно, вот первый исходный код компилятора C Денниса Ричи.

Обычно первый компилятор пишется на другом языке (в данном случае непосредственно на ассемблере PDP11 или на C для большинства «современных» языков). Затем этот первый компилятор используется для программирования компилятора, написанного на самом языке.

Вы можете прочитать эту страницу об истории языка C. Вы увидите, что он также тесно связан с системой UNIX.

3

См. раздел «Курица и яйцо» на странице Википедии:

Если кому-то нужен компилятор для языка X, чтобы получить компилятор для языка X (который написан на языке X), как был написан первый компилятор? Возможные методы решения проблемы курицы или яйца включают:

  • Внедрение интерпретатора или компилятора для языка X в язык Y. Никлаус Вирт сообщил, что он написал первый компилятор Паскаля на Фортране.
  • Другой интерпретатор или компилятор для X уже написан на другом языке Y; именно так Scheme часто загружается.
  • Более ранние версии компилятора были написаны в подмножестве X, для которого существовал какой-то другой компилятор; именно так загружаются некоторые надмножества Java, Haskell и исходный компилятор Free Pascal.
  • Компилятор для X перекрестно скомпилирован из другой архитектуры, где существует компилятор для X; именно так компиляторы для C обычно переносятся на другие платформы. Также этот метод используется для Free Pascal после начальной загрузки.

    No related posts.