Precedence Climbing in JavaCC

Precedence Climbing is described in Parsing Expressions by Recursive Descent.  Here we look at how to implement the highlighted part in JavaCC, namely, how to exit the loop.

Exp( p ) is
    var t : Tree
    t := P
    while next is a binary operator and prec(binary(next)) >= p
       const op := binary(next)
       consume
       const q := case associativity(op)
                  of Right: prec( op )
                     Left:  1+prec( op )
       const t1 := Exp( q )
       t := mkNode( op, t, t1)
    return t

Semantic lookahead looks like a nice solution.  Below is a sample implementation:

public ExprNode Expr(int p) :
{
    ExprNode expr, expr1;
    OpBinary op;
}
{
    (
        expr = ExprPrefix()
        (
            LOOKAHEAD({ nextBinaryOp() != null && 
                nextBinaryOp().getPrecedence() >= p })
            op = BinOp()
            expr1 = Expr(op.getAssoc() == OpBinary.Assoc.RIGHT ?
                op.getPrecedence() : op.getPrecedence() + 1)
            { expr = new ASTExprBinary(op, expr,  expr1); }
        )*
    )
    { return expr; }

} 

()* construct corresponds to the while loop.  Since this construct is a choice point, the false expression value in the LOOKAHEAD simply exits the loop.

We define nextBinaryOp() in the parser class as follows:

private OpBinary nextBinaryOp()
{
    return OpBinary.fromCode(getToken(1).kind);
}

getToken(1) does not modify the input stream and is equivalent to next in the original algorithm.

Definitions of ExprNode, OpBinary, ExprPrefix, BinOp and ASTExprBinary are omitted for brevity.