First commit

5 files changed, 199 insertions, 0 deletions

diff --git a/README b/README
new file mode 100644
index 0000000..6ec4d1f
--- /dev/null
+++ b/README
@@ -0,0 +1,20 @@
+If an emulation of a machine is a virtual machine, then this is VFSM: the Virtual Finite State Machine.
+
+Usage is: ruby vfsm.rb <machine description file> <input>
+
+A Machine description must have:
+ * A Nodes: line, followed by space separated node ids
+ * A Start: line, followed by the starting node id
+ * An Accept: line, followed by space separated node ids which may accept
+ * An Edges: line, followed by edge definition lines and an End: line
+
+There may be any number of Comment: lines which are unsurprisingly ignored.
+
+An edge definition line must have:
+ * The source node
+ * The input to accept
+ * The destination node
+
+The input is a string of space separated input tokens.
+
+See the examples.
diff --git a/examples/abc.vfsm b/examples/abc.vfsm
new file mode 100644
index 0000000..691d5f6
--- /dev/null
+++ b/examples/abc.vfsm
@@ -0,0 +1,19 @@
+Comment: This machine accepts any number of "a b c"
+Comment: Eg. "a b c a b c"
+Comment: VFSM example
+Comment: Nathan Lasseter (User_4574) 2013
+
+Nodes: Start firsta firstb S0 S1 HA
+
+Start: Start
+
+Accept: HA
+
+Edges:
+	Start a firsta
+	firsta b firstb
+	firstb c HA
+	HA a S0
+	S0 b S1
+	S1 c HA
+End:
diff --git a/examples/even.vfsm b/examples/even.vfsm
new file mode 100644
index 0000000..cc281b2
--- /dev/null
+++ b/examples/even.vfsm
@@ -0,0 +1,17 @@
+Comment: This machine accepts any even binary number
+Comment: Eg. "0 1 0 0 1 0"
+Comment: VFSM example
+Comment: Nathan Lasseter (User_4574) 2013
+
+Nodes: Start HA
+
+Start: Start
+
+Accept: HA
+
+Edges:
+	Start 1 Start
+	Start 0 HA
+	HA 1 Start
+	HA 0 HA
+End:
diff --git a/examples/helloworld.vfsm b/examples/helloworld.vfsm
new file mode 100644
index 0000000..ab808f0
--- /dev/null
+++ b/examples/helloworld.vfsm
@@ -0,0 +1,14 @@
+Comment: This machine accepts "hello world"
+Comment: VFSM example
+Comment: Nathan Lasseter (User_4574) 2013
+
+Nodes: Start S0 HA
+
+Start: Start
+
+Accept: HA
+
+Edges:
+	Start hello S0
+	S0 world HA
+End:
diff --git a/vfsm.rb b/vfsm.rb
new file mode 100644
index 0000000..dbec072
--- /dev/null
+++ b/vfsm.rb
@@ -0,0 +1,129 @@
+class Node
+	def initialize id
+		@id = id
+		@accepting = false
+		@edges = []
+	end
+
+	def id
+		return @id
+	end
+
+	def accepting! accepting=true
+		@accepting = accepting
+	end
+
+	def accepting?
+		return @accepting
+	end
+
+	def pushedge on, to
+		tempto = @edges.select do |edge|
+			edge[0] == on
+		end
+		if tempto.length > 0 then
+			puts "Non-determinism error at node #{@id}"
+			puts "Multiple definitions for on #{on}"
+			exit
+		else
+			@edges.push [on, to]
+		end
+	end
+
+	def goto on
+		to = @edges.select do |edge|
+			edge[0] == on
+		end
+
+		if to.length == 0 then
+			return :reject
+		else
+			return to[0][1]
+		end
+	end
+end
+
+if ARGV[0] == nil or ARGV[1] == nil then
+	puts "Usage: ruby vfsm.rb <machine description file> <input>"
+	exit
+end
+
+inedges = false
+nodes = []
+currentnode = nil
+
+lineno = 0
+File.foreach(ARGV[0]) do |line|
+	lineno += 1
+	linearray = line.chomp.split
+	unless inedges then
+		if linearray == [] then
+			#do nothing
+		elsif linearray[0].downcase == "comment:" then
+			#do nothing
+		elsif linearray[0].downcase == "nodes:" then
+			linearray[1..-1].each do |node|
+				extnode = nodes.select do |inode|
+					inode.id == node
+				end
+				if extnode.length > 0 then
+					puts "Duplicate node id in declaration at line #{lineno}"
+					puts line
+					exit
+				else
+					nodes.push(Node.new node)
+				end
+			end
+		elsif linearray[0].downcase == "start:" then
+			tempsnode = nodes.select do |node|
+				node.id == linearray[1]
+			end
+			currentnode = tempsnode[0]
+		elsif linearray[0].downcase == "accept:" then
+			anodes = nodes.select do |inode|
+				linearray[1..-1].include? inode.id
+			end
+			anodes.each do |inode|
+				inode.accepting!
+			end
+		elsif linearray[0].downcase == "edges:" then
+			inedges = true
+		else
+			puts "Syntax error at line #{lineno}"
+			puts line
+			exit
+		end
+	else
+		if linearray[0].downcase == "end:" then
+			inedges = false
+		else
+			fnodes = nodes.select do |node|
+				node.id == linearray[0]
+			end
+			tnodes = nodes.select do |node|
+				node.id == linearray[2]
+			end
+			fnodes[0].pushedge linearray[1], tnodes[0]
+		end
+	end
+end
+
+ARGV[1].chomp.split.each do |input|
+	print "(#{currentnode.id}) --#{input}--> "
+	nextnode = currentnode.goto input
+	if nextnode == :reject then
+		puts
+		puts "Invalid input, REJECTED"
+		exit
+	else
+		currentnode = nextnode
+	end
+end
+
+puts "(#{currentnode.id})"
+
+if currentnode.accepting? then
+	puts "Valid input, ACCEPTED"
+else
+	puts "Invalid input, REJECTED"
+end