Хороший способ создать ассемблер?

Question

У меня есть домашнее задание для моей школы. Цель состоит в том, чтобы создать действительно базовую виртуальную машину, а также простой ассемблер. У меня не возникло проблем с созданием виртуальной машины, но я не могу придумать «хороший» способ создания ассемблера.

Грамматика этого ассемблера действительно базовая: необязательная метка, за которой следует двоеточие, а затем мнемоника с последующим 1, 2 или 3 операндами. Если имеется более одного операнда, они должны быть разделены запятыми. Кроме того, пробелы игнорируются, если они не встречаются в середине слова.

Я уверен, что смогу сделать это с помощью strtok() и некоторой черной магией, но я бы предпочел сделать это «чистым» способом. Я слышал о Parse Trees/AST, но я не знаю, как перевести код сборки в эти структуры.

Answer 1

Я написал такого ассемблера, когда был подростком. Вам не нужен сложный парсер.

Все, что вам нужно сделать, это пять шагов для каждой строки:

1. разметить (т.е. разделить строку на лексемы). Это даст вам массив токенов, и вам не нужно беспокоиться об этом, потому что вы удалите его во время токенизации.
2. Инициализировать некоторые переменные, представляющие части строки, до NULL.
3. Последовательность операторов if, чтобы пройти через массив токенов и проверить, какие части строки присутствуют. Если они присутствуют, помещают токен (или обработанную его версию) в соответствующую переменную, в противном случае оставить эту переменную равной NULL (т. Е. Ничего не делать).
4. Сообщить о любых синтаксических ошибках (т. Е. Комбинациях типов токенов, которые не разрешены).
5. Генерация кода - я думаю, вы знаете, как сделать эту часть!

Answer 2

То, что вы ищете, на самом деле является лексическим анализом, анализируя наконец команду генерации скомпилированного кода. Существует множество фреймворков, которые помогают создавать/генерировать парсер, например Gold Parser или ANTLR. Создание определения языка (и изучение того, как в зависимости от используемой структуры) чаще всего представляет собой довольно много работы.

Я думаю, что вам лучше с внедрением shunting yard algorithm. Который преобразует ваш источник в компьютеры представления, которые понимают, что позволяет легко понять вашу виртуальную машину.

Я также хочу сказать, что погружение в синтаксические анализаторы, абстрактные деревья синтаксиса, все инструменты, доступные в Интернете, и чтение большого количества работ по этому предмету - действительно хорошее изучение!

Answer 3

Если операнды могут быть выражениями, такими как «1 < < (x + 5)», вам нужно будет написать парсер. Если нет, синтаксический анализатор настолько прост, что вам не нужно думать в этих терминах. Для каждой строки получаем первую строку (пропуская пробелы). Строка заканчивается двоеточием? то это ярлык, иначе это менонический. и т. д.

Answer 4

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

В сущности, вы пишете небольшой лексер, который по-разному использует входной файл по-символу и классифицирует все на простые маркеры, например. числа, метки, коды операций и специальные символы.

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

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

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

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

О, и я настоятельно рекомендует рекомендовать вам выписать the dragon book из своей местной университетской библиотеки как можно скорее.

Answer 5

Вы можете ознакомиться с некоторыми уже созданными ассемблерами, такими как PASMO: assmbler для Z80 CPU и получить от него идеи. Вот он: http://pasmo.speccy.org/

Я написал пару очень простых ассемблеров, причем оба они используют строковые манипуляции с помощью strtok() и тому подобное. Для простой грамматики, такой как язык ассемблера, достаточно. Ключами моих сборщиков являются:

Таблица символов: всего лишь массив структур, с именем символа и его значением.

typedef struct 
{ 
    char nombre[256]; 
    u8 valor; 
} TSymbol; 

TSymbol tablasim[MAXTABLA]; 
int maxsim = 0; 

Символ - это просто имя, связанное с этим значением. Это значение может быть текущей позицией (адресом, где будет собираться следующая инструкция), или может быть явным значением, назначенным псевдонимом EQU.

Названия символов в этой реализации ограничены 255 символами, а один исходный файл ограничен MAXTABLA символами.

я выполнить два прохода в исходный код:

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

Здесь у вас есть образец моего кода, который отвечает за обновление таблицы символов значением от EQU текущей позиции и, если необходимо, продвижение текущей позиции.

case 1: 
    if (es_equ (token)) 
    { 
     token = strtok (NULL, "\n"); 
     tablasim[maxsim].valor = parse_numero (token, &err); 
     if (err) 
     { 
      if (err==1) 
       fprintf (stderr, "Error de sintaxis en linea %d\n", nlinea); 
      else if (err==2) 
       fprintf (stderr, "Simbolo [%s] no encontrado en linea %d\n", token, nlinea); 
      estado = 2; 
     } 
     else 
     { 
      maxsim++; 
      token = NULL; 
      estado = 0; 
     } 
    } 
    else 
    { 
     tablasim[maxsim].valor = pcounter; 
     maxsim++; 
     if (es_instruccion (token)) 
      pcounter++; 
     token = NULL; 
     estado = 0; 
    } 
    break; 

Второй проход, где я на самом деле собрать инструкции, заменяя символ с его значением, когда я нашел. Это довольно просто, используя strtok() разделить линию на ее компоненты, а также с помощью strncasecmp() сравнить то, что я нахожу с мнемоникой

Answer 6

По крайней мере, в моем опыте, нормальные генераторы лексера/анализатор (например, флекс, бизон/byacc) являются все это бесполезно для этой задачи.

Когда я это сделал, почти все было сильно управляемым таблицей - обычно одна таблица мнемоники, а для каждого из них - набор индексов в таблицу форматов инструкций, указав, какие форматы возможны для это инструкция. В зависимости от ситуации, это может иметь смысл сделать это для каждого операнда, а не для каждой инструкции (например, для команд mov, которые имеют довольно большой набор возможных форматов как для источника, так и для адресата).

В типичном случае вам придется посмотреть на формат (ы) операнда (ов), чтобы определить формат инструкции для конкретной команды. Для довольно типичного примера формат #x может указывать на немедленное значение, x - прямой адрес, а @x - косвенный адрес. Другой распространенной формой для косвенного адреса является (x) или [x], но для вашего первого ассемблера я стараюсь придерживаться формата, который задает режим форматирования/адресации, основанный только на первом символе операнда, если это возможно.

Разборные этикетки проще, и (в основном) раздельные. В принципе, каждая метка - это просто имя с адресом.

В качестве стороннего, если возможно, я, вероятно, следовал бы типичному формату ярлыка, заканчивающегося двоеточием («:») вместо точки с запятой («;»). Гораздо чаще точка с запятой будет отмечать начало комментария.