Class: Aurum::Grammar::LexicalRules::Automata

Inherits:
Object
  • Object
show all
Defined in:
lib/aurum/grammar/automata.rb

Defined Under Namespace

Classes: Transition

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(table = []) ⇒ Automata

Returns a new instance of Automata.



7
8
9
 
# File 'lib/aurum/grammar/automata.rb', line 7

def initialize(table=[])
  @table = table.is_a?(Array) ? table : Array.new(table){[]}
end

Instance Attribute Details

#table ⇒ Object (readonly)

Returns the value of attribute table.



6
7
8
 
# File 'lib/aurum/grammar/automata.rb', line 6

def table
  @table
end

Instance Method Details

#all_states ⇒ Object 



29
30
31
 
# File 'lib/aurum/grammar/automata.rb', line 29

def all_states
  (0..@table.size - 1).to_a
end

#alphabet(states) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/aurum/grammar/automata.rb', line 33

def alphabet states
  points, reachable_states = [], []
  for state in states
    @table[state].each {|tran| points.concat(tran.character_set.to_points(tran.destination))}
  end
  points.sort!
  points.each_with_index do |point, index|
    if point.is_start
      reachable_states << point.destination
    else
      reachable_states.delete point.destination
      next if reachable_states.empty?
    end
    character_set = range(point, points[index + 1])
    yield(reachable_states.uniq, character_set) if character_set
  end
end

#connect(start, character_set, destination) ⇒ Object 



11
12
13
14
 
# File 'lib/aurum/grammar/automata.rb', line 11

def connect start, character_set, destination
  @table[start]  << Transition.new(character_set, destination)
  destination
end

#dup ⇒ Object 



51
52
53
 
# File 'lib/aurum/grammar/automata.rb', line 51

def dup
  Automata.new(@table.map {|x| x.dup})
end

#merge!(other) ⇒ Object 



16
17
18
19
20
21
22
 
# File 'lib/aurum/grammar/automata.rb', line 16

def merge! other
  start = @table.length
  for trans in other.table
    @table << trans.map {|tran| Transition.new(tran.character_set, tran.destination + start)}
  end
  start
end

#new_state ⇒ Object 



24
25
26
27
 
# File 'lib/aurum/grammar/automata.rb', line 24

def new_state
  @table << []
  @table.size - 1
end

#remove_dead_states(accepts) ⇒ Object 



63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/aurum/grammar/automata.rb', line 63

def remove_dead_states accepts
  dead_states = []
  @table.each_with_index do |state, index|
    next if accepts.include?(index) || state.any? {|tran| tran.destination != index }
    dead_states << index
  end
  unless dead_states.empty?
    @table.each_with_index do |state, index|
      state.delete_if {|tran| dead_states.include?(tran.destination) }
    end
  end
end

#reverse ⇒ Object 



55
56
57
58
59
60
61
 
# File 'lib/aurum/grammar/automata.rb', line 55

def reverse
  reverse = Automata.new(@table.size)
  @table.each_with_index do |state, index|
    state.each{|tran| reverse.connect(tran.destination, tran.character_set, index)}
  end
  reverse
end