/*-------------------------------------------------------------------------
Tab.java -- Symbol Table Management
Compiler Generator Coco/R,
Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz
extended by M. Loeberbauer & A. Woess, Univ. of Linz
ported from C# to Java by Wolfgang Ahorner
with improvements by Pat Terry, Rhodes University

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

As an exception, it is allowed to write an extension of Coco/R that is
used as a plugin in non-free software.

If not otherwise stated, any source code generated by Coco/R (other than
Coco/R itself) does not fall under the GNU General Public License.
------------------------------------------------------------------------*/

package Coco;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Hashtable;
import java.util.Map;
import java.util.TreeMap;


class Position { // position of source code stretch (e.g. semantic action, resolver expressions)
	public int beg;      // start relative to the beginning of the file
	public int len;      // length of stretch
	public int col;      // column number of start position

	public Position(int beg, int len, int col) {
		this.beg = beg; this.len = len; this.col = col;
	}
}

class SymInfo { // output attribute of symbols in the ATG
	String name;
	int kind;		// 0 = ident, 1 = string
}

//=====================================================================
// Symbol
//=====================================================================

class Symbol implements Comparable {

	// token kinds
	public static final int fixedToken    = 0; // e.g. 'a' ('b' | 'c') (structure of literals)
	public static final int classToken    = 1; // e.g. digit {digit}   (at least one char class)
	public static final int litToken      = 2; // e.g. "while"
	public static final int classLitToken = 3; // e.g. letter {letter} but without literals that have the same structure

	public int      n;           // symbol number
	public int      typ;         // t, nt, pr, unknown, rslv /* ML 29_11_2002 slv added */ /* AW slv --> rslv */
	public String   name;        // symbol name
	public Node     graph;       // nt: to first node of syntax graph
	public int      tokenKind;   // t:  token kind (fixedToken, classToken, ...)
	public boolean  deletable;   // nt: true if nonterminal is deletable
	public boolean  firstReady;  // nt: true if terminal start symbols have already been computed
	public BitSet   first;       // nt: terminal start symbols
	public BitSet   follow;      // nt: terminal followers
	public BitSet   nts;         // nt: nonterminals whose followers have to be added to this sym
	public int      line;        // source text line number of item in this node
	public Position attrPos;     // nt: position of attributes in source text (or null)
	public Position semPos;      // pr: pos of semantic action in source text (or null)
															 // nt: pos of local declarations in source text (or null)
	public String   retType;     // AH - nt: Type of output attribute (or null)
	public String   retVar;      // AH - nt: Name of output attribute (or null)

	public Symbol(int typ, String name, int line) {
		this.typ = typ; this.name = name; this.line = line;
	}

	public int compareTo(Object x) {
		return name.compareTo(((Symbol)x).name);
	}

}


//=====================================================================
// Node
//=====================================================================

class Node {
	// constants for node kinds
	public static final int t    =  1;  // terminal symbol
	public static final int pr   =  2;  // pragma
	public static final int nt   =  3;  // nonterminal symbol
	public static final int clas =  4;  // character class
	public static final int chr  =  5;  // character
	public static final int wt   =  6;  // weak terminal symbol
	public static final int any  =  7;  //
	public static final int eps  =  8;  // empty
	public static final int sync =  9;  // synchronization symbol
	public static final int sem  = 10;  // semantic action: (. .)
	public static final int alt  = 11;  // alternative: |
	public static final int iter = 12;  // iteration: { }
	public static final int opt  = 13;  // option: [ ]
	public static final int rslv = 14;  // resolver expr  /* ML */ /* AW 03-01-13 renamed slv --> rslv */

	public static final int normalTrans  = 0;		// transition codes
	public static final int contextTrans = 1;

	public int      n;				// node number
	public int      typ;			// t, nt, wt, chr, clas, any, eps, sem, sync, alt, iter, opt, rslv
	public Node     next;			// to successor node
	public Node     down;			// alt: to next alternative
	public Node     sub;			// alt, iter, opt: to first node of substructure
	public boolean  up;				// true: "next" leads to successor in enclosing structure
	public Symbol   sym;			// nt, t, wt: symbol represented by this node
	public int      val;			// chr:  ordinal character value
														// clas: index of character class
	public int      code;			// chr, clas: transition code
	public BitSet set;				// any, sync: the set represented by this node
	public Position pos;			// nt, t, wt: pos of actual attributes
														// sem:       pos of semantic action in source text
	public int      line;			// source text line number of item in this node
	public State    state;		// DFA state corresponding to this node
														// (only used in DFA.ConvertToStates)
	public String retVar;			// AH 20040206 - nt: name of output attribute (or null)

	public Node(int typ, Symbol sym, int line) {
		this.typ = typ; this.sym = sym; this.line = line;
	}

}

//=====================================================================
// Graph
//=====================================================================

class Graph {
	public Node l;	// left end of graph = head
	public Node r;	// right end of graph = list of nodes to be linked to successor graph

	public Graph() {}

	public Graph(Node left, Node right) {
		l = left; r = right;
	}

	public Graph(Node p) {
		l = p; r = p;
	}

}

//=====================================================================
// Sets
//=====================================================================
class Sets {

	public static int Elements(BitSet s) {
		int max = s.size();
		int n = 0;
		for (int i=0; i<max; i++)
			if (s.get(i)) n++;
		return n;
	}

	public static boolean Equals(BitSet a, BitSet b) {
		int max = a.size();
		for (int i=0; i<max; i++)
			if (a.get(i) != b.get(i)) return false;
		return true;
	}

