tab.java

cocorj09-一个Java语言分析器

package Coco;

import java.io.*;
import java.util.*;

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

class SymInfo {
	String name;
	int kind;           // 0 = ident, 1 = string
}

class Symbol {
	int typ;            // t, nt, pr, unknown
	String name;        // symbol name
	String symName;     // symbolic name
	int struct;         // nt: index of first node of syntax graph
	                    // t:  token kind (literal, class, ...)
	boolean deletable;  // nt: true if nonterminal is deletable
	Position attrPos;   // position of attributes in source text (or null)
	String retType;     // nt: Type of output attribute (or null)
	String retVar;      // nt: Name of output attribute (or null)
	Position semPos;    // pr: pos of semantic action in source text (or null)
	                    // nt: pos of local declarations in source text (or null)
	int line;           // source text line number of item in this node
}

class GraphNode {
	int typ;            // t, nt, wt, chr, clas, any, eps, sem, sync, alt, iter, opt
	int next;           // index of successor node
	                    // next<0: to successor in enclosing structure
	int p1;             // nt, t, wt: index to symbol list
	                    // any:       index to any-set
	                    // sync:      index to sync-set
	                    // alt:       index of 1st node of 1st alternative
	                    // iter, opt: 1st node in subexpression
	                    // chr:       ordinal character value
	                    // clas:      index of character class
	int p2;             // alt:       index of 1st node of next alternative
	                    // chr, clas: transition code
	Position pos;       // nt, t, wt: pos of actual attributes
	                    // sem:       pos of semantic action in source text
	String retVar;      // nt: name of output attribute (or null)
	int line;           // source text line number of item in this node
	State state;        // DFA state corresponding to this node
	                    // (only used in Sgen.ConvertToStates)
}

class FirstSet {
	BitSet ts;          // terminal symbols
	boolean ready;      // if true, ts is complete
}

class FollowSet {
	BitSet ts;          // terminal symbols
	BitSet nts;         // nonterminals whose start set is to be included into ts
}

class CharClass {
	String name;        // class name
	int set;            // index of set representing the class
}

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

class XNode {        // node of cross reference list
	int line;
	XNode next;
}

class CNode {        // node of list for finding circular productions
	int left, right;
	boolean deleted;
}

class UserName {     // user defined aliases for terminal names
	String alias, str;
}

class Tab {

	/*--- constants ---*/
	static final int maxSymbols   =  300; // max. no. of t, nt, and pragmas
	static final int maxTerminals =  256; // max. no. of terminals
	static final int maxNt        =  128; // max. no. of nonterminals
	static final int maxNodes     = 1500; // max. no. of graph nodes
	static final int maxSetNr     =  128; // max. no. of symbol sets
	static final int maxClasses   =   50; // max. no. of character classes
	static final int maxList      =  150; // max. no. of elements in checking circular
	static final int maxNames     =  150; // max. no. of user defined names
	static final int lineLength   =   80; // linelength in listing file

	static final int t    = 1;            // node kinds
	static final int pr   = 2;
	static final int nt   = 3;
	static final int clas = 4;
	static final int chr  = 5;
	static final int wt   = 6;
	static final int any  = 7;
	static final int eps  = 8;
	static final int sync = 9;
	static final int sem  = 10;
	static final int alt  = 11;
	static final int iter = 12;
	static final int opt  = 13;

	static final int classToken    = 0;   // token kinds
	static final int litToken      = 1;
	static final int classLitToken = 2;

	static final int normTrans    = 0;    // transition codes
	static final int contextTrans = 1;

	static final int eofSy = 0;
	static final int noSym = -1;

	/*--- variables ---*/
	static int maxSet;              // index of last set
	static int maxT;                // terminals stored from 0 to maxT
	static int maxP;                // pragmas stored from maxT+1 to maxP
	static int firstNt;             // index of first nt: available after CompSymbolSets
	static int lastNt;              // index of last nt: available after CompSymbolSets
	static int maxC;                // index of last character class
	static int lastName;            // index of last user defined name
	static Position semDeclPos;     // position of global semantic declarations
	static Position importPos;      // position of imported identifiers
	static BitSet ignored;          // characters ignored by the scanner
	static boolean[] ddt = new boolean[10]; // debug and test switches
	static int nNodes;              // index of last graph node
	static int gramSy;              // root nonterminal; filled by ATG

	static Symbol[] sy = new Symbol[maxSymbols];            // symbol table
	static GraphNode[] gn = new GraphNode[maxNodes];        // grammar graph
	static FirstSet[] first = new FirstSet[maxNt];          // first[i] = start symbols of sy[i+firstNt]
	static FollowSet[] follow = new FollowSet[maxNt];       // follow[i] = followers of sy[i+firstNt]
	static CharClass[] chClass = new CharClass[maxClasses]; // character classes
	static BitSet[] set = new BitSet[maxSetNr];             // set[0] = union of all synchr. sets
	static UserName[] NameTab = new UserName[maxNames];     // user defined names

	static ErrorStream err;         // error messages
	static int dummyName;           // for unnamed character classes
	static BitSet visited, termNt;  // mark lists for graph traversals
	static int curSy;               // current symbol in computation of sets
	static String[] nTyp =
		{" ", "t   ", "pr  ", "nt  ", "clas", "chr ", "wt  ", "any ", "eps ", "sync",
		"sem ", "alt ", "iter", "opt "};

	static void Assert(boolean cond, int n) {
		if (!cond) {
			System.out.println("-- Coco/R fatal error ");
			switch (n) {
				case 3: {System.out.println("-- too many nodes in graph"); break;}
				case 4: {System.out.println("-- too many sets"); break;}
				case 5: {System.out.println("-- too many symbol sets"); break;}
				case 6: {System.out.println("-- too many symbols"); break;}
				case 7: {System.out.println("-- too many character classes"); break;}
				case 8: {System.out.println("-- too many token names"); break;}
				case 9: {System.out.println("-- circular check buffer overflow"); break;}
			}
			System.exit(n);
		}
	}

	/*---------------------------------------------------------------------
	  Symbol table management
	---------------------------------------------------------------------*/

	static int NewSym(int typ, String name, int line) {
		Symbol s;
		int i = 0;
		Assert(maxT+1 < firstNt, 6);
		switch (typ) {
			case t:  {maxT++; i = maxT; break;}
			case pr: {maxP--; firstNt--; lastNt--; i = maxP; break;}
			case nt: {firstNt--; i = firstNt; break;}
		}
		Assert(maxT+1 < firstNt, 6);
		s = new Symbol();
		s.typ = typ; s.name = name; s.line = line;
		sy[i] = s;
		return i;
	}

	static Symbol Sym(int i) {
		return sy[i];
	}

	static int FindSym(String name) {
		int i;
		for (i=0; i<=maxT; i++)
			if (name.equals(sy[i].name)) return i;
		for (i=firstNt; i<maxSymbols; i++)
			if (name.equals(sy[i].name)) return i;
		return noSym;
	}

	/*---------------------------------------------------------------------
	  topdown graph management
	---------------------------------------------------------------------*/

	static int NewNode(int typ, int p1, int line) {
		GraphNode n;
		nNodes++; Assert(nNodes <= maxNodes, 3);
		n = new GraphNode();
		n.typ = typ; n.p1 = p1; n.line = line;
		gn[nNodes] = n;
		return nNodes;
	}

	static GraphNode Node(int i) {
		return gn[i];
	}

	static void CompleteGraph(int p) {
		int q;
		while (p != 0) {
			q = gn[p].next; gn[p].next = 0; p = q;
		}
	}

	static Graph Alternative(Graph g1, Graph g2) {
		int p;
		g2.l = NewNode(alt, g2.l, 0);
		p = g1.l; while (gn[p].p2 != 0) p = gn[p].p2;
		gn[p].p2 = g2.l;
		p = g1.r; while (gn[p].next != 0) p = gn[p].next;
		gn[p].next = g2.r;
		return g1;
	}

	static Graph Sequence(Graph g1, Graph g2) {
		int p, q;
		p = gn[g1.r].next; gn[g1.r].next = g2.l; // head node
		while (p != 0) { // substructure
			q = gn[p].next; gn[p].next = -g2.l; p = q;
		}
		g1.r = g2.r;
		return g1;
	}

	static Graph FirstAlt(Graph g) {
		g.l = NewNode(alt, g.l, 0); gn[g.l].next = g.r; g.r = g.l;
		return g;
	}

	static Graph Iteration(Graph g) {
		int p, q;
		g.l = NewNode(iter, g.l, 0);
		p = g.r; g.r = g.l;
		while (p != 0) {
			q = gn[p].next; gn[p].next = -g.l; p = q;
		}
		return g;
	}

	static Graph Option(Graph g) {
		g.l = NewNode(opt, g.l, 0); gn[g.l].next = g.r; g.r = g.l;
		return g;
	}

	static Graph StrToGraph(String s) {
		int len = s.length() - 1;
		Graph g = new Graph();
		for (int i=1; i<len; i++) {
			gn[g.r].next = NewNode(chr, (int) s.charAt(i), 0);
			g.r = gn[g.r].next;
		}
		g.l = gn[0].next; gn[0].next = 0;
		return g;
	}

	static boolean DelGraph(int p) {
		GraphNode n;
		if (p==0) return true; // end of graph found
		n = Node(p);
		return DelNode(n) && DelGraph(Math.abs(n.next));
	}

	static boolean DelAlt(int p) {
		GraphNode n;
		if (p<=0) return true; // end of graph found
		n = Node(p);
		return DelNode(n) && DelAlt(n.next);
	}

	static boolean DelNode(GraphNode n) {
		if (n.typ==nt) return sy[n.p1].deletable;
		else if (n.typ==alt) return DelAlt(n.p1) || n.p2!=0 && DelAlt(n.p2);
		else return n.typ==eps || n.typ==iter || n.typ==opt || n.typ==sem || n.typ==sync;
	}

	static void PrintGraph() {
		GraphNode n;
		Trace.println("Graph:");
		Trace.println("  nr typ  next   p1   p2 line");
		for (int i=1; i<=nNodes; i++) {
			n = Node(i);
			Trace.println(Int(i,4) + " " + nTyp[n.typ] + Int(n.next,5) +Int(n.p1,5)
				+ Int(n.p2,5) + Int(n.line,5));
		}
		Trace.println();
	}

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

	static int NewClass(String name, BitSet s) {
		CharClass c;
		maxC++; Assert(maxC < maxClasses, 7);
		if (name.equals("#")) name = new String("#" + (char)((int)'A' + dummyName++));
		c = new CharClass(); c.name = name; c.set = NewSet(s);
		chClass[maxC] = c;
		return maxC;
	}

	static int ClassWithName(String name) {
		int i;
		for (i=maxC; i>=0 && !name.equals(chClass[i].name); i--);
		return i;
	}

	static int ClassWithSet(BitSet s) {
		int i;
		for (i=maxC; i>=0 && !s.equals(set[chClass[i].set]); i--);
		return i;
	}

	static BitSet Class(int i) {
		return set[chClass[i].set];
	}

	static String ClassName(int i) {
		return chClass[i].name;
	}

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

	static void PrintSet(BitSet s, int indent) {
		int col, i, len;
		col = indent;
		for (i=0; i<=maxT; i++) {
			if (s.get(i)) {
				len = sy[i].name.length();
				if (col + len + 1 > lineLength) {
					Trace.println();
					for (col=1; col<indent; col++) Trace.print(" ");
				}
				Trace.print(sy[i].name + "  ");
				col += len + 2;
			}
		}
		if (col==indent) Trace.print("-- empty set --");
		Trace.println();
	}

	static int NewSet(BitSet s) {
		maxSet++; Assert(maxSet <= maxSetNr, 4);
		set[maxSet] = s;
		return maxSet;
	}

	static BitSet Set(int i) {
		return set[i];
	}

	static private BitSet First0(int p, BitSet mark) {
		GraphNode n;
		BitSet s1, s2, fs = new BitSet();
		while (p!=0 && !mark.get(p)) {
			n = Node(p); mark.set(p);
			switch (n.typ) {
				case nt: {
					if (first[n.p1-firstNt].ready) fs.or(first[n.p1-firstNt].ts);
					else fs.or(First0(sy[n.p1].struct, mark));
					break;
				}
				case t: case wt: {
					fs.set(n.p1); break;
				}
				case any: {
					fs.or(set[n.p1]); break;
				}
				case alt: case iter: case opt: {
					fs.or(First0(n.p1, mark));
					if (n.typ==alt)
						fs.or(First0(n.p2, mark));
					break;
				}
			}
			if (!DelNode(n)) break;
			p = Math.abs(n.next);
		}
		return fs;
	}

	static BitSet First(int p) {
		BitSet fs = First0(p, new BitSet(nNodes+1));
		if (ddt[3]) {Trace.println(); Trace.println("First: gp = " + p); PrintSet(fs, 0);}
		return fs;
	}

	static private void CompFirstSets() {
		FirstSet s;
		int i;
		for (i=firstNt; i<=lastNt; i++) {
			s = new FirstSet();
			s.ts = new BitSet(); s.ready = false;
			first[i-firstNt] = s;
		}
		for (i=firstNt; i<=lastNt; i++) {
			first[i-firstNt].ts = First(sy[i].struct);
			first[i-firstNt].ready = true;
		}
	}

	static private void CompFollow(int p) {
		GraphNode n;
		BitSet s;
		while (p>0 && !visited.get(p)) {
			n = Node(p); visited.set(p);
			if (n.typ==nt) {
				s = First(Math.abs(n.next));
				follow[n.p1-firstNt].ts.or(s);
				if (DelGraph(Math.abs(n.next)))
					follow[n.p1-firstNt].nts.set(curSy-firstNt);
			} else if (n.typ==opt || n.typ==iter) {
				CompFollow(n.p1);
			} else if (n.typ==alt) {
				CompFollow(n.p1); CompFollow(n.p2);
			}
			p = n.next;
		}
	}

	static private void Complete(int i) {
		if (!visited.get(i)) {
			visited.set(i);
			for (int j=0; j<=lastNt-firstNt; j++) { // for all nonterminals
				if (follow[i].nts.get(j)) {
					Complete(j);
					follow[i].ts.or(follow[j].ts);
					if (i == curSy) follow[i].nts.clear(j);
				}
			}
		}
	}

	static private void CompFollowSets() {
		FollowSet s;
		for (curSy=firstNt; curSy<=lastNt/*+1*/; curSy++) {
			s = new FollowSet();
			s.ts = new BitSet(); s.nts = new BitSet();
			follow[curSy-firstNt] = s;
		}
		visited = new BitSet();
		for (curSy=firstNt; curSy<=lastNt; curSy++) // get direct successors of nonterminals
			CompFollow(sy[curSy].struct);
		// CompFollow(root); // curSy = lastNt+1
		for (curSy=0; curSy<=lastNt-firstNt; curSy++) { // add indirect successors to follow.ts
			visited = new BitSet();
			Complete(curSy);
		}
	}

	static private GraphNode LeadingAny(int p) {
		GraphNode n, a = null;
		if (p <= 0) return null;
		n = Node(p);
		if (n.typ==any) a = n;
		else if (n.typ==alt) {
			a = LeadingAny(n.p1);
			if (a==null) a = LeadingAny(n.p2);
		}
		else if (n.typ==opt || n.typ==iter) a = LeadingAny(n.p1);
		else if (DelNode(n)) a = LeadingAny(n.next);
		return a;
	}

	static private void FindAS(int p) {
		GraphNode n, nod, a;
		BitSet s1, s2;
		int q;
		while (p > 0) {
			n = Node(p);
			if (n.typ==opt || n.typ==iter) {
				FindAS(n.p1);
				a = LeadingAny(n.p1);
				if (a!=null) {
					s1 = First(Math.abs(n.next));
					Sets.Differ(set[a.p1], s1);
				}
			} else if (n.typ==alt) {
				s1 = new BitSet();
				q = p;
				while (q != 0) {
					nod = Node(q); FindAS(nod.p1);
					a = LeadingAny(nod.p1);