Brainfuck для компилятора сборки x86

После моего переводчика Brainfuck, написанного на сборке x86 , я решил, что пришло время перейти к следующему шагу, написав компилятор Brainfuck на Java, который генерирует сборку x86 и компилирует ее для исполняемого файла.

В настоящее время он поддерживает только Windows и по-прежнему использует NASM и GCC в качестве зависимостей для преобразования кода сборки x86 в реальные исполняемые файлы. Это не идеально, но это также самый простой способ.

В настоящее время компилятор полностью не оптимизирован и будет очень рад повторять указатели увеличения /уменьшения и /или памяти.

На этот раз у меня нет видео, но мой интерпретатор выполнил файл Mandelbrot BF за 60 секунд, и исполняемый файл, полученный от этого компилятора, выполняет его через 4 секунды.

Мой код намеревается следовать общей схеме компилятора, состоящей из следующих этапов:

  • Чтение файла исходного кода
  • Лексический анализатор, который переводит исходный файл в поток токенов
  • Анализатор синтаксиса, который строит абстрактное дерево синтаксиса (AST) из потока токенов и проверяет простые вещи, например, если петли соответствуют
  • Генератор промежуточного кода, который берет исходный АСТ и преобразует его в промежуточный АСТ
  • Генератор целевого кода, который принимает промежуточный АСТ и преобразует его в целевой АСТ
  • Писатель целевого кода, который принимает целевой АСТ и записывает фактический код сборки x86 в качестве вывода.

Есть несколько примечательных примечаний:

  • Нет семантического анализатора. На более полном языке такая фаза будет проверять, происходит ли назначение между совместимыми типами и т. Д. Так как Brainfuck недостаточно продвинут, нет необходимости в этой фазе.
  • Промежуточный AST напрямую не используется прямо сейчас, на более поздней стадии все оптимизации будут выполняться на этом промежуточном АСТ. Подумайте о замене +++ на псевдокод addmemorycell(3), <<< на addpointer(-3), [-] по setmemorycell(0).

Теперь на код, давайте начнем с интерфейса AST и Expression:

public interface Expression {
}

Каждый фрагмент кода в моей программе является подклассом Expression, большинство подклассов не определяют никаких полей или методов и равны сами по себе, единственными исключениями являются IntegerExpression, StringExpression и RegisterExpression, они имеют Integer, String и Register как поле соответственно.

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

Пакет expression.source содержит:

  • DecrementExpression
  • IncrementExpression
  • InputExpression
  • LoopExpression
  • OutputExpression
  • PoinerLeftExpression
  • PointerRightExpression

Это действительно только токены Brainfuck.

Пакет expression.intermediate содержит:

  • MemoryInputExpression
  • MemoryLoopExpression
  • MemoryOutputExpression
  • MemoryPointerChangeExpression
  • MemoryValueChangeExpression

Это промежуточные представления токенов Brainfuck, чтобы облегчить их рассуждение. Вы можете видеть, что Increment /Decrement и PointerLeft /PointerRight объединены.

Тогда есть пакет expression.target:

  • AddExpression
  • BssSectionExpression
  • значение вложенного ВыраженияCall
  • DataSectionExpression
  • DefineByteExpression
  • DefineLabelExpression
  • DwordExpression
  • ExternExpression
  • ВыражениеФункции
  • GlobalExpression
  • IdentifierExpression
  • JmpExpression
  • JmpShortExpression
  • JnzExpression
  • JzExpression
  • LabelExpression
  • MemoryAddressExpression
  • MovExpression
  • OperandExpression
  • PushExpression
  • Регистрация
  • RegisterExpression
  • ReserveDoubleExpression
  • RetExpression
  • TestExpression
  • TextSectionExpression
  • ValueExpression
  • ValueListExpression

Они содержат довольно много выражений Assembly, и, на мой взгляд, их довольно много.

Чтобы вы почувствовали, как они выглядят, я возьму RegisterExpression:

public class RegisterExpression implements Expression {
    private final Register register;

    public RegisterExpression(final Register register) {
        this.register = register;
    }

    public Register getRegister() {
        return register;
    }

    @Override
    public String toString() {
        return "Register(" + register + ")";
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        RegisterExpression that = (RegisterExpression)obj;
        return register == that.register;
    }

    @Override
    public int hashCode() {
        return Objects.hash(register);
    }
}

И Register:

public enum Register {
    EAX,
    AX,
    AH,
    AL,
    EBX,
    BX,
    BH,
    BL,
    ECX,
    CX,
    CH,
    CL,
    EDX,
    DX,
    DH,
    DL,
    ESI,
    SI,
    EDI,
    DI,
    EBP,
    BP,
    ESP,
    SP;
}

С пояснениями объясняется, что настало время показать структуру AST.

У нас есть класс AST:

public class AST {
    private final ASTNode root;

    public AST(final ASTNode root) {
        this.root = root;
    }

    public ASTNode getRoot() {
        return root;
    }

    public Stream<String> prettyPrintStream() {
        return root.prettyPrintStream("", false);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        AST ast = (AST)obj;
        return Objects.equals(root, ast.root);
    }

    @Override
    public int hashCode() {
        return Objects.hash(root);
    }
}

И затем большой класс ASTNode:

public class ASTNode {
    private final Expression expression;

    private ASTNode parent;

    private final List<ASTNode> children = new ArrayList<>();

    public ASTNode(final Expression expression) {
        this.expression = expression;
    }

    public static ASTNode newWithChild(final Expression expression, final ASTNode node) {
        return newWithChildren(expression, Arrays.asList(node));
    }

    public static ASTNode newWithChildren(final Expression expression, final List<ASTNode> nodes) {
        ASTNode newNode = new ASTNode(expression);
        nodes.forEach(newNode::addChild);
        return newNode;
    }

    public static ASTNode newWithMappedChildren(final Expression expression, final List<ASTNode> nodes, final UnaryOperator<ASTNode> mapper) {
        ASTNode newNode = new ASTNode(expression);
        nodes.stream().map(mapper).forEach(newNode::addChild);
        return newNode;
    }

    public Expression getExpression() {
        return expression;
    }

    public <T extends Expression> T getExpression(final Class<T> clazz) {
        if (clazz.isInstance(expression)) {
            return clazz.cast(expression);
        }
        throw new IllegalStateException("Expression " + expression + " cannot be cast to class " + clazz);
    }

