На основе курса Nand2Tetris и книги The Elements of Computing Systems

Мы уже можем программировать - у нас есть машинный код, который позволяет записывать значения в память и управлять потоком выполнения. Например, напишем простую программу сложения 2 и 3. Результат вычисления будет складываться в самое начало оперативной памяти:

0000000000000010
1110110000010000
0000000000000011
1110000010010000
0000000000000000
1110001100001000

В коде выше последовательно чередуются А и С команды, разберем что именно там написано:

  1. 0000000000000010 - записать в А регистр 2
  2. 1110110000010000 - записать в D регистр значение A регистра
  3. 0000000000000011 - записать в А регистр 3
  4. 1110000010010000 - записать в D регистр сумму из А регистра и D регистра
  5. 0000000000000000 - записать в А регистр 0
  6. 1110001100001000 - записать в М регистр значение из D регистра. Напомню, что M регистр всегда ссылается на RAM[A].

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

@2
D=A
@3
D=D+A
@0
M=D

Гораздо более читабельно. Кроме всего прочего, мы только что придумали язык ассемблера.

Рассмотрим еще одну программу. Она складывает числа от 0 до 100:

// Variables
@i
M=0     // Clear memory at i
@sum
M=0     // Clear memory at sum

(LOOP_START)
  @i
  D=M
  @100
  D=D-A
  @LOOP_END
  D;JGT  
  @i
  D=M
  @sum
  M=D+M
  
  @i
  M=M+1
  @LOOP_START
  0;JMP
(LOOP_END)

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

Комментарии

Комментарий - это любые символы, которые начинаются с “//”. С комментариями (как и с пустыми строчками) все просто - они просто вырезаются и в машинный код никак не вставляются. Они нужны, для облегчения чтения кода.

Символы

Символы можно разделить на два типа: переменные и метки

Переменные

Часть переменных уже задана заранее, например R0 - переменная из списка предустановленных, равна 0. Полный список предустановленных переменных можно посмотреть в книге The Elements of Computing Systems. А переменные i и sum - новые. За каждой новой переменной встретившийся в тексте программы закрепляется определенный адрес в RAM, начиная с адреса 16. 16 - потому что в реализации нашего ассемблера места с 0 по 15 отведены под предустановленные переменные.

Таким образом i = 16, sum = 17. Значение самой переменной всегда статично и, после присваивания, не меняется, но мы работаем обычно с местом в памяти. То есть, когда мы суммируем в программе числа, то фактически происходит не sum += i, а RAM[sum] += RAM[i], стоит это помнить.

Метки

Метки это переменные в скобочках: (LOOP_START), (LOOP_END). Они нужны для облегчения работы с ветвлением программы. Вместо того что бы руками высчитывать строчку, откуда нужно продолжить программу (и надеяться что оно не изменится, что вряд ли), можно просто поставить метку, которую тоже можно использовать как переменную, но вместо нее будет подставляться не 16 + variable_number, а номер строчки, на которой метка объявлена. В вычислении строки игнорируются сами объявления меток и пустые строки. Таким образом LOOP_START = 4, а LOOP_END = 18.

Перевод программы

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

Шаг 1: удалим пустые строчки\комментарии и пронумеруем только те строчки кода, которые будут переведены в машинный код

0:  @i
1:  M=0    
2:  @sum
3:  M=0    
    (LOOP_START)
4:    @i
5:    D=M
6:    @100
7:    D=D-A
8:    @LOOP_END
9:    D;JGT
10:   @i
11:   D=M
12:   @sum
13:   M=D+M
14:   @i
15:   M=M+1
16:   @LOOP_START
17:   0;JMP
    (LOOP_END)

Шаг 2: переведем метки

0:  @i
1:  M=0    
2:  @sum
3:  M=0    
4:  @i
5:  D=M
6:  @100
7:  D=D-A
8:  @18
9:  D;JGT
10: @i
11: D=M
12: @sum
13: M=D+M
14: @i
15: M=M+1
16: @4
17: 0;JMP

Шаг 3: переведем переменные

0:  @16
1:  M=0    
2:  @17
3:  M=0    
4:  @16
5:  D=M
6:  @100
7:  D=D-A
8:  @18
9:  D;JGT
10: @16
11: D=M
12: @17
13: M=D+M
14: @16
15: M=M+1
16: @4
17: 0;JMP

Шаг 4: В таком виде эти команды уже напрямую можно перевести в машинный код:

0000000000010000
1110101010001000
0000000000010001
1110101010001000
0000000000010000
1111110000010000
0000000001100100
1110010011010000
0000000000010010
1110001100000001
0000000000010000
1111110000010000
0000000000010001
1111000010001000
0000000000010000
1111110111001000
0000000000000100
1110101010000111

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

Реализация

Здесь реализация довольно прямолинейная, просто последовательно брать строчку и переводить ее в машинный код. Единственное, с чем может быть проблема - метки. С метками могут быть ситуации, когда их используют раньше, чем они объявлены (LOOP_END в примере выше). Один из способов справиться с этим - два прохода. В первый проход нужно будет собрать метки и их значения, во второй уже реализовать непосредственно перевод программы в машинный код.

Вариант реализации: https://github.com/ngrishaev/HackAssembler