llanalyze.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

// Main class for LLAnalyze -- analyze a presumably LL(1) grammar and report
// various features.

package Iota.util.grammar;

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

public class LLAnalyze
{
    public static void main(String[] args)
    {
	boolean dumpGrammar = false;
	boolean dumpNullable = false;
	boolean dumpFirst = false;
	boolean dumpFollow = false;

	// Parse the args.
	for (int i = 0; i < args.length; i++) {
	    if (args[i].equals("-dump_grammar")) {
		dumpGrammar = true;
	    }
	    else if (args[i].equals("-dump_nullable")) {
		dumpNullable = true;
	    }
	    else if (args[i].equals("-dump_first")) {
		dumpFirst = true;
	    }
	    else if (args[i].equals("-dump_follow")) {
		dumpFollow = true;
	    }
	    else if (args[i].startsWith("-")) {
		help();
		System.exit(2);
	    }
	}

	try {
	    Parse p = new Parse(System.in);
	    Grammar g = p.parse();

	    if (dumpGrammar) {
		System.out.println("Dumping grammar...");
		System.out.println("--------------------------------" +
				   "--------------------------------");

		Iterator it = g.getRules().iterator();

		while (it.hasNext()) {
		    Rule rule = (Rule) it.next();
		    System.out.println(rule);
		}

		System.out.println();
	    }

	    if (dumpNullable) {
		System.out.println("Dumping NULLABLE flags...");
		System.out.println("--------------------------------" +
				   "--------------------------------");

		Iterator it = g.getNonterminals().iterator();

		while (it.hasNext()) {
		    Nonterminal s = (Nonterminal) it.next();
		    System.out.println("NULLABLE(" + s + ") = " +
					g.isNullable(s));
		}

		System.out.println();
	    }

	    if (dumpFirst) {
		System.out.println("Dumping FIRST sets...");
		System.out.println("--------------------------------" +
				   "--------------------------------");

		Iterator it = g.getNonterminals().iterator();

		while (it.hasNext()) {
		    Nonterminal s = (Nonterminal) it.next();
		    System.out.println("FIRST(" + s + ") = " +
					g.getFirst(s));
		}

		System.out.println();
	    }

	    if (dumpFollow) {
		System.out.println("Dumping FOLLOW sets...");
		System.out.println("--------------------------------" +
				   "--------------------------------");

		Iterator it = g.getNonterminals().iterator();

		while (it.hasNext()) {
		    Nonterminal s = (Nonterminal) it.next();
		    System.out.println("FOLLOW(" + s + ") = " +
					g.getFollow(s));
		}

		System.out.println();
	    }

	    if (isLL1(g)) {
		System.out.println("The grammar is LL(1).");
	    }
	    else {
		System.out.println("The grammar is not LL(1).");
	    }
	}
	catch (IOException e) {
	    System.err.println(e);
	}
    }

    // Check if a grammar is LL(1).
    private static boolean isLL1(Grammar g)
    {
	boolean isLL = true;

	int numNonterms = g.getNonterminalSize();
	int numTerms = g.getTerminalSize();

	// Create the LL(1) parsing table and also a table containing
	// the reason a rule fills an entry in the table for error reporting.
	Rule[][] table = new Rule[numNonterms][numTerms];
	String[][] reason = new String[numNonterms][numTerms];

	// Go through all the rules, filling the tables and checking for
	// conflicts.
	Iterator it = g.getRules().iterator();

	while (it.hasNext()) {
	    Rule r = (Rule) it.next();

	    Nonterminal lhs = r.getLHS();
	    List rhs = r.getRHS();

	    Rule[] row = table[lhs.getIndex()];
	    String[] rowReason = reason[lhs.getIndex()];

	    boolean nullable = true;

	    // Traverse the RHS of the rule until a non-nullable symbol
	    // is found, inserting rules in the table based on FIRST(RHS).
	    //
	    // For L ::= alpha S gamma, where alpha is nullable and S is a
	    // nonterminal, insert the rule in entries table[L][x] for all x
	    // in FIRST(S).
	    //
	    // For L ::= alpha x gamma, where alpha is nullable and x is a
	    // terminal, insert the rule in entries table[L][x].
	    //
	    // If all symbols in the RHS are nullable, insert rules
	    // for FOLLOW(LHS).
	    //
	    Iterator rit = rhs.iterator();

	    while (rit.hasNext()) {
		Expr e = (Expr) rit.next();

		if (e instanceof Nonterminal) {
		    Nonterminal s = (Nonterminal) e;
		    Set first = g.getFirst(s);

		    Iterator fit = first.iterator();

		    while (fit.hasNext()) {
			Terminal t = (Terminal) fit.next();

			Rule rt = row[t.getIndex()];
			String why = "FIRST(" + s + ")";

			if (rt == null) {
			    row[t.getIndex()] = r;
			    rowReason[t.getIndex()] = why;
			}
			else {
			    String why2 = rowReason[t.getIndex()];
			    reportConflict(r, rt, t, why, why2);
			    isLL = false;
			}
		    }

		    if (! g.isNullable(s)) {
			nullable = false;
			break;
		    }
		}
		else if (e instanceof Terminal) {
		    Terminal t = (Terminal) e;

		    Rule rt = row[t.getIndex()];
		    String why = "FIRST(" + t + ")";

		    if (rt == null) {
			row[t.getIndex()] = r;
			rowReason[t.getIndex()] = why;
		    }
		    else {
			String why2 = rowReason[t.getIndex()];
			reportConflict(r, rt, t, why, why2);
			isLL = false;
		    }

		    nullable = false;
		    break;
		}
		else {
		    // Shouldn't happen with canonicalized grammar.
		    throw new RuntimeException();
		}
	    }

	    // If the RHS is nullable, then insert the rule into table[L][x]
	    // for all x in FOLLOW(L).
	    if (nullable) {
		Set follow = g.getFollow(lhs);

		Iterator fit = follow.iterator();

		while (fit.hasNext()) {
		    Terminal t = (Terminal) fit.next();

		    Rule rt = row[t.getIndex()];
		    String why = "FOLLOW(" + lhs + ")";

		    if (rt == null) {
			row[t.getIndex()] = r;
			rowReason[t.getIndex()] = why;
		    }
		    else {
			String why2 = rowReason[t.getIndex()];
			reportConflict(r, rt, t, why, why2);
			isLL = false;
		    }
		}
	    }
	}

	return isLL;
    }

    private static void reportConflict(Rule r1, Rule r2, Terminal t,
		String why1, String why2)
    {
	System.out.println("Conflict with rules:");
	System.out.println("    " + r1);
	System.out.println("    " + r2);
	System.out.println("  lookahead token: " + t + " contained in both");
	System.out.println("    " + why1 + " and " + why2);
	System.out.println();
    }

    private static void help()
    {
	System.out.println("java Iota.util.grammar.LLAnalyze [options] " +
							"< grammar_file");
	System.out.println("   where options are:");
	System.out.println("       -dump_grammar   " +
			   "dump the grammar without EBNF features");
	System.out.println("       -dump_nullable  " +
		           "dump NULLABLE flags for all nonterminals");
	System.out.println("       -dump_first     " +
		           "dump FIRST sets for all nonterminals");
	System.out.println("       -dump_follow    " +
		           "dump FOLLOW sets for all nonterminals");
	System.out.println("       -help           " +
		           "what?");
    }
}