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
181
182
183
184
185
186
187
188
189
|
/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
* Use of this file is governed by the BSD 3-clause license that
* can be found in the LICENSE.txt file in the project root.
*/
#include "atn/RuleStopState.h"
#include "atn/Transition.h"
#include "atn/RuleTransition.h"
#include "atn/SingletonPredictionContext.h"
#include "atn/WildcardTransition.h"
#include "atn/NotSetTransition.h"
#include "misc/IntervalSet.h"
#include "atn/ATNConfig.h"
#include "support/CPPUtils.h"
#include "atn/LL1Analyzer.h"
using namespace antlr4;
using namespace antlr4::atn;
using namespace antlrcpp;
namespace {
struct ATNConfigHasher final {
size_t operator()(const ATNConfig& atn_config) const {
return atn_config.hashCode();
}
};
struct ATNConfigComparer final {
bool operator()(const ATNConfig& lhs, const ATNConfig& rhs) const {
return lhs == rhs;
}
};
class LL1AnalyzerImpl final {
public:
LL1AnalyzerImpl(const ATN& atn, misc::IntervalSet& look, bool seeThruPreds, bool addEOF) : _atn(atn), _look(look), _seeThruPreds(seeThruPreds), _addEOF(addEOF) {}
/// <summary>
/// Compute set of tokens that can follow {@code s} in the ATN in the
/// specified {@code ctx}.
/// <p/>
/// If {@code ctx} is {@code null} and {@code stopState} or the end of the
/// rule containing {@code s} is reached, <seealso cref="Token#EPSILON"/> is added to
/// the result set. If {@code ctx} is not {@code null} and {@code addEOF} is
/// {@code true} and {@code stopState} or the end of the outermost rule is
/// reached, <seealso cref="Token#EOF"/> is added to the result set.
/// </summary>
/// <param name="s"> the ATN state. </param>
/// <param name="stopState"> the ATN state to stop at. This can be a
/// <seealso cref="BlockEndState"/> to detect epsilon paths through a closure. </param>
/// <param name="ctx"> The outer context, or {@code null} if the outer context should
/// not be used. </param>
/// <param name="look"> The result lookahead set. </param>
/// <param name="lookBusy"> A set used for preventing epsilon closures in the ATN
/// from causing a stack overflow. Outside code should pass
/// {@code new HashSet<ATNConfig>} for this argument. </param>
/// <param name="calledRuleStack"> A set used for preventing left recursion in the
/// ATN from causing a stack overflow. Outside code should pass
/// {@code new BitSet()} for this argument. </param>
/// <param name="seeThruPreds"> {@code true} to true semantic predicates as
/// implicitly {@code true} and "see through them", otherwise {@code false}
/// to treat semantic predicates as opaque and add <seealso cref="#HIT_PRED"/> to the
/// result if one is encountered. </param>
/// <param name="addEOF"> Add <seealso cref="Token#EOF"/> to the result if the end of the
/// outermost context is reached. This parameter has no effect if {@code ctx}
/// is {@code null}. </param>
void LOOK(ATNState *s, ATNState *stopState, Ref<const PredictionContext> const& ctx) {
if (!_lookBusy.insert(ATNConfig(s, 0, ctx)).second) {
return;
}
// ml: s can never be null, hence no need to check if stopState is != null.
if (s == stopState) {
if (ctx == nullptr) {
_look.add(Token::EPSILON);
return;
} else if (ctx->isEmpty() && _addEOF) {
_look.add(Token::EOF);
return;
}
}
if (s->getStateType() == ATNStateType::RULE_STOP) {
if (ctx == nullptr) {
_look.add(Token::EPSILON);
return;
} else if (ctx->isEmpty() && _addEOF) {
_look.add(Token::EOF);
return;
}
if (ctx != PredictionContext::EMPTY) {
bool removed = _calledRuleStack.test(s->ruleIndex);
_calledRuleStack[s->ruleIndex] = false;
// run thru all possible stack tops in ctx
for (size_t i = 0; i < ctx->size(); i++) {
ATNState *returnState = _atn.states[ctx->getReturnState(i)];
LOOK(returnState, stopState, ctx->getParent(i));
}
if (removed) {
_calledRuleStack.set(s->ruleIndex);
}
return;
}
}
size_t n = s->transitions.size();
for (size_t i = 0; i < n; i++) {
const Transition *t = s->transitions[i].get();
const auto tType = t->getTransitionType();
if (tType == TransitionType::RULE) {
if (_calledRuleStack[(static_cast<const RuleTransition*>(t))->target->ruleIndex]) {
continue;
}
Ref<const PredictionContext> newContext = SingletonPredictionContext::create(ctx, (static_cast<const RuleTransition*>(t))->followState->stateNumber);
_calledRuleStack.set((static_cast<const RuleTransition*>(t))->target->ruleIndex);
LOOK(t->target, stopState, newContext);
_calledRuleStack[(static_cast<const RuleTransition*>(t))->target->ruleIndex] = false;
} else if (tType == TransitionType::PREDICATE || tType == TransitionType::PRECEDENCE) {
if (_seeThruPreds) {
LOOK(t->target, stopState, ctx);
} else {
_look.add(LL1Analyzer::HIT_PRED);
}
} else if (t->isEpsilon()) {
LOOK(t->target, stopState, ctx);
} else if (tType == TransitionType::WILDCARD) {
_look.addAll(misc::IntervalSet::of(Token::MIN_USER_TOKEN_TYPE, static_cast<ssize_t>(_atn.maxTokenType)));
} else {
misc::IntervalSet set = t->label();
if (!set.isEmpty()) {
if (tType == TransitionType::NOT_SET) {
set = set.complement(misc::IntervalSet::of(Token::MIN_USER_TOKEN_TYPE, static_cast<ssize_t>(_atn.maxTokenType)));
}
_look.addAll(set);
}
}
}
}
private:
const ATN& _atn;
misc::IntervalSet& _look;
antlrcpp::BitSet _calledRuleStack;
std::unordered_set<ATNConfig, ATNConfigHasher, ATNConfigComparer> _lookBusy;
bool _seeThruPreds;
bool _addEOF;
};
}
std::vector<misc::IntervalSet> LL1Analyzer::getDecisionLookahead(ATNState *s) const {
std::vector<misc::IntervalSet> look;
if (s == nullptr) {
return look;
}
look.resize(s->transitions.size()); // Fills all interval sets with defaults.
for (size_t alt = 0; alt < s->transitions.size(); alt++) {
LL1AnalyzerImpl impl(_atn, look[alt], false, false);
impl.LOOK(s->transitions[alt]->target, nullptr, PredictionContext::EMPTY);
// Wipe out lookahead for this alternative if we found nothing
// or we had a predicate when we !seeThruPreds
if (look[alt].size() == 0 || look[alt].contains(LL1Analyzer::HIT_PRED)) {
look[alt].clear();
}
}
return look;
}
misc::IntervalSet LL1Analyzer::LOOK(ATNState *s, RuleContext *ctx) const {
return LOOK(s, nullptr, ctx);
}
misc::IntervalSet LL1Analyzer::LOOK(ATNState *s, ATNState *stopState, RuleContext *ctx) const {
Ref<const PredictionContext> lookContext = ctx != nullptr ? PredictionContext::fromRuleContext(_atn, ctx) : nullptr;
misc::IntervalSet r;
LL1AnalyzerImpl impl(_atn, r, true, true);
impl.LOOK(s, stopState, lookContext);
return r;
}
|
