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

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

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

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

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

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

164 голоса | спросил Googlebot 20 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 20 Sep 2012 19:53:01 +0400 2012, 19:53:01

5 ответов


259

Введение

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

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

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

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

Вспомните основы

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

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

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

Прочитайте книги!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сгенерировать код

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

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

Задайте независимую от платформы низкоуровневую VM

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

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

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

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

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

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

Итак, что?

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

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

ответил 9000 20 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 20 Sep 2012 21:52:35 +0400 2012, 21:52:35
24

Jack Crenshaw Давайте построим компилятор , в то время как незавершенный, представляет собой чрезвычайно читаемое введение и учебник.

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

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

ответил John R. Strohm 20 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 20 Sep 2012 22:25:28 +0400 2012, 22:25:28
15

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

ответил World Engineer 20 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 20 Sep 2012 21:38:18 +0400 2012, 21:38:18
9

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

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

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

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

Гораздо сложнее, чем сказано. Я предлагаю вам прочитать компиляторы и интерпретаторы в C ++ в качестве отправной точки (By Ronald Mak). Кроме того, «позволяет создавать компилятор» Crenshaw в порядке.

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

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

Удачи!

ответил Aniket Inge 20 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 20 Sep 2012 20:28:44 +0400 2012, 20:28:44
9

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

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

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

ответил MaR 20 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 20 Sep 2012 21:52:29 +0400 2012, 21:52:29

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132