    public ASTNode getParent() {
        return parent;
    }

    public void addChild(ASTNode node) {
        children.add(node);
        node.parent = this;
    }

    public List<ASTNode> getChildren() {
        return children;
    }

    public ASTNode getChild(final int index, final Class<? extends Expression> clazz) {
        ASTNode node = children.get(index);
        Expression childExpression = node.getExpression();
        if (!clazz.isInstance(childExpression)) {
            throw new IllegalStateException("Expected child " + index + " to be of class " + clazz + ", but it is " + childExpression);
        }
        return node;
    }

    public <T extends Expression> T getChildExpression(final int index, final Class<T> clazz) {
        ASTNode node = children.get(index);
        return node.getExpression(clazz);
    }

    protected Stream<String> prettyPrintStream(String prefix, boolean tail) {
        return Stream.concat(
            Stream.of(prefix + (tail ? "└── " : "├── ") + expression),
            IntStream.range(0, children.size())
                .boxed()
                .flatMap(i -> children.get(i).prettyPrintStream(prefix + (tail ? "    " : "│   "), (i == children.size() - 1)))
        );
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        ASTNode node = (ASTNode)obj;
        return Objects.equals(expression, node.expression) &&
            Objects.equals(children, node.children);
    }

    @Override
    public int hashCode() {
        return Objects.hash(expression, children);
    }
}

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

public class SourceFile {
    private final Path path;

    public SourceFile(final Path path) {
        this.path = path;
    }

    public IntStream getCharacterStream() throws IOException {
        return Files.lines(path, StandardCharsets.UTF_8)
            .flatMapToInt(CharSequence::chars);
    }
}

Далее следуетЛексический анализатор:

public class LexicalAnalyzer {
    private final SourceFile sourceFile;

    public LexicalAnalyzer(final SourceFile sourceFile) {
        this.sourceFile = sourceFile;
    }

    public Stream<Token> getTokens() throws IOException {
        return sourceFile.getCharacterStream()
            .mapToObj(character -> Token.forCharacter((char)character))
            .filter(token -> token != null);
    }
}

Что использует класс Token:

public enum Token {
    POINTER_RIGHT('>'),
    POINTER_LEFT('<'),
    INCREMENT('+'),
    DECREMENT('-'),
    OUTPUT('.'),
    INPUT(','),
    JUMP_PAST('['),
    JUMP_BACK(']');

    private static final Map<Character, Token> CHARACTER_TOKEN_MAP = Arrays.stream(Token.values())
        .collect(Collectors.toMap(Token::getCharacter, i -> i));

    public static Token forCharacter(final char character) {
        return CHARACTER_TOKEN_MAP.get(character);
    }

    private final char character;

    Token(final char character) {
        this.character = character;
    }

    public char getCharacter() {
        return character;
    }
}

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

public class SyntaxAnalyzer {
    public AST getAST(final Stream<Token> tokens) {
        ASTNode rootNode = new ASTNode(new RootExpression());
        AST ast = new AST(rootNode);
        ASTNode currentNode = rootNode;

        int loopCounter = 0;

        for (Token token : (Iterable<Token>)tokens::iterator) {
            ASTNode newNode = null;
            ASTNode nextNode = null;

            switch (token) {
                case POINTER_RIGHT:
                    newNode = new ASTNode(new PointerRightExpression());
                    break;
                case POINTER_LEFT:
                    newNode = new ASTNode(new PointerLeftExpression());
                    break;
                case INCREMENT:
                    newNode = new ASTNode(new IncrementExpression());
                    break;
                case DECREMENT:
                    newNode = new ASTNode(new DecrementExpression());
                    break;
                case OUTPUT:
                    newNode = new ASTNode(new OutputExpression());
                    break;
                case INPUT:
                    newNode = new ASTNode(new InputExpression());
                    break;
                case JUMP_PAST:
                    loopCounter++;
                    newNode = new ASTNode(new LoopExpression());
                    nextNode = newNode;
                    break;
                case JUMP_BACK:
                    if (loopCounter == 0) {
                        throw new InvalidSyntaxException("A ] has been found without a matching opening [.");
                    }
                    loopCounter--;
                    nextNode = currentNode.getParent();
                    break;
            }

            if (newNode != null) {
                currentNode.addChild(newNode);
            }

            if (nextNode != null) {
                currentNode = nextNode;
            }
        }

        if (loopCounter > 0) {
            throw new InvalidSyntaxException("A ] is missing.");
        }

        return ast;
    }
}

Что использует этот простой класс InvalidSyntaxException:

public class InvalidSyntaxException extends RuntimeException {
    public InvalidSyntaxException(String message) {
        super(message);
    }
}

Если вы сделали это так далеко в вопросе, остановитесь на минутку и посмотрите на следующую программу Hello World, которую я использовал для тестирования по всему моему коду:

>++++++++[-<+++++++++>]<.>>+>-[+]++>++>+++[>[->+++<<+++>]<<]
>-----.>->+++..+++.>-.<<+[>[+>+]>>]<--------------.>>.+++.------.--------.>+.>+.

Я уверен, что все эксперты Brainfuck сразу поймут, как это работает, если вы этого не сделаете, это не большая проблема, потому что изначально я тоже не был уверен. Единственное, что я знаю, это не самая оптимальная программа, так как в какой-то момент есть последовательность -[+]++, означающая, что ячейка памяти уменьшается, а затем увеличивается до нулевой ( мы используем 8-битные ячейки памяти, поэтому 255 переполняется в 0), а затем снова увеличиваем в два раза.

