From d9fbb2c4900b008daa9c5e0302677f9d1674a473 Mon Sep 17 00:00:00 2001 From: Nathan Lasseter Date: Sat, 29 Mar 2014 16:23:06 +0000 Subject: Begun modularising --- lib/ndfa.rb | 146 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/node.rb | 44 +++++++++++++++ lib/vfsm.rb | 2 + vfsm.rb | 183 ++---------------------------------------------------------- 4 files changed, 196 insertions(+), 179 deletions(-) create mode 100644 lib/ndfa.rb create mode 100644 lib/node.rb create mode 100644 lib/vfsm.rb diff --git a/lib/ndfa.rb b/lib/ndfa.rb new file mode 100644 index 0000000..2e610cf --- /dev/null +++ b/lib/ndfa.rb @@ -0,0 +1,146 @@ +module VFSM + class NDFA + attr_reader :currentnodes + + def initialize(machineDefinition) + inedges = false + nodes = [] + @currentnodes = [] + + lineno = 0 + File.foreach(machineDefinition) 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 + #do nothing + #ignore line for backwards compatability + elsif linearray[0].downcase == "start:" then + tempsnode = nodes.select do |node| + node.id == linearray[1] + end + if tempsnode.length == 0 then + startnode = Node.new linearray[1] + nodes.push startnode + @currentnodes.push startnode + else + @currentnodes.push tempsnode[0] + end + 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 + else + puts "Syntax error at line #{lineno}" + puts line + exit + end + else + 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 + if tnodes.length == 0 then + tnode = Node.new linearray[2] + nodes.push tnode + else + tnode = tnodes[0] + end + if linearray[1].downcase == "epsilon:" or linearray[1].downcase == "lambda:" then + fnode.pushedge :lambda, tnode + else + fnode.pushedge linearray[1], tnode + end + end + end + end + NDFA.recurse @currentnodes + NDFA.printnodes @currentnodes + end + + def handleinput(inputString) + inputString.chomp.split.each do |input| + nextnodes = [] + @currentnodes.each do |node| + nextnode = node.goto input + unless nextnode == :reject + nextnode.each do |x| + nextnodes.push x + end + end + end + + NDFA.recurse nextnodes + + print " --#{input}--> " + + NDFA.printnodes nextnodes + + if nextnodes == [] then + puts + puts "Invalid input, REJECTED" + exit + else + @currentnodes = nextnodes + end + end + end + + class << self + def printnodes nodes + print "{ " + (0..(nodes.length - 1)).each do |x| + if nodes[x].accepting? then + print "((#{nodes[x].id}))" + else + print "(#{nodes[x].id})" + end + print ", " unless x == (nodes.length - 1) + end + print " }" + end + + def recurse nodeslist + begin + oldlist = nodeslist.dup + oldlist.each do |node| + tmp = node.goto :lambda + unless tmp == :reject then + tmp.each do |x| + nodeslist.push x + end + end + end + nodeslist.uniq! + end while oldlist != nodeslist + end + end + end +end diff --git a/lib/node.rb b/lib/node.rb new file mode 100644 index 0000000..5875e38 --- /dev/null +++ b/lib/node.rb @@ -0,0 +1,44 @@ +module VFSM + class Node + def initialize id, accepting = false + @id = id + @accepting = accepting + @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 + @edges.push [on, to] + end + + def goto on + to = @edges.select do |edge| + edge[0] == on + end + + if to.length == 0 then + return :reject + else + ret = [] + to.each do |x| + ret.push x[1] + end + return ret + end + end + end +end diff --git a/lib/vfsm.rb b/lib/vfsm.rb new file mode 100644 index 0000000..6c5ff96 --- /dev/null +++ b/lib/vfsm.rb @@ -0,0 +1,2 @@ +require './lib/node' +require './lib/ndfa' diff --git a/vfsm.rb b/vfsm.rb index 238b1f6..3bd4251 100644 --- a/vfsm.rb +++ b/vfsm.rb @@ -1,192 +1,17 @@ -require 'pp' -class Node - def initialize id, accepting = false - @id = id - @accepting = accepting - @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 - @edges.push [on, to] - end - - def goto on - to = @edges.select do |edge| - edge[0] == on - end - - if to.length == 0 then - return :reject - else - ret = [] - to.each do |x| - ret.push x[1] - end - return ret - end - end -end +require './lib/vfsm' if ARGV[0] == nil or ARGV[1] == nil then puts "Usage: ruby vfsm.rb " exit end -inedges = false -nodes = [] -currentnodes = [] - -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 - #do nothing - #ignore line for backwards compatability - elsif linearray[0].downcase == "start:" then - tempsnode = nodes.select do |node| - node.id == linearray[1] - end - if tempsnode.length == 0 then - startnode = Node.new linearray[1] - nodes.push startnode - currentnodes.push startnode - else - currentnodes.push tempsnode[0] - end - 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 - else - puts "Syntax error at line #{lineno}" - puts line - exit - end - else - 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 - if tnodes.length == 0 then - tnode = Node.new linearray[2] - nodes.push tnode - else - tnode = tnodes[0] - end - if linearray[1].downcase == "epsilon:" or linearray[1].downcase == "lambda:" then - fnode.pushedge :lambda, tnode - else - fnode.pushedge linearray[1], tnode - end - end - end -end - -def printnodes nodes - print "{ " - (0..(nodes.length - 1)).each do |x| - if nodes[x].accepting? then - print "((#{nodes[x].id}))" - else - print "(#{nodes[x].id})" - end - print ", " unless x == (nodes.length - 1) - end - print " }" -end - -def recurse nodeslist - begin - oldlist = nodeslist.dup - oldlist.each do |node| - tmp = node.goto :lambda - unless tmp == :reject then - tmp.each do |x| - nodeslist.push x - end - end - end - nodeslist.uniq! - end while oldlist != nodeslist -end - -recurse currentnodes -printnodes currentnodes - -ARGV[1].chomp.split.each do |input| - nextnodes = [] - currentnodes.each do |node| - nextnode = node.goto input - unless nextnode == :reject - nextnode.each do |x| - nextnodes.push x - end - end - end - - recurse nextnodes - - print " --#{input}--> " - - printnodes nextnodes - - if nextnodes == [] then - puts - puts "Invalid input, REJECTED" - exit - else - currentnodes = nextnodes - end -end +machine = VFSM::NDFA.new(ARGV[0]) +machine.handleinput(ARGV[1]) puts acc = false -currentnodes.each do |node| +machine.currentnodes.each do |node| acc = true if node.accepting? end if acc then -- cgit v1.2.1