tab.cs

c#源代码

	}
	
	//---------------------------------------------------------------------
	//  Grammar checks
	//---------------------------------------------------------------------
	
	public static 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;
		}
	}

	static void GetSingles(Node p, ArrayList singles) {
		if (p == null) return;  // end of graph
		if (p.typ == Node.nt) {
			if (p.up || Node.DelGraph(p.next)) singles.Add(p.sym);
		} else if (p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt) {
			if (p.up || Node.DelGraph(p.next)) {
				GetSingles(p.sub, singles);
				if (p.typ == Node.alt) GetSingles(p.down, singles);
			}
		}
		if (!p.up && Node.DelNode(p)) GetSingles(p.next, singles);
	}
	
	public static bool NoCircularProductions() {
		bool ok, changed, onLeftSide, onRightSide;
		ArrayList list = new ArrayList();
		foreach (Symbol sym in Symbol.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++;
			Console.WriteLine("  {0} --> {1}", n.left.name, n.right.name);
		}
		return ok;
	}
	
	//--------------- check for LL(1) errors ----------------------
	
	static void LL1Error(int cond, Symbol sym) {
		Console.Write("  LL1 warning in {0}: ", curSy.name);
		if (sym != null) Console.Write("{0} is ", sym.name);
		switch (cond) {
			case 1: Console.WriteLine("start of several alternatives"); break;
			case 2: Console.WriteLine("start & successor of deletable structure"); break;
			case 3: Console.WriteLine("an ANY node that matches no symbol"); break;
		}
	}
	
	static void CheckOverlap(BitArray s1, BitArray s2, int cond) {
		foreach (Symbol sym in Symbol.terminals) {
			if (s1[sym.n] && s2[sym.n]) LL1Error(cond, sym);
		}
	}
	
	static void CheckAlts(Node p) {
		BitArray s1, s2;
		while (p != null) {
			if (p.typ == Node.alt) {
				Node q = p;
				s1 = new BitArray(Symbol.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) {
				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) LL1Error(3, null);
				// e.g. {ANY} ANY or [ANY] ANY
			}
			if (p.up) break;
			p = p.next;
		}
	}

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

	//------------- check if every nts has a production --------------------
	
	public static bool NtsComplete() {
		bool complete = true;
		foreach (Symbol sym in Symbol.nonterminals) {
			if (sym.graph == null) {
				complete = false; Errors.count++;
				Console.WriteLine("  No production for {0}", sym.name);
			}
		}
		return complete;
	}
	
	//-------------- check if every nts can be reached  -----------------
	
	static 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 static bool AllNtReached() {
		bool ok = true;
		visited = new BitArray(Symbol.nonterminals.Count);
		visited[gramSy.n] = true;
		MarkReachedNts(gramSy.graph);
		foreach (Symbol sym in Symbol.nonterminals) {
			if (!visited[sym.n]) {
				ok = false; Errors.count++;
				Console.WriteLine("  {0} cannot be reached", sym.name);
			}
		}
		return ok;
	}
	
	//--------- check if every nts can be derived to terminals  ------------
	
	static 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 static bool AllNtToTerm() {
		bool changed, ok = true;
		BitArray mark = new BitArray(Symbol.nonterminals.Count);
		// a nonterminal is marked if it can be derived to terminal symbols
		do {
			changed = false;
			foreach (Symbol sym in Symbol.nonterminals)
				if (!mark[sym.n] && IsTerm(sym.graph, mark)) {
					mark[sym.n] = true; changed = true;
				}
		} while (changed);
		foreach (Symbol sym in Symbol.nonterminals)
			if (!mark[sym.n]) {
				ok = false; Errors.count++;
				Console.WriteLine("  {0} cannot be derived to terminals", sym.name);
			}
		return ok;
	}
	
	/*---------------------------------------------------------------------
	  Utility functions
	---------------------------------------------------------------------*/
	
	static int Num(Node p) {
		if (p == null) return 0; else return p.n;
	}
	
	static string[] tKind = {"fixedToken", "classToken", "litToken", "classLitToken"};
	
	static void PrintSym(Symbol sym) {
		Trace.Write("{0,3} {1,-14} {2}", sym.n, Node.Name(sym.name), Node.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 static void PrintSymbolTable() {
		Trace.WriteLine("Symbol Table:");
		Trace.WriteLine("------------"); Trace.WriteLine();
		Trace.WriteLine(" nr name          typ  hasAt graph  del    line tokenKind");
		foreach (Symbol sym in Symbol.terminals) PrintSym(sym);
		foreach (Symbol sym in Symbol.pragmas) PrintSym(sym);
		foreach (Symbol sym in Symbol.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 static void XRef() {
		SortedList tab = new SortedList();
		// collect lines where symbols have been defined
		foreach (Symbol sym in Symbol.nonterminals) {
			ArrayList list = (ArrayList)tab[sym];
			if (list == null) {list = new ArrayList(); tab[sym] = list;}
			list.Add(- sym.line);
		}
		// collect lines where symbols have been referenced
		foreach (Node n in Node.nodes) {
			if (n.typ == Node.t || n.typ == Node.wt || n.typ == Node.nt) {
				ArrayList list = (ArrayList)tab[n.sym];
				if (list == null) {list = new ArrayList(); tab[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 tab.Keys) {
			Trace.Write("  {0,-12}", Node.Name(sym.name));
			ArrayList list = (ArrayList)tab[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 static 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
				default : break;
			}
		}
	}

	public static void Init () {
		eofSy = new Symbol(Node.t, "EOF", 0);
		literals = new Hashtable();
	}
	
} // end Tab

} // end namespace