Ассемблер: Начало

Инструкции… Собери!

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

Технически.

А что такое ассемблер? Это программа, которая может превратить это:

LOAD $1 #10

в:

00 01 00 0A

У него также есть несколько других обязанностей:

  • Обращение с ярлыками
  • Вычисление констант
  • Оптимизации

лексинг

лексер – это программа, которая принимает поток текста, проверяет его на соответствие набору правил и выдает поток токенов.

Лексемы и токены

Лексирование создает лексемы, которые являются чем-то вроде «единиц значения» в предложении. В нашем примере LOAD $1 #10 лексемами будут: LOAD, $, 1, #, 1, 0.

Эти лексемы объединяются с идентификатором или именем в маркер. Итак, в нашем примере наши токены:

  • ‹код операции, 0›
  • ‹регистр, 1›
  • ‹число, 10›

Грамматика

Итак, давайте определим некоторые вещи о нашем языке ассемблера:

  1. Программа состоит из Инструкций
    Инструкция состоит из:
    * Кода операции
    * A Регистр
    * IntegerOperand
    * Новая строка
  2. Код операции состоит из:
    * одной или нескольких букв подряд
    * пробела.
  3. Реестр состоит из:
    * символа $
    * числа
    * >Космос
  4. IntegerOperand состоит из:
    * символа #
    * числа
  5. Число состоит из:
    * символов 0–9.
  6. Новая строка состоит из:
    * символа \, за которым следует символ n.

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

Важно:
Чтобы глубже изучить лексику и грамматики, погуглите контекстно-свободные грамматики и форму Бэкуса-Наура.

Назад к Лексинг

Итак, как нам получить лексер?

Два варианта:

  1. Мы могли бы написать свой собственный лексер. Это не суперсложно, и каждый должен сделать это хотя бы один раз.
  2. Мы могли бы использовать такой инструмент, как `lex`.

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

Омномномномном

Чтобы начать поглощать биты, мы должны сделать следующее:

  1. Добавить nom в качестве зависимости
  2. Добавьте крейт nom в main.rs
  3. Создайте каталог модуля для ассемблера
  4. Добавьте модуль ассемблера в main.rs
  5. Создать перечисление токена
  6. Создать правила для nom

Номинальная зависимость

В файле Cargo.toml добавьте nom в качестве зависимости:

[dependencies]
nom = “4.0”

Файлы

  1. Создайте новый каталог в разделе src с именем assembler и добавьте в него файл mod.rs.
  2. В main.rs добавьте pub mod assembler вверху.
  3. В main.rs добавьте #[macro_use]; вверху
  4. В main.rs добавьте extern crate nom; на следующей строке.
  5. Создайте opcode.rs в src/assembler.

Перечисление токена

nom нужно что-то для генерации, поэтому нам нужно создать перечисление Token. В src/assembler/mod.rs поместите:

use instruction::Opcode;
#[derive(Debug, PartialEq)]
pub enum Token {
 Op{code: Opcode},
}

Прямо сейчас мы собираемся научить наш парсер распознавать код операции. Всякий раз, когда он находит его, он создает Token::Op{code: Opcode}.