Поместите этот код Brainfuck в наш синтаксический анализатор, получим следующий AST (который получен методом prettyPrintStream() в классе AST:

├── Root
│   ├── PointerRight
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Loop
│   │   ├── Decrement
│   │   ├── PointerLeft
│   │   ├── Increment
│   │   ├── Increment
│   │   ├── Increment
│   │   ├── Increment
│   │   ├── Increment
│   │   ├── Increment
│   │   ├── Increment
│   │   ├── Increment
│   │   ├── Increment
│   │   └── PointerRight
│   ├── PointerLeft
│   ├── Output
│   ├── PointerRight
│   ├── PointerRight
│   ├── Increment
│   ├── PointerRight
│   ├── Decrement
│   ├── Loop
│   │   └── Increment
│   ├── Increment
│   ├── Increment
│   ├── PointerRight
│   ├── Increment
│   ├── Increment
│   ├── PointerRight
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Loop
│   │   ├── PointerRight
│   │   ├── Loop
│   │   │   ├── Decrement
│   │   │   ├── PointerRight
│   │   │   ├── Increment
│   │   │   ├── Increment
│   │   │   ├── Increment
│   │   │   ├── PointerLeft
│   │   │   ├── PointerLeft
│   │   │   ├── Increment
│   │   │   ├── Increment
│   │   │   ├── Increment
│   │   │   └── PointerRight
│   │   ├── PointerLeft
│   │   └── PointerLeft
│   ├── PointerRight
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Output
│   ├── PointerRight
│   ├── Decrement
│   ├── PointerRight
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Output
│   ├── Output
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Output
│   ├── PointerRight
│   ├── Decrement
│   ├── Output
│   ├── PointerLeft
│   ├── PointerLeft
│   ├── Increment
│   ├── Loop
│   │   ├── PointerRight
│   │   ├── Loop
│   │   │   ├── Increment
│   │   │   ├── PointerRight
│   │   │   └── Increment
│   │   ├── PointerRight
│   │   └── PointerRight
│   ├── PointerLeft
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Output
│   ├── PointerRight
│   ├── PointerRight
│   ├── Output
│   ├── Increment
│   ├── Increment
│   ├── Increment
│   ├── Output
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Output
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Decrement
│   ├── Output
│   ├── PointerRight
│   ├── Increment
│   ├── Output
│   ├── PointerRight
│   ├── Increment
│   └── Output

И класс public class IntermediateCodeGenerator { public AST generateAST(final AST sourceAST) { return new AST(sourceToIntermediateNode(sourceAST.getRoot())); } private ASTNode sourceToIntermediateNode(final ASTNode node) { Expression expression = node.getExpression(); if (expression instanceof RootExpression) { return ASTNode.newWithMappedChildren(new RootExpression(), node.getChildren(), this::sourceToIntermediateNode); } if (expression instanceof PointerRightExpression) { return ASTNode.newWithChild(new MemoryPointerChangeExpression(), new ASTNode(new IntegerExpression(1))); } if (expression instanceof PointerLeftExpression) { return ASTNode.newWithChild(new MemoryPointerChangeExpression(), new ASTNode(new IntegerExpression(-1))); } if (expression instanceof IncrementExpression) { return ASTNode.newWithChild(new MemoryValueChangeExpression(), new ASTNode(new IntegerExpression(1))); } if (expression instanceof DecrementExpression) { return ASTNode.newWithChild(new MemoryValueChangeExpression(), new ASTNode(new IntegerExpression(-1))); } if (expression instanceof OutputExpression) { return new ASTNode(new MemoryOutputExpression()); } if (expression instanceof InputExpression) { return new ASTNode(new MemoryInputExpression()); } if (expression instanceof LoopExpression) { return ASTNode.newWithMappedChildren(new MemoryLoopExpression(), node.getChildren(), this::sourceToIntermediateNode); } throw new IllegalArgumentException("Node with unknown expression type: " + expression); } } :

├── Root
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryLoop
│   │   ├── MemoryValueChange
│   │   │   └── Integer(-1)
│   │   ├── MemoryPointerChange
│   │   │   └── Integer(-1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   ├── MemoryValueChange
│   │   │   └── Integer(1)
│   │   └── MemoryPointerChange
│   │       └── Integer(1)
│   ├── MemoryPointerChange
│   │   └── Integer(-1)
│   ├── MemoryOutput
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryLoop
│   │   └── MemoryValueChange
│   │       └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryLoop
│   │   ├── MemoryPointerChange
│   │   │   └── Integer(1)
│   │   ├── MemoryLoop
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(-1)
│   │   │   ├── MemoryPointerChange
│   │   │   │   └── Integer(1)
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(1)
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(1)
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(1)
│   │   │   ├── MemoryPointerChange
│   │   │   │   └── Integer(-1)
│   │   │   ├── MemoryPointerChange
│   │   │   │   └── Integer(-1)
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(1)
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(1)
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(1)
│   │   │   └── MemoryPointerChange
│   │   │       └── Integer(1)
│   │   ├── MemoryPointerChange
│   │   │   └── Integer(-1)
│   │   └── MemoryPointerChange
│   │       └── Integer(-1)
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryOutput
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryOutput
│   ├── MemoryOutput
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryOutput
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryOutput
│   ├── MemoryPointerChange
│   │   └── Integer(-1)
│   ├── MemoryPointerChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryLoop
│   │   ├── MemoryPointerChange
│   │   │   └── Integer(1)
│   │   ├── MemoryLoop
│   │   │   ├── MemoryValueChange
│   │   │   │   └── Integer(1)
│   │   │   ├── MemoryPointerChange
│   │   │   │   └── Integer(1)
│   │   │   └── MemoryValueChange
│   │   │       └── Integer(1)
│   │   ├── MemoryPointerChange
│   │   │   └── Integer(1)
│   │   └── MemoryPointerChange
│   │       └── Integer(1)
│   ├── MemoryPointerChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryOutput
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryOutput
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryOutput
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryOutput
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryValueChange
│   │   └── Integer(-1)
│   ├── MemoryOutput
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   ├── MemoryOutput
│   ├── MemoryPointerChange
│   │   └── Integer(1)
│   ├── MemoryValueChange
│   │   └── Integer(1)
│   └── MemoryOutput

Поскольку созданный Target AST действительно огромен, вы можете найти его на Pastebin .

И в качестве последнего этапа у нас есть создатель целевого кода:

public class TargetCodeGenerator {
    private final BFOptions bfOptions;

    public TargetCodeGenerator(final BFOptions bfOptions) {
        this.bfOptions = bfOptions;
    }

    public AST generateAST(final AST intermediateAST) {
        int stderr = 2;
        int bfMemoryCellAmount = bfOptions.getMemoryCellAmount();

        ASTNode rootNode = new ASTNode(new RootExpression());
        AST ast = new AST(rootNode);

        // Header of the BF.exe program -do not modify-
        ASTNode externNode = new ASTNode(new ExternExpression());
        externNode.addChild(ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_calloc"))));
        externNode.addChild(ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_fdopen"))));
        externNode.addChild(ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_fprintf"))));
        externNode.addChild(ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_getchar"))));
        externNode.addChild(ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_putchar"))));
        rootNode.addChild(externNode);

        ASTNode dataSectionNode = new ASTNode(new DataSectionExpression());
        dataSectionNode.addChild(ASTNode.newWithChildren(new DefineByteExpression(), Arrays.asList(
            ASTNode.newWithChild(new IdentifierExpression(), new ASTNode(new StringExpression("write_mode"))),
            ASTNode.newWithChild(new ValueExpression(), ASTNode.newWithChildren(new ValueListExpression(), Arrays.asList(
                new ASTNode(new StringExpression("w")),
                new ASTNode(new IntegerExpression(0))
            )))
        )));
        dataSectionNode.addChild(ASTNode.newWithChildren(new DefineByteExpression(), Arrays.asList(
            ASTNode.newWithChild(new IdentifierExpression(), new ASTNode(new StringExpression("error_outofmemory"))),
            ASTNode.newWithChild(new ValueExpression(), ASTNode.newWithChildren(new ValueListExpression(), Arrays.asList(
                new ASTNode(new StringExpression("Fatal: The Operating System does not have enough memory available.")),
                new ASTNode(new IntegerExpression(0))
            )))
        )));
        rootNode.addChild(dataSectionNode);

        ASTNode bssSectionNode = new ASTNode(new BssSectionExpression());
        bssSectionNode.addChild(ASTNode.newWithChildren(new ReserveDoubleExpression(), Arrays.asList(
            ASTNode.newWithChild(new IdentifierExpression(), new ASTNode(new StringExpression("bf_memory"))),
            ASTNode.newWithChild(new ValueExpression(), new ASTNode(new IntegerExpression(1)))
        )));
        rootNode.addChild(bssSectionNode);

        ASTNode textSectionNode = new ASTNode(new TextSectionExpression());
        textSectionNode.addChild(ASTNode.newWithChild(new GlobalExpression(),
            ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("_main")))));
        textSectionNode.addChild(ASTNode.newWithChild(new DefineLabelExpression(),
            ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("_main")))));
        textSectionNode.addChild(ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EBP))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.ESP)))
        )));
        textSectionNode.addChild(ASTNode.newWithChild(new PushExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new DwordExpression(), new ASTNode(new IntegerExpression(1))))));
        textSectionNode.addChild(ASTNode.newWithChild(new PushExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new DwordExpression(), new ASTNode(new IntegerExpression(bfMemoryCellAmount))))));
        textSectionNode.addChild(ASTNode.newWithChild(new CallExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_calloc"))))));
        textSectionNode.addChild(ASTNode.newWithChildren(new AddExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.ESP))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(8)))
        )));
        textSectionNode.addChild(ASTNode.newWithChildren(new TestExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX)))
        )));
        textSectionNode.addChild(ASTNode.newWithChild(new JzExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("error_exit_outofmemory"))))));
        textSectionNode.addChild(ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new MemoryAddressExpression(),
                    ASTNode.newWithChild(new IdentifierExpression(), new ASTNode(new StringExpression("bf_memory"))))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX)))
        )));
        textSectionNode.addChild(ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EDI))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX)))
        )));

        // Code Generated from the Intermediate AST
        convertIntermediateToTargetNodes(intermediateAST.getRoot(), "").forEach(textSectionNode::addChild);

        // Bottom of the BF.exe program -do not modify-
        textSectionNode.addChild(ASTNode.newWithChild(new JmpExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("normal_exit"))))));

        textSectionNode.addChild(ASTNode.newWithChild(new DefineLabelExpression(),
            ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("error_exit_outofmemory")))));
        textSectionNode.addChild(ASTNode.newWithChild(new PushExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new IdentifierExpression(), new ASTNode(new StringExpression("write_mode"))))));
        textSectionNode.addChild(ASTNode.newWithChild(new PushExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new DwordExpression(), new ASTNode(new IntegerExpression(stderr))))));
        textSectionNode.addChild(ASTNode.newWithChild(new CallExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_fdopen"))))));
        textSectionNode.addChild(ASTNode.newWithChildren(new AddExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.ESP))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(8)))
        )));
        textSectionNode.addChild(ASTNode.newWithChild(new PushExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new IdentifierExpression(), new ASTNode(new StringExpression("error_outofmemory"))))));
        textSectionNode.addChild(ASTNode.newWithChild(new PushExpression(),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX)))));
        textSectionNode.addChild(ASTNode.newWithChild(new CallExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_fprintf"))))));
        textSectionNode.addChild(ASTNode.newWithChildren(new AddExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.ESP))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(8)))
        )));
        textSectionNode.addChild(ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(-1)))
        )));
        textSectionNode.addChild(ASTNode.newWithChild(new JmpShortExpression(),
            ASTNode.newWithChild(new OperandExpression(),
                ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("exit"))))));

        textSectionNode.addChild(ASTNode.newWithChild(new DefineLabelExpression(),
            ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("normal_exit")))));
        textSectionNode.addChild(ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX))),
            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(0)))
        )));

        textSectionNode.addChild(ASTNode.newWithChild(new DefineLabelExpression(),
            ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("exit")))));
        textSectionNode.addChild(new ASTNode(new RetExpression()));
        rootNode.addChild(textSectionNode);

        return ast;
    }

    private Stream<ASTNode> convertIntermediateToTargetNodes(final ASTNode node, final String uniqueIndex) {
        Expression expression = node.getExpression();
        if (expression instanceof RootExpression) {
            return IntStream.range(0, node.getChildren().size())
                .boxed()
                .flatMap(i -> convertIntermediateToTargetNodes(node.getChildren().get(i), uniqueIndex + "_" + i));
        }
        if (expression instanceof MemoryLoopExpression) {
            return Stream.concat(
                Stream.of(
                    ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
                        ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL))),
                        ASTNode.newWithChild(new OperandExpression(),
                            ASTNode.newWithChild(new MemoryAddressExpression(), new ASTNode(new RegisterExpression(Register.EDI))))
                    )),
                    ASTNode.newWithChildren(new TestExpression(), Arrays.asList(
                        ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL))),
                        ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL)))
                    )),
                    ASTNode.newWithChild(new JzExpression(),
                        ASTNode.newWithChild(new OperandExpression(),
                            ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("loop_end" + uniqueIndex))))),
                    ASTNode.newWithChild(new DefineLabelExpression(),
                        ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("loop_start" + uniqueIndex))))
                ),
                Stream.concat(
                    IntStream.range(0, node.getChildren().size())
                        .boxed()
                        .flatMap(i -> convertIntermediateToTargetNodes(node.getChildren().get(i), uniqueIndex + "_" + i)),
                    Stream.of(
                        ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
                            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL))),
                            ASTNode.newWithChild(new OperandExpression(),
                                ASTNode.newWithChild(new MemoryAddressExpression(), new ASTNode(new RegisterExpression(Register.EDI))))
                        )),
                        ASTNode.newWithChildren(new TestExpression(), Arrays.asList(
                            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL))),
                            ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL)))
                        )),
                        ASTNode.newWithChild(new JnzExpression(),
                            ASTNode.newWithChild(new OperandExpression(),
                                ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("loop_start" + uniqueIndex))))),
                        ASTNode.newWithChild(new DefineLabelExpression(),
                            ASTNode.newWithChild(new LabelExpression(), new ASTNode(new StringExpression("loop_end" + uniqueIndex))))
                    )
                )
            );
        }
        if (expression instanceof MemoryPointerChangeExpression) {
            int changeValue = node.getChildren().get(0).getExpression(IntegerExpression.class).getInteger();
            if (changeValue == 0) {
                return Stream.empty();
            }
            return Stream.of(
                ASTNode.newWithChildren(new AddExpression(), Arrays.asList(
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EDI))),
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(changeValue)))
                ))
            );
        }
        if (expression instanceof MemoryValueChangeExpression) {
            int changeValue = node.getChildren().get(0).getExpression(IntegerExpression.class).getInteger();
            if (changeValue == 0) {
                return Stream.empty();
            }
            return Stream.of(
                ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL))),
                    ASTNode.newWithChild(new OperandExpression(),
                        ASTNode.newWithChild(new MemoryAddressExpression(), new ASTNode(new RegisterExpression(Register.EDI))))
                )),
                ASTNode.newWithChildren(new AddExpression(), Arrays.asList(
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL))),
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(changeValue)))
                )),
                ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
                    ASTNode.newWithChild(new OperandExpression(),
                        ASTNode.newWithChild(new MemoryAddressExpression(), new ASTNode(new RegisterExpression(Register.EDI)))),
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL)))
                ))
            );
        }
        if (expression instanceof MemoryInputExpression) {
            return Stream.of(
                ASTNode.newWithChild(new CallExpression(),
                    ASTNode.newWithChild(new OperandExpression(),
                        ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_getchar"))))),
                ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
                    ASTNode.newWithChild(new OperandExpression(),
                        ASTNode.newWithChild(new MemoryAddressExpression(), new ASTNode(new RegisterExpression(Register.EDI)))),
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL)))
                ))
            );
        }
        if (expression instanceof MemoryOutputExpression) {
            return Stream.of(
                ASTNode.newWithChildren(new MovExpression(), Arrays.asList(
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.AL))),
                    ASTNode.newWithChild(new OperandExpression(),
                        ASTNode.newWithChild(new MemoryAddressExpression(), new ASTNode(new RegisterExpression(Register.EDI))))
                )),
                ASTNode.newWithChild(new PushExpression(),
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.EAX)))),
                ASTNode.newWithChild(new CallExpression(),
                    ASTNode.newWithChild(new OperandExpression(),
                        ASTNode.newWithChild(new FunctionExpression(), new ASTNode(new StringExpression("_putchar"))))),
                ASTNode.newWithChildren(new AddExpression(), Arrays.asList(
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.ESP))),
                    ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(4)))
                ))
            );
        }
        throw new IllegalArgumentException("Node with unsupported expression type: " + expression);
    }
}

