Компилирование булевых выражений

16.11.2015 / 01:21 от Senderman

Java перевод, парсер

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

Набор инструкцийВ нашей маленькой ВМ есть небольшой набор инструкций для поддержки логических выражений.
* PUSH кладет значение переменной в стек
* AND выполняет логическое «И» между двумя операндами в стеке
* OR выполняет логическое «ИЛИ» между двумя операндами в стеке
* NOT выполняет логическое «НЕ» между одним операндом в стеке
Виртуальная машина понимает 1 как true и 0 как false.

[копировать] [скачать]
public class OpCode {
    public static final int PUSH = 0;
    public static final int AND = 1;
    public static final int OR = 2;
    public static final int NOT = 3;
}
 
public class Bool {
    public static final int FALSE = 0;
    public static final int TRUE = 1;
}

Сгенерированный «компилятором» код – это массив целых чисел Integer[], которые сгенерированы тем же способом, что и в настоящих компиляторах.
Вот реализация виртуальной машины:

[копировать] [скачать]
public final class BooleanVM {
    private Stack<Integer> stack;
 
    public BooleanVM() {
        this.stack = new Stack<>();
    }
 
    public boolean start(Integer[] code) {
        System.out.println("CODE: " + Arrays.toString(code));
        int opcode;
        int ip = 0;
        while (ip < code.length) {
            opcode = code[ip++];
            switch (opcode) {
                case OpCode.PUSH:
                    stack.push(code[ip++]);
                    break;
                case OpCode.AND: {
                    int b = stack.pop();
                    stack.push(stack.pop() & b);
                    break;
                }
                case OpCode.OR: {
                    int b = stack.pop();
                    stack.push(stack.pop() | b);
                    break;
                }
                case OpCode.NOT:
                    stack.push(~stack.pop() & 0x01);
                    break;
                default:
                    throw new RuntimeException("Invalid opcode " + code[ip -1]);
            }
        }
        return stack.pop() == Bool.TRUE;
    }
}

Код внутри boolean start(...) описывает цикл fetch-decode-execute (выборка-декодирование-выполнение), который выполняет каждый настоящий процессор.
За этап выборки отвечает код opcode = code[ip++]; затем следует декодирование в операторе switch, а выполнение проводится в теле веток case.
После вычисления компилируемого выражения, результат сохраняется на вершине стека, откуда мы можем получить результат всего вычисляемого выражения.
Поскольку виртуальная машина использует целые числа, логическая операция должна быть выполнена с использованием побитовых операций (т.к. наша архитектура не знает, что такое boolean).
Операции AND и OR можно выполнять, используя побитовые & и | соответственно.
Так как мы используем Integer в Java, операция NOT на числе 0 может привести к неожиданным результатам.
Integer в JVM занимает 32 бита, и, выполнив ~0, мы получим -1, а не 1.
0 в двоичном виде представляется как 00...00 (32 нуля), применяя оператор инверсии ~, мы получаем 11...11 (32 единицы), то есть -1 (Java использует дополнительный код).
Применив к результату & 0x01, мы будем уверены, что получим только последний бит.

Компиляция
Что такое компиляция? Упрощённо (ну уж очень-очень упрощённо), это перевод одного чётко определённого способа описания операций в другой.
Как вы успели заметить, архитектура процессора обычно не имеет представления о том, что такое boolean , что есть цикл while, что такое класс, и т.д.
Компилятор переводит высокоуровневый язык в низкоуровневый.
В нашем случае, «высокоуровневый язык» это логические выражения, а «низкоуровневый» – набор инструкций, описанный выше.
Начнём с исходников, приведённых в предыдущей статье про вычисление булевых выражений.

Компиляция посещениемРаспространённая техника реализации компилятора – это посещение абстрактного синтаксического дерева (AST) и генерирование машинного кода (бинарного кода или байт-кода, как угодно).

[копировать] [скачать]
public interface BooleanVisitor<T> {
    T visit(And a);
 
    T visit(Or o);
 
    T visit(Not n);
 
    T visit(True t);
 
    T visit(False f);
}

