I am working on a project that involves me writing an interpreter for a small toy language in Java, and while I intend to build it into a fully featured programming language at some point, it is currently in its very early stages (I have only implemented parsing complex mathematical expressions and boolean expressions involving <
, >
, =
, and AND
OR
NOT
, as well as a very rudimentary way of storing values in variables). My code seems to be increasing in complexity very rapidly, and before I continue on to implementing IF
statements, loops, and functions, I want to make sure that
- I am following good programming practice (I'm not new at Java but its been a while and I usually code in python so I am likely to miss idiomatic ways of doing things)
- My class design/structure is appropriate and (more importantly) easily extensible if I want to add more features somewhere down the line
- I'm handling the actual logic (tokenizing, parsing, building syntax trees, etc.) the correct way. My interpreter works right now for what it is supposed to do, but I want to make sure I am doing things the right way so that in the future it is easy for me to expand it.
The codebase itself consists of 22 classes which is a ridiculous number to copy/paste into here, so I figured I'd just share the relevant/important ones and then provide a quick description of the others. If code from the other classes is relevant, I can edit this to include them.
Without further ado, here is the tokenizer class (TokenStream.java
):
public class TokenStream {
private String expression;
private int pos;
private int saved;
public TokenStream(String exp) {
expression = exp;
pos = 0;
}
/**
* Peek at the next character without incrementing the position counter
* @return The next character in the stream
*/
public char peek() {
if (pos == expression.length())
return 0;
return expression.charAt(pos);
}
/**
* Peek at the next `n` characters without incrementing the position counter
* @param n (Number of characters to peek)
* @return A string of the next `n` characters
*/
public String peek(int n) {
try {
return expression.substring(pos, pos + n);
} catch (StringIndexOutOfBoundsException e) {
return "";
}
}
/**
* Read and return the next character from the stream
* @return the next character in the stream
*/
public char next() {
return expression.charAt(pos++);
}
/**
* Read the next `n` characters from the stream
* @param n (Number of characters to read)
* @return a string of the next `n` characters
*/
public String next(int n) {
try {
String r = expression.substring(pos, pos + n);
pos += n;
return r;
} catch (StringIndexOutOfBoundsException e) {
return "";
}
}
/**
*
* @return the next integer token in the stream
*/
public Token getNextInt() {
int result = 0;
while(peek() != 0 && Character.isDigit(peek())) {
result *= 10;
result += next() - '0';
}
return new Token(result);
}
/**
*
* @return the next identifier token in the stream
*/
public Token getNextIdentifier() {
StringBuilder id = new StringBuilder();
while(peek() != 0 && Character.isAlphabetic(peek()))
id.append(next());
return new Token(id.toString());
}
/**
*
* @return the next operator token
* @throws IllegalTokenException if the next token is not recognized by the parser
*/
public Token getNextOperator() throws IllegalTokenException {
// Start by looking for the longest operator
TokenType type;
if (peek(2).equals(":-")) {
next(2);
type = TokenType.OP_ASSIGN;
} else if (peek(2).equals("&&")) {
next(2);
type = TokenType.OP_AND;
} else if (peek(2).equals("||")) {
next(2);
type = TokenType.OP_OR;
} else {
switch(peek()) {
case '+':
type = TokenType.OP_PLUS;
break;
case '-':
type = TokenType.OP_MINUS;
break;
case '*':
type = TokenType.OP_MUL;
break;
case '/':
type = TokenType.OP_DIV;
break;
case '(':
type = TokenType.LPAREN;
break;
case ')':
type = TokenType.RPAREN;
break;
case '~':
type = TokenType.OP_NOT;
break;
case '>':
type = TokenType.OP_GT;
break;
case '<':
type = TokenType.OP_LT;
break;
case '=':
type = TokenType.OP_EQ;
break;
case 0:
type = TokenType.EOF;
break;
default:
throw new IllegalTokenException("Unexpected token: " + (int)peek());
}
next();
}
return new Token(type);
}
/**
* @return the next token in the stream
* @throws IllegalTokenException if the next token is not recognized by the parser
*/
public Token getNextToken() throws IllegalTokenException {
try {
while (peek() == ' ')
next();
if (peek(5).equals("false")) {
next(5);
return new Token(TokenType.LIT_FALSE);
} else if (peek(4).equals("true")) {
next(4);
return new Token(TokenType.LIT_TRUE);
}
if (Character.isDigit(peek()))
return getNextInt();
else if (Character.isAlphabetic(peek()))
return getNextIdentifier();
else
return getNextOperator();
} catch (StringIndexOutOfBoundsException e) {
return new Token(TokenType.EOF);
}
}
/**
*
* @return the next token in the stream without advancing the pointer
* @throws IllegalTokenException if the next token is not recognized by the parser
*/
public Token peekNextToken() throws IllegalTokenException {
return peekNextToken(1);
}
/**
*
* @param n (Number of tokens to peek ahead)
* @return the next nth toke in the stream without advancing the pointer
* @throws IllegalTokenException if any of the next tokens are not recognized by the parser
*/
public Token peekNextToken(int n) throws IllegalTokenException {
int position = pos;
Token t = null;
while(n-->0)
t = getNextToken();
pos = position;
return t;
}
/**
* Save the current position in the token stream (can be returned to with rewind())
*/
public void mark() {
saved = pos;
}
/**
* Rewind the token stream to the position saved by the last call to mark()
*/
public void rewind() {
pos = saved;
}
}
Here is the parser class (Lexer.java
):
public class Lexer {
private TokenStream stream;
public Lexer(String expression) {
stream = new TokenStream(expression);
}
public static void die(String message) {
System.out.println("Fatal error: " + message);
System.exit(0);
}
/**
*
* @return an AST representing a single term being multiplied (either an atom or an expression enclosed in parentheses)
*/
public MathematicalExpressionAST factor() {
MathematicalExpressionAST res = null;
try {
if (stream.peekNextToken().type == TokenType.OP_PLUS || stream.peekNextToken().type == TokenType.OP_MINUS)
res = new MathematicalExpressionAST(stream.getNextToken().type, factor());
else if (stream.peekNextToken().type == TokenType.LPAREN) {
stream.getNextToken(); // consume the lparen
res = mathExpression();
if (stream.peekNextToken().type != TokenType.RPAREN)
die("Missing RPAREN!");
stream.getNextToken(); // consume the rparen
} else if (stream.peekNextToken().type == TokenType.IDENTIFIER)
res = new MathematicalExpressionAST(new MathAtomAST(stream.getNextToken().id));
else if (stream.peekNextToken().type == TokenType.INTEGER)
res = new MathematicalExpressionAST(new MathAtomAST((double) stream.getNextToken().value));
else
die("Unexpected token ".concat(stream.peekNextToken().type.name()));
} catch (IllegalTokenException e) {
die(e.getMessage());
}
return res;
}
/**
*
* @return an AST representing a product of atomic terms
*/
public MathematicalExpressionAST term() {
MathematicalExpressionAST res = factor();
try {
while(stream.peekNextToken().type == TokenType.OP_MUL ||
stream.peekNextToken().type == TokenType.OP_DIV) {
res = new MathematicalExpressionAST(stream.getNextToken().type, res, term());
}
} catch (IllegalTokenException e) {
die(e.getMessage());
}
return res;
}
/**
*
* @return an AST representing a sum of terms
*/
public MathematicalExpressionAST mathExpression() {
MathematicalExpressionAST res = term();
try {
while(stream.peekNextToken().type == TokenType.OP_PLUS ||
stream.peekNextToken().type == TokenType.OP_MINUS) {
res = new MathematicalExpressionAST(stream.getNextToken().type, res, mathExpression());
}
} catch (IllegalTokenException e) {
die(e.getMessage());
}
return res;
}
/**
*
* @return an AST representing a single boolean value (either a literal or a comparison expression)
*/
public BooleanExpressionAST singleBool() {
BooleanExpressionAST res = null;
try {
if (stream.peekNextToken().type == TokenType.OP_NOT)
res = new BooleanExpressionAST(stream.getNextToken().type, singleBool());
else if (stream.peekNextToken().type == TokenType.LPAREN) {
stream.getNextToken(); // Consume the LPAREN
res = boolExpression();
if (stream.peekNextToken().type != TokenType.RPAREN)
die("Missing RPAREN!");
stream.getNextToken(); // Consume the RPAREN
}
else if (stream.peekNextToken().type == TokenType.LIT_TRUE ||
stream.peekNextToken().type == TokenType.LIT_FALSE)
res = new BooleanExpressionAST(new BoolAtomAST(stream.getNextToken().type == TokenType.LIT_TRUE));
else {
MathematicalExpressionAST lhs = mathExpression();
TokenType op = stream.getNextToken().type;
if (!((op == TokenType.OP_EQ) || (op == TokenType.OP_GT) || (op == TokenType.OP_LT)))
throw new AssertionError();
MathematicalExpressionAST rhs = mathExpression();
res = new ComparisonExpressionAST<Double>(op, lhs, rhs);
}
return res;
} catch (IllegalTokenException e) {
die(e.getMessage());
}
return res;
}
/**
*
* @return an AST representing a 'minterm'
*/
public BooleanExpressionAST minterms() {
BooleanExpressionAST res = singleBool();
try {
while (stream.peekNextToken().type == TokenType.OP_AND)
res = new BooleanExpressionAST(stream.getNextToken().type, res, minterms());
} catch (IllegalTokenException e) {
die(e.getMessage());
}
return res;
}
/**
*
* @return an AST representing a maxterm of minterms, or a boolean expression
*/
public BooleanExpressionAST boolExpression() {
BooleanExpressionAST res = minterms();
try {
while (stream.peekNextToken().type == TokenType.OP_OR)
res = new BooleanExpressionAST(stream.getNextToken().type, res, boolExpression());
} catch (IllegalTokenException e) {
die(e.getMessage());
}
return res;
}
/**
* Try to parse a boolean expression; if it fails parse a math expression
* @return either BooleanExpressionAST or MathematicalExpressionAST
*/
public ExpressionAST<?> expression() {
try {
stream.mark();
return boolExpression();
} catch (AssertionError e) {
stream.rewind();
return mathExpression();
}
}
/**
*
* @return an AST representing either a variable assignment (if it exists) or a mathematical or boolean
* expression
*/
public AST programLine() {
try {
if (stream.peekNextToken(2).type == TokenType.OP_ASSIGN) {
if (stream.peekNextToken().type != TokenType.IDENTIFIER)
die("Invalid identifier: " + stream.peekNextToken().type.name());
String id = stream.getNextToken().id;
stream.getNextToken(); // consume the assignment operator
ExpressionAST<?> exp = expression();
return new AssignmentAST(id, exp);
} else return expression();
} catch (IllegalTokenException e) {
die(e.getMessage());
}
return null;
}
}
I have public interface AST
which declares a single evaluate()
method; the following classes implement AST
:
AssignmentAST
: represents code that assigns a value to a variable
public class AssignmentAST implements AST {
String lhs;
ExpressionAST<?> rhs;
/**
*
* @param id The identifier used to refer to this variable
* @param val An abstract syntax tree that evaluates to the value to be stored
*/
public AssignmentAST(String id, ExpressionAST<?> val) {
lhs = id;
rhs = val;
}
/**
* Allocate the necessary space in the symbol table for the current scope, and
* associate the value to the given identifier
*/
@Override
public GenericType<?> evaluate() throws IllegalOperatorException {
GenericType<?> value = rhs.evaluate();
ScopeManager.createLocalVariable(lhs, value);
return value;
}
}
ExpressionAST
: Represents an expression that evaluates to a single value. This is an abstract class, and is subclassed by MathematicalExpressionAST
and BooleanExpressionAST
which differ only in the operators implemented in the overridden evaluate()
method.
public abstract class ExpressionAST <T> implements AST {
protected ExpressionAST<T> left, right;
protected TokenType operator;
protected AtomicAST<T> singleValue;
public ExpressionAST() {
}
/**
*
* @param op operator
* @param lhs expression on the left
* @param rhs expression on the right
*
* Expression consisting of a binary operator
*/
public ExpressionAST(TokenType op, ExpressionAST<T> lhs, ExpressionAST<T> rhs) {
left = lhs;
right = rhs;
operator = op;
}
/**
*
* @param op operator
* @param arg argument to the operator (right side)
*
* Expression consisting of a unary operator
*/
public ExpressionAST(TokenType op, ExpressionAST<T> arg) {
left = null;
right = arg;
operator = op;
}
/**
*
* @param val atomic value
*
* Expression consisting of no operators and just a single value
*/
public ExpressionAST(AtomicAST<T> val) {
singleValue = val;
left = null;
right = null;
}
/**
* Reduce and evaluate the expression to result in a single generic atomic value
* Each subclass that derives ExpressionAST must provide a customized implementation for this method that
* supports the related operator set.
*/
public abstract GenericType<T> evaluate() throws IllegalOperatorException;
}
ComparisonExpressionAST
subclasses BooleanExpressionAST
and implements the specific syntax of [math_expr] GT|LT|EQ [math_expr] which is not covered by BooleanExpressionAST
:
public class ComparisonExpressionAST<T extends Comparable<T>> extends BooleanExpressionAST {
private ExpressionAST<T> left, right;
private TokenType operator;
public ComparisonExpressionAST(TokenType op, ExpressionAST<T> lhs, ExpressionAST<T> rhs) {
operator = op;
left = lhs;
right = rhs;
}
public ComparisonExpressionAST(TokenType op, ExpressionAST<T> arg) {
op = operator;
right = arg;
}
/**
* Implemented three comparison operators (=, <, >) to reduce a pair of expressions to a single boolean
*/
@Override
public GenericType<Boolean> evaluate() throws IllegalOperatorException {
switch(operator) {
case OP_EQ:
return new GenericType<Boolean>(left.evaluate().getValue().equals(right.evaluate().getValue()));
case OP_LT:
return new GenericType<Boolean>(left.evaluate().getValue().compareTo(right.evaluate().getValue()) < 0);
case OP_GT:
return new GenericType<Boolean>(left.evaluate().getValue().compareTo(right.evaluate().getValue()) > 0);
default:
return null;
}
}
}
GenericType<T>
is a tiny class I wrote to "box" variable types so that I don't have to know what kind of an AST
it is, just that it has to be evaluated. I'm not sure that this is the best way to do it, but I couldn't think of anything else that maintains that level of abstraction.
I'm also slightly uncomfortable with how complicated the ComparisonExpressionAST
class got, but it doesn't really fit into the BooleanExpressionAST
because that deals with operators whose arguments are also BooleanExpressionAST
s, whereas ComparisonExpressionAST
takes MathExpressionAST
arguments.
Finally, the expression()
method in my Lexer.java
class currently just tries to evaluate a boolean expression and if it doesn't work it tries to get a math expression; the boolean expression class tries to parse a single boolean and if it doesn't work, it tries to find a comparison. I don't like this "guess and check" approach but I don't know how else to do it, because I can't just look ahead in the token stream as I wouldn't know how many tokens to look ahead.
Any and all advice you can give me would be greatly appreciated.