dfa.cs

c#源代码

/*-------------------------------------------------------------------------
DFA.cs -- Generation of the Scanner Automaton
Compiler Generator Coco/R,
Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz
extended by M. Loeberbauer & A. Woess, Univ. of Linz
with improvements by Pat Terry, Rhodes University

This program is free software; you can redistribute it and/or modify it 
under the terms of the GNU General Public License as published by the 
Free Software Foundation; either version 2, or (at your option) any 
later version.

This program is distributed in the hope that it will be useful, but 
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License 
for more details.

You should have received a copy of the GNU General Public License along 
with this program; if not, write to the Free Software Foundation, Inc., 
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

As an exception, it is allowed to write an extension of Coco/R that is
used as a plugin in non-free software.

If not otherwise stated, any source code generated by Coco/R (other than 
Coco/R itself) does not fall under the GNU General Public License.
-------------------------------------------------------------------------*/
using System;
using System.IO;
using System.Collections;
using System.Text;

namespace at.jku.ssw.Coco {

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

public class State {				// state of finite automaton
	public static int lastNr;	// highest state number
	public int nr;						// state number
	public Action firstAction;// to first action of this state
	public Symbol endOf;			// recognized token if state is final
	public bool ctx;					// true if state is reached via contextTrans
	public State next;
	
	public State() {
		nr = ++lastNr;
	}
	
	public 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;
	}
	
	public 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;
	}
	
	public Action TheAction(char ch) {
		BitArray s;
		for (Action a = firstAction; a != null; a = a.next)
			if (a.typ == Node.chr && ch == a.sym) return a;
			else if (a.typ == Node.clas) {
				s = CharClass.Set(a.sym);
				if (s[ch]) return a;
			}
		return null;
	}
	
	public 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
//-----------------------------------------------------------------------------

public class Action {			// action of finite automaton
	public int typ;					// type of action symbol: clas, chr
	public int sym;					// action symbol
	public int tc;					// transition code: normalTrans, contextTrans
	public Target target;		// states reached from this action
	public Action next;
	
	public Action(int typ, int sym, int tc) {
		this.typ = typ; this.sym = sym; this.tc = tc;
	}
	
	public void AddTarget(Target t) { // add t to the action.targets
		Target last = null;
		Target 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;
	}

	public void AddTargets(Action a) { // add copy of a.targets to action.targets
		for (Target p = a.target; p != null; p = p.next) {
			Target t = new Target(p.state);
			AddTarget(t);
		}
		if (a.tc == Node.contextTrans) tc = Node.contextTrans;
	}
	
	public BitArray Symbols() {
		BitArray s;
		if (typ == Node.clas)
			s = (BitArray) CharClass.Set(sym).Clone();
		else {
			s = new BitArray(CharClass.charSetSize); s[sym] = true;
		}
		return s;
	}
	
	public void ShiftWith(BitArray s) {
		if (Sets.Elements(s) == 1) {
			typ = Node.chr; sym = Sets.First(s);
		} else {
			CharClass c = CharClass.Find(s);
			if (c == null) c = new CharClass("#", s); // class with dummy name
			typ = Node.clas; sym = c.n;
		}
	}
	
	public void GetTargetStates(out BitArray targets, out Symbol endOf, out bool ctx) { 
		// compute the set of target states
		targets = new BitArray(DFA.maxStates); endOf = null;
		ctx = false;
		for (Target t = target; t != null; t = t.next) {
			int stateNr = t.state.nr;
			if (stateNr <= DFA.lastSimState) targets[stateNr] = true;
			else targets.Or(Melted.Set(stateNr));
			if (t.state.endOf != null)
				if (endOf == null || endOf == t.state.endOf)
					endOf = t.state.endOf;
				else {
					Console.WriteLine("Tokens {0} and {1} cannot be distinguished", endOf.name, t.state.endOf.name);
					Errors.count++;
				}
			if (t.state.ctx) {
				ctx = true;
				// The following check seems to be unnecessary. It reported an error
				// if a symbol + context was the prefix of another symbol, e.g.
				//   s1 = "a" "b" "c".
				//   s2 = "a" CONTEXT("b").
				// But this is ok.
				// if (t.state.endOf != null) {
				//   Console.WriteLine("Ambiguous context clause");
				//	 Errors.count++;
				// }
			}
		}
	}
	
}

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

