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

214

Продвинутые компиляторы, например, gccкомпилируют коды в машиночитаемые файлы в соответствии с языком, на котором был написан код (например, C, C ++ и т. Д.). Фактически они интерпретируют значение каждого кода в соответствии с библиотекой и функциями соответствующих языков. Поправьте меня если я ошибаюсь.

Я хочу лучше понять компиляторы, написав очень простой компилятор (вероятно, на C) для компиляции статического файла (например, Hello World в текстовом файле). Я пробовал некоторые учебники и книги, но все они для практических случаев. Они имеют дело с составлением динамических кодов со значениями, связанными с соответствующим языком.

Как я могу написать базовый компилятор для преобразования статического текста в машиночитаемый файл?

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

Представление практических руководств и ресурсов высоко ценится :-)

Googlebot
источник
Вы пробовали lex / flex и yacc / bison?
mouviciel
15
@mouviciel: Это не хороший способ узнать о сборке компилятора. Эти инструменты делают значительную часть тяжелой работы за вас, поэтому вы никогда не делаете это на самом деле и не узнаете, как это делается.
Мейсон Уилер
11
@ Интересно, что первая из ваших ссылок дает 404, а вторая теперь помечена как дубликат этого вопроса.
Руслан

Ответы:

326

вступление

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

  • Разбор: исходный текст преобразуется в абстрактное синтаксическое дерево (AST).
  • Разрешение ссылок на другие модули (C откладывает этот шаг до ссылки).
  • Семантическая проверка: отсеивание синтаксически правильных утверждений, которые не имеют смысла, например, недоступный код или дублированные объявления.
  • Эквивалентные преобразования и оптимизация высокого уровня: AST преобразуется, чтобы представить более эффективные вычисления с той же семантикой. Это включает, например, раннее вычисление общих подвыражений и константных выражений, устранение чрезмерных локальных назначений (см. Также SSA ) и т. Д.
  • Генерация кода: AST преобразуется в линейный низкоуровневый код с переходами, распределением регистров и т.п. Некоторые вызовы функций могут быть встроены на этом этапе, некоторые циклы развернуты и т. Д.
  • Оптимизация глазка: низкоуровневый код сканируется для выявления простых локальных неэффективностей, которые устраняются.

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

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

Помните основы

  • Сделай так, чтобы это работало
  • Сделай это красиво
  • Сделайте это эффективным

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

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

Читай книги!

Прочитайте Книгу Дракона Ахо и Уллмана. Это классика и до сих пор вполне применима сегодня.

Современный дизайн компилятора также хвалят.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выход вашего парсера - абстрактное синтаксическое дерево.

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

Создать семантический валидатор

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

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

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

Генерировать код

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

Опять же, игнорируйте эффективность и сосредоточьтесь на правильности.

Таргетинг на независимую от платформы низкоуровневую виртуальную машину

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

Ваши варианты:

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

Игнорировать оптимизацию

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

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

И что?

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

Просмотр «Hello world» из программы, созданной вашим компилятором, может стоить усилий.

9000
источник
45
Это один из лучших ответов, которые я когда-либо видел.
gahooa
11
Я думаю, что вы пропустили часть вопроса ... ОП хотел написать очень простой компилятор. Я думаю, что вы выходите за рамки очень простой здесь.
marco-fiset
22
@ marco-fiset , напротив, я думаю, что это выдающийся ответ, который говорит оператору, как сделать очень простой компилятор, указывая при этом ловушки, чтобы избежать и определить более продвинутые фазы.
smci
6
Это один из лучших ответов, которые я когда-либо видел во всей вселенной Stack Exchange. Престижность!
Андре Терра
3
Просмотр «Hello world» из программы, созданной вашим компилятором, может стоить усилий. -
INDEED
27

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

Nicklaus Wirth's Compiler Construction - очень хороший учебник по основам простой конструкции компилятора. Он фокусируется на рекурсивном спуске сверху вниз, что, скажем прямо, намного проще, чем lex / yacc или flex / bison. Оригинальный компилятор PASCAL, который написал его группа, был сделан таким образом.

Другие люди упоминали различные книги о драконах.

