gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/atn/LL1Analyzer.cpp

   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
  25 LL1Analyzer::LL1Analyzer(const ATN &atn) : _atn(atn) {
  26 }
  27
  28 LL1Analyzer::~LL1Analyzer() {
  29 }
  30
  31 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
  56 misc::IntervalSet LL1Analyzer::LOOK(ATNState *s, RuleContext *ctx) const {
  57   return LOOK(s, nullptr, ctx);
  58 }
  59
  60 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
  72 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       bool removed = calledRuleStack.test(s->ruleIndex);
 104       calledRuleStack[s->ruleIndex] = false;
 105        auto onExit = finally([removed, &calledRuleStack, s] {
 106                 if (removed) {
 107                   calledRuleStack.set(s->ruleIndex);
 108                 }
 109               });
 110        // run thru all possible stack tops in ctx
 111       for (size_t i = 0; i < ctx->size(); i++) {
 112         ATNState *returnState = _atn.states[ctx->getReturnState(i)];
 113         _LOOK(returnState, stopState, ctx->getParent(i), look, lookBusy, calledRuleStack, seeThruPreds, addEOF);
 114       }
 115       return;
 116     }
 117   }
 118
 119   size_t n = s->transitions.size();
 120   for (size_t i = 0; i < n; i++) {
 121     Transition *t = s->transitions[i];
 122
 123     if (t->getSerializationType() == Transition::RULE) {
 124       if (calledRuleStack[(static_cast<RuleTransition*>(t))->target->ruleIndex]) {
 125         continue;
 126       }
 127
 128       Ref<PredictionContext> newContext = SingletonPredictionContext::create(ctx, (static_cast<RuleTransition*>(t))->followState->stateNumber);
 129       auto onExit = finally([t, &calledRuleStack] {
 130         calledRuleStack[(static_cast<RuleTransition*>(t))->target->ruleIndex] = false;
 131       });
 132
 133       calledRuleStack.set((static_cast<RuleTransition*>(t))->target->ruleIndex);
 134       _LOOK(t->target, stopState, newContext, look, lookBusy, calledRuleStack, seeThruPreds, addEOF);
 135
 136     } else if (is<AbstractPredicateTransition *>(t)) {
 137       if (seeThruPreds) {
 138         _LOOK(t->target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF);
 139       } else {
 140         look.add(HIT_PRED);
 141       }
 142     } else if (t->isEpsilon()) {
 143       _LOOK(t->target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF);
 144     } else if (t->getSerializationType() == Transition::WILDCARD) {
 145       look.addAll(misc::IntervalSet::of(Token::MIN_USER_TOKEN_TYPE, static_cast<ssize_t>(_atn.maxTokenType)));
 146     } else {
 147       misc::IntervalSet set = t->label();
 148       if (!set.isEmpty()) {
 149         if (is<NotSetTransition*>(t)) {
 150           set = set.complement(misc::IntervalSet::of(Token::MIN_USER_TOKEN_TYPE, static_cast<ssize_t>(_atn.maxTokenType)));
 151         }
 152         look.addAll(set);
 153       }
 154     }
 155   }
 156 }