Как создать интерпретатор бейсика на ассемблере

Хотите попрактиковаться в кодинге на ассемблере? Давайте вместе шаг за шагом создадим интерпретатор бейсика и запустим его прямо из загрузочного сектора вашего компьютера. Для этого придется задействовать перекрывающиеся подпрограммы с разветвленной рекурсией, иначе бейсик не уместится в 512 байт. Скорее всего, это будет самая сложная программа в вашей жизни. Когда вы создадите ее своими руками, сможете без зазрения совести называть себя суперкоддером / хакером.

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

Как пользоваться интерпретатором

По сути, написав бейсик для бутсектора, мы превратим ваш компьютер в аналог старых домашних компьютеров типа Commodore 64 или ZX Spectrum, которые имели этот язык в ПЗУ и позволяли программировать на нем сразу после загрузки.

Техническое задание (что будет уметь наш интерпретатор) я сформулирую в виде инструкции пользователя. Вот она.

Интерпретатор работает в двух режимах: интерактивном и обычном. В интерактивном режиме он выполняет команды сразу после ввода.

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

Если нужно удалить строку из исходника, просто введите в командной строке ее номер.

Как интерпретатор узнаёт, в каком режиме обрабатывать текст из командной строки? Если строка начинается с номера, интерпретатор обрабатывает ее в обычном режиме. Если не с номера — в интерактивном.

Максимальный размер программы — 999 строчек. Максимальная длина строки — 19 символов. Обратите внимание, что клавиша Backspace функционирует как надо. Хоть на экране символ и не затирается, в буфере все в порядке.

В распоряжении у программиста:

• три команды: run (запускает программу), list (выводит исходник на экран), new (стирает программу);
• 26 переменных (от a до z): двухбайтовые целые числа без знака;
• выражения, которые могут включать в себя: числа, четыре арифметические операции, скобки, переменные;
• три оператора: if, goto, =;
• две функции: print, input.

Вот языковые конструкции, которые понимает наш интерпретатор:

• var=expr присваивает значение expr переменной var (от a до z);
• print expr выводит значение expr и переводит курсор на следующую строку;
• print expr; выводит значение expr и оставляет курсор на текущей строке;
• print "][ello" печатает строку и переводит курсор на следующую строку;
• print "][ello"; печатает строку и оставляет курсор на текущей строке;
• input var считывает значение с клавиатуры, помещает его в переменную var (a..z);
• goto expr переходит на указанную строку программы;
• if expr1 goto expr2 — если expr1 не 0, прыгнуть на строку expr2, иначе на следующую после if.

Пример: if c-5 goto 2 (если c-5 не 0, прыгаем на строку 2).

Создание интерпретатора

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

• буфер для текста из командной строки;
• буфер для хранения исходника программы;
• массив для хранения переменных (от a до z);
• указатель на текущую строку программы.

Все сегментные регистры нацеливаем на CS. Затем сбрасываем «флаг направления», чтобы строки обрабатывались слева направо, а не наоборот (когда будем обращаться к инструкциям вроде stosb). Буфер, который предназначен для исходника программы, заполняем символом 0x0D (символ возврата каретки, более известный как клавиша Enter).

Исходник программы на бейсике будем обрабатывать как двумерный символьный массив: 1000 × 20.

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

Запуск главного рабочего цикла

Здесь сначала восстанавливаем указатель стека (регистр SP). На тот случай, если программа на бейсике обрушилась из-за ошибки.

Затем сбрасываем указатель running (текущая строка программы). Потом вызываем подпрограмму input_line, которая ждет, пока программист что-нибудь напечатает. Подпрограмма сохраняет полученную строку в регистр SI.

Дальше смотрим, начинается строка с номера или нет. Если с номера, нам надо записать ее в буфер, который отведен под исходник. Для этого сначала вычисляем адрес, куда записывать строку. За это у нас отвечает подпрограмма find_address (результат кладет в регистр DI). Определив нужный адрес, копируем туда строку: rep movsb.

