1 /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
2 * Use of this file is governed by the BSD 3-clause license that
3 * can be found in the LICENSE.txt file in the project root.
4 */
5
6 #include "atn/ATNConfig.h"
7 #include "atn/AbstractPredicateTransition.h"
8 #include "atn/EmptyPredictionContext.h"
9 #include "atn/NotSetTransition.h"
10 #include "atn/RuleStopState.h"
11 #include "atn/RuleTransition.h"
12 #include "atn/SingletonPredictionContext.h"
13 #include "atn/Transition.h"
14 #include "atn/WildcardTransition.h"
15 #include "misc/IntervalSet.h"
16
17 #include "support/CPPUtils.h"
18
19 #include "atn/LL1Analyzer.h"
20
21 using namespace antlr4;
22 using namespace antlr4::atn;
23 using namespace antlrcpp;
24
LL1Analyzer(const ATN & atn)25 LL1Analyzer::LL1Analyzer(const ATN& atn) : _atn(atn) {}
26
~LL1Analyzer()27 LL1Analyzer::~LL1Analyzer() {}
28
getDecisionLookahead(ATNState * s) const29 std::vector<misc::IntervalSet> LL1Analyzer::getDecisionLookahead(
30 ATNState* s) const {
31 std::vector<misc::IntervalSet> look;
32
33 if (s == nullptr) {
34 return look;
35 }
36
37 look.resize(s->transitions.size()); // Fills all interval sets with defaults.
38 for (size_t alt = 0; alt < s->transitions.size(); alt++) {
39 bool seeThruPreds = false; // fail to get lookahead upon pred
40
41 ATNConfig::Set lookBusy;
42 antlrcpp::BitSet callRuleStack;
43 _LOOK(s->transitions[alt]->target, nullptr, PredictionContext::EMPTY,
44 look[alt], lookBusy, callRuleStack, seeThruPreds, false);
45
46 // Wipe out lookahead for this alternative if we found nothing
47 // or we had a predicate when we !seeThruPreds
48 if (look[alt].size() == 0 || look[alt].contains(HIT_PRED)) {
49 look[alt].clear();
50 }
51 }
52 return look;
53 }
54
LOOK(ATNState * s,RuleContext * ctx) const55 misc::IntervalSet LL1Analyzer::LOOK(ATNState* s, RuleContext* ctx) const {
56 return LOOK(s, nullptr, ctx);
57 }
58
LOOK(ATNState * s,ATNState * stopState,RuleContext * ctx) const59 misc::IntervalSet LL1Analyzer::LOOK(ATNState* s, ATNState* stopState,
60 RuleContext* ctx) const {
61 misc::IntervalSet r;
62 bool seeThruPreds = true; // ignore preds; get all lookahead
63 Ref<PredictionContext> lookContext =
64 ctx != nullptr ? PredictionContext::fromRuleContext(_atn, ctx) : nullptr;
65
66 ATNConfig::Set lookBusy;
67 antlrcpp::BitSet callRuleStack;
68 _LOOK(s, stopState, lookContext, r, lookBusy, callRuleStack, seeThruPreds,
69 true);
70
71 return r;
72 }
73
_LOOK(ATNState * s,ATNState * stopState,Ref<PredictionContext> const & ctx,misc::IntervalSet & look,ATNConfig::Set & lookBusy,antlrcpp::BitSet & calledRuleStack,bool seeThruPreds,bool addEOF) const74 void LL1Analyzer::_LOOK(ATNState* s, ATNState* stopState,
75 Ref<PredictionContext> const& ctx,
76 misc::IntervalSet& look, ATNConfig::Set& lookBusy,
77 antlrcpp::BitSet& calledRuleStack, bool seeThruPreds,
78 bool addEOF) const {
79 Ref<ATNConfig> c = std::make_shared<ATNConfig>(s, 0, ctx);
80
81 if (lookBusy.count(c) > 0) // Keep in mind comparison is based on members of
82 // the class, not the actual instance.
83 return;
84
85 lookBusy.insert(c);
86
87 // ml: s can never be null, hence no need to check if stopState is != null.
88 if (s == stopState) {
89 if (ctx == nullptr) {
90 look.add(Token::EPSILON);
91 return;
92 } else if (ctx->isEmpty() && addEOF) {
93 look.add(Token::EOF);
94 return;
95 }
96 }
97
98 if (s->getStateType() == ATNState::RULE_STOP) {
99 if (ctx == nullptr) {
100 look.add(Token::EPSILON);
101 return;
102 } else if (ctx->isEmpty() && addEOF) {
103 look.add(Token::EOF);
104 return;
105 }
106
107 if (ctx != PredictionContext::EMPTY) {
108 // run thru all possible stack tops in ctx
109 for (size_t i = 0; i < ctx->size(); i++) {
110 ATNState* returnState = _atn.states[ctx->getReturnState(i)];
111
112 bool removed = calledRuleStack.test(returnState->ruleIndex);
113 auto onExit = finally([removed, &calledRuleStack, returnState] {
114 if (removed) {
115 calledRuleStack.set(returnState->ruleIndex);
116 }
117 });
118
119 calledRuleStack[returnState->ruleIndex] = false;
120 _LOOK(returnState, stopState, ctx->getParent(i), look, lookBusy,
121 calledRuleStack, seeThruPreds, addEOF);
122 }
123 return;
124 }
125 }
126
127 size_t n = s->transitions.size();
128 for (size_t i = 0; i < n; i++) {
129 Transition* t = s->transitions[i];
130
131 if (t->getSerializationType() == Transition::RULE) {
132 if (calledRuleStack[(static_cast<RuleTransition*>(t))
133 ->target->ruleIndex]) {
134 continue;
135 }
136
137 Ref<PredictionContext> newContext = SingletonPredictionContext::create(
138 ctx, (static_cast<RuleTransition*>(t))->followState->stateNumber);
139 auto onExit = finally([t, &calledRuleStack] {
140 calledRuleStack[(static_cast<RuleTransition*>(t))->target->ruleIndex] =
141 false;
142 });
143
144 calledRuleStack.set((static_cast<RuleTransition*>(t))->target->ruleIndex);
145 _LOOK(t->target, stopState, newContext, look, lookBusy, calledRuleStack,
146 seeThruPreds, addEOF);
147
148 } else if (is<AbstractPredicateTransition*>(t)) {
149 if (seeThruPreds) {
150 _LOOK(t->target, stopState, ctx, look, lookBusy, calledRuleStack,
151 seeThruPreds, addEOF);
152 } else {
153 look.add(HIT_PRED);
154 }
155 } else if (t->isEpsilon()) {
156 _LOOK(t->target, stopState, ctx, look, lookBusy, calledRuleStack,
157 seeThruPreds, addEOF);
158 } else if (t->getSerializationType() == Transition::WILDCARD) {
159 look.addAll(misc::IntervalSet::of(
160 Token::MIN_USER_TOKEN_TYPE, static_cast<ssize_t>(_atn.maxTokenType)));
161 } else {
162 misc::IntervalSet set = t->label();
163 if (!set.isEmpty()) {
164 if (is<NotSetTransition*>(t)) {
165 set = set.complement(
166 misc::IntervalSet::of(Token::MIN_USER_TOKEN_TYPE,
167 static_cast<ssize_t>(_atn.maxTokenType)));
168 }
169 look.addAll(set);
170 }
171 }
172 }
173 }
174