dfa.java

cocorj09-一个Java语言分析器

package Coco;

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

class StateSet {       // set of target states returned by GetTargetStates
	BitSet set;           // all target states of an action
	int endOf;            // token that is recognized after this action
	boolean ctx;          // true if target states are reached via context transition
	boolean correct;      // true if no error occured in GetTargetStates
}

//-----------------------------------------------------------------------------
//  State
//-----------------------------------------------------------------------------

class State {          // state of finite automaton
	static int lastNr;    // highest state number
	int nr;               // state number
	Action firstAction;   // to first action of this state
	int endOf;            // nr. of recognized token if state is final
	boolean ctx;          // true if state is reached via contextTrans
	State next;

	State() {
		nr = ++lastNr; endOf = Tab.noSym;
	}

	void AddAction(Action act) {
		Action lasta = null, a = firstAction;
		while (a != null && act.typ >= a.typ) {lasta = a; a = a.next;}
		// collecting classes at the beginning gives better performance
		act.next = a;
		if (a==firstAction) firstAction = act; else lasta.next = act;
	}

	void DetachAction(Action act) {
		Action lasta = null, a = firstAction;
		while (a != null && a != act) {lasta = a; a = a.next;}
		if (a != null)
			if (a==firstAction) firstAction = a.next; else lasta.next = a.next;
	}

	Action TheAction(char ch) {
		for (Action a=firstAction; a!=null; a=a.next)
			if (a.typ==Tab.chr && ch==a.sym) return a;
			else if (a.typ==Tab.clas && Tab.Class(a.sym).get(ch)) return a;
		return null;
	}

	void MeltWith(State s) { // copy actions of s to state
		Action a;
		for (Action action=s.firstAction; action!=null; action=action.next) {
			a = new Action(action.typ, action.sym, action.tc);
			a.AddTargets(action);
			AddAction(a);
		}
	}

}

//-----------------------------------------------------------------------------
//  Action
//-----------------------------------------------------------------------------

class Action {         // action of finite automaton
	int typ;              // type of action symbol: chr, clas
	int sym;              // action symbol
	int tc;               // transition code: normTrans, contextTrans
	Target target;        // states reached from this action
	Action next;

	Action(int typ, int sym, int tc) {
		this.typ = typ; this.sym = sym; this.tc = tc;
	}

	void AddTarget(Target t) {
		Target p, last = null;
		p = target;
		while (p != null && t.state.nr >= p.state.nr) {
			if (t.state==p.state) return;
			last = p; p = p.next;
		}
		t.next = p;
		if (p==target) target = t; else last.next = t;
	}

	void AddTargets(Action a) { // add copy of a.targets to action.targets
		Target p, t;
		for (p=a.target; p!=null; p=p.next) {
			t = new Target(p.state);
			AddTarget(t);
		}
		if (a.tc==Tab.contextTrans) tc = Tab.contextTrans;
	}

	BitSet Symbols() {
		BitSet s;
		if (typ==Tab.clas) s = (BitSet) Tab.Class(sym).clone();
		else {s = new BitSet(); s.set(sym);}
		return s;
	}

	void ShiftWith(BitSet s) {
		int i;
		if (Sets.Size(s)==1) {
			typ = Tab.chr; sym = Sets.First(s);
		} else {
			i = Tab.ClassWithSet(s);
			if (i < 0) i = Tab.NewClass("#", s); // class with dummy name
			typ = Tab.clas; sym = i;
		}
	}

	StateSet GetTargetStates() { // compute the set of target states
		int stateNr;
		StateSet states = new StateSet();
		states.set = new BitSet(); states.endOf = Tab.noSym; states.ctx = false;
		states.correct = true;
		for (Target t=target; t!=null; t=t.next) {
			stateNr = t.state.nr;
			if (stateNr <= DFA.lastSimState) states.set.set(stateNr);
			else states.set.or(Melted.Set(stateNr));
			if (t.state.endOf!=Tab.noSym)
				if (states.endOf==Tab.noSym || states.endOf==t.state.endOf)
					states.endOf = t.state.endOf;
				else {
					System.out.println("Tokens " + states.endOf + " and " + t.state.endOf
						+ " cannot be distinguished");
					states.correct = false;
				}
			if (t.state.ctx) {
				states.ctx = true;
				if (t.state.endOf!=Tab.noSym) {
					System.out.println("Ambiguous context clause");
					states.correct = false;
				}
			}
		}
		return states;
	}
}

//-----------------------------------------------------------------------------
//  Target
//-----------------------------------------------------------------------------

class Target {         // set of states that are reached by an action
	State state;          // target state
	Target next;

	Target (State s) {
		state = s;
	}
}

//-----------------------------------------------------------------------------
//  Melted
//-----------------------------------------------------------------------------

class Melted {         // info about melted states
	static Melted first;  // head of melted state list
	BitSet set;           // set of old states
	State state;          // new state
	Melted next;

	Melted(BitSet set, State state) {
		this.set = set; this.state = state;
		this.next = first; first = this;
	}

	static BitSet Set(int nr) {
		Melted m;
		for (m=first; m!=null && m.state.nr!=nr; m=m.next) ;
		return m.set;
	}

	static Melted StateWithSet(BitSet s) {
		for (Melted m=first; m!=null; m=m.next)
			if (s.equals(m.set)) return m;
		return null;
	}
}

//-----------------------------------------------------------------------------
//  Comment
//-----------------------------------------------------------------------------

class Comment {        // info about comment syntax
	static Comment first; // list of comments
	String start;
	String stop;
	boolean nested;
	Comment next;

	private static String Str(int p) {
		StringBuffer s = new StringBuffer();
		GraphNode n;
		BitSet set;
		while (p != 0) {
			n = Tab.Node(p);
			if (n.typ==Tab.chr) {
				s.append((char)n.p1);
			} else if (n.typ==Tab.clas) {
				set = Tab.Class(n.p1);
				if (Sets.Size(set) != 1) Parser.SemError(26);
				s.append((char)Sets.First(set));
			} else Parser.SemError(22);
			p = n.next;
		}
		if (s.length() == 0) {Parser.SemError(25); s.append('?');}
		else if (s.length() > 2) Parser.SemError(25);
		return s.toString();
	}

	Comment(int from, int to, boolean nested) {
		start = Str(from);
		stop = Str(to);
		this.nested = nested;
		this.next = first; first = this;
	}
}

//-----------------------------------------------------------------------------
//  DFA
//-----------------------------------------------------------------------------

class DFA {
	static final int maxStates = 300;
	static final char EOF = '\uffff';
	static final char CR  = '\r';
	static final char LF  = '\n';

	static State firstState;
	static State lastState;  // last allocated state
	static int lastSimState; // last non melted state
	static String srcDir;    // directory of attribute grammar file
	static int curSy;        // current token to be recognized (in FindTrans)
	static int curGraph;     // start of graph for current token (in FindTrans)

// Portability - Use the following for Java 1.0
//	static InputStream fram; // scanner frame input    Java 1.0
//	static PrintStream gen;  // generated scanner file Java 1.0
// Portability - Use the following for Java 1.1
//	static Reader fram;      // scanner frame input    Java 1.1
//	static PrintWriter gen;  // generated scanner file Java 1.1

	static Reader fram;      // scanner frame input    Java 1.1
	static PrintWriter gen;  // generated scanner file Java 1.1

	private static String Int(int n, int len) {
		String s = String.valueOf(n);
		int i = s.length(); if (len < i) len = i;
		int j = 0, d = len - s.length();
		char[] a = new char[len];
		for (i=0; i<d; i++) a[i] = ' ';
		for (j=0; i<len; i++) {a[i] = s.charAt(j); j++;}
		return new String(a, 0, len);
	}

	private static String Ch(char ch) {
		if (ch<' ' || ch>=127 || ch=='\'' || ch=='\\') return String.valueOf((int)ch);
		else return "'" + ch + "'";
	}

	private static String ChCond(char ch) {
		return "ch == " + Ch(ch);
	}

	private static void PutRange(BitSet s) {
		int[] lo = new int[32];
		int[] hi = new int[32];
		BitSet s1;
		int i, top;
		// fill lo and hi
		top = -1; i = 0;
		while (i < 128) {
			if (s.get(i)) {
				top++; lo[top] = i; i++;
				while (i < 128 && s.get(i)) i++;
				hi[top] = i-1;
			} else i++;
		}
		// print ranges
		if (top==1 && lo[0]==0 && hi[1]==127 && hi[0]+2==lo[1]) {
			s1 = new BitSet(); s1.set(hi[0]+1);
			gen.print("!("); PutRange(s1); gen.print(")");
		} else {
			for (i=0; i<=top; i++) {
				if (hi[i]==lo[i]) gen.print("ch == " + Ch((char)lo[i]));
				else if (lo[i]==0) gen.print("ch <= " + Ch((char)hi[i]));
				else if (hi[i]==127) gen.print("ch >= " + Ch((char)lo[i]));
				else gen.print("ch >= " + Ch((char)lo[i]) + " && ch <= " + Ch((char)hi[i]));
				if (i < top) {gen.println(); gen.print("\t\t\t\t\t  || ");}
			}
		}
	}

