Форум программистов, компьютерный форум, киберфорум
dserp18
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 1.

Интерпретатор Brainfuck на TASMe

Запись от dserp18 размещена 06.10.2018 в 23:00
Обновил(-а) dserp18 09.10.2018 в 10:57 (Добавил новый код)

Для начала напишем интерпретатор на высокоуровневом языке, например, на Паскале.

Массив data_arr будет представлять память данных, строка str_arr будет содержать команды.

Напишем программу, выводящую символ, ascii-код которого соответствует количеству + (поэтому нам нужны будут только команды + и .)
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
var
 data_arr:array[1..10] of integer;    // массив данных
 str_arr: string;                     // команды  
 i, j: integer;                       // индексы строки и массива
begin
 j:=1;                  // нумерация элементов массива (внезапно) начинается с единицы
 readln(str_arr);       //считываем строку
 
 for i:=1 to length(str_arr) do begin    // в цикле обрабатываем строку
  if (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1;
  if (str_arr[i]='.') then write(chr(data_arr[j]));
 end;
end.
bf-код +++++++++++++++++++++++++++++++++. выдаст ! (ascii-код символа ! равен 33 ).

Программу можно проверить в online ide ideone.com
можно выполнить отладку bf-кода в пошаговом режиме

Далее, заменим цикл for оператором goto и добавим команды - < >
В конце будем выводить массив data_arr
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LABEL prev,next;
var
 data_arr:array[1..10] of integer;    // массив данных
 str_arr: string;                     // команды  
 i,j,k: integer;                       // индексы строки и массива
begin
 i:=1;                 
 j:=1;
 readln(str_arr);       //считываем строку
 prev:
 if i>length(str_arr) then goto next; 
    if (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1;
    if (str_arr[i]='-') then data_arr[j]:= data_arr[j]-1;
    if (str_arr[i]='>') then j:=j+1;
    if (str_arr[i]='<') then j:=j-1;
    if (str_arr[i]='.') then write(chr(data_arr[j])); 
    
 i:=i+1;
 goto prev;
 next:
for k:=1 to 10 do begin 
write(data_arr[k]);
write(' ');
end;
end.
bf-код +>++>+++ выдаст 1 2 3 0 0 0 0 0 0 0
bf-код +>++>+++- выдаст 1 2 2 0 0 0 0 0 0 0
https://ideone.com/1whGbP

Далее, добавим [ и ]
Добавим ещё одну переменную i_stor
Если текущий элемент прошёл проверку на [ ,то проверяем текущий элемент массива data_arr на ноль, и, если элемент больше нуля, загружаем в i_stor значение из переменной i.

При обработке закрывающей скобки ] ,если data_arr не ноль, в переменную i из переменной i_stor загружаем адрес открывающей скобки [

Далее переходим к команде i:=i+1;
Если до этого в i было загружено значение из i_stor ( при проверке ] ), то после джампа мы окажемся за [ ( в противном случае мы окажемся за ] )
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
LABEL prev,next;
var
 data_arr:array[1..10] of integer;    // массив данных
 str_arr: string;                     // команды  
 i,j,k: integer;                       // индексы строки и массива
 i_stor: integer; 
begin
 j:=1;                 
 i:=1;
 readln(str_arr);       //считываем строку
 prev:
 if i>length(str_arr) then goto next; 
    if (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1;
    if (str_arr[i]='-') then data_arr[j]:= data_arr[j]-1;
    if (str_arr[i]='>') then j:=j+1;
    if (str_arr[i]='<') then j:=j-1;
    if (str_arr[i]='.') then write(chr(data_arr[j]));
    if (str_arr[i]='[') then
     begin  
      if data_arr[j]>0 then i_stor:=i;
     end;
    if (str_arr[i]=']') then
     begin  
      if data_arr[j]>0 then 
       begin
       i:=i_stor;
       end;
     end;
    
 i:=i+1;
 goto prev;
 next:
for k:=1 to 10 do begin 
write(data_arr[k]);
write(' ');
end;
end.
Код +++++[>+<-] переносит число 5 в соседнюю ячейку 0 5 0 0 0 0 0 0 0 0
https://ideone.com/zGI4ev
Код HelloWorld выглядит так https://ideone.com/QLIhX5

Перейдем к ассемблеру

Чтобы организовать цикл loop, необходимо поместить в регистр CX количество тактов цикла и поставить метку, на которую будет сделан переход по завершении такта (по команде loop).
Assembler
1
2
3
4
5
6
mov CX, 28h    ; кол-во тактов цикла
prev:                ; метка цикла
; выполняем 
; операции
; внутри цикла
loop prev          ; возвращаемся на метку prev
Создадим массив команд str_arr, поместим туда +++
Создадим массив данных data_arr, (для наглядности) поместим туда 1 1 1 1 1 1 1 1 1 1

В цикле сравниваем текущий символ с символом + и, если символы равны, увеличиваем значение в текущей ячейке на 1
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
text segment                      ; bf1.asm 
assume cs:text, ds:data, ss:stk
begin: 
 ;Подготовим все необходимое
  mov AX,data          ; настраиваем сегмент данных                                       
  mov DS,AX             
  mov DL, str_arr      ; загружаем в DL 1ую команду 
  mov CX, 0Ah          ; 10 тактов
prev:                    
 cmp DL, 2Bh           ; ячейка содержит +
 jne next              ; нет, переходим на метку next  
 mov BL, 00h           ; загружаем в BL индекс 
 inc data_arr[BX]      ; да, увеличиваем  значение в ячейке на 1
 next:
 inc i                 ; переходим на следующий символ массива команд
 mov BL, i
 mov DL, str_arr [BX]   
 loop prev 
         
  mov AX, 4c00h        ; завершение программы  
  int 21h 
text ends
 
data segment           
str_arr DB  2Bh,2Bh,2Bh,'$' ; код +++
data_arr DB 1,1,1,1,1,1,1,1,1,1,'$' ; данные
i DB 0                  ;индекс элемента массива команд 
data ends
 
stk segment stack      
 db 100h dup (0)       ; резервируем 256 ячеек
stk ends
end begin
Ассемблирование (трансляция) выполняется командой tasm.exe bf1.asm
Линковка выполняется командой tlink.exe bf1.obj

После выполнения программы в отладчике TurboDebagger видно, что начиная с адреса 0130 расположены команды +++
Далее идет массив данных, в котором мы изменили первый элемент, далее идет переменная i, которая после выполнения цикла стала равна 0Ah.
Нажмите на изображение для увеличения
Название: abf1.jpg
Просмотров: 286
Размер:	49.6 Кб
ID:	5048

Добавим команды - < > .
Для того, чтобы вывести одиночный символ с помощью функции 02h прерывания int 21h, необходимо (перед вызовом прерывания) поместить код символа в регистр DL
Assembler
1
2
3
 mov AH,2 
 mov DL, код символа
 int 21h
Напишем программу целиком
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
text segment                     ; bf2.asm 
assume cs:text,ds:data, ss:stk
begin: 
 ;Подготовим все необходимое
  mov AX,data        ; настраиваем сегмент данных                                       
  mov DS,AX             
  mov DL, str_arr    ; загружаем в DL 1ую команду 
  mov CX, 0Ah        ; 10 тактов
prev:                    
 cmp DL, 2Bh         ; ячейка содержит +
 jne next            ; нет, переходим на метку next  
 mov BL, j           ; загружаем в BL индекс данных
 inc data_arr[BX]    ; да, увеличиваем  значение в ячейке на 1
next: 
 cmp DL, 2Dh         ; ячейка содержит -
 jne next1           ; нет, переходим на метку next1  
 mov BL, j 
 dec data_arr[BX]     
next1: 
 cmp DL, 3Eh        ; ячейка содержит >
 jne next2          ; нет, переходим на метку next2  
 inc j              ; да, переходим на сдедующий элемент массива data_arr
next2: 
 cmp DL, 3Ch        ; ячейка содержит <
 jne next3          ; нет, переходим на метку next3  
 dec j              ; да, переходим на предыдущий элемент массива data_arr
next3: 
 cmp DL, 2Eh        ; ячейка содержит .
 jne next4          ; нет, переходим на метку next4  
 mov AH,2           ; да, выводим содержимое ячейки
 mov BL, j
 mov DL, data_arr[BX]
 int 21h
 next4:
 inc i                 ; переходим на следующий символ массива команд
 mov BL, i
 mov DL, str_arr [BX]   
 loop prev 
         
 mov AX, 4c00h        ; завершение программы  
 int 21h 
text ends
 
data segment           
str_arr DB  2Bh,3Eh,2Bh,2Bh,'$' ; код +>++
data_arr DB 0,0,0,0,0,0,0,0,0,0,'$'  ; данные
i DB 0, '$'                              ;индекс элемента массива команд 
j DB 0, '$'                             ;индекс элемента массива данных
data ends
 
stk segment stack      
 db 100h dup (0)       ; резервируем 256 ячеек
stk ends
end begin
Нажмите на изображение для увеличения
Название: abf2.jpg
Просмотров: 371
Размер:	49.2 Кб
ID:	5049

Цикл работает так:
если текущий элемент строки str_arr не + то перепрыгиваем на метку next: (иначе выполняем +)
если текущий элемент строки str_arr не - то перепрыгиваем на метку next1:
если текущий элемент строки str_arr не > то перепрыгиваем на метку next2:
если текущий элемент строки str_arr не < то перепрыгиваем на метку next3:
если текущий элемент строки str_arr не . то перепрыгиваем на метку next4:
После метки next4: увеличиваем индекс строки str_arr и прыгаем в начало цикла — на метку prev:

Также добавим [ и ]
Добавим переменную i_stor.

Если текущий элемент прошёл проверку на [ ,то проверяем текущий элемент массива data_arr на ноль, и, если элемент равен нулю, перепрыгиваем дальше (на следующую метку), в противном случае загружаем в i_stor значение из переменной i.
Assembler
1
2
3
4
5
6
7
8
9
10
next4:
 cmp DL, 5Bh         ; ячейка содержит [
 jne next5           ; нет, переходим на метку next5
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next5            ; если ноль, прыгаем дальше
 mov DL, i           ; иначе загружаем 
 mov i_stor, Dl      ; в i_stor значение переменной i 
next5:
При обработке закрывающей скобки ], если data_arr не ноль, то в переменную i из переменной i_stor загружаем адрес открывающей скобки [
Assembler
1
2
3
4
5
6
7
8
9
10
next5:
 cmp DL, 5Dh         ; ячейка содержит ]
 jne next6           ; нет, переходим на метку next6
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next6            ; если ноль, прыгаем дальше
 mov DL, i_stor      ; иначе загружаем 
 mov i, Dl           ; в i_stor значение переменной i 
next6:
Проверим код +++++[>+<-]
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
text segment                     ; bf4.asm
assume cs:text, ds:data, ss:stk
begin: 
 ;Подготовим все необходимое
  mov AX,data        ; настраиваем сегмент данных                                       
  mov DS,AX             
  mov DL, str_arr    ; загружаем в DL 1ую команду 
  mov CX, 50h        ; 80 тактов
prev:                    
 cmp DL, 2Bh         ; ячейка содержит +
 jne next            ; нет, переходим на метку next  
 mov BL, j           ; загружаем в BL индекс данных
 inc data_arr[BX]    ; да, увеличиваем  значение в ячейке на 1
next: 
 cmp DL, 2Dh         ; ячейка содержит -
 jne next1           ; нет, переходим на метку next1  
 mov BL, j 
 dec data_arr[BX]    ;BX, но не Bl 
next1: 
 cmp DL, 3Eh         ; ячейка содержит >
 jne next2           ; нет, переходим на метку next2  
 inc j               ; да, переходим на сдедующий элемент массива data_arr
next2: 
 cmp DL, 3Ch         ; ячейка содержит <
 jne next3           ; нет, переходим на метку next3  
 dec j               ; да, переходим на предыдущий элемент массива data_arr
next3: 
 cmp DL, 2Eh         ; ячейка содержит .
 jne next4           ; нет, переходим на метку next4  
 mov AH,2            ; да, выводим содержимое ячейки
 mov BL, j
 mov DL, data_arr[BX]
 int 21h
next4:
 cmp DL, 5Bh         ; ячейка содержит [
 jne next5           ; нет, переходим на метку next5
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next5            ; если ноль, прыгаем дальше
 mov DL, i           ; иначе загружаем 
 mov i_stor, Dl      ; в i_stor значение переменной i 
next5:
 cmp DL, 5Dh         ; ячейка содержит ]
 jne next6           ; нет, переходим на метку next6
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next6            ; если ноль, прыгаем дальше
 mov DL, i_stor      ; иначе загружаем 
 mov i, Dl           ; в i_stor значение переменной i 
next6:
 inc i               ; переходим к следующей команде
 mov BL, i
 mov DL, str_arr[BX]   
 loop prev          ; прыгаем на метку prev:
         
 mov AX, 4c00h      ; завершение программы  
 int 21h 
text ends
 
data segment           
 str_arr DB  2Bh,2Bh,2Bh,2Bh,5Bh, 3Eh,2Bh,3Ch,2Dh ,5Dh, '$'   ; код ++++[>+<-]
 data_arr DB 0,0,0,0,0,0,0,0,0,0,'$'  ; данные
 i DB 0,'$'                              ;индекс элемента массива команд 
 j DB 0,'$'                            ;индекс элемента массива данных
 i_stor DB 0,'$'
data ends
 
stk segment stack      
 db 100h dup (0)       ; резервируем 256 ячеек
stk ends
end begin
Нажмите на изображение для увеличения
Название: abf3.jpg
Просмотров: 272
Размер:	50.4 Кб
ID:	5050

Добавим функцию ввода строки/файла 3fh прерывания 21h
Assembler
1
2
3
4
  mov ah, 3fh          ; функция ввода
  mov cx, 100h        ; 256 символов
  mov dx,OFFSET str_arr
  int 21h
Выходить из цикла будем по достижении конца строки '$'.
Для этого будем сравнивать текущий символ с символом '$'
Assembler
1
2
cmp DL, 24h ; символ '$'
je  exit_loop
Заменим цикл loop командой jmp.

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
text segment                    
assume cs:text,ds:data, ss: stk
begin:  
 ;Подготовим все необходимое
  mov AX,data        ; настраиваем сегмент данных                                       
  mov DS,AX
  
; функция ввода
  mov ah, 3fh        
  mov cx, 100h       ; 256 символов
  mov dx,OFFSET str_arr
  int 21h
  ;             
  mov DL, str_arr    ; загружаем в DL 1ую команду 
  ;mov CX, 100h        ; 256 тактов
prev:
 cmp DL, 24h ; символ '$'
 je  exit_loop
                    
 cmp DL, 2Bh         ; ячейка содержит +
 jne next            ; нет, переходим на метку next  
 mov BL, j           ; загружаем в BL индекс данных
 inc data_arr[BX]    ; да, увеличиваем  значение в ячейке на 1
next: 
 cmp DL, 2Dh         ; ячейка содержит -
 jne next1           ; нет, переходим на метку next1  
 mov BL, j 
 dec data_arr[BX]    ;BX, но не Bl 
next1: 
 cmp DL, 3Eh         ; ячейка содержит >
 jne next2           ; нет, переходим на метку next2  
 inc j               ; да, переходим на следующий элемент массива data_arr
next2: 
 cmp DL, 3Ch         ; ячейка содержит <
 jne next3           ; нет, переходим на метку next3  
 dec j               ; да, переходим на предыдущий элемент массива data_arr
next3: 
 cmp DL, 2Eh         ; ячейка содержит .
 jne next4           ; нет, переходим на метку next4  
 mov AH,2            ; да, выводим содержимое ячейки
 mov BL, j
 mov DL, data_arr[BX]
 int 21h
next4:
 cmp DL, 5Bh         ; ячейка содержит [
 jne next5           ; нет, переходим на метку next5
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next5            ; если ноль, прыгаем дальше
 mov DL, i           ; иначе загружаем 
 mov i_stor, Dl      ; в i_stor значение переменной i
next5:
 cmp DL, 5Dh         ; ячейка содержит ]
 jne next6           ; нет, переходим на метку next6
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next6            ; если ноль, прыгаем дальше
 mov DL, i_stor      ; иначе загружаем 
 mov i, Dl           ; в i_stor значение переменной i 
 ; здесь должен быть переход на метку prev:    
next6:
 inc i               ; переходим к следующей команде
 mov BL, i
 mov DL, str_arr[BX]   
; loop prev          ; прыгаем на метку prev:
 jmp prev
 exit_loop: 
 
 MOV    AH,2       ; переходим на новую строку
 MOV    DL,0Ah     
 INT    21h        
 mov AX, 4c00h      ; завершение программы  
 int 21h 
text ends
 
data segment           
  str_arr DB 256h DUP('$')  ; буфер на 256 символов
 data_arr DB 0,0,0,0,0,0,0,0,0,0,'$'  ; данные
 i DB 0,'$'                              ;индекс элемента массива команд 
 j DB 0,'$'                            ;индекс элемента массива данных
 i_stor DB 0,'$'
data ends
 
stk segment para stack 
 db 100h dup (0)       ; резервируем 256 ячеек
stk ends
end begin
В процессе компиляции получаем ошибку
Цитата:
Relative jump out of range by 0001h bytes
Дело в том, что команды je/jne могут перепрыгнуть только через несколько строчек программы (каждая строчка занимает в памяти от 1 до 5 байт).
Нажмите на изображение для увеличения
Название: jmp.gif
Просмотров: 166
Размер:	9.6 Кб
ID:	5052
Прыжок через 9 bytes

Длинные переходы в конец программы je/jne совершать не могут.
Поэтому заменим выражение
Assembler
1
2
3
4
 cmp DL, 24h ; символ '$'
 je  exit_loop
 ...
exit_loop:
выражением
Assembler
1
2
3
4
5
6
cmp DL, 24h ; символ '$'
 jne  exit_
jmp exit_loop
 exit_
...
exit_loop:
Итак, если текущий символ соответствует $, то переходим на метку exit_loop: командой jmp, иначе перепрыгиваем через команду jmp.
На метку команда jmp может делать внутрисегментный относительный короткий переход (переход меньше 128 байт, т.е. IP:=IP+i8) или внутрисегментный относительный длинный переход (переход меньше 32767 байт, т.е. IP:=IP+i16).
По умолчанию команда jmp делает относительный длинный переход, что нам и надо (а вообще вместо этого можно просто добавить директиву jumps в начало программы).
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
;jumps
text segment                    
assume cs:text,ds:data, ss: stk
begin:  
 ;Подготовим все необходимое
  mov AX,data        ; настраиваем сегмент данных                                       
  mov DS,AX
  ;;;
  mov ah, 3fh        ; функция ввода
  mov cx, 100h       ; 256 символов
  mov dx,OFFSET str_arr
  int 21h
  ;;;             
  mov DL, str_arr    ; загружаем в DL 1ую команду 
  ;mov CX, 100h        ; 256 тактов
prev:
 cmp DL, 24h ; символ '$'
 ;je  exit_loop
 jne l1
 jmp exit_loop 
 l1:
                   
 cmp DL, 2Bh         ; ячейка содержит +                        
 jne next            ; нет, переходим на метку next  
 mov BL, j           ; загружаем в BL индекс данных             
 inc data_arr[BX]    ; да, увеличиваем  значение в ячейке на 1  
next: 
 cmp DL, 2Dh         ; ячейка содержит -                             
 jne next1           ; нет, переходим на метку next1  
 mov BL, j 
 dec data_arr[BX]    ;BX, но не Bl 
next1: 
 cmp DL, 3Eh         ; ячейка содержит >
 jne next2           ; нет, переходим на метку next2  
 inc j               ; да, переходим на следующий элемент массива data_arr
next2: 
 cmp DL, 3Ch         ; ячейка содержит <
 jne next3           ; нет, переходим на метку next3  
 dec j               ; да, переходим на предыдущий элемент массива data_arr
next3: 
 cmp DL, 2Eh         ; ячейка содержит .
 jne next4           ; нет, переходим на метку next4  
 mov AH,2            ; да, выводим содержимое ячейки
 mov BL, j
 mov DL, data_arr[BX]
 int 21h
next4:
 cmp DL, 5Bh         ; ячейка содержит [
 jne next5           ; нет, переходим на метку next5
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next5            ; если ноль, прыгаем дальше
 mov DL, i           ; иначе загружаем 
 mov i_stor, Dl      ; в i_stor значение переменной i
next5:
 cmp DL, 5Dh         ; ячейка содержит ]
 jne next6           ; нет, переходим на метку next6
 mov BL, j
 mov DL, data_arr[BX]
 cmp DL, 00          ; да, проверяем текущий элемент data_arr на ноль  
 jz next6            ; если ноль, прыгаем дальше
 mov DL, i_stor      ; иначе загружаем 
 mov i, Dl           ; в i_stor значение переменной i 
 ; здесь должен быть переход на метку prev:    
next6:
 inc i               ; переходим к следующей команде
 mov BL, i
 mov DL, str_arr[BX]   
; loop prev          ; прыгаем на метку prev:
 jmp prev
 exit_loop: 
 
 MOV    AH,2       ; переходим на новую строку
 MOV    DL,0Ah     
 INT    21h        
 mov AX, 4c00h      ; завершение программы  
 int 21h 
text ends
Размещено в Без категории
Показов 488 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.