tab.cs

c#源代码

/*-------------------------------------------------------------------------
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.Collections;

namespace at.jku.ssw.Coco {

public 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;
	}
}


//---------------------------------------------------------------------
// Symbols
//---------------------------------------------------------------------
	
public class Symbol : IComparable {
	public static ArrayList terminals = new ArrayList();
	public static ArrayList pragmas = new ArrayList();
	public static ArrayList nonterminals = new ArrayList();
	
	// 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) {
		if (name.Length == 2 && name[0] == '"') {
			Parser.SemErr("empty token not allowed"); name = "???";
		}
		this.typ = typ; this.name = name; this.line = line;
		switch (typ) {
			case Node.t:  n = terminals.Count; terminals.Add(this); break;
			case Node.pr: pragmas.Add(this); break;
			case Node.nt: n = nonterminals.Count; nonterminals.Add(this); break;
		}
	}

	public static Symbol Find(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;
	}
	
	public int CompareTo(object x) {
		return name.CompareTo(((Symbol)x).name);
	}
	
}


//---------------------------------------------------------------------
// Syntax graph (class Node, class Graph)
//---------------------------------------------------------------------

public class Node {
	public static ArrayList nodes = new ArrayList();
	public static string[] nTyp =
		{"    ", "t   ", "pr  ", "nt  ", "clas", "chr ", "wt  ", "any ", "eps ",  /* AW 03-01-14 nTyp[0]: " " --> "    " */
		 "sync", "sem ", "alt ", "iter", "opt ", "rslv"};
	
	// 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  /* ML */ /* AW 03-01-13 renamed slv --> rslv */
	
	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;
		n = nodes.Count;
		nodes.Add(this);
	}
	
	public Node(int typ, Node sub): this(typ, null, 0) {
		this.sub = sub;
	}
	
	public Node(int typ, int val, int line): this(typ, null, line) {
		this.val = val;
	}
	
	public static bool DelGraph(Node p) {
		return p == null || DelNode(p) && DelGraph(p.next);
	}
	
	public static bool DelAlt(Node p) {
		return p == null || DelNode(p) && (p.up || DelAlt(p.next));
	}
	
	public static bool DelNode(Node p) {
		if (p.typ == nt) return p.sym.deletable;
		else if (p.typ == alt) return DelAlt(p.sub) || p.down != null && DelAlt(p.down);
		else return p.typ == eps || p.typ == iter || p.typ == opt || p.typ == sem 
			|| p.typ == rslv || p.typ == sync;
	}
	
	//----------------- for printing ----------------------
	
	static int Ptr(Node p, bool up) {
		if (p == null) return 0; 
		else if (up) return -p.n;
		else return p.n;
	}
	
	static string Pos(Position pos) {
		if (pos == null) return "     "; else return String.Format("{0,5}", pos.beg);
	}
	
	public static 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 static 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)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 t: case nt: case wt:
					Trace.Write("             {0,5}", Pos(p.pos)); break;
				case chr:
					Trace.Write("{0,5} {1,5}       ", p.val, p.code); break;
				case clas:
					Trace.Write("      {0,5}       ", p.code); break;
				case alt: case iter: case opt:
					Trace.Write("{0,5} {1,5}       ", Ptr(p.down, false), Ptr(p.sub, false)); break;
				case sem:
					Trace.Write("             {0,5}", Pos(p.pos)); break;
				case eps: case any: case sync:
					Trace.Write("                  "); break;
			}
			Trace.WriteLine("{0,5}", p.line);
		}
		Trace.WriteLine();
	}
	
}


public class Graph {
	static Node dummyNode = new Node(Node.eps, null, 0);
	
	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;
	}

	public static void MakeFirstAlt(Graph g) {
		g.l = new Node(Node.alt, g.l); g.l.line = g.l.sub.line; /* AW 2002-03-07 make line available for error handling */
		g.l.next = g.r;
		g.r = g.l;
	}
	
	public static void MakeAlternative(Graph g1, Graph g2) {
		g2.l = new Node(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 static 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 static void MakeIteration(Graph g) {
		g.l = new Node(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 static void MakeOption(Graph g) {
		g.l = new Node(Node.opt, g.l);
		g.l.next = g.r;
		g.r = g.l;
	}
	
	public static void Finish(Graph g) {
		Node p = g.r;
		while (p != null) {
			Node q = p.next; p.next = null; p = q;
		}
	}
	
  public static void SetContextTrans(Node p) { // set transition code in the graph rooted at p
    DFA.hasCtxMoves = true;
    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;
    }
  }
	
	public static void DeleteNodes() {
		Node.nodes = new ArrayList();
		dummyNode = new Node(Node.eps, null, 0);
	}
	
	public static Graph StrToGraph(string str) {
		string s = DFA.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 = new Node(Node.chr, (int)s[i], 0);
			g.r.next = p; g.r = p;
		}
		g.l = dummyNode.next; dummyNode.next = null;
		return g;
	}
	
}


//----------------------------------------------------------------
// Bit 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;