class Rutile::NFA
Attributes
end[RW]
new_stack[RW]
nodes[RW]
old_stack[RW]
start[RW]
Public Class Methods
new(str = [], opp = false, value = :transition_state, dummy: false)
click to toggle source
# File lib/rutile/nfa.rb, line 69 def initialize(str = [], opp = false, value = :transition_state, dummy: false) if !(dummy) @nodes = Array.new(2) {|x| Node.new x } @start = @nodes.first.pos @end = @nodes.last.pos val = opp ? :not : @end if opp @nodes[@start].set_not [@end] end str.each do |char| if char == :dot throw Exception.new ("can't be not AND dot.") if val == :not @nodes[@start].set_not([val]) @nodes[@start].empty("\n") else @nodes[@start].add(char, val) end end end @new_stack = [] @old_stack = [] end
to_nfa(regex_raw, value)
click to toggle source
# File lib/rutile/nfa.rb, line 206 def self::to_nfa(regex_raw, value) regex_raw = regex_raw.chars regex = [] brackets = false while (!regex_raw.empty?) char = regex_raw.shift if brackets case char when "]" regex << :clb brackets = false when "\\" ch = regex_raw.shift case ch when 'd' regex += "1234567890".chars when 'a' regex += "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".chars when 'w' regex += " \t".chars else regex << ch end else regex << char end else case char when "." regex << :dot when "(" regex << :opp when ")" regex << :clp when "*" regex << :ast when "+" regex << :plu when "?" regex << :que when "[" brackets = true regex << :opb when "|" regex << :pip when "\\" regex << regex_raw.shift else regex << char end end end ret = create_nfa(regex) if (regex != []) throw Exception.new "malformed regex." end ret.set_val value return ret end
Private Class Methods
create_nfa(regex)
click to toggle source
# File lib/rutile/nfa.rb, line 271 def self::create_nfa(regex) ret = NFA.new([""]) while !regex.empty? case regex.first # parens first when :opp sub_regex = [] count = 1 regex.shift while count > 0 curr = regex.shift if curr.nil? throw Exception.new "malformed regex: unmatched parenthases" end if curr == :opp count += 1 elsif curr == :clp count -= 1 end sub_regex.append(curr) end sub_regex.pop ret.and create_nfa(sub_regex) # brackets when :opb chars = [] regex.shift opp = (regex.first == :not) regex.shift if opp while ((curr = regex.shift) != :clb) chars.append(curr) end segment = NFA.new(chars, opp) case (ch = regex.shift) when :plu segment.plus when :que segment.question when :ast segment.asterix else regex.unshift ch end ret.and segment # or when :pip regex.shift ret.or create_nfa(regex) break # lastly asterix plus and question when :ast regex.shift ret.asterix when :plu regex.shift ret.plus when :que regex.shift ret.question # otherwise it is just a char else char = NFA.new([regex.shift]) case x = regex.shift when :plu char.plus when :ast char.asterix when nil else regex.unshift x end ret.and char end end return ret end
Public Instance Methods
and(a)
click to toggle source
# File lib/rutile/nfa.rb, line 110 def and a a.nodes.each {|node| node.update_pos @nodes.size} @nodes[@end].add("", a.start + @nodes.size) @end = a.end + @nodes.size @nodes += a.nodes end
asterix()
click to toggle source
# File lib/rutile/nfa.rb, line 138 def asterix @nodes[@end].add("", @start) @nodes[@start].add("", @end) end
dup()
click to toggle source
# File lib/rutile/nfa.rb, line 153 def dup dupl = NFA.new(dummy: true) dupl.nodes = (@nodes.map {|node| node.dup}).to_a dupl.start = @start dupl.end = @end return dupl end
feed(char)
click to toggle source
# File lib/rutile/nfa.rb, line 96 def feed(char) move(char) finalize return val end
or(a)
click to toggle source
# File lib/rutile/nfa.rb, line 117 def or a total_size = a.nodes.size + @nodes.size new_start = Node.new(total_size) new_end = Node.new(total_size + 1) a.nodes.each {|node| node.update_pos @nodes.size} new_start.add("",@start) new_start.add("",a.start + @nodes.size) @nodes[@end].add("", new_end.pos) a.nodes[a.end].add("", new_end.pos) @nodes += a.nodes @nodes += [new_start, new_end] @start = new_start.pos @end = new_end.pos end
plus()
click to toggle source
# File lib/rutile/nfa.rb, line 147 def plus clone = self.dup clone.asterix self.and(clone) end
question()
click to toggle source
# File lib/rutile/nfa.rb, line 143 def question @nodes[@start].add("", @end) end
reset()
click to toggle source
# File lib/rutile/nfa.rb, line 102 def reset @new_stack = [] @old_stack = [] e_closure(@start) finalize return val end
set_val(value)
click to toggle source
# File lib/rutile/nfa.rb, line 163 def set_val value @nodes[@end].value = value end
val()
click to toggle source
# File lib/rutile/nfa.rb, line 168 def val return @old_stack.map do |ind| @nodes[ind].value end.to_a.uniq end
Private Instance Methods
e_closure(ind)
click to toggle source
# File lib/rutile/nfa.rb, line 176 def e_closure(ind) return if @nodes[ind].marked? @new_stack << ind node = @nodes[ind] node.mark node.next("").each do |edge| e_closure(edge) end end
finalize()
click to toggle source
# File lib/rutile/nfa.rb, line 197 def finalize @new_stack.each do |ind| @nodes[ind].unmark old_stack << ind end @new_stack = [] end
move(char)
click to toggle source
# File lib/rutile/nfa.rb, line 186 def move(char) @old_stack.each do |ind| @nodes[ind].next(char).each do |edge| if !@nodes[edge].marked? e_closure(edge) end end end @old_stack = [] end