public class Target {				// set of states that are reached by an action
	public State state;				// target state
	public Target next;
	
	public Target (State s) {
		state = s;
	}
}

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

public class Melted {					// info about melted states
	public static Melted first;	// head of melted state list
	public BitArray set;				// set of old states
	public State state;					// new state
	public Melted next;
	
	public Melted(BitArray set, State state) {
		this.set = set; this.state = state;
		this.next = first; first = this;
	}

	public static BitArray Set(int nr) {
		Melted m = first;
		while (m != null) {
			if (m.state.nr == nr) return m.set; else m = m.next;
		}
		throw new Exception("-- compiler error in Melted.Set");
	}
	
	public static Melted StateWithSet(BitArray s) {
		for (Melted m = first; m != null; m = m.next)
			if (Sets.Equals(s, m.set)) return m;
		return null;
	}
	
}

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

public class Comment {					// info about comment syntax
	public static Comment first;	// list of comments
	public string start;
	public string stop;
	public bool nested;
	public Comment next;
	
	static string Str(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) {
				BitArray set = CharClass.Set(p.val);
				if (Sets.Elements(set) != 1) Parser.SemErr("character set contains more than 1 character");
				s.Append((char)Sets.First(set));
			} 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 Comment(Node from, Node to, bool nested) {
		start = Str(from);
		stop = Str(to);
		this.nested = nested;
		this.next = first; first = this;
	}
	
}

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

public class DFA {
	public static int maxStates;
	public const int  EOF = -1;
	
	public static State firstState;
	public static State lastState;		// last allocated state
	public static int lastSimState;		// last non melted state
	public static FileStream fram;		// scanner frame input
	public static StreamWriter gen;		// generated scanner file
	public static Symbol curSy;				// current token to be recognized (in FindTrans)
	public static Node curGraph;			// start of graph for current token (in FindTrans)
	public static bool ignoreCase;    // true if input should be treated case-insensitively
	public static bool dirtyDFA;			// DFA may become nondeterministic in MatchLiteral
	public static bool hasCtxMoves;		// DFA has context transitions
		     static string srcName;     // name of the attributed grammar file
		     static string srcDir;      // directory of attributed grammar file

	//---------- Output primitives
	private static string Ch(char ch) {
		if (ch < ' ' || ch >= 127 || ch == '\'' || ch == '\\') return Convert.ToString((int)ch);
		else return String.Format("'{0}'", ch);
	}
	
	private static string ChCond(char ch) {
		return String.Format("ch == {0}", Ch(ch));
	}
	
	private static void PutRange(BitArray s) {
		int[] lo = new int[32];
		int[] hi = new int[32];
		// fill lo and hi
		int max = CharClass.charSetSize;
		int top = -1;
		int i = 0;
		while (i < max) {
			if (s[i]) {
				top++; lo[top] = i; i++;
				while (i < max && s[i]) i++;
				hi[top] = i-1;
			} else i++;
		}
		// print ranges
		if (top == 1 && lo[0] == 0 && hi[1] == max-1 && hi[0]+2 == lo[1]) {
			BitArray s1 = new BitArray(max); s1[hi[0]+1] = true;
			gen.Write("!"); PutRange(s1);
		} else {
			gen.Write("(");
			for (i = 0; i <= top; i++) {
				if (hi[i] == lo[i]) gen.Write("ch == {0}", Ch((char)lo[i]));
				else if (lo[i] == 0) gen.Write("ch <= {0}", Ch((char)hi[i]));
				else if (hi[i] == max-1) gen.Write("ch >= {0}", Ch((char)lo[i]));
				else gen.Write("ch >= {0} && ch <= {1}", Ch((char)lo[i]), Ch((char)hi[i]));
				if (i < top) gen.Write(" || ");
			}
			gen.Write(")");
		}
	}