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

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

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

Набор инструкцийВ нашей маленькой ВМ есть небольшой набор инструкций для поддержки логических выражений.
  * PUSH кладет значение переменной в стек
  * AND выполняет логическое «И» между двумя операндами в стеке
  * OR выполняет логическое «ИЛИ» между двумя операндами в стеке
  * NOT выполняет логическое «НЕ» между одним операндом в стеке
Виртуальная машина понимает 1 как true и 0 как false.
  1. public class OpCode {
  2.     public static final int PUSH = 0;
  3.     public static final int AND = 1;
  4.     public static final int OR = 2;
  5.     public static final int NOT = 3;
  6. }
  7.  
  8. public class Bool {
  9.     public static final int FALSE = 0;
  10.     public static final int TRUE = 1;
  11. }
Сгенерированный «компилятором» код – это массив целых чисел Integer[], которые сгенерированы тем же способом, что и в настоящих компиляторах.
Вот реализация виртуальной машины:
  1. public final class BooleanVM {
  2.     private Stack<Integer> stack;
  3.  
  4.     public BooleanVM() {
  5.         this.stack = new Stack<>();
  6.     }
  7.  
  8.     public boolean start(Integer[] code) {
  9.         System.out.println("CODE: " + Arrays.toString(code));
  10.         int opcode;
  11.         int ip = 0;
  12.         while (ip < code.length) {
  13.             opcode = code[ip++];
  14.             switch (opcode) {
  15.                 case OpCode.PUSH:
  16.                     stack.push(code[ip++]);
  17.                     break;
  18.                 case OpCode.AND: {
  19.                     int b = stack.pop();
  20.                     stack.push(stack.pop() & b);
  21.                     break;
  22.                 }
  23.                 case OpCode.OR: {
  24.                     int b = stack.pop();
  25.                     stack.push(stack.pop() | b);
  26.                     break;
  27.                 }
  28.                 case OpCode.NOT:
  29.                     stack.push(~stack.pop() & 0x01);
  30.                     break;
  31.                 default:
  32.                     throw new RuntimeException("Invalid opcode " + code[ip -1]);
  33.             }
  34.         }
  35.         return stack.pop() == Bool.TRUE;
  36.     }
  37. }
Код внутри 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) и генерирование машинного кода (бинарного кода или байт-кода, как угодно).
  1. public interface BooleanVisitor<T> {
  2.     T visit(And a);
  3.  
  4.     T visit(Or o);
  5.  
  6.     T visit(Not n);
  7.  
  8.     T visit(True t);
  9.  
  10.     T visit(False f);
  11. }
Этот интерфейс обобщён, потому что иначе нельзя обойти дерево AST и выполнить какую-либо операцию.
Как написано в Википедии:
Посетитель – поведенческий шаблон проектирования, описывающий операцию, которая выполняется над объектами других классов. [...]Мне  нужно модифицировать интерфейс BooleanExpression соответственно:
  1. public interface BooleanExpression {
  2.     <T> T accept(BooleanVisitor<T> visitor);
  3. }
Теперь, для рекурсивного применения Посетителя в AST, используем шаблон проектирования Интерпретатор.

Фактическое компилирование
Обычно, для того, чтобы сгенерировать код для стековой ВМ, достаточно обойти AST в обратном порядке.
  1. public class BooleanCompiler implements BooleanVisitor<Void> {
  2.     private List<Integer> code;
  3.  
  4.     public BooleanCompiler() {
  5.         this.code = new LinkedList<>();
  6.     }
  7.  
  8.     @Override
  9.     public Void visit(And a) {
  10.         visit(a.getLeft());
  11.         visit(a.getRight());
  12.         code.add(OpCode.AND);
  13.         return null;
  14.     }
  15.  
  16.     @Override
  17.     public Void visit(Or o) {
  18.         visit(o.getLeft());
  19.         visit(o.getRight());
  20.         code.add(OpCode.OR);
  21.         return null;
  22.     }
  23.  
  24.     @Override
  25.     public Void visit(Not n) {
  26.         visit(n.getLeft());
  27.         code.add(OpCode.NOT);
  28.         return null;
  29.     }
  30.  
  31.     @Override
  32.     public Void visit(True t) {
  33.         code.add(OpCode.PUSH);
  34.         code.add(Bool.TRUE);
  35.         return null;
  36.     }
  37.  
  38.     @Override
  39.     public Void visit(False f) {
  40.         code.add(OpCode.PUSH);
  41.         code.add(Bool.FALSE);
  42.         return null;
  43.     }
  44.  
  45.     private Void visit(BooleanExpression b) {
  46.         b.accept(this);
  47.         return null;
  48.     }
  49.  
  50.     public Integer[] getCode() {
  51.         return code.toArray(new Integer[code.size()]);
  52.     }
  53. }
