Numeric expression parser - calculator

Question

In particular, if someone could describe a better way to go from the tokenized list to the Expression tree, it would be super helpful. I would like to get rid of the casting in the parser but am not sure how.

Full code here

package org.bws.calc;

import java.util.ArrayList;

import org.bws.calc.exception.ParseException;
import org.bws.calc.expression.Expression;
import org.bws.calc.expression.ValueExpression;
import org.bws.calc.tokens.OpToken;
import org.bws.calc.tokens.Token;

public class SimpleParser implements Parsable{

    public Expression parse(ArrayList<Token> tokens){   
        if(tokens.size() == 1){
            Token t = tokens.get(0);
            try{
                int intVal = Integer.parseInt(t.getValue());
                return new ValueExpression(intVal);
            }catch(NumberFormatException nfe){
                throw new ParseException("expected int but found: "+t.getValue());
            }
        }

        Expression left;
        Expression right;

        int index=0;
        Token firstToken = tokens.get(index++);

        if("(".equals(firstToken.getValue())){
            int openParens =1;
            while(openParens > 0 ){
                if(index>tokens.size()-1){throw new ParseException("Missing right Parenthesis");}
                Token token = tokens.get(index);
                if("(".equals(token.getValue())){ ++openParens;}
                if(")".equals(token.getValue())){ --openParens;}
                ++index;
            }
            if(index == tokens.size()){
                return parse(new ArrayList<Token>(tokens.subList(1, index-1) ) );
            }
            left = parse(new ArrayList<Token>(tokens.subList(1,index-1)));

        }else{
            int tokenVal = Integer.parseInt(firstToken.getValue());
             left = new ValueExpression(tokenVal);
        }

        Token op = tokens.get(index);
        if(! (op instanceof OpToken) ){
            throw new ParseException("Invalid Syntax. expected Operator but found:"+op);
        }
        OpToken opToken = (OpToken) op;
        ++index;

        Token firstRightToken = tokens.get(index++);
        if("(".equals(firstRightToken.getValue() ) ){
            right = parse(new ArrayList<Token>(tokens.subList(index,tokens.size()-1)));         
        }else{
            int tokenVal = Integer.parseInt(firstRightToken.getValue());
            right = new ValueExpression(tokenVal);
        }

        return opToken.toExpression(left, right);
    }
}

Answer 1

Before I begin, let me say, it looks like a well engineered project. You've separated the work into a tokenizer, parser, and calculator, which is excellent. The unit tests were helpful as well. Congratulations.

---

Before you begin to write a parser, you should define the grammar, which you should state as a long comment in your parser's JavaDoc. From my interpretation of your code, I see the following productions:

EXPRESSION = BINARY_EXPRESSION |
             TERM

BINARY_EXPRESSION = EXPRESSION BINARY_OPERATOR TERM

BINARY_OPERATOR = "+" | "-"

TERM = VALUE_EXPRESSION |
       PARENTHESIZED_EXPRESSION

VALUE_EXPRESSION = number

PARENTHESIZED_EXPRESSION = "(" EXPRESSION ")"

You don't support unary minus (negative numbers). That's OK; we'll keep it simple for now.

---

It would be a good idea to add the following unit test:

@Test
public void evaluateThreeOperatorWithNoParens(){
        int result = c.evaluate("5-2+1");
        Assert.assertEquals(4,result);
}

If you had defined the grammar carelessly, such as the following…

EXPRESSION = VALUE_EXPRESSION |
             BINARY_EXPRESSION |
             PARENTHESIZED_EXPRESSION

VALUE_EXPRESSION = number

BINARY_EXPRESSION = EXPRESSION BINARY_OPERATOR EXPRESSION

BINARY_OPERATOR = "+" | "-"

PARENTHESIZED_EXPRESSION = "(" EXPRESSION ")"

… then it would be ambiguous whether "5-2+1" should be interpreted as (5-2)+1 or 5-(2+1). The evaluateThreeOperatorWithNoParens() test enforces the former interpretation.

---

The main problem is your handling of parentheses. Scanning the entire token list in advance to check for matching parentheses is inelegant; you should be able to detect such syntax errors as part of your parsing routine. Also, having four if-statements checking for opening/closing parentheses is a sign of confusion.

To enforce some structure to your parser, you should have a helper function for each production listed above.

Instead of taking .subList()s, I think it would be more elegant to use a ListIterator<Token> to keep track of your position. Also, there's no reason why your parser has to take an ArrayList, when any List<Token> would be acceptable.

Parsable is an odd name for the interface. I'd consider a string to be parsable. Therefore, I suggest breaking with the "-able" suffix convention and just call it a Parser. (Plenty of interfaces in the standard Java API aren't named with an "-able" suffix either.)

/**
 * (JavaDoc describing the grammar goes here.)
 */
public class SimpleParser implements Parser {

    public Expression parse(List<Token> tokens) {
        ListIterator<Token> tokenIter = tokens.listIterator();
        Expression expr = parseExpression(tokenIter);
        if (tokenIter.hasNext()) {
            throw new ParseException("Extra text after expression: " + tokenIter.next().getValue());
        }
        return expr;
    }

