40
\$\begingroup\$

After my Brainfuck Interpreter written in x86 Assembly I decided that it was time to get to the next step, writing a Brainfuck Compiler in Java that generates x86 Assembly and compiles that to an executable.

Currently it only supports Windows and it still uses NASM and GCC as dependencies to transform the x86 Assembly code to actual executables. This is not ideal, but this is also the easiest way.

The compiler is currently still completely unoptimized and will be very happy to repeatedly increment/decrement pointers and/or memory locations.

I don't have a video this time, but my interpreter executed a Mandelbrot BF file in 60 seconds, and the executable obtained from this compiler executes it in 4 seconds.

My code intends to follow a generic compiler design, consisting of the following phases:

  • Reading the source code file
  • The Lexical Analyzer which translates the source file to a stream of tokens
  • The Syntax Analyzer which builds an Abstract Syntax Tree (AST) from the stream of tokens and checks simple things like if loops match
  • The Intermediate Code Generator which takes the Source AST and transforms it into an Intermediate AST
  • The Target Code Generator which takes the Intermediate AST and transforms it into a Target AST
  • The Target Code Writer which takes the Target AST and writes actual x86 Assembly code as output.

There are a few notable things to mention:

  • There is no Semantic Analyzer. In a more complete language such phase would check whether assignment happens between compatible types, etc. Since Brainfuck is not advanced enough there is no need for this phase.
  • The Intermediate AST is not directly used right now, in a later phase all optimizations will be done on this Intermediate AST. Think about replacing +++ by the pseudocode addmemorycell(3), <<< by addpointer(-3), [-] by setmemorycell(0).

Now onto the code, let's start with the AST and the Expression interface:

public interface Expression {
}

Every code fragment in my program is a subclass of Expression, most subclasses do not define any fields or methods and are equal to themselves, the only exceptions are IntegerExpression, StringExpression and RegisterExpression, they have an Integer, a String and a Register as field respectively.

I do not believe it is worthwhile to copy all expressions here, so I will just list them grouped by package.

The expression.source package contains:

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

These are really just the Brainfuck tokens.

The expression.intermediate package contains:

  • MemoryInputExpression
  • MemoryLoopExpression
  • MemoryOutputExpression
  • MemoryPointerChangeExpression
  • MemoryValueChangeExpression

These are intermediate representations of the Brainfuck tokens to allow easier reasoning about them, you can see that Increment/Decrement and PointerLeft/PointerRight are merged.

Then there's the expression.target package:

  • AddExpression
  • BssSectionExpression
  • CallExpression
  • DataSectionExpression
  • DefineByteExpression
  • DefineLabelExpression
  • DwordExpression
  • ExternExpression
  • FunctionExpression
  • GlobalExpression
  • IdentifierExpression
  • JmpExpression
  • JmpShortExpression
  • JnzExpression
  • JzExpression
  • LabelExpression
  • MemoryAddressExpression
  • MovExpression
  • OperandExpression
  • PushExpression
  • Register
  • RegisterExpression
  • ReserveDoubleExpression
  • RetExpression
  • TestExpression
  • TextSectionExpression
  • ValueExpression
  • ValueListExpression

These contain pretty much Assembly expressions and in my opinion there are quite a lot of them.

To get you a feel of how they look like I'll take the 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);
    }
}

And 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;
}

With the expressions explained it's now time to show the AST structure.

We have the AST class:

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);
    }
}

And then the big ASTNode class:

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);
    }
}

Now we can take a look at the first phase, reading the source file in the SourceFile class.

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);
    }
}

Next up is the Lexical Analyzer:

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);
    }
}

Which uses the Token class:

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;
    }
}

Next is the Syntax Analyzer:

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;
    }
}

Which uses this simple InvalidSyntaxException class:

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

If you've made it this far into the question, please stop for a minute and look at the following Hello World program, which I've been using for tests all over my code:

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

I'm sure all Brainfuck experts will immediately see how it works, if you don't then that's not a big issue because initially I wasn't sure either. The only thing I know is that it is not the most optimal program as at one point there is a -[+]++ sequence meaning that the memory cell is decremented, then incremented until it is zero (we are using 8-bit memory cells so 255 overflows into 0) and then incremented twice again.

Putting this Brainfuck code into our Syntax Analyzer we obtain the following AST (which is obtained by the prettyPrintStream() method in the AST class:

├── 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

Then we can continue to the Intermediate Code Generator:

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);
    }
}

Which generates this Intermediate AST:

├── 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

Next up is the Target Code Generator:

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);
    }
}

And the BFOptions class:

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);
        }
    }
}

Since the generated Target AST is really huge, you can find it on Pastebin.

And as last phase we have the Target Code Writer:

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();
    }
}

It generates the following ASM code which is available on Pastebin.

And then there's the BFCompiler class, to actually compile the x86 Assembly code into an executable:

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));
        }
    }
}

The ProcessUtils class:

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;
    }
}