Так как нам нужно всего лишь обойти дерево и получить нужный код операции (опкод), результирующим типом класса Посетителя будет Void.
Если мы хотим вычислить выражение (как в этой статье), а не компилировать его, мы можем сделать следующее:
  1. public class BooleanEvaluator implements BooleanVisitor<Boolean>{
  2.     @Override
  3.     public Boolean visit(And a) {
  4.         return visit(a.getLeft()) && visit(a.getRight());
  5.     }
  6.  
  7.     @Override
  8.     public Boolean visit(Or o) {
  9.         return visit(o.getLeft()) || visit(o.getRight());
  10.     }
  11.  
  12.     @Override
  13.     public Boolean visit(Not n) {
  14.         return !visit(n.getLeft());
  15.     }
  16.  
  17.     @Override
  18.     public Boolean visit(True t) {
  19.         return true;
  20.     }
  21.  
  22.     @Override
  23.     public Boolean visit(False f) {
  24.         return false;
  25.     }
  26.  
  27.     private Boolean visit(BooleanExpression b) {
  28.         return b.accept(this);
  29.     }
  30. }
Заметьте, вычисление выражения всё ещё проводится в центрированном порядке обхода, как было описано в последней статье про логические выражения.
Генерирование ассемблерного кода для ВМ (парсинг кода не поддерживается в этом проекте) тоже очень простой:
  1. public class ToAssembly implements BooleanVisitor<Void> {
  2.     private StringBuilder sb = new StringBuilder();
  3.  
  4.     @Override
  5.     public Void visit(And a) {
  6.         visit(a.getLeft());
  7.         visit(a.getRight());
  8.         sb.append("AND").append("\n");
  9.         return null;
  10.     }
  11.  
  12.     @Override
  13.     public Void visit(Or o) {
  14.         visit(o.getLeft());
  15.         visit(o.getRight());
  16.         sb.append("OR").append("\n");
  17.         return null;
  18.     }
  19.  
  20.     @Override
  21.     public Void visit(Not n) {
  22.         visit(n.getLeft());
  23.         sb.append("NOT").append("\n");
  24.         return null;
  25.     }
  26.  
  27.     @Override
  28.     public Void visit(True t) {
  29.         sb.append("PUSH")
  30.                 .append(' ')
  31.                 .append("TRUE")
  32.                 .append("\n");
  33.         return null;
  34.     }
  35.  
  36.     @Override
  37.     public Void visit(False f) {
  38.         sb.append("PUSH")
  39.                 .append(' ')
  40.                 .append("FALSE")
  41.                 .append("\n");
  42.         return null;
  43.     }
  44.  
  45.     private Void visit(BooleanExpression b) {
  46.         b.accept(this);
  47.         return null;
  48.     }
  49.  
  50.     public String getASM() {
  51.         return sb.toString();
  52.     }
  53. }
Давайте для примера рассмотрим следующее выражение:

  1. (true & ((true | false) & !(true & false)))

Абстрактное синтаксическое дерево будет выглядеть так:
  ast-boolean-expression.png

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

  1. PUSH TRUE
  2. PUSH TRUE
  3. PUSH FALSE
  4. OR
  5. PUSH TRUE
  6. PUSH FALSE
  7. AND
  8. NOT
  9. AND
  10. AND


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