Распознавание имен

Цель: Изучение основ работы ассемблера, создание простой программы генерации кода виртуального процессора.

Краткие теоретические сведения

В общем случае предложения языка Ассемблера состоят из следующих компонент:

  • метка или имя;
  • мнемоника; (имя инструкции)
  • операнды;
  • комментарии.

    Метка или имя является необязательным компонентом. Не во всех языках Ассемблеров эти понятия различаются. Если они различаются (например, MASM), то метка - точка программы, на которую передается управление, следовательно, метка стоит в предложении, содержащем команду; имя - имя переменной программы, ячейки памяти, следовательно, имя стоит в предложении, содержащем псевдокоманду резервирования памяти или определения константы. В некоторых случаях метка и имя могут отличаться даже синтаксически, так, в MASM/TASM после метки ставится двоеточие, а после имени - нет.

    Постановка задачи

    Написать программу распознавания имен ассемблерных команд. Входной файл содержит мнемоники команд и имена (по одному в строке). Выходной файл – коды операций и номера имен.

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

    Для хранения имен необходимо использовать перемешанные таблицы (хеширование). Для исследуемого имени вычисляется ключ – функция перемешивания, например:

    Hash = hash_function(name) % HashSize;

    где HashSize – число «букетов». Значение Hash служит для входа в таблицу букетов:

    int HashHeads [HashSize];

    которая хранит начало связного списка имен для каждого букета. Сами связные списки для всех букетов с информацией об именах хранятся в массивах:

    int HashName[MAXNAMESNUM]; int HashData[MAXNAMESNUM]; int HashNext[MAXNAMESNUM];

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

    char NamesPool[MAXNAMESPOOLSIZE];

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

    Например, для входного файла

    ADD QWERTY MUL DIV MYLABEL SUB LABEL3 XOR AND MYLABEL OR LDD QWERTY

    Результат мог бы выглядеть так

    ADD keyword, opcode=6 QWERTY new name, hash=24 MUL keyword, opcode=2 DIV keyword, opcode=18 MYLABEL new name, hash=13 SUB keyword, opcode=16 LABEL3 new name, hash=123 XOR keyword, opcode=26 AND keyword, opcode=11 MYLABEL old name, hash=13 OR keyword, opcode=31 LDD keyword, opcode=12 QWERTY old name, hash=24