Click here to Skip to main content
11,706,979 members (45,377 online)
Click here to Skip to main content
Articles » Languages » C# » General » Downloads
Add your own
alternative version

Coco Custom Tool for Visual Studio.NET

, 29 Oct 2005 CPOL 90.9K 604 52
Use the award winning Coco compiler's compiler directly from within Visual Studio
vscoco.zip
vsCoco
bin
VsCoco.dll
vsCoco.tlb
vsCocoRegistration.exe
Calculator
App.ico
Calc.atg
Calculator.csproj.user
Calculator.suo
VsCoCo
vsCoco.png
Coco
Coco.atg
Parser.frame
Scanner.frame
CustomToolGenerator
vsCoco
VsCoco.csproj.user
vsCocoRegistration
reg.ico
Thumbs.db
vsCocoRegistration.csproj.user
/*-------------------------------------------------------------------------
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

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Pascal Ganaye
Software Developer (Senior)
United Kingdom United Kingdom
I am a French programmer.
These days I spend most of my time with the .NET framework, JavaScript and html.

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150819.1 | Last Updated 29 Oct 2005
Article Copyright 2005 by Pascal Ganaye
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid