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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
require "action_dispatch/journey/gtg/transition_table"
module ActionDispatch
module Journey # :nodoc:
module GTG # :nodoc:
class Builder # :nodoc:
DUMMY = Nodes::Dummy.new
attr_reader :root, :ast, :endpoints
def initialize(root)
@root = root
@ast = Nodes::Cat.new root, DUMMY
@followpos = nil
end
def transition_table
dtrans = TransitionTable.new
marked = {}
state_id = Hash.new { |h,k| h[k] = h.length }
start = firstpos(root)
dstates = [start]
until dstates.empty?
s = dstates.shift
next if marked[s]
marked[s] = true # mark s
s.group_by { |state| symbol(state) }.each do |sym, ps|
u = ps.flat_map { |l| followpos(l) }
next if u.empty?
if u.uniq == [DUMMY]
from = state_id[s]
to = state_id[Object.new]
dtrans[from, to] = sym
dtrans.add_accepting(to)
ps.each { |state| dtrans.add_memo(to, state.memo) }
else
dtrans[state_id[s], state_id[u]] = sym
if u.include?(DUMMY)
to = state_id[u]
accepting = ps.find_all { |l| followpos(l).include?(DUMMY) }
accepting.each { |accepting_state|
dtrans.add_memo(to, accepting_state.memo)
}
dtrans.add_accepting(state_id[u])
end
end
dstates << u
end
end
dtrans
end
def nullable?(node)
case node
when Nodes::Group
true
when Nodes::Star
true
when Nodes::Or
node.children.any? { |c| nullable?(c) }
when Nodes::Cat
nullable?(node.left) && nullable?(node.right)
when Nodes::Terminal
!node.left
when Nodes::Unary
nullable?(node.left)
else
raise ArgumentError, "unknown nullable: %s" % node.class.name
end
end
def firstpos(node)
case node
when Nodes::Star
firstpos(node.left)
when Nodes::Cat
if nullable?(node.left)
firstpos(node.left) | firstpos(node.right)
else
firstpos(node.left)
end
when Nodes::Or
node.children.flat_map { |c| firstpos(c) }.uniq
when Nodes::Unary
firstpos(node.left)
when Nodes::Terminal
nullable?(node) ? [] : [node]
else
raise ArgumentError, "unknown firstpos: %s" % node.class.name
end
end
def lastpos(node)
case node
when Nodes::Star
firstpos(node.left)
when Nodes::Or
node.children.flat_map { |c| lastpos(c) }.uniq
when Nodes::Cat
if nullable?(node.right)
lastpos(node.left) | lastpos(node.right)
else
lastpos(node.right)
end
when Nodes::Terminal
nullable?(node) ? [] : [node]
when Nodes::Unary
lastpos(node.left)
else
raise ArgumentError, "unknown lastpos: %s" % node.class.name
end
end
def followpos(node)
followpos_table[node]
end
private
def followpos_table
@followpos ||= build_followpos
end
def build_followpos
table = Hash.new { |h, k| h[k] = [] }
@ast.each do |n|
case n
when Nodes::Cat
lastpos(n.left).each do |i|
table[i] += firstpos(n.right)
end
when Nodes::Star
lastpos(n).each do |i|
table[i] += firstpos(n)
end
end
end
table
end
def symbol(edge)
case edge
when Journey::Nodes::Symbol
edge.regexp
else
edge.left
end
end
end
end
end
end
|
