parse.java

To help you in writing an LL grammar, we have developed a tool to analyze a grammar and determine if

// LLAnalyze -- Nathaniel Nystrom, February 2000
// For use in Cornell University Computer Science 412/413

// Parse the grammar file.  This is structured as a recursive-descent parser.

package Iota.util.grammar;

import java.io.*;
import java.util.*;

public class Parse
{
    Yylex yy;
    Yytoken lookahead;
    IntMap terms;
    IntMap nonterms;
    Set termSet;
    Set nontermSet;
    Nonterminal start;
    List rules;

    public Parse(InputStream in)
    {
	yy = new Yylex(in);
	terms = new IntMap();
	nonterms = new IntMap();
	termSet = new HashSet();
	nontermSet = new HashSet();
	start = null;
	rules = new LinkedList();
    }

    public Grammar parse() throws IOException
    {
	lookahead = yy.yylex();

        if (lookahead == null) {
            die(yy.yyline() + ": Parse error: unexpected EOF");
	    throw new RuntimeException();
        }

	List rules;

	switch (lookahead.index) {
	    case Yytoken.SEPSTART:
	    case Yytoken.SEPTOKEN:
		parse_Decls();
		match(Yytoken.SEPSEP);
		rules = parse_Rules();
		break;
	    case Yytoken.SEPSEP:
		match(Yytoken.SEPSEP);
		rules = parse_Rules();
		break;
	    default:
		die(yy.yyline() +
		  ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}

	return new Grammar(start, rules, termSet, nontermSet);
    }

    private void parse_Decl() throws IOException
    {
	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.SEPTOKEN:
		parse_Token();
		break;
	    case Yytoken.SEPSTART:
		parse_Start();
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead); 
		throw new RuntimeException();
	}
    }

    private void parse_Decls() throws IOException
    {
	switch (lookahead.index) {
	    case Yytoken.SEPTOKEN:
	    case Yytoken.SEPSTART:
		parse_Decl();
		parse_Decls();
		break;
	}
    }

    private Expr parse_Expr() throws IOException
    {
	Expr result;
	List exprs;
	int mod;
	int index;

	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.ID:
		index = terms.lookup(lookahead.text);

		if (index < 0) {
		    index = nonterms.insert(lookahead.text);
		    result = new Nonterminal(lookahead.text, index);
		    nontermSet.add(result);
		}
		else {
		    result = new Terminal(lookahead.text, index);
		}
		match(Yytoken.ID);
		break;
	    case Yytoken.LPAREN:
		match(Yytoken.LPAREN);

		exprs = parse_Exprs();

		match(Yytoken.RPAREN);

		mod = parse_Mod();

		if (mod == Yytoken.STAR) {
		    result = new Star(exprs);
		}
		else {
		    result = new Plus(exprs);
		}

		break;
	    case Yytoken.LBRACKET:
		match(Yytoken.LBRACKET);

		exprs = parse_Exprs();

		match(Yytoken.RBRACKET);

		result = new Question(exprs);

		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}

	return result;
    }

    private List parse_Exprs() throws IOException
    {
	List exprs = new LinkedList();
	Expr e;

	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.ID:
	    case Yytoken.LPAREN:
	    case Yytoken.LBRACKET:
		e = parse_Expr();
		exprs = parse_Exprs();
		exprs.add(0, e);
		break;
	    case Yytoken.SEMI:
	    case Yytoken.OR:
	    case Yytoken.RPAREN:
	    case Yytoken.RBRACKET:
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}

	return exprs;
    }

    private Nonterminal parse_Left() throws IOException
    {
	Nonterminal result;
	int index;

	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.ID:
		index = nonterms.insert(lookahead.text);
		result = new Nonterminal(lookahead.text, index);
		nontermSet.add(result);
		match(Yytoken.ID);
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}

	return result;
    }

    private int parse_Mod() throws IOException
    {
	int result;

	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.STAR:
		result = Yytoken.STAR;
		match(Yytoken.STAR);
		break;
	    case Yytoken.PLUS:
		result = Yytoken.PLUS;
		match(Yytoken.PLUS);
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}

	return result;
    }

    private List parse_Right() throws IOException
    {
	List exprs;
	List rights = new LinkedList();

	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.ID:
	    case Yytoken.LPAREN:
	    case Yytoken.LBRACKET:
		exprs = parse_Exprs();
		rights.add(exprs);
		while (lookahead.index == Yytoken.OR) {
		    match(Yytoken.OR);
		    exprs = parse_Exprs();
		    rights.add(exprs);
		}
		break;
	}

	return rights;
    }

    private List parse_Rule() throws IOException
    {
	Nonterminal left;
	List right;
	List rules = new LinkedList();

	if (lookahead == null) {
	    return rules;
	}

	switch (lookahead.index) {
	    case Yytoken.ID:
		left = parse_Left();
		match(Yytoken.COLON);
		right = parse_Right();
		match(Yytoken.SEMI);

		Iterator it = right.iterator();

		while (it.hasNext()) {
		    List exprs = (List) it.next();
		    rules.add(new Rule(left, exprs));
		}
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}

	return rules;
    }

    private List parse_Rules() throws IOException
    {
	List rules = new LinkedList();
	List r;

	if (lookahead == null) {
	    return rules;
	}

	switch (lookahead.index) {
	    case Yytoken.ID:
		r = parse_Rule();
		rules.addAll(r);
		r = parse_Rules();
		rules.addAll(r);
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}

	return rules;
    }

    private void parse_Start() throws IOException
    {
	int index;

	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.SEPSTART:
		match(Yytoken.SEPSTART);
		index = nonterms.insert(lookahead.text);
		start = new Nonterminal(lookahead.text, index);
		nontermSet.add(start);
		match(Yytoken.ID);
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}
    }

    private void parse_Token() throws IOException
    {
	int index;
	Terminal term;

	if (lookahead == null) {
	    die(yy.yyline() + ": Parse error: unexpected EOF"); 
	    throw new RuntimeException();
	}

	switch (lookahead.index) {
	    case Yytoken.SEPTOKEN:
		match(Yytoken.SEPTOKEN);
		index = terms.insert(lookahead.text);
		term = new Terminal(lookahead.text, index);
		termSet.add(term);
		match(Yytoken.ID);
		break;
	    default:
		die(yy.yyline() +
		    ": Parse error: unexpected token: " + lookahead);
		throw new RuntimeException();
	}
    }

    private void match(int token) throws IOException
    {
	if (lookahead == null) {
	    die(yy.yyline() +
		": Parse error: unexpected EOF, expected <" + token + ">");
	    throw new RuntimeException();
	}

	if (lookahead.index == token) {
	    lookahead = yy.yylex();
	}
	else {
	    die(yy.yyline() +
		": Parse error: unexpected token: got " + lookahead +
		", expected <" + token + ">");
	    throw new RuntimeException();
	}
    }

    private void die(String message)
    {
	System.out.println(message);
	System.exit(1);
    }
}

class IntMap
{
    Map table;
    int next;

    public IntMap()
    {
	table = new HashMap();
	next = 0;
    }

    public int lookup(String sym)
    {
	Integer i = (Integer) table.get(sym);

	if (i == null) {
	    return -1;
	}

	return i.intValue();
    }

    public int insert(String sym)
    {
	Integer i = (Integer) table.get(sym);

	if (i == null) {
	    table.put(sym, new Integer(next));
	    return next++;
	}

	return i.intValue();
    }

    public Set getSymbols()
    {
	return table.keySet();
    }
}