	public static boolean Intersect(BitSet a, BitSet b) { // a * b != {}
		int max = a.size();
		for (int i=0; i<max; i++)
			if (a.get(i) && b.get(i)) return true;
		return false;
	}

	public static void Subtract(BitSet a, BitSet b) { // a = a - b
		BitSet c = (BitSet)b.clone();
		//a.and(c.not());
		c.flip(0, c.size());	// c.not
		a.and(c);
	}

}

//=====================================================================
// CharClass
//=====================================================================

class CharClass {
	public int n;       // class number
	public String name;	// class name
	public CharSet set;	// set representing the class

	public CharClass(String name, CharSet s) {
		this.name = name; this.set = s;
	}
}

//===========================================================
// Tab
//===========================================================

public class Tab {
	public Position semDeclPos;        // position of global semantic declarations
	public CharSet ignored;            // characters ignored by the scanner
	public boolean[] ddt = new boolean[10];	// debug and test switches
	public Symbol gramSy;              // root nonterminal; filled by ATG
	public Symbol eofSy;               // end of file symbol
	public Symbol noSym;               // used in case of an error
	public BitSet allSyncSets;         // union of all synchronisation sets
	public Hashtable literals;         // symbols that are used as literals

	public String srcName;             // name of the atg file (including path)
	public String srcDir;              // directory path of the atg file
	public String nsName;              // package name for generated files
	public String frameDir;            // directory containing the frame files
	public String outDir;              // directory for generated files

	BitSet visited;                    // mark list for graph traversals
	Symbol curSy;                      // current symbol in computation of sets

	Parser parser;                     // other Coco objects
	Trace trace;
	Errors errors;

	public Tab(Parser parser) {
		this.parser = parser;
		trace = parser.trace;
		errors = parser.errors;
		eofSy = NewSym(Node.t, "EOF", 0);
		dummyNode = NewNode(Node.eps, null, 0);
		literals = new Hashtable();
	}

	//---------------------------------------------------------------------
	//  Symbol list management
	//---------------------------------------------------------------------

	public ArrayList terminals = new ArrayList();
	public ArrayList pragmas = new ArrayList();
	public ArrayList nonterminals = new ArrayList();

	String[] tKind = {"fixedToken", "classToken", "litToken", "classLitToken"};

	public Symbol NewSym(int typ, String name, int line) {
		if (name.length() == 2 && name.charAt(0) == '"') {
			parser.SemErr("empty token not allowed"); name = "???";
		}
		Symbol sym = new Symbol(typ, name, line);
		switch (typ) {
			case Node.t:  sym.n = terminals.size(); terminals.add(sym); break;
			case Node.pr: pragmas.add(sym); break;
			case Node.nt: sym.n = nonterminals.size(); nonterminals.add(sym); break;
		}
		return sym;
	}

	public Symbol FindSym(String name) {
		Symbol s;
		//foreach (Symbol s in terminals)
		for (int i = 0; i < terminals.size(); i++) {
			s = (Symbol)terminals.get(i);
			if (s.name.compareTo(name) == 0) return s;
		}
		//foreach (Symbol s in nonterminals)
		for (int i = 0; i < nonterminals.size(); i++) {
			s = (Symbol)nonterminals.get(i);
			if (s.name.compareTo(name) == 0) return s;
		}
		return null;
	}

	int Num(Node p) {
		if (p == null) return 0; else return p.n;
	}

	void PrintSym(Symbol sym) {
		trace.Write(Integer.toString(sym.n), 3);
		trace.Write(" ");
		trace.Write(Name(sym.name), -14);
		trace.Write(" ");
		trace.Write(nTyp[sym.typ], 2);
		if (sym.attrPos==null) trace.Write(" false "); else trace.Write(" true  ");
		if (sym.typ == Node.nt) {
			trace.Write(Integer.toString(Num(sym.graph)), 5);
			if (sym.deletable) trace.Write(" true  "); else trace.Write(" false ");
		} else
			trace.Write("            ");
		trace.Write(Integer.toString(sym.line), 5);
		trace.WriteLine(" " + tKind[sym.tokenKind]);
	}

	public void PrintSymbolTable() {
		trace.WriteLine("Symbol Table:");
		trace.WriteLine("------------"); trace.WriteLine();
		trace.WriteLine(" nr name           typ  hasAt graph  del   line tokenKind");
		//foreach (Symbol sym in Symbol.terminals)
		for (int i = 0; i < terminals.size(); i++) {
			PrintSym((Symbol)terminals.get(i));
		}
		//foreach (Symbol sym in Symbol.pragmas)
		for (int i = 0; i < pragmas.size(); i++) {
			PrintSym((Symbol)pragmas.get(i));
		}
		//foreach (Symbol sym in Symbol.nonterminals)
		for (int i = 0; i < nonterminals.size(); i++) {
			PrintSym((Symbol)nonterminals.get(i));
		}
		trace.WriteLine();
		trace.WriteLine("Literal Tokens:");
		trace.WriteLine("--------------");
		java.util.Iterator iter = literals.entrySet().iterator();
		Map.Entry me = null;
		//foreach (DictionaryEntry e in literals) {
		while (iter.hasNext()) {
			me = (Map.Entry)iter.next();
			trace.WriteLine("_" + ((Symbol)me.getValue()).name + " = " + me.getKey() + ".");
		}
		trace.WriteLine();
	}