Джон Р. Штром
источник
1
Одна из приятных особенностей Pascal заключается в том, что все должно быть определено или объявлено перед использованием. Поэтому он может быть скомпилирован за один проход. Turbo Pascal 3.0 является одним из таких примеров, и есть много документации о внутренностях здесь .
tcrosley
1
PASCAL был специально разработан с учетом однопроходной компиляции и ссылок. В книге компиляторов Вирта упоминаются многопроходные компиляторы и добавляется, что он знал о компиляторе PL / I, который прошел 70 (да, семьдесят) проходов.
Джон Р. Штром
Обязательное объявление перед использованием восходит к Алголу. Тони Хоар прислушался комитетом АЛГОЛ к своим ушам, когда попытался предложить добавить правила типа по умолчанию, аналогичные тем, которые были у ФОРТРАНА. Они уже знали о проблемах, которые это может создать, с опечатками в именах и правилами по умолчанию, создающих интересные ошибки.
Джон Р. Штром
1
Вот более обновленная и законченная версия книги самого автора: stack.nl/~marcov/compiler.pdf Пожалуйста, отредактируйте свой ответ и добавьте это :)
sonnet
16

На самом деле я бы начал с написания компилятора для Brainfuck . Это довольно тупой язык для программирования, но в нем всего 8 инструкций. Это настолько просто, насколько это возможно, и есть эквивалентные инструкции C для задействованных команд, если вы обнаружите, что синтаксис не соответствует действительности.

Мировой инженер
источник
7
Но затем, когда у вас есть готовый компилятор BF, вы должны написать в нем свой код :(
500 - Внутренняя ошибка сервера
@ 500-InternalServerError использует метод подмножества C
World Engineer
12

Если вы действительно хотите писать только машиночитаемый код и не ориентироваться на виртуальную машину, вам придется прочитать руководства Intel и понять,

  • а. Связывание и загрузка исполняемого кода

  • б. Форматы COFF и PE (для окон), альтернативно понимают формат ELF (для Linux)

  • с. Понимать форматы файлов .COM (проще, чем PE)
  • д. Понять ассемблеры
  • е. Понимать компиляторы и механизм генерации кода в компиляторах.

Гораздо сложнее сделать, чем сказать. Я предлагаю вам прочитать компиляторы и интерпретаторы в C ++ в качестве отправной точки (Автор Рональд Мак). В качестве альтернативы, «давайте создадим компилятор» Креншоу, это нормально.

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

Советы: Изучите Flex и Bison FIRST. Затем продолжайте создавать свой собственный компилятор / ВМ.

Удачи!

Аникет Инге
источник
7
Я думаю, что нацеливание на LLVM, а не на реальный машинный код - это лучший способ, доступный сегодня.
9000
Я согласен, я уже некоторое время слежу за LLVM, и должен сказать, что это была одна из лучших вещей, которую я видел за последние годы с точки зрения усилий программистов, необходимых для его нацеливания!
Аникет Инге
2
Как насчет MIPS и использовать spim для его запуска? Или MIX ?
@MichaelT Я не использовал MIPS, но я уверен, что это будет хорошо.
Аникет Инге
@PrototypeStark RISC набор команд, процессор реального мира, который все еще используется сегодня (понимание того, что он будет переведен во встроенные системы). Полный набор инструкций находится в Википедии . Глядя на сеть, есть много примеров, и это используется во многих академических классах как цель для программирования машинного языка. В SO есть немного активности .
10

Подход DIY для простого компилятора может выглядеть следующим образом (по крайней мере, так выглядел мой проект uni):

  1. Определите грамматику языка. Контекст бесплатно.
  2. Если ваша грамматика еще не LL (1), сделайте это сейчас. Обратите внимание, что некоторые правила, которые выглядят хорошо в простой грамматике CF, могут оказаться ужасными. Возможно, ваш язык слишком сложен ...
  3. Напишите Lexer, который разрезает поток текста на токены (слова, числа, литералы).
  4. Напишите синтаксический анализатор рекурсивного спуска сверху вниз для вашей грамматики, который принимает или отклоняет ввод.
  5. Добавьте генерацию синтаксического дерева в ваш парсер.
  6. Написать генератор машинного кода из синтаксического дерева.
  7. Profit & Beer, в качестве альтернативы вы можете начать думать, как сделать более умный парсер или сгенерировать лучший код.

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

MaR
источник
Седьмой пункт - это то, о чем спрашивает ОП.
Флориан Маргэйн
7
1-5 не имеют значения и не заслуживают такого пристального внимания. 6 самая интересная часть. К сожалению, большинство книг следуют тому же шаблону после печально известной книги о драконах, уделяя слишком много внимания анализу и оставлению кодовых преобразований вне области видимости.
SK-logic