Class: ActionDispatch::Journey::NFA::TransitionTable

Inherits:
Object
  • Object
show all
Includes:
Dot
Defined in:
lib/action_dispatch/journey/nfa/transition_table.rb

Overview

:nodoc:

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Dot

#to_dot

Constructor Details

#initialize ⇒ TransitionTable

Returns a new instance of TransitionTable.



12
13
14
15
16
17
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 12

def initialize
  @table     = Hash.new { |h, f| h[f] = {} }
  @memos     = {}
  @accepting = nil
  @inverted  = nil
end

Instance Attribute Details

#accepting ⇒ Object

Returns the value of attribute accepting.



9
10
11
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 9

def accepting
  @accepting
end

#memos ⇒ Object (readonly)

Returns the value of attribute memos.



10
11
12
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 10

def memos
  @memos
end

Instance Method Details

#[]=(i, f, s) ⇒ Object 



35
36
37
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 35

def []=(i, f, s)
  @table[f][i] = s
end

#accepting?(state) ⇒ Boolean

Returns:

  • (Boolean) 


19
20
21
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 19

def accepting?(state)
  accepting == state
end

#accepting_states ⇒ Object 



23
24
25
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 23

def accepting_states
  [accepting]
end

#add_memo(idx, memo) ⇒ Object 



27
28
29
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 27

def add_memo(idx, memo)
  @memos[idx] = memo
end

#alphabet ⇒ Object 



64
65
66
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 64

def alphabet
  inverted.values.flat_map(&:keys).compact.uniq.sort_by(&:to_s)
end

#eclosure(t) ⇒ Object

Returns a set of NFA states reachable from some NFA state s in set t on nil-transitions alone.



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 70

def eclosure(t)
  stack = Array(t)
  seen  = {}
  children = []

  until stack.empty?
    s = stack.pop
    next if seen[s]

    seen[s] = true
    children << s

    stack.concat(inverted[s][nil])
  end

  children.uniq
end

#following_states(t, a) ⇒ Object

Returns set of NFA states to which there is a transition on ast symbol a from some state s in t.



50
51
52
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 50

def following_states(t, a)
  Array(t).flat_map { |s| inverted[s][a] }.uniq
end

#memo(idx) ⇒ Object 



31
32
33
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 31

def memo(idx)
  @memos[idx]
end

#merge(left, right) ⇒ Object 



39
40
41
42
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 39

def merge(left, right)
  @memos[right] = @memos.delete(left)
  @table[right] = @table.delete(left)
end

#move(t, a) ⇒ Object

Returns set of NFA states to which there is a transition on ast symbol a from some state s in t.



56
57
58
59
60
61
62
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 56

def move(t, a)
  Array(t).map { |s|
    inverted[s].keys.compact.find_all { |sym|
      sym === a
    }.map { |sym| inverted[s][sym] }
  }.flatten.uniq
end

#states ⇒ Object 



44
45
46
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 44

def states
  (@table.keys + @table.values.flat_map(&:keys)).uniq
end

#transitions ⇒ Object 



88
89
90
91
92
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 88

def transitions
  @table.flat_map { |to, hash|
    hash.map { |from, sym| [from, sym, to] }
  }
end