воскресенье, 9 декабря 2012 г.

Пишем компилятор ассемблера на Java

Последние две лабораторные работы по системному программированию были посвящены разработке анализатора и компилятора для языка Assembler. Тема интересная, а поскольку я ничего подобного никогда в жизни не делал, то с удовольствием взялся за дело. Писал, конечно же на Java, так как понимал, что придётся много работать со строками. В прочем, обо всём по порядку.

Сперва нужно было создать анализаторы: лексический и синтаксический.
Первый из текстового исходника делал таблицу, где каждой директиве ассемблера ставился в соответствие свой код. Например: символ запятой - 5, add - 10, mul - 11, регистр 2 байт - 201, переменная 2 байт - 502, и т.д. В итоге из строк:
add dx, num_word
mul bx
должна получиться таблица:
10 201 5 502
11 201
Что может быть проще?

Синтаксический анализатор должен в этой таблице кодов проверить правильность их последовательности. Например, 10 5 201 - неправильно, так как это соответствует команде add, ax. Также нужно проверять, какой тип переменной использует та или иная команда, например, нужно учитывать, что к регистру размером 1 байт нельзя добавить двухбайтовую переменную.

Лексический анализатор

Итак, пора начинать. Я создал класс LexicalAnalyzer, в котором будет происходить конвертирование директив в коды. Сначала нужно разбить весь исходник на строки, так как в ассемблере в каждой строке только одна команда. Строка:
String[] lines = text.split(System.lineSeparator());
прекрасно с этим справляется. Далее, нужно каждую строку разбить на части так, чтобы выделить основные директивы. Можно разбить по пробелу, но тогда мы не сможем выделить такую запись, как "add ax,bx". Поэтому пришлось писать функцию разбиения и по пробелу и по символу запятой, причём так, чтобы запятая входила как отдельный элемент.
/**
 * Разбить строку на подстроки с учётом запятых.
 * @param text текст.
 * @return массив строк.
 */
public static  String[] split(String text) {
    ArrayList parts = new ArrayList<>();
    int length = text.length();
    StringBuilder sb = new StringBuilder();
    for (int ch = 0; ch < length; ch++) {
        int i = text.charAt(ch);
        if (i == ' ') {
            if (sb.length() > 0) {
                parts.add(sb.toString().trim());
                sb.setLength(0);
            }
        } else if (i == ',') {
            if (sb.length() > 0) {
                parts.add(sb.toString().trim());
                parts.add(",");
                sb.setLength(0);
            }
        } else {
            sb.append((char) i);
        }
    }
    if (sb.length() > 0) {
        parts.add(sb.toString().trim());
    }
    String[] m = new String[parts.size()];
    m = parts.toArray(m);
    return m;
}
Вот теперь из строки "add ax,bx" мы честно получим массив { "add", "ax", ",", "bx" }. Теперь можно создать таблицу перекодировки текст->идентификатор и обычным проходом по всем строкам и директивам получить нужную нам таблицу. Но это было бы слишком просто и без ООП, поэтому такой вариант не годится. Вместо массивов создадим базовый класс Directive:
/**
 * Базовый класс директив.
 * @author aNNiMON
 */
public abstract class Directive {
 
    protected String name;
    protected int id;
 
    protected Directive(String name, int id) {
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return id;
    }
 
    /**
     * Проверка на соответствие директивы тексту.
     * @param text строка директивы, которую нужно проверить.
     * @return результат совпадения.
     */
    public boolean isDirective(String text) {
        return text.equalsIgnoreCase(name);
    }
}
и на каждую простую директиву создадим свой класс:
public class Add extends Directive {
    public Add() {
        super("add", ID.ADD);
    }
}

public class Mul extends Directive {
    public Mul() {
        super("mul", ID.MUL);
    }
}
Зачем это нужно? Ну во-первых, так будет легче добавлять остальные директивы, а во-вторых, дальше ведь мы будем добавлять синтаксический анализатор, вот и создадим в этих классах методы, которые и будут выполнять проверку. Таким образом всё будет по своим местам и мы точно будем знать, что если анализатор пропустил строку "add, ax", то нужно заглянуть в класс Add, а не в какой-нибудь другой.
Вот так, наследуясь от класса Directive я создал множество других классов, которые были у меня в задании. Некоторые классы пришлось расширить, например Register:
@Override
public boolean isDirective(String text) {
    String[] names = getRegisterNames();
    for (int i = 0; i < names.length; i++) {
        if (text.equalsIgnoreCase(names[i])) {
            return true;
        }
    }
    return false;
}