	public void PrintSet(BitSet s, int indent) {
		int col = indent;
		//foreach (Symbol sym in Symbol.terminals) {
		for (int i = 0; i < terminals.size(); i++) {
			Symbol sym = (Symbol)terminals.get(i);
			if (s.get(sym.n)) {
				int len = sym.name.length();
				if (col + len >= 80) {
					trace.WriteLine();
					for (col = 1; col < indent; col++) trace.Write(" ");
				}
				trace.Write(sym.name + " ");
				col += len + 1;
			}
		}
		if (col == indent) trace.Write("-- empty set --");
		trace.WriteLine();
	}

	//---------------------------------------------------------------------
	//  Syntax graph management
	//---------------------------------------------------------------------

	public ArrayList nodes = new ArrayList();
	public String[] nTyp =
	{"    ", "t   ", "pr  ", "nt  ", "clas", "chr ", "wt  ", "any ", "eps ",  /* AW 03-01-14 nTyp[0]: " " --> "    " */
	"sync", "sem ", "alt ", "iter", "opt ", "rslv"};
	Node dummyNode;

	public Node NewNode(int typ, Symbol sym, int line) {
		Node node = new Node(typ, sym, line);
		node.n = nodes.size();
		nodes.add(node);
		return node;
	}

	public Node NewNode(int typ, Node sub) {
		Node node = NewNode(typ, null, 0);
		node.sub = sub;
		return node;
	}

	public Node NewNode(int typ, int val, int line) {
		Node node = NewNode(typ, null, line);
		node.val = val;
		return node;
	}

	public void MakeFirstAlt(Graph g) {
		g.l = NewNode(Node.alt, g.l); g.l.line = g.l.sub.line;
		g.l.next = g.r;
		g.r = g.l;
	}

	public void MakeAlternative(Graph g1, Graph g2) {
		g2.l = NewNode(Node.alt, g2.l); g2.l.line = g2.l.sub.line;
		Node p = g1.l; while (p.down != null) p = p.down;
		p.down = g2.l;
		p = g1.r; while (p.next != null) p = p.next;
		p.next = g2.r;
	}

	public void MakeSequence(Graph g1, Graph g2) {
		Node p = g1.r.next; g1.r.next = g2.l; // link head node
		while (p != null) {  // link substructure
			Node q = p.next; p.next = g2.l; p.up = true;
			p = q;
		}
		g1.r = g2.r;
	}

	public void MakeIteration(Graph g) {
		g.l = NewNode(Node.iter, g.l);
		Node p = g.r;
		g.r = g.l;
		while (p != null) {
			Node q = p.next; p.next = g.l; p.up = true;
			p = q;
		}
	}

	public void MakeOption(Graph g) {
		g.l = NewNode(Node.opt, g.l);
		g.l.next = g.r;
		g.r = g.l;
	}

	public void Finish(Graph g) {
		Node p = g.r;
		while (p != null) {
			Node q = p.next; p.next = null; p = q;
		}
	}

	public void DeleteNodes() {
		nodes = new ArrayList();
		dummyNode = NewNode(Node.eps, null, 0);
	}

	public Graph StrToGraph(String str) {
		String s = Unescape(str.substring(1, str.length()-1));
		if (s.length() == 0) parser.SemErr("empty token not allowed");
		Graph g = new Graph();
		g.r = dummyNode;
		for (int i = 0; i < s.length(); i++) {
			Node p = NewNode(Node.chr, (int)s.charAt(i), 0);
			g.r.next = p; g.r = p;
		}
		g.l = dummyNode.next; dummyNode.next = null;
		return g;
	}

	public void SetContextTrans(Node p) { // set transition code in the graph rooted at p
		while (p != null) {
			if (p.typ == Node.chr || p.typ == Node.clas) {
				p.code = Node.contextTrans;
			} else if (p.typ == Node.opt || p.typ == Node.iter) {
				SetContextTrans(p.sub);
			} else if (p.typ == Node.alt) {
				SetContextTrans(p.sub); SetContextTrans(p.down);
			}
			if (p.up) break;
			p = p.next;
		}
	}

	//---------------- graph deletability check ---------------------

	public boolean DelGraph(Node p) {
		return p == null || DelNode(p) && DelGraph(p.next);
	}

	public boolean DelSubGraph(Node p) {
		return p == null || DelNode(p) && (p.up || DelSubGraph(p.next));
	}

	public boolean DelAlt(Node p) {
		return p == null || DelNode(p) && (p.up || DelAlt(p.next));
	}

	public boolean DelNode(Node p) {
		if (p.typ == Node.nt) return p.sym.deletable;
		else if (p.typ == Node.alt) return DelAlt(p.sub) || p.down != null && DelAlt(p.down);
		else return p.typ == Node.iter || p.typ == Node.opt || p.typ == Node.sem
			|| p.typ == Node.eps || p.typ == Node.sync || p.typ == Node.rslv;
	}

	//-------------------- graph printing ------------------------

	int Ptr(Node p, boolean up) {
		if (p == null) return 0;
		else if (up) return -p.n;
		else return p.n;
	}

	String Pos(Position pos) {
		if (pos == null) return "     ";
		else return trace.formatString(Integer.toString(pos.beg), 5);
	}

	public String Name(String name) {
		return (name + "           ").substring(0, 12);
		// found no simpler way to get the first 12 characters of the name
		// padded with blanks on the right
	}

	public void PrintNodes() {
		trace.WriteLine("Graph nodes:");
		trace.WriteLine("----------------------------------------------------");
		trace.WriteLine("   n type name          next  down   sub   pos  line");
		trace.WriteLine("                               val  code");
		trace.WriteLine("----------------------------------------------------");
		//foreach (Node p in nodes) {
		for (int i = 0; i < nodes.size(); i++) {
			Node p = (Node)nodes.get(i);
			trace.Write(Integer.toString(p.n), 4);
			trace.Write(" " + nTyp[p.typ] + " ");
			if (p.sym != null) {
				trace.Write(Name(p.sym.name), 12);
				trace.Write(" ");
			} else if (p.typ == Node.clas) {
				CharClass c = (CharClass)classes.get(p.val);
				trace.Write(Name(c.name), 12);
				trace.Write(" ");
			} else trace.Write("             ");
			trace.Write(Integer.toString(Ptr(p.next, p.up)), 5);
			trace.Write(" ");
			switch (p.typ) {
				case Node.t: case Node.nt: case Node.wt:
					trace.Write("             ");
					trace.Write(Pos(p.pos), 5);
					break;
				case Node.chr:
					trace.Write(Integer.toString(p.val), 5);
					trace.Write(" ");
					trace.Write(Integer.toString(p.code), 5);
					trace.Write("       ");
					break;
				case Node.clas:
					trace.Write("      ");
					trace.Write(Integer.toString(p.code), 5);
					trace.Write("       ");
					break;
				case Node.alt: case Node.iter: case Node.opt:
					trace.Write(Integer.toString(Ptr(p.down, false)), 5);
					trace.Write(" ");
					trace.Write(Integer.toString(Ptr(p.sub, false)), 5);
					trace.Write("       ");
					break;
				case Node.sem:
					trace.Write("             ");
					trace.Write(Pos(p.pos), 5);
					break;
				case Node.eps: case Node.any: case Node.sync:
					trace.Write("                  "); break;
			}
			trace.WriteLine(Integer.toString(p.line), 5);
		}
		trace.WriteLine();
	}

	//---------------------------------------------------------------------
	//  character class management
	//---------------------------------------------------------------------

	public ArrayList classes = new ArrayList();
	public int dummyName = 'A';

	public CharClass NewCharClass(String name, CharSet s) {
		if (name.compareTo("#") == 0) name = "#" + (char)dummyName++;
		CharClass c = new CharClass(name, s);
		c.n = classes.size();
		classes.add(c);
		return c;
	}

	public CharClass FindCharClass(String name) {
		//foreach (CharClass c in classes)
		for (int i = 0; i < classes.size(); i++) {
			CharClass c = (CharClass)classes.get(i);
			if (c.name.compareTo(name) == 0) return c;
		}
		return null;
	}

	public CharClass FindCharClass(CharSet s) {
		//foreach (CharClass c in classes)
		for (int i = 0; i < classes.size(); i++) {
			CharClass c = (CharClass)classes.get(i);
			if (s.Equals(c.set)) return c;
		}
		return null;
	}

	public CharSet CharClassSet(int i) {
		return ((CharClass)classes.get(i)).set;
	}

	//-------------------- character class printing -----------------------

	String Ch(int ch) {
		if (ch < ' ' || ch >= 127 || ch == '\'' || ch == '\\') return Integer.toString(ch);
		else return ("'" + (char)ch + "'");
	}

	void WriteCharSet(CharSet s) {
		for (CharSet.Range r = s.head; r != null; r = r.next) {
			if (r.from < r.to) { trace.Write(Ch(r.from) + ".." + Ch(r.to) + " "); }
			else { trace.Write(Ch(r.from) + " "); }
		}
	}

	public void WriteCharClasses () {
		//foreach (CharClass c in classes) {
		for (int i = 0; i < classes.size(); i++) {
			CharClass c = (CharClass)classes.get(i);
			trace.Write(c.name + ": ", -10);
			WriteCharSet(c.set);
			trace.WriteLine();
		}
		trace.WriteLine();
	}

	//---------------------------------------------------------------------
	//  Symbol set computations
	//---------------------------------------------------------------------

	// Computes the first set for the graph rooted at p
	BitSet First0(Node p, BitSet mark) {
		BitSet fs = new BitSet(terminals.size());
		while (p != null && !mark.get(p.n)) {
			mark.set(p.n);
			switch (p.typ) {
				case Node.nt: {
					if (p.sym.firstReady) fs.or(p.sym.first);
					else fs.or(First0(p.sym.graph, mark));
					break;
				}
				case Node.t: case Node.wt: {
					fs.set(p.sym.n); break;
				}
				case Node.any: {
					fs.or(p.set); break;
				}
				case Node.alt: {
					fs.or(First0(p.sub, mark));
					fs.or(First0(p.down, mark));
					break;
				}
				case Node.iter: case Node.opt: {
					fs.or(First0(p.sub, mark));
					break;
				}
			}
			if (!DelNode(p)) break;
			p = p.next;
		}
		return fs;
	}

	public BitSet First(Node p) {
		BitSet fs = First0(p, new BitSet(nodes.size()));
		if (ddt[3]) {
			trace.WriteLine();
			if (p != null) trace.WriteLine("First: node = " + p.n);
			else trace.WriteLine("First: node = null");
			PrintSet(fs, 0);
		}
		return fs;
	}


	void CompFirstSets() {
		Symbol sym;
		//foreach (Symbol sym in Symbol.nonterminals) {
		for (int i = 0; i < nonterminals.size(); i++) {
			sym = (Symbol)nonterminals.get(i);
			sym.first = new BitSet(terminals.size());
			sym.firstReady = false;
		}
		//foreach (Symbol sym in Symbol.nonterminals) {
		for (int i = 0; i < nonterminals.size(); i++) {
			sym = (Symbol)nonterminals.get(i);
			sym.first = First(sym.graph);
			sym.firstReady = true;
		}
	}

