Программирование компилятора: Каковы основные составляющие?

Question

Я заинтересован в написании очень минималистичного компилятора.

Я хочу написать небольшую часть программного обеспечения (на C / C ++), которая отвечает следующим критериям:

• вывод в формате ELF (* nix)
• ввод - один текстовый файл
• C-подобная грамматика и синтаксис
• без компоновщика
• без препроцессора
• очень маленький (макс. 1-2 KLOC)

Особенности языка:

• собственные типы данных: char, int и float
• массивы (для всех собственных типов данных)
• переменные
• управляющие структуры (if-else)
• функции
• петли (было бы неплохо)
• простая алгебра (div, add, sub, mul, логические выражения, bit-shift и т. Д.)
• встроенный asm (для системных вызовов)

Кто-нибудь может сказать мне, как начать? Я не знаю, из каких частей состоит компилятор (по крайней мере, в том смысле, в котором я мог бы начать прямо с полки) и как их программировать. Спасибо за ваши идеи.

Answer 1

Из всего, что вы надеетесь выполнить, наиболее сложным требованием может быть «очень мало (макс. 1-2 KLOC)». Я думаю, что ваше первое требование (генерация вывода в формате ELF) само по себе может занять более тысячи строк кода.

Один из способов упростить проблему, по крайней мере, для начала, - это сгенерировать код в тексте на языке ассемблера, который затем будет передан в существующий ассемблер ( nasm будет хорошим выбором). Ассемблер позаботится о генерации фактического машинного кода, а также всего специального кода ELF, необходимого для создания фактического исполняемого исполняемого файла. Тогда ваша работа сводится к анализу языка и генерации ассемблерного кода. Когда ваш проект достигнет точки, в которой вы хотите удалить зависимость от ассемблера, вы можете переписать эту часть самостоятельно и подключить ее в любое время.

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

print "hello"
a = 5
print a

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

Удачи!

Answer 2

Во-первых, вам нужно решить, собираетесь ли вы создавать компилятор или интерпретатор. Компилятор переводит ваш код во что-то, что может быть запущено либо непосредственно на оборудовании, в интерпретаторе, либо скомпилировано на другом языке, который затем каким-то образом интерпретируется. Оба типа языков завершены, поэтому они имеют одинаковые выразительные возможности. Я бы посоветовал вам создать компилятор, который компилирует ваш код в байт-код .net или Java, поскольку он дает вам очень оптимизированный интерпретатор для работы, а также множество стандартных библиотек.

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

1. Определение языка Во-первых, вы должны определить, как ваш язык должен выглядеть синтаксически.

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

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

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

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

Что касается реальных материалов для чтения, я бы предложил «Программирование языковых процессоров в JAVA» Дэвида А. Ватта и Дерика Ф. Брауна. Я использовал эту книгу в своем курсе по компиляции, и в этой области можно учиться на примерах.

Answer 3

Это абсолютно необходимые детали:

• Сканер: разбивает входной файл на токены
• Parser: создает абстрактное синтаксическое дерево (AST) из токенов, идентифицированных сканером.
• Генерация кода: производит вывод из AST.

Вы также, вероятно, захотите:

• Обработка ошибок: сообщает парсеру, что делать, если он обнаружил неожиданный токен
• Оптимизация: это позволит компилятору генерировать более эффективный машинный код

Редактировать: Вы уже разработали язык? Если нет, то вы тоже захотите взглянуть на языковой дизайн.

Answer 4

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

Answer 5

Номер один важный является книга о написании компилятора. Многие скажут вам прочитать «Книгу Дракона» Ахо и др., Но лучшая книга, которую я прочитал о компиляторах, - «Бринч Хансен о компиляторах Паскаля». Я подозреваю, что он вышел из печати (Amazon - ваш друг), но он проведет вас через все этапы разработки и написания компилятора с использованием рекурсивного спуска, который является самым простым методом для новичков в компиляции.

Хотя книга использует Pascal в качестве языка реализации и целевых языков, представленные уроки и методы в равной степени применимы ко всем другим языкам.

Answer 6

Действительно хороший набор бесплатных ссылок, ИМХО, это:

Общее руководство по компилятору: Давайте построим компилятор Джека Креншоу (http://compilers.iecc.com/crenshaw/) Это многословно, но мне нравится.

Ассемблер: NASM ( nasm.us ) хорош для Linux и Windows / DOS, и, что наиболее важно, много документации и примеров / учебных пособий ( FASM тоже хорошо, но меньше документации / учебных пособий)

другие источники Сборка ПК книга (http://www.drpaulcarter.com/pcasm/index.php)

Я пытаюсь написать LISP, поэтому я использую Lisp 1.5 Manual . Вы можете получить спецификацию языка для любого языка, который вы пишете.

Что касается 1-2KLOC, при условии, что вы используете язык высокого уровня (например, Py или Rb), вы должны быть близко, если вы не слишком амбициозны.

Answer 7

Все примеры приведены на Perl, но Изучение архитектуры языка программирования на Perl - хорошая книга (и бесплатная).

Answer 8

Я всегда рекомендую flex и bison для такого рода работы новичка. Вы всегда можете изучить все тонкости написания своего собственного сканера и анализатора позже, хотя они могут увеличить размер кода, по крайней мере, они будут сгенерированы для вас инструментами. :)