Он генерирует следующий код ASM, который доступен на Pastebin .

И тогда есть класс BFOptions, чтобы скомпилировать код сборки x86 в исполняемый файл:

public class BFOptions {
    private final int memoryCellAmount;

    private BFOptions(final Builder builder) {
        this.memoryCellAmount = builder.memoryCellAmount;
    }

    public int getMemoryCellAmount() {
        return memoryCellAmount;
    }

    public static class Builder {
        private int memoryCellAmount;

        public Builder memoryCellAmount(final int memoryCellAmount) {
            this.memoryCellAmount = memoryCellAmount;
            return this;
        }

        public BFOptions build() {
            return new BFOptions(this);
        }
    }
}

Класс public class TargetCodeWriter { public Stream<String> write(final AST targetAst) { return targetAst.getRoot().getChildren().stream() .flatMap(this::resolveNode); } private Stream<String> resolveNode(final ASTNode node) { Expression expression = node.getExpression(); if (expression instanceof ExternExpression) { String functions = node.getChildren().stream() .flatMap(n -> resolveNode(n, FunctionExpression.class)) .collect(Collectors.joining(", ")); return Stream.of("extern " + functions); } if (expression instanceof FunctionExpression) { return Stream.of(resolveFunction(node)); } if (expression instanceof DataSectionExpression) { return Stream.concat( Stream.of("section .data"), resolveChildren(node) ); } if (expression instanceof DefineByteExpression) { String identifier = resolveIdentifier(node.getChild(0, IdentifierExpression.class)); String value = resolveValue(node.getChild(1, ValueExpression.class)); return Stream.of(identifier + " db " + value); } if (expression instanceof BssSectionExpression) { return Stream.concat( Stream.of("section .bss"), resolveChildren(node) ); } if (expression instanceof ReserveDoubleExpression) { String identifier = resolveIdentifier(node.getChild(0, IdentifierExpression.class)); String value = resolveValue(node.getChild(1, ValueExpression.class)); return Stream.of(identifier + " resd " + value); } if (expression instanceof TextSectionExpression) { return Stream.concat( Stream.of("section .text"), resolveChildren(node) ); } if (expression instanceof GlobalExpression) { String label = resolveLabel(node.getChild(0, LabelExpression.class)); return Stream.of("global " + label); } if (expression instanceof DefineLabelExpression) { String label = resolveLabel(node.getChild(0, LabelExpression.class)); return Stream.of(label + ":"); } if (expression instanceof MovExpression) { String operand1 = resolveOperand(node.getChild(0, OperandExpression.class)); String operand2 = resolveOperand(node.getChild(1, OperandExpression.class)); return Stream.of("mov " + operand1 + ", " + operand2); } if (expression instanceof PushExpression) { String operand = resolveOperand(node.getChild(0, OperandExpression.class)); return Stream.of("push " + operand); } if (expression instanceof CallExpression) { String operand = resolveOperand(node.getChild(0, OperandExpression.class)); return Stream.of("call " + operand); } if (expression instanceof AddExpression) { String operand1 = resolveOperand(node.getChild(0, OperandExpression.class)); String operand2 = resolveOperand(node.getChild(1, OperandExpression.class)); return Stream.of("add " + operand1 + ", " + operand2); } if (expression instanceof TestExpression) { String operand1 = resolveOperand(node.getChild(0, OperandExpression.class)); String operand2 = resolveOperand(node.getChild(1, OperandExpression.class)); return Stream.of("test " + operand1 + ", " + operand2); } if (expression instanceof JzExpression) { String operand = resolveOperand(node.getChild(0, OperandExpression.class)); return Stream.of("jz " + operand); } if (expression instanceof JnzExpression) { String operand = resolveOperand(node.getChild(0, OperandExpression.class)); return Stream.of("jnz " + operand); } if (expression instanceof JmpExpression) { String operand = resolveOperand(node.getChild(0, OperandExpression.class)); return Stream.of("jmp " + operand); } if (expression instanceof JmpShortExpression) { String operand = resolveOperand(node.getChild(0, OperandExpression.class)); return Stream.of("jmp short " + operand); } if (expression instanceof RetExpression) { return Stream.of("ret"); } throw new IllegalStateException("Unsupported expression: " + expression); } private Stream<String> resolveNode(final ASTNode node, final Class<? extends Expression> expectedExpression) { Expression expression = node.getExpression(); if (!expectedExpression.isInstance(expression)) { throw new IllegalStateException("Cannot resolve node " + node + ": Expected " + expectedExpression + ", found " + expression); } return resolveNode(node); } private Stream<String> resolveChildren(final ASTNode node) { return node.getChildren().stream().flatMap(this::resolveNode); } private String resolveIdentifier(final ASTNode node) { return node.getChildExpression(0, StringExpression.class).getString(); } private String resolveValue(final ASTNode node) { Expression expression = node.getExpression(); if (expression instanceof ValueExpression) { return resolveValue(node.getChild(0, Expression.class)); } if (expression instanceof ValueListExpression) { return node.getChildren().stream().map(this::resolveValue).collect(Collectors.joining(", ")); } if (expression instanceof StringExpression) { return "\"" + resolveString(node) + "\""; } if (expression instanceof IntegerExpression) { return resolveInteger(node); } throw new IllegalStateException("Unsupported expression while resolving value: " + expression); } private String resolveString(final ASTNode node) { return node.getExpression(StringExpression.class).getString(); } private String resolveInteger(final ASTNode node) { return String.valueOf(node.getExpression(IntegerExpression.class).getInteger()); } private String resolveLabel(final ASTNode node) { return node.getChildExpression(0, StringExpression.class).getString(); } private String resolveOperand(final ASTNode node) { Expression expression = node.getExpression(); if (expression instanceof OperandExpression) { return resolveOperand(node.getChild(0, Expression.class)); } if (expression instanceof RegisterExpression) { return resolveRegister(node); } if (expression instanceof DwordExpression) { return "dword " + resolveOperand(node.getChild(0, Expression.class)); } if (expression instanceof IntegerExpression) { return resolveInteger(node); } if (expression instanceof FunctionExpression) { return resolveFunction(node); } if (expression instanceof LabelExpression) { return resolveLabel(node); } if (expression instanceof MemoryAddressExpression) { return "[" + resolveOperand(node.getChild(0, Expression.class)) + "]"; } if (expression instanceof IdentifierExpression) { return resolveIdentifier(node); } throw new IllegalStateException("Unsupported expression while resolving operand: " + expression); } private String resolveRegister(final ASTNode node) { return node.getExpression(RegisterExpression.class).getRegister().name().toLowerCase(Locale.ENGLISH); } private String resolveFunction(final ASTNode node) { return node.getChildExpression(0, StringExpression.class).getString(); } } :