	void CompFollow(Node p) {
		while (p != null && !visited.get(p.n)) {
			visited.set(p.n);
			if (p.typ == Node.nt) {
				BitSet s = First(p.next);
				p.sym.follow.or(s);
				if (DelGraph(p.next))
					p.sym.nts.set(curSy.n);
			} else if (p.typ == Node.opt || p.typ == Node.iter) {
				CompFollow(p.sub);
			} else if (p.typ == Node.alt) {
				CompFollow(p.sub); CompFollow(p.down);
			}
			p = p.next;
		}
	}

	void Complete(Symbol sym) {
		if (!visited.get(sym.n)) {
			visited.set(sym.n);
			//foreach (Symbol s in Symbol.nonterminals) {
			for (int i = 0; i < nonterminals.size(); i++) {
				Symbol s = (Symbol)nonterminals.get(i);
				if (sym.nts.get(s.n)) {
					Complete(s);
					sym.follow.or(s.follow);
					if (sym == curSy) sym.nts.clear(s.n);
				}
			}
		}
	}

	void CompFollowSets() {
		int nNonterminals = nonterminals.size();
		//foreach (Symbol sym in Symbol.nonterminals) {
		for (int i = 0; i < nNonterminals; i++) {
			Symbol sym = (Symbol)nonterminals.get(i);
			sym.follow = new BitSet(terminals.size());
			sym.nts = new BitSet(nNonterminals);
		}
		gramSy.follow.set(eofSy.n);
		visited = new BitSet(nodes.size());
		//foreach (Symbol sym in Symbol.nonterminals) { // get direct successors of nonterminals
		for (int i = 0; i < nNonterminals; i++) {
			curSy = (Symbol)nonterminals.get(i);
			CompFollow(curSy.graph);
		}
		//foreach (Symbol sym in Symbol.nonterminals) { // add indirect successors to followers
		for (int i = 0; i < nNonterminals; i++) {
			curSy = (Symbol)nonterminals.get(i);
			visited = new BitSet(nNonterminals);
			Complete(curSy);
		}
	}

	Node LeadingAny(Node p) {
		if (p == null) return null;
		Node a = null;
		if (p.typ == Node.any) a = p;
		else if (p.typ == Node.alt) {
			a = LeadingAny(p.sub);
			if (a == null) a = LeadingAny(p.down);
		}
		else if (p.typ == Node.opt || p.typ == Node.iter) a = LeadingAny(p.sub);
		else if (DelNode(p) && !p.up) a = LeadingAny(p.next);
		return a;
	}

	void FindAS(Node p) { // find ANY sets
		Node a;
		while (p != null) {
			if (p.typ == Node.opt || p.typ == Node.iter) {
				FindAS(p.sub);
				a = LeadingAny(p.sub);
				if (a != null) Sets.Subtract(a.set, First(p.next));
			} else if (p.typ == Node.alt) {
				BitSet s1 = new BitSet(terminals.size());
				Node q = p;
				while (q != null) {
					FindAS(q.sub);
					a = LeadingAny(q.sub);
					if (a != null) {
						BitSet h = First(q.down);
						h.or(s1);
						Sets.Subtract(a.set, h);
					}
					else
						s1.or(First(q.sub));
					q = q.down;
				}
			}
			if (p.up) break;
			p = p.next;
		}
	}

	void CompAnySets() {
		Symbol sym;
		//foreach (Symbol sym in Symbol.nonterminals)
		for (int i = 0; i < nonterminals.size(); i++) {
			sym = (Symbol)nonterminals.get(i);
			FindAS(sym.graph);
		}
	}

	public BitSet Expected(Node p, Symbol curSy) {
		BitSet s = First(p);
		if (DelGraph(p)) s.or(curSy.follow);
		return s;
	}

	// does not look behind resolvers; only called during LL(1) test and in CheckRes
	public BitSet Expected0(Node p, Symbol curSy) {
		if (p.typ == Node.rslv) return new BitSet(terminals.size());
		else return Expected(p, curSy);
	}

	void CompSync(Node p) {
		while (p != null && !visited.get(p.n)) {
			visited.set(p.n);
			if (p.typ == Node.sync) {
				BitSet s = Expected(p.next, curSy);
				s.set(eofSy.n);
				allSyncSets.or(s);
				p.set = s;
			} else if (p.typ == Node.alt) {
				CompSync(p.sub); CompSync(p.down);
			} else if (p.typ == Node.opt || p.typ == Node.iter)
				CompSync(p.sub);
			p = p.next;
		}
	}

void CompSyncSets() {
		allSyncSets = new BitSet(terminals.size());
		allSyncSets.set(eofSy.n);
		visited = new BitSet(nodes.size());
		//foreach (Symbol sym in Symbol.nonterminals) {
		for (int i = 0; i < nonterminals.size(); i++) {
			curSy = (Symbol)nonterminals.get(i);
			CompSync(curSy.graph);
		}
	}

	public void SetupAnys() {
		//foreach (Node p in Node.nodes)
		for (int i = 0; i < nodes.size(); i++) {
			Node p = (Node)nodes.get(i);
			if (p.typ == Node.any) {
				p.set = new BitSet(terminals.size());
				p.set.set(0, p.set.size());
				p.set.clear(eofSy.n);
			}
		}
	}

