Написание простейшего компилятора Brainfuck

Введение

В данной статье я хочу описать поэтапное создание компилятора языка Brainfuck на языке Go. И хоть это и далеко от компиляторов "больших" ЯП, многие принципы работы являются такими же, как и у "взрослых" собратьев Brainfuck.

О языке Brainfuck

Brainfuck — это эзотерический (esolang) язык программирования, созданный Урбаном Мюллером в 1993 году. Он состоит всего из 8 команд: + - > < . , [ ]. Программа работает с массивом из 30.000 ячеек памяти и указателем. Несмотря на крайне простой набор команд, на Brainfuck можно (не надо) реализовать почти любые вычисления.

Команды в языке Brainfuck

> — переместить указатель на ячейку вправо
< — переместить указатель на ячейку влево
+ — увеличить значение текущей ячейки на 1
- — уменьшить значение текущей ячейки на 1
. — вывести значение текущей ячейки как символ
, — считать символ во входную ячейку
[ — начать цикл, если текущая ячейка не равна 0
] — вернуться к [ или завершить цикл, если значение равно 0

Понятие компилятора

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

Структура компилятора

Компилятор обычно состоит из следующих компонентов, вызывающихся поочерёдно:

Лексический анализатор (Lexer) — разбивает исходный код на токены.
Синтаксический анализатор (Parser) — проверяет структуру программы и строит AST.
Семантический анализатор — проверяет смысл программы: типы, переменные, области видимости и т. д.
Оптимизатор — преобразует код, чтобы сделать его быстрее или компактнее.
Генератор кода — переводит программу в машинный код, байткод или другой целевой язык.

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

Создание структуры компилятора

Для начала список токенов:

internal/bf/tokens.go

package bf

var TOKENS = []string{"+", "-", ",", ".", "<", ">", "[", "]"}

И далее создадим структуру компилятора и публичный метод Compile:

internal/bf/compiler.go

package bf

type Compiler struct {
    Tokens []string
}

func NewCompiler() *Compiler {
    return &Compiler{
        Tokens: TOKENS,
    }
}

func (compiler *Compiler) Compile(code string) (string, error) {
    parsed := compiler.parse(code)

    translated, err := compiler.translate(parsed)

    return translated, err
}

Парсинг

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

internal/bf/parse.go

package bf

import "slices"

func (compiler *Compiler) parse(commands string) []string {
    parsed := []string{}

    for _, command := range commands {
        if slices.Contains(compiler.Tokens, string(command)) {
            parsed = append(parsed, string(command))
        }
    }

    return parsed
}

Трансляция

Опишем команды Go, в которые будет транслироваться код Brainfuck:

internal/bf/commands.go

package bf

const BEGIN = `// Generated by brainfuck compiler

package main

import (
    "bufio"
    "os"
)

func main() {

    memory := []rune{}
    cursor := 0

    for i := 0; i < 30000; i++ {
        memory = append(memory, 0)
    }
`

const END = `
}

func input() rune {
    reader := bufio.NewReader(os.Stdin)
    input, _ := reader.ReadString('\n')
    return rune([]byte(input)[0])
}
`

const TAB = "    "

var COMMANDS = map[string]string{
    "+": "memory[cursor]++",
    "-": "memory[cursor]--",
    ",": "memory[cursor] = input()",
    ".": "print(string(memory[cursor]))",
    "<": "cursor--",
    ">": "cursor++",
    "[": "for memory[cursor] != 0 {",
    "]": "}",
}

Далее опишем сам метод трансляции и файл с ошибками. В случае с трансляцией в Go важно помнить про корректное сохранение табуляции.

internal/bf/errors.go

package bf

import (
    "errors"
)

var (
    ErrNotOpenedCycle = errors.New("cycle not opened but close operator used")
)

internal/bf/translate.go

package bf

import "strings"

func (compiler *Compiler) translate(commands []string) (string, error) {
    end := BEGIN
    tabs := 1

    for _, command := range commands {

        end = end + "\n" + strings.Repeat(TAB, tabs) + COMMANDS[command]

        if command == "[" {
            tabs = tabs + 1
        }

        if command == "]" {
            tabs = tabs - 1
        }

        if tabs == 0 {
            return "", ErrNotOpenedCycle
        }
    }

    end = end + END
    return end, nil
}

Главный файл

В главном файле реализуем простейший CLI-интерфейс для работы компилятора, а так же функцию для компиляции итогового Go-кода:

cmd/bf/main.go

package main

import (
    "alexdenkk/bf/internal/bf"
    "fmt"
    "log"
    "os"
    "os/exec"
)

const HELP_MSG = `
brainfuck compiler

Usage:
build <filename> - compile file

Commands:
, | input cell
. | print cell
> | next cell
< | previous cell
+ | plus 1 to cell value
- | minus to cell value
[ | open cycle
] | close cycle

*Cycles must be closed

Basic expressions:
,>,[<+>-]<.                                | summation
>,[<->-]<.                                 | subtraction
,>,[<[->>+>+<<<]>>>[-<<<+>>>]<<<>-]<[-]>>. | multiplication`

func main() {
    compiler := bf.NewCompiler()

    if len(os.Args) > 2 {
        bfCode, err := readFile(os.Args[2])

        if err != nil {
            log.Fatal(err)
        }

        goCode, err := compiler.Compile(bfCode)

        if err != nil {
            log.Fatal(err)
        }

        err = writeFile(os.Args[2][:len(os.Args[2])-3]+".go", goCode)

        if err != nil {
            log.Fatal(err)
        }

        err = compileGoFile(os.Args[2][:len(os.Args[2])-3])

        if err != nil {
            log.Fatal(err)
        }
    } else {
        fmt.Println(HELP_MSG)
    }
}

func compileGoFile(filename string) error {
    cmd := exec.Command("go", "build", filename+".go")

    if err := cmd.Run(); err != nil {
        return err
    }

    return nil
}

func readFile(filename string) (string, error) {
    b, err := os.ReadFile(filename)

    if err != nil {
        return "", err
    }

    return string(b), nil
}

func writeFile(filename string, text string) error {
    return os.WriteFile(filename, []byte(text), 0644)
}

Тестирование

Попробуем скомпилировать две программы на Brainfuck:

hello_world.bf

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-<.+++.------.--------.>>+.>++.
# Hello World!

sum.bf

,>,[<+>-]<. # Сумма двух чисел

Вывод корректен:

Hello World!

4

h

Заключение

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

«The language had served its purpose. Or so I thought.» — Urban Müller

Написание простейшего компилятора brainfuck