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

Inherits:
Object
  • Object
show all
Includes:
Dot
Defined in:
actionpack/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.



14
15
16
17
18
19
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 14

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



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

def accepting
  @accepting
end

#memos ⇒ Object (readonly)

Returns the value of attribute memos



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

def memos
  @memos
end

Instance Method Details

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



37
38
39
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 37

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

#accepting?(state) ⇒ Boolean

Returns:

  • (Boolean) 


21
22
23
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 21

def accepting?(state)
  accepting == state
end

#accepting_states ⇒ Object 



25
26
27
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 25

def accepting_states
  [accepting]
end

#add_memo(idx, memo) ⇒ Object 



29
30
31
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 29

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

#alphabet ⇒ Object 



66
67
68
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 66

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.



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

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.



52
53
54
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 52

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

#memo(idx) ⇒ Object 



33
34
35
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 33

def memo(idx)
  @memos[idx]
end

#merge(left, right) ⇒ Object 



41
42
43
44
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 41

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.



58
59
60
61
62
63
64
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 58

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 



46
47
48
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 46

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

#transitions ⇒ Object 



90
91
92
93
94
 
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 90

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