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

#initializeTransitionTable

Returns a new instance of TransitionTable


12
13
14
15
16
17
# File 'actionpack/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

#acceptingObject

Returns the value of attribute accepting


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

def accepting
  @accepting
end

#memosObject (readonly)

Returns the value of attribute memos


10
11
12
# File 'actionpack/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 'actionpack/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 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 19

def accepting?(state)
  accepting == state
end

#accepting_statesObject


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

def accepting_states
  [accepting]
end

#add_memo(idx, memo) ⇒ Object


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

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

#alphabetObject


109
110
111
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 109

def alphabet
  inverted.values.map(&:keys).flatten.compact.uniq.sort_by { |x| x.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.


115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 115

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.


95
96
97
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 95

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

#generalized_tableObject

Returns a generalized transition graph with reduced states. The states are reduced like a DFA, but the table must be simulated like an NFA.

Edges of the GTG are regular expressions.


52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 52

def generalized_table
  gt       = GTG::TransitionTable.new
  marked   = {}
  state_id = Hash.new { |h,k| h[k] = h.length }
  alphabet = self.alphabet

  stack = [eclosure(0)]

  until stack.empty?
    state = stack.pop
    next if marked[state] || state.empty?

    marked[state] = true

    alphabet.each do |alpha|
      next_state = eclosure(following_states(state, alpha))
      next if next_state.empty?

      gt[state_id[state], state_id[next_state]] = alpha
      stack << next_state
    end
  end

  final_groups = state_id.keys.find_all { |s|
    s.sort.last == accepting
  }

  final_groups.each do |states|
    id = state_id[states]

    gt.add_accepting(id)
    save = states.find { |s|
      @memos.key?(s) && eclosure(s).sort.last == accepting
    }

    gt.add_memo(id, memo(save))
  end

  gt
end

#memo(idx) ⇒ Object


31
32
33
# File 'actionpack/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 'actionpack/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.


101
102
103
104
105
106
107
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 101

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

#statesObject


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

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

#transitionsObject


133
134
135
136
137
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 133

def transitions
  @table.map { |to, hash|
    hash.map { |from, sym| [from, sym, to] }
  }.flatten(1)
end