	private static State NewState() {
		State s = new State();
		if (firstState==null) firstState = s; else lastState.next = s;
		lastState = s;
		return s;
	}

	private static void NewTransition(State from, State to, int typ, int sym, int tc) {
		Action a;
		Target t;
		if (to==firstState) Parser.SemError(21);
		t = new Target(to);
		a = new Action(typ, sym, tc); a.target = t;
		from.AddAction(a);
	}

	private static void CombineShifts() {
		State state;
		Action a, b, c;
		BitSet seta, setb;
		for (state=firstState; state!=null; state=state.next) {
			for (a=state.firstAction; a!=null; a=a.next) {
				b = a.next;
				while (b != null)
					if (a.target.state==b.target.state && a.tc==b.tc) {
						seta = a.Symbols(); setb = b.Symbols();
						seta.or(setb);
						a.ShiftWith(seta);
						c = b; b = b.next; state.DetachAction(c);
					} else b = b.next;
			}
		}
	}

	private static void FindUsedStates(State state, BitSet used) {
		if (used.get(state.nr)) return;
		used.set(state.nr);
		for (Action a=state.firstAction; a!=null; a=a.next)
			FindUsedStates(a.target.state, used);
	}

	private static void DeleteRedundantStates() {
		State[] newState = new State[maxStates];
		BitSet used = new BitSet();
		FindUsedStates(firstState, used);
		// combine equal final states
		for (State s1=firstState.next; s1!=null; s1=s1.next) // firstState cannot be final
			if (used.get(s1.nr) && s1.endOf!=Tab.noSym && s1.firstAction==null && !s1.ctx)
				for (State s2=s1.next; s2!=null; s2=s2.next)
					if (used.get(s2.nr) && s1.endOf==s2.endOf && s2.firstAction==null & !s2.ctx) {
						used.clear(s2.nr); newState[s2.nr] = s1;
					}
		for (State state=firstState; state!=null; state=state.next)
			if (used.get(state.nr))
				for (Action a=state.firstAction; a!=null; a=a.next)
					if (!used.get(a.target.state.nr))
						a.target.state = newState[a.target.state.nr];
		// delete unused states
		lastState = firstState; State.lastNr = 0; // firstState has number 0
		for (State state=firstState.next; state!=null; state=state.next)
			if (used.get(state.nr)) {state.nr = ++State.lastNr; lastState = state;}
			else lastState.next = state.next;
	}

	private static State TheState(int p) {
		State state;
		if (p==0) {state = NewState(); state.endOf = curSy; return state;}
		else return Tab.Node(p).state;
	}

	private static void Step(State from, int p) {
		if (p==0) return;
		GraphNode n = Tab.Node(p);
		switch (n.typ) {
			case Tab.clas: case Tab.chr: {
				NewTransition(from, TheState(Math.abs(n.next)), n.typ, n.p1, n.p2);
				break;
			}
			case Tab.alt: {
				Step(from, n.p1); Step(from, n.p2);
				break;
			}
			case Tab.iter: case Tab.opt: {
				Step(from, Math.abs(n.next)); Step(from, n.p1);
				break;
			}
		}
	}

private static void NumberNodes(int p, State 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.sym. All nodes in an alternative
		 chain are represented by the same state.
	*/
	if (p==0) return;
	GraphNode n = Tab.Node(p);
	if (n.state != null) return; // already visited;
	if (state==null) state = NewState();
	n.state = state;
	if (Tab.DelGraph(p)) state.endOf = curSy;
	switch (n.typ) {
		case Tab.clas: case Tab.chr: {
			NumberNodes(Math.abs(n.next), null);
			break;
		}
		case Tab.opt: {
			NumberNodes(Math.abs(n.next), null); NumberNodes(n.p1, state);
			break;
		}
		case Tab.iter: {
			NumberNodes(Math.abs(n.next), state); NumberNodes(n.p1, state);
			break;
		}
		case Tab.alt: {
			NumberNodes(n.p1, state); NumberNodes(n.p2, state);
			break;
		}
	}
}

private static void FindTrans (int p, boolean start, BitSet mark) {
	if (p==0 || mark.get(p)) return;
	mark.set(p);
	GraphNode n = Tab.Node(p);
	if (start) Step(n.state, p); // start of group of equally numbered nodes
	switch (n.typ) {
		case Tab.clas: case Tab.chr: {
			FindTrans(Math.abs(n.next), true, mark);
			break;
		}
		case Tab.opt: {
			FindTrans(Math.abs(n.next), true, mark); FindTrans(n.p1, false, mark);