Parsing Expressions in Java
by Cliff Berg

Figure 1:
     
Expression        : Term TermOp ;

TermOp            : Plus Term TermOp
                  | Hyphen Term TermOp
                  | ;

Term              : Factor FactorOp ;

FactorOp          : Asterisk Factor FactorOp
                  | Slash Factor FactorOp
                  | ;

Factor            : Primary PrimaryOp ;

PrimaryOp         : OpenParen EList CloseParen PrimaryOp
                  | ;

Primary           : Ident
                  | NumericLiteral
                  | OpenParen Expression CloseParen
                  | SignedExpression ;

IntExpression     : Expression ;

Selector          : Ident ;

SignedExpression  : Hyphen Primary
                  | Plus Primary ;

EList             : Expression MoreEList 
                  | ;

MoreEList         : Comma Expression MoreEList
                  | ;

NumericLiteral    : IntLiteral 
                  | FloatLiteral ;


Figure 2:

Primary         : Ident
                | Literal
                | OpenParen Expression CloseParen
                | SignedExpression ;


Figure 3:

TermOp          : Plus Term TermOp
                | Hyphen Term TermOp
                | ;    // null


Listing One
public interface Lexer
{
    public Token getNextToken() throws LexicalException;
    public String getTokenValue();
}


Listing Two
public interface Token
{
    public String getValue();
    public int getTokenKind();
}

Listing Three
public interface SymbolInstance
{
}
public abstract class Expression
implements SymbolInstance
{
    public abstract String toString();
    public void setType(Type t) { type = t; }
    public Type getType() { return type; }
    public Object evaluate(EvaluationContext evaluation_context) 
    { return null; }
    public void setSyntacticallyGrouped(boolean b) { sg = b; }
    public boolean syntacticallyGrouped() { return sg; }
    private boolean sg = false;
    private Type type;
}

Listing Four
Expression 
    IdentExpression
    LiteralExpression 
        NumericLiteralExpression 
            IntegerLiteralExpression
            FloatLiteralExpression
    FunctionCallExpression
    ArithmeticExpression 
        TermExpression
        FactorExpression
    SignedExpression

Listing Five
protected void push(Expression ex)
{
    stack.insertElementAt(ex, 0);
}
protected Expression pop()
{
    Expression e = (Expression)(stack.elementAt(0));
    stack.removeElementAt(0);
    return e;
}


Listing Six
public interface Type
{
    public boolean isInstanceOf(Type t);
}
public interface Symbol
{
    public String getName();
    public void setType(Type t);
    public Type getType();
}
public interface Region
{
    public Symbol lookup(String identifier);
    public Region getContainingRegion();
    public abstract Symbol createNewSymbol(String s);
}


Listing Seven
private static final int[][] first = 
{
    { k_NONE },
    { k_IntLiteral },
    { k_FloatLiteral },
    { k_Ident },
    { k_Asterisk },
    { k_Slash },
    { k_Plus },
    { k_Hyphen },
    { k_OpenParen },
    { k_CloseParen },
    { k_Comma },

    // k_Expression:
    { k_IntLiteral, k_FloatLiteral, k_Plus, k_Hyphen, 
        k_Ident, k_OpenParen },
    // k_Term:
    { k_FloatLiteral, k_IntLiteral, k_Hyphen, k_Plus, 
        k_OpenParen, k_Ident },
    // k_TermOp:
    { k_NONE, k_Hyphen, k_Plus },
    // k_Factor:
    { k_IntLiteral, k_FloatLiteral, k_Plus, k_Hyphen, 
        k_Ident, k_OpenParen },
    // k_FactorOp:
    { k_NONE, k_Slash, k_Asterisk },
    // k_Primary:
    { k_FloatLiteral, k_IntLiteral, k_Hyphen, k_Plus, 
        k_OpenParen, k_Ident },
    // k_PrimaryOp:
    { k_NONE, k_OpenParen },
    // k_EList:
    { k_FloatLiteral, k_IntLiteral, k_Hyphen, k_Plus, 
        k_OpenParen, k_Ident, k_NONE },
    // k_NumericLiteral:
    { k_FloatLiteral, k_IntLiteral },
    // k_SignedExpression:
    { k_Plus, k_Hyphen },
    // k_IntExpression:
    { k_FloatLiteral, k_IntLiteral, k_Hyphen, k_Plus, 
        k_OpenParen, k_Ident },
    // k_MoreEList:
    { k_NONE, k_Comma }
};


Listing Eight
protected static boolean tokenIsInFirstOf(int termkind, int symkind)
{
    int[] firstSet = first[symkind];
    for (int i = 0; i < firstSet.length; i++)
    {
        if (termkind == firstSet[i]) return true;
    }
    return false;
}

Listing Nine
protected void parse_Expression()
throws ParseException, LexicalException
{
    if (tokenIsInFirstOf(getTokenKind(), k_Term))
    {
        parse_Term();
        parse_TermOp();
        return;
    }
    throw createSyntacticException(k_Expression);
}

Listing Ten
protected void parse_TermOp()
throws ParseException, LexicalException
{
    if (tokenIsInFirstOf(getTokenKind(), k_Plus))
    {
        parse_Plus();
        parse_Term();
            
        TermExpression e = new TermExpression();
        Expression rhs = pop();
        Expression lhs = pop();
        e.setLHS(lhs);
        e.setRHS(rhs);
        e.setAdditive(true);
        e.setType(resolveType(lhs.getType(), PLUS, rhs.getType()));
        push(e);

        parse_TermOp();
        return;
    }
    if (tokenIsInFirstOf(getTokenKind(), k_Hyphen))
    {
        parse_Hyphen();
        // ...same as for k_Plus...
        e.setAdditive(false);
        // ...same as for k_Plus...
    }
    // Handle the null production case
    {
        if (getTokenKind() == k_NONE) wasReducing(k_TermOp);
        return;
    }
}

Listing Eleven
protected void parse_Ident()
throws ParseException, LexicalException
{
    if (getTokenKind() != k_Ident) throw createSyntacticException(k_Ident);
    IdentExpression e = new IdentExpression();

    Symbol s = null;
    try
    {
        s = resolve(getCurrentRegion(), getTokenValue(), false);
        e.setSymbol(s);
        e.setType(s.getType());
    }
    catch (UnresolvedSymbolException ex1)
    {
        // Symbol not found - that's ok at this level
    }
    catch (SymbolConflictException ex2)
    {
        throw new RuntimeException("Should not happen");
    }
    getNextToken();
    push(e);
    return;
}



6