Если в начале строки нет номера, сразу выполняем ее: execute_statement.

Обработка строки программы

Строки программы обрабатываем следующим образом. Берем первое слово из строки и последовательно сравниваем его с каждой записью из таблицы @@statements (см. внизу статьи последний кусок кода). В этой таблице общим списком перечислены команды, операторы и функции, которые понимает наш интерпретатор.

Обратите внимание, какую эвристику я здесь использую, чтобы сэкономить байты на обработку условного оператора. Перед точкой входа execute_statement я поставил дополнительный вход в ту же самую подпрограмму: @@if_handler.

Зачем? Чтобы не надо было писать отдельный обработчик для конструкций вроде if a-2 goto 10. Если результат выражения (в данном случае a-2) равняется нулю, мы не заходим в if, то есть игнорируем остаток строки (в нашем случае goto 10).

С if разобрались. Дальше обрабатываем остальные команды, операторы и функции. Начинаем с того, что пропускаем лишние пробелы, которые программист добавил для своего удобства. Если в строке нет ничего, кроме пробелов, просто игнорируем ее.

Но если строка не пустая, присматриваемся к ней внимательно. Сначала перебираем по порядку таблицу @@statements и сверяем свою строку с каждой записью оттуда. Каким образом сверяем? Считываем размер строки (в случае run это 3) и затем сравниваем, используя repe / cmpsb.

Если совпадение обнаружилось, то регистр DI теперь указывает на соответствующий адрес обработчика. Поэтому мы без лишних телодвижений прыгаем туда: jmp [di]. Чтобы лучше понять, в чем тут прикол, загляните в конец статьи, посмотрите, как устроена таблица @@statements. Подсказка: метки, которые начинаются с @@, — это как раз и есть адреса обработчиков.

Если всю таблицу перебрали, но совпадения так и не нашли, значит, текущая строка программы — это не команда, не оператор и не функция. Раз так, может быть, это название переменной? Прыгаем на @@to_get_var, чтобы проверить.