BFCompiler

И, наконец, это класс public class BFCompiler { public void compile(final Stream<String> targetCode, Path workingDirectory, String programName) throws IOException, InterruptedException { Path assemblyFile = workingDirectory.resolve(programName + ".asm"); Files.deleteIfExists(assemblyFile); Files.write(assemblyFile, (Iterable<String>)targetCode::iterator, StandardCharsets.UTF_8, StandardOpenOption.CREATE_NEW); ProcessBuilder processBuilder = new ProcessBuilder().directory(workingDirectory.toFile()).redirectErrorStream(true); Process nasmProcess = processBuilder.command("nasm", "-f", "win32", assemblyFile.getFileName().toString()).start(); nasmProcess.waitFor(); List<String> nasmOutput = ProcessUtils.toInputStream(nasmProcess.getInputStream()); if (!nasmOutput.isEmpty()) { throw new IllegalStateException("Compiling failed when invoking NASM: " + String.join(System.lineSeparator(), nasmOutput)); } Process gccProcess = processBuilder.command("gcc", "-o", programName, programName + ".obj").start(); gccProcess.waitFor(); if (!nasmOutput.isEmpty()) { throw new IllegalStateException("Compiling failed when invoking GCC: " + String.join(System.lineSeparator(), nasmOutput)); } } } , который также показывает некоторое использование других классов:

