1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
require_relative "dot"
module ActionDispatch
module Journey # :nodoc:
module NFA # :nodoc:
class TransitionTable # :nodoc:
include Journey::NFA::Dot
attr_accessor :accepting
attr_reader :memos
def initialize
@table = Hash.new { |h, f| h[f] = {} }
@memos = {}
@accepting = nil
@inverted = nil
end
def accepting?(state)
accepting == state
end
def accepting_states
[accepting]
end
def add_memo(idx, memo)
@memos[idx] = memo
end
def memo(idx)
@memos[idx]
end
def []=(i, f, s)
@table[f][i] = s
end
def merge(left, right)
@memos[right] = @memos.delete(left)
@table[right] = @table.delete(left)
end
def states
(@table.keys + @table.values.flat_map(&:keys)).uniq
end
# Returns set of NFA states to which there is a transition on ast symbol
# +a+ from some state +s+ in +t+.
def following_states(t, a)
Array(t).flat_map { |s| inverted[s][a] }.uniq
end
# Returns set of NFA states to which there is a transition on ast symbol
# +a+ from some state +s+ in +t+.
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
def alphabet
inverted.values.flat_map(&:keys).compact.uniq.sort_by(&:to_s)
end
# Returns a set of NFA states reachable from some NFA state +s+ in set
# +t+ on nil-transitions alone.
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
def transitions
@table.flat_map { |to, hash|
hash.map { |from, sym| [from, sym, to] }
}
end
private
def inverted
return @inverted if @inverted
@inverted = Hash.new { |h, from|
h[from] = Hash.new { |j, s| j[s] = [] }
}
@table.each { |to, hash|
hash.each { |from, sym|
if sym
sym = Nodes::Symbol === sym ? sym.regexp : sym.left
end
@inverted[from][sym] << to
}
}
@inverted
end
end
end
end
end
|
