LL(1) parser example for a simple context-free language

Main.java

/*
Original grammer:
EXPR -> FIRST_ITEM | EXPR '+' ITEM | EXPR '-' ITEM
ITEM -> VALUE | ITEM '*' VALUE | ITEM '/' VALUE
FIRST_ITEM -> FIRST_VALUE | FIRST_ITEM '*' VALUE | FIRST_ITEM '/' VALUE
VALUE -> number | '(' EXPR ')'
FIRST_VALUE -> VALUE | '-' VALUE

Modified grammer to be LL(1)
EXPR -> ITEM EXPRSUFFIX | '-' ITEM EXPRSUFFIX
EXPRSUFFIX -> ε | '+' ITEM EXPRSUFFIX | '-' ITEM EXPRSUFFIX
ITEM -> ELEM ITEMSUFFIX
ITEMSUFFIX -> ε | '*' ELEM ITEMSUFFIX | '/' ELEM ITEMSUFFIX
ELEM -> number | '(' EXPR ')'

NOTE: All left-bounded ops become right-bounded, so we need to use lazy-evaluation
*/

import java.util.Stack;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class FormulaException extends Exception {}
class ZeroException extends Exception {}

/** A terminator or a non-terminator of a context-free grammar */
abstract class Token
{
    Token children[] = {};

    /** Construct parse tree */
    abstract void parse(StringBuffer input) throws FormulaException;

    /** Evaluate, given result from the left side */
    abstract double eval(double init) throws ZeroException;

    static double evalExpr(String input) throws FormulaException, ZeroException
    {
        if (input.contains("$"))
            throw new FormulaException();
        StringBuffer buffer = new StringBuffer(input + "$");
        Stack<Token> stack = new Stack<>();
        Expr expr = new Expr();
        stack.push(expr);
        while (!stack.isEmpty())
        {
            Token t = stack.pop();
            t.parse(buffer);
            for (int i = t.children.length - 1; i >= 0; i--)
                stack.push(t.children[i]);
        }
        if (!buffer.toString().equals("$"))
            throw new FormulaException();
        return expr.eval(0);
    }
}

class Expr extends Token
{
    @Override
    void parse(StringBuffer input)
    {
        switch (input.charAt(0))
        {
            case '-':
                children = new Token[]{ new Terminator("\\-"), new Item(), new ExprSuff() };
                break;
            default:
                children = new Token[]{ new Item(), new ExprSuff() };
        }
    }

    @Override
    double eval(double init) throws ZeroException
    {
        if (children.length == 3)
            return children[2].eval(-children[1].eval(0));
        else
            return children[1].eval(children[0].eval(0));
    }
}

class ExprSuff extends Token
{
    private char op;

    @Override
    void parse(StringBuffer input)
    {
        switch (input.charAt(0))
        {
            case '+':
                op = '+';
                children = new Token[]{ new Terminator("\\+"), new Item(), new ExprSuff() };
                break;
            case '-':
                op = '-';
                children = new Token[]{ new Terminator("\\-"), new Item(), new ExprSuff() };
                break;
            default:
                // empty string
        }
    }

    @Override
    double eval(double init) throws ZeroException
    {
        if (children.length == 0)
            return init;
        return children[2].eval(op == '+' ? init + children[1].eval(0) : init - children[1].eval(0));
    }
}

class Item extends Token
{
    @Override
    void parse(StringBuffer input)
    {
        children = new Token[]{ new Elem(), new ItemSuff() };
    }

    @Override
    double eval(double init) throws ZeroException
    {
        return children[1].eval(children[0].eval(0));
    }
}

class ItemSuff extends Token
{
    private char op;

    @Override
    void parse(StringBuffer input)
    {
        switch (input.charAt(0))
        {
            case '*':
                op = '*';
                children = new Token[]{ new Terminator("\\*"), new Elem(), new ItemSuff() };
                break;
            case '/':
                op = '/';
                children = new Token[]{ new Terminator("\\/"), new Elem(), new ItemSuff() };
                break;
            default:
                // empty string
        }
    }

    @Override
    double eval(double init) throws ZeroException
    {
        if (children.length == 0)
            return init;
        double cur = children[1].eval(0);
        if (op == '/' && cur == 0)
            throw new ZeroException();
        return children[2].eval(op == '*' ? init * cur : init / cur);
    }
}

class Elem extends Token
{
    @Override
    void parse(StringBuffer input)
    {
        switch (input.charAt(0))
        {
            case '(':
                children = new Token[]{ new Terminator("\\("), new Expr(), new Terminator("\\)") };
                break;
            default:
                children = new Token[]{ new NumberToken() };
        }
    }

    @Override
    double eval(double init) throws ZeroException
    {
        return children.length == 3 ? children[1].eval(0) : children[0].eval(0);
    }
}

class Terminator extends Token
{
    private final Pattern pattern;
    String content = null;

    Terminator(String _regex)
    {
        pattern = Pattern.compile("^" + _regex);
    }

    @Override
    void parse(StringBuffer input) throws FormulaException
    {
        Matcher m = pattern.matcher(input);
        if (!m.find())
            throw new FormulaException();
        content = m.group(0);
        input.delete(0, content.length());
    }

    @Override
    double eval(double init) throws ZeroException { return Double.NaN; }
}

class NumberToken extends Terminator
{
    NumberToken()
    {
        super("(0|[1-9][0-9]*)(\\.[0-9]+)?");
    }

    @Override
    double eval(double init) throws ZeroException
    {
        return Double.parseDouble(content);
    }
}

class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        try
        {
            double ans = Token.evalExpr(scanner.nextLine().trim());
            System.out.printf("%.2f\n", ans);
        } catch (FormulaException e)
        {
            System.out.println("FormulaException");
        } catch (ZeroException e)
        {
            System.out.println("ZeroException");
        }
    }
}