protected abstract String[] getRegisterNames();
Теперь мы можем создать подкласс однобайтных и двухбайтных регистров:
public class ByteRegister extends Register {
 
    public ByteRegister() {
        super();
    }

    @Override
    public int getId() {
        return ID.REGISTER_BYTE;
    }

    @Override
    protected String[] getRegisterNames() {
        return new String[] {
            "ah", "al",
            "bh", "bl",
            "ch", "cl",
            "dh", "dl",
        };
    }
}
здорово, не так ли?

Прежде чем приступать к перекодировке, нужно еще создать пару классов, для удобства.
public class LexicLine {
    int lineNumber;
    int[] line;

    public LexicLine(int lineNumber, int[] line) {
        this.lineNumber = lineNumber;
        this.line = line;
    }
}


public class LexicTable {
 
    private ArrayList lexicLines;
 
    public LexicTable() {
        lexicLines = new ArrayList<>();
    }
 
    public void addLexicLine(int lineNumber, int[] line) {
        lexicLines.add(new LexicLine(lineNumber, line));
    }
 
    public int getSize() {
        return lexicLines.size();
    }
 
    public LexicLine getLexicAt(int pos) {
        return lexicLines.get(pos);
    }
 
    public void updateLexicAt(int pos, LexicLine line) {
        lexicLines.set(pos, line);
    }

}
LexicLine хранит номер строки и набор идентификаторов для одной строки.
LexicTable хранит последовательность таких строк. Всё просто.

Вот, наконец-то мы подошли к самому интересному - перекодирование. Я не буду здесь показывать код прохода по строкам, это обычный цикл for, лучше покажу, как пришедшей команде "add" ставится в соответствие код 10.
private static final Directive[] DIRECTIVES = {
    new Comma(),
    new DB(), new DW(),
    new InfinityValue(), new ByteValue(), new WordValue(),
    new Add(), new Mul(), new Push(), new Pop(), new Idiv(),
    new ByteRegister(), new WordRegister(),
    new Variable()
};

/**
 * Конвертировать директиву в её идентификатор.
 * @param text директива (dw, push, 0 и т.д.)
 * @return идентификатор директивы.
 */
public static int convert(String text) {
    for (int i = 0; i < DIRECTIVES.length; i++) {
        if (DIRECTIVES[i].isDirective(text)) {
            return DIRECTIVES[i].getId();
        }
    }
    return -1;
}
Итак, мы имеем массив директив. В метод convert поступила строка "add", что же делается дальше? А дальше из массива берётся первый класс Comma:
public class Comma extends Directive {
    public Comma() {
        super(",", ID.COMMA);
    }
}
Вызывается конструктор базового класса Directive:
protected Directive(String name, int id) {
    this.name = name;
    this.id = id;
}
которому передаются переменные name = "," и id = ID.COMMA (то есть 5). Далее вызывается метод DIRECTIVES[i].isDirective(text):
public boolean isDirective(String text) {
    return text.equalsIgnoreCase(name);
}
Так как text у нас равен "add", а name - ",", то метод возвратит false и далее, по циклу увеличится i. В следующем проходе вызовется метод класса DB, потом DW и так далее, пока не достигнем класса Add, где наконец-то метод isDirective вернёт true. Возьмём из этого класса id методом getId() и возвратим его. Вот такой принцип.

Синтаксический анализ

Для синтаксического анализа понадобится таблица, генерируемая лексическим анализатором. Поэтому создав класс SyntaxAnalyzer, нужно определить конструктор с параметром LexicTable lexicTable. Синтаксический анализатор будет брать по одному элементу из этой таблицы и сравнивать последовательности идентификаторов команд. 
Создадим интерфейс ISyntaxChecker
/**
 * Проверка синтаксиса.
 * @author aNNiMON
 */
public interface ISyntaxChecker {
    
    /**
     * Проверить синтаксис.
     * @param lineNumber номер строки.
     * @param ids последовательность идентификаторов в строке.
     * @return правильность последовательности директив.
     * @throws ExceptionWithLineNumber 
     */
    public boolean check(int lineNumber, int[] ids) throws ExceptionWithLineNumber;
    
}
Далее, добавим его реализацию в нужные нам классы. Возьмём класс Pop, он легче для понимания:
public class Pop extends Directive implements ISyntaxChecker {

    public Pop() {
        super("pop", ID.POP);
    }
    
