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