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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
#include "stdafx.h"
#include "State.h"
#include "Parser.h"
namespace storm {
namespace syntax {
namespace earley {
StatePtr::StatePtr() : step(-1), index(-1) {}
StatePtr::StatePtr(Nat step, Nat index) : step(step), index(index) {}
void StatePtr::toS(StrBuf *to) const {
*to << S("(") << step << S(", ") << index << S(")");
}
wostream &operator <<(wostream &to, StatePtr p) {
return to << L"(" << p.step << L", " << p.index << L")";
}
State::State() : from(0) {}
State::State(ProductionIter pos, Nat from) : pos(pos), from(from) {}
State::State(ProductionIter pos, Nat from, StatePtr prev)
: pos(pos), from(from), prev(prev) {}
State::State(ProductionIter pos, Nat from, StatePtr prev, StatePtr completed)
: pos(pos), from(from), prev(prev), completed(completed) {}
void State::toS(StrBuf *to) const {
*to << S("{") << pos << S(", ") << from << S(", ") << prev << S(", ") << completed << S("}");
}
wostream &operator <<(wostream &to, State s) {
return to << L"{" << s.pos << L", " << s.from << L", " << s.prev << L", " << s.completed << L"}";
}
StateSet::StateSet() : chunks(null) {
stateArrayType = StormInfo<State>::handle(engine()).gcArrayType;
}
void StateSet::push(Parser *parser, const State &s) {
if (!s.valid())
return;
// TODO: Optimize this somehow. A lot of time is spent here!
Nat chunkCount = chunks ? Nat(chunks->filled) : 0;
for (nat c = 0; c < chunkCount; c++) {
GcArray<State> *chunk = chunks->v[c];
Nat cnt = Nat(chunk->filled);
for (nat i = 0; i < cnt; i++) {
State &old = chunk->v[i];
if (old == s) {
// Generated this state alreadly, shall we update it?
// Keep the largest in a lexiographic ordering.
if (execOrder(parser, s, old) != before)
return;
chunk->v[i] = s;
return;
}
}
}
// Push the new state somewhere.
GcArray<State> *last = null;
if (chunks == null) {
ensure(1);
last = chunks->v[0];
} else {
last = chunks->v[chunks->filled - 1];
}
if (last->filled >= chunkSize) {
ensure(Nat(chunks->filled + 1));
last = chunks->v[chunks->filled - 1];
}
last->v[last->filled++] = s;
}
void StateSet::ensure(Nat n) {
// Need to resize the array?
if (chunks == null || chunks->count < n) {
Nat newCount = 1;
if (chunks)
newCount = 2 * Nat(chunks->count);
newCount = max(n, newCount);
GcArray<GcArray<State> *> *old = chunks;
chunks = runtime::allocArray<GcArray<State> *>(engine(), &pointerArrayType, newCount);
if (old) {
memcpy(chunks->v, old->v, sizeof(void *)*old->count);
chunks->filled = old->filled;
}
}
// Make sure all entries are filled.
while (chunks->filled < n) {
chunks->v[chunks->filled++] = runtime::allocArray<State>(engine(), stateArrayType, chunkSize);
}
}
void StateSet::push(Parser *parser, ProductionIter pos, Nat from) {
push(parser, pos, from, StatePtr(), StatePtr());
}
void StateSet::push(Parser *parser, ProductionIter pos, Nat from, StatePtr prev) {
push(parser, pos, from, prev, StatePtr());
}
void StateSet::push(Parser *parser, ProductionIter pos, Nat from, StatePtr prev, StatePtr completed) {
if (!pos.valid())
return;
push(parser, State(pos, from, prev, completed));
}
StateSet::Order StateSet::execOrder(Parser *parser, const StatePtr &aPtr, const StatePtr &bPtr) const {
// Invalid states have no ordering.
if (aPtr == StatePtr() || bPtr == StatePtr())
return none;
// Same state, realize that quickly!
if (aPtr == bPtr)
return none;
return execOrder(parser, parser->state(aPtr), parser->state(bPtr));
}
StateSet::Order StateSet::execOrder(Parser *parser, const State &a, const State &b) const {
// Check which has the highest priority.
if (a.priority() != b.priority())
return (a.priority() > b.priority()) ? before : after;
// If they are different productions and noone has a higher priority than the other, the
// ordering is undefined.
if (a.production() != b.production())
return none;
// Order them lexiographically to see which has the highest priority!
StateArray aStates(engine());
prevCompleted(parser, a, aStates);
StateArray bStates(engine());
prevCompleted(parser, b, bStates);
nat to = min(aStates.count(), bStates.count());
for (nat i = 0; i < to; i++) {
Order order = execOrder(parser, aStates[i], bStates[i]);
if (order != none)
return order;
}
// Pick the longer one in case they are equal so far. This makes * and + greedy.
if (aStates.count() > bStates.count()) {
return before;
} else if (aStates.count() < bStates.count()) {
return after;
}
// The rules are equal as far as we are concerned.
return none;
}
void StateSet::prevCompleted(Parser *parser, const State &from, StateArray &to) const {
to.clear();
// Note: the first state is never completed, so we skip that.
for (const State *at = &from; at->prev != StatePtr(); at = &parser->state(at->prev)) {
to.push(at->completed);
}
to.reverse();
}
}
}
}
|
