tab.cs

c#源代码

		for (int i=0; i<max; i++)
			if (b[i] && ! a[i]) return false;
		return true;
	}
	
	public static bool Intersect(BitArray a, BitArray b) { // a * b != {}
		int max = a.Count;
		for (int i=0; i<max; i++)
			if (a[i] && b[i]) return true;
		return false;
	}
	
	public static void Subtract(BitArray a, BitArray b) { // a = a - b
		BitArray c = (BitArray) b.Clone();
		a.And(c.Not());
	}
	
	public static void PrintSet(BitArray s, int indent) {
		int col, len;
		col = indent;
		foreach (Symbol sym in Symbol.terminals) {
			if (s[sym.n]) {
				len = sym.name.Length;
				if (col + len >= 80) {
					Trace.WriteLine();
					for (col = 1; col < indent; col++) Trace.Write(" ");
				}
				Trace.Write("{0} ", sym.name);
				col += len + 1;
			}
		}
		if (col == indent) Trace.Write("-- empty set --");
		Trace.WriteLine();
	}
	
}


//---------------------------------------------------------------------
// Character class management
//---------------------------------------------------------------------

public class CharClass {
	public static ArrayList classes = new ArrayList();
	public static int dummyName = 'A';
	
	public const int charSetSize = 256;  // must be a multiple of 16
	
	public int n;       	// class number
	public string name;		// class name
	public BitArray set;	// set representing the class

	public CharClass(string name, BitArray s) {
		if (name == "#") name = "#" + (char)dummyName++;
		this.n = classes.Count; this.name = name; this.set = s;
		classes.Add(this);
	}
	
	public static CharClass Find(string name) {
		foreach (CharClass c in classes)
			if (c.name == name) return c;
		return null;
	}
	
	public static CharClass Find(BitArray s) {
		foreach (CharClass c in classes)
			if (Sets.Equals(s, c.set)) return c;
		return null;
	}
	
	public static BitArray Set(int i) {
		return ((CharClass)classes[i]).set;
	}
	
	static string Ch(int ch) {
		if (ch < ' ' || ch >= 127 || ch == '\'' || ch == '\\') return ch.ToString();
		else return String.Format("'{0}'", (char)ch);
	}
	
	static void WriteCharSet(BitArray s) {
			int i = 0, len = s.Count;
			while (i < len) {
				while (i < len && !s[i]) i++;
				if (i == len) break;
				int j = i;
				while (i < len && s[i]) i++;
				if (j < i-1) Trace.Write("{0}..{1} ", Ch(j), Ch(i-1)); 
				else Trace.Write("{0} ", Ch(j));
			}
	}
	
	public static void WriteClasses () {
		foreach (CharClass c in classes) {
			Trace.Write("{0,-10}: ", c.name);
			WriteCharSet(c.set);
			Trace.WriteLine();
		}
		Trace.WriteLine();
	}
}


//-----------------------------------------------------------
// Symbol table management routines
//-----------------------------------------------------------

public class Tab {
	public static Position semDeclPos;	    // position of global semantic declarations
	public static BitArray ignored;			    // characters ignored by the scanner
	public static bool[] ddt = new bool[10];	// debug and test switches
	public static Symbol gramSy;				    // root nonterminal; filled by ATG
	public static Symbol eofSy;					    // end of file symbol
	public static Symbol noSym;					    // used in case of an error
	public static BitArray allSyncSets;	    // union of all synchronisation sets
	public static string nsName;            // namespace for generated files
	public static string frameDir = null;   // directory containing the frame files
	public static Hashtable literals;       // symbols that are used as literals
	
	static BitArray visited;						    // mark list for graph traversals
	static Symbol curSy;								    // current symbol in computation of sets
		
	//---------------------------------------------------------------------
	//  Symbol set computations
	//---------------------------------------------------------------------

	/* Computes the first set for the given Node. */
	static BitArray First0(Node p, BitArray mark) {
		BitArray fs = new BitArray(Symbol.terminals.Count);
		while (p != null && !mark[p.n]) {
			mark[p.n] = true;
			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[p.sym.n] = true; 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 (!Node.DelNode(p)) break;
			p = p.next;
		}
		return fs;
	}
	
	public static BitArray First(Node p) {
		BitArray fs = First0(p, new BitArray(Node.nodes.Count));
		if (ddt[3]) {
			Trace.WriteLine(); 
			if (p != null) Trace.WriteLine("First: node = {0}", p.n);
			else Trace.WriteLine("First: node = null");
			Sets.PrintSet(fs, 0);
		}
		return fs;
	}

	static void CompFirstSets() {
		foreach (Symbol sym in Symbol.nonterminals) {
			sym.first = new BitArray(Symbol.terminals.Count);
			sym.firstReady = false;
		}
		foreach (Symbol sym in Symbol.nonterminals) {
			sym.first = First(sym.graph);
			sym.firstReady = true;
		}
	}
	
