Coco Custom Tool for Visual Studio.NET

/*-------------------------------------------------------------------------
Tab.cs -- 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
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.
-------------------------------------------------------------------------*/
using System;
using System.IO;
using System.Text;
using System.Collections;
using VsCoco;

namespace at.jku.ssw.Coco 
{

	public class Position 
	{  // position of source code stretch (e.g. semantic action, resolver expressions)

		public int lin;
		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 lin, int col) 
		{
			this.beg = beg; this.len = len; 

			this.lin=lin;
			this.col = col; 
		}
	}


	//=====================================================================
	// Symbol
	//=====================================================================
	
	public class Symbol : IComparable 
	{
	
		// token kinds
		public const int fixedToken    = 0; // e.g. 'a' ('b' | 'c') (structure of literals)
		public const int classToken    = 1;	// e.g. digit {digit}   (at least one char class)
		public const int litToken      = 2; // e.g. "while"
		public const 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 bool     deletable;   // nt: true if nonterminal is deletable
		public bool     firstReady;  // nt: true if terminal start symbols have already been computed
		public BitArray first;       // nt: terminal start symbols
		public BitArray follow;      // nt: terminal followers
		public BitArray 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 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
	//=====================================================================

	public class Node 
	{
		// constants for node kinds
		public const int t    =  1;  // terminal symbol
		public const int pr   =  2;  // pragma
		public const int nt   =  3;  // nonterminal symbol
		public const int clas =  4;  // character class
		public const int chr  =  5;  // character
		public const int wt   =  6;  // weak terminal symbol
		public const int any  =  7;  // 
		public const int eps  =  8;  // empty
		public const int sync =  9;  // synchronization symbol
		public const int sem  = 10;  // semantic action: (. .)
		public const int alt  = 11;  // alternative: |
		public const int iter = 12;  // iteration: { }
		public const int opt  = 13;  // option: [ ]
		public const int rslv = 14;  // resolver expr
	
		public const int normalTrans  = 0;		// transition codes
		public const 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 bool     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 BitArray 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 Node(int typ, Symbol sym, int line) 
		{
			this.typ = typ; this.sym = sym; this.line = line;
		}
	}

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

	public 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() 
		{
			l = null; r = null;
		}
	
		public Graph(Node left, Node right) 
		{
			l = left; r = right;
		}
	
		public Graph(Node p) 
		{
			l = p; r = p;
		}
	}

	//=====================================================================
	// Sets 
	//=====================================================================

	public class Sets 
	{
	
		public static int First(BitArray s) 
		{
			int max = s.Count;
			for (int i=0; i<max; i++)
				if (s[i]) return i;
			return -1;
		}
	
		public static int Elements(BitArray s) 
		{
			int max = s.Count;
			int n = 0;
			for (int i=0; i<max; i++)
				if (s[i]) n++;
			return n;
		}
	
		public static bool Equals(BitArray a, BitArray b) 
		{
			int max = a.Count;
			for (int i=0; i<max; i++)
				if (a[i] != b[i]) return false;
			return true;
		}
	
		public static bool Includes(BitArray a, BitArray b) 
		{	// a > b ?
			int max = a.Count;
			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());
		}
	
	}

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

	public class CharClass 
	{	
		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) 
		{
			this.name = name; this.set = s;
		}
	
	}


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

	public class Tab 
	{
		public Position semDeclPos;       // position of global semantic declarations
		public BitArray ignored;          // characters ignored by the scanner
		public bool[] ddt = new bool[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 BitArray 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;             // namespace for generated files
		public string frameDir;           // directory containing the frame files

		BitArray visited;                 // mark list for graph traversals
		Symbol curSy;                     // current symbol in computation of sets
	
		Parser parser;                    // other Coco objects
		TextWriter 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[0] == '"') 
			{
				parser.SemErr("empty token not allowed"); name = "???";
			}
			Symbol sym = new Symbol(typ, name, line);
			switch (typ) 
			{
				case Node.t:  sym.n = terminals.Count; terminals.Add(sym); break;
				case Node.pr: pragmas.Add(sym); break;
				case Node.nt: sym.n = nonterminals.Count; nonterminals.Add(sym); break;
			}
			return sym;
		}

		public Symbol FindSym(string name) 
		{
			foreach (Symbol s in terminals)
				if (s.name == name) return s;
			foreach (Symbol s in nonterminals)
				if (s.name == name) return s;
			return null;
		}
	
		int Num(Node p) 
		{
			if (p == null) return 0; else return p.n;
		}
	
		void PrintSym(Symbol sym) 
		{
			trace.Write("{0,3} {1,-14} {2}", sym.n, Name(sym.name), nTyp[sym.typ]);
			if (sym.attrPos==null) trace.Write(" false "); else trace.Write(" true  ");
			if (sym.typ == Node.nt) 
			{
				trace.Write("{0,5}", Num(sym.graph));
				if (sym.deletable) trace.Write(" true  "); else trace.Write(" false ");
			} 
			else
				trace.Write("            ");
			trace.WriteLine("{0,5} {1}", sym.line, 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 terminals) PrintSym(sym);
			foreach (Symbol sym in pragmas) PrintSym(sym);
			foreach (Symbol sym in nonterminals) PrintSym(sym);
			trace.WriteLine();
			trace.WriteLine("Literal Tokens:");
			trace.WriteLine("--------------");
			foreach (DictionaryEntry e in literals) 
			{
				trace.WriteLine("_" + ((Symbol)e.Value).name + " = " + e.Key + ".");
			}
			trace.WriteLine();
		}
	
		public void PrintSet(BitArray s, int indent) 
		{
			int col, len;
			col = indent;
			foreach (Symbol sym in 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();
		}
	
		//---------------------------------------------------------------------
		//  Syntax graph management
		//---------------------------------------------------------------------
	
		public ArrayList nodes = new ArrayList();
		public string[] nTyp =
		{
				"    ", "t   ", "pr  ", "nt  ", "clas", "chr ", "wt  ", "any ", "eps ",
			"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.Count;
			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-2));
			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[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 bool DelGraph(Node p) 
		{
			return p == null || DelNode(p) && DelGraph(p.next);
		}
	
		public bool DelSubGraph(Node p) 
		{
			return p == null || DelNode(p) && (p.up || DelSubGraph(p.next));
		}
	
		public bool DelAlt(Node p) 
		{
			return p == null || DelNode(p) && (p.up || DelAlt(p.next));
		}
	
		public bool 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.rslv || p.typ == Node.sync;
		}
	
		//----------------- graph printing ----------------------
	
		int Ptr(Node p, bool 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 String.Format("{0,5}", pos.beg);
		}
	
		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) 
			{
				trace.Write("{0,4} {1} ", p.n, nTyp[p.typ]);
				if (p.sym != null)
					trace.Write("{0,12} ", Name(p.sym.name));
				else if (p.typ == Node.clas) 
				{
					CharClass c = (CharClass)classes[p.val];
					trace.Write("{0,12} ", Name(c.name));
				} 
				else trace.Write("             ");
				trace.Write("{0,5} ", Ptr(p.next, p.up));
				switch (p.typ) 
				{
					case Node.t: case Node.nt: case Node.wt:
						trace.Write("             {0,5}", Pos(p.pos)); break;
					case Node.chr:
						trace.Write("{0,5} {1,5}       ", p.val, p.code); break;
					case Node.clas:
						trace.Write("      {0,5}       ", p.code); break;
					case Node.alt: case Node.iter: case Node.opt:
						trace.Write("{0,5} {1,5}       ", Ptr(p.down, false), Ptr(p.sub, false)); break;
					case Node.sem:
						trace.Write("             {0,5}", Pos(p.pos)); break;
					case Node.eps: case Node.any: case Node.sync:
						trace.Write("                  "); break;
				}
				trace.WriteLine("{0,5}", p.line);
			}
			trace.WriteLine();
		}
	

		//---------------------------------------------------------------------
		//  Character class management
		//---------------------------------------------------------------------
	
		public ArrayList classes = new ArrayList();
		public int dummyName = 'A';

		public CharClass NewCharClass(string name, BitArray s) 
		{
			if (name == "#") name = "#" + (char)dummyName++;
			CharClass c = new CharClass(name, s);
			c.n = classes.Count;
			classes.Add(c);
			return c;
		}

		public CharClass FindCharClass(string name) 
		{
			foreach (CharClass c in classes)
				if (c.name == name) return c;
			return null;
		}
	
		public CharClass FindCharClass(BitArray s) 
		{
			foreach (CharClass c in classes)
				if (Sets.Equals(s, c.set)) return c;
			return null;
		}
	
		public BitArray CharClassSet(int i) 
		{
			return ((CharClass)classes[i]).set;
		}
	
		//----------- character class printing

		string Ch(int ch) 
		{
			if (ch < ' ' || ch >= 127 || ch == '\'' || ch == '\\') return ch.ToString();
			else return String.Format("'{0}'", (char)ch);
		}
	
		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 void WriteCharClasses () 
		{
			foreach (CharClass c in classes) 
			{
				trace.Write("{0,-10}: ", c.name);
				WriteCharSet(c.set);
				trace.WriteLine();
			}
			trace.WriteLine();
		}
	

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

		/* Computes the first set for the graph rooted at p */
		BitArray First0(Node p, BitArray mark) 
		{
			BitArray fs = new BitArray(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 (!DelNode(p)) break;
				p = p.next;
			}
			return fs;
		}
	
		public BitArray First(Node p) 
		{
			BitArray fs = First0(p, new BitArray(nodes.Count));
			if (ddt[3]) 
			{
				trace.WriteLine(); 
				if (p != null) trace.WriteLine("First: node = {0}", p.n);
				else trace.WriteLine("First: node = null");
				PrintSet(fs, 0);
			}
			return fs;
		}

		void CompFirstSets() 
		{
			foreach (Symbol sym in nonterminals) 
			{
				sym.first = new BitArray(terminals.Count);
				sym.firstReady = false;
			}
			foreach (Symbol sym in nonterminals) 
			{
				sym.first = First(sym.graph);
				sym.firstReady = true;
			}
		}
	
		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 (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;
			}
		}
	
		void Complete(Symbol sym) 
		{
			if (!visited[sym.n]) 
			{
				visited[sym.n] = true;
				foreach (Symbol s in nonterminals) 
				{
					if (sym.nts[s.n]) 
					{
						Complete(s);
						sym.follow.Or(s.follow);
						if (sym == curSy) sym.nts[s.n] = false;
					}
				}
			}
		}
	
		void CompFollowSets() 
		{
			foreach (Symbol sym in nonterminals) 
			{
				sym.follow = new BitArray(terminals.Count);
				sym.nts = new BitArray(nonterminals.Count);
			}
			gramSy.follow[eofSy.n] = true;
			visited = new BitArray(nodes.Count);
			foreach (Symbol sym in nonterminals) 
			{ // get direct successors of nonterminals
				curSy = sym;
				CompFollow(sym.graph);
			}
			foreach (Symbol sym in nonterminals) 
			{ // add indirect successors to followers
				visited = new BitArray(nonterminals.Count);
				curSy = sym;
				Complete(sym);
			}
		}
	
		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) 
				{
					BitArray s1 = new BitArray(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;
			}
		}
	
		void CompAnySets() 
		{
			foreach (Symbol sym in nonterminals) FindAS(sym.graph);
		}
	
		public BitArray Expected(Node p, Symbol curSy) 
		{
			BitArray 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 BitArray Expected0(Node p, Symbol curSy) 
		{
			if (p.typ == Node.rslv) return new BitArray(terminals.Count);
			else return Expected(p, curSy);
		}

		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;
			}
		}
	
		void CompSyncSets() 
		{
			allSyncSets = new BitArray(terminals.Count);
			allSyncSets[eofSy.n] = true;
			visited = new BitArray(nodes.Count);
			foreach (Symbol sym in nonterminals) 
			{
				curSy = sym;
				CompSync(curSy.graph);
			}
		}
	
		public void SetupAnys() 
		{
			foreach (Node p in nodes)
				if (p.typ == Node.any) 
				{
					p.set = new BitArray(terminals.Count, true);
					p.set[eofSy.n] = false;
				}
		}
	
		public void CompDeletableSymbols() 
		{
			bool changed;
			do 
			{
				changed = false;
				foreach (Symbol sym in nonterminals)
					if (!sym.deletable && sym.graph != null && DelGraph(sym.graph)) 
					{
						sym.deletable = true; changed = true;
					}
			} while (changed);
			foreach (Symbol sym in nonterminals)
				if (sym.deletable) parser.scanner.WriteLine(string.Format("{0} deletable", sym.name));
		}
	
		public void RenumberPragmas() 
		{
			int n = terminals.Count;
			foreach (Symbol sym in pragmas) 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();
				foreach (Symbol sym in nonterminals) 
				{
					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 nodes)
					if (p.typ == Node.any || p.typ == Node.sync) 
					{
						trace.Write("{0,4} {1,4}: ", p.n, nTyp[p.typ]);
						PrintSet(p.set, 11);
					}
			}
		}
	
		//---------------------------------------------------------------------
		//  String handling
		//---------------------------------------------------------------------
	
		char Hex2Char(string s) 
		{
			int val = 0;
			for (int i = 0; i < s.Length; i++) 
			{
				char ch = s[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 > CharClass.charSetSize) /* pdt */
				parser.SemErr("bad escape sequence in string or character");
			return (char) (val % CharClass.charSetSize);
		}

		string Char2Hex(char ch) 
		{
			StringWriter w = new StringWriter();
			w.Write("\\u{0:x4}", (int)ch);
			return w.ToString();
		}

		public string Unescape (string s) 
		{
			/* replaces escape sequences in s by their Unicode values. */
			StringBuilder buf = new StringBuilder();
			int i = 0;
			while (i < s.Length) 
			{
				if (s[i] == '\\') 
				{
					switch (s[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 'a': buf.Append('\a'); i += 2; break;
						case 'b': buf.Append('\b'); i += 2; break;
						case 'f': buf.Append('\f'); i += 2; break;
						case 'v': buf.Append('\v'); i += 2; break;
						case 'u': case 'x':
							if (i + 6 <= s.Length) 
							{
								buf.Append(Hex2Char(s.Substring(i+2, 4))); 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[i]);
					i++;
				}
			}
			return buf.ToString();
		}

		public string Escape (string s) 
		{
			StringBuilder buf = new StringBuilder();
			foreach (char ch in s) 
			{
				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 bool GrammarOk() 
		{
			bool ok = NtsComplete() 
				&& AllNtReached() 
				&& NoCircularProductions()
				&& AllNtToTerm()
				&& ResolversOk();
			if (ok) 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 bool NoCircularProductions() 
		{
			bool ok, changed, onLeftSide, onRightSide;
			ArrayList list = new ArrayList();
			foreach (Symbol sym in nonterminals) 
			{
				ArrayList singles = new ArrayList();
				GetSingles(sym.graph, singles); // get nonterminals s such that sym-->s
				foreach (Symbol s in singles) list.Add(new CNode(sym, s));
			}
			do 
			{
				changed = false;
				for (int i = 0; i < list.Count; i++) 
				{
					CNode n = (CNode)list[i];
					onLeftSide = false; onRightSide = false;
					foreach (CNode m in list) 
					{
						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;
			foreach (CNode n in list) 
			{
				ok = false; errors.count++;
				this.parser.scanner.WriteLine(string.Format("{0} --> {1}", n.left.name, n.right.name));
			}
			return ok;
		}
	



		//--------------- check for LL(1) errors ----------------------
	
		void LL1Warning(int cond, Symbol sym) 
		{
			string msg=String.Format("LL1 warning in {0}: ", curSy.name);
			if (sym != null) msg+=String.Format("{0} is ", sym.name);
		
			switch (cond) 
			{
				case 1: msg+="start of several alternatives"; break;
				case 2: msg+="start & successor of deletable structure"; break;
				case 3: msg+="an ANY node that matches no symbol"; break;
				case 4: msg+="contents of [...] or {...} must not be deletable"; break;
			}
			int lin=1;
			int col=1;
			if (curSy!=null && curSy.attrPos!=null) 
			{
				lin=curSy.attrPos.lin;
				col=curSy.attrPos.col;
			}
			vsCoco.WriteError(0,0,vsCoco.ErrorLevel.warning,msg);
		}

		void CheckOverlap(BitArray s1, BitArray s2, int cond) 
		{
			foreach (Symbol sym in terminals) 
			{
				if (s1[sym.n] && s2[sym.n]) LL1Warning(cond, sym);
			}
		}
	
		void CheckAlts(Node p) 
		{
			BitArray s1, s2;
			while (p != null) 
			{
				if (p.typ == Node.alt) 
				{
					Node q = p;
					s1 = new BitArray(terminals.Count);
					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)) LL1Warning(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) LL1Warning(3, null);
					// e.g. {ANY} ANY or [ANY] ANY
				}
				if (p.up) break;
				p = p.next;
			}
		}

		public void CheckLL1() 
		{
			foreach (Symbol sym in nonterminals) 
			{
				curSy = sym;
				CheckAlts(curSy.graph);
			}
		}
	
		//------------- check if resolvers are legal  --------------------
	
		bool resOk;
	
		void ResErr(Node p, string msg) 
		{
			vsCoco.WriteError(p.line,p.pos.col,vsCoco.ErrorLevel.error,msg);
			resOk = false;
		}
	
		void CheckRes(Node p, bool rslvAllowed) 
		{
			while (p != null) 
			{
				switch (p.typ) 
				{
					case Node.alt:
						BitArray expected = new BitArray(terminals.Count);
						for (Node q = p; q != null; q = q.down)
							expected.Or(Expected0(q.sub, curSy));
						BitArray soFar = new BitArray(terminals.Count);
						for (Node q = p; q != null; q = q.down) 
						{
							if (q.sub.typ == Node.rslv) 
							{
								BitArray fs = Expected(q.sub.next, curSy);
								if (Sets.Intersect(fs, soFar))
									ResErr(q.sub, "Resolver will never be evaluated. " +
										"Place it at previous conflicting alternative.");
								if (!Sets.Intersect(fs, expected))
									ResErr(q.sub, "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) 
						{
							BitArray fs = First(p.sub.next);
							BitArray fsNext = Expected(p.next, curSy);
							if (!Sets.Intersect(fs, fsNext)) 
								ResErr(p.sub, "Misplaced resolver: no LL(1) conflict.");
						}
						CheckRes(p.sub, true);
						break;
					case Node.rslv:
						if (!rslvAllowed)
							ResErr(p, "Misplaced resolver: no alternative.");
						break;
				}
				if (p.up) break;
				p = p.next;
				rslvAllowed = false;
			}
		}
	
		public bool ResolversOk() 
		{
			resOk = true;
			foreach (Symbol sym in nonterminals) 
			{
				curSy = sym;
				CheckRes(curSy.graph, false);
			}
			return resOk;
		}

		//------------- check if every nts has a production --------------------
	
		public bool NtsComplete() 
		{
			bool complete = true;
			foreach (Symbol sym in nonterminals) 
			{
				if (sym.graph == null) 
				{
					complete = false; errors.count++;
					this.parser.scanner.WriteLine(string.Format("No production for {0}", sym.name));
				}
			}
			return complete;
		}
	
		//-------------- check if every nts can be reached  -----------------
	
		void MarkReachedNts(Node p) 
		{
			while (p != null) 
			{
				if (p.typ == Node.nt && !visited[p.sym.n]) 
				{ // new nt reached
					visited[p.sym.n] = true;
					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 bool AllNtReached() 
		{
			bool ok = true;
			visited = new BitArray(nonterminals.Count);
			visited[gramSy.n] = true;
			MarkReachedNts(gramSy.graph);
			foreach (Symbol sym in nonterminals) 
			{
				if (!visited[sym.n]) 
				{
					ok = false; errors.count++;
					this.parser.scanner.WriteLine(string.Format("{0} cannot be reached", sym.name));
				}
			}
			return ok;
		}
	
		//--------- check if every nts can be derived to terminals  ------------
	
		bool IsTerm(Node p, BitArray mark) 
		{ // true if graph can be derived to terminals
			while (p != null) 
			{
				if (p.typ == Node.nt && !mark[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 bool AllNtToTerm() 
		{
			bool changed, ok = true;
			BitArray mark = new BitArray(nonterminals.Count);
			// a nonterminal is marked if it can be derived to terminal symbols
			do 
			{
				changed = false;
				foreach (Symbol sym in nonterminals)
					if (!mark[sym.n] && IsTerm(sym.graph, mark)) 
					{
						mark[sym.n] = true; changed = true;
					}
			} while (changed);
			foreach (Symbol sym in nonterminals)
				if (!mark[sym.n]) 
				{
					ok = false; errors.count++;
					this.parser.scanner.WriteLine(string.Format("{0} cannot be derived to terminals", sym.name));
				}
			return ok;
		}
	
		//---------------------------------------------------------------------
		//  Cross reference list
		//---------------------------------------------------------------------
	
		public void XRef() 
		{
			SortedList xref = new SortedList();
			// collect lines where symbols have been defined
			foreach (Symbol sym in nonterminals) 
			{
				ArrayList list = (ArrayList)xref[sym];
				if (list == null) {list = new ArrayList(); xref[sym] = list;}
				list.Add(- sym.line);
			}
			// collect lines where symbols have been referenced
			foreach (Node n in nodes) 
			{
				if (n.typ == Node.t || n.typ == Node.wt || n.typ == Node.nt) 
				{
					ArrayList list = (ArrayList)xref[n.sym];
					if (list == null) {list = new ArrayList(); xref[n.sym] = list;}
					list.Add(n.line);
				}
			}
			// print cross reference list
			trace.WriteLine();
			trace.WriteLine("Cross reference list:");
			trace.WriteLine("--------------------"); trace.WriteLine();
			foreach (Symbol sym in xref.Keys) 
			{
				trace.Write("  {0,-12}", Name(sym.name));
				ArrayList list = (ArrayList)xref[sym];
				int col = 14;
				foreach (int line in list) 
				{
					if (col + 5 > 80) 
					{
						trace.WriteLine();
						for (col = 1; col <= 14; col++) trace.Write(" ");
					}
					trace.Write("{0,5}", line); col += 5;
				}
				trace.WriteLine();
			}
			trace.WriteLine(); trace.WriteLine();
		}
	
		public void SetDDT(string s) 
		{
			s = s.ToUpper();
			foreach (char ch in s) 
			{
				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
						 case 'L' : ddt[9] = true; break; // #line
						 default : break;
					 }
			}
		}

	} // end Tab

} // end namespace