	public void CompDeletableSymbols() {
		boolean changed;
		Symbol sym;
		do {
			changed = false;
			//foreach (Symbol sym in Symbol.nonterminals)
			for (int i = 0; i < nonterminals.size(); i++) {
				sym = (Symbol)nonterminals.get(i);
				if (!sym.deletable && sym.graph != null && DelGraph(sym.graph)) {
					sym.deletable = true; changed = true;
				}
			}
		} while (changed);
		//foreach (Symbol sym in Symbol.nonterminals)
		for (int i = 0; i < nonterminals.size(); i++) {
			sym = (Symbol)nonterminals.get(i);
			if (sym.deletable) errors.Warning("  " + sym.name + " deletable");
		}
	}

	public void RenumberPragmas() {
		int n = terminals.size();
		//foreach (Symbol sym in Symbol.pragmas)
		for (int i = 0; i < pragmas.size(); i++) {
			Symbol sym = (Symbol)pragmas.get(i);
			sym.n = n++;
		}
	}

	public void CompSymbolSets() {
		CompDeletableSymbols();
		CompFirstSets();
		CompFollowSets();
		CompAnySets();
		CompSyncSets();
		if (ddt[1]) {
			trace.WriteLine();
			trace.WriteLine("First & follow symbols:");
			trace.WriteLine("----------------------"); trace.WriteLine();
			Symbol sym;
			//foreach (Symbol sym in Symbol.nonterminals) {
			for (int i = 0; i < nonterminals.size(); i++) {
				sym = (Symbol)nonterminals.get(i);
				trace.WriteLine(sym.name);
				trace.Write("first:   "); PrintSet(sym.first, 10);
				trace.Write("follow:  "); PrintSet(sym.follow, 10);
				trace.WriteLine();
			}
		}
		if (ddt[4]) {
			trace.WriteLine();
			trace.WriteLine("ANY and SYNC sets:");
			trace.WriteLine("-----------------");
			//foreach (Node p in Node.nodes)
			for (int i = 0; i < nodes.size(); i++) {
				Node p = (Node)nodes.get(i);
				if (p.typ == Node.any || p.typ == Node.sync) {
					trace.Write(Integer.toString(p.n), 4);
					trace.Write(" ");
					trace.Write(nTyp[p.typ], 4);
					trace.Write(": ");
					PrintSet(p.set, 11);
				}
			}
		}
	}

	//---------------------------------------------------------------------
	//  String handling
	//---------------------------------------------------------------------

  char Hex2Char(String s) {
    int val = 0;
    for (int i = 0; i < s.length(); i++) {
      char ch = s.charAt(i);
      if ('0' <= ch && ch <= '9') val = 16 * val + (ch - '0');
      else if ('a' <= ch && ch <= 'f') val = 16 * val + (10 + ch - 'a');
      else if ('A' <= ch && ch <= 'F') val = 16 * val + (10 + ch - 'A');
      else parser.SemErr("bad escape sequence in string or character");
    }
    if (val > Character.MAX_VALUE) /* pdt */
      parser.SemErr("bad escape sequence in string or character");
    return (char) val;
  }

  String Char2Hex(char ch) {
    String hex = Integer.toHexString((int)ch);
    for (int i = hex.length(); i < 4; i++) hex = "0" + hex;
    return "\\u" + hex;
  }

  public String Unescape (String s) {
    /* replaces escape sequences in s by their Unicode values. */
    StringBuffer buf = new StringBuffer();
    int i = 0;
    while (i < s.length()) {
      if (s.charAt(i) == '\\') {
        switch (s.charAt(i+1)) {
          case '\\': buf.append('\\'); i += 2; break;
          case '\'': buf.append('\''); i += 2; break;
          case '\"': buf.append('\"'); i += 2; break;
          case 'r': buf.append('\r'); i += 2; break;
          case 'n': buf.append('\n'); i += 2; break;
          case 't': buf.append('\t'); i += 2; break;
          case '0': buf.append('\0'); i += 2; break;
          case 'b': buf.append('\b'); i += 2; break;
          case 'f': buf.append('\f'); i += 2; break;
          case 'u': case 'x':
            if (i + 6 <= s.length()) {
              buf.append(Hex2Char(s.substring(i+2, i+6))); i += 6; break;
            } else {
              parser.SemErr("bad escape sequence in string or character");
              i = s.length(); break;
            }
          default: parser.SemErr("bad escape sequence in string or character"); i += 2; break;
        }
      } else {
        buf.append(s.charAt(i));
        i++;
      }
    }
    return buf.toString();
  }

  public String Escape (String s) {
    StringBuffer buf = new StringBuffer();
    for (int i = 0; i < s.length(); i++) {
      char ch = s.charAt(i);
      switch(ch) {
        case '\\': buf.append("\\\\"); break;
        case '\'': buf.append("\\'"); break;
        case '\"': buf.append("\\\""); break;
        case '\t': buf.append("\\t"); break;
        case '\r': buf.append("\\r"); break;
        case '\n': buf.append("\\n"); break;
        default:
          if (ch < ' ' || ch > '\u007f') buf.append(Char2Hex(ch));
          else buf.append(ch);
          break;
      }
    }
    return buf.toString();
  }

	//---------------------------------------------------------------------
	//  Grammar checks
	//---------------------------------------------------------------------

	public boolean GrammarOk() {
		boolean ok = NtsComplete()
			&& AllNtReached()
			&& NoCircularProductions()
			&& AllNtToTerm();
		if (ok) { CheckResolvers(); CheckLL1(); }
		return ok;
	}

	//--------------- check for circular productions ----------------------

	class CNode {	// node of list for finding circular productions
		public Symbol left, right;

		public CNode (Symbol l, Symbol r) {
			left = l; right = r;
		}
	}

