gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/Parser.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/ATNDeserializationOptions.h"
   7 #include "tree/pattern/ParseTreePatternMatcher.h"
   8 #include "dfa/DFA.h"
   9 #include "ParserRuleContext.h"
  10 #include "tree/TerminalNode.h"
  11 #include "tree/ErrorNodeImpl.h"
  12 #include "Lexer.h"
  13 #include "atn/ParserATNSimulator.h"
  14 #include "misc/IntervalSet.h"
  15 #include "atn/RuleStartState.h"
  16 #include "DefaultErrorStrategy.h"
  17 #include "atn/ATNDeserializer.h"
  18 #include "atn/RuleTransition.h"
  19 #include "atn/ATN.h"
  20 #include "Exceptions.h"
  21 #include "ANTLRErrorListener.h"
  22 #include "tree/pattern/ParseTreePattern.h"
  23
  24 #include "atn/ProfilingATNSimulator.h"
  25 #include "atn/ParseInfo.h"
  26
  27 #include "Parser.h"
  28
  29 using namespace antlr4;
  30 using namespace antlr4::atn;
  31
  32 using namespace antlrcpp;
  33
  34 std::map<std::vector<uint16_t>, atn::ATN> Parser::bypassAltsAtnCache;
  35
  36 Parser::TraceListener::TraceListener(Parser *outerInstance_) : outerInstance(outerInstance_) {
  37 }
  38
  39 Parser::TraceListener::~TraceListener() {
  40 }
  41
  42 void Parser::TraceListener::enterEveryRule(ParserRuleContext *ctx) {
  43   std::cout << "enter   " << outerInstance->getRuleNames()[ctx->getRuleIndex()]
  44     << ", LT(1)=" << outerInstance->_input->LT(1)->getText() << std::endl;
  45 }
  46
  47 void Parser::TraceListener::visitTerminal(tree::TerminalNode *node) {
  48   std::cout << "consume " << node->getSymbol() << " rule "
  49     << outerInstance->getRuleNames()[outerInstance->getContext()->getRuleIndex()] << std::endl;
  50 }
  51
  52 void Parser::TraceListener::visitErrorNode(tree::ErrorNode * /*node*/) {
  53 }
  54
  55 void Parser::TraceListener::exitEveryRule(ParserRuleContext *ctx) {
  56   std::cout << "exit    " << outerInstance->getRuleNames()[ctx->getRuleIndex()]
  57     << ", LT(1)=" << outerInstance->_input->LT(1)->getText() << std::endl;
  58 }
  59
  60 Parser::TrimToSizeListener Parser::TrimToSizeListener::INSTANCE;
  61
  62 Parser::TrimToSizeListener::~TrimToSizeListener() {
  63 }
  64
  65 void Parser::TrimToSizeListener::enterEveryRule(ParserRuleContext * /*ctx*/) {
  66 }
  67
  68 void Parser::TrimToSizeListener::visitTerminal(tree::TerminalNode * /*node*/) {
  69 }
  70
  71 void Parser::TrimToSizeListener::visitErrorNode(tree::ErrorNode * /*node*/) {
  72 }
  73
  74 void Parser::TrimToSizeListener::exitEveryRule(ParserRuleContext * ctx) {
  75   ctx->children.shrink_to_fit();
  76 }
  77
  78 Parser::Parser(TokenStream *input) {
  79   InitializeInstanceFields();
  80   setInputStream(input);
  81 }
  82
  83 Parser::~Parser() {
  84   _tracker.reset();
  85   delete _tracer;
  86 }
  87
  88 void Parser::reset() {
  89   if (getInputStream() != nullptr) {
  90     getInputStream()->seek(0);
  91   }
  92   _errHandler->reset(this); // Watch out, this is not shared_ptr.reset().
  93
  94   _matchedEOF = false;
  95   _syntaxErrors = 0;
  96   setTrace(false);
  97   _precedenceStack.clear();
  98   _precedenceStack.push_back(0);
  99   _ctx = nullptr;
 100   _tracker.reset();
 101
 102   atn::ATNSimulator *interpreter = getInterpreter<atn::ParserATNSimulator>();
 103   if (interpreter != nullptr) {
 104     interpreter->reset();
 105   }
 106 }
 107
 108 Token* Parser::match(size_t ttype) {
 109   Token *t = getCurrentToken();
 110   if (t->getType() == ttype) {
 111     if (ttype == EOF) {
 112       _matchedEOF = true;
 113     }
 114     _errHandler->reportMatch(this);
 115     consume();
 116   } else {
 117     t = _errHandler->recoverInline(this);
 118     if (_buildParseTrees && t->getTokenIndex() == INVALID_INDEX) {
 119       // we must have conjured up a new token during single token insertion
 120       // if it's not the current symbol
 121       _ctx->addChild(createErrorNode(t));
 122     }
 123   }
 124   return t;
 125 }
 126
 127 Token* Parser::matchWildcard() {
 128   Token *t = getCurrentToken();
 129   if (t->getType() > 0) {
 130     _errHandler->reportMatch(this);
 131     consume();
 132   } else {
 133     t = _errHandler->recoverInline(this);
 134     if (_buildParseTrees && t->getTokenIndex() == INVALID_INDEX) {
 135       // we must have conjured up a new token during single token insertion
 136       // if it's not the current symbol
 137       _ctx->addChild(createErrorNode(t));
 138     }
 139   }
 140
 141   return t;
 142 }
 143
 144 void Parser::setBuildParseTree(bool buildParseTrees) {
 145   this->_buildParseTrees = buildParseTrees;
 146 }
 147
 148 bool Parser::getBuildParseTree() {
 149   return _buildParseTrees;
 150 }
 151
 152 void Parser::setTrimParseTree(bool trimParseTrees) {
 153   if (trimParseTrees) {
 154     if (getTrimParseTree()) {
 155       return;
 156     }
 157     addParseListener(&TrimToSizeListener::INSTANCE);
 158   } else {
 159     removeParseListener(&TrimToSizeListener::INSTANCE);
 160   }
 161 }
 162
 163 bool Parser::getTrimParseTree() {
 164   return std::find(getParseListeners().begin(), getParseListeners().end(), &TrimToSizeListener::INSTANCE) != getParseListeners().end();
 165 }
 166
 167 std::vector<tree::ParseTreeListener *> Parser::getParseListeners() {
 168   return _parseListeners;
 169 }
 170
 171 void Parser::addParseListener(tree::ParseTreeListener *listener) {
 172   if (!listener) {
 173     throw NullPointerException("listener");
 174   }
 175
 176   this->_parseListeners.push_back(listener);
 177 }
 178
 179 void Parser::removeParseListener(tree::ParseTreeListener *listener) {
 180   if (!_parseListeners.empty()) {
 181     auto it = std::find(_parseListeners.begin(), _parseListeners.end(), listener);
 182     if (it != _parseListeners.end()) {
 183       _parseListeners.erase(it);
 184     }
 185   }
 186 }
 187
 188 void Parser::removeParseListeners() {
 189   _parseListeners.clear();
 190 }
 191
 192 void Parser::triggerEnterRuleEvent() {
 193   for (auto *listener : _parseListeners) {
 194     listener->enterEveryRule(_ctx);
 195     _ctx->enterRule(listener);
 196   }
 197 }
 198
 199 void Parser::triggerExitRuleEvent() {
 200   // reverse order walk of listeners
 201   for (auto it = _parseListeners.rbegin(); it != _parseListeners.rend(); ++it) {
 202     _ctx->exitRule(*it);
 203     (*it)->exitEveryRule(_ctx);
 204   }
 205 }
 206
 207 size_t Parser::getNumberOfSyntaxErrors() {
 208   return _syntaxErrors;
 209 }
 210
 211 TokenFactory<CommonToken>* Parser::getTokenFactory() {
 212   return _input->getTokenSource()->getTokenFactory();
 213 }
 214
 215
 216 const atn::ATN& Parser::getATNWithBypassAlts() {
 217   std::vector<uint16_t> serializedAtn = getSerializedATN();
 218   if (serializedAtn.empty()) {
 219     throw UnsupportedOperationException("The current parser does not support an ATN with bypass alternatives.");
 220   }
 221
 222   std::lock_guard<std::mutex> lck(_mutex);
 223
 224   // XXX: using the entire serialized ATN as key into the map is a big resource waste.
 225   //      How large can that thing become?
 226   if (bypassAltsAtnCache.find(serializedAtn) == bypassAltsAtnCache.end())
 227   {
 228     atn::ATNDeserializationOptions deserializationOptions;
 229     deserializationOptions.setGenerateRuleBypassTransitions(true);
 230
 231     atn::ATNDeserializer deserializer(deserializationOptions);
 232     bypassAltsAtnCache[serializedAtn] = deserializer.deserialize(serializedAtn);
 233   }
 234
 235   return bypassAltsAtnCache[serializedAtn];
 236 }
 237
 238 tree::pattern::ParseTreePattern Parser::compileParseTreePattern(const std::string &pattern, int patternRuleIndex) {
 239   if (getTokenStream() != nullptr) {
 240     TokenSource *tokenSource = getTokenStream()->getTokenSource();
 241     if (is<Lexer*>(tokenSource)) {
 242       Lexer *lexer = dynamic_cast<Lexer *>(tokenSource);
 243       return compileParseTreePattern(pattern, patternRuleIndex, lexer);
 244     }
 245   }
 246   throw UnsupportedOperationException("Parser can't discover a lexer to use");
 247 }
 248
 249 tree::pattern::ParseTreePattern Parser::compileParseTreePattern(const std::string &pattern, int patternRuleIndex,
 250   Lexer *lexer) {
 251   tree::pattern::ParseTreePatternMatcher m(lexer, this);
 252   return m.compile(pattern, patternRuleIndex);
 253 }
 254
 255 Ref<ANTLRErrorStrategy> Parser::getErrorHandler() {
 256   return _errHandler;
 257 }
 258
 259 void Parser::setErrorHandler(Ref<ANTLRErrorStrategy> const& handler) {
 260   _errHandler = handler;
 261 }
 262
 263 IntStream* Parser::getInputStream() {
 264   return getTokenStream();
 265 }
 266
 267 void Parser::setInputStream(IntStream *input) {
 268   setTokenStream(static_cast<TokenStream*>(input));
 269 }
 270
 271 TokenStream* Parser::getTokenStream() {
 272   return _input;
 273 }
 274
 275 void Parser::setTokenStream(TokenStream *input) {
 276   _input = nullptr; // Just a reference we don't own.
 277   reset();
 278   _input = input;
 279 }
 280
 281 Token* Parser::getCurrentToken() {
 282   return _input->LT(1);
 283 }
 284
 285 void Parser::notifyErrorListeners(const std::string &msg) {
 286   notifyErrorListeners(getCurrentToken(), msg, nullptr);
 287 }
 288
 289 void Parser::notifyErrorListeners(Token *offendingToken, const std::string &msg, std::exception_ptr e) {
 290   _syntaxErrors++;
 291   size_t line = offendingToken->getLine();
 292   size_t charPositionInLine = offendingToken->getCharPositionInLine();
 293
 294   ProxyErrorListener &listener = getErrorListenerDispatch();
 295   listener.syntaxError(this, offendingToken, line, charPositionInLine, msg, e);
 296 }
 297
 298 Token* Parser::consume() {
 299   Token *o = getCurrentToken();
 300   if (o->getType() != EOF) {
 301     getInputStream()->consume();
 302   }
 303
 304   bool hasListener = _parseListeners.size() > 0 && !_parseListeners.empty();
 305   if (_buildParseTrees || hasListener) {
 306     if (_errHandler->inErrorRecoveryMode(this)) {
 307       tree::ErrorNode *node = createErrorNode(o);
 308       _ctx->addChild(node);
 309       if (_parseListeners.size() > 0) {
 310         for (auto *listener : _parseListeners) {
 311           listener->visitErrorNode(node);
 312         }
 313       }
 314     } else {
 315       tree::TerminalNode *node = _ctx->addChild(createTerminalNode(o));
 316       if (_parseListeners.size() > 0) {
 317         for (auto *listener : _parseListeners) {
 318           listener->visitTerminal(node);
 319         }
 320       }
 321     }
 322   }
 323   return o;
 324 }
 325
 326 void Parser::addContextToParseTree() {
 327   // Add current context to parent if we have a parent.
 328   if (_ctx->parent == nullptr)
 329     return;
 330
 331   ParserRuleContext *parent = dynamic_cast<ParserRuleContext *>(_ctx->parent);
 332   parent->addChild(_ctx);
 333 }
 334
 335 void Parser::enterRule(ParserRuleContext *localctx, size_t state, size_t /*ruleIndex*/) {
 336   setState(state);
 337   _ctx = localctx;
 338   _ctx->start = _input->LT(1);
 339   if (_buildParseTrees) {
 340     addContextToParseTree();
 341   }
 342   if (_parseListeners.size() > 0) {
 343     triggerEnterRuleEvent();
 344   }
 345 }
 346
 347 void Parser::exitRule() {
 348   if (_matchedEOF) {
 349     // if we have matched EOF, it cannot consume past EOF so we use LT(1) here
 350     _ctx->stop = _input->LT(1); // LT(1) will be end of file
 351   } else {
 352     _ctx->stop = _input->LT(-1); // stop node is what we just matched
 353   }
 354
 355   // trigger event on ctx, before it reverts to parent
 356   if (_parseListeners.size() > 0) {
 357     triggerExitRuleEvent();
 358   }
 359   setState(_ctx->invokingState);
 360   _ctx = dynamic_cast<ParserRuleContext *>(_ctx->parent);
 361 }
 362
 363 void Parser::enterOuterAlt(ParserRuleContext *localctx, size_t altNum) {
 364   localctx->setAltNumber(altNum);
 365
 366   // if we have new localctx, make sure we replace existing ctx
 367   // that is previous child of parse tree
 368   if (_buildParseTrees && _ctx != localctx) {
 369     if (_ctx->parent != nullptr) {
 370       ParserRuleContext *parent = dynamic_cast<ParserRuleContext *>(_ctx->parent);
 371       parent->removeLastChild();
 372       parent->addChild(localctx);
 373     }
 374   }
 375   _ctx = localctx;
 376 }
 377
 378 int Parser::getPrecedence() const {
 379   if (_precedenceStack.empty()) {
 380     return -1;
 381   }
 382
 383   return _precedenceStack.back();
 384 }
 385
 386 void Parser::enterRecursionRule(ParserRuleContext *localctx, size_t ruleIndex) {
 387   enterRecursionRule(localctx, getATN().ruleToStartState[ruleIndex]->stateNumber, ruleIndex, 0);
 388 }
 389
 390 void Parser::enterRecursionRule(ParserRuleContext *localctx, size_t state, size_t /*ruleIndex*/, int precedence) {
 391   setState(state);
 392   _precedenceStack.push_back(precedence);
 393   _ctx = localctx;
 394   _ctx->start = _input->LT(1);
 395   if (!_parseListeners.empty()) {
 396     triggerEnterRuleEvent(); // simulates rule entry for left-recursive rules
 397   }
 398 }
 399
 400 void Parser::pushNewRecursionContext(ParserRuleContext *localctx, size_t state, size_t /*ruleIndex*/) {
 401   ParserRuleContext *previous = _ctx;
 402   previous->parent = localctx;
 403   previous->invokingState = state;
 404   previous->stop = _input->LT(-1);
 405
 406   _ctx = localctx;
 407   _ctx->start = previous->start;
 408   if (_buildParseTrees) {
 409     _ctx->addChild(previous);
 410   }
 411
 412   if (_parseListeners.size() > 0) {
 413     triggerEnterRuleEvent(); // simulates rule entry for left-recursive rules
 414   }
 415 }
 416
 417 void Parser::unrollRecursionContexts(ParserRuleContext *parentctx) {
 418   _precedenceStack.pop_back();
 419   _ctx->stop = _input->LT(-1);
 420   ParserRuleContext *retctx = _ctx; // save current ctx (return value)
 421
 422   // unroll so ctx is as it was before call to recursive method
 423   if (_parseListeners.size() > 0) {
 424     while (_ctx != parentctx) {
 425       triggerExitRuleEvent();
 426       _ctx = dynamic_cast<ParserRuleContext *>(_ctx->parent);
 427     }
 428   } else {
 429     _ctx = parentctx;
 430   }
 431
 432   // hook into tree
 433   retctx->parent = parentctx;
 434
 435   if (_buildParseTrees && parentctx != nullptr) {
 436     // add return ctx into invoking rule's tree
 437     parentctx->addChild(retctx);
 438   }
 439 }
 440
 441 ParserRuleContext* Parser::getInvokingContext(size_t ruleIndex) {
 442   ParserRuleContext *p = _ctx;
 443   while (p) {
 444     if (p->getRuleIndex() == ruleIndex) {
 445       return p;
 446     }
 447     if (p->parent == nullptr)
 448       break;
 449     p = dynamic_cast<ParserRuleContext *>(p->parent);
 450   }
 451   return nullptr;
 452 }
 453
 454 ParserRuleContext* Parser::getContext() {
 455   return _ctx;
 456 }
 457
 458 void Parser::setContext(ParserRuleContext *ctx) {
 459   _ctx = ctx;
 460 }
 461
 462 bool Parser::precpred(RuleContext * /*localctx*/, int precedence) {
 463   return precedence >= _precedenceStack.back();
 464 }
 465
 466 bool Parser::inContext(const std::string &/*context*/) {
 467   // TODO: useful in parser?
 468   return false;
 469 }
 470
 471 bool Parser::isExpectedToken(size_t symbol) {
 472   const atn::ATN &atn = getInterpreter<atn::ParserATNSimulator>()->atn;
 473   ParserRuleContext *ctx = _ctx;
 474   atn::ATNState *s = atn.states[getState()];
 475   misc::IntervalSet following = atn.nextTokens(s);
 476
 477   if (following.contains(symbol)) {
 478     return true;
 479   }
 480
 481   if (!following.contains(Token::EPSILON)) {
 482     return false;
 483   }
 484
 485   while (ctx && ctx->invokingState != ATNState::INVALID_STATE_NUMBER && following.contains(Token::EPSILON)) {
 486     atn::ATNState *invokingState = atn.states[ctx->invokingState];
 487     atn::RuleTransition *rt = static_cast<atn::RuleTransition*>(invokingState->transitions[0]);
 488     following = atn.nextTokens(rt->followState);
 489     if (following.contains(symbol)) {
 490       return true;
 491     }
 492
 493     ctx = dynamic_cast<ParserRuleContext *>(ctx->parent);
 494   }
 495
 496   if (following.contains(Token::EPSILON) && symbol == EOF) {
 497     return true;
 498   }
 499
 500   return false;
 501 }
 502
 503 bool Parser::isMatchedEOF() const {
 504   return _matchedEOF;
 505 }
 506
 507 misc::IntervalSet Parser::getExpectedTokens() {
 508   return getATN().getExpectedTokens(getState(), getContext());
 509 }
 510
 511 misc::IntervalSet Parser::getExpectedTokensWithinCurrentRule() {
 512   const atn::ATN &atn = getInterpreter<atn::ParserATNSimulator>()->atn;
 513   atn::ATNState *s = atn.states[getState()];
 514   return atn.nextTokens(s);
 515 }
 516
 517 size_t Parser::getRuleIndex(const std::string &ruleName) {
 518   const std::map<std::string, size_t> &m = getRuleIndexMap();
 519   auto iterator = m.find(ruleName);
 520   if (iterator == m.end()) {
 521     return INVALID_INDEX;
 522   }
 523   return iterator->second;
 524 }
 525
 526 ParserRuleContext* Parser::getRuleContext() {
 527   return _ctx;
 528 }
 529
 530 std::vector<std::string> Parser::getRuleInvocationStack() {
 531   return getRuleInvocationStack(_ctx);
 532 }
 533
 534 std::vector<std::string> Parser::getRuleInvocationStack(RuleContext *p) {
 535   std::vector<std::string> const& ruleNames = getRuleNames();
 536   std::vector<std::string> stack;
 537   RuleContext *run = p;
 538   while (run != nullptr) {
 539     // compute what follows who invoked us
 540     size_t ruleIndex = run->getRuleIndex();
 541     if (ruleIndex == INVALID_INDEX ) {
 542       stack.push_back("n/a");
 543     } else {
 544       stack.push_back(ruleNames[ruleIndex]);
 545     }
 546     if (p->parent == nullptr)
 547       break;
 548     run = dynamic_cast<RuleContext *>(run->parent);
 549   }
 550   return stack;
 551 }
 552
 553 std::vector<std::string> Parser::getDFAStrings() {
 554   atn::ParserATNSimulator *simulator = getInterpreter<atn::ParserATNSimulator>();
 555   if (!simulator->decisionToDFA.empty()) {
 556     std::lock_guard<std::mutex> lck(_mutex);
 557
 558     std::vector<std::string> s;
 559     for (size_t d = 0; d < simulator->decisionToDFA.size(); d++) {
 560       dfa::DFA &dfa = simulator->decisionToDFA[d];
 561       s.push_back(dfa.toString(getVocabulary()));
 562     }
 563     return s;
 564   }
 565   return std::vector<std::string>();
 566 }
 567
 568 void Parser::dumpDFA() {
 569   atn::ParserATNSimulator *simulator = getInterpreter<atn::ParserATNSimulator>();
 570   if (!simulator->decisionToDFA.empty()) {
 571     std::lock_guard<std::mutex> lck(_mutex);
 572     bool seenOne = false;
 573     for (size_t d = 0; d < simulator->decisionToDFA.size(); d++) {
 574       dfa::DFA &dfa = simulator->decisionToDFA[d];
 575       if (!dfa.states.empty()) {
 576         if (seenOne) {
 577           std::cout << std::endl;
 578         }
 579         std::cout << "Decision " << dfa.decision << ":" << std::endl;
 580         std::cout << dfa.toString(getVocabulary());
 581         seenOne = true;
 582       }
 583     }
 584   }
 585 }
 586
 587 std::string Parser::getSourceName() {
 588   return _input->getSourceName();
 589 }
 590
 591 atn::ParseInfo Parser::getParseInfo() const {
 592   atn::ProfilingATNSimulator *interp = getInterpreter<atn::ProfilingATNSimulator>();
 593   return atn::ParseInfo(interp);
 594 }
 595
 596 void Parser::setProfile(bool profile) {
 597   atn::ParserATNSimulator *interp = getInterpreter<atn::ProfilingATNSimulator>();
 598   atn::PredictionMode saveMode = interp != nullptr ? interp->getPredictionMode() : atn::PredictionMode::LL;
 599   if (profile) {
 600     if (!is<atn::ProfilingATNSimulator *>(interp)) {
 601       setInterpreter(new atn::ProfilingATNSimulator(this)); /* mem-check: replacing existing interpreter which gets deleted. */
 602     }
 603   } else if (is<atn::ProfilingATNSimulator *>(interp)) {
 604     /* mem-check: replacing existing interpreter which gets deleted. */
 605     atn::ParserATNSimulator *sim = new atn::ParserATNSimulator(this, getATN(), interp->decisionToDFA, interp->getSharedContextCache());
 606     setInterpreter(sim);
 607   }
 608   getInterpreter<atn::ParserATNSimulator>()->setPredictionMode(saveMode);
 609 }
 610
 611 void Parser::setTrace(bool trace) {
 612   if (!trace) {
 613     if (_tracer)
 614       removeParseListener(_tracer);
 615     delete _tracer;
 616     _tracer = nullptr;
 617   } else {
 618     if (_tracer)
 619       removeParseListener(_tracer); // Just in case this is triggered multiple times.
 620     _tracer = new TraceListener(this);
 621     addParseListener(_tracer);
 622   }
 623 }
 624
 625 bool Parser::isTrace() const {
 626   return _tracer != nullptr;
 627 }
 628
 629 tree::TerminalNode *Parser::createTerminalNode(Token *t) {
 630   return _tracker.createInstance<tree::TerminalNodeImpl>(t);
 631 }
 632
 633 tree::ErrorNode *Parser::createErrorNode(Token *t) {
 634   return _tracker.createInstance<tree::ErrorNodeImpl>(t);
 635 }
 636
 637 void Parser::InitializeInstanceFields() {
 638   _errHandler = std::make_shared<DefaultErrorStrategy>();
 639   _precedenceStack.clear();
 640   _precedenceStack.push_back(0);
 641   _buildParseTrees = true;
 642   _syntaxErrors = 0;
 643   _matchedEOF = false;
 644   _input = nullptr;
 645   _tracer = nullptr;
 646   _ctx = nullptr;
 647 }
 648