Как сделать компилятор

Обновлено: 07.07.2024

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

3 ответа 3

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками c++ компилятор brainfuck или задайте свой вопрос.

Метод раскрутки

Пусть есть компилятор , где P - некоторый язык более высокого уровня, чем язык ассемблера. Тогда напишем : L \to A" />
, а затем применим компилятор к компилятору " />
, т.е. получим ): L \to A" />
. Такая схема проиллюстрирована с помощью Т-диаграмм на слайде и называется раскруткой ( bootstrapping 2 Название метода раскрутки произошло от фразы "to pull oneself up by one's bootstrap ", т.е. "вытянуть себя за шнурки", аналогично легендарному методу барона Мюнхгаузена ); компилятор " />
как бы "раскручивается" с помощью компилятора .

Описанная схема может быть использована при написании компилятора некоторого языка на нем самом. Пусть у нас есть компилятор некоторого подмножества S языка L в язык A, написанный на языке A, . Тогда мы можем написать : L \to A " />
и получим новый компилятор )" />
. Мы используем это подмножество S для того, чтобы написать компилятор языка L в язык A, : L \to A " />
. Если теперь мы применим компилятор к программе " />
, то получим ): L \to A" />

Впервые такая схема была применена в 1960 году при реализации языка Neliac. В 1971 году Вирт написал с использованием раскрутки транслятор языка Pascal , причем самый первый компилятор был оттранслирован вручную. Количество шагов раскрутки было больше 1, т.е. была построена последовательность языков и построена последовательность компиляторов: \to A, K_^=K_(K_: S_ \to A), .." />
.

Раскрутку можно использовать и в следующей ситуации. Пусть у нас есть недостаточно эффективный компилятор . Можно написать более эффективный компилятор : L \to A " />
, а затем применить раскрутку.

Кросс-транслятор

Пусть у нас есть два компьютера: компьютер M с языком ассемблера A и компьютер " />
с языком ассемблера " />
. Кроме того, предположим, что имеется компилятор : P \to A_" />
, а сам компьютер M по каким-то причинам не доступен либо пока еще не существует компилятор . Нас интересует компилятор . В такой ситуации мы можем использовать " />
в качестве инструментальной машины и написать компилятор : L \to A " />
, который принято называть кросс-транслятором (cross-compiler) . Как только машина M станет доступной, мы сможем перенести " />
на M и "раскрутить" его с помощью . Понятно, что это решение достаточно трудоемко, поскольку могут возникнуть проблемы при переносе, например, из-за различий операционных систем.

Под переносимой (portable) программой понимается программа , которая может без перетрансляции выполняться на нескольких (по меньшей мере, на двух) платформах. В связи с этим возникает вопрос о переносимости объектных программ, создаваемых компилятором. Компиляторы, созданные по методикам, рассмотренным выше, порождают непереносимые (non-portable) объектные программы. Поскольку компилятор , в конечном итоге, является программой, то мы можем говорить и о переносимых компиляторах. Одним из способов получения переносимых объектных программ является генерация объектной программы на языке более высокого уровня, чем язык ассемблера. Такие компиляторы иногда называют конвертерами (converter) .

Почему LLVM?

Модульная архитектура компилятора

Рис. 1. Модульная архитектура компилятора

Кроме вышеперечисленных программ, LLVM включает в себя и другие утилиты [6].
Итак, напишем простейшую программу на C.

И скомпилируем её:
clang-3.5 -c add.c -O0 --target=xcore -emit-llvm -S -o add_o0.ll

Некоторые пояснения:
-c add.c — входной файл;
-O0 — уровень оптимизации 0, оптимизация отсутствует;
—target=xcore — ядро процессора xcore не имеет каких-либо сложных особенностей при компиляции в IR-код, поэтому является идеальным объектом для исследований. Это ядро имеет разрядность 32, и clang выравнивает все переменные по границам 32-битных слов;
-emit-llvm -S — указание clang-у сгенерировать файл llvm в текстовом виде (на ассемблере LLVM);
-o add_o0.ll — выходной файл
Посмотрим на результат:
; ModuleID = 'add.c'
target datalayout = "e-m:e-p:32:32-i1:8:32-i8:8:32-i16:16:32-i64:32-f64:32-a:0:32-n32"
target triple = "xcore"

Структура кода LLVM

Структура кода LLVM очень проста. Код программы состоит из модулей, компилятор обрабатывает по одному модулю за раз. В модуле есть глобальные объявления (переменные, константы и объявления заголовков функций, находящихся в других модулях) и функции. Функции имеют аргументы и возвращаемые типы. Функции состоят из базовых блоков. Базовый блок — это последовательность команд ассемблера LLVM, имеющая одну точку входа и одну точку выхода. Базовый блок не содержит внутри себя никаких ветвлений и циклов, он выполняется строго последовательно от начала до конца и должен заканчиваться терминирующей командой (возвратом из функции или переходом на другой блок).
И, наконец, базовый блок состоит из команд ассемблера. Список команд приведён в документации на LLVM [7].
Итак, ещё раз: базовый блок имеет одну точку входа, помеченную меткой, и обязательно должен заканчиваться командой безусловного перехода br или командой возврата ret. Перед ними может быть команда условного перехода, в этом случае она должна быть непосредственно перед терминирующей командой. Базовый блок имеет список predecessors — базовых блоков, из которых управление может приходить на него, и successors — базовых блоков, которым он может передавать управление. На основе этой информации строится CFG — Control Flow Graph, граф потока управления, важнейшая структура, представляющая программу в компиляторе.
Рассмотрим тестовый пример на языке С:
Пусть исходный код на языке С имеет цикл:

Его CFG имеет вид:

Ещё одним видом графов в LLVM является DAG — directed acyclic graph, направленный ациклический граф, представляющий собой базовый блок.
Он представляет команды ассемблера и зависимости между ними. На рисунке ниже приведён DAG базового блока, представляющий тело цикла в примере выше, при уровне оптимизации -O1:

SSA-форма

Ключевой особенностью IR-кода, отличающей его от языков высокого уровня является то, что он представлен в так называемой SSA-форме (Static Single Assignment form). Эта особенность очень важна для понимания при разработке компилятора на платформе LLVM, поэтому уделим ей некоторое внимание. Если формулировать кратко, то в SSA-форме каждой переменной значение присваивается ровно один раз и только в одной точке программы. Все алгоритмы оптимизации и преобразования IR-кода работают только с такой формой.
Однако, как преобразовать обычную программу на языке высокого уровня в такую форму? Ведь в обычных языках программирования значение переменной может присваиваться несколько раз в разных местах программы, или, например, в цикле.
Для реализации такого поведения программы используется один из двух приемов. Первый прием заключается в использовании пар команд load/store, как в вышеприведённом коде. Ограничение единственного присваивания распространяется только на именованные переменные LLVM, и не распространяется на ячейки памяти, на которые ссылаются указатели. То есть, можно неограниченное количество раз производить запись в ячейку памяти командой store, и формальное правило SSA будет соблюдено, так как указатель на эту ячейку не меняется. Этот способ используется обычно при уровне оптимизации -O0, и мы не будем на нём подробно останавливаться. Второй прием использует φ-функции, ещё одну интересную концепцию IR-кода.

Код в SSA-форме: load/store

; :2 ; preds = %12, %0
%3 = load i32* %i, align 4
%4 = icmp slt i32 %3, 10
br i1 %4, label %5, label %15

; :5 ; preds = %2
%6 = load i32* %i, align 4
%7 = load i32** %1, align 4
%8 = getelementptr inbounds i32* %7, i32 %6
%9 = load i32* %8, align 4
%10 = load i32* %sum, align 4
%11 = add nsw i32 %10, %9
store i32 %11, i32* %sum, align 4
br label %12

; :12 ; preds = %5
%13 = load i32* %i, align 4
%14 = add nsw i32 %13, 1
store i32 %14, i32* %i, align 4
br label %2

; :15 ; preds = %2
%16 = load i32* %sum, align 4
ret i32 %16
>

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

Код в SSA-форме: φ-функции

; :1 ; preds = %1, %0
%i.02 = phi i32 [ 0, %0 ], [ %5, %1 ]
%sum.01 = phi i32 [ 0, %0 ], [ %4, %1 ]
%2 = getelementptr inbounds i32* %x, i32 %i.02
%3 = load i32* %2, align 4, !tbaa !2
%4 = add nsw i32 %3, %sum.01
%5 = add nsw i32 %i.02, 1
%exitcond = icmp eq i32 %5, 10
br i1 %exitcond, label %6, label %1

; :6 ; preds = %1
ret i32 %4
>

Здесь мы видим, что переменной цикла является %i.02 (имена переменных в LLVM могут содержать точки), и это не указатель, а обычная 32-битная переменная, а присваивание значения происходит с помощью функции phi i32 [ 0, %0 ], [ %5, %1 ]. Это означает, что функция примет значение 0, если переход произошёл с базового блока %0 (первый базовый блок в функции), и значение переменной %5, если переход произошёл с базового блока %1 (т.е. с выходной точки этого же базового блока). Таким образом, генератор IR-кода избавился от двух присваиваний переменной, строго следуя формальным правилам SSA. Далее видно, что сходным образом происходит присваивание переменной %sum.01.
Итак, смысл φ-функции состоит в том, что её значение зависит от того, из какого базового блока был произведён переход на неё. φ-функции могут находиться только в начале базового блока. Если их несколько, они должны следовать непрерывно, начиная с первой инструкции базового блока.

Moar optimization!

Компоновка IR-кода

