Code skeleton for hand write LL parser, with arbitrary lookahead buffer.

LLStarParser.java

/**
 * 
 * This is the code skeleton for arbitrary-lookahead LL parser. Look ahead tokens are cached.
 * 
 */
public class ActionParser {
    private ActionLexer lexer;

    // buffered tokens that were look-ahead
    private List<ActionToken> aheadBuffer = new ArrayList<ActionToken>();
    // current token in buffer position, -1 when no tokens in buffer
    private int p = -1;

    public ActionParser(ActionLexer lexer) {
        this.lexer = lexer;
    }

    // TODO your recursive decent parsing methods goes here... 

    /**
     * 
     * match a token by tokenType, actually consumes a token
     * 
     * @param type
     * @return the matched token
     */
    public ActionToken match(ActionTokenType type) {
        ActionToken t = this.nextToken();
        if (t.getType() != type) {
            throw new ActionException("Unexpected token: " + t + ", " + type + " expected.");
        } else {
            return t;
        }
    }

    // lookahead by 'ahead', cache tokens in buffer while lookahead
    private ActionToken LT(int ahead) {
        Iterator<ActionToken> it = lexer.iterator();
        if (p == -1) {
            // should load from lexer until 'ahead'
            for (int i = 0; i < ahead; i++) {
                aheadBuffer.add(it.next());
            }
            p = 0;
        } else {
            if (p + ahead > aheadBuffer.size()) {
                /*
                 * should load from lexer until the look-ahead token is in
                 * buffer
                 */
                int more = p + ahead - aheadBuffer.size();
                for (int i = 0; i < more; i++) {
                    aheadBuffer.add(it.next());
                }
            }
        }
        return aheadBuffer.get(p + ahead - 1);
    }

    // if there's tokens buffered, try to read the buffer first
    private ActionToken nextToken() {
        Iterator<ActionToken> it = lexer.iterator();
        if (p == -1) {
            if (it.hasNext()) {
                return it.next();
            } else {
                throw new ActionException("No more token.");
            }
        } else {
            ActionToken ret = aheadBuffer.get(p);
            if (p == aheadBuffer.size() - 1) {
                // last one in buffer
                p = -1;
                aheadBuffer.clear();
            } else {
                p += 1;
            }
            return ret;
        }
    }
}