    @Override
    public boolean check(int lineNumber, int[] ids) throws ExceptionWithLineNumber {
        if (ids[0] != getId()) return false;
        
        if (ids.length < 2) throw new FewArgumentsException(lineNumber, 1);
        for (int i = 1; i < ids.length; i++) {
            if ( (ids[i] != ID.REGISTER_WORD) &&
                 (ids[i] != ID.VAR_WORD)) {
                throw new WrongArgumentException(lineNumber);
            }
        }
        return true;
    }
}
В методе check сначала проверяем, совпадает ли первый идентификатор таблицы с идентификатором нашего класса. Это сделано для того же обхода, что и в случае с лексическим анализатором. Затем проверяем количество идентификаторов в строке, их должно быть как минимум два (сама команда pop и операнд). Так как в ассемблере можно писать pop ax bx cx dx и т.д., то в цикле, начиная с первого операнда, проверяем их тип. Он должен быть строго равен двум байтам. Если хотя бы один операнд не двухбайтный, либо встретилось вообще другое слово, то выбрасываем исключение, поясняющую ошибку и выводящую номер строки, в которой произошла ошибка. 
Сам класс SyntaxAnalyzer, выглядит так:
/**
 * Синтаксический анализатор.
 * @author aNNiMON
 */
public class SyntaxAnalyzer {
    
    private static final ISyntaxChecker[] DIRECTIVES = {
        new Add(), new Mul(), new Push(), new Pop(), new Idiv(),
        new Variable()
    };
    
    private LexicTable lexicTable;

    public SyntaxAnalyzer(LexicTable lexicTable) {
        this.lexicTable = lexicTable;
    }
    
    public void analyze() throws ExceptionWithLineNumber {
        for (int i = 0; i < lexicTable.getSize(); i++) {
            LexicLine line = lexicTable.getLexicAt(i);
            analyzeLine(line.lineNumber, line.line);
        }
    }
    
    private void analyzeLine(int lineNumber, int[] lexic) throws ExceptionWithLineNumber {
        for (int i = 0; i < DIRECTIVES.length; i++) {
            if (DIRECTIVES[i].check(lineNumber, lexic)) {
                return;
            }
        }
    }
    
}

Генерируем листинг объектного кода

Последним штрихом нашей работы, будет создание листинга объектного кода, чтобы наглядно видеть, в какой байт преобразовалась та или иная команда. Это аналог параметра /l компилятора tasm.
public interface IListingGenerator {
    
    /**
     * Сгенерировать строку листинга.
     * @param lineNumber номер строки.
     * @param ids последовательность идентификаторов в строке.
     * @param strs строковая последовательность идентификаторов.
     * @param var таблица переменных
     * @return строка листинга.
     */
    public String generate(int lineNumber, int[] ids, String[] strs, VarTable var);
}
Далее, начинаем кропотливо работать с документацией (которой нет :), таблицами и материалами сайтов. Вот, к примеру, реализация интерфейса для класса Push:
@Override
public String generate(int lineNumber, int[] ids, String[] strs, VarTable vars) {
    if (ids[0] != getId()) return "";
    
    StringBuilder sb = new StringBuilder();

    if (ids[1] == ID.REGISTER_WORD) {
        byte segmentID = ListingGenerateHelper.getSegmentRegisterCode(strs[1]);
        if (segmentID != -1) {
            //seg (только cs, ds, ss, es)  00seg110
            byte val = (byte) (0b00_000_110 | (segmentID << 3));
            sb.append(ListingGenerateHelper.toHexString(val));
        } else {
            // reg16/32 01010reg
            byte regID = ListingGenerateHelper.getRegisterCode(strs[1]);
            byte val = (byte) (0b01010_000 | regID);
            sb.append(ListingGenerateHelper.toHexString(val));
        }
    } else if (ids[1] == ID.VAR_WORD) {
        // r/m16/32 11111111 | mod110r/m
        short offset = vars.getAddressOfVariable(strs[1]);
        
        sb.append(ListingGenerateHelper.toHexString(0b11111111))
                .append(' ')
          .append(ListingGenerateHelper.toHexString(0b00_110_110))
                .append(' ')
          .append(ListingGenerateHelper.toLittleEndianString(offset));
    }

    return sb.toString();
}
На первый взгляд кажется сложным, но привыкнуть можно.
Вот так выглядит работа программы.

Исходники берём здесь

Комментариев нет:

Отправить комментарий