From 771cdb55c4a30be16ddafebc9b43f087765f9876 Mon Sep 17 00:00:00 2001 From: Nathan Lasseter Date: Sat, 23 Mar 2013 22:10:22 +0000 Subject: First commit --- README | 20 ++++++++ examples/abc.vfsm | 19 +++++++ examples/even.vfsm | 17 +++++++ examples/helloworld.vfsm | 14 +++++ vfsm.rb | 129 +++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 199 insertions(+) create mode 100644 README create mode 100644 examples/abc.vfsm create mode 100644 examples/even.vfsm create mode 100644 examples/helloworld.vfsm create mode 100644 vfsm.rb 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 + +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 " + 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 -- cgit v1.2.1