Module: Flexr::Automaton::Minimizer

Defined in:
lib/flexr/automaton/minimizer.rb

Class Method Summary collapse

Class Method Details

.enqueue(partition, worklist, pending) ⇒ Object 



67
68
69
70
 
# File 'lib/flexr/automaton/minimizer.rb', line 67

def enqueue(partition, worklist, pending)
  worklist << partition
  pending[partition] = true
end

.group_ids(partitions) ⇒ Object 



93
94
95
96
97
 
# File 'lib/flexr/automaton/minimizer.rb', line 93

def group_ids(partitions)
  partitions.each_with_index.with_object({}) do |(partition, group), result|
    partition.each { |state| result[state] = group }
  end
end

.initial_partitions(dfa, dead) ⇒ Object 



18
19
20
 
# File 'lib/flexr/automaton/minimizer.rb', line 18

def initial_partitions(dfa, dead)
  (0..dead).group_by { |state| state == dead ? [] : dfa.accepts[state] }.values
end

.minimize(dfa) ⇒ Object 



8
9
10
11
12
13
14
15
16
 
# File 'lib/flexr/automaton/minimizer.rb', line 8

def minimize(dfa)
  dead = dfa.states
  rows = dfa.transitions.map { |row| row.map { |destination| destination.nil? ? dead : destination } }
  rows << Array.new(dfa.class_count, dead)
  partitions = initial_partitions(dfa, dead)
  predecessors = predecessor_index(rows, dfa.class_count)
  partitions = refine(partitions, predecessors, dfa.class_count)
  rebuild(dfa, partitions, dead)
end

.predecessor_index(rows, class_count) ⇒ Object 



22
23
24
25
26
27
28
 
# File 'lib/flexr/automaton/minimizer.rb', line 22

def predecessor_index(rows, class_count)
  Array.new(class_count) { Array.new(rows.length) { [] } }.tap do |index|
    rows.each_with_index do |row, state|
      row.each_with_index { |destination, class_id| index[class_id][destination] << state }
    end
  end
end

.reachable_groups(dfa, groups, representatives, start_group, dead_group) ⇒ Object 



99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/flexr/automaton/minimizer.rb', line 99

def reachable_groups(dfa, groups, representatives, start_group, dead_group)
  result = []
  queue = [start_group]
  seen = {}
  cursor = 0
  while cursor < queue.length
    group = queue.fetch(cursor)
    cursor += 1
    next if seen[group] || (group == dead_group && group != start_group)

    seen[group] = true
    result << group
    representative = representatives.fetch(group)
    dfa.transitions.fetch(representative).compact.each { |destination| queue << groups.fetch(destination) }
  end
  result
end

.rebuild(dfa, partitions, dead) ⇒ Object 



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/flexr/automaton/minimizer.rb', line 72

def rebuild(dfa, partitions, dead)
  groups = group_ids(partitions)
  dead_group = groups.fetch(dead)
  start_group = groups.fetch(dfa.start)
  representatives = partitions.map { |partition| partition.find { |state| state != dead } }
  order = reachable_groups(dfa, groups, representatives, start_group, dead_group)
  index = order.each_with_index.to_h
  transitions = order.map do |group|
    representative = representatives.fetch(group)
    dfa.transitions.fetch(representative).map do |destination|
      next nil if destination.nil? || groups.fetch(destination) == dead_group

      index.fetch(groups.fetch(destination))
    end
  end
  accepts = order.map { |group| dfa.accepts.fetch(representatives.fetch(group)) }
  rule_ids = accepts.flatten.map(&:rule_index).uniq.sort
  DFA.new(transitions: transitions, accepts: accepts, ec: dfa.ec, class_count: dfa.class_count,
          start: 0, rule_ids: rule_ids)
end

.refine(partitions, predecessors, class_count) ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/flexr/automaton/minimizer.rb', line 30

def refine(partitions, predecessors, class_count)
  worklist = partitions.dup
  pending = {}.compare_by_identity
  partitions.each { |partition| pending[partition] = true }
  cursor = 0
  while cursor < worklist.length
    splitter = worklist.fetch(cursor)
    cursor += 1
    next unless pending.delete(splitter)

    class_count.times do |class_id|
      marked = splitter.each_with_object({}) do |state, result|
        predecessors[class_id][state].each { |predecessor| result[predecessor] = true }
      end
      next if marked.empty?

      partitions = split_partitions(partitions, marked, worklist, pending)
    end
  end
  partitions
end

.split_partitions(partitions, marked, worklist, pending) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/flexr/automaton/minimizer.rb', line 52

def split_partitions(partitions, marked, worklist, pending)
  partitions.flat_map do |partition|
    inside, outside = partition.partition { |state| marked[state] }
    next [partition] if inside.empty? || outside.empty?

    if pending.delete(partition)
      enqueue(inside, worklist, pending)
      enqueue(outside, worklist, pending)
    else
      enqueue(inside.length <= outside.length ? inside : outside, worklist, pending)
    end
    [inside, outside]
  end
end