ProcessUtils

Полный репозиторий можно найти на GitHub .

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

  • Количество подклассов public class ProcessUtils { private ProcessUtils() { throw new UnsupportedOperationException(); } public static List<String> toInputStream(final InputStream inputStream) throws IOException { List<String> output = new ArrayList<>(); try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream, StandardCharsets.UTF_8))) { String line; while ((line = bufferedReader.readLine()) != null) { output.add(line); } } return output; } } - это, вероятно, плохая идея.
  • Написание всего кода с учетом структуры данных Main было, вероятно, плохой идеей, использование public class Main { public static void main(final String[] args) throws IOException, InterruptedException { Path currentWorkingDirectory = Paths.get(".").toAbsolutePath().normalize(); if (args.length == 0) { throw new IllegalStateException("Expected the Brainfuck source file as first argument."); } String sourceFileString = args[0]; Path sourceFile = currentWorkingDirectory.resolve(sourceFileString); if (!Files.exists(sourceFile)) { throw new IllegalStateException("The source file does not exist."); } String completeFileName = sourceFile.getFileName().toString(); int dotIndex = completeFileName.lastIndexOf('.'); String fileName = (dotIndex > 0) ? completeFileName.substring(0, dotIndex) : completeFileName; SourceFile bfSourceFile = new SourceFile(sourceFile); LexicalAnalyzer lexicalAnalyzer = new LexicalAnalyzer(bfSourceFile); SyntaxAnalyzer syntaxAnalyzer = new SyntaxAnalyzer(); IntermediateCodeGenerator intermediateCodeGenerator = new IntermediateCodeGenerator(); BFOptions bfOptions = new BFOptions.Builder().memoryCellAmount(30000).build(); TargetCodeGenerator targetCodeGenerator = new TargetCodeGenerator(bfOptions); TargetCodeWriter targetCodeWriter = new TargetCodeWriter(); AST sourceAst = syntaxAnalyzer.getAST(lexicalAnalyzer.getTokens()); AST intermediateAst = intermediateCodeGenerator.generateAST(sourceAst); AST targetAst = targetCodeGenerator.generateAST(intermediateAst); BFCompiler bfCompiler = new BFCompiler(); bfCompiler.compile(targetCodeWriter.write(targetAst), currentWorkingDirectory, fileName); } } могло бы быть более ясным.
  • Существует много связей между Expression и Stream, которые мне не нравятся.
  • Множество конструкторов разных фаз фактически не принимает никаких аргументов.
  • Существует довольно беспорядок при разрешении одного типа выражения на другой, в частности:
    • Из List в исходные выражения
    • От исходных выражений до промежуточных выражений
    • От промежуточных выражений до целевых выражений
    • От целевых выражений до строк сборки

