From 5e179bfadb1d73779f69737dea611c43c6d48587 Mon Sep 17 00:00:00 2001
From: Nathan Lasseter <nathan.je.lasseter@googlemail.com>
Date: Sun, 24 Mar 2013 13:05:46 +0000
Subject: Parser for syntax v2, more examples, formatted output to (())
 accepting nodes

---
 README              |  6 ++---
 examples/mfcs.vfsm  | 15 ++++++++++++
 examples/mfcs2.vfsm | 19 +++++++++++++++
 vfsm.rb             | 68 +++++++++++++++++++++++++++++++++++------------------
 4 files changed, 82 insertions(+), 26 deletions(-)
 create mode 100644 examples/mfcs.vfsm
 create mode 100644 examples/mfcs2.vfsm

diff --git a/README b/README
index 6ec4d1f..6478a54 100644
--- a/README
+++ b/README
@@ -3,18 +3,18 @@ If an emulation of a machine is a virtual machine, then this is VFSM: the Virtua
 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
 
+There may be any number of Comment: lines which are unsurprisingly ignored.
+In the VFSM v2 syntax, you do not need a nodes line, the node ids are inferred from the start:, accept:, and edges:-end: lines. Nodes: lines are ignored for backwards compatability.
+
 The input is a string of space separated input tokens.
 
 See the examples.
diff --git a/examples/mfcs.vfsm b/examples/mfcs.vfsm
new file mode 100644
index 0000000..2320199
--- /dev/null
+++ b/examples/mfcs.vfsm
@@ -0,0 +1,15 @@
+comment: MFCS Problems for Lecture 1
+comment: Question 5a
+comment: VFSM syntax version 2
+comment: Any 00 in the string must be followed by a 1.
+comment: eg. "1 0 1" "0 0 1 0 0 1 1 0 1"
+
+start: s0
+accept: s0 s1
+edges:
+	s0 0 s1
+	s1 0 s2
+	s1 1 s0
+	s2 1 s0
+	s0 1 s0
+end:
diff --git a/examples/mfcs2.vfsm b/examples/mfcs2.vfsm
new file mode 100644
index 0000000..2e70532
--- /dev/null
+++ b/examples/mfcs2.vfsm
@@ -0,0 +1,19 @@
+comment: MFCS Problems for Lecture 1
+comment: VFSM Syntax v2
+comment: Input over the alphabet {0, 1}
+comment: The leftmost and rightmost input must differ
+
+start: start
+accept: h0 h1
+edges:
+	start 1 q0
+	q0 1 q0
+	q0 0 h0
+	h0 1 q0
+	h0 0 h0
+	start 0 q1
+	q1 0 q1
+	q1 1 h1
+	h1 1 h1
+	h1 0 q1
+end:
diff --git a/vfsm.rb b/vfsm.rb
index dbec072..efbf949 100644
--- a/vfsm.rb
+++ b/vfsm.rb
@@ -1,7 +1,7 @@
 class Node
-	def initialize id
+	def initialize id, accepting = false
 		@id = id
-		@accepting = false
+		@accepting = accepting
 		@edges = []
 	end
 
@@ -62,29 +62,29 @@ File.foreach(ARGV[0]) do |line|
 		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
+			#do nothing
+			#ignore line for backwards compatability
 		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
+			if tempsnode.length == 0 then
+				currentnode = Node.new linearray[1]
+				nodes.push currentnode
+			else
+				currentnode = tempsnode[0]
 			end
-			anodes.each do |inode|
-				inode.accepting!
+		elsif linearray[0].downcase == "accept:" then
+			linearray[1..-1].each do |node|
+				anodes = nodes.select do |inode|
+					node == inode.id
+				end
+				if anodes.length == 0 then
+					mynode = Node.new node, true
+					nodes.push mynode
+				else
+					anodes[0].accepting!
+				end
 			end
 		elsif linearray[0].downcase == "edges:" then
 			inedges = true
@@ -97,19 +97,37 @@ File.foreach(ARGV[0]) do |line|
 		if linearray[0].downcase == "end:" then
 			inedges = false
 		else
+			fnode = nil
+			tnode = nil
 			fnodes = nodes.select do |node|
 				node.id == linearray[0]
 			end
+			if fnodes.length == 0 then
+				fnode = Node.new linearray[0]
+				nodes.push fnode
+			else
+				fnode = fnodes[0]
+			end
 			tnodes = nodes.select do |node|
 				node.id == linearray[2]
 			end
-			fnodes[0].pushedge linearray[1], tnodes[0]
+			if tnodes.length == 0 then
+				tnode = Node.new linearray[2]
+				nodes.push tnode
+			else
+				tnode = tnodes[0]
+			end
+			fnode.pushedge linearray[1], tnode
 		end
 	end
 end
 
 ARGV[1].chomp.split.each do |input|
-	print "(#{currentnode.id}) --#{input}--> "
+	if currentnode.accepting? then
+		print "((#{currentnode.id})) --#{input}--> "
+	else
+		print "(#{currentnode.id}) --#{input}--> "
+	end
 	nextnode = currentnode.goto input
 	if nextnode == :reject then
 		puts
@@ -120,7 +138,11 @@ ARGV[1].chomp.split.each do |input|
 	end
 end
 
-puts "(#{currentnode.id})"
+if currentnode.accepting? then
+	puts "((#{currentnode.id}))"
+else
+	puts "(#{currentnode.id})"
+end
 
 if currentnode.accepting? then
 	puts "Valid input, ACCEPTED"
-- 
cgit v1.2.1