Writing an interpreter for a toy language in Java

Question

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

1. 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)
2. My class design/structure is appropriate and (more importantly) easily extensible if I want to add more features somewhere down the line
3. 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 BooleanExpressionASTs, 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.

Answer 1

You should rewrite your TokenType enum. I'd add a field raw (you might need to come up with a different name to better suit your needs) of type String. It would contain "+", "-", "*" and "/" for TokenType.OP_PLUS, OP_MINUS, OP_MUL and OP_DIV respectively. You could then have a Map<String, TokenType> to quickly look up the relevant TokenTypes and get rid of that huge switch.

I'd also structure your tokens differently. Instead of only having a TokenType I'd create specific interfaces for them. Say, for OP_EQ/GT/LT tokens. They in some way or another compare the parameters and alter them. You could have a interface ComparisonToken (symbolic name, feel free to come up with a better one) in which you'd have a method compare(ExpressionAST lhs, ExpressionAST rhs). That'd make your at least a little bit easier and allow you to simplify ComparisonExpressionAST's evaluate method. The same goes for OP_PLUS/MINUS/DIV/MUL.

In TokenStream in peek(int) you have the following code:

    try {
        return expression.substring(pos, pos + n);
    } catch (StringIndexOutOfBoundsException e) {
        return "";
    }

but you actually could (and IMO it would be better to) write

    return expression.substring(pos, Math.min(expression.length(), pos + n);

The same goes to next(int) (but remember to increment pos by Math.min(...), not n)

Answer 2

Overall your code makes a pretty good impression. Now I normally don't work with Java, so I won't say too much about that, but here's what I've got:

Tokenizer

• true and false are parsed too greedily: trueTypeFontSize + falseMarginOffset is parsed as [LIT_TRUE, IDENTIFIER("TypeFontSize"), OP_PLUS, LIT_FALSE, IDENTIFIER("MarginOffset")]
• Most methods in TokenStream should be private. Calling code shouldn't be able to mess with the parsing by advancing the stream, or by calling a token-specific method such as getNextInt when it's not appropriate to do so. Only getNextToken, peekNextToken, mark and rewind need to be public, the rest are implementation details.
• peekNextToken(int n) does not restore pos if getNextToken throws an exception.
• Besides spaces, you may also want to ignore (or otherwise handle) other whitespace characters, such as tabs and newlines. Replacing the while (peek() == ' ') next(); part with a skipWhitespace method call should make that a little easier and more self-descriptive, too.

Lexer

• Similar to Tokenizer, Lexer should hide its implementation details. programLine is probably the only method that should be public.
• programLine is not a very descriptive name. parseProgramLine sounds a little better. 'line' may not be very accurate however (depending on whether you support multiple expressions per line), so maybe parseNextExpression is better still. Most method names here are missing a verb.
• I'd move assignment-parsing out of programLine into a separate parseAssignment method.
• Assignments behave as expressions (they return the assigned value), so the lexer could treat them as any other expression, which would allow things like a :- b :- 4.
• Lexer is almost always calling peekNextToken before getNextToken. Because of how token peeking is implemented this results in twice as much parsing work. It's better to cache peeked tokens.
• Some lexer method names are a little confusing. For example, singleBool can return complex boolean expressions, and minTerms and boolExpression are actually used to handle && and || precedence.
• The lexer seems to perform some kind of type checking. But it doesn't have sufficient information to do so: is a a boolean or a math expression? You don't know unless you inspect the context in which it appears.
• Since type checking at this stage isn't very useful, you could unify boolean and math expressions. Both a == b and 4 + 5 would be binary expressions. This should simplify the parsing code a lot. Type checking can be done after parsing is complete, or even at runtime, depending on how you want your language to work.

AST

• I'd expect evaluate to take some kind of context argument. Right now, assignments use a ScopeManager, which looks like it's static/global, so that probably limits your language to a single global scope.
• I don't think reusing TokenType for operators is a good idea, because many languages tend to have symbols with context-specific meanings. For example, a < token may be interpreted as a less-than operator, but some languages also use it for generic parameter syntax. Also, things like TokenType.IDENTIFIER and TokenType.EOF aren't valid operators.

Other

• Putting else bodies on the same line (else return expression();) makes code harder to read.
• Some people always surround single-line if and else bodies with braces. Personally I'm not that strict about it (I just add braces when I add another line), but seeing an if body with braces and its else body without does look inconsistent.
• It would be useful to document the grammar of your language.
• I don't know if you're using automated tests, but doing so shouldn't be too difficult and probably pays off fairly quick.
• It may be useful to have some test that pass randomly generated strings to your tokenizer, or randomly generated lists of tokens to your lexer, to increase the chance of spotting broken edge-cases (fuzzing).