    private static Expression parseExpression(ListIterator<Token> tokenIter) {
        if (!tokenIter.hasNext()) {
            throw new ParseException("Premature end of expression");
        }

        Expression expr = parseTerm(tokenIter);
        while (tokenIter.hasNext()) {
            Token op = tokenIter.next();
            if (op instanceof OpToken) {
                expr = parseBinaryExpression(expr, (OpToken)op, tokenIter);
            } else {
                tokenIter.previous();
                break;
            }
        }
        return expr;
    }

    private static Expression parseBinaryExpression(Expression leftExpr, OpToken op, ListIterator<Token> tokenIter) {
        return op.toExpression(leftExpr, parseTerm(tokenIter));
    }

    private static Expression parseTerm(ListIterator<Token> tokenIter) {
        Token t = tokenIter.next();
        if ("(".equals(t.getValue())) {
            return parseParenthesizedExpression(tokenIter);
        } else {
            return parseValueExpression(t);
        }
    }

    private static Expression parseValueExpression(Token t) {
        try {
            int intVal = Integer.parseInt(t.getValue());
            return new ValueExpression(intVal);
        } catch (NumberFormatException nfe) {
            throw new ParseException("expected int but found: " + t.getValue());
        }
    }

    private static Expression parseParenthesizedExpression(ListIterator<Token> tokenIter) {
        Expression innerExpr = parseExpression(tokenIter);
        if (!tokenIter.hasNext() || !")".equals(tokenIter.next().getValue())) {
            throw new ParseException("Missing right parenthesis");
        }
        return innerExpr;
    }
}

Answer 2

There is a grammar that I wrote to handle C-like expressions. This is very similar to what 200_success talks about. One aspect of this grammar, it gives you the exact priority of the different operators. With this you can clearly see that the unary "+" has priority over the binary "+".

Also, since the multiplicative expression is called by the additive expression, the expression: 3 + 5 * 7 will properly be parsed as (5 * 7) + 3.

The easiest to write code to transform that grammar to a tree, is to write one function per rule (i.e. a rule is for example expr_list). All the choices of one rule can be handled in that one function. First you read a token from your lexer, then call the "start" function (in my case it would be expr() or something like that). The start function when calls the function of the previous level if it cannot match the current token to one of the tokens the current function is expecting. So the expr() function would call the assignment() function. The assignment() would call the conditional_expr(), etc. In other words, you use the CPU stack to help generate the tree.

When a token is matched, you go on with that possibility. If that possibility returns "false" in some way (i.e. that choice [a line represents a choice] did not match the following tokens) then drop it and try the next one. Once a whole choice was a match, you "reduce it", in other words, you create a node that represents it. For example, the IDENTIFIER in the unary_expr can be changed to a node of type "variable". And in the additive_expr, you would create an "add" node with two children (a left hand side and a right hand side.)

It is a little bit of work when you want to handle quite complete grammars. But that's the basics and how pretty much all proper compilers are built.

// expr_list
expr_list ::= expr
            | expr_list "," expr

// unary_expr
unary_expr ::= "!" unary_expr
             | "~" unary_expr
             | "+" unary_expr
             | "-" unary_expr
             | "(" expr_list ")"
             | IDENTIFIER "(" expr_list ")"
             | IDENTIFIER
             | keyword_true
             | keyword_false
             | STRING
             | INTEGER
             | FLOAT

// multiplicative_expr
multiplicative_expr ::= unary_expr
                      | multiplicative_expr "*" unary_expr
                      | multiplicative_expr "/" unary_expr
                      | multiplicative_expr "%" unary_expr

// additive_expr
additive_expr ::= multiplicative_expr
                | additive_expr "+" multiplicative_expr
                | additive_expr "-" multiplicative_expr

// shift_expr
shift_expr ::= additive_expr
             | shift_expr "<<" additive_expr
             | shift_expr ">>" additive_expr

// relational_expr
relational_expr ::= shift_expr
                  | relational_expr "<" shift_expr
                  | relational_expr "<=" shift_expr
                  | relational_expr ">" shift_expr
                  | relational_expr ">=" shift_expr
                  | relational_expr "<?" shift_expr
                  | relational_expr ">?" shift_expr

// equality_expr
equality_expr ::= relational_expr
                | equality_expr "==" relational_expr
                | equality_expr "!=" relational_expr

// bitwise_and_expr
bitwise_and_expr ::= equality_expr
                   | bitwise_and_expr "&" equality_expr

// bitwise_xor_expr
bitwise_xor_expr ::= bitwise_and_expr
                   | bitwise_xor_expr "^" bitwise_and_expr

// bitwise_or_expr
bitwise_or_expr ::= bitwise_xor_expr
                  | bitwise_or_expr "|" bitwise_xor_expr

// logical_and_expr
logical_and_expr ::= bitwise_or_expr
                   | logical_and_expr "&&" bitwise_or_expr

// logical_xor_expr
logical_xor_expr ::= logical_and_expr
                   | logical_xor_expr "^^" logical_and_expr

// logical_or_expr
logical_or_expr ::= logical_xor_expr
                  | logical_or_expr "||" logical_xor_expr

// conditional_expr
// The C/C++ definition is somewhat different:
// logical-OR-expression ? expression : conditional-expression
conditional_expr ::= logical_or_expr
                  | conditional_expr "?" expr ":" logical_or_expr

// assignment
// (this is NOT a C compatible assignment, hence I used ":=")
assignment ::= conditional_expr
             | TOKEN_ID_IDENTIFIER ":=" conditional_expr

// expr
expr ::= assignment