Этот интерфейс обобщён, потому что иначе нельзя обойти дерево AST и выполнить какую-либо операцию.
Как написано в Википедии:
Посетитель – поведенческий шаблон проектирования, описывающий операцию, которая выполняется над объектами других классов. [...]Мне нужно модифицировать интерфейс BooleanExpression соответственно:

public interface BooleanExpression {
    <T> T accept(BooleanVisitor<T> visitor);
}

Теперь, для рекурсивного применения Посетителя в AST, используем шаблон проектирования Интерпретатор.

Фактическое компилирование
Обычно, для того, чтобы сгенерировать код для стековой ВМ, достаточно обойти AST в обратном порядке.

[копировать] [скачать]
public class BooleanCompiler implements BooleanVisitor<Void> {
    private List<Integer> code;
 
    public BooleanCompiler() {
        this.code = new LinkedList<>();
    }
 
    @Override
    public Void visit(And a) {
        visit(a.getLeft());
        visit(a.getRight());
        code.add(OpCode.AND);
        return null;
    }
 
    @Override
    public Void visit(Or o) {
        visit(o.getLeft());
        visit(o.getRight());
        code.add(OpCode.OR);
        return null;
    }
 
    @Override
    public Void visit(Not n) {
        visit(n.getLeft());
        code.add(OpCode.NOT);
        return null;
    }
 
    @Override
    public Void visit(True t) {
        code.add(OpCode.PUSH);
        code.add(Bool.TRUE);
        return null;
    }
 
    @Override
    public Void visit(False f) {
        code.add(OpCode.PUSH);
        code.add(Bool.FALSE);
        return null;
    }
 
    private Void visit(BooleanExpression b) {
        b.accept(this);
        return null;
    }
 
    public Integer[] getCode() {
        return code.toArray(new Integer[code.size()]);
    }
}

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

[копировать] [скачать]
public class BooleanEvaluator implements BooleanVisitor<Boolean>{
    @Override
    public Boolean visit(And a) {
        return visit(a.getLeft()) && visit(a.getRight());
    }
 
    @Override
    public Boolean visit(Or o) {
        return visit(o.getLeft()) || visit(o.getRight());
    }
 
    @Override
    public Boolean visit(Not n) {
        return !visit(n.getLeft());
    }
 
    @Override
    public Boolean visit(True t) {
        return true;
    }
 
    @Override
    public Boolean visit(False f) {
        return false;
    }
 
    private Boolean visit(BooleanExpression b) {
        return b.accept(this);
    }
}

Заметьте, вычисление выражения всё ещё проводится в центрированном порядке обхода, как было описано в последней статье про логические выражения.
Генерирование ассемблерного кода для ВМ (парсинг кода не поддерживается в этом проекте) тоже очень простой:

[копировать] [скачать]
public class ToAssembly implements BooleanVisitor<Void> {
    private StringBuilder sb = new StringBuilder();
 
    @Override
    public Void visit(And a) {
        visit(a.getLeft());
        visit(a.getRight());
        sb.append("AND").append("\n");
        return null;
    }
 
    @Override
    public Void visit(Or o) {
        visit(o.getLeft());
        visit(o.getRight());
        sb.append("OR").append("\n");
        return null;
    }
 
    @Override
    public Void visit(Not n) {
        visit(n.getLeft());
        sb.append("NOT").append("\n");
        return null;
    }
 
    @Override
    public Void visit(True t) {
        sb.append("PUSH")
                .append(' ')
                .append("TRUE")
                .append("\n");
        return null;
    }
 
    @Override
    public Void visit(False f) {
        sb.append("PUSH")
                .append(' ')
                .append("FALSE")
                .append("\n");
        return null;
    }
 
    private Void visit(BooleanExpression b) {
        b.accept(this);
        return null;
    }
 
    public String getASM() {
        return sb.toString();
    }
}

Давайте для примера рассмотрим следующее выражение:

(true & ((true | false) & !(true & false)))

Абстрактное синтаксическое дерево будет выглядеть так:

И теперь мы можем в любом порядке применить один из определённых ранее классов Посетителя.

PUSH TRUE
PUSH TRUE
PUSH FALSE
OR
PUSH TRUE
PUSH FALSE
AND
NOT
AND
AND

Благодарю aNNiMON за помощь в переводе и коррекции.
Исходный код проекта: GitHub.
Автор оригинала: Nicola Malizia.