Я не уверен, следует ли обрабатывать разрешающую часть в ASTNode подклассы.

Я готов к умственному воздействию этого кода, <

39 голосов | спросил skiwi 22 22016vEurope/Moscow11bEurope/MoscowTue, 22 Nov 2016 20:10:53 +0300 2016, 20:10:53

2 ответа


6

Созданный вами TargetStationGenerator имеет несколько уровней абстракции, встроенных в один метод.

И это длинный метод.

Он содержит все эти детали, которые довольно сложны - когда я вижу такие функции, как

    dataSectionNode.addChild(ASTNode.newWithChildren(new DefineByteExpression(), Arrays.asList(
        ASTNode.newWithChild(new IdentifierExpression(), new ASTNode(new StringExpression("write_mode"))),
        ASTNode.newWithChild(new ValueExpression(), ASTNode.newWithChildren(new ValueListExpression(), Arrays.asList(
            new ASTNode(new StringExpression("w")),
            new ASTNode(new IntegerExpression(0))
        )))
    )));

Пройдите, я начинаю читать, а не читать. Что происходит со всеми этими супер подробными вещами?

Что, разумеется, помогает этой команде немного:

// Header of the BF.exe program -do not modify-

Это заголовок.

Прежде чем я вернусь и расскажу о сложности generateAST, давайте быстро взглянем на этот комментарий - в нем говорится: «Не изменяйте».

Кто является целевой аудиторией для этого комментария? Наверное, только ты. Но вы также тот человек, который (вроде) знает, почему это предупреждение существует.

Рассматривали ли вы возможность включения своих комментариев в функции?

    ASTNode externNode = new ASTNode(new ExternExpression());
    ...
    rootNode.addChild(externNode);

    ASTNode dataSectionNode = new ASTNode(new DataSectionExpression());
    ...
    rootNode.addChild(dataSectionNode);

    ASTNode bssSectionNode = new ASTNode(new BssSectionExpression());
    ...
    rootNode.addChild(bssSectionNode);

    ASTNode textSectionNode = new ASTNode(new TextSectionExpression());
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...;
    textSectionNode.addChild(...);

    // Code Generated from the Intermediate AST
    convertIntermediateToTargetNodes(intermediateAST.getRoot(), "").forEach(textSectionNode::addChild);

    // Bottom of the BF.exe program -do not modify-
    textSectionNode.addChild(...);

    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);
    textSectionNode.addChild(...);

    textSectionNode.addChild(...);

    textSectionNode.addChild(...);
    textSectionNode.addChild(new ASTNode(new RetExpression()));
    rootNode.addChild(textSectionNode);

Я превратил тела добавляемых дочерних бит в эллипсы.

Я думаю, что externNode и dataSectionNode и bssSectionNode могут быть частью метода addHeader. Возможно, существуют отдельные функции для создания такого externNode и dataSectionNode и т. Д.

Остальное, вероятно, входит в метод createBody - нет нижнего колонтитула, если честно, потому что все после заголовка переходит в textSectionNode. Кажется, что-то вроде определения calloc и основного метода или чего-то еще. Я бы ожидал, что createBody рассмотрит строки типа textSectionNode.addChild(createNodeForCalloc()). Конечно, внутри должно быть тело, поэтому, возможно, createBody требуется промежуточный АСТ.

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

И главная причина, по которой это так важно, состоит в том, что компиляция скрыта между всеми этими шагами.

Между всеми этими фиксированными значениями /созданиями узлов является эта строка

    // Code Generated from the Intermediate AST
    convertIntermediateToTargetNodes(intermediateAST.getRoot(), "").forEach(textSectionNode::addChild);

И это не строка, которая должна быть скрыта, потому что это фактический код.

...

И, возможно, когда вы разделите код на множество небольших функций, вы найдете способ избавиться от дублирования между добавлением операций Add и Mov. Оба они, кажется, принимают два аргумента.

    textSectionNode.addChild(ASTNode.newWithChildren(new AddExpression(), Arrays.asList(
        ASTNode.newWithChild(new OperandExpression(), new ASTNode(new RegisterExpression(Register.ESP))),
        ASTNode.newWithChild(new OperandExpression(), new ASTNode(new IntegerExpression(8)))
    )));

