Skip to content

Files

Latest commit

 

History

History

python

README.md

Brainfuck. Транслятор и модель

Table of Contents


  • Преподаватель: Пенской Александр Владимирович.
  • bf_lang | bf_isa | harv | hw | tick | binary | stream | port | - | - | -

Примечания:

  • Данный проект имеет избыточное количество комментариев (к примеру, схемы продублированы в исходном коде для удобства читателя).
    • Более того, такое количество комментариев затруднит проверку вашей работы.
  • Данный проект предпочитает простоту элегантности, так как является учебным примером. Там, где можно написать без синтаксического сахара -- написано без него.
  • MR приветствуются, но должны учитывать вышесказанное.
  • Данный проект не является обязательным шаблоном, и вы можете использовать другую структуру проекта. При этом нагромождения модулей и классов следует избегать. Будьте проще.
  • Данный проект не может претендовать на высший балл, т.к.:
    • только интеграционные тесты;
    • ужасное бинарное представление инструкций.
  • Указанный выше вариант -- вымышленный.
  • Задание на лабораторную работу: lab4-task.md.

Язык программирования

program ::= term

term ::= symbol
       | comment
       | term term
       | "[" term "]"

symbol ::= ">" | "<" | "+" | "-" | "." | ","

comment ::= <any symbols except: "><+-.,[]">

