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
|
require 'journey/gtg/transition_table'
module Journey
module GTG
class Builder
DUMMY = Nodes::Dummy.new # :nodoc:
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.map { |l| followpos(l) }.flatten
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.map { |c| firstpos(c) }.flatten.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.map { |c| lastpos(c) }.flatten.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
|