And lastly here is the Main class, which also shows some usage of the other classes:

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);
    }
}

The full repository can be found on GitHub.

I would like a review on every aspect of the code, though I'll mention the following things of which I'm not entirely happy which may help you in writing a review:

  • The amount of Expression subclasses is probably a bad idea.
  • Writing all code with the Stream data structure in mind was probably a bad idea, using a List might have been clearer.
  • There is a lot of coupling between ASTNode and Expression which I dislike.
  • Lots of the constructors of different phases actually don't take any arguments.
  • There is quite a mess when resolving from one expression type into another, in particular:
    • From Stream<Token> to source expressions
    • From source expressions to intermediate expressions
    • From intermediate expressions to target expressions
    • From target expressions to Assembly lines

I'm not sure whether the resolving part should be handled in the Expression subclasses.

I am prepared for the mental impact of this code being ripped apart, but hey at least it produces the correct results.

\$\endgroup\$
2
  • 18
    \$\begingroup\$ I like this part - "I am prepared for the mental impact of this code being ripped apart" :) \$\endgroup\$
    – Thomas
    Nov 22, 2016 at 17:55
  • \$\begingroup\$ Bro, post it on Github. \$\endgroup\$
    – Jaumzera
    Jul 20, 2017 at 19:35

2 Answers 2

7
\$\begingroup\$

Your TargetCodeGenerator's generateAST has multiple abstraction levels embedded into one method.

And it's a long method.

It has all of these details that are pretty complex - when I see functionality like

    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))
        )))
    )));

go by, I start to skim instead of reading. What's up with all of these super detailed things?

What helps, of course, is this commment a bit up:

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

It's a header.

Before I go back and talk about the complexity of generateAST, let's take a quick look at that comment - it says "do not modify".

Who's the target audience for that comment? Probably just you. But you're also the person who (sort of) knows why that warning is there.

Have you considered turning your comments into functions?

    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);

I turned the bodies of the add child bits into ellipses.

I think the externNode and the dataSectionNode and the bssSectionNode could all be part of a addHeader method. Perhaps there being separate functions for creating such an externNode and dataSectionNode etc.

The rest probably goes into a createBody method - there is no footer, to be honest, because everything after the header goes into the textSectionNode. It seems to be something like defining calloc and a main method or something. I'd expect createBody to consider of lines like textSectionNode.addChild(createNodeForCalloc()). Of course, there has to be a body inside that too so maybe the createBody needs the intermediate AST.

What you don't want to see (which is what you have right now) is 70 lines (if not more, I just estimated) of code which look like the initialization code generated by those GUI tools that IDE's have. The sort of code you skim over without a second thought because it's auto generated.

And the main reason this is so important is because the compilation is hidden between all these steps.

Between all these fixed values/node creations is this line

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

And that's not a line that should be hidden because it's the actual code.

...

And maybe, when you split the code up into many small functions, you'll find a way to get rid of the duplication between adding Add and Mov operations. They both seem to take two arguments.

    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)))
    )));

Something to convert that into

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

Because then you get rid of the cruft and show the relevant code.


In short,

Write something that will create Expressions from Expressions, without you having to create ASTNodes by yourself. If you need the more complex structure you can create the ASTNodes but the ASTNodes seem like noise when defining a program.

Using the simplified manner of creating Expressions to generate code with, restructure the generateAST so it is easier to read and see what it does.

\$\endgroup\$
3
\$\begingroup\$

Things I changed (aka. TOC):

  • Separate the different ASTs from one another
  • Collapse ASTNode classes into enums where possible
  • Generify ASTNode and AST to take a <T extends AstExpression>
  • Implement the IntermediateCodeGenerator in terms of enum-based transformers

The code does (and can) not differentiate between intermediateAST, sourceAST and targetAST, because they are not differentiable by type.

To alleviate this, the first step is to make these two different. As such I introduced a generic parameter to ASTNode and AST, that is restricted to a subtype of 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;
    }
    // ...
}

That generic parameter should obviously be extended to AST


The AST node classes and instanceof checks can in very large parts be replaced by the following enums:

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;
    }
}

This significantly drops the amount of classes you have and it allows existing static analyzers to infer assumptions when handling the respective expressions. Especially useful are checks that "every enum member should be handled"


While we're at these instanceof checks: Now that we replaced these expressions with nicely named enums, we can change how the IntermediateCodeGenerator works:

We can abstract the process of mapping from SourceExpressions to IntermediateExpressions from the data required to perform said mapping.

Consider the following:

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);
}   

What we need for that to work is only the following definition for mappings:

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()));
}

Unfortunately, the target code generation doesn't benefit quite as much from the changes as the intermediate code generation. What we do gain, is the possibility to add a select case instead of chaining if-statements.


I may have done some other changes as well, but for the life of me I can't figure out what the heck I also changed in the 4.5kLoC diff I now have sitting around since ages

Do drop me a note if you want some of that :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.