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

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

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

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

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

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

вступление

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

• Разбор: исходный текст преобразуется в абстрактное синтаксическое дерево (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» из программы, созданной вашим компилятором, может стоить усилий.

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

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

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

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

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

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

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

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

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

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

• Другая отправная точка: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Великая книга Кеннета Лоудена: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

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

Удачи!

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

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

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