Примечание:
Да, немного странно, что Token::Op содержит код, который является кодом операции. Первоначально определение было Token::Opcode{code: Opcode, но это сбивало с толку из-за дублирования слова Opcode и его использования в двух разных местах. Надеюсь, это прояснит ситуацию.

Правила: основы

Хорошо, время написать наше первое правило. Я постараюсь достаточно подробно рассказать о nom по ходу дела, но чтобы глубже погрузиться в него, просмотрите их GitHub.

Основная идея заключается в том, что мы собираемся использовать макросы nom для написания набора правил, которые при их применении могут анализировать файл, содержащий действительный ассемблерный код Iridium. Эти синтаксические анализаторы могут основываться друг на друге; это позволяет создавать сложные правила, состоящие из более простых правил. Вскоре мы увидим, насколько это полезно.

Правила: Опкод

Ранее в посте мы определили код операции как:

  1. «Код операции» состоит из:
    * одной или нескольких «букв» подряд
    * «пробела»

Давайте возьмем эту строчку за раз. В src/assembler/opcode_parsers.rs:

use nom::types::CompleteStr;

Это загружается в тип nom CompleteStr. Мы будем передавать в наши правила полные строки, а не потоковые данные.

named!(opcode_load<CompleteStr, Token>,

При этом используется макрос named! в контейнере nom для определения функции с именем opcode_load. Он примет CompleteStr и вернет Token.

  do_parse!(
    tag!(“load”) >> (Token::Op{code: Opcode::LOAD})
  )
)

Критической частью здесь является tag!(“load”) ›› (Token::Op{code: Opcode::LOAD}). Он ищет подстроку «load» в строке, которую мы ему передаем, и, если находит, возвращает перечисление.

Примечание.
Часть `›› (Token::Op{code: Opcode::LOAD})` взята из макроса `do_parse!`. Это позволяет нам связывать парсеры и передавать результаты парсерам, расположенным ниже по течению. Чуть позже мы увидим, как это работает более подробно.

Тесты

Пришло время написать тест для нашего парсера! В opcode_parsers.rs поместите:

mod tests {
 use super::*;
  #[test]
  fn test_opcode_load() {
  // First tests that the opcode is detected and parsed correctly
  let result = opcode_load(CompleteStr(“load”));
  assert_eq!(result.is_ok(), true);
  let (rest, token) = result.unwrap();
  assert_eq!(token, Token::Op{code: Opcode::LOAD});
  assert_eq!(rest, CompleteStr(“”));
  // Tests that an invalid opcode isn’t recognized
  let result = opcode_load(CompleteStr(“aold”));
  assert_eq!(result.is_ok(), false);
 }
}

Ура, у нас есть функция, которая может распознавать один опкод!

Правила: Регистры

Теперь о регистрах. Во-первых, давайте создадим вариант Register нашего перечисления Token в src/assembler/mod.rs:

#[derive(Debug, PartialEq)]
pub enum Token {
 Op{code: Opcode},
 Register{reg_num: u8}
}

Далее парсер для регистра. Мы поместим это в src/assembler/register_parsers.rs.

На нашем ассемблере они принимают форму $0; знак доллара, за которым следует число ›= 0. Наша функция для этого выглядит так:

use nom::types::CompleteStr;
use nom::digit;
use assembler::Token;
named!(register <CompleteStr, Token>, 
 ws!(
   do_parse!(
     tag!(“$”) >>
     reg_num: digit >>
     (
     Token::Register{
       reg_num: reg_num.parse::<u8>().unwrap()
     )
   )
 )
);
  1. Мы создаем функцию с именем «register», которая принимает «CompleteStr» и возвращает «CompleteStr» и «Token» или «Error».
  2. Мы используем макрос `ws!`, который говорит ему использовать любые пробелы по обе стороны от нашего регистра. Это позволяет нам писать такие варианты, как «LOAD $0» в дополнение к «LOAD $0».
  3. Мы используем do_parse! макрос для парсеров цепочки
  4. Мы используем tag! для поиска $, передаем результат tag!…
  5. …в функцию digit и сохраните результат в переменной с именем reg_num. nom предоставляет функцию digit, которая распознает один или несколько символов от 0 до 9.
  6. Попытка развернуть и сохранить результат разбора цифр в `u8`
  7. Создайте перечисление Token::Register с соответствующей информацией и верните
  8. Закройте структуру `Token`
  9. Закройте результат кортежа, который вернет макрос

Тесты

А теперь испытание для него…

#[test]
 fn test_parse_register() {
 let result = register(CompleteStr(“$0”));
 assert_eq!(result.is_ok(), true);
 let result = register(CompleteStr(“0”));
 assert_eq!(result.is_ok(), false);
 let result = register(CompleteStr(“$a”));
 assert_eq!(result.is_ok(), false);
}

Вы можете добавить еще больше ошибок, таких как «$», в зависимости от того, насколько вы довольны тестами.

Правила: Целочисленные операнды

И, наконец, целые операнды! Создайте вариант IntegerOperand нашего перечисления Token в src/assembler/mod.rs:

#[derive(Debug, PartialEq)]
pub enum Token {
 Op{code: Opcode},
 Register{reg_num: u8},
 IntegerOperand{value: i32},
}

Примечание:
Да, технически мы разрешаем пользователю вводить здесь отрицательные числа, так как мы анализируем их в i32. Однако наша инструкция LOAD может загружать только 16 бит. Это для будущего расширения.

Затем создайте файл src/assembler/operand_parsers.rs, в который мы поместим последний синтаксический анализатор, который нам нужно написать: тот, который распознает IntegerOperand. Мы сказали, что они состоят из #, за которыми следуют цифры. В operand_parsers.rs поместите:

use nom::types::CompleteStr;
use nom::digit;
use assembler::Token;
/// Parser for integer numbers, which we preface with `#` in our assembly language:
/// #100
named!(integer<CompleteStr, Token>,
 ws!(
   do_parse!(
     tag!(“#”) >>
     reg_num: digit >>
     (
       Token::Number{value: reg_num.parse::<i32>().unwrap()}
     )
   )
 )
);

Тесты

Угадайте, что это? Тест!

#[test]
fn test_parse_integer_operand() {
 // Test a valid integer operand
 let result = integer_operand(CompleteStr(“#10”));
 assert_eq!(result.is_ok(), true);
 let (rest, value) = result.unwrap();
 assert_eq!(rest, CompleteStr(“”));
 assert_eq!(value, Token::IntegerOperand{value: 10});
 // Test an invalid one (missing the #)
 let result = integer_operand(CompleteStr(“10”));
 assert_eq!(result.is_ok(), false);
}

Заворачиваем в mod.rs

Теперь в src/assembler/mod.rs экспортируйте три созданных нами модуля, добавив:

pub mod opcode_parsers;
pub mod operand_parsers;
pub mod register_parsers;

наверх.

Конец

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

Первоначально опубликовано на blog.subnetzero.io.