Что-то, чтобы преобразовать это в

textSectionNode.addChild(createNewAddNode(new RegisterExpression(Register.ESP), new IntegerExpression(8)));

Потому что тогда вы избавляетесь от трещины и показываете соответствующий код.


Короче говоря,

Напишите что-то, что создаст выражения из выражений, без необходимости самостоятельно создавать ASTNodes. Если вам нужна более сложная структура, вы можете создать ASTNodes, но ASTNodes кажутся шумом при определении программы.

Используя упрощенный способ создания выражений для генерации кода, реструктурируйте generateAST, чтобы его было легче читать и видеть, что он делает.

ответил Pimgd 27 J000000Thursday17 2017, 12:16:51
3

Вещи, которые я изменил (aka. TOC):

  • Отделить разные АСТ друг от друга.
  • Свернуть классы ASTNode в перечисления, где это возможно
  • Генерируйте ASTNode и AST для принятия <T extends AstExpression>
  • Внедрить IntermediateCodeGenerator в терминах трансформаторов на основе enum

Код выполняет (и может) не различать intermediateAST, sourceAST и targetAST, потому что они не различаются по типу.

Чтобы облегчить это, первым шагом является make эти два разных. Таким образом, я ввел общий параметр в ASTNode и AST, который ограничен подтипом ASTExpression.

public class ASTNode<T extends AstExpression> {
    private final T expression;

    private ASTNode<T> parent;

    private final List<ASTNode<T>> children = new LinkedList<>();

    public ASTNode(final T expression) {
        this.expression = expression;
    }
    // ...
}

Этот общий параметр, очевидно, должен быть расширен до AST


Классы узлов AST и instanceof могут быть заменены на очень большие части следующими перечислениями:

public enum SourceExpressions implements AstExpression {
    INCREMENT, DECREMENT, INPUT, LOOP, OUTPUT, POINTER_LEFT, POINTER_RIGHT, ROOT;

    @Override
    public boolean isLogicalLeaf() {
        return this != LOOP;
    }
}

public enum IntermediateExpressions implements AstExpression {
    ADD_MULTIPLE_OF_STORED_VALUE, INPUT, LOOP, OUTPUT, POINTER_CHANGE, VALUE_SET, VALUE_STORE, VALUE_CHANGE, VALUE, ROOT;

    @Override
    public boolean isLogicalLeaf() {
        return this != LOOP;
    }
}

public enum TargetExpressions implements TargetExpression {
    ADD, BSS_SECTION, BYTE, CALL, DATA_SECTION, DEFINE_BYTE, DEFINE_LABEL, DWORD, EXTERN, FUNCTION, GLOBAL, IDENTIFIER,
    JMP, JNZ, JZ, LABEL, MEMORY_ADDRESS, MOV, MUL, OPERAND, PUSH, REGISTER, RESERVE_DOUBLE, RET, TEST, TEXT_SECTION,
    VALUE, VALUE_LIST, XOR, ROOT, JMP_SHORT;

    @Override
    public boolean isLogicalLeaf() {
        return false;
    }
}

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


Пока мы находимся в этих instanceof проверках: теперь, когда мы заменили эти выражения красиво названными перечислениями, мы можем изменить способ работы IntermediateCodeGenerator:

Мы можем абстрагировать процесс сопоставления из SourceExpressions в IntermediateExpressions из данных, необходимых для выполнения указанного отображения.

Рассмотрим следующее:

public static AST<IntermediateExpressions> generateAST(final AST<SourceExpressions> sourceAST) {
    return new AST<>(sourceToIntermediateNode(sourceAST.getRoot()));
}

private static ASTNode<IntermediateExpressions> sourceToIntermediateNode(final ASTNode<SourceExpressions> node) {
    SourceExpressions expression = node.getExpression();
    final Function<ASTNode<SourceExpressions>, ASTNode<IntermediateExpressions>> nodeFunction = transformer.get(expression);
    if (nodeFunction == null) {
        throw new IllegalArgumentException("Node with unknown expression type: " + expression);
    }
    return nodeFunction.apply(node);
}   

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

private static final Map<SourceExpressions, Function<ASTNode<SourceExpressions>, ASTNode<IntermediateExpressions>>> transformer = new EnumMap<>(SourceExpressions.class);

static {
    transformer.put(SourceExpressions.ROOT, node -> ASTNode.newWithMappedChildren(IntermediateExpressions.ROOT
            , IntermediateCodeGenerator::sourceToIntermediateNode
            , node.getChildren().stream()));
    transformer.put(SourceExpressions.POINTER_RIGHT, node -> ASTNode.newWithChildren(IntermediateExpressions.POINTER_CHANGE, new IntegerExpression(1)));
    transformer.put(SourceExpressions.POINTER_LEFT, node -> ASTNode.newWithChildren(IntermediateExpressions.POINTER_CHANGE, new IntegerExpression(-1)));
    transformer.put(SourceExpressions.INCREMENT, node -> ASTNode.newWithChildren(IntermediateExpressions.VALUE_CHANGE, new IntegerExpression(1)));
    transformer.put(SourceExpressions.DECREMENT, node -> ASTNode.newWithChildren(IntermediateExpressions.VALUE_CHANGE, new IntegerExpression(-1)));
    transformer.put(SourceExpressions.OUTPUT, node -> new ASTNode<>(IntermediateExpressions.OUTPUT));
    transformer.put(SourceExpressions.INPUT, node -> new ASTNode<>(IntermediateExpressions.INPUT));
    transformer.put(SourceExpressions.LOOP, node -> ASTNode.newWithMappedChildren(IntermediateExpressions.LOOP
            , IntermediateCodeGenerator::sourceToIntermediateNode
            , node.getChildren().stream()));
}

К сожалению, генерация целевого кода не так сильно выигрывает от изменений, как генерация промежуточного кода. То, что мы делаем, - это возможность добавить случай select case вместо цепочки if-statements.


Возможно, я сделал и другие изменения, но для жизни я не могу понять, что я тоже изменил в 4.5kLoC diff. Теперь я сижу с тех пор, как возрасты

Поставьте мне примечание, если вы хотите что-то из этого:)

ответил Vogel612 8 32017vEurope/Moscow11bEurope/MoscowWed, 08 Nov 2017 19:54:20 +0300 2017, 19:54:20

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132