	void GetSingles(Node p, ArrayList singles) {
		if (p == null) return;  // end of graph
		if (p.typ == Node.nt) {
			if (p.up || DelGraph(p.next)) singles.add(p.sym);
		} else if (p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt) {
			if (p.up || DelGraph(p.next)) {
				GetSingles(p.sub, singles);
				if (p.typ == Node.alt) GetSingles(p.down, singles);
			}
		}
		if (!p.up && DelNode(p)) GetSingles(p.next, singles);
	}

	public boolean NoCircularProductions() {
		boolean ok, changed, onLeftSide, onRightSide;
		ArrayList list = new ArrayList();
		for (int i = 0; i < nonterminals.size(); i++) {
			Symbol sym = (Symbol)nonterminals.get(i);
			ArrayList singles = new ArrayList();
			GetSingles(sym.graph, singles); // get nonterminals s such that sym-->s
			for (int j = 0; j < singles.size(); j++) {
				Symbol s = (Symbol)singles.get(j);
				list.add(new CNode(sym, s));
			}
		}
		do {
			changed = false;
			for (int i = 0; i < list.size(); i++) {
				CNode n = (CNode)list.get(i);
				onLeftSide = false; onRightSide = false;
				for (int j = 0; j < list.size(); j++) {
					CNode m = (CNode)list.get(j);
					if (n.left == m.right) onRightSide = true;
					if (n.right == m.left) onLeftSide = true;
				}
				if (!onLeftSide || !onRightSide) {
					list.remove(n); i--; changed = true;
				}
			}
		} while(changed);
		ok = true;
		for (int i = 0; i < list.size(); i++) {
			CNode n = (CNode)list.get(i);
			ok = false;
			errors.SemErr("  " + n.left.name + " --> " + n.right.name);
		}
		return ok;
	}

	//--------------- check for LL(1) errors ----------------------

	void LL1Error(int cond, Symbol sym) {
		String s = "  LL1 warning in " + curSy.name + ": ";
		if (sym != null) s += sym.name + " is ";
		switch (cond) {
			case 1: s += "start of several alternatives"; break;
			case 2: s += "start & successor of deletable structure"; break;
			case 3: s += "an ANY node that matches no symbol"; break;
			case 4: s += "contents of [...] or {...} must not be deletable"; break;
		}
		errors.Warning(s);
	}

	void CheckOverlap(BitSet s1, BitSet s2, int cond) {
		for (int i = 0; i < terminals.size(); i++) {
			Symbol sym = (Symbol)terminals.get(i);
			if (s1.get(sym.n) && s2.get(sym.n)) LL1Error(cond, sym);
		}
	}

	void CheckAlts(Node p) {
		BitSet s1, s2;
		while (p != null) {
			if (p.typ == Node.alt) {
				Node q = p;
				s1 = new BitSet(terminals.size());
				while (q != null) { // for all alternatives
					s2 = Expected0(q.sub, curSy);
					CheckOverlap(s1, s2, 1);
					s1.or(s2);
					CheckAlts(q.sub);
					q = q.down;
				}
			} else if (p.typ == Node.opt || p.typ == Node.iter) {
				if (DelSubGraph(p.sub)) LL1Error(4, null); // e.g. [[...]]
				else {
					s1 = Expected0(p.sub, curSy);
					s2 = Expected(p.next, curSy);
					CheckOverlap(s1, s2, 2);
				}
				CheckAlts(p.sub);
			} else if (p.typ == Node.any) {
				if (Sets.Elements(p.set) == 0) LL1Error(3, null);
				// e.g. {ANY} ANY or [ANY] ANY
			}
			if (p.up) break;
			p = p.next;
		}
	}

	public void CheckLL1() {
		for (int i = 0; i < nonterminals.size(); i++) {
			curSy = (Symbol)nonterminals.get(i);
			CheckAlts(curSy.graph);
		}
	}

	//------------- check if resolvers are legal  --------------------

	void ResErr(Node p, String msg) {
		errors.Warning(p.line, p.pos.col, msg);
	}

	void CheckRes(Node p, boolean rslvAllowed) {
		while (p != null) {
			switch (p.typ) {
				case Node.alt:
					BitSet expected = new BitSet(terminals.size());
					for (Node q = p; q != null; q = q.down)
						expected.or(Expected0(q.sub, curSy));
					BitSet soFar = new BitSet(terminals.size());
					for (Node q = p; q != null; q = q.down) {
						if (q.sub.typ == Node.rslv) {
							BitSet fs = Expected(q.sub.next, curSy);
							if (Sets.Intersect(fs, soFar))
								ResErr(q.sub, "Warning: Resolver will never be evaluated. " +
									"Place it at previous conflicting alternative.");
							if (!Sets.Intersect(fs, expected))
								ResErr(q.sub, "Warning: Misplaced resolver: no LL(1) conflict.");
						} else soFar.or(Expected(q.sub, curSy));
						CheckRes(q.sub, true);
					}
					break;
				case Node.iter: case Node.opt:
					if (p.sub.typ == Node.rslv) {
						BitSet fs = First(p.sub.next);
						BitSet fsNext = Expected(p.next, curSy);
						if (!Sets.Intersect(fs, fsNext))
							ResErr(p.sub, "Warning: Misplaced resolver: no LL(1) conflict.");
					}
					CheckRes(p.sub, true);
					break;
				case Node.rslv:
					if (!rslvAllowed)
						ResErr(p, "Warning: Misplaced resolver: no alternative.");
					break;
			}
			if (p.up) break;
			p = p.next;
			rslvAllowed = false;
		}
	}