	static void CompFollow(Node p) {
		while (p != null && !visited[p.n]) {
			visited[p.n] = true;
			if (p.typ == Node.nt) {
				BitArray s = First(p.next);
				p.sym.follow.Or(s);
				if (Node.DelGraph(p.next))
					p.sym.nts[curSy.n] = true;
			} 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;
		}
	}
	
	static void Complete(Symbol sym) {
		if (!visited[sym.n]) {
			visited[sym.n] = true;
			foreach (Symbol s in Symbol.nonterminals) {
				if (sym.nts[s.n]) {
					Complete(s);
					sym.follow.Or(s.follow);
					if (sym == curSy) sym.nts[s.n] = false;
				}
			}
		}
	}
	
	static void CompFollowSets() {
		foreach (Symbol sym in Symbol.nonterminals) {
			sym.follow = new BitArray(Symbol.terminals.Count);
			sym.nts = new BitArray(Symbol.nonterminals.Count);
		}
		gramSy.follow[eofSy.n] = true;
		visited = new BitArray(Node.nodes.Count);
		foreach (Symbol sym in Symbol.nonterminals) { // get direct successors of nonterminals
			curSy = sym;
			CompFollow(sym.graph);
		}
		foreach (Symbol sym in Symbol.nonterminals) { // add indirect successors to followers
			visited = new BitArray(Symbol.nonterminals.Count);
			curSy = sym;
			Complete(sym);
		}
	}
	
	static 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 (Node.DelNode(p) && !p.up) a = LeadingAny(p.next);
		return a;
	}
	
	static 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) {
				BitArray s1 = new BitArray(Symbol.terminals.Count);
				Node q = p;
				while (q != null) {
					FindAS(q.sub);
					a = LeadingAny(q.sub);
					if (a != null)
						Sets.Subtract(a.set, First(q.down).Or(s1));
					else
						s1.Or(First(q.sub));
					q = q.down;
				}
			}
			if (p.up) break;
			p = p.next;
		}
	}
	
	static void CompAnySets() {
		foreach (Symbol sym in Symbol.nonterminals) FindAS(sym.graph);
	}
	
	public static BitArray Expected(Node p, Symbol curSy) {
		BitArray s = First(p);
		if (Node.DelGraph(p)) s.Or(curSy.follow);
		return s;
	}

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

	static void CompSync(Node p) {
		while (p != null && !visited[p.n]) {
			visited[p.n] = true;
			if (p.typ == Node.sync) {
				BitArray s = Expected(p.next, curSy);
				s[eofSy.n] = true;
				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;
		}
	}
	
	static void CompSyncSets() {
		allSyncSets = new BitArray(Symbol.terminals.Count);
		allSyncSets[eofSy.n] = true;
		visited = new BitArray(Node.nodes.Count);
		foreach (Symbol sym in Symbol.nonterminals) {
			curSy = sym;
			CompSync(curSy.graph);
		}
	}
	
	public static void SetupAnys() {
		foreach (Node p in Node.nodes)
			if (p.typ == Node.any) {
				p.set = new BitArray(Symbol.terminals.Count, true);
				p.set[eofSy.n] = false;
			}
	}
	
	public static void CompDeletableSymbols() {
		bool changed;
		do {
			changed = false;
			foreach (Symbol sym in Symbol.nonterminals)
				if (!sym.deletable && sym.graph != null && Node.DelGraph(sym.graph)) {
					sym.deletable = true; changed = true;
				}
		} while (changed);
		foreach (Symbol sym in Symbol.nonterminals)
			if (sym.deletable) Console.WriteLine("  {0} deletable", sym.name);
	}
	
	public static void RenumberPragmas() {
		int n = Symbol.terminals.Count;
		foreach (Symbol sym in Symbol.pragmas) sym.n = n++;
	}

	public static void CompSymbolSets() {
		CompDeletableSymbols();
		CompFirstSets();
		CompFollowSets();
		CompAnySets();
		CompSyncSets();
		if (ddt[1]) {
			Trace.WriteLine();
			Trace.WriteLine("First & follow symbols:");
			Trace.WriteLine("----------------------"); Trace.WriteLine();
			foreach (Symbol sym in Symbol.nonterminals) {
				Trace.WriteLine(sym.name);
				Trace.Write("first:   "); Sets.PrintSet(sym.first, 10);
				Trace.Write("follow:  "); Sets.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)
				if (p.typ == Node.any || p.typ == Node.sync) {
					Trace.Write("{0,4} {1,4}: ", p.n, Node.nTyp[p.typ]);
					Sets.PrintSet(p.set, 11);
				}
		}