Дальше проматываем регистр DI к следующей записи таблицы. Каким образом? Прибавляем CX (длина имени текущей команды, оператора или функции плюс еще два байта (адрес обработчика). Потом восстанавливаем значение регистра SI ( rep cmpsb перемотала его вперед), чтобы он опять указывал на начало строки, по которой мы выполняем поиск в таблице операторов.

Теперь DI указывает на следующую запись из таблицы. Если эта запись ненулевая, прыгаем на @@next_entry, чтобы сравнить строку программы, вернее ее начало, с этой записью.

Если мы прошли всю таблицу, но так и не нашли совпадения, значит, текущая строка — не команда, не оператор и не функция. В таком случае это, скорее всего, конструкция присваивания вроде var=expr. По идее, других вариантов больше нет. Если, конечно, в исходник не закралась синтаксическая ошибка.

Теперь нам надо вычислить выражение expr и поместить результат по адресу, с которым связана переменная var. Подпрограмма get_variable вычисляет нужный нам адрес и кладет его на стек.

После того как адрес найден, проверяем, есть ли после имени переменной оператор присваивания. Если да, нам надо его выполнить. Но в целях экономии байтов мы сделаем это не здесь.

Чуть ниже нам с вами так и так придется реализовывать присваивание внутри функции input. Вот на тот кусок кода мы и прыгнем: @@assign. Целиком нам тут функция input ни к чему. Понадобится только ее финальная часть, вот ее и берем. Обратно в execute_statement возвращаться не будем. Нужный ret выполнит сама функция input.

Если знака присваивания нет, печатаем сообщение об ошибке и прекращаем выполнение программы, то есть прыгаем на @@main_loop. Там интерпретатор восстановит указатель стека и сможет работать дальше, несмотря на то что наткнулся на синтаксическую ошибку.

Выполнение команды list

Команда list выводит на экран листинг программы, которая записана в буфере. Каким образом она работает?

Сначала сбрасываем в ноль номер текущей строки в программе: xor ax, ax. Затем по номеру строки вычисляем адрес, откуда считывать строку программы: find_address. Когда адрес строки найден, сравниваем первый символ с 0x0D, то есть смотрим, не пустая ли строка. Если пустая, переходим к следующей.

Но если нет, то выводим ее на экран. Сначала отображаем ее номер: output_number. Потом считываем из буфера саму строку посимвольно, пока не наткнемся на 0x0D. И так же посимвольно выводим ее на экран.

Затем переходим к следующей строке программы ( inc ax) и повторяем все то же самое. Продолжаем до тех пор, пока не достигнем max_line, то есть 1000.

Выполнение функции input

Функция input позволяет ввести число с клавиатуры. Работает она так.

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

На случай, если пользователь введет не просто число, а какое-нибудь заковыристое выражение, мы прогоняем введенную строку через process_expr. Конечный результат помещаем по тому адресу, который вычислили в начале подпрограммы. В этом нам поможет инструкция stosw.

Обработка выражения

Обработка выражений будет трехуровневая.

1. Сложение и вычитание.
2. Умножение и деление.
3. Вложенные выражения (в скобках), имена переменных и числа.

На первом уровне, у которого приоритет самый низкий, сразу же передаем управление второму уровню: вызываем expr2_left. Затем, когда более приоритетные операции обработаны, смотрим на следующий символ. Если это знак сложения или вычитания, обрабатываем его. Каким образом?

Сначала сохраняем левое значение: push ax. Затем передаем правую часть выражения второму уровню: expr2_right. Когда более приоритетные операции выполнены, берем левое значение ( pop cx) и выполняем нужную операцию с правым: add ax, cx или sub ax, cx.

Наконец, зацикливаемся на @@next_sub_add, чтобы корректно вычислять выражения вроде 1+2+5-4.

На втором уровне делаем все то же самое, что и на первом. Сначала опять передаем управление более приоритетному уровню: обращаемся к expr3_left. Затем смотрим на следующий символ. Если это знак деления или умножения, обрабатываем его. В конце, как и в предыдущем случае, закручиваем цикл ( @@next_div_mul), чтобы интерпретатор понимал выражения вроде 3*4*2/1.

Обратите внимание, что при такой организации уровней наш интерпретатор автоматически учитывает приоритет операций. Например, выражение 5*6+3*4 вычисляется как (5*6)+(3*4).

На третьем уровне обрабатываем скобки (вложенные выражения), имена переменных и числа.

Сначала удаляем пробелы из входной строки. Затем смотрим на левый символ. Если это открывающая скобка, запускаем рекурсию: обращаемся к process_expr. После того как вложенное выражение обработано, проверяем, есть ли у него закрывающая скобка. Если нет, выдаем ошибку. А если есть, пропускаем пробелы, следующие за ней, и радостно делаем ret.

Но что, если слева не открывающая скобка, а какой-то другой символ? Может быть, это имя переменной? Проверяем: cmp al 0x40 / jnc @@yes_var.

Если предположение подтвердилось, идем считывать значение переменной. А если нет, значит, текущий символ — это кусок числа. Отступаем на один шаг ( dec si) и вызываем dec_str_to_number, чтобы прочитать число.

Подпрограмма: адрес переменной по ее имени

У этой подпрограммы две точки входа. На первой точке входа ( get_var) читаем букву переменной при помощи lodsb, на второй ( get_var_2) — используем имя переменной, которое передано через регистр AL. Изврат, конечно, но чего не сделаешь, чтобы сэкономить пару-тройку байтов.

Теперь, когда имя переменной у нас есть, надо вычислить адрес, с которым она связана. Делаем это в три шага.

1. Выполняем and al, 0x1F, чтобы извлечь номер переменной; здесь ASCII-значения 0x61–0x7A конвертируются в 0x01–0x1A.
2. Умножаем результат на 2, поскольку каждая переменная использует 16-битное слово в памяти.
3. Добавляем к адресу старшую его часть: mov ah, vars>>8.

Все! Мы знаем ячейку памяти, с которой связана переменная.

Обратите внимание, что этот код переплетен с подпрограммой, которая пропускает пробелы. У той подпрограммы тоже две точки входа. Первая ( skip_spaces) пропускает пробелы, которые идут за переменной, вторая ( skip_spaces_2) делает то же самое, но только оставляет первый пробел.

Подпрограмма: печать десятичного числа

Подпрограмма печатает на экране число, переданное через регистр AX. Каким образом? Рекурсивно делим AX на 10. После каждого деления сохраняем остаток на стеке. После того как доделились до нуля, начинаем выходить из рекурсии. Перед каждым выходом снимаем со стека очередной остаток и выводим его на экран.

Несколько примеров. Если AX = 4, то после деления на 10 в AX будет 0 и поэтому output_number не зайдет в рекурсию. Просто выведет остаток, то есть четверку, и все.

Если AX = 15, то после деления на 10 в AX будет единица. И поэтому подпрограмма залезет в рекурсию. Покажет там единичку, затем выйдет из внутреннего вызова в основной и там уже напечатает цифру 5.

Обратите внимание на jmp в конце и на то, что у программы нету своего ret. Это еще один небольшой хак, чтобы сэкономить парочку байтов. Мы не вызываем подпрограмму вывода символа, а джампимся на нее. Нужный нам ret она сделает сама.

Подпрограмма: из десятичной строки в шестнадцатеричное число

Подпрограмма переводит строку, в которой записано десятичное число (на нее указывает регистр SI), и записывает результат в регистр AX.

Переводить десятичную строку в шестнадцатеричное число будем вот как. Проходим в цикле по всем цифрам слева направо. Каждый раз умножаем аккумулятор на 10 (первый раз там у нас ноль) и прибавляем к нему текущую цифру. Если натыкаемся в строке на что-то отличное от цифры, сконфуженно выходим — ошибка.

Обратите внимание: между cmp al, 10 и условным переходом стоит две операции. Так что итоговый результат всегда попадает в регистр AX, даже в случае ошибки.

Выполнение команды run/goto

Команды run и goto запускают программу, которая записана в буфере. Run запускает ее с самого начала, а goto — с произвольной строчки. Обе команды будем обрабатывать одной и той же подпрограммой.

Когда интерпретатор видит команду run, он сначала превращает ее в goto 0 и дальше обрабатывает ее точно так же, как goto. Каким образом превращает? Сбрасывает регистр AX в ноль и прыгает на @@goto_handler.

Выполнять команду goto начинаем с того, что вычисляем выражение, которое записано после goto. Результат, то есть номер строки, куда прыгать, помещаем в AX.

Затем по номеру строки вычисляем адрес, где записана эта строка: find_address.

Обратите внимание, что командой goto можно пользоваться как в интерактивном, так и в обычном режиме. То есть и в программе ее использовать в качестве оператора, и с клавиатуры набирать для непосредственного выполнения.

Что делает инструкция сравнения cmp word [running], 0? Смотрит, откуда мы сюда попали: из интерактивного режима или из обычного.

Если из обычного режима, просто записываем в переменную running адрес, откуда дальше выполнять программу. На следующем такте интерпретатор вытащит с этого адреса нужную строку программы и выполнит ее.

Но если мы попали сюда из интерактивного режима (программист вошел в программу не через run, а через goto), то прыгаем на строку исходника, которая указана в goto.

А вот та подпрограмма, которая по заданному номеру вычисляет адрес строки в исходнике. Каким образом? В AX у нас записан номер строки. Умножаем его на стандартную длину строки и прибавляем адрес первой строки программы. Так мы получаем искомый адрес.

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

Теперь научим наш интерпретатор принимать с клавиатуры строки программы. За это будет отвечать подпрограмма input_line. На входе она получает символ командной строки (через регистр AL): знак «больше».

Сначала выводим командную строку. Затем нацеливаемся на буфер, куда будем сохранять текст из командной строки. Потом читаем символ с клавиатуры и, если это не Backspace ( 0x08), сохраняем его в буфер. Но если нажата Backspace, уменьшаем регистр DI на единицу, чтобы он указывал на предыдущий символ.

Выполнение функции print

Функцию print сделаем такой, чтобы она понимала разный синтаксис:

• print переводит курсор на следующую строку;
• print "Hello" печатает текст и ставит курсор на следующую строку;
• print "Hello;" печатает текст и оставляет курсор на текущей строке;
• print 5 печатает число и ставит курсор на следующую строку;
• print 5+2; печатает число и оставляет курсор на текущей строке.

Первое сравнение, cmp al, 0x0D, отслеживает первый вариант синтаксиса — без аргументов.

Второе сравнение, cmp al, '"', отслеживает два варианта синтаксиса, когда надо напечатать строку. В этом случае поочередно выводим все символы, пока не наткнемся на закрывающую кавычку или на 0x0D. Если наткнулись на 0x0D, значит, программист забыл ввести вторую кавычку. Ругаться ошибкой на него за это не будем.

Дальше смотрим, есть ли после кавычки точка с запятой. Если нет, переводим курсор на следующую строку.

На метке @@no_quote обрабатываем два варианта синтаксиса, когда надо напечатать число. Если вместо числа нам подсунули выражение, вычисляем его. Потом выводим его и смотрим, есть ли дальше точка с запятой. Если нет, переводим курсор на следующую строку.

Подпрограммы: ввод-вывод символов

Сделаем две вспомогательные подпрограммы — для input и для print.

Подпрограмма input_key считывает нажатую клавишу при помощи прерывания BIOS 0x16, функция 0x00. ASCII-код клавиши попадает в регистр AL.

Обратите внимание: эта подпрограмма перекрывается со следующей, поэтому она не заканчивается инструкцией ret. Зачем здесь такое трюкачество? Чтобы, не отходя от кассы, в смысле не тратя дополнительных байтов, вывести на экран символ, который пришел с клавиатуры.

Подпрограмма output_char сначала проверяет, не нажат ли Enter: cmp al, 0xD. Если так, то в довесок к символу 0xD печатаем еще и 0xA. Без 0xA курсор будет просто уходить влево, не перескакивая на следующую строку. Символы печатаем при помощи BIOS: прерывание 0x10, функция 0x0E.

Таблица команд, функций и операторов

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

При такой структуре очень удобно добавлять новые команды, функции и операторы. Просто дописываете сюда еще одну строчку, затем вставляете обработчик в удобном месте, и все. Больше ничего править в коде не надо.

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

Тестирование интерпретатора: создание программы «Треугольник Паскаля»

Треугольник Паскаля — это треугольная таблица биноминальных коэффициентов. Сверху стоит число 1. Числа, которые появляются в последующих строках, — это сумма двух ближайших вышестоящих чисел. Вот исходник, который надо скормить интерпретатору.

Если вы все сделали правильно, интерпретатор должен выдать что-то похожее на такую картинку.

Интерпретатор работает правильно? Если так, можете гордиться собой. Вы только что своими руками создали полноценный интерпретатор языка бейсик. При желании можете попытаться расширить его функциональность. Например:

• добавить команду cls (очистка экрана);
• добавить операторы gosub и return, чтобы можно было писать подпрограммы;
• реализовать поддержку массивов.

Напоследок пара организационных моментов.

• Для компиляции программы используйте NASM: nasm -f bin MicroB.asm.asm -o MicroB.asm.com.
• Если боитесь редактировать бутсектор, можете тестировать интерпретатор через эмулятор DOS — например, DOSBox.

РЕКОМЕНДУЕМ:
Змейка на ассемблер NASM под Linux

На этом все. Теперь вы знаете, как создать интерпретатор бейсика на ассемблере.