	public void CheckResolvers() {
		//foreach (Symbol sym in Symbol.nonterminals) {
		for (int i = 0; i < nonterminals.size(); i++) {
			curSy = (Symbol)nonterminals.get(i);
			CheckRes(curSy.graph, false);
		}
	}

	//------------- check if every nts has a production --------------------

	public boolean NtsComplete() {
		boolean complete = true;
		for (int i = 0; i < nonterminals.size(); i++) {
			Symbol sym = (Symbol)nonterminals.get(i);
			if (sym.graph == null) {
				complete = false;
				errors.SemErr("  No production for " + sym.name);
			}
		}
		return complete;
	}

	//-------------- check if every nts can be reached  -----------------

	void MarkReachedNts(Node p) {
		while (p != null) {
			if (p.typ == Node.nt && !visited.get(p.sym.n)) { // new nt reached
				visited.set(p.sym.n);
				MarkReachedNts(p.sym.graph);
			} else if (p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt) {
				MarkReachedNts(p.sub);
				if (p.typ == Node.alt) MarkReachedNts(p.down);
			}
			if (p.up) break;
			p = p.next;
		}
	}

	public boolean AllNtReached() {
		boolean ok = true;
		visited = new BitSet(nonterminals.size());
		visited.set(gramSy.n);
		MarkReachedNts(gramSy.graph);
		for (int i = 0; i < nonterminals.size(); i++) {
			Symbol sym = (Symbol)nonterminals.get(i);
			if (!visited.get(sym.n)) {
				ok = false;
				errors.SemErr("  " + sym.name + " cannot be reached");
			}
		}
		return ok;
	}

	//--------- check if every nts can be derived to terminals  ------------

	boolean IsTerm(Node p, BitSet mark) { // true if graph can be derived to terminals
		while (p != null) {
			if (p.typ == Node.nt && !mark.get(p.sym.n)) return false;
			if (p.typ == Node.alt && !IsTerm(p.sub, mark)
			&& (p.down == null || !IsTerm(p.down, mark))) return false;
			if (p.up) break;
			p = p.next;
		}
		return true;
	}

	public boolean AllNtToTerm() {
		boolean changed, ok = true;
		BitSet mark = new BitSet(nonterminals.size());
		// a nonterminal is marked if it can be derived to terminal symbols
		do {
			changed = false;
			for (int i = 0; i < nonterminals.size(); i++) {
				Symbol sym = (Symbol)nonterminals.get(i);
				if (!mark.get(sym.n) && IsTerm(sym.graph, mark)) {
					mark.set(sym.n); changed = true;
				}
			}
		} while (changed);
		for (int i = 0; i < nonterminals.size(); i++) {
			Symbol sym = (Symbol)nonterminals.get(i);
			if (!mark.get(sym.n)) {
				ok = false;
				errors.SemErr("  " + sym.name + " cannot be derived to terminals");
			}
		}
		return ok;
	}

	//---------------------------------------------------------------------
	//  Cross reference list
	//---------------------------------------------------------------------

	public void XRef() {
		TreeMap xref = new TreeMap();
		// collect lines where symbols have been defined
		//foreach (Symbol sym in Symbol.nonterminals) {
		for (int i = 0; i < nonterminals.size(); i++) {
			Symbol sym = (Symbol)nonterminals.get(i);
			ArrayList list = (ArrayList)xref.get(sym);
			if (list == null) {list = new ArrayList(); xref.put(sym, list);}
			list.add(new Integer(- sym.line));
		}
		// collect lines where symbols have been referenced
		//foreach (Node n in Node.nodes) {
		for (int i = 0; i < nodes.size(); i++) {
			Node n = (Node)nodes.get(i);
			if (n.typ == Node.t || n.typ == Node.wt || n.typ == Node.nt) {
				ArrayList list = (ArrayList)xref.get(n.sym);
				if (list == null) {list = new ArrayList(); xref.put(n.sym, list);}
				list.add(new Integer(n.line));
			}
		}
		// print cross reference list
		trace.WriteLine();
		trace.WriteLine("Cross reference list:");
		trace.WriteLine("--------------------"); trace.WriteLine();
		//foreach (Symbol sym in xref.Keys) {
		java.util.Iterator iter = xref.keySet().iterator();
		while (iter.hasNext()) {
			Symbol sym = (Symbol)iter.next();
			trace.Write("  ");
			trace.Write(Name(sym.name), -12);
			ArrayList list = (ArrayList)xref.get(sym);
			int col = 14;
			//foreach (int line in list) {
			for (int j = 0; j < list.size(); j++) {
				Integer line = (Integer)list.get(j);
				if (col + 5 > 80) {
					trace.WriteLine();
					for (col = 1; col <= 14; col++) trace.Write(" ");
				}
				trace.Write(line.toString(), 5); col += 5;
			}
			trace.WriteLine();
		}
		trace.WriteLine(); trace.WriteLine();
	}

	public void SetDDT (String s) {
		s = s.toUpperCase();
		for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
			if ('0' <= ch && ch <= '9') ddt[ch - '0'] = true;
			else switch (ch) {
				case 'A' : ddt[0] = true; break; // trace automaton
				case 'F' : ddt[1] = true; break; // list first/follow sets
				case 'G' : ddt[2] = true; break; // print syntax graph
				case 'I' : ddt[3] = true; break; // trace computation of first sets
				case 'J' : ddt[4] = true; break; // print ANY and SYNC sets
				case 'P' : ddt[8] = true; break; // print statistics
				case 'S' : ddt[6] = true; break; // list symbol table
				case 'X' : ddt[7] = true; break; // list cross reference table
				default : break;
			}
		}
	}

}