blob: 532f765094e1f2e1dcea90f5041cefe9af93d9ae (
plain) (
blame)
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
|
require "action_dispatch/journey/nfa/transition_table"
require "action_dispatch/journey/gtg/transition_table"
module ActionDispatch
module Journey # :nodoc:
module NFA # :nodoc:
class Visitor < Visitors::Visitor # :nodoc:
def initialize(tt)
@tt = tt
@i = -1
end
def visit_CAT(node)
left = visit(node.left)
right = visit(node.right)
@tt.merge(left.last, right.first)
[left.first, right.last]
end
def visit_GROUP(node)
from = @i += 1
left = visit(node.left)
to = @i += 1
@tt.accepting = to
@tt[from, left.first] = nil
@tt[left.last, to] = nil
@tt[from, to] = nil
[from, to]
end
def visit_OR(node)
from = @i += 1
children = node.children.map { |c| visit(c) }
to = @i += 1
children.each do |child|
@tt[from, child.first] = nil
@tt[child.last, to] = nil
end
@tt.accepting = to
[from, to]
end
def terminal(node)
from_i = @i += 1 # new state
to_i = @i += 1 # new state
@tt[from_i, to_i] = node
@tt.accepting = to_i
@tt.add_memo(to_i, node.memo)
[from_i, to_i]
end
end
class Builder # :nodoc:
def initialize(ast)
@ast = ast
end
def transition_table
tt = TransitionTable.new
Visitor.new(tt).accept(@ast)
tt
end
end
end
end
end
|
