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 pseudocodeaddmemorycell(3)
,<<<
byaddpointer(-3)
,[-]
bysetmemorycell(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 aList
might have been clearer. - There is a lot of coupling between
ASTNode
andExpression
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
- From
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.