Код выполняется последовательно. Операции:

  • + -- увеличить значение в текущей ячейке на 1
  • - -- уменьшить значение в текущей ячейке на 1
  • > -- перейти к следующей ячейке
  • < -- перейти к предыдущей ячейке
  • . -- напечатать значение из текущей ячейки (символ)
  • , -- ввести извне значение и сохранить в текущей ячейке (символ)
  • [ -- если значение текущей ячейки ноль, перейти вперёд по тексту программы на символ, следующий за соответствующей ] (с учётом вложенности)
  • ] -- если значение текущей ячейки не ноль, перейти назад по тексту программы на символ [ (с учётом вложенности)

Любые другие символы трактуются как комментарии.

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

Язык программирования Asm

Альтернативный вариант, реализующий язык программирования Asm вместо Brainfuck см. в файле ./README_asm.md.

Организация памяти

Модель памяти процессора (приведено списком, так как тривиальна):

  1. Память команд1. Машинное слово -- 32 бита. Адресация машинными словами -- 28 бит.
  2. Память данных. Машинное слово -- 8 бит, знаковое. Линейное адресное пространство. Реализуется списком чисел.

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

Система команд

Особенности процессора:

  • Доступ к памяти данных осуществляется по адресу, хранящемуся в специальном регистре data_address. Установка адреса осуществляется путём инкрементирования или декрементирования инструкциями < и >.
  • Обработка данных осуществляется по текущему адресу операциями + и -, а также через ввод/вывод.
  • Поток управления:
    • инкремент PC после каждой инструкции;
    • условный (jz) и безусловный (jmp) переходы (использование см. в разделе транслятор).

Набор инструкций

Язык Инструкция Кол-во тактов Описание
+ increment 2 увеличить значение в текущей ячейке на 1
- decrement 2 уменьшить значение в текущей ячейке на 1
< left 1 перейти к предыдущей ячейке
> right 1 перейти к следующей ячейке
. print 2 напечатать значение из текущей ячейки (символ)
, input 2 ввести извне значение и сохранить в текущей ячейке (символ)
jmp <addr> 1 безусловный переход
jz <addr> 2 переход, если в текущей ячейке 0
halt 0 остановка
  • <addr> -- исключительно непосредственная адресация памяти команд.

Кодирование инструкций

Типы данных в модуле isa, где:

  • Opcode -- перечисление кодов операций;
  • Term -- структура для описания значимого фрагмента кода исходной программы.

Бинарное представление

Бинарное представление инструкций:

┌─────────┬─────────────────────────────────────────────────────────────┐
│ 31...28 │ 27                                                        0 │
├─────────┼─────────────────────────────────────────────────────────────┤
│  опкод  │                      адрес перехода                         │
└─────────┴─────────────────────────────────────────────────────────────┘

Коды операций:

  • 0000 (0x0) -- increment -- увеличить значение в текущей ячейке на 1
  • 0001 (0x1) -- decrement -- уменьшить значение в текущей ячейке на 1
  • 0010 (0x2) -- left -- перейти к предыдущей ячейке
  • 0011 (0x3) -- right -- перейти к следующей ячейке
  • 0100 (0x4) -- print -- напечатать значение из текущей ячейки
  • 0101 (0x5) -- input -- ввести значение и сохранить в текущей ячейке
  • 0110 (0x6) -- jmp -- безусловный переход по адресу
  • 0111 (0x7) -- jz -- переход по адресу, если в текущей ячейке 0
  • 1000 (0x8) -- halt -- остановка выполнения программы

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

JSON представление

  • Машинный код сериализуется в JSON список.
  • Один элемент списка -- одна инструкция.
  • Индекс списка -- адрес инструкции. Используется для команд перехода.
  • Используется для работы с OCaml демо (legacy).

Пример:

[
    { "opcode": "jz", "arg": 5, "term": [ 1, 5, "]" ] }
]

где:

  • opcode -- строка с кодом операции;
  • arg -- аргумент (может отсутствовать);
  • term -- информация о связанном месте в исходном коде (если есть).

Транслятор

Интерфейс командной строки: translator.py <input_file> <target_file>

Реализовано в модуле: translator

Этапы трансляции (функция translate):

  1. Трансформирование текста в последовательность значимых термов.
  2. Проверка корректности программы (парность квадратных скобок).
  3. Генерация машинного кода.

Правила генерации машинного кода:

  • один символ языка -- одна инструкция;

  • для команд, однозначно соответствующих инструкциям, -- прямое отображение;

  • для циклов с соблюдением парности (многоточие -- произвольный код):

    Номер команды/инструкции Программа Машинный код
    n [ JZ (k+1)
    ... ... ...
    k ] JMP n
    k+1 ... ...

Примечание: вопросы отображения переменных на регистры опущены из-за отсутствия оных.

Модель процессора

Интерфейс командной строки: machine.py <machine_code_file> <input_file>

Реализовано в модуле: machine.

DataPath

     latch ─────────►┌──────────────┐  addr   ┌────────┐
     data            │ data_address │───┬────►│  data  │
     addr      ┌────►└──────────────┘   │     │ memory │
               │                        │     │        │
           ┌───────┐                    │     │        │
    sel ──►│  MUX  │         ┌──────────┘     │        │
           └───────┘         │                │        │
            ▲     ▲          │                │        │
            │     │          │       data_in  │        │ data_out
            │     └───(+1)───┘          ┌────►│        │─────┐
            │                │          │     │        │     │
            └─────────(-1)───┘          │  oe │        │     │
                                        │ ───►│        │     │
                                        │     │        │     │
                                        │  wr │        │     │
                                        │ ───►│        │     │
                                        │     └────────┘     │
                                        │                    ▼
                                    ┌────────┐  latch_acc ┌─────┐
                           sel ────►│  MUX   │  ─────────►│ acc │
                                    └────────┘            └─────┘
                                     ▲   ▲  ▲               │
                                     │   │  │               └───(==0)───► zero
                                     │   │  │               │
                                     │   │  └───(+1)────────┘
                                     │   │                  │
                                     │   └──────(-1)────────┘
                                     │                      │
            input ───────────────────┘                      └──────────► output

Реализован в классе DataPath.

data_memory -- однопортовая память, поэтому либо читаем, либо пишем.

Сигналы (обрабатываются за один такт, реализованы в виде методов класса):

  • latch_data_addr -- защёлкнуть выбранное значение в data_addr;
  • latch_acc -- защёлкнуть в аккумулятор выход памяти данных;
  • wr -- записать выбранное значение в память:
    • инкрементированное;
    • декрементированное;
    • с порта ввода input (обработка на Python):
      • извлечь из входного буфера значение и записать в память;
      • если буфер пуст -- выбросить исключение;
  • output -- записать аккумулятор в порт вывода (обработка на Python).

Флаги:

  • zero -- отражает наличие нулевого значения в аккумуляторе.

ControlUnit

   ┌─────────────────(+1)───────┐
   │                             │
   │    latch_program_counter    │
   │                  │          │
   │   ┌─────┐        ▼          │
   └──►│     │     ┌─────────┐   │    ┌─────────┐
       │ MUX │────►│ program │───┴───►│ program │
   ┌──►│     │     │ counter │        │ memory  │
   │   └─────┘     └─────────┘        └─────────┘
   │      ▲                               │
   │      │ sel_next                      │ current instruction
   │      │                               │
   └──────────────(select-arg)────────────┘
          │                               │      ┌─────────┐
          │                               │      │  step   │
          │                               │  ┌───│ counter │
          │                               │  │   └─────────┘
          │                               ▼  ▼        ▲
          │                       ┌─────────────┐     │
          └───────────────────────│ instruction │─────┘
                                  │   decoder   │
                                  │             │◄───────┐
                                  └─────────────┘        │
                                          │              │
                                          │ signals      │
                                          ▼              │
                                    ┌──────────┐  zero   │
                                    │          │─────────┘
                                    │ DataPath │
                     input ─────────►          ├─────────► output
                                    └──────────┘

Реализован в классе ControlUnit.

  • Hardwired (реализовано полностью на Python).
  • Метод process_next_tick моделирует выполнение полного цикла инструкции (1-2 такта процессора).
  • step_counter необходим для многотактовых инструкций;
    • в реализации класса ControlUnit отсутствует, т.к. неявно задан потоком управления.

Сигнал:

  • latch_program_counter -- сигнал для обновления счётчика команд в ControlUnit.

Особенности работы модели:

  • Цикл симуляции осуществляется в функции simulation.
  • Шаг моделирования соответствует одной инструкции с выводом состояния в журнал.
  • Для журнала состояний процессора используется стандартный модуль logging.
  • Количество инструкций для моделирования лимитировано.
  • Остановка моделирования осуществляется при:
    • превышении лимита количества выполняемых инструкций;
    • исключении EOFError -- если нет данных для чтения из порта ввода;
    • исключении StopIteration -- если выполнена инструкция halt.

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

Тестирование выполняется при помощи golden test-ов.

  1. Тесты для языка bf реализованы в: golden_bf_test.py. Конфигурации:
  2. Тесты для языка asm реализованы в: golden_asm_test.py. Конфигурации:

Запустить тесты: poetry run pytest . -v

Обновить конфигурацию golden tests: poetry run pytest . -v --update-goldens

Пример использования транслятора (бинарное и json представление машинного кода):

$ cd brainfuck/python
$ cat examples/cat.bf
,[.,]
$ ./translator.py examples/cat.bf out/target.bin
source LoC: 2 code instr: 6
$ xxd out/target.bin
00000000: 5000 0000 7000 0005 4000 0000 5000 0000  P...p...@...P...
00000010: 6000 0001 8000 0000                      `.......
$ cat out/target.bin.hex
0 - 50000000 - input
1 - 70000005 - jz 5
2 - 40000000 - print
3 - 50000000 - input
4 - 60000001 - jmp 1
5 - 80000000 - halt⏎
$ ./translator.py examples/cat.bf out/target.json
source LoC: 2 code instr: 6
$ cat out/target.json
[{"index": 0, "opcode": "input", "term": [1, 1, ","]},
 {"index": 4, "opcode": "jz", "arg": 5, "term": [1, 2, "["]},
 {"index": 2, "opcode": "print", "term": [1, 3, "."]},
 {"index": 3, "opcode": "input", "term": [1, 4, ","]},
 {"index": 4, "opcode": "jmp", "arg": 1, "term": [1, 5, "]"]},
 {"index": 5, "opcode": "halt"}]⏎

Пример использования модели процессора:

$ cat examples/foo_input.txt
foo
$ ./machine.py out/target.bin examples/foo_input.txt
DEBUG:root:TICK:   0 PC:   0/0 ADDR:   0 MEM_OUT: 0 ACC: 0 	input [50000000]
DEBUG:root:TICK:   1 PC:   0/1 ADDR:   0 MEM_OUT: 0 ACC: 0 	input [50000000]
DEBUG:root:input: 'f'
DEBUG:root:TICK:   2 PC:   1/0 ADDR:   0 MEM_OUT: 102 ACC: 0 	jz 5 [70000005]
DEBUG:root:TICK:   3 PC:   1/1 ADDR:   0 MEM_OUT: 102 ACC: 102 	jz 5 [70000005]
DEBUG:root:TICK:   4 PC:   2/0 ADDR:   0 MEM_OUT: 102 ACC: 102 	print [40000000]
DEBUG:root:TICK:   5 PC:   2/1 ADDR:   0 MEM_OUT: 102 ACC: 102 	print [40000000]
DEBUG:root:output: '' << 'f'
DEBUG:root:TICK:   6 PC:   3/0 ADDR:   0 MEM_OUT: 102 ACC: 102 	input [50000000]
DEBUG:root:TICK:   7 PC:   3/1 ADDR:   0 MEM_OUT: 102 ACC: 102 	input [50000000]
DEBUG:root:input: 'o'
DEBUG:root:TICK:   8 PC:   4/0 ADDR:   0 MEM_OUT: 111 ACC: 102 	jmp 1 [60000001]
DEBUG:root:TICK:   9 PC:   1/0 ADDR:   0 MEM_OUT: 111 ACC: 102 	jz 5 [70000005]
DEBUG:root:TICK:  10 PC:   1/1 ADDR:   0 MEM_OUT: 111 ACC: 111 	jz 5 [70000005]
DEBUG:root:TICK:  11 PC:   2/0 ADDR:   0 MEM_OUT: 111 ACC: 111 	print [40000000]
DEBUG:root:TICK:  12 PC:   2/1 ADDR:   0 MEM_OUT: 111 ACC: 111 	print [40000000]
DEBUG:root:output: 'f' << 'o'
DEBUG:root:TICK:  13 PC:   3/0 ADDR:   0 MEM_OUT: 111 ACC: 111 	input [50000000]
DEBUG:root:TICK:  14 PC:   3/1 ADDR:   0 MEM_OUT: 111 ACC: 111 	input [50000000]
DEBUG:root:input: 'o'
DEBUG:root:TICK:  15 PC:   4/0 ADDR:   0 MEM_OUT: 111 ACC: 111 	jmp 1 [60000001]
DEBUG:root:TICK:  16 PC:   1/0 ADDR:   0 MEM_OUT: 111 ACC: 111 	jz 5 [70000005]
DEBUG:root:TICK:  17 PC:   1/1 ADDR:   0 MEM_OUT: 111 ACC: 111 	jz 5 [70000005]
DEBUG:root:TICK:  18 PC:   2/0 ADDR:   0 MEM_OUT: 111 ACC: 111 	print [40000000]
DEBUG:root:TICK:  19 PC:   2/1 ADDR:   0 MEM_OUT: 111 ACC: 111 	print [40000000]
DEBUG:root:output: 'fo' << 'o'
DEBUG:root:TICK:  20 PC:   3/0 ADDR:   0 MEM_OUT: 111 ACC: 111 	input [50000000]
DEBUG:root:TICK:  21 PC:   3/1 ADDR:   0 MEM_OUT: 111 ACC: 111 	input [50000000]
DEBUG:root:input: '\n'
DEBUG:root:TICK:  22 PC:   4/0 ADDR:   0 MEM_OUT: 10 ACC: 111 	jmp 1 [60000001]
DEBUG:root:TICK:  23 PC:   1/0 ADDR:   0 MEM_OUT: 10 ACC: 111 	jz 5 [70000005]
DEBUG:root:TICK:  24 PC:   1/1 ADDR:   0 MEM_OUT: 10 ACC: 10 	jz 5 [70000005]
DEBUG:root:TICK:  25 PC:   2/0 ADDR:   0 MEM_OUT: 10 ACC: 10 	print [40000000]
DEBUG:root:TICK:  26 PC:   2/1 ADDR:   0 MEM_OUT: 10 ACC: 10 	print [40000000]
DEBUG:root:output: 'foo' << '\n'
DEBUG:root:TICK:  27 PC:   3/0 ADDR:   0 MEM_OUT: 10 ACC: 10 	input [50000000]
DEBUG:root:TICK:  28 PC:   3/1 ADDR:   0 MEM_OUT: 10 ACC: 10 	input [50000000]
WARNING:root:Input buffer is empty!
INFO:root:output_buffer: 'foo\n'
foo

ticks: 28

Footnotes

  1. Отвратительная реализация: чудовищная плотность кода, нереалистичная адресация словами. Историческое наследие. PR на исправление приветствуется в рамках дополнительных квестов.