/* AW: this replaces the method int Alternatives (Node p) */
	static bool UseSwitch (Node p) {
		if (p.typ != Node.alt) return false;
		int nAlts = 0;
		while (p != null) {
		  ++nAlts;
		  // must not optimize with switch-statement, if alt uses a resolver expression
		  if (p.sub.typ == Node.rslv) return false;  
		  p = p.down;
		}
		return nAlts > 5;
	}

	// use a switch if more than 5 alternatives and none starts with a resolver
	bool UseSwitch (Node p) {
		BitArray s1, s2;
		if (p.typ != Node.alt) return false;
		int nAlts = 0;
		s1 = new BitArray(tab.terminals.Count);
		while (p != null) {
			s2 = tab.Expected0(p.sub, curSy);
			// must not optimize with switch statement, if there are ll1 warnings
			if (Overlaps(s1, s2)) { return false; }
			s1.Or(s2);
			++nAlts;
			// must not optimize with switch-statement, if alt uses a resolver expression
			if (p.sub.typ == Node.rslv) return false;
			p = p.down;
		}
		return nAlts > 5;
	}

 void GenCode(Node p, int indent, BitArray isChecked)
 {
     Node p2;
     BitArray s1, s2;
     while (p != null) {
     switch (p.typ) {
         case Node.nt: {
             Indent(indent);
             gen.Write(p.sym.name + "(");
             CopySourcePart(p.pos, 0);
             gen.WriteLine(");");
             break;
         }
         case Node.t: {
             Indent(indent);
             // assert: if isChecked[p.sym.n] is true, then isChecked contains only p.sym.n
             if (isChecked[p.sym.n]) gen.WriteLine("Get();");
             else gen.WriteLine("Expect({0});", p.sym.n);
             break;
         }
         case Node.wt: {
             Indent(indent);
             s1 = tab.Expected(p.next, curSy);
             s1.Or(tab.allSyncSets);
             gen.WriteLine("ExpectWeak({0}, {1});", p.sym.n, NewCondSet(s1));
             break;
         }
         case Node.any: {
             Indent(indent);
             int acc = Sets.Elements(p.set);
             if (tab.terminals.Count == (acc + 1) || (acc > 0 && Sets.Equals(p.set, isChecked))) {
                 // either this ANY accepts any terminal (the + 1 = end of file), or exactly what's allowed here
                 gen.WriteLine("Get();");
             } else {
                 GenErrorMsg(altErr, curSy);
                 if (acc > 0) {
                     gen.Write("if ("); GenCond(p.set, p); gen.WriteLine(") Get(); else SynErr({0});", errorNr);
                 } else gen.WriteLine("SynErr({0}); // ANY node that matches no symbol", errorNr);
             }
             break;
         }
         case Node.eps: break; // nothing
         case Node.rslv: break; // nothing
         case Node.sem: {
             CopySourcePart(p.pos, indent);
             break;
         }
         case Node.sync: {
             Indent(indent);
             GenErrorMsg(syncErr, curSy);
             s1 = (BitArray)p.set.Clone();
             gen.Write("while (!("); GenCond(s1, p); gen.Write(")) {");
             gen.Write("SynErr({0}); Get();", errorNr); gen.WriteLine("}");
             break;
         }
         case Node.alt: {
             s1 = tab.First(p);
             bool equal = Sets.Equals(s1, isChecked);
             bool useSwitch = UseSwitch(p);
             if (useSwitch) { Indent(indent); gen.WriteLine("switch (la.kind) {"); }
             p2 = p;
             while (p2 != null) {
                 s1 = tab.Expected(p2.sub, curSy);
                 Indent(indent);
                 if (useSwitch) {
                     PutCaseLabels(s1); gen.WriteLine("{");
                 } else if (p2 == p) {
                     gen.Write("if ("); GenCond(s1, p2.sub); gen.WriteLine(") {");
                 } else if (p2.down == null && equal) { gen.WriteLine("} else {");
                 } else {
                     gen.Write("} else if (");  GenCond(s1, p2.sub); gen.WriteLine(") {");
                 }
                 GenCode(p2.sub, indent + 1, s1);
                 if (useSwitch) {
                     Indent(indent); gen.WriteLine("\tbreak;");
                     Indent(indent); gen.WriteLine("}");
                 }
                 p2 = p2.down;
             }
             Indent(indent);
             if (equal) {
                 gen.WriteLine("}");
             } else {
                 GenErrorMsg(altErr, curSy);
                 if (useSwitch) {
                     gen.WriteLine("default: SynErr({0}); break;", errorNr);
                     Indent(indent); gen.WriteLine("}");
                 } else {
                     gen.Write("} "); gen.WriteLine("else SynErr({0});", errorNr);
                 }
             }
             break;
         }
         case Node.iter: {
             Indent(indent);
             p2 = p.sub;
             gen.Write("while (");
             if (p2.typ == Node.wt) {
                 s1 = tab.Expected(p2.next, curSy);
                 s2 = tab.Expected(p.next, curSy);
//.........这里部分代码省略.........

 State TheState(Node p)
 {
     State state;
     if (p == null) {state = NewState(); state.endOf = curSy; return state;}
     else return p.state;
 }

 // Assigns a state n.state to every node n. There will be a transition from
 // n.state to n.next.state triggered by n.val. All nodes in an alternative
 // chain are represented by the same state.
 // Numbering scheme:
 //  - any node after a chr, clas, opt, or alt, must get a new number
 //  - if a nested structure starts with an iteration the iter node must get a new number
 //  - if an iteration follows an iteration, it must get a new number
 void NumberNodes(Node p, State state, bool renumIter)
 {
     if (p == null) return;
     if (p.state != null) return; // already visited;
     if (state == null || (p.typ == Node.iter && renumIter)) state = NewState();
     p.state = state;
     if (Tab.DelGraph(p)) state.endOf = curSy;
     switch (p.typ) {
     case Node.clas: case Node.chr: {
         NumberNodes(p.next, null, false);
         break;
     }
     case Node.opt: {
         NumberNodes(p.next, null, false);
         NumberNodes(p.sub, state, true);
         break;
     }
     case Node.iter: {
         NumberNodes(p.next, state, true);
         NumberNodes(p.sub, state, true);
         break;
     }
     case Node.alt: {
         NumberNodes(p.next, null, false);
         NumberNodes(p.sub, state, true);
         NumberNodes(p.down, state, renumIter);
         break;
     }
     }
 }

 string CommentStr(Node p)
 {
     StringBuilder s = new StringBuilder();
     while (p != null) {
     if (p.typ == Node.chr) {
         s.Append((char)p.val);
     } else if (p.typ == Node.clas) {
         CharSet set = tab.CharClassSet(p.val);
         if (set.Elements() != 1) parser.SemErr("character set contains more than 1 character");
         s.Append((char)set.First());
     } else parser.SemErr("comment delimiters may not be structured");
     p = p.next;
     }
     if (s.Length == 0 || s.Length > 2) {
     parser.SemErr("comment delimiters must be 1 or 2 characters long");
     s = new StringBuilder("?");
     }
     return s.ToString();
 }

 public void ConvertToStates(Node p, Symbol sym)
 {
     curSy = sym;
     if (Tab.DelGraph(p)) {
     parser.SemErr("token might be empty");
     return;
     }
     NumberNodes(p, firstState, true);
     FindTrans(p, true, new BitArray(tab.nodes.Count));
     if (p.typ == Node.iter) {
     Step(firstState, p, new BitArray(tab.nodes.Count));
     }
 }

	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 static bool DelNode(Node p) {
		if (p.typ == Node.nt) return p.sym.deletable;
		else if (p.typ == Node.alt) return DelSubGraph(p.sub) || p.down != null && DelSubGraph(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;
	}

	public static bool DelSubGraph(Node p) {
		return p == null || DelNode(p) && (p.up || DelSubGraph(p.next));
	}

	//------------ graph deletability check -----------------

	public static bool DelGraph(Node p) {
		return p == null || DelNode(p) && DelGraph(p.next);
	}

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

	public void DeleteNodes() {
		nodes = new ArrayList();
		dummyNode = NewNode(Node.eps, null, 0);
	}

	public Node NewNode(int typ, Node sub) {
		Node node = NewNode(typ, null, 0);
		node.sub = sub;
		return node;
	}

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

	//----------------- graph printing ----------------------
	
	string Ptr(Node p, bool up) {
		string ptr = (p == null) ? "0" : p.n.ToString();
		return (up) ? ("-" + ptr) : ptr;
	}

	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)) LL1Error(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) LL1Error(3, null);
				// e.g. {ANY} ANY or [ANY] ANY or ( ANY | ANY )
			}
			if (p.up) break;
			p = p.next;
		}
	}

	//---------------------------------------------------------------------
	//  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 void NewComment(Node from, Node to, bool nested)
 {
     Comment c = new Comment(CommentStr(from), CommentStr(to), nested);
     c.next = firstComment; firstComment = c;
 }