Commits

Haiko Schol committed f6965aa

initial commit

Comments (0)

Files changed (4)

+public class Band
+{
+		private class Slot
+		{
+				public char content;
+				public Slot prev;
+				public Slot next;
+
+				public Slot(Slot prev, Slot next)
+				{
+						content = '0';
+						this.prev = prev;
+						this.next = next;
+				}
+
+				public Slot(char content, Slot previous, Slot next)
+				{
+						this.content = content;
+						this.prev = prev;
+						this.next = next;
+				}
+		}
+
+		public static final int LEFT = 0;
+		public static final int RIGHT = 1;
+		public static final int HOLD = 2;
+
+		private Slot current;    // zeigt auf den aktuell zu lesenden bandeintrag
+		private Slot first;      // zeigt auf den ersten bandeintrag (den kopf der zeigerliste)
+
+		public Band()
+		{
+				first = new Slot('0', null, null);
+				current = first;
+		}
+
+		public char read()
+		{
+				return (current != null) ? current.content : '0';
+		}
+
+		public void write(char c)
+		{
+				if (current != null) 
+						current.content = c;
+		}
+
+		public void write(Character c)
+		{
+				if (current != null)
+						current.content = c.charValue();
+		}
+
+		public void left()
+		{
+				if (current.prev == null) {
+						Slot temp = new Slot('0', null, current);
+						current.prev = temp;
+				}
+				current = current.prev;
+		}
+
+		public void right()
+		{
+				if (current.next == null) {
+						Slot temp = new Slot('0', current, null);
+						current.next = temp;
+				}
+				current = current.next;
+		}
+
+		public String toString(int state)
+		{
+				Slot temp = first;
+				StringBuffer stribu = new StringBuffer();
+
+				while (temp.prev != null)
+						temp = temp.prev;
+
+				while (temp != null) {
+					if (temp == current)
+						stribu.append(" q" + state + " ");
+					stribu.append(temp.content);
+					temp = temp.next;
+				} 
+				return stribu.toString();
+		}
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+import java.io.BufferedReader;
+import java.io.FileReader;
+import java.io.File;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.util.Vector;
+import java.util.StringTokenizer;
+
+public class FileParser extends BufferedReader
+{
+	private Vector alphabet;
+	private Vector final_states;
+	private Band band;
+	private RuleSet delta;
+
+	public FileParser(String filename, Band band, RuleSet delta) throws FileNotFoundException
+	{
+		super(new FileReader(new File(filename)));
+		this.band = band;
+		this.delta = delta;
+		alphabet = new Vector();
+		final_states = new Vector();
+	}
+
+	private void parseAlphabet()
+	{
+		String input = null;
+		try {
+			input = readLine();
+		} catch (IOException ioex) {
+			System.err.println(ioex.getMessage());
+		}
+		String temp;
+		StringTokenizer strito = new StringTokenizer(input, ",", false);
+
+		while(strito.hasMoreTokens()) {
+			temp = strito.nextToken().trim();
+			alphabet.add(temp);
+		}
+	}
+
+	private void parseFinalStates()
+	{
+		String input = null;
+		try {
+			input = readLine();
+		} catch (IOException ioex) {
+			System.err.println(ioex.getMessage());
+		}
+		String temp;
+		StringTokenizer strito = new StringTokenizer(input, ",", false);
+
+		while(strito.hasMoreTokens()) {
+			temp = strito.nextToken().trim();
+			try {
+				final_states.add(new Integer(temp));
+			} catch (NumberFormatException nufoma) {
+				System.err.println(nufoma.getMessage());
+			}
+		}
+	}
+
+	public int parseDirection(String input)
+	{
+		if (input.startsWith("L"))
+			return Band.LEFT;
+		if (input.startsWith("R"))
+			return Band.RIGHT;
+		return Band.HOLD;
+	}
+
+	/* die methode liest die zustandsuebergangstabelle und zerhackt jede zeile in ihre spalten. 
+	 * jede spalte enhaelt das resultat der delta-funktion fuer die entsprechende eingabe (zustand,
+     * gelesenes zeichen)
+     */
+	public void parse()
+	{
+		String temp = null;
+		StringTokenizer strito;
+		int alphabet_index = 0;
+		int new_state = 0;
+		int state = 0;
+		char c;
+
+		parseAlphabet();
+		parseFinalStates();
+		delta.setFinalStates(final_states);
+		try {
+			temp = readLine();
+		} catch (IOException ioex) {
+			System.err.println(ioex.getMessage());
+		}
+		if (temp == null) {
+			System.err.println("premature end of file");
+			return;
+		}
+
+		while(temp != null) {            // zeilenweise die tabelle einlesen und in einzelne
+			if (temp.trim().compareTo("") == 0)
+				continue;
+			strito = new StringTokenizer(temp);        // zellen zerhacken
+			while(strito.hasMoreTokens()) {
+				StringTokenizer cellto = new StringTokenizer(strito.nextToken(), ",", false); 
+				try {                                                                         
+					new_state = Integer.parseInt(cellto.nextToken());          // regeln speichern
+				} catch (NumberFormatException nufoma) {
+					System.err.println(nufoma.getMessage());
+				}
+				delta.add(alphabet_index, ((String)alphabet.get(alphabet_index)).charAt(0), new_state, 
+						  cellto.nextToken().charAt(0), parseDirection(cellto.nextToken()));
+				alphabet_index++;
+			}
+			alphabet_index = 0;
+			delta.incState();
+			try {
+				temp = readLine();
+			} catch (Exception e) {
+				System.err.println(e.getMessage());
+			}
+		}
+		delta.resetState();
+	}
+}
+
+
+
+
+
+
+import java.io.FileNotFoundException;
+
+public class Interpreter
+{
+		public static void main(String args[])
+		{
+				RuleSet ruse = new RuleSet();
+				Band band = new Band();
+				FileParser fipa = null;
+				try {
+						fipa = new FileParser(args[0], band, ruse);
+				} catch (FileNotFoundException e) {
+						System.err.println(e.getMessage());
+				}
+				fipa.parse();
+				while(!ruse.isDone()) {
+						System.out.println(band.toString(ruse.getState()));
+						ruse.applyRule(band);
+				}
+				System.out.println(band.toString(ruse.getState()));
+		}
+}
+/* der speicher der delta-funktion und der zustaende (inkl. des aktuellen zustands).
+ * das objekt einer konkreten turing maschine hat einen verweis auf das band und
+ * kann so mittels read(), write(), left(), right() die delta funktion auf dem band
+ * realisieren.
+ * das objekt wird schrittweise von Interpreter.java gesteuert.  
+ */
+
+import java.util.Vector;
+import java.util.Hashtable;
+import java.util.Enumeration;
+
+public class RuleSet
+{
+	private class Result
+	{
+		public int state;
+		public Character c;
+		public int direction;
+
+		public Result(int state, Character c, int direction)
+		{
+			this.state = state;
+			this.c = c;
+			this.direction = direction;
+		}
+
+		public String toString()
+		{
+			return new String(state + "," + c + "," + direction);
+		}
+	}
+
+	private int current_state;           // der aktuelle zustand der turing maschine
+	private Vector final_states;         // finalzustaende der turingmaschine
+	private Vector rules;                // hier wird pro zustand eine hashtabelle gespeichert, in
+	// der reihenfolge des einlesens aus der datei.
+
+	public RuleSet()
+	{
+		current_state = 0;
+		final_states = new Vector();
+		rules = new Vector();
+	}
+
+	public void addFinal(int i)
+	{
+		final_states.add(new Integer(i));
+	}
+
+	public void addFinal(Integer i)
+	{
+		final_states.add(i);
+	}
+
+	public void setFinalStates(Vector final_states)
+	{
+		this.final_states = final_states;
+	}
+
+	public int getState()
+	{
+		return current_state;
+	}
+
+	public void incState()
+	{
+		current_state++;
+	}
+
+	public void resetState()
+	{
+		current_state = 0;
+	}
+
+	public boolean isFinal(int state)
+	{
+		return final_states.contains(new Integer(state));   // geht das? equals() 
+	}
+
+	public boolean isDone()
+	{
+		return isFinal(current_state);
+	}
+
+	public void add(int column, char c, int new_state, char new_c, int direction)
+	{
+		Hashtable temp;
+		if (column == 0) {
+			temp = new Hashtable();
+		} else {
+			temp = (Hashtable) rules.get(current_state);
+		}
+		Result res = new Result(new_state, new Character(new_c), direction);
+		temp.put(new Character(c), res);
+		if (column == 0)
+			rules.add(temp);
+	}
+
+	public void applyRule(Band b)
+	{
+		Hashtable hash = (Hashtable) rules.get(current_state);
+		Result res = (Result) hash.get(new Character(b.read()));
+		if (isDone()) {
+			return;
+		}
+		current_state = res.state;
+		b.write(res.c);
+		switch(res.direction) {
+		case Band.LEFT : b.left();
+			break;
+		case Band.RIGHT : b.right();
+			break;
+		}
+	}
+
+	public void gibAus()
+	{
+		Object obj[] = rules.toArray();
+		for (int i = 0; i < obj.length; i++) {
+			Hashtable temp = (Hashtable) obj[i];
+			Enumeration enum = temp.elements();
+			while (enum.hasMoreElements()) {
+				Result auchtemp = (Result) enum.nextElement();
+				System.out.print(auchtemp.toString() + '\t');
+			}
+			System.out.println();
+		}
+	}
+}
+
+
+