dfa.java

cocorj09-一个Java语言分析器

			break;
		}
		case Tab.iter: {
			FindTrans(Math.abs(n.next), false, mark); FindTrans(n.p1, false, mark);
			break;
		}
		case Tab.alt: {
			FindTrans(n.p1, false, mark); FindTrans(n.p2, false, mark);
			break;
		}
	}
}

static void ConvertToStates(int p, int sp) {
	curGraph = p; curSy = sp;
	if (Tab.DelGraph(curGraph)) Parser.SemError(20);
	NumberNodes(curGraph, firstState);
	FindTrans(curGraph, true, new BitSet(512));
}

static int MatchedDFA(String s, int sp) {
		State state, to;
		Action a;
		int i, matchedSp, len = s.length() - 1;
		// s has quotes
		state = firstState;
		for (i=1; i<len; i++) { // try to match s against existing DFA
			a = state.TheAction(s.charAt(i));
			if (a==null) break;
			state = a.target.state;
		}
		for (;i<len; i++) { // make new DFA for s[i..len-1]
			to = NewState();
			NewTransition(state, to, Tab.chr, s.charAt(i), Tab.normTrans);
			state = to;
		}
		matchedSp = state.endOf;
		if (state.endOf==Tab.noSym) state.endOf = sp;
		return matchedSp;
	}

	private static void SplitActions(State state, Action a, Action b) {
		Action c; BitSet seta, setb, setc;
		seta = a.Symbols(); setb = b.Symbols();
		if (seta.equals(setb)) {
			a.AddTargets(b);
			state.DetachAction(b);
		} else if (Sets.Includes(seta, setb)) {
			setc = (BitSet) seta.clone(); Sets.Differ(setc, setb);
			b.AddTargets(a);
			a.ShiftWith(setc);
		} else if (Sets.Includes(setb, seta)) {
			setc = (BitSet) setb.clone(); Sets.Differ(setc, seta);
			a.AddTargets(b);
			b.ShiftWith(setc);
		} else {
			setc = (BitSet) seta.clone(); setc.and(setb);
			Sets.Differ(seta, setc);
			Sets.Differ(setb, setc);
			a.ShiftWith(seta);
			b.ShiftWith(setb);
			c = new Action(0, 0, 0);
			c.AddTargets(a);
			c.AddTargets(b);
			c.ShiftWith(setc);
			state.AddAction(c);
		}
	}

	private static boolean Overlap(Action a, Action b) {
		BitSet seta, setb;
		if (a.typ==Tab.chr)
			if (b.typ==Tab.chr) return a.sym==b.sym;
			else {setb = Tab.Class(b.sym); return setb.get(a.sym);}
		else {
			seta = Tab.Class(a.sym);
			if (b.typ==Tab.chr) return seta.get(b.sym);
			else {setb = Tab.Class(b.sym); return !Sets.Different(seta, setb);}
		}
	}

	private static boolean MakeUnique(State state) { // return true if actions were split
		boolean changed = false;
		for (Action a=state.firstAction; a!=null; a=a.next)
			for (Action b=a.next; b!=null; b=b.next)
				if (Overlap(a, b)) {SplitActions(state, a, b); changed = true;}
		return changed;
	}

	private static boolean MeltStates(State state) {
		boolean changed, correct = true;
		StateSet states;
		State s;
		Target targ;
		Melted melt;
		for (Action action=state.firstAction; action!=null; action=action.next) {
			if (action.target.next != null) {
				states = action.GetTargetStates();
				correct = correct && states.correct;
				melt = Melted.StateWithSet(states.set);
				if (melt==null) {
					s = NewState(); s.endOf = states.endOf; s.ctx = states.ctx;
					for (targ=action.target; targ!=null; targ=targ.next)
						s.MeltWith(targ.state);
					do {changed = MakeUnique(s);} while (changed);
					melt = new Melted(states.set, s);
				}
				action.target.next = null;
				action.target.state = melt.state;
			}
		}
		return correct;
	}

	private static void FindCtxStates() {
		for (State state=firstState; state!=null; state=state.next)
			for (Action a=state.firstAction; a!=null; a=a.next)
				if (a.tc==Tab.contextTrans) a.target.state.ctx = true;
	}

	static boolean MakeDeterministic() {
		State state;
		boolean changed, correct;
		lastSimState = lastState.nr;
		FindCtxStates();
		for (state=firstState; state!=null; state=state.next)
			do {changed = MakeUnique(state);} while (changed);
		correct = true;
		for (state=firstState; state!=null; state=state.next)
			correct = MeltStates(state) && correct;
		DeleteRedundantStates();
		CombineShifts();
		return correct;
	}

	static void PrintStates() {
		Action action; Target targ;
		BitSet set;
		boolean first;
		Trace.println("\n---------- states ----------");
		for (State state=firstState; state!=null; state=state.next) {
			first = true;
			if (state.endOf==Tab.noSym) Trace.print("     ");
			else Trace.print("E(" + Int(state.endOf, 2) + ")");
			Trace.print(Int(state.nr, 3) + ":");
			if (state.firstAction==null) Trace.println();
			for (action=state.firstAction; action!=null; action=action.next) {
				if (first) {Trace.print(" "); first = false;} else Trace.print("          ");
				if (action.typ==Tab.clas) Trace.print(Tab.ClassName(action.sym));
				else Trace.print(Ch((char)action.sym));
				for (targ=action.target; targ!=null; targ=targ.next)
					Trace.print(" " + targ.state.nr);
				if (action.tc==Tab.contextTrans) Trace.println(" context"); else Trace.println();
			}
		}
		Trace.println("\n---------- character classes ----------");
		for (int i=0; i<=Tab.maxC; i++) {
			set = Tab.Class(i);
			Trace.println(Tab.ClassName(i) + ": " + set.toString());
		}
	}

	private static void GenComBody(Comment com) {
		gen.println("\t\t\t\tfor(;;) {");
		gen.println("\t\t\t\t\tif (" + ChCond(com.stop.charAt(0)) + ") {");
		if (com.stop.length()==1) {
			gen.println("\t\t\t\t\t\tlevel--;");
			gen.println("\t\t\t\t\t\tif (level == 0) {NextCh(); return true;}");
			gen.println("\t\t\t\t\t\tNextCh();");
		} else {
			gen.println("\t\t\t\t\t\tNextCh();");
			gen.println("\t\t\t\t\t\tif (" + ChCond(com.stop.charAt(1)) + ") {");
			gen.println("\t\t\t\t\t\t\tlevel--;");
			gen.println("\t\t\t\t\t\t\tif (level == 0) {NextCh(); return true;}");
			gen.println("\t\t\t\t\t\t\tNextCh();");
			gen.println("\t\t\t\t\t\t}");
		}
		if (com.nested) {
			gen.println("\t\t\t\t\t} else if (" + ChCond(com.start.charAt(0)) + ") {");
			if (com.start.length()==1)
				gen.println("\t\t\t\t\t\tlevel++; NextCh();");
			else {
				gen.println("\t\t\t\t\t\tNextCh();");
				gen.println("\t\t\t\t\t\tif (" + ChCond(com.start.charAt(1)) + ") {");
				gen.println("\t\t\t\t\t\t\tlevel++; NextCh();");
				gen.println("\t\t\t\t\t\t}");
			}
		}
		gen.println("\t\t\t\t\t} else if (ch == EOF) return false;");
		gen.println("\t\t\t\t\telse NextCh();");
		gen.println("\t\t\t\t}");
	}

	private static void GenComment(Comment com) {
		gen.println("\t\tif (" + ChCond(com.start.charAt(0)) + ") {");
		if (com.start.length()==1) {
			gen.println("\t\t\tNextCh();");
			GenComBody(com);
		} else {
			gen.println("\t\t\tNextCh();");
			gen.println("\t\t\tif (" + ChCond(com.start.charAt(1)) + ") {");
			gen.println("\t\t\t\tNextCh();");
			GenComBody(com);
			gen.println("\t\t\t} else {");
			gen.println("\t\t\t\tif (ch == CR || ch == LF) {line--; lineStart = lineStart0;}");
			gen.println("\t\t\t\tpos = pos - 2; Buffer.Set(pos+1); NextCh();");
			gen.println("\t\t\t}");
		}
		gen.println("\t\t}");
	}

	private static void CopyFramePart(String stop) {
		int ch, i;
		int last = 0;
		int startCh = stop.charAt(0);
		int high = stop.length() - 1;
		try {
			ch = fram.read();
			while (ch!=EOF)
				if (ch==startCh) {
					i = 0;
					do {
						if (i==high) return; // stop[0..i] found
						ch = fram.read(); i++;
					} while (ch==stop.charAt(i));
					// stop[0..i-1] found; continue with last read character
					gen.print(stop.substring(0, i));
				} else if (ch==LF) { if (last!=CR) gen.println(); last = ch; ch = fram.read();
				} else if (ch==CR) { gen.println(); last = ch; ch = fram.read();
				} else {
					gen.print((char)ch); last = ch; ch = fram.read();
				}
		} catch (IOException e) {
			Scanner.err.Exception("-- error reading Scanner.frame");
		}
	}

	private static void PrintTermName(int n) {
		if (Tab.sy[n].symName == null) gen.print(n);
		else gen.print("SYM." + Tab.sy[n].symName);
	}

	private static void GenLiterals(boolean ignoreCase) {
		int i, j, k;
		char ch;
		Symbol sym;
		String[] key = new String[Tab.maxTerminals];
		int[] knr = new int[Tab.maxTerminals];
		// sort literal list (don't consider eofSy)
		k = 0;
		for (i=1; i<=Tab.maxT; i++) {
			sym = Tab.Sym(i);
			if (sym.struct==Tab.litToken) {
				for (j=k-1; j>=0 && sym.name.compareTo(key[j]) < 0; j--) {
					key[j+1] = key[j]; knr[j+1] = knr[j];
				}
				key[j+1] = sym.name; knr[j+1] = i; k++;
			}
		}
		// print switch statement
		i = 0;
		if (ignoreCase) gen.println("\t\tt.val = buf.toString().toUpperCase();");
		else gen.println("\t\tt.val = buf.toString();");
		gen.println("\t\tswitch (t.val.charAt(0)) {");
		while (i < k) {
			ch = key[i].charAt(1); // key[i, 0] is quote
			gen.println("\t\t\tcase " + Ch(ch) + ": {");
			j = i;
			do {
				if (i==j) gen.print("\t\t\t\tif ");
				else gen.print("\t\t\t\telse if ");
				gen.print("(t.val.equals(" + key[i] + ")) t.kind = ");
				PrintTermName(knr[i]);
				gen.println(";");
				i++;
			} while (i<k && key[i].charAt(1)==ch);
			gen.println("\t\t\t\tbreak;}");
		}
		gen.print("\t\t}");
	}

	private static void WriteState(State state) {
		Action action;
		Symbol sym;
		boolean ctxEnd;
		int endOf = state.endOf;
		if (endOf > Tab.maxT)
			endOf = Tab.maxT + Tab.maxSymbols - endOf; // pragmas have been moved
		gen.println("\t\t\t\tcase " + state.nr + ":");
		ctxEnd = state.ctx;
		for (action=state.firstAction; action!=null; action=action.next) {
			if (action==state.firstAction) gen.print("\t\t\t\t\tif (");
			else gen.print("\t\t\t\t\telse if (");
			if (action.typ==Tab.chr) gen.print(ChCond((char)action.sym));
			else {PutRange(Tab.Class(action.sym));}
			gen.print(") {");
			if (action.target.state != state)
				gen.print("state = " + action.target.state.nr + "; ");
			if (action.tc == Tab.contextTrans) {
				gen.print("apx++; "); ctxEnd = false;
			} else if (state.ctx)
				gen.print("apx = 0; ");
			gen.println("break;}");
		}
		if (state.firstAction != null) gen.print("\t\t\t\t\telse ");
		if (endOf==Tab.noSym)
			gen.println("{t.kind = noSym; break loop;}");
		else { // final state
			if (state.firstAction==null)
				gen.print("\t\t\t\t\t{");
			else
				gen.print("{");
			sym = Tab.Sym(endOf);
			if (ctxEnd) { // final context state: cut appendix
				gen.println("pos = pos - apx - 1;");
				gen.println("\t\t\t\t\tbuf.setLength(buf.length() - apx);");
				gen.println("\t\t\t\t\tline = t.line; Buffer.Set(pos+1); NextCh();");
				gen.print("\t\t\t\t\t");
			}
			gen.print("t.kind = ");
			PrintTermName(endOf);
			gen.print("; ");
			if (sym.struct==Tab.classLitToken)
				gen.print("CheckLiteral(buf); ");
			gen.println("break loop;}");
		}
	}

	private static void FillStartTab(int[] startTab) {
		int targetState, max, i;
		BitSet s;
		startTab[0] = State.lastNr + 1; // eof
		for (Action action= firstState.firstAction; action!=null; action=action.next) {
			targetState = action.target.state.nr;
			if (action.typ==Tab.chr) startTab[action.sym] = targetState;
			else {
				s = Tab.Class(action.sym); max = s.size();
				for (i=0; i<=max; i++)
					if (s.get(i)) startTab[i] = targetState;
			}
		}
	}

	static void WriteScanner(boolean ignoreCase) {
		int i, j, max;
		int[] startTab = new int[128];
		Comment com;
		Symbol root = Tab.Sym(Tab.gramSy);

// Portability - Use the following for Java 1.0
//		try {fram = new BufferedInputStream(new FileInputStream("Scanner.frame"));}
// Portability - Use the following for Java 1.1
//		try {fram = new BufferedReader(new FileReader("Scanner.frame"));}

		try {fram = new BufferedReader(new FileReader("Scanner.frame"));}

		catch (IOException e) {
			Scanner.err.Exception("-- cannot open Scanner.frame. " +
			"Must be in application directory.");
		}
		try {

// Portability - Use the following for Java 1.0
//			gen = new PrintStream(new BufferedOutputStream(new FileOutputStream(srcDir + "Scanner.java")));
// Portability - Use the following for Java 1.1
//			gen = new PrintWriter(new BufferedWriter(new FileWriter(srcDir + "Scanner.java")));

			gen = new PrintWriter(new BufferedWriter(new FileWriter(srcDir + "Scanner.java")));

		} catch (IOException e) {
			Scanner.err.Exception("-- cannot generate scanner file");
		}
		FillStartTab(startTab);
		gen.println("package " + root.name + ";");
		CopyFramePart("-->declarations");
		gen.println("\tprivate static final int noSym = " + Tab.maxT + ";");
		gen.println("\tprivate static final int[] start = {");
		for (i=0; i<8; i++) {
			gen.print("\t");
			for (j=0; j<16; j++)
				gen.print(Int(startTab[16*i+j], 3) + ",");
			gen.println();
		}
		gen.println("\t  0};");
		CopyFramePart("-->initialization");
		gen.print("\t\t");
		max = Tab.ignored.size(); j = 0;
		for (i=0; i<=max; i++)
			if (Tab.ignored.get(i)) {
				gen.print("ignore.set(" + i + "); ");
				if (++j % 4 == 0) {gen.println(); gen.print("\t\t");}
			}
		CopyFramePart("-->scan0");
		if (ignoreCase) gen.print("\t\tch = Character.toUpperCase(strCh);");
		else gen.print("\t\tch = strCh;");
		CopyFramePart("-->comment");
		for (com=Comment.first; com!=null; com=com.next) GenComment(com);
		CopyFramePart("-->literals"); GenLiterals(ignoreCase);
		CopyFramePart("-->scan1");
		if (Comment.first!=null) {
			gen.print("\t\tif ((");
			for (com=Comment.first; com!=null; com=com.next) {
				gen.print(ChCond(com.start.charAt(0)));
				if (com.next != null) gen.print(" || ");
			}
			gen.print(") && Comment()) return Scan();");
		}
		CopyFramePart("-->scan2");
		for (State state=firstState.next; state!=null; state=state.next)
			WriteState(state);
		gen.println("\t\t\t\tcase "+(State.lastNr+1)+":");
		gen.print("\t\t\t\t\t{t.kind = ");
		PrintTermName(0); gen.print("; break loop;}");
		CopyFramePart("-->scan3");
		if (ignoreCase) gen.print("\t\tt.val = t.str.toUpperCase();");
		else gen.print("\t\tt.val = t.str;");
		CopyFramePart("$$$");
		gen.flush();
	}

	static void Init(String dir) {
		srcDir = dir;
		firstState = null; lastState = null; State.lastNr = -1;
		firstState = NewState();
		Melted.first = null; Comment.first = null;
	}

}