Реальные программы состоят не из одного модуля. Традиционный компилятор компилирует модули по отдельности, превращая их в объектные файлы, а затем передаёт их компоновщику (линкеру), который объединяет их в один исполняемый файл. LLVM тоже позволяет так делать.
Но LLVM имеет также возможность компоновки IR-кода. Проще всего рассмотреть это на примере. Пусть есть два исходных модуля: foo.c и bar.c:

Генерация кода целевой платформы

Заключение

В рамках небольшой статьи нельзя рассмотреть подробно ни архитектуру LLVM, ни синтаксис языка LLVM IR, ни процесс разработки бэкенда. Однако эти вопросы подробно освещаются в документации. Автор скорее старался дать общее представление об инфраструктуре компиляторов LLVM, сделав упор на то, что эта платформа является современной, мощной, универсальной, и независимой ни от входного языка, ни от целевой архитектуры процессора, позволяя реализовать и то, и другое по желанию разработчика.
Помимо рассмотренных, LLVM содержит и другие утилиты, однако их рассмотрение выходит за рамки статьи.
LLVM позволяет реализовать бэкенд для любой архитектуры (см. примечание), включая архитектуры с конвейеризацией, с внеочередным выполнением команд, с различными вариантами параллелизации, VLIW, для классических и стековых архитектур, в общем, для любых вариантов.
Вне зависимости от того, насколько нестандартные решения лежат в основе процессорной архитектуры, это всего лишь вопрос написания большего или меньшего объёма кода.

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

Литература

Помогите с решением данного задания
По заданию нужно сделать компилятор который будет решать простые арифметические действия(+,-,*,/), проверять логические условия = и переходить по метке (if (логич условие )) then goto metka и выводить результат.
Подскажите какую литературу почитать,какие статьи, на чем лучше написать(visual studio c++?)

Компилятор с поддержкой русского языка
Использую MS Visual с++ 6.0, но он не поддерживает русского языка. Если в коде есть русские буквы -.

Интерпретатор/компилятор ассемблер-подобного языка
Привет! Чую, что изобрёл велисипед, даже скорее велопарк, но всё же, поделюсь: Некоторое время.

написать компилятор
Написать транслятор для следующего фрагмента программы (на языке Паскаль или Си++). Недостающие.

Книги: Б. Страуструп, Дейтел, Джесс Либерти.

Ну, чтобы выводить результат нужно чтобы, как минимум, оператор вывода поддерживал. А переменные не нужно?

Ищите по форуму. Тема многократно обсуждалась и все ссылки давались.

Ну, чтобы выводить результат нужно чтобы, как минимум, оператор вывода поддерживал. А переменные не нужно?

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

какие следующие шаги нужно сделать можете по пунктам написать

Думается, тут речь идёт всё-таки об интерпретаторе, а не о компиляторе
Пишем свой интерпретатор языка BASIC

Т.е. всё-таки по смыслу псевдокомпилятор, работающий до псевдоассемблера. Передняя часть остаётся такой же (построение промежуточного представления), в задней части вместо исполнения выполняется печать псевдоассемблера

Взял версию отсюда Пишем свой интерпретатор языка BASIC
Отрезал от неё работу с графикой, чтобы не было геморроя при компиляции (т.к. для графики требуется дополнительная библиотека SDL)

В своё время поленился входной файл передавать по опции, а потому входной файл должен иметь имя a.txt. Если что, в каталоге test есть всякие другие программы, которые можно исполнять (кроме графики, которую отрезал)

Для такого исходника:

имеем такое исполнение

по опции -q можно распечатать промежуточное представление, которое по смыслу уже можно считать что-то ассемблероподобным

по опции -v можно увидеть таблицу переменных

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

Задачка интересная. Помнится, писал я трансляторы с ассемблеров для разных микроконтроллеров. Похожая задача.
Сценарий такой: 1) пишем лексический анализатор (входящий поток символов разбиваем на лексемы, проверяем их принадлежность предопределенным классам лексем); 2) делаем синтаксический анализатор (проверяем порядок сочетания лексем по диаграммам переходов, отражающим корректный порядок следования лексем); 3) разрабатываем семантический анализатор и генератор кода. Вот в примитивном случае как-то так.

В строке линковки у тебя опция -lm находится слева от объектных файлов, а должна быть справа (грубо говоря, в конце строки)

Написать компилятор
Всем привет! У меня возник вот такой вопрос? Нужно написать компилятор, а я незнаю с чего.

Написать интерпретатор программного языка -помощь
Здраствуйте! Ребят, кто хорошо разбирается в C++ помогите пожалуйста с реализацией данного задания.

Написать Интерпретатор Программного Языка(собственного)
Здраствуйте! Кто знает C++ помогите пожалуйста с реализацией данного задания. Пожалуйста.

Возможно ли на c++ написать простой видеочат
Привет, мир! Помогите разрешить спор, мы с другом поспорили. Возможно ли на c++ написать простой.

Читайте также: