tab.cs

来自「全功能c#编译器」· CS 代码 · 共 1,069 行 · 第 1/3 页

			&& AllNtToTerm();
    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 = Expected(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 = Expected(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;
		}
	}

	static void RSlvError(string msg) {
		Console.WriteLine(msg);
	}


	static void CheckResolver(Node p) {
		while (p != null) {
			// check subnodes of current node p
			if ((p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt) &&
			    !p.sub.up)
				if (p.sub.typ == Node.rslv) CheckResolver(p.sub.next);
				else CheckResolver(p.sub);
			
			// check current node p
			switch (p.typ) {
				case Node.alt:
					BitArray uncovered = new BitArray(Symbol.terminals.Count);  // first symbols of alternatives without a resolver (not "covered" by a resolver)
					ArrayList coveredList = new ArrayList();  // list of follow symbols of each resolver (these are "covered" by the resolver)
					ArrayList rslvList = new ArrayList();

					// build set of uncovered first symbols & check for misplaced resolvers 
					// (= not at the first n-1 of n conflicting alternatives)
					Node q = p;
					while (q != null) {
						BitArray curCovered;
						if (q.sub.typ == Node.rslv) {
						  // get followers of resolver (these are "covered" by it)
							if (q.sub.next == null) curCovered = curSy.follow;
							else curCovered = First0(q.sub.next, new BitArray(Node.nodes.Count));
							coveredList.Add(curCovered);
							rslvList.Add(q.sub);
							// resolver must "cover" all but the last occurrence of a conflicting symbol
							if (Sets.Intersect(uncovered, curCovered))
								RSlvError("Misplaced resolver at line " + q.sub.line + " will never be evaluated. " +
								          "Place resolver at previous conflicting alternative.");
						} else uncovered.Or(First0(q.sub, new BitArray(Node.nodes.Count)));
						q = q.down;
					}

					// check for obsolete resolvers 
					// (= alternatives starting with resolvers, when there is no conflict)
					BitArray[] covered = (BitArray[]) coveredList.ToArray(typeof(BitArray));
					Node[] rslvs = (Node[]) rslvList.ToArray(typeof(Node));
					for (int i = 0; i < rslvs.Length; ++i) {
						if (!Sets.Intersect(uncovered, covered[i])) 
							RSlvError("Obsolete resolver at line " + rslvs[i].line + ". " +
							          "Neither of the start symbols of the alternative occurs without a resolver.");
						/*
						if (!Sets.Includes(uncovered, covered[i]))
							RSlvError("At least one of the symbols after the resolver at line " + rslvs[i].line + 
							          " does not appear without a resolver. Remove the last resolver covering this symbol.");
						*/
						/*
						if (Sets.Equals(, covered[i]))
							RSlvError("Resolver at line " + rslvArr[i].line + " covers more symbols than necessary.\n" +
							          "Place resolvers only in front of conflicting symbols.");
						*/
					}
					break;
				case Node.iter: case Node.opt:
					if (p.sub.typ == Node.rslv) {
						BitArray fs = First0(p.sub.next, new BitArray(Node.nodes.Count));
						BitArray fsNext;
						if (p.next == null) fsNext = curSy.follow;
						else fsNext = First0(p.next, new BitArray(Node.nodes.Count));
						if (!Sets.Intersect(fs, fsNext)) 
							RSlvError("Obsolete resolver expression (IF ...) at line " + p.sub.line);
					}
					break;
				case Node.rslv:
					RSlvError("Unexpected Resolver in line " + p.line + ". Will cause parsing error.");
					break;
			}
			if (p.up) break; 
			p = p.next;
		}
	}

	public static void CheckLL1() {
		foreach (Symbol sym in Symbol.nonterminals) {
			curSy = sym;
			CheckAlts(curSy.graph);
			CheckResolver(curSy.graph);
		}
	}
	
	//------------- 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 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}", sym.line);
	}

	public static void PrintSymbolTable() {
		Trace.WriteLine("Symbol Table:");
		Trace.WriteLine("------------"); Trace.WriteLine();
		Trace.WriteLine(" nr name          typ  hasAt graph  del   line");
		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();
	}
	
	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);
	}
	
} // end Tab

} // end namespace