From 45409c781a9e35df68c43b1e2f028d30bf90c0a0 Mon Sep 17 00:00:00 2001 From: Patrick Schönberger Date: Wed, 28 Jul 2021 09:07:53 +0200 Subject: Initial commit --- .../install/include/antlr4-runtime/atn/ATN.h | 118 +++ .../install/include/antlr4-runtime/atn/ATNConfig.h | 154 ++++ .../include/antlr4-runtime/atn/ATNConfigSet.h | 110 +++ .../antlr4-runtime/atn/ATNDeserializationOptions.h | 50 ++ .../include/antlr4-runtime/atn/ATNDeserializer.h | 91 +++ .../include/antlr4-runtime/atn/ATNSerializer.h | 61 ++ .../include/antlr4-runtime/atn/ATNSimulator.h | 87 ++ .../install/include/antlr4-runtime/atn/ATNState.h | 140 ++++ .../install/include/antlr4-runtime/atn/ATNType.h | 20 + .../atn/AbstractPredicateTransition.h | 24 + .../include/antlr4-runtime/atn/ActionTransition.h | 33 + .../include/antlr4-runtime/atn/AmbiguityInfo.h | 68 ++ .../antlr4-runtime/atn/ArrayPredictionContext.h | 43 + .../include/antlr4-runtime/atn/AtomTransition.h | 30 + .../antlr4-runtime/atn/BasicBlockStartState.h | 22 + .../include/antlr4-runtime/atn/BasicState.h | 21 + .../include/antlr4-runtime/atn/BlockEndState.h | 24 + .../include/antlr4-runtime/atn/BlockStartState.h | 21 + .../antlr4-runtime/atn/ContextSensitivityInfo.h | 47 ++ .../include/antlr4-runtime/atn/DecisionEventInfo.h | 70 ++ .../include/antlr4-runtime/atn/DecisionInfo.h | 227 ++++++ .../include/antlr4-runtime/atn/DecisionState.h | 30 + .../antlr4-runtime/atn/EmptyPredictionContext.h | 27 + .../include/antlr4-runtime/atn/EpsilonTransition.h | 39 + .../install/include/antlr4-runtime/atn/ErrorInfo.h | 43 + .../include/antlr4-runtime/atn/LL1Analyzer.h | 115 +++ .../include/antlr4-runtime/atn/LexerATNConfig.h | 44 + .../include/antlr4-runtime/atn/LexerATNSimulator.h | 217 +++++ .../include/antlr4-runtime/atn/LexerAction.h | 66 ++ .../antlr4-runtime/atn/LexerActionExecutor.h | 115 +++ .../include/antlr4-runtime/atn/LexerActionType.h | 55 ++ .../antlr4-runtime/atn/LexerChannelAction.h | 63 ++ .../include/antlr4-runtime/atn/LexerCustomAction.h | 87 ++ .../antlr4-runtime/atn/LexerIndexedCustomAction.h | 82 ++ .../include/antlr4-runtime/atn/LexerModeAction.h | 61 ++ .../include/antlr4-runtime/atn/LexerMoreAction.h | 57 ++ .../antlr4-runtime/atn/LexerPopModeAction.h | 57 ++ .../antlr4-runtime/atn/LexerPushModeAction.h | 61 ++ .../include/antlr4-runtime/atn/LexerSkipAction.h | 55 ++ .../include/antlr4-runtime/atn/LexerTypeAction.h | 55 ++ .../antlr4-runtime/atn/LookaheadEventInfo.h | 42 + .../include/antlr4-runtime/atn/LoopEndState.h | 22 + .../include/antlr4-runtime/atn/NotSetTransition.h | 25 + .../antlr4-runtime/atn/OrderedATNConfigSet.h | 20 + .../install/include/antlr4-runtime/atn/ParseInfo.h | 102 +++ .../antlr4-runtime/atn/ParserATNSimulator.h | 904 +++++++++++++++++++++ .../antlr4-runtime/atn/PlusBlockStartState.h | 25 + .../include/antlr4-runtime/atn/PlusLoopbackState.h | 22 + .../atn/PrecedencePredicateTransition.h | 29 + .../include/antlr4-runtime/atn/PredicateEvalInfo.h | 62 ++ .../antlr4-runtime/atn/PredicateTransition.h | 39 + .../include/antlr4-runtime/atn/PredictionContext.h | 266 ++++++ .../include/antlr4-runtime/atn/PredictionMode.h | 436 ++++++++++ .../antlr4-runtime/atn/ProfilingATNSimulator.h | 60 ++ .../include/antlr4-runtime/atn/RangeTransition.h | 29 + .../include/antlr4-runtime/atn/RuleStartState.h | 25 + .../include/antlr4-runtime/atn/RuleStopState.h | 25 + .../include/antlr4-runtime/atn/RuleTransition.h | 40 + .../include/antlr4-runtime/atn/SemanticContext.h | 222 +++++ .../include/antlr4-runtime/atn/SetTransition.h | 30 + .../atn/SingletonPredictionContext.h | 36 + .../antlr4-runtime/atn/StarBlockStartState.h | 21 + .../antlr4-runtime/atn/StarLoopEntryState.h | 35 + .../include/antlr4-runtime/atn/StarLoopbackState.h | 21 + .../include/antlr4-runtime/atn/TokensStartState.h | 21 + .../include/antlr4-runtime/atn/Transition.h | 76 ++ .../antlr4-runtime/atn/WildcardTransition.h | 25 + 67 files changed, 5450 insertions(+) create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATN.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfig.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfigSet.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializationOptions.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializer.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSerializer.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSimulator.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNType.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AbstractPredicateTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ActionTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AmbiguityInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ArrayPredictionContext.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AtomTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicBlockStartState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockEndState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockStartState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ContextSensitivityInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionEventInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EmptyPredictionContext.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EpsilonTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ErrorInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LL1Analyzer.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNConfig.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNSimulator.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionExecutor.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionType.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerChannelAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerCustomAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerIndexedCustomAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerModeAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerMoreAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPopModeAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPushModeAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerSkipAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerTypeAction.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LookaheadEventInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LoopEndState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/NotSetTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/OrderedATNConfigSet.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParseInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParserATNSimulator.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusBlockStartState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusLoopbackState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PrecedencePredicateTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateEvalInfo.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionMode.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ProfilingATNSimulator.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RangeTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStartState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStopState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SemanticContext.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SetTransition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SingletonPredictionContext.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarBlockStartState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopEntryState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopbackState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/TokensStartState.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/Transition.h create mode 100644 antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/WildcardTransition.h (limited to 'antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn') diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATN.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATN.h new file mode 100644 index 0000000..125469b --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATN.h @@ -0,0 +1,118 @@ +/* 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. + */ + +#pragma once + +#include "RuleContext.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC ATN { + public: +#if __cplusplus >= 201703L + static constexpr size_t INVALID_ALT_NUMBER = 0; +#else + enum : size_t { + INVALID_ALT_NUMBER = 0, + }; +#endif + + /// Used for runtime deserialization of ATNs from strings. + ATN(); + ATN(ATN &&other); + ATN(ATNType grammarType, size_t maxTokenType); + virtual ~ATN(); + + std::vector states; + + /// Each subrule/rule is a decision point and we must track them so we + /// can go back later and build DFA predictors for them. This includes + /// all the rules, subrules, optional blocks, ()+, ()* etc... + std::vector decisionToState; + + /// Maps from rule index to starting state number. + std::vector ruleToStartState; + + /// Maps from rule index to stop state number. + std::vector ruleToStopState; + + /// The type of the ATN. + ATNType grammarType; + + /// The maximum value for any symbol recognized by a transition in the ATN. + size_t maxTokenType; + + /// + /// For lexer ATNs, this maps the rule index to the resulting token type. + /// For parser ATNs, this maps the rule index to the generated bypass token + /// type if the + /// + /// deserialization option was specified; otherwise, this is {@code null}. + /// + std::vector ruleToTokenType; + + /// For lexer ATNs, this is an array of {@link LexerAction} objects which may + /// be referenced by action transitions in the ATN. + std::vector> lexerActions; + + std::vector modeToStartState; + + ATN& operator = (ATN &other) NOEXCEPT; + ATN& operator = (ATN &&other) NOEXCEPT; + + /// + /// Compute the set of valid tokens that can occur starting in state {@code s}. + /// If {@code ctx} is null, the set of tokens will not include what can follow + /// the rule surrounding {@code s}. In other words, the set will be + /// restricted to tokens reachable staying within {@code s}'s rule. + /// + virtual misc::IntervalSet nextTokens(ATNState *s, RuleContext *ctx) const; + + /// + /// Compute the set of valid tokens that can occur starting in {@code s} and + /// staying in same rule. is in set if we reach end of + /// rule. + /// + virtual misc::IntervalSet const& nextTokens(ATNState *s) const; + + virtual void addState(ATNState *state); + + virtual void removeState(ATNState *state); + + virtual int defineDecisionState(DecisionState *s); + + virtual DecisionState *getDecisionState(size_t decision) const; + + virtual size_t getNumberOfDecisions() const; + + /// + /// Computes the set of input symbols which could follow ATN state number + /// {@code stateNumber} in the specified full {@code context}. This method + /// considers the complete parser context, but does not evaluate semantic + /// predicates (i.e. all predicates encountered during the calculation are + /// assumed true). If a path in the ATN exists from the starting state to the + /// of the outermost context without matching any + /// symbols, is added to the returned set. + ///

+ /// If {@code context} is {@code null}, it is treated as + /// . + ///

+ /// the ATN state number + /// the full parse context + /// The set of potentially valid input symbols which could follow the + /// specified state in the specified context. + /// if the ATN does not contain a state with + /// number {@code stateNumber} + virtual misc::IntervalSet getExpectedTokens(size_t stateNumber, RuleContext *context) const; + + std::string toString() const; + + private: + mutable std::mutex _mutex; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfig.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfig.h new file mode 100644 index 0000000..767655b --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfig.h @@ -0,0 +1,154 @@ +/* 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. + */ + +#pragma once + +namespace antlr4 { +namespace atn { + + /// + /// A tuple: (ATN state, predicted alt, syntactic, semantic context). + /// The syntactic context is a graph-structured stack node whose + /// path(s) to the root is the rule invocation(s) + /// chain used to arrive at the state. The semantic context is + /// the tree of semantic predicates encountered before reaching + /// an ATN state. + /// + class ANTLR4CPP_PUBLIC ATNConfig { + public: + struct Hasher + { + size_t operator()(ATNConfig const& k) const { + return k.hashCode(); + } + }; + + struct Comparer { + bool operator()(ATNConfig const& lhs, ATNConfig const& rhs) const { + return (&lhs == &rhs) || (lhs == rhs); + } + }; + + + using Set = std::unordered_set, Hasher, Comparer>; + + /// The ATN state associated with this configuration. + ATNState * state; + + /// What alt (or lexer rule) is predicted by this configuration. + const size_t alt; + + /// The stack of invoking states leading to the rule/states associated + /// with this config. We track only those contexts pushed during + /// execution of the ATN simulator. + /// + /// Can be shared between multiple ANTConfig instances. + Ref context; + + /** + * We cannot execute predicates dependent upon local context unless + * we know for sure we are in the correct context. Because there is + * no way to do this efficiently, we simply cannot evaluate + * dependent predicates unless we are in the rule that initially + * invokes the ATN simulator. + * + *

+ * closure() tracks the depth of how far we dip into the outer context: + * depth > 0. Note that it may not be totally accurate depth since I + * don't ever decrement. TODO: make it a boolean then

+ * + *

+ * For memory efficiency, the {@link #isPrecedenceFilterSuppressed} method + * is also backed by this field. Since the field is publicly accessible, the + * highest bit which would not cause the value to become negative is used to + * store this field. This choice minimizes the risk that code which only + * compares this value to 0 would be affected by the new purpose of the + * flag. It also ensures the performance of the existing {@link ATNConfig} + * constructors as well as certain operations like + * {@link ATNConfigSet#add(ATNConfig, DoubleKeyMap)} method are + * completely unaffected by the change.

+ */ + size_t reachesIntoOuterContext; + + /// Can be shared between multiple ATNConfig instances. + Ref semanticContext; + + ATNConfig(ATNState *state, size_t alt, Ref const& context); + ATNConfig(ATNState *state, size_t alt, Ref const& context, Ref const& semanticContext); + + ATNConfig(Ref const& c); // dup + ATNConfig(Ref const& c, ATNState *state); + ATNConfig(Ref const& c, ATNState *state, Ref const& semanticContext); + ATNConfig(Ref const& c, Ref const& semanticContext); + ATNConfig(Ref const& c, ATNState *state, Ref const& context); + ATNConfig(Ref const& c, ATNState *state, Ref const& context, Ref const& semanticContext); + + ATNConfig(ATNConfig const&) = default; + virtual ~ATNConfig(); + + virtual size_t hashCode() const; + + /** + * This method gets the value of the {@link #reachesIntoOuterContext} field + * as it existed prior to the introduction of the + * {@link #isPrecedenceFilterSuppressed} method. + */ + size_t getOuterContextDepth() const ; + bool isPrecedenceFilterSuppressed() const; + void setPrecedenceFilterSuppressed(bool value); + + /// An ATN configuration is equal to another if both have + /// the same state, they predict the same alternative, and + /// syntactic/semantic contexts are the same. + bool operator == (const ATNConfig &other) const; + bool operator != (const ATNConfig &other) const; + + virtual std::string toString(); + std::string toString(bool showAlt); + + private: + /** + * This field stores the bit mask for implementing the + * {@link #isPrecedenceFilterSuppressed} property as a bit within the + * existing {@link #reachesIntoOuterContext} field. + */ +#if __cplusplus >= 201703L + static constexpr size_t SUPPRESS_PRECEDENCE_FILTER = 0x40000000; +#else + enum : size_t { + SUPPRESS_PRECEDENCE_FILTER = 0x40000000, + }; +#endif + }; + +} // namespace atn +} // namespace antlr4 + + +// Hash function for ATNConfig. + +namespace std { + using antlr4::atn::ATNConfig; + + template <> struct hash + { + size_t operator() (const ATNConfig &x) const + { + return x.hashCode(); + } + }; + + template <> struct hash>> + { + size_t operator() (const std::vector> &vector) const + { + std::size_t seed = 0; + for (const auto &config : vector) { + seed ^= config->hashCode() + 0x9e3779b9 + (seed << 6) + (seed >> 2); + } + return seed; + } + }; +} diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfigSet.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfigSet.h new file mode 100644 index 0000000..850a07c --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNConfigSet.h @@ -0,0 +1,110 @@ +/* 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. + */ + +#pragma once + +#include "support/BitSet.h" +#include "atn/PredictionContext.h" + +namespace antlr4 { +namespace atn { + + /// Specialized set that can track info about the set, with support for combining similar configurations using a + /// graph-structured stack. + class ANTLR4CPP_PUBLIC ATNConfigSet { + public: + /// Track the elements as they are added to the set; supports get(i) + std::vector> configs; + + // TODO: these fields make me pretty uncomfortable but nice to pack up info together, saves recomputation + // TODO: can we track conflicts as they are added to save scanning configs later? + size_t uniqueAlt; + + /** Currently this is only used when we detect SLL conflict; this does + * not necessarily represent the ambiguous alternatives. In fact, + * I should also point out that this seems to include predicated alternatives + * that have predicates that evaluate to false. Computed in computeTargetState(). + */ + antlrcpp::BitSet conflictingAlts; + + // Used in parser and lexer. In lexer, it indicates we hit a pred + // while computing a closure operation. Don't make a DFA state from this. + bool hasSemanticContext; + bool dipsIntoOuterContext; + + /// Indicates that this configuration set is part of a full context + /// LL prediction. It will be used to determine how to merge $. With SLL + /// it's a wildcard whereas it is not for LL context merge. + const bool fullCtx; + + ATNConfigSet(bool fullCtx = true); + ATNConfigSet(const Ref &old); + + virtual ~ATNConfigSet(); + + virtual bool add(const Ref &config); + + /// + /// Adding a new config means merging contexts with existing configs for + /// {@code (s, i, pi, _)}, where {@code s} is the + /// , {@code i} is the , and + /// {@code pi} is the . We use + /// {@code (s,i,pi)} as key. + ///

+ /// This method updates and + /// when necessary. + ///

+ virtual bool add(const Ref &config, PredictionContextMergeCache *mergeCache); + + virtual std::vector getStates(); + + /** + * Gets the complete set of represented alternatives for the configuration + * set. + * + * @return the set of represented alternatives in this configuration set + * + * @since 4.3 + */ + antlrcpp::BitSet getAlts(); + virtual std::vector> getPredicates(); + + virtual Ref get(size_t i) const; + + virtual void optimizeConfigs(ATNSimulator *interpreter); + + bool addAll(const Ref &other); + + bool operator == (const ATNConfigSet &other); + virtual size_t hashCode(); + virtual size_t size(); + virtual bool isEmpty(); + virtual void clear(); + virtual bool isReadonly(); + virtual void setReadonly(bool readonly); + virtual std::string toString(); + + protected: + /// Indicates that the set of configurations is read-only. Do not + /// allow any code to manipulate the set; DFA states will point at + /// the sets and they must not change. This does not protect the other + /// fields; in particular, conflictingAlts is set after + /// we've made this readonly. + bool _readonly; + + virtual size_t getHash(ATNConfig *c); // Hash differs depending on set type. + + private: + size_t _cachedHashCode; + + /// All configs but hashed by (s, i, _, pi) not including context. Wiped out + /// when we go readonly as this set becomes a DFA state. + std::unordered_map _configLookup; + + void InitializeInstanceFields(); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializationOptions.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializationOptions.h new file mode 100644 index 0000000..66aa37d --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializationOptions.h @@ -0,0 +1,50 @@ +/* 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. + */ + +#pragma once + +#include "antlr4-common.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC ATNDeserializationOptions { + private: + static ATNDeserializationOptions defaultOptions; + + bool readOnly; + bool verifyATN; + bool generateRuleBypassTransitions; + + public: + ATNDeserializationOptions(); + ATNDeserializationOptions(ATNDeserializationOptions *options); + ATNDeserializationOptions(ATNDeserializationOptions const&) = default; + virtual ~ATNDeserializationOptions(); + ATNDeserializationOptions& operator=(ATNDeserializationOptions const&) = default; + + static const ATNDeserializationOptions& getDefaultOptions(); + + bool isReadOnly(); + + void makeReadOnly(); + + bool isVerifyATN(); + + void setVerifyATN(bool verify); + + bool isGenerateRuleBypassTransitions(); + + void setGenerateRuleBypassTransitions(bool generate); + + protected: + virtual void throwIfReadOnly(); + + private: + void InitializeInstanceFields(); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializer.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializer.h new file mode 100644 index 0000000..12fd11d --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNDeserializer.h @@ -0,0 +1,91 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/ATNDeserializationOptions.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC ATNDeserializer { + public: +#if __cplusplus >= 201703L + static constexpr size_t SERIALIZED_VERSION = 3; +#else + enum : size_t { + SERIALIZED_VERSION = 3, + }; +#endif + + /// This is the current serialized UUID. + // ml: defined as function to avoid the “static initialization order fiasco”. + static Guid SERIALIZED_UUID(); + + ATNDeserializer(); + ATNDeserializer(const ATNDeserializationOptions& dso); + virtual ~ATNDeserializer(); + + static Guid toUUID(const unsigned short *data, size_t offset); + + virtual ATN deserialize(const std::vector &input); + virtual void verifyATN(const ATN &atn); + + static void checkCondition(bool condition); + static void checkCondition(bool condition, const std::string &message); + + static Transition *edgeFactory(const ATN &atn, size_t type, size_t src, size_t trg, size_t arg1, size_t arg2, + size_t arg3, const std::vector &sets); + + static ATNState *stateFactory(size_t type, size_t ruleIndex); + + protected: + /// Determines if a particular serialized representation of an ATN supports + /// a particular feature, identified by the used for serializing + /// the ATN at the time the feature was first introduced. + /// + /// The marking the first time the feature was + /// supported in the serialized ATN. + /// The of the actual serialized ATN which is + /// currently being deserialized. + /// {@code true} if the {@code actualUuid} value represents a + /// serialized ATN at or after the feature identified by {@code feature} was + /// introduced; otherwise, {@code false}. + virtual bool isFeatureSupported(const Guid &feature, const Guid &actualUuid); + void markPrecedenceDecisions(const ATN &atn); + Ref lexerActionFactory(LexerActionType type, int data1, int data2); + + private: + /// This is the earliest supported serialized UUID. + static Guid BASE_SERIALIZED_UUID(); + + /// This UUID indicates an extension of for the + /// addition of precedence predicates. + static Guid ADDED_PRECEDENCE_TRANSITIONS(); + + /** + * This UUID indicates an extension of ADDED_PRECEDENCE_TRANSITIONS + * for the addition of lexer actions encoded as a sequence of + * LexerAction instances. + */ + static Guid ADDED_LEXER_ACTIONS(); + + /** + * This UUID indicates the serialized ATN contains two sets of + * IntervalSets, where the second set's values are encoded as + * 32-bit integers to support the full Unicode SMP range up to U+10FFFF. + */ + static Guid ADDED_UNICODE_SMP(); + + /// This list contains all of the currently supported UUIDs, ordered by when + /// the feature first appeared in this branch. + static std::vector& SUPPORTED_UUIDS(); + + ATNDeserializationOptions deserializationOptions; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSerializer.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSerializer.h new file mode 100644 index 0000000..a6d1d69 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSerializer.h @@ -0,0 +1,61 @@ +/* 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. + */ + +#pragma once + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC ATNSerializer { + public: + ATN *atn; + + ATNSerializer(ATN *atn); + ATNSerializer(ATN *atn, const std::vector &tokenNames); + virtual ~ATNSerializer(); + + /// + /// Serialize state descriptors, edge descriptors, and decision->state map + /// into list of ints: + /// + /// grammar-type, (ANTLRParser.LEXER, ...) + /// max token type, + /// num states, + /// state-0-type ruleIndex, state-1-type ruleIndex, ... state-i-type + /// ruleIndex optional-arg ... + /// num rules, + /// rule-1-start-state rule-1-args, rule-2-start-state rule-2-args, ... + /// (args are token type,actionIndex in lexer else 0,0) + /// num modes, + /// mode-0-start-state, mode-1-start-state, ... (parser has 0 modes) + /// num sets + /// set-0-interval-count intervals, set-1-interval-count intervals, ... + /// num total edges, + /// src, trg, edge-type, edge arg1, optional edge arg2 (present always), + /// ... + /// num decisions, + /// decision-0-start-state, decision-1-start-state, ... + /// + /// Convenient to pack into unsigned shorts to make as Java string. + /// + virtual std::vector serialize(); + + virtual std::string decode(const std::wstring& data); + virtual std::string getTokenName(size_t t); + + /// Used by Java target to encode short/int array as chars in string. + static std::wstring getSerializedAsString(ATN *atn); + static std::vector getSerialized(ATN *atn); + + static std::string getDecoded(ATN *atn, std::vector &tokenNames); + + private: + std::vector _tokenNames; + + void serializeUUID(std::vector &data, Guid uuid); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSimulator.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSimulator.h new file mode 100644 index 0000000..f702c97 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNSimulator.h @@ -0,0 +1,87 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATN.h" +#include "misc/IntervalSet.h" +#include "support/CPPUtils.h" +#include "atn/PredictionContext.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC ATNSimulator { + public: + /// Must distinguish between missing edge and edge we know leads nowhere. + static const Ref ERROR; + const ATN &atn; + + ATNSimulator(const ATN &atn, PredictionContextCache &sharedContextCache); + virtual ~ATNSimulator(); + + virtual void reset() = 0; + + /** + * Clear the DFA cache used by the current instance. Since the DFA cache may + * be shared by multiple ATN simulators, this method may affect the + * performance (but not accuracy) of other parsers which are being used + * concurrently. + * + * @throws UnsupportedOperationException if the current instance does not + * support clearing the DFA. + * + * @since 4.3 + */ + virtual void clearDFA(); + virtual PredictionContextCache& getSharedContextCache(); + virtual Ref getCachedContext(Ref const& context); + + /// @deprecated Use instead. + static ATN deserialize(const std::vector &data); + + /// @deprecated Use instead. + static void checkCondition(bool condition); + + /// @deprecated Use instead. + static void checkCondition(bool condition, const std::string &message); + + /// @deprecated Use instead. + static Transition *edgeFactory(const ATN &atn, int type, int src, int trg, int arg1, int arg2, int arg3, + const std::vector &sets); + + /// @deprecated Use instead. + static ATNState *stateFactory(int type, int ruleIndex); + + protected: + static antlrcpp::SingleWriteMultipleReadLock _stateLock; // Lock for DFA states. + static antlrcpp::SingleWriteMultipleReadLock _edgeLock; // Lock for the sparse edge map in DFA states. + + /// + /// The context cache maps all PredictionContext objects that are equals() + /// to a single cached copy. This cache is shared across all contexts + /// in all ATNConfigs in all DFA states. We rebuild each ATNConfigSet + /// to use only cached nodes/graphs in addDFAState(). We don't want to + /// fill this during closure() since there are lots of contexts that + /// pop up but are not used ever again. It also greatly slows down closure(). + ///

+ /// This cache makes a huge difference in memory and a little bit in speed. + /// For the Java grammar on java.*, it dropped the memory requirements + /// at the end from 25M to 16M. We don't store any of the full context + /// graphs in the DFA because they are limited to local context only, + /// but apparently there's a lot of repetition there as well. We optimize + /// the config contexts before storing the config set in the DFA states + /// by literally rebuilding them with cached subgraphs only. + ///

+ /// I tried a cache for use during closure operations, that was + /// whacked after each adaptivePredict(). It cost a little bit + /// more time I think and doesn't save on the overall footprint + /// so it's not worth the complexity. + ///

+ PredictionContextCache &_sharedContextCache; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNState.h new file mode 100644 index 0000000..8ed6137 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNState.h @@ -0,0 +1,140 @@ +/* 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. + */ + +#pragma once + +#include "misc/IntervalSet.h" + +namespace antlr4 { +namespace atn { + + /// + /// The following images show the relation of states and + /// for various grammar constructs. + /// + ///
    + /// + ///
  • Solid edges marked with an ε indicate a required + /// .
    • + /// + ///
  • Dashed edges indicate locations where any transition derived from + /// might appear.
    • + /// + ///
  • Dashed nodes are place holders for either a sequence of linked + /// states or the inclusion of a block representing a nested + /// construct in one of the forms below.
    • + /// + ///
  • Nodes showing multiple outgoing alternatives with a {@code ...} support + /// any number of alternatives (one or more). Nodes without the {@code ...} only + /// support the exact number of alternatives shown in the diagram.
    • + /// + ///
+ /// + ///

Basic Blocks

+ /// + ///

Rule

+ /// + /// + /// + ///

Block of 1 or more alternatives

+ /// + /// + /// + ///

Greedy Loops

+ /// + ///

Greedy Closure: {@code (...)*}

+ /// + /// + /// + ///

Greedy Positive Closure: {@code (...)+}

+ /// + /// + /// + ///

Greedy Optional: {@code (...)?}

+ /// + /// + /// + ///

Non-Greedy Loops

+ /// + ///

Non-Greedy Closure: {@code (...)*?}

+ /// + /// + /// + ///

Non-Greedy Positive Closure: {@code (...)+?}

+ /// + /// + /// + ///

Non-Greedy Optional: {@code (...)??}

+ /// + /// + /// + class ANTLR4CPP_PUBLIC ATN; + + class ANTLR4CPP_PUBLIC ATNState { + public: + ATNState(); + ATNState(ATNState const&) = delete; + + virtual ~ATNState(); + + ATNState& operator=(ATNState const&) = delete; + +#if __cplusplus >= 201703L + static constexpr size_t INITIAL_NUM_TRANSITIONS = 4; + static constexpr size_t INVALID_STATE_NUMBER = std::numeric_limits::max(); +#else + enum : size_t { + INITIAL_NUM_TRANSITIONS = 4, + INVALID_STATE_NUMBER = static_cast(-1), // std::numeric_limits::max(); doesn't work in VS 2013 + }; +#endif + + enum { + ATN_INVALID_TYPE = 0, + BASIC = 1, + RULE_START = 2, + BLOCK_START = 3, + PLUS_BLOCK_START = 4, + STAR_BLOCK_START = 5, + TOKEN_START = 6, + RULE_STOP = 7, + BLOCK_END = 8, + STAR_LOOP_BACK = 9, + STAR_LOOP_ENTRY = 10, + PLUS_LOOP_BACK = 11, + LOOP_END = 12 + }; + + static const std::vector serializationNames; + + size_t stateNumber = INVALID_STATE_NUMBER; + size_t ruleIndex = 0; // at runtime, we don't have Rule objects + bool epsilonOnlyTransitions = false; + + public: + virtual size_t hashCode(); + bool operator == (const ATNState &other); + + /// Track the transitions emanating from this ATN state. + std::vector transitions; + + virtual bool isNonGreedyExitState(); + virtual std::string toString() const; + virtual void addTransition(Transition *e); + virtual void addTransition(size_t index, Transition *e); + virtual Transition* removeTransition(size_t index); + virtual size_t getStateType() = 0; + + private: + /// Used to cache lookahead during parsing, not used during construction. + + misc::IntervalSet _nextTokenWithinRule; + std::atomic _nextTokenUpdated { false }; + + friend class ATN; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNType.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNType.h new file mode 100644 index 0000000..19ed7a6 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ATNType.h @@ -0,0 +1,20 @@ +/* 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. + */ + +#pragma once + +#include "antlr4-common.h" + +namespace antlr4 { +namespace atn { + + /// Represents the type of recognizer an ATN applies to. + enum class ATNType { + LEXER = 0, + PARSER = 1, + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AbstractPredicateTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AbstractPredicateTransition.h new file mode 100644 index 0000000..4865cb1 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AbstractPredicateTransition.h @@ -0,0 +1,24 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + class ANTState; + + class ANTLR4CPP_PUBLIC AbstractPredicateTransition : public Transition { + + public: + AbstractPredicateTransition(ATNState *target); + ~AbstractPredicateTransition(); + + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ActionTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ActionTransition.h new file mode 100644 index 0000000..652e75f --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ActionTransition.h @@ -0,0 +1,33 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC ActionTransition final : public Transition { + public: + const size_t ruleIndex; + const size_t actionIndex; + const bool isCtxDependent; // e.g., $i ref in action + + ActionTransition(ATNState *target, size_t ruleIndex); + + ActionTransition(ATNState *target, size_t ruleIndex, size_t actionIndex, bool isCtxDependent); + + virtual SerializationType getSerializationType() const override; + + virtual bool isEpsilon() const override; + + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AmbiguityInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AmbiguityInfo.h new file mode 100644 index 0000000..db594a1 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AmbiguityInfo.h @@ -0,0 +1,68 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionEventInfo.h" +#include "support/BitSet.h" + +namespace antlr4 { +namespace atn { + + /// + /// This class represents profiling event information for an ambiguity. + /// Ambiguities are decisions where a particular input resulted in an SLL + /// conflict, followed by LL prediction also reaching a conflict state + /// (indicating a true ambiguity in the grammar). + /// + /// + /// This event may be reported during SLL prediction in cases where the + /// conflicting SLL configuration set provides sufficient information to + /// determine that the SLL conflict is truly an ambiguity. For example, if none + /// of the ATN configurations in the conflicting SLL configuration set have + /// traversed a global follow transition (i.e. + /// is 0 for all configurations), then + /// the result of SLL prediction for that input is known to be equivalent to the + /// result of LL prediction for that input. + /// + /// + /// In some cases, the minimum represented alternative in the conflicting LL + /// configuration set is not equal to the minimum represented alternative in the + /// conflicting SLL configuration set. Grammars and inputs which result in this + /// scenario are unable to use , which in turn means + /// they cannot use the two-stage parsing strategy to improve parsing performance + /// for that input. + /// + /// + /// + class ANTLR4CPP_PUBLIC AmbiguityInfo : public DecisionEventInfo { + public: + /// The set of alternative numbers for this decision event that lead to a valid parse. + antlrcpp::BitSet ambigAlts; + + /// + /// Constructs a new instance of the class with the + /// specified detailed ambiguity information. + /// + /// The decision number + /// The final configuration set identifying the ambiguous + /// alternatives for the current input + /// The set of alternatives in the decision that lead to a valid parse. + /// The predicted alt is the min(ambigAlts) + /// The input token stream + /// The start index for the current prediction + /// The index at which the ambiguity was identified during + /// prediction + /// {@code true} if the ambiguity was identified during LL + /// prediction; otherwise, {@code false} if the ambiguity was identified + /// during SLL prediction + AmbiguityInfo(size_t decision, ATNConfigSet *configs, const antlrcpp::BitSet &ambigAlts, TokenStream *input, + size_t startIndex, size_t stopIndex, bool fullCtx); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ArrayPredictionContext.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ArrayPredictionContext.h new file mode 100644 index 0000000..53a5b17 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ArrayPredictionContext.h @@ -0,0 +1,43 @@ + +/* 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. + */ + +#pragma once + +#include "atn/PredictionContext.h" + +namespace antlr4 { +namespace atn { + + class SingletonPredictionContext; + + class ANTLR4CPP_PUBLIC ArrayPredictionContext : public PredictionContext { + public: + /// Parent can be empty only if full ctx mode and we make an array + /// from EMPTY and non-empty. We merge EMPTY by using null parent and + /// returnState == EMPTY_RETURN_STATE. + // Also here: we use a strong reference to our parents to avoid having them freed prematurely. + // See also SinglePredictionContext. + const std::vector> parents; + + /// Sorted for merge, no duplicates; if present, EMPTY_RETURN_STATE is always last. + const std::vector returnStates; + + ArrayPredictionContext(Ref const& a); + ArrayPredictionContext(std::vector> const& parents_, std::vector const& returnStates); + virtual ~ArrayPredictionContext(); + + virtual bool isEmpty() const override; + virtual size_t size() const override; + virtual Ref getParent(size_t index) const override; + virtual size_t getReturnState(size_t index) const override; + bool operator == (const PredictionContext &o) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 + diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AtomTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AtomTransition.h new file mode 100644 index 0000000..cc22e5a --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/AtomTransition.h @@ -0,0 +1,30 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + /// TODO: make all transitions sets? no, should remove set edges. + class ANTLR4CPP_PUBLIC AtomTransition final : public Transition { + public: + /// The token type or character value; or, signifies special label. + const size_t _label; + + AtomTransition(ATNState *target, size_t label); + + virtual SerializationType getSerializationType() const override; + + virtual misc::IntervalSet label() const override; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicBlockStartState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicBlockStartState.h new file mode 100644 index 0000000..471fbc7 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicBlockStartState.h @@ -0,0 +1,22 @@ +/* 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. + */ + +#pragma once + +#include "antlr4-common.h" +#include "atn/BlockStartState.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC BasicBlockStartState final : public BlockStartState { + + public: + virtual size_t getStateType() override; + + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicState.h new file mode 100644 index 0000000..b650dc2 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BasicState.h @@ -0,0 +1,21 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC BasicState final : public ATNState { + + public: + virtual size_t getStateType() override; + + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockEndState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockEndState.h new file mode 100644 index 0000000..b24bee1 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockEndState.h @@ -0,0 +1,24 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + /// Terminal node of a simple {@code (a|b|c)} block. + class ANTLR4CPP_PUBLIC BlockEndState final : public ATNState { + public: + BlockStartState *startState = nullptr; + + BlockEndState(); + + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockStartState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockStartState.h new file mode 100644 index 0000000..725c700 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/BlockStartState.h @@ -0,0 +1,21 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionState.h" + +namespace antlr4 { +namespace atn { + + /// The start of a regular {@code (...)} block. + class ANTLR4CPP_PUBLIC BlockStartState : public DecisionState { + public: + ~BlockStartState(); + BlockEndState *endState = nullptr; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ContextSensitivityInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ContextSensitivityInfo.h new file mode 100644 index 0000000..430ce3b --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ContextSensitivityInfo.h @@ -0,0 +1,47 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionEventInfo.h" + +namespace antlr4 { +namespace atn { + + /// + /// This class represents profiling event information for a context sensitivity. + /// Context sensitivities are decisions where a particular input resulted in an + /// SLL conflict, but LL prediction produced a single unique alternative. + /// + /// + /// In some cases, the unique alternative identified by LL prediction is not + /// equal to the minimum represented alternative in the conflicting SLL + /// configuration set. Grammars and inputs which result in this scenario are + /// unable to use , which in turn means they cannot use + /// the two-stage parsing strategy to improve parsing performance for that + /// input. + /// + /// + /// + class ANTLR4CPP_PUBLIC ContextSensitivityInfo : public DecisionEventInfo { + public: + /// + /// Constructs a new instance of the class + /// with the specified detailed context sensitivity information. + /// + /// The decision number + /// The final configuration set containing the unique + /// alternative identified by full-context prediction + /// The input token stream + /// The start index for the current prediction + /// The index at which the context sensitivity was + /// identified during full-context prediction + ContextSensitivityInfo(size_t decision, ATNConfigSet *configs, TokenStream *input, size_t startIndex, size_t stopIndex); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionEventInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionEventInfo.h new file mode 100644 index 0000000..af7f5f4 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionEventInfo.h @@ -0,0 +1,70 @@ +/* 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. + */ + +#pragma once + +#include "antlr4-common.h" + +namespace antlr4 { +namespace atn { + + /// + /// This is the base class for gathering detailed information about prediction + /// events which occur during parsing. + /// + /// Note that we could record the parser call stack at the time this event + /// occurred but in the presence of left recursive rules, the stack is kind of + /// meaningless. It's better to look at the individual configurations for their + /// individual stacks. Of course that is a object + /// not a parse tree node and so it does not have information about the extent + /// (start...stop) of the various subtrees. Examining the stack tops of all + /// configurations provide the return states for the rule invocations. + /// From there you can get the enclosing rule. + /// + /// @since 4.3 + /// + class ANTLR4CPP_PUBLIC DecisionEventInfo { + public: + /// + /// The invoked decision number which this event is related to. + /// + /// + const size_t decision; + + /// + /// The configuration set containing additional information relevant to the + /// prediction state when the current event occurred, or {@code null} if no + /// additional information is relevant or available. + /// + const ATNConfigSet *configs; + + /// + /// The input token stream which is being parsed. + /// + const TokenStream *input; + + /// + /// The token index in the input stream at which the current prediction was + /// originally invoked. + /// + const size_t startIndex; + + /// + /// The token index in the input stream at which the current event occurred. + /// + const size_t stopIndex; + + /// + /// {@code true} if the current event occurred during LL prediction; + /// otherwise, {@code false} if the input occurred during SLL prediction. + /// + const bool fullCtx; + + DecisionEventInfo(size_t decision, ATNConfigSet *configs, TokenStream *input, size_t startIndex, + size_t stopIndex, bool fullCtx); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionInfo.h new file mode 100644 index 0000000..cfbb2e9 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionInfo.h @@ -0,0 +1,227 @@ +/* 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. + */ + +#pragma once + +#include "atn/ContextSensitivityInfo.h" +#include "atn/AmbiguityInfo.h" +#include "atn/PredicateEvalInfo.h" +#include "atn/ErrorInfo.h" + +namespace antlr4 { +namespace atn { + + class LookaheadEventInfo; + + /// + /// This class contains profiling gathered for a particular decision. + /// + /// + /// Parsing performance in ANTLR 4 is heavily influenced by both static factors + /// (e.g. the form of the rules in the grammar) and dynamic factors (e.g. the + /// choice of input and the state of the DFA cache at the time profiling + /// operations are started). For best results, gather and use aggregate + /// statistics from a large sample of inputs representing the inputs expected in + /// production before using the results to make changes in the grammar. + /// + /// @since 4.3 + /// + class ANTLR4CPP_PUBLIC DecisionInfo { + public: + /// + /// The decision number, which is an index into . + /// + const size_t decision; + + /// + /// The total number of times was + /// invoked for this decision. + /// + long long invocations = 0; + + /// + /// The total time spent in for + /// this decision, in nanoseconds. + /// + /// + /// The value of this field contains the sum of differential results obtained + /// by , and is not adjusted to compensate for JIT + /// and/or garbage collection overhead. For best accuracy, use a modern JVM + /// implementation that provides precise results from + /// , and perform profiling in a separate process + /// which is warmed up by parsing the input prior to profiling. If desired, + /// call to reset the DFA cache to its initial + /// state before starting the profiling measurement pass. + /// + long long timeInPrediction = 0; + + /// + /// The sum of the lookahead required for SLL prediction for this decision. + /// Note that SLL prediction is used before LL prediction for performance + /// reasons even when or + /// is used. + /// + long long SLL_TotalLook = 0; + + /// + /// Gets the minimum lookahead required for any single SLL prediction to + /// complete for this decision, by reaching a unique prediction, reaching an + /// SLL conflict state, or encountering a syntax error. + /// + long long SLL_MinLook = 0; + + /// + /// Gets the maximum lookahead required for any single SLL prediction to + /// complete for this decision, by reaching a unique prediction, reaching an + /// SLL conflict state, or encountering a syntax error. + /// + long long SLL_MaxLook = 0; + + /// Gets the associated with the event where the + /// value was set. + Ref SLL_MaxLookEvent; + + /// + /// The sum of the lookahead required for LL prediction for this decision. + /// Note that LL prediction is only used when SLL prediction reaches a + /// conflict state. + /// + long long LL_TotalLook = 0; + + /// + /// Gets the minimum lookahead required for any single LL prediction to + /// complete for this decision. An LL prediction completes when the algorithm + /// reaches a unique prediction, a conflict state (for + /// , an ambiguity state (for + /// , or a syntax error. + /// + long long LL_MinLook = 0; + + /// + /// Gets the maximum lookahead required for any single LL prediction to + /// complete for this decision. An LL prediction completes when the algorithm + /// reaches a unique prediction, a conflict state (for + /// , an ambiguity state (for + /// , or a syntax error. + /// + long long LL_MaxLook = 0; + + /// + /// Gets the associated with the event where the + /// value was set. + /// + Ref LL_MaxLookEvent; + + /// + /// A collection of instances describing the + /// context sensitivities encountered during LL prediction for this decision. + /// + /// + std::vector contextSensitivities; + + /// + /// A collection of instances describing the parse errors + /// identified during calls to for + /// this decision. + /// + /// + std::vector errors; + + /// + /// A collection of instances describing the + /// ambiguities encountered during LL prediction for this decision. + /// + /// + std::vector ambiguities; + + /// + /// A collection of instances describing the + /// results of evaluating individual predicates during prediction for this + /// decision. + /// + /// + std::vector predicateEvals; + + /// + /// The total number of ATN transitions required during SLL prediction for + /// this decision. An ATN transition is determined by the number of times the + /// DFA does not contain an edge that is required for prediction, resulting + /// in on-the-fly computation of that edge. + /// + /// + /// If DFA caching of SLL transitions is employed by the implementation, ATN + /// computation may cache the computed edge for efficient lookup during + /// future parsing of this decision. Otherwise, the SLL parsing algorithm + /// will use ATN transitions exclusively. + /// + /// + /// + /// + long long SLL_ATNTransitions = 0; + + /// + /// The total number of DFA transitions required during SLL prediction for + /// this decision. + /// + /// If the ATN simulator implementation does not use DFA caching for SLL + /// transitions, this value will be 0. + /// + /// + /// + long long SLL_DFATransitions = 0; + + /// + /// Gets the total number of times SLL prediction completed in a conflict + /// state, resulting in fallback to LL prediction. + /// + /// Note that this value is not related to whether or not + /// may be used successfully with a particular + /// grammar. If the ambiguity resolution algorithm applied to the SLL + /// conflicts for this decision produce the same result as LL prediction for + /// this decision, would produce the same overall + /// parsing result as . + /// + long long LL_Fallback = 0; + + /// + /// The total number of ATN transitions required during LL prediction for + /// this decision. An ATN transition is determined by the number of times the + /// DFA does not contain an edge that is required for prediction, resulting + /// in on-the-fly computation of that edge. + /// + /// + /// If DFA caching of LL transitions is employed by the implementation, ATN + /// computation may cache the computed edge for efficient lookup during + /// future parsing of this decision. Otherwise, the LL parsing algorithm will + /// use ATN transitions exclusively. + /// + /// + /// + /// + long long LL_ATNTransitions = 0; + + /// + /// The total number of DFA transitions required during LL prediction for + /// this decision. + /// + /// If the ATN simulator implementation does not use DFA caching for LL + /// transitions, this value will be 0. + /// + /// + /// + long long LL_DFATransitions = 0; + + /// + /// Constructs a new instance of the class to contain + /// statistics for a particular decision. + /// + /// The decision number + DecisionInfo(size_t decision); + + std::string toString() const; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionState.h new file mode 100644 index 0000000..005de25 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/DecisionState.h @@ -0,0 +1,30 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC DecisionState : public ATNState { + public: + int decision; + bool nonGreedy; + + private: + void InitializeInstanceFields(); + + public: + DecisionState() { + InitializeInstanceFields(); + } + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EmptyPredictionContext.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EmptyPredictionContext.h new file mode 100644 index 0000000..93c036c --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EmptyPredictionContext.h @@ -0,0 +1,27 @@ +/* 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. + */ + +#pragma once + +#include "atn/SingletonPredictionContext.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC EmptyPredictionContext : public SingletonPredictionContext { + public: + EmptyPredictionContext(); + + virtual bool isEmpty() const override; + virtual size_t size() const override; + virtual Ref getParent(size_t index) const override; + virtual size_t getReturnState(size_t index) const override; + virtual std::string toString() const override; + + virtual bool operator == (const PredictionContext &o) const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EpsilonTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EpsilonTransition.h new file mode 100644 index 0000000..41fb0fb --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/EpsilonTransition.h @@ -0,0 +1,39 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC EpsilonTransition final : public Transition { + public: + EpsilonTransition(ATNState *target); + EpsilonTransition(ATNState *target, size_t outermostPrecedenceReturn); + + /** + * @return the rule index of a precedence rule for which this transition is + * returning from, where the precedence value is 0; otherwise, INVALID_INDEX. + * + * @see ATNConfig#isPrecedenceFilterSuppressed() + * @see ParserATNSimulator#applyPrecedenceFilter(ATNConfigSet) + * @since 4.4.1 + */ + size_t outermostPrecedenceReturn(); + virtual SerializationType getSerializationType() const override; + + virtual bool isEpsilon() const override; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + + private: + const size_t _outermostPrecedenceReturn; // A rule index. + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ErrorInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ErrorInfo.h new file mode 100644 index 0000000..d34642a --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ErrorInfo.h @@ -0,0 +1,43 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionEventInfo.h" + +namespace antlr4 { +namespace atn { + + /// + /// This class represents profiling event information for a syntax error + /// identified during prediction. Syntax errors occur when the prediction + /// algorithm is unable to identify an alternative which would lead to a + /// successful parse. + /// + /// + /// + class ANTLR4CPP_PUBLIC ErrorInfo : public DecisionEventInfo { + public: + /// + /// Constructs a new instance of the class with the + /// specified detailed syntax error information. + /// + /// The decision number + /// The final configuration set reached during prediction + /// prior to reaching the state + /// The input token stream + /// The start index for the current prediction + /// The index at which the syntax error was identified + /// {@code true} if the syntax error was identified during LL + /// prediction; otherwise, {@code false} if the syntax error was identified + /// during SLL prediction + ErrorInfo(size_t decision, ATNConfigSet *configs, TokenStream *input, size_t startIndex, size_t stopIndex, + bool fullCtx); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LL1Analyzer.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LL1Analyzer.h new file mode 100644 index 0000000..e297bc9 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LL1Analyzer.h @@ -0,0 +1,115 @@ +/* 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. + */ + +#pragma once + +#include "Token.h" +#include "support/BitSet.h" +#include "atn/PredictionContext.h" +#include "atn/ATNConfig.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC LL1Analyzer { + public: + /// Special value added to the lookahead sets to indicate that we hit + /// a predicate during analysis if {@code seeThruPreds==false}. +#if __cplusplus >= 201703L + static constexpr size_t HIT_PRED = Token::INVALID_TYPE; +#else + enum : size_t { + HIT_PRED = Token::INVALID_TYPE, + }; +#endif + + const atn::ATN &_atn; + + LL1Analyzer(const atn::ATN &atn); + virtual ~LL1Analyzer(); + + /// + /// Calculates the SLL(1) expected lookahead set for each outgoing transition + /// of an . The returned array has one element for each + /// outgoing transition in {@code s}. If the closure from transition + /// i leads to a semantic predicate before matching a symbol, the + /// element at index i of the result will be {@code null}. + /// + /// the ATN state + /// the expected symbols for each outgoing transition of {@code s}. + virtual std::vector getDecisionLookahead(ATNState *s) const; + + /// + /// Compute set of tokens that can follow {@code s} in the ATN in the + /// specified {@code ctx}. + ///

+ /// If {@code ctx} is {@code null} and the end of the rule containing + /// {@code s} is reached, is added to the result set. + /// If {@code ctx} is not {@code null} and the end of the outermost rule is + /// reached, is added to the result set. + ///

+ /// the ATN state + /// the complete parser context, or {@code null} if the context + /// should be ignored + /// + /// The set of tokens that can follow {@code s} in the ATN in the + /// specified {@code ctx}. + virtual misc::IntervalSet LOOK(ATNState *s, RuleContext *ctx) const; + + /// + /// Compute set of tokens that can follow {@code s} in the ATN in the + /// specified {@code ctx}. + ///

+ /// If {@code ctx} is {@code null} and the end of the rule containing + /// {@code s} is reached, is added to the result set. + /// If {@code ctx} is not {@code null} and the end of the outermost rule is + /// reached, is added to the result set. + ///

+ /// the ATN state + /// the ATN state to stop at. This can be a + /// to detect epsilon paths through a closure. + /// the complete parser context, or {@code null} if the context + /// should be ignored + /// + /// The set of tokens that can follow {@code s} in the ATN in the + /// specified {@code ctx}. + virtual misc::IntervalSet LOOK(ATNState *s, ATNState *stopState, RuleContext *ctx) const; + + /// + /// Compute set of tokens that can follow {@code s} in the ATN in the + /// specified {@code ctx}. + ///

+ /// If {@code ctx} is {@code null} and {@code stopState} or the end of the + /// rule containing {@code s} is reached, 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, is added to the result set. + ///

+ /// the ATN state. + /// the ATN state to stop at. This can be a + /// to detect epsilon paths through a closure. + /// The outer context, or {@code null} if the outer context should + /// not be used. + /// The result lookahead set. + /// A set used for preventing epsilon closures in the ATN + /// from causing a stack overflow. Outside code should pass + /// {@code new HashSet} for this argument. + /// 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. + /// {@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 to the + /// result if one is encountered. + /// Add to the result if the end of the + /// outermost context is reached. This parameter has no effect if {@code ctx} + /// is {@code null}. + protected: + virtual void _LOOK(ATNState *s, ATNState *stopState, Ref const& ctx, misc::IntervalSet &look, + ATNConfig::Set &lookBusy, antlrcpp::BitSet &calledRuleStack, bool seeThruPreds, bool addEOF) const; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNConfig.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNConfig.h new file mode 100644 index 0000000..e25d3d1 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNConfig.h @@ -0,0 +1,44 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNConfig.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC LexerATNConfig : public ATNConfig { + public: + LexerATNConfig(ATNState *state, int alt, Ref const& context); + LexerATNConfig(ATNState *state, int alt, Ref const& context, Ref const& lexerActionExecutor); + + LexerATNConfig(Ref const& c, ATNState *state); + LexerATNConfig(Ref const& c, ATNState *state, Ref const& lexerActionExecutor); + LexerATNConfig(Ref const& c, ATNState *state, Ref const& context); + + /** + * Gets the {@link LexerActionExecutor} capable of executing the embedded + * action(s) for the current configuration. + */ + Ref getLexerActionExecutor() const; + bool hasPassedThroughNonGreedyDecision(); + + virtual size_t hashCode() const override; + + bool operator == (const LexerATNConfig& other) const; + + private: + /** + * This is the backing field for {@link #getLexerActionExecutor}. + */ + const Ref _lexerActionExecutor; + const bool _passedThroughNonGreedyDecision; + + static bool checkNonGreedyDecision(Ref const& source, ATNState *target); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNSimulator.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNSimulator.h new file mode 100644 index 0000000..c050d51 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerATNSimulator.h @@ -0,0 +1,217 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNSimulator.h" +#include "atn/LexerATNConfig.h" +#include "atn/ATNConfigSet.h" + +namespace antlr4 { +namespace atn { + + /// "dup" of ParserInterpreter + class ANTLR4CPP_PUBLIC LexerATNSimulator : public ATNSimulator { + protected: + class SimState { + public: + virtual ~SimState(); + + protected: + size_t index; + size_t line; + size_t charPos; + dfa::DFAState *dfaState; + virtual void reset(); + friend class LexerATNSimulator; + + private: + void InitializeInstanceFields(); + + public: + SimState() { + InitializeInstanceFields(); + } + }; + + + public: +#if __cplusplus >= 201703L + static constexpr size_t MIN_DFA_EDGE = 0; + static constexpr size_t MAX_DFA_EDGE = 127; // forces unicode to stay in ATN +#else + enum : size_t { + MIN_DFA_EDGE = 0, + MAX_DFA_EDGE = 127, // forces unicode to stay in ATN + }; +#endif + + protected: + /// + /// When we hit an accept state in either the DFA or the ATN, we + /// have to notify the character stream to start buffering characters + /// via and record the current state. The current sim state + /// includes the current index into the input, the current line, + /// and current character position in that line. Note that the Lexer is + /// tracking the starting line and characterization of the token. These + /// variables track the "state" of the simulator when it hits an accept state. + ///

+ /// We track these variables separately for the DFA and ATN simulation + /// because the DFA simulation often has to fail over to the ATN + /// simulation. If the ATN simulation fails, we need the DFA to fall + /// back to its previously accepted state, if any. If the ATN succeeds, + /// then the ATN does the accept and the DFA simulator that invoked it + /// can simply return the predicted token type. + ///

+ Lexer *const _recog; + + /// The current token's starting index into the character stream. + /// Shared across DFA to ATN simulation in case the ATN fails and the + /// DFA did not have a previous accept state. In this case, we use the + /// ATN-generated exception object. + size_t _startIndex; + + /// line number 1..n within the input. + size_t _line; + + /// The index of the character relative to the beginning of the line 0..n-1. + size_t _charPositionInLine; + + public: + std::vector &_decisionToDFA; + + protected: + size_t _mode; + + /// Used during DFA/ATN exec to record the most recent accept configuration info. + SimState _prevAccept; + + public: + static int match_calls; + + LexerATNSimulator(const ATN &atn, std::vector &decisionToDFA, PredictionContextCache &sharedContextCache); + LexerATNSimulator(Lexer *recog, const ATN &atn, std::vector &decisionToDFA, PredictionContextCache &sharedContextCache); + virtual ~LexerATNSimulator () {} + + virtual void copyState(LexerATNSimulator *simulator); + virtual size_t match(CharStream *input, size_t mode); + virtual void reset() override; + + virtual void clearDFA() override; + + protected: + virtual size_t matchATN(CharStream *input); + virtual size_t execATN(CharStream *input, dfa::DFAState *ds0); + + /// + /// Get an existing target state for an edge in the DFA. If the target state + /// for the edge has not yet been computed or is otherwise not available, + /// this method returns {@code null}. + /// + /// The current DFA state + /// The next input symbol + /// The existing target DFA state for the given input symbol + /// {@code t}, or {@code null} if the target state for this edge is not + /// already cached + virtual dfa::DFAState *getExistingTargetState(dfa::DFAState *s, size_t t); + + /// + /// Compute a target state for an edge in the DFA, and attempt to add the + /// computed state and corresponding edge to the DFA. + /// + /// The input stream + /// The current DFA state + /// The next input symbol + /// + /// The computed target DFA state for the given input symbol + /// {@code t}. If {@code t} does not lead to a valid DFA state, this method + /// returns . + virtual dfa::DFAState *computeTargetState(CharStream *input, dfa::DFAState *s, size_t t); + + virtual size_t failOrAccept(CharStream *input, ATNConfigSet *reach, size_t t); + + /// + /// Given a starting configuration set, figure out all ATN configurations + /// we can reach upon input {@code t}. Parameter {@code reach} is a return + /// parameter. + /// + void getReachableConfigSet(CharStream *input, ATNConfigSet *closure_, // closure_ as we have a closure() already + ATNConfigSet *reach, size_t t); + + virtual void accept(CharStream *input, const Ref &lexerActionExecutor, size_t startIndex, size_t index, + size_t line, size_t charPos); + + virtual ATNState *getReachableTarget(Transition *trans, size_t t); + + virtual std::unique_ptr computeStartState(CharStream *input, ATNState *p); + + /// + /// Since the alternatives within any lexer decision are ordered by + /// preference, this method stops pursuing the closure as soon as an accept + /// state is reached. After the first accept state is reached by depth-first + /// search from {@code config}, all other (potentially reachable) states for + /// this rule would have a lower priority. + /// + /// {@code true} if an accept state is reached, otherwise + /// {@code false}. + virtual bool closure(CharStream *input, const Ref &config, ATNConfigSet *configs, + bool currentAltReachedAcceptState, bool speculative, bool treatEofAsEpsilon); + + // side-effect: can alter configs.hasSemanticContext + virtual Ref getEpsilonTarget(CharStream *input, const Ref &config, Transition *t, + ATNConfigSet *configs, bool speculative, bool treatEofAsEpsilon); + + /// + /// Evaluate a predicate specified in the lexer. + ///

+ /// If {@code speculative} is {@code true}, this method was called before + /// for the matched character. This method should call + /// before evaluating the predicate to ensure position + /// sensitive values, including , , + /// and , properly reflect the current + /// lexer state. This method should restore {@code input} and the simulator + /// to the original state before returning (i.e. undo the actions made by the + /// call to . + ///

+ /// The input stream. + /// The rule containing the predicate. + /// The index of the predicate within the rule. + /// {@code true} if the current index in {@code input} is + /// one character before the predicate's location. + /// + /// {@code true} if the specified predicate evaluates to + /// {@code true}. + virtual bool evaluatePredicate(CharStream *input, size_t ruleIndex, size_t predIndex, bool speculative); + + virtual void captureSimState(CharStream *input, dfa::DFAState *dfaState); + virtual dfa::DFAState* addDFAEdge(dfa::DFAState *from, size_t t, ATNConfigSet *q); + virtual void addDFAEdge(dfa::DFAState *p, size_t t, dfa::DFAState *q); + + /// + /// Add a new DFA state if there isn't one with this set of + /// configurations already. This method also detects the first + /// configuration containing an ATN rule stop state. Later, when + /// traversing the DFA, we will know which rule to accept. + /// + virtual dfa::DFAState *addDFAState(ATNConfigSet *configs); + + public: + dfa::DFA& getDFA(size_t mode); + + /// Get the text matched so far for the current token. + virtual std::string getText(CharStream *input); + virtual size_t getLine() const; + virtual void setLine(size_t line); + virtual size_t getCharPositionInLine(); + virtual void setCharPositionInLine(size_t charPositionInLine); + virtual void consume(CharStream *input); + virtual std::string getTokenName(size_t t); + + private: + void InitializeInstanceFields(); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerAction.h new file mode 100644 index 0000000..8e833b6 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerAction.h @@ -0,0 +1,66 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerActionType.h" +#include "antlr4-common.h" + +namespace antlr4 { +namespace atn { + + /// + /// Represents a single action which can be executed following the successful + /// match of a lexer rule. Lexer actions are used for both embedded action syntax + /// and ANTLR 4's new lexer command syntax. + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerAction { + public: + virtual ~LexerAction(); + + /// + /// Gets the serialization type of the lexer action. + /// + /// The serialization type of the lexer action. + virtual LexerActionType getActionType() const = 0; + + /// + /// Gets whether the lexer action is position-dependent. Position-dependent + /// actions may have different semantics depending on the + /// index at the time the action is executed. + /// + /// Many lexer commands, including {@code type}, {@code skip}, and + /// {@code more}, do not check the input index during their execution. + /// Actions like this are position-independent, and may be stored more + /// efficiently as part of the . + /// + /// {@code true} if the lexer action semantics can be affected by the + /// position of the input at the time it is executed; + /// otherwise, {@code false}. + virtual bool isPositionDependent() const = 0; + + /// + /// Execute the lexer action in the context of the specified . + /// + /// For position-dependent actions, the input stream must already be + /// positioned correctly prior to calling this method. + /// + /// The lexer instance. + virtual void execute(Lexer *lexer) = 0; + + virtual size_t hashCode() const = 0; + virtual bool operator == (const LexerAction &obj) const = 0; + virtual bool operator != (const LexerAction &obj) const { + return !(*this == obj); + } + + virtual std::string toString() const = 0; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionExecutor.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionExecutor.h new file mode 100644 index 0000000..488b54c --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionExecutor.h @@ -0,0 +1,115 @@ +/* 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. + */ + +#pragma once + +#include "CharStream.h" +#include "atn/LexerAction.h" + +namespace antlr4 { +namespace atn { + + /// Represents an executor for a sequence of lexer actions which traversed during + /// the matching operation of a lexer rule (token). + /// + /// The executor tracks position information for position-dependent lexer actions + /// efficiently, ensuring that actions appearing only at the end of the rule do + /// not cause bloating of the created for the lexer. + class ANTLR4CPP_PUBLIC LexerActionExecutor : public std::enable_shared_from_this { + public: + /// + /// Constructs an executor for a sequence of actions. + /// The lexer actions to execute. + LexerActionExecutor(const std::vector> &lexerActions); + virtual ~LexerActionExecutor(); + + /// + /// Creates a which executes the actions for + /// the input {@code lexerActionExecutor} followed by a specified + /// {@code lexerAction}. + /// + /// The executor for actions already traversed by + /// the lexer while matching a token within a particular + /// . If this is {@code null}, the method behaves as + /// though it were an empty executor. + /// The lexer action to execute after the actions + /// specified in {@code lexerActionExecutor}. + /// + /// A for executing the combine actions + /// of {@code lexerActionExecutor} and {@code lexerAction}. + static Ref append(Ref const& lexerActionExecutor, + Ref const& lexerAction); + + /// + /// Creates a which encodes the current offset + /// for position-dependent lexer actions. + /// + /// Normally, when the executor encounters lexer actions where + /// returns {@code true}, it calls + /// on the input to set the input + /// position to the end of the current token. This behavior provides + /// for efficient DFA representation of lexer actions which appear at the end + /// of a lexer rule, even when the lexer rule matches a variable number of + /// characters. + /// + /// Prior to traversing a match transition in the ATN, the current offset + /// from the token start index is assigned to all position-dependent lexer + /// actions which have not already been assigned a fixed offset. By storing + /// the offsets relative to the token start index, the DFA representation of + /// lexer actions which appear in the middle of tokens remains efficient due + /// to sharing among tokens of the same length, regardless of their absolute + /// position in the input stream. + /// + /// If the current executor already has offsets assigned to all + /// position-dependent lexer actions, the method returns {@code this}. + /// + /// The current offset to assign to all position-dependent + /// lexer actions which do not already have offsets assigned. + /// + /// A which stores input stream offsets + /// for all position-dependent lexer actions. + virtual Ref fixOffsetBeforeMatch(int offset); + + /// + /// Gets the lexer actions to be executed by this executor. + /// The lexer actions to be executed by this executor. + virtual std::vector> getLexerActions() const; + + /// + /// Execute the actions encapsulated by this executor within the context of a + /// particular . + /// + /// This method calls to set the position of the + /// {@code input} prior to calling + /// on a position-dependent action. Before the + /// method returns, the input position will be restored to the same position + /// it was in when the method was invoked. + /// + /// The lexer instance. + /// The input stream which is the source for the current token. + /// When this method is called, the current for + /// {@code input} should be the start of the following token, i.e. 1 + /// character past the end of the current token. + /// The token start index. This value may be passed to + /// to set the {@code input} position to the beginning + /// of the token. + virtual void execute(Lexer *lexer, CharStream *input, size_t startIndex); + + virtual size_t hashCode() const; + virtual bool operator == (const LexerActionExecutor &obj) const; + virtual bool operator != (const LexerActionExecutor &obj) const; + + private: + const std::vector> _lexerActions; + + /// Caches the result of since the hash code is an element + /// of the performance-critical operation. + const size_t _hashCode; + + size_t generateHashCode() const; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionType.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionType.h new file mode 100644 index 0000000..a72f15c --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerActionType.h @@ -0,0 +1,55 @@ +/* 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. + */ + +#pragma once + +#include "antlr4-common.h" + +namespace antlr4 { +namespace atn { + + /// + /// Represents the serialization type of a . + /// + /// @author Sam Harwell + /// @since 4.2 + /// + enum class LexerActionType : size_t { + /// + /// The type of a action. + /// + CHANNEL, + /// + /// The type of a action. + /// + CUSTOM, + /// + /// The type of a action. + /// + MODE, + /// + /// The type of a action. + /// + MORE, + /// + /// The type of a action. + /// + POP_MODE, + /// + /// The type of a action. + /// + PUSH_MODE, + /// + /// The type of a action. + /// + SKIP, + /// + /// The type of a action. + /// + TYPE, + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerChannelAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerChannelAction.h new file mode 100644 index 0000000..73e3a26 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerChannelAction.h @@ -0,0 +1,63 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/LexerActionType.h" + +namespace antlr4 { +namespace atn { + + using antlr4::Lexer; + + /// + /// Implements the {@code channel} lexer action by calling + /// with the assigned channel. + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerChannelAction final : public LexerAction { + public: + /// + /// Constructs a new {@code channel} action with the specified channel value. + /// The channel value to pass to . + LexerChannelAction(int channel); + + /// + /// Gets the channel to use for the created by the lexer. + /// + /// The channel to use for the created by the lexer. + int getChannel() const; + + /// + /// {@inheritDoc} + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code false}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// This action is implemented by calling with the + /// value provided by . + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + const int _channel; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerCustomAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerCustomAction.h new file mode 100644 index 0000000..bd1c5d3 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerCustomAction.h @@ -0,0 +1,87 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/LexerActionType.h" + +namespace antlr4 { +namespace atn { + + /// + /// Executes a custom lexer action by calling with the + /// rule and action indexes assigned to the custom action. The implementation of + /// a custom action is added to the generated code for the lexer in an override + /// of when the grammar is compiled. + /// + /// This class may represent embedded actions created with the {...} + /// syntax in ANTLR 4, as well as actions created for lexer commands where the + /// command argument could not be evaluated when the grammar was compiled. + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerCustomAction final : public LexerAction { + public: + /// + /// Constructs a custom lexer action with the specified rule and action + /// indexes. + /// + /// The rule index to use for calls to + /// . + /// The action index to use for calls to + /// . + LexerCustomAction(size_t ruleIndex, size_t actionIndex); + + /// + /// Gets the rule index to use for calls to . + /// + /// The rule index for the custom action. + size_t getRuleIndex() const; + + /// + /// Gets the action index to use for calls to . + /// + /// The action index for the custom action. + size_t getActionIndex() const; + + /// + /// {@inheritDoc} + /// + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// Gets whether the lexer action is position-dependent. Position-dependent + /// actions may have different semantics depending on the + /// index at the time the action is executed. + /// + /// Custom actions are position-dependent since they may represent a + /// user-defined embedded action which makes calls to methods like + /// . + /// + /// This method returns {@code true}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// Custom actions are implemented by calling with the + /// appropriate rule and action indexes. + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + const size_t _ruleIndex; + const size_t _actionIndex; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerIndexedCustomAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerIndexedCustomAction.h new file mode 100644 index 0000000..bb371f8 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerIndexedCustomAction.h @@ -0,0 +1,82 @@ +/* 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. + */ + +#pragma once + +#include "RuleContext.h" +#include "atn/LexerAction.h" + +namespace antlr4 { +namespace atn { + + /// + /// This implementation of is used for tracking input offsets + /// for position-dependent actions within a . + /// + /// This action is not serialized as part of the ATN, and is only required for + /// position-dependent lexer actions which appear at a location other than the + /// end of a rule. For more information about DFA optimizations employed for + /// lexer actions, see and + /// . + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerIndexedCustomAction final : public LexerAction { + public: + /// + /// Constructs a new indexed custom action by associating a character offset + /// with a . + /// + /// Note: This class is only required for lexer actions for which + /// returns {@code true}. + /// + /// The offset into the input , relative to + /// the token start index, at which the specified lexer action should be + /// executed. + /// The lexer action to execute at a particular offset in the + /// input . + LexerIndexedCustomAction(int offset, Ref const& action); + + /// + /// Gets the location in the input at which the lexer + /// action should be executed. The value is interpreted as an offset relative + /// to the token start index. + /// + /// The location in the input at which the lexer + /// action should be executed. + int getOffset() const; + + /// + /// Gets the lexer action to execute. + /// + /// A object which executes the lexer action. + Ref getAction() const; + + /// + /// {@inheritDoc} + /// + /// This method returns the result of calling + /// on the returned by . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code true}. + virtual bool isPositionDependent() const override; + + virtual void execute(Lexer *lexer) override; + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + const int _offset; + const Ref _action; + }; + +} // namespace atn +} // namespace antlr4 + diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerModeAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerModeAction.h new file mode 100644 index 0000000..49a858b --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerModeAction.h @@ -0,0 +1,61 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/LexerActionType.h" + +namespace antlr4 { +namespace atn { + + /// + /// Implements the {@code mode} lexer action by calling with + /// the assigned mode. + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerModeAction final : public LexerAction { + public: + /// + /// Constructs a new {@code mode} action with the specified mode value. + /// The mode value to pass to . + LexerModeAction(int mode); + + /// + /// Get the lexer mode this action should transition the lexer to. + /// + /// The lexer mode for this {@code mode} command. + int getMode(); + + /// + /// {@inheritDoc} + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code false}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// This action is implemented by calling with the + /// value provided by . + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + const int _mode; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerMoreAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerMoreAction.h new file mode 100644 index 0000000..ee3b2aa --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerMoreAction.h @@ -0,0 +1,57 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/LexerActionType.h" + +namespace antlr4 { +namespace atn { + + /// + /// Implements the {@code more} lexer action by calling . + /// + /// The {@code more} command does not have any parameters, so this action is + /// implemented as a singleton instance exposed by . + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerMoreAction final : public LexerAction { + public: + /// + /// Provides a singleton instance of this parameterless lexer action. + /// + static const Ref getInstance(); + + /// + /// {@inheritDoc} + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code false}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// This action is implemented by calling . + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + /// Constructs the singleton instance of the lexer {@code more} command. + LexerMoreAction(); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPopModeAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPopModeAction.h new file mode 100644 index 0000000..497305c --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPopModeAction.h @@ -0,0 +1,57 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/LexerActionType.h" + +namespace antlr4 { +namespace atn { + + /// + /// Implements the {@code popMode} lexer action by calling . + /// + /// The {@code popMode} command does not have any parameters, so this action is + /// implemented as a singleton instance exposed by . + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerPopModeAction final : public LexerAction { + public: + /// + /// Provides a singleton instance of this parameterless lexer action. + /// + static const Ref getInstance(); + + /// + /// {@inheritDoc} + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code false}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// This action is implemented by calling . + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + /// Constructs the singleton instance of the lexer {@code popMode} command. + LexerPopModeAction(); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPushModeAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPushModeAction.h new file mode 100644 index 0000000..43cb888 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerPushModeAction.h @@ -0,0 +1,61 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/LexerActionType.h" + +namespace antlr4 { +namespace atn { + + /// + /// Implements the {@code pushMode} lexer action by calling + /// with the assigned mode. + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerPushModeAction final : public LexerAction { + public: + /// + /// Constructs a new {@code pushMode} action with the specified mode value. + /// The mode value to pass to . + LexerPushModeAction(int mode); + + /// + /// Get the lexer mode this action should transition the lexer to. + /// + /// The lexer mode for this {@code pushMode} command. + int getMode() const; + + /// + /// {@inheritDoc} + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code false}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// This action is implemented by calling with the + /// value provided by . + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + const int _mode; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerSkipAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerSkipAction.h new file mode 100644 index 0000000..5bd2e1c --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerSkipAction.h @@ -0,0 +1,55 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerAction.h" +#include "atn/LexerActionType.h" + +namespace antlr4 { +namespace atn { + + /// + /// Implements the {@code skip} lexer action by calling . + /// + /// The {@code skip} command does not have any parameters, so this action is + /// implemented as a singleton instance exposed by . + /// + /// @author Sam Harwell + /// @since 4.2 + /// + class ANTLR4CPP_PUBLIC LexerSkipAction final : public LexerAction { + public: + /// Provides a singleton instance of this parameterless lexer action. + static const Ref getInstance(); + + /// + /// {@inheritDoc} + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code false}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// This action is implemented by calling . + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + /// Constructs the singleton instance of the lexer {@code skip} command. + LexerSkipAction(); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerTypeAction.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerTypeAction.h new file mode 100644 index 0000000..1c4a8a1 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LexerTypeAction.h @@ -0,0 +1,55 @@ +/* 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. + */ + +#pragma once + +#include "atn/LexerActionType.h" +#include "atn/LexerAction.h" + +namespace antlr4 { +namespace atn { + + /// Implements the {@code type} lexer action by calling + /// with the assigned type. + class ANTLR4CPP_PUBLIC LexerTypeAction : public LexerAction { + public: + /// + /// Constructs a new {@code type} action with the specified token type value. + /// The type to assign to the token using . + LexerTypeAction(int type); + + /// + /// Gets the type to assign to a token created by the lexer. + /// The type to assign to a token created by the lexer. + virtual int getType() const; + + /// + /// {@inheritDoc} + /// This method returns . + virtual LexerActionType getActionType() const override; + + /// + /// {@inheritDoc} + /// This method returns {@code false}. + virtual bool isPositionDependent() const override; + + /// + /// {@inheritDoc} + /// + /// This action is implemented by calling with the + /// value provided by . + /// + virtual void execute(Lexer *lexer) override; + + virtual size_t hashCode() const override; + virtual bool operator == (const LexerAction &obj) const override; + virtual std::string toString() const override; + + private: + const int _type; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LookaheadEventInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LookaheadEventInfo.h new file mode 100644 index 0000000..f5fc24f --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LookaheadEventInfo.h @@ -0,0 +1,42 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionEventInfo.h" + +namespace antlr4 { +namespace atn { + + /// This class represents profiling event information for tracking the lookahead + /// depth required in order to make a prediction. + class ANTLR4CPP_PUBLIC LookaheadEventInfo : public DecisionEventInfo { + public: + /// The alternative chosen by adaptivePredict(), not necessarily + /// the outermost alt shown for a rule; left-recursive rules have + /// user-level alts that differ from the rewritten rule with a (...) block + /// and a (..)* loop. + size_t predictedAlt = 0; + + /// + /// Constructs a new instance of the class with + /// the specified detailed lookahead information. + /// + /// The decision number + /// The final configuration set containing the necessary + /// information to determine the result of a prediction, or {@code null} if + /// the final configuration set is not available + /// The input token stream + /// The start index for the current prediction + /// The index at which the prediction was finally made + /// {@code true} if the current lookahead is part of an LL + /// prediction; otherwise, {@code false} if the current lookahead is part of + /// an SLL prediction + LookaheadEventInfo(size_t decision, ATNConfigSet *configs, size_t predictedAlt, TokenStream *input, size_t startIndex, + size_t stopIndex, bool fullCtx); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LoopEndState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LoopEndState.h new file mode 100644 index 0000000..c90efa3 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/LoopEndState.h @@ -0,0 +1,22 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + /// Mark the end of a * or + loop. + class ANTLR4CPP_PUBLIC LoopEndState final : public ATNState { + public: + ATNState *loopBackState = nullptr; + + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/NotSetTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/NotSetTransition.h new file mode 100644 index 0000000..214fb06 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/NotSetTransition.h @@ -0,0 +1,25 @@ +/* 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. + */ + +#pragma once + +#include "atn/SetTransition.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC NotSetTransition final : public SetTransition { + public: + NotSetTransition(ATNState *target, const misc::IntervalSet &set); + + virtual SerializationType getSerializationType() const override; + + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/OrderedATNConfigSet.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/OrderedATNConfigSet.h new file mode 100644 index 0000000..4ce43bb --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/OrderedATNConfigSet.h @@ -0,0 +1,20 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNConfigSet.h" +#include "atn/ATNConfig.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC OrderedATNConfigSet : public ATNConfigSet { + protected: + virtual size_t getHash(ATNConfig *c) override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParseInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParseInfo.h new file mode 100644 index 0000000..7ced7de --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParseInfo.h @@ -0,0 +1,102 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionInfo.h" + +namespace antlr4 { +namespace atn { + + class ProfilingATNSimulator; + + /// This class provides access to specific and aggregate statistics gathered + /// during profiling of a parser. + class ANTLR4CPP_PUBLIC ParseInfo { + public: + ParseInfo(ProfilingATNSimulator *atnSimulator); + ParseInfo(ParseInfo const&) = default; + virtual ~ParseInfo(); + + ParseInfo& operator=(ParseInfo const&) = default; + + /// + /// Gets an array of instances containing the profiling + /// information gathered for each decision in the ATN. + /// + /// An array of instances, indexed by decision + /// number. + virtual std::vector getDecisionInfo(); + + /// + /// Gets the decision numbers for decisions that required one or more + /// full-context predictions during parsing. These are decisions for which + /// is non-zero. + /// + /// A list of decision numbers which required one or more + /// full-context predictions during parsing. + virtual std::vector getLLDecisions(); + + /// + /// Gets the total time spent during prediction across all decisions made + /// during parsing. This value is the sum of + /// for all decisions. + /// + virtual long long getTotalTimeInPrediction(); + + /// + /// Gets the total number of SLL lookahead operations across all decisions + /// made during parsing. This value is the sum of + /// for all decisions. + /// + virtual long long getTotalSLLLookaheadOps(); + + /// + /// Gets the total number of LL lookahead operations across all decisions + /// made during parsing. This value is the sum of + /// for all decisions. + /// + virtual long long getTotalLLLookaheadOps(); + + /// + /// Gets the total number of ATN lookahead operations for SLL prediction + /// across all decisions made during parsing. + /// + virtual long long getTotalSLLATNLookaheadOps(); + + /// + /// Gets the total number of ATN lookahead operations for LL prediction + /// across all decisions made during parsing. + /// + virtual long long getTotalLLATNLookaheadOps(); + + /// + /// Gets the total number of ATN lookahead operations for SLL and LL + /// prediction across all decisions made during parsing. + /// + /// + /// This value is the sum of and + /// . + /// + virtual long long getTotalATNLookaheadOps(); + + /// + /// Gets the total number of DFA states stored in the DFA cache for all + /// decisions in the ATN. + /// + virtual size_t getDFASize(); + + /// + /// Gets the total number of DFA states stored in the DFA cache for a + /// particular decision. + /// + virtual size_t getDFASize(size_t decision); + + protected: + const ProfilingATNSimulator *_atnSimulator; // non-owning, we are created by this simulator. + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParserATNSimulator.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParserATNSimulator.h new file mode 100644 index 0000000..6520a44 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ParserATNSimulator.h @@ -0,0 +1,904 @@ +/* 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. + */ + +#pragma once + +#include "PredictionMode.h" +#include "dfa/DFAState.h" +#include "atn/ATNSimulator.h" +#include "atn/PredictionContext.h" +#include "SemanticContext.h" +#include "atn/ATNConfig.h" + +namespace antlr4 { +namespace atn { + + /** + * The embodiment of the adaptive LL(*), ALL(*), parsing strategy. + * + *

+ * The basic complexity of the adaptive strategy makes it harder to understand. + * We begin with ATN simulation to build paths in a DFA. Subsequent prediction + * requests go through the DFA first. If they reach a state without an edge for + * the current symbol, the algorithm fails over to the ATN simulation to + * complete the DFA path for the current input (until it finds a conflict state + * or uniquely predicting state).

+ * + *

+ * All of that is done without using the outer context because we want to create + * a DFA that is not dependent upon the rule invocation stack when we do a + * prediction. One DFA works in all contexts. We avoid using context not + * necessarily because it's slower, although it can be, but because of the DFA + * caching problem. The closure routine only considers the rule invocation stack + * created during prediction beginning in the decision rule. For example, if + * prediction occurs without invoking another rule's ATN, there are no context + * stacks in the configurations. When lack of context leads to a conflict, we + * don't know if it's an ambiguity or a weakness in the strong LL(*) parsing + * strategy (versus full LL(*)).

+ * + *

+ * When SLL yields a configuration set with conflict, we rewind the input and + * retry the ATN simulation, this time using full outer context without adding + * to the DFA. Configuration context stacks will be the full invocation stacks + * from the start rule. If we get a conflict using full context, then we can + * definitively say we have a true ambiguity for that input sequence. If we + * don't get a conflict, it implies that the decision is sensitive to the outer + * context. (It is not context-sensitive in the sense of context-sensitive + * grammars.)

+ * + *

+ * The next time we reach this DFA state with an SLL conflict, through DFA + * simulation, we will again retry the ATN simulation using full context mode. + * This is slow because we can't save the results and have to "interpret" the + * ATN each time we get that input.

+ * + *

+ * CACHING FULL CONTEXT PREDICTIONS

+ * + *

+ * We could cache results from full context to predicted alternative easily and + * that saves a lot of time but doesn't work in presence of predicates. The set + * of visible predicates from the ATN start state changes depending on the + * context, because closure can fall off the end of a rule. I tried to cache + * tuples (stack context, semantic context, predicted alt) but it was slower + * than interpreting and much more complicated. Also required a huge amount of + * memory. The goal is not to create the world's fastest parser anyway. I'd like + * to keep this algorithm simple. By launching multiple threads, we can improve + * the speed of parsing across a large number of files.

+ * + *

+ * There is no strict ordering between the amount of input used by SLL vs LL, + * which makes it really hard to build a cache for full context. Let's say that + * we have input A B C that leads to an SLL conflict with full context X. That + * implies that using X we might only use A B but we could also use A B C D to + * resolve conflict. Input A B C D could predict alternative 1 in one position + * in the input and A B C E could predict alternative 2 in another position in + * input. The conflicting SLL configurations could still be non-unique in the + * full context prediction, which would lead us to requiring more input than the + * original A B C. To make a prediction cache work, we have to track the exact + * input used during the previous prediction. That amounts to a cache that maps + * X to a specific DFA for that context.

+ * + *

+ * Something should be done for left-recursive expression predictions. They are + * likely LL(1) + pred eval. Easier to do the whole SLL unless error and retry + * with full LL thing Sam does.

+ * + *

+ * AVOIDING FULL CONTEXT PREDICTION

+ * + *

+ * We avoid doing full context retry when the outer context is empty, we did not + * dip into the outer context by falling off the end of the decision state rule, + * or when we force SLL mode.

+ * + *

+ * As an example of the not dip into outer context case, consider as super + * constructor calls versus function calls. One grammar might look like + * this:

+ * + * 
+   * ctorBody
+   *   : '{' superCall? stat* '}'
+   *   ;
+   *
+ * + *

+ * Or, you might see something like

+ * + * 
+   * stat
+   *   : superCall ';'
+   *   | expression ';'
+   *   | ...
+   *   ;
+   *
+ * + *

+ * In both cases I believe that no closure operations will dip into the outer + * context. In the first case ctorBody in the worst case will stop at the '}'. + * In the 2nd case it should stop at the ';'. Both cases should stay within the + * entry rule and not dip into the outer context.

+ * + *

+ * PREDICATES

+ * + *

+ * Predicates are always evaluated if present in either SLL or LL both. SLL and + * LL simulation deals with predicates differently. SLL collects predicates as + * it performs closure operations like ANTLR v3 did. It delays predicate + * evaluation until it reaches and accept state. This allows us to cache the SLL + * ATN simulation whereas, if we had evaluated predicates on-the-fly during + * closure, the DFA state configuration sets would be different and we couldn't + * build up a suitable DFA.

+ * + *

+ * When building a DFA accept state during ATN simulation, we evaluate any + * predicates and return the sole semantically valid alternative. If there is + * more than 1 alternative, we report an ambiguity. If there are 0 alternatives, + * we throw an exception. Alternatives without predicates act like they have + * true predicates. The simple way to think about it is to strip away all + * alternatives with false predicates and choose the minimum alternative that + * remains.

+ * + *

+ * When we start in the DFA and reach an accept state that's predicated, we test + * those and return the minimum semantically viable alternative. If no + * alternatives are viable, we throw an exception.

+ * + *

+ * During full LL ATN simulation, closure always evaluates predicates and + * on-the-fly. This is crucial to reducing the configuration set size during + * closure. It hits a landmine when parsing with the Java grammar, for example, + * without this on-the-fly evaluation.

+ * + *

+ * SHARING DFA

+ * + *

+ * All instances of the same parser share the same decision DFAs through a + * static field. Each instance gets its own ATN simulator but they share the + * same {@link #decisionToDFA} field. They also share a + * {@link PredictionContextCache} object that makes sure that all + * {@link PredictionContext} objects are shared among the DFA states. This makes + * a big size difference.

+ * + *

+ * THREAD SAFETY

+ * + *

+ * The {@link ParserATNSimulator} locks on the {@link #decisionToDFA} field when + * it adds a new DFA object to that array. {@link #addDFAEdge} + * locks on the DFA for the current decision when setting the + * {@link DFAState#edges} field. {@link #addDFAState} locks on + * the DFA for the current decision when looking up a DFA state to see if it + * already exists. We must make sure that all requests to add DFA states that + * are equivalent result in the same shared DFA object. This is because lots of + * threads will be trying to update the DFA at once. The + * {@link #addDFAState} method also locks inside the DFA lock + * but this time on the shared context cache when it rebuilds the + * configurations' {@link PredictionContext} objects using cached + * subgraphs/nodes. No other locking occurs, even during DFA simulation. This is + * safe as long as we can guarantee that all threads referencing + * {@code s.edge[t]} get the same physical target {@link DFAState}, or + * {@code null}. Once into the DFA, the DFA simulation does not reference the + * {@link DFA#states} map. It follows the {@link DFAState#edges} field to new + * targets. The DFA simulator will either find {@link DFAState#edges} to be + * {@code null}, to be non-{@code null} and {@code dfa.edges[t]} null, or + * {@code dfa.edges[t]} to be non-null. The + * {@link #addDFAEdge} method could be racing to set the field + * but in either case the DFA simulator works; if {@code null}, and requests ATN + * simulation. It could also race trying to get {@code dfa.edges[t]}, but either + * way it will work because it's not doing a test and set operation.

+ * + *

+ * Starting with SLL then failing to combined SLL/LL (Two-Stage + * Parsing)

+ * + *

+ * Sam pointed out that if SLL does not give a syntax error, then there is no + * point in doing full LL, which is slower. We only have to try LL if we get a + * syntax error. For maximum speed, Sam starts the parser set to pure SLL + * mode with the {@link BailErrorStrategy}:

+ * + * 
+   * parser.{@link Parser#getInterpreter() getInterpreter()}.{@link #setPredictionMode setPredictionMode}{@code (}{@link PredictionMode#SLL}{@code )};
+   * parser.{@link Parser#setErrorHandler setErrorHandler}(new {@link BailErrorStrategy}());
+   *
+ * + *

+ * If it does not get a syntax error, then we're done. If it does get a syntax + * error, we need to retry with the combined SLL/LL strategy.

+ * + *

+ * The reason this works is as follows. If there are no SLL conflicts, then the + * grammar is SLL (at least for that input set). If there is an SLL conflict, + * the full LL analysis must yield a set of viable alternatives which is a + * subset of the alternatives reported by SLL. If the LL set is a singleton, + * then the grammar is LL but not SLL. If the LL set is the same size as the SLL + * set, the decision is SLL. If the LL set has size > 1, then that decision + * is truly ambiguous on the current input. If the LL set is smaller, then the + * SLL conflict resolution might choose an alternative that the full LL would + * rule out as a possibility based upon better context information. If that's + * the case, then the SLL parse will definitely get an error because the full LL + * analysis says it's not viable. If SLL conflict resolution chooses an + * alternative within the LL set, them both SLL and LL would choose the same + * alternative because they both choose the minimum of multiple conflicting + * alternatives.

+ * + *

+ * Let's say we have a set of SLL conflicting alternatives {@code {1, 2, 3}} and + * a smaller LL set called s. If s is {@code {2, 3}}, then SLL + * parsing will get an error because SLL will pursue alternative 1. If + * s is {@code {1, 2}} or {@code {1, 3}} then both SLL and LL will + * choose the same alternative because alternative one is the minimum of either + * set. If s is {@code {2}} or {@code {3}} then SLL will get a syntax + * error. If s is {@code {1}} then SLL will succeed.

+ * + *

+ * Of course, if the input is invalid, then we will get an error for sure in + * both SLL and LL parsing. Erroneous input will therefore require 2 passes over + * the input.

+ */ + class ANTLR4CPP_PUBLIC ParserATNSimulator : public ATNSimulator { + public: + /// Testing only! + ParserATNSimulator(const ATN &atn, std::vector &decisionToDFA, + PredictionContextCache &sharedContextCache); + + ParserATNSimulator(Parser *parser, const ATN &atn, std::vector &decisionToDFA, + PredictionContextCache &sharedContextCache); + + virtual void reset() override; + virtual void clearDFA() override; + virtual size_t adaptivePredict(TokenStream *input, size_t decision, ParserRuleContext *outerContext); + + static const bool TURN_OFF_LR_LOOP_ENTRY_BRANCH_OPT; + + std::vector &decisionToDFA; + + /** Implements first-edge (loop entry) elimination as an optimization + * during closure operations. See antlr/antlr4#1398. + * + * The optimization is to avoid adding the loop entry config when + * the exit path can only lead back to the same + * StarLoopEntryState after popping context at the rule end state + * (traversing only epsilon edges, so we're still in closure, in + * this same rule). + * + * We need to detect any state that can reach loop entry on + * epsilon w/o exiting rule. We don't have to look at FOLLOW + * links, just ensure that all stack tops for config refer to key + * states in LR rule. + * + * To verify we are in the right situation we must first check + * closure is at a StarLoopEntryState generated during LR removal. + * Then we check that each stack top of context is a return state + * from one of these cases: + * + * 1. 'not' expr, '(' type ')' expr. The return state points at loop entry state + * 2. expr op expr. The return state is the block end of internal block of (...)* + * 3. 'between' expr 'and' expr. The return state of 2nd expr reference. + * That state points at block end of internal block of (...)*. + * 4. expr '?' expr ':' expr. The return state points at block end, + * which points at loop entry state. + * + * If any is true for each stack top, then closure does not add a + * config to the current config set for edge[0], the loop entry branch. + * + * Conditions fail if any context for the current config is: + * + * a. empty (we'd fall out of expr to do a global FOLLOW which could + * even be to some weird spot in expr) or, + * b. lies outside of expr or, + * c. lies within expr but at a state not the BlockEndState + * generated during LR removal + * + * Do we need to evaluate predicates ever in closure for this case? + * + * No. Predicates, including precedence predicates, are only + * evaluated when computing a DFA start state. I.e., only before + * the lookahead (but not parser) consumes a token. + * + * There are no epsilon edges allowed in LR rule alt blocks or in + * the "primary" part (ID here). If closure is in + * StarLoopEntryState any lookahead operation will have consumed a + * token as there are no epsilon-paths that lead to + * StarLoopEntryState. We do not have to evaluate predicates + * therefore if we are in the generated StarLoopEntryState of a LR + * rule. Note that when making a prediction starting at that + * decision point, decision d=2, compute-start-state performs + * closure starting at edges[0], edges[1] emanating from + * StarLoopEntryState. That means it is not performing closure on + * StarLoopEntryState during compute-start-state. + * + * How do we know this always gives same prediction answer? + * + * Without predicates, loop entry and exit paths are ambiguous + * upon remaining input +b (in, say, a+b). Either paths lead to + * valid parses. Closure can lead to consuming + immediately or by + * falling out of this call to expr back into expr and loop back + * again to StarLoopEntryState to match +b. In this special case, + * we choose the more efficient path, which is to take the bypass + * path. + * + * The lookahead language has not changed because closure chooses + * one path over the other. Both paths lead to consuming the same + * remaining input during a lookahead operation. If the next token + * is an operator, lookahead will enter the choice block with + * operators. If it is not, lookahead will exit expr. Same as if + * closure had chosen to enter the choice block immediately. + * + * Closure is examining one config (some loopentrystate, some alt, + * context) which means it is considering exactly one alt. Closure + * always copies the same alt to any derived configs. + * + * How do we know this optimization doesn't mess up precedence in + * our parse trees? + * + * Looking through expr from left edge of stat only has to confirm + * that an input, say, a+b+c; begins with any valid interpretation + * of an expression. The precedence actually doesn't matter when + * making a decision in stat seeing through expr. It is only when + * parsing rule expr that we must use the precedence to get the + * right interpretation and, hence, parse tree. + */ + bool canDropLoopEntryEdgeInLeftRecursiveRule(ATNConfig *config) const; + virtual std::string getRuleName(size_t index); + + virtual Ref precedenceTransition(Ref const& config, PrecedencePredicateTransition *pt, + bool collectPredicates, bool inContext, bool fullCtx); + + void setPredictionMode(PredictionMode newMode); + PredictionMode getPredictionMode(); + + Parser* getParser(); + + virtual std::string getTokenName(size_t t); + + virtual std::string getLookaheadName(TokenStream *input); + + /// + /// Used for debugging in adaptivePredict around execATN but I cut + /// it out for clarity now that alg. works well. We can leave this + /// "dead" code for a bit. + /// + virtual void dumpDeadEndConfigs(NoViableAltException &nvae); + + protected: + Parser *const parser; + + /// + /// Each prediction operation uses a cache for merge of prediction contexts. + /// Don't keep around as it wastes huge amounts of memory. The merge cache + /// isn't synchronized but we're ok since two threads shouldn't reuse same + /// parser/atnsim object because it can only handle one input at a time. + /// This maps graphs a and b to merged result c. (a,b)->c. We can avoid + /// the merge if we ever see a and b again. Note that (b,a)->c should + /// also be examined during cache lookup. + /// + PredictionContextMergeCache mergeCache; + + // LAME globals to avoid parameters!!!!! I need these down deep in predTransition + TokenStream *_input; + size_t _startIndex; + ParserRuleContext *_outerContext; + dfa::DFA *_dfa; // Reference into the decisionToDFA vector. + + /// + /// Performs ATN simulation to compute a predicted alternative based + /// upon the remaining input, but also updates the DFA cache to avoid + /// having to traverse the ATN again for the same input sequence. + /// + /// There are some key conditions we're looking for after computing a new + /// set of ATN configs (proposed DFA state): + /// if the set is empty, there is no viable alternative for current symbol + /// does the state uniquely predict an alternative? + /// does the state have a conflict that would prevent us from + /// putting it on the work list? + /// + /// We also have some key operations to do: + /// add an edge from previous DFA state to potentially new DFA state, D, + /// upon current symbol but only if adding to work list, which means in all + /// cases except no viable alternative (and possibly non-greedy decisions?) + /// collecting predicates and adding semantic context to DFA accept states + /// adding rule context to context-sensitive DFA accept states + /// consuming an input symbol + /// reporting a conflict + /// reporting an ambiguity + /// reporting a context sensitivity + /// reporting insufficient predicates + /// + /// cover these cases: + /// dead end + /// single alt + /// single alt + preds + /// conflict + /// conflict + preds + /// + virtual size_t execATN(dfa::DFA &dfa, dfa::DFAState *s0, TokenStream *input, size_t startIndex, + ParserRuleContext *outerContext); + + /// + /// Get an existing target state for an edge in the DFA. If the target state + /// for the edge has not yet been computed or is otherwise not available, + /// this method returns {@code null}. + /// + /// The current DFA state + /// The next input symbol + /// The existing target DFA state for the given input symbol + /// {@code t}, or {@code null} if the target state for this edge is not + /// already cached + virtual dfa::DFAState* getExistingTargetState(dfa::DFAState *previousD, size_t t); + + /// + /// Compute a target state for an edge in the DFA, and attempt to add the + /// computed state and corresponding edge to the DFA. + /// + /// The DFA + /// The current DFA state + /// The next input symbol + /// + /// The computed target DFA state for the given input symbol + /// {@code t}. If {@code t} does not lead to a valid DFA state, this method + /// returns . + virtual dfa::DFAState *computeTargetState(dfa::DFA &dfa, dfa::DFAState *previousD, size_t t); + + virtual void predicateDFAState(dfa::DFAState *dfaState, DecisionState *decisionState); + + // comes back with reach.uniqueAlt set to a valid alt + virtual size_t execATNWithFullContext(dfa::DFA &dfa, dfa::DFAState *D, ATNConfigSet *s0, + TokenStream *input, size_t startIndex, ParserRuleContext *outerContext); // how far we got before failing over + + virtual std::unique_ptr computeReachSet(ATNConfigSet *closure, size_t t, bool fullCtx); + + /// + /// Return a configuration set containing only the configurations from + /// {@code configs} which are in a . If all + /// configurations in {@code configs} are already in a rule stop state, this + /// method simply returns {@code configs}. + ///

+ /// When {@code lookToEndOfRule} is true, this method uses + /// for each configuration in {@code configs} which is + /// not already in a rule stop state to see if a rule stop state is reachable + /// from the configuration via epsilon-only transitions. + ///

+ /// the configuration set to update + /// when true, this method checks for rule stop states + /// reachable by epsilon-only transitions from each configuration in + /// {@code configs}. + /// + /// {@code configs} if all configurations in {@code configs} are in a + /// rule stop state, otherwise return a new configuration set containing only + /// the configurations from {@code configs} which are in a rule stop state + virtual ATNConfigSet* removeAllConfigsNotInRuleStopState(ATNConfigSet *configs, bool lookToEndOfRule); + + virtual std::unique_ptr computeStartState(ATNState *p, RuleContext *ctx, bool fullCtx); + + /* parrt internal source braindump that doesn't mess up + * external API spec. + + applyPrecedenceFilter is an optimization to avoid highly + nonlinear prediction of expressions and other left recursive + rules. The precedence predicates such as {3>=prec}? Are highly + context-sensitive in that they can only be properly evaluated + in the context of the proper prec argument. Without pruning, + these predicates are normal predicates evaluated when we reach + conflict state (or unique prediction). As we cannot evaluate + these predicates out of context, the resulting conflict leads + to full LL evaluation and nonlinear prediction which shows up + very clearly with fairly large expressions. + + Example grammar: + + e : e '*' e + | e '+' e + | INT + ; + + We convert that to the following: + + e[int prec] + : INT + ( {3>=prec}? '*' e[4] + | {2>=prec}? '+' e[3] + )* + ; + + The (..)* loop has a decision for the inner block as well as + an enter or exit decision, which is what concerns us here. At + the 1st + of input 1+2+3, the loop entry sees both predicates + and the loop exit also sees both predicates by falling off the + edge of e. This is because we have no stack information with + SLL and find the follow of e, which will hit the return states + inside the loop after e[4] and e[3], which brings it back to + the enter or exit decision. In this case, we know that we + cannot evaluate those predicates because we have fallen off + the edge of the stack and will in general not know which prec + parameter is the right one to use in the predicate. + + Because we have special information, that these are precedence + predicates, we can resolve them without failing over to full + LL despite their context sensitive nature. We make an + assumption that prec[-1] <= prec[0], meaning that the current + precedence level is greater than or equal to the precedence + level of recursive invocations above us in the stack. For + example, if predicate {3>=prec}? is true of the current prec, + then one option is to enter the loop to match it now. The + other option is to exit the loop and the left recursive rule + to match the current operator in rule invocation further up + the stack. But, we know that all of those prec are lower or + the same value and so we can decide to enter the loop instead + of matching it later. That means we can strip out the other + configuration for the exit branch. + + So imagine we have (14,1,$,{2>=prec}?) and then + (14,2,$-dipsIntoOuterContext,{2>=prec}?). The optimization + allows us to collapse these two configurations. We know that + if {2>=prec}? is true for the current prec parameter, it will + also be true for any prec from an invoking e call, indicated + by dipsIntoOuterContext. As the predicates are both true, we + have the option to evaluate them early in the decision start + state. We do this by stripping both predicates and choosing to + enter the loop as it is consistent with the notion of operator + precedence. It's also how the full LL conflict resolution + would work. + + The solution requires a different DFA start state for each + precedence level. + + The basic filter mechanism is to remove configurations of the + form (p, 2, pi) if (p, 1, pi) exists for the same p and pi. In + other words, for the same ATN state and predicate context, + remove any configuration associated with an exit branch if + there is a configuration associated with the enter branch. + + It's also the case that the filter evaluates precedence + predicates and resolves conflicts according to precedence + levels. For example, for input 1+2+3 at the first +, we see + prediction filtering + + [(11,1,[$],{3>=prec}?), (14,1,[$],{2>=prec}?), (5,2,[$],up=1), + (11,2,[$],up=1), (14,2,[$],up=1)],hasSemanticContext=true,dipsIntoOuterContext + + to + + [(11,1,[$]), (14,1,[$]), (5,2,[$],up=1)],dipsIntoOuterContext + + This filters because {3>=prec}? evals to true and collapses + (11,1,[$],{3>=prec}?) and (11,2,[$],up=1) since early conflict + resolution based upon rules of operator precedence fits with + our usual match first alt upon conflict. + + We noticed a problem where a recursive call resets precedence + to 0. Sam's fix: each config has flag indicating if it has + returned from an expr[0] call. then just don't filter any + config with that flag set. flag is carried along in + closure(). so to avoid adding field, set bit just under sign + bit of dipsIntoOuterContext (SUPPRESS_PRECEDENCE_FILTER). + With the change you filter "unless (p, 2, pi) was reached + after leaving the rule stop state of the LR rule containing + state p, corresponding to a rule invocation with precedence + level 0" + */ + + /** + * This method transforms the start state computed by + * {@link #computeStartState} to the special start state used by a + * precedence DFA for a particular precedence value. The transformation + * process applies the following changes to the start state's configuration + * set. + * + *
    + *
  1. Evaluate the precedence predicates for each configuration using + * {@link SemanticContext#evalPrecedence}.
    2. + *
  2. When {@link ATNConfig#isPrecedenceFilterSuppressed} is {@code false}, + * remove all configurations which predict an alternative greater than 1, + * for which another configuration that predicts alternative 1 is in the + * same ATN state with the same prediction context. This transformation is + * valid for the following reasons: + *
      + *
    • The closure block cannot contain any epsilon transitions which bypass + * the body of the closure, so all states reachable via alternative 1 are + * part of the precedence alternatives of the transformed left-recursive + * rule.
      • + *
    • The "primary" portion of a left recursive rule cannot contain an + * epsilon transition, so the only way an alternative other than 1 can exist + * in a state that is also reachable via alternative 1 is by nesting calls + * to the left-recursive rule, with the outer calls not being at the + * preferred precedence level. The + * {@link ATNConfig#isPrecedenceFilterSuppressed} property marks ATN + * configurations which do not meet this condition, and therefore are not + * eligible for elimination during the filtering process.
      • + *
    + *
    3. + *
+ * + *

+ * The prediction context must be considered by this filter to address + * situations like the following. + *

+ * + * 
+     * grammar TA;
+     * prog: statement* EOF;
+     * statement: letterA | statement letterA 'b' ;
+     * letterA: 'a';
+     *
+ * + *

+ * If the above grammar, the ATN state immediately before the token + * reference {@code 'a'} in {@code letterA} is reachable from the left edge + * of both the primary and closure blocks of the left-recursive rule + * {@code statement}. The prediction context associated with each of these + * configurations distinguishes between them, and prevents the alternative + * which stepped out to {@code prog} (and then back in to {@code statement} + * from being eliminated by the filter. + *

+ * + * @param configs The configuration set computed by + * {@link #computeStartState} as the start state for the DFA. + * @return The transformed configuration set representing the start state + * for a precedence DFA at a particular precedence level (determined by + * calling {@link Parser#getPrecedence}). + */ + std::unique_ptr applyPrecedenceFilter(ATNConfigSet *configs); + + virtual ATNState *getReachableTarget(Transition *trans, size_t ttype); + + virtual std::vector> getPredsForAmbigAlts(const antlrcpp::BitSet &ambigAlts, + ATNConfigSet *configs, size_t nalts); + + virtual std::vector getPredicatePredictions(const antlrcpp::BitSet &ambigAlts, + std::vector> const& altToPred); + + /** + * This method is used to improve the localization of error messages by + * choosing an alternative rather than throwing a + * {@link NoViableAltException} in particular prediction scenarios where the + * {@link #ERROR} state was reached during ATN simulation. + * + *

+ * The default implementation of this method uses the following + * algorithm to identify an ATN configuration which successfully parsed the + * decision entry rule. Choosing such an alternative ensures that the + * {@link ParserRuleContext} returned by the calling rule will be complete + * and valid, and the syntax error will be reported later at a more + * localized location.

+ * + *
    + *
  • If a syntactically valid path or paths reach the end of the decision rule and + * they are semantically valid if predicated, return the min associated alt.
    • + *
  • Else, if a semantically invalid but syntactically valid path exist + * or paths exist, return the minimum associated alt. + *
    • + *
  • Otherwise, return {@link ATN#INVALID_ALT_NUMBER}.
    • + *
+ * + *

+ * In some scenarios, the algorithm described above could predict an + * alternative which will result in a {@link FailedPredicateException} in + * the parser. Specifically, this could occur if the only configuration + * capable of successfully parsing to the end of the decision rule is + * blocked by a semantic predicate. By choosing this alternative within + * {@link #adaptivePredict} instead of throwing a + * {@link NoViableAltException}, the resulting + * {@link FailedPredicateException} in the parser will identify the specific + * predicate which is preventing the parser from successfully parsing the + * decision rule, which helps developers identify and correct logic errors + * in semantic predicates. + *

+ * + * @param configs The ATN configurations which were valid immediately before + * the {@link #ERROR} state was reached + * @param outerContext The is the \gamma_0 initial parser context from the paper + * or the parser stack at the instant before prediction commences. + * + * @return The value to return from {@link #adaptivePredict}, or + * {@link ATN#INVALID_ALT_NUMBER} if a suitable alternative was not + * identified and {@link #adaptivePredict} should report an error instead. + */ + size_t getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule(ATNConfigSet *configs, + ParserRuleContext *outerContext); + + virtual size_t getAltThatFinishedDecisionEntryRule(ATNConfigSet *configs); + + /** Walk the list of configurations and split them according to + * those that have preds evaluating to true/false. If no pred, assume + * true pred and include in succeeded set. Returns Pair of sets. + * + * Create a new set so as not to alter the incoming parameter. + * + * Assumption: the input stream has been restored to the starting point + * prediction, which is where predicates need to evaluate. + */ + std::pair splitAccordingToSemanticValidity(ATNConfigSet *configs, + ParserRuleContext *outerContext); + + /// + /// Look through a list of predicate/alt pairs, returning alts for the + /// pairs that win. A {@code NONE} predicate indicates an alt containing an + /// unpredicated config which behaves as "always true." If !complete + /// then we stop at the first predicate that evaluates to true. This + /// includes pairs with null predicates. + /// + virtual antlrcpp::BitSet evalSemanticContext(std::vector predPredictions, + ParserRuleContext *outerContext, bool complete); + + /** + * Evaluate a semantic context within a specific parser context. + * + *

+ * This method might not be called for every semantic context evaluated + * during the prediction process. In particular, we currently do not + * evaluate the following but it may change in the future:

+ * + *
    + *
  • Precedence predicates (represented by + * {@link SemanticContext.PrecedencePredicate}) are not currently evaluated + * through this method.
    • + *
  • Operator predicates (represented by {@link SemanticContext.AND} and + * {@link SemanticContext.OR}) are evaluated as a single semantic + * context, rather than evaluating the operands individually. + * Implementations which require evaluation results from individual + * predicates should override this method to explicitly handle evaluation of + * the operands within operator predicates.
    • + *
+ * + * @param pred The semantic context to evaluate + * @param parserCallStack The parser context in which to evaluate the + * semantic context + * @param alt The alternative which is guarded by {@code pred} + * @param fullCtx {@code true} if the evaluation is occurring during LL + * prediction; otherwise, {@code false} if the evaluation is occurring + * during SLL prediction + * + * @since 4.3 + */ + virtual bool evalSemanticContext(Ref const& pred, ParserRuleContext *parserCallStack, + size_t alt, bool fullCtx); + + /* TODO: If we are doing predicates, there is no point in pursuing + closure operations if we reach a DFA state that uniquely predicts + alternative. We will not be caching that DFA state and it is a + waste to pursue the closure. Might have to advance when we do + ambig detection thought :( + */ + virtual void closure(Ref const& config, ATNConfigSet *configs, ATNConfig::Set &closureBusy, + bool collectPredicates, bool fullCtx, bool treatEofAsEpsilon); + + virtual void closureCheckingStopState(Ref const& config, ATNConfigSet *configs, ATNConfig::Set &closureBusy, + bool collectPredicates, bool fullCtx, int depth, bool treatEofAsEpsilon); + + /// Do the actual work of walking epsilon edges. + virtual void closure_(Ref const& config, ATNConfigSet *configs, ATNConfig::Set &closureBusy, + bool collectPredicates, bool fullCtx, int depth, bool treatEofAsEpsilon); + + virtual Ref getEpsilonTarget(Ref const& config, Transition *t, bool collectPredicates, + bool inContext, bool fullCtx, bool treatEofAsEpsilon); + virtual Ref actionTransition(Ref const& config, ActionTransition *t); + + virtual Ref predTransition(Ref const& config, PredicateTransition *pt, bool collectPredicates, + bool inContext, bool fullCtx); + + virtual Ref ruleTransition(Ref const& config, RuleTransition *t); + + /** + * Gets a {@link BitSet} containing the alternatives in {@code configs} + * which are part of one or more conflicting alternative subsets. + * + * @param configs The {@link ATNConfigSet} to analyze. + * @return The alternatives in {@code configs} which are part of one or more + * conflicting alternative subsets. If {@code configs} does not contain any + * conflicting subsets, this method returns an empty {@link BitSet}. + */ + virtual antlrcpp::BitSet getConflictingAlts(ATNConfigSet *configs); + + /// + /// Sam pointed out a problem with the previous definition, v3, of + /// ambiguous states. If we have another state associated with conflicting + /// alternatives, we should keep going. For example, the following grammar + /// + /// s : (ID | ID ID?) ';' ; + /// + /// When the ATN simulation reaches the state before ';', it has a DFA + /// state that looks like: [12|1|[], 6|2|[], 12|2|[]]. Naturally + /// 12|1|[] and 12|2|[] conflict, but we cannot stop processing this node + /// because alternative to has another way to continue, via [6|2|[]]. + /// The key is that we have a single state that has config's only associated + /// with a single alternative, 2, and crucially the state transitions + /// among the configurations are all non-epsilon transitions. That means + /// we don't consider any conflicts that include alternative 2. So, we + /// ignore the conflict between alts 1 and 2. We ignore a set of + /// conflicting alts when there is an intersection with an alternative + /// associated with a single alt state in the state->config-list map. + /// + /// It's also the case that we might have two conflicting configurations but + /// also a 3rd nonconflicting configuration for a different alternative: + /// [1|1|[], 1|2|[], 8|3|[]]. This can come about from grammar: + /// + /// a : A | A | A B ; + /// + /// After matching input A, we reach the stop state for rule A, state 1. + /// State 8 is the state right before B. Clearly alternatives 1 and 2 + /// conflict and no amount of further lookahead will separate the two. + /// However, alternative 3 will be able to continue and so we do not + /// stop working on this state. In the previous example, we're concerned + /// with states associated with the conflicting alternatives. Here alt + /// 3 is not associated with the conflicting configs, but since we can continue + /// looking for input reasonably, I don't declare the state done. We + /// ignore a set of conflicting alts when we have an alternative + /// that we still need to pursue. + /// + + virtual antlrcpp::BitSet getConflictingAltsOrUniqueAlt(ATNConfigSet *configs); + + virtual NoViableAltException noViableAlt(TokenStream *input, ParserRuleContext *outerContext, + ATNConfigSet *configs, size_t startIndex, bool deleteConfigs); + + static size_t getUniqueAlt(ATNConfigSet *configs); + + /// + /// Add an edge to the DFA, if possible. This method calls + /// to ensure the {@code to} state is present in the + /// DFA. If {@code from} is {@code null}, or if {@code t} is outside the + /// range of edges that can be represented in the DFA tables, this method + /// returns without adding the edge to the DFA. + ///

+ /// If {@code to} is {@code null}, this method returns {@code null}. + /// Otherwise, this method returns the returned by calling + /// for the {@code to} state. + ///

+ /// The DFA + /// The source state for the edge + /// The input symbol + /// The target state for the edge + /// + /// If {@code to} is {@code null}, this method returns {@code null}; + /// otherwise this method returns the result of calling + /// on {@code to} + virtual dfa::DFAState *addDFAEdge(dfa::DFA &dfa, dfa::DFAState *from, ssize_t t, dfa::DFAState *to); + + /// + /// Add state {@code D} to the DFA if it is not already present, and return + /// the actual instance stored in the DFA. If a state equivalent to {@code D} + /// is already in the DFA, the existing state is returned. Otherwise this + /// method returns {@code D} after adding it to the DFA. + ///

+ /// If {@code D} is , this method returns and + /// does not change the DFA. + ///

+ /// The dfa + /// The DFA state to add + /// The state stored in the DFA. This will be either the existing + /// state if {@code D} is already in the DFA, or {@code D} itself if the + /// state was not already present. + virtual dfa::DFAState *addDFAState(dfa::DFA &dfa, dfa::DFAState *D); + + virtual void reportAttemptingFullContext(dfa::DFA &dfa, const antlrcpp::BitSet &conflictingAlts, + ATNConfigSet *configs, size_t startIndex, size_t stopIndex); + + virtual void reportContextSensitivity(dfa::DFA &dfa, size_t prediction, ATNConfigSet *configs, + size_t startIndex, size_t stopIndex); + + /// If context sensitive parsing, we know it's ambiguity not conflict. + virtual void reportAmbiguity(dfa::DFA &dfa, + dfa::DFAState *D, // the DFA state from execATN() that had SLL conflicts + size_t startIndex, size_t stopIndex, + bool exact, + const antlrcpp::BitSet &ambigAlts, + ATNConfigSet *configs); // configs that LL not SLL considered conflicting + + private: + // SLL, LL, or LL + exact ambig detection? + PredictionMode _mode; + + static bool getLrLoopSetting(); + void InitializeInstanceFields(); + }; + +} // namespace atn +} // namespace antlr4 + diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusBlockStartState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusBlockStartState.h new file mode 100644 index 0000000..a3affb8 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusBlockStartState.h @@ -0,0 +1,25 @@ +/* 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. + */ + +#pragma once + +#include "atn/BlockStartState.h" + +namespace antlr4 { +namespace atn { + + /// Start of {@code (A|B|...)+} loop. Technically a decision state, but + /// we don't use for code generation; somebody might need it, so I'm defining + /// it for completeness. In reality, the node is the + /// real decision-making note for {@code A+}. + class ANTLR4CPP_PUBLIC PlusBlockStartState final : public BlockStartState { + public: + PlusLoopbackState *loopBackState = nullptr; + + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusLoopbackState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusLoopbackState.h new file mode 100644 index 0000000..ba7a4b6 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PlusLoopbackState.h @@ -0,0 +1,22 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionState.h" + +namespace antlr4 { +namespace atn { + + /// Decision state for {@code A+} and {@code (A|B)+}. It has two transitions: + /// one to the loop back to start of the block and one to exit. + class ANTLR4CPP_PUBLIC PlusLoopbackState final : public DecisionState { + + public: + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PrecedencePredicateTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PrecedencePredicateTransition.h new file mode 100644 index 0000000..bc22146 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PrecedencePredicateTransition.h @@ -0,0 +1,29 @@ +/* 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. + */ + +#pragma once + +#include "atn/AbstractPredicateTransition.h" +#include "SemanticContext.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC PrecedencePredicateTransition final : public AbstractPredicateTransition { + public: + const int precedence; + + PrecedencePredicateTransition(ATNState *target, int precedence); + + virtual SerializationType getSerializationType() const override; + virtual bool isEpsilon() const override; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + Ref getPredicate() const; + virtual std::string toString() const override; + + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateEvalInfo.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateEvalInfo.h new file mode 100644 index 0000000..b0513ae --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateEvalInfo.h @@ -0,0 +1,62 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionEventInfo.h" + +namespace antlr4 { +namespace atn { + + /// + /// This class represents profiling event information for semantic predicate + /// evaluations which occur during prediction. + /// + /// + class ANTLR4CPP_PUBLIC PredicateEvalInfo : public DecisionEventInfo { + public: + /// The semantic context which was evaluated. + const Ref semctx; + + /// + /// The alternative number for the decision which is guarded by the semantic + /// context . Note that other ATN + /// configurations may predict the same alternative which are guarded by + /// other semantic contexts and/or . + /// + const size_t predictedAlt; + + /// The result of evaluating the semantic context . + const bool evalResult; + + /// + /// Constructs a new instance of the class with the + /// specified detailed predicate evaluation information. + /// + /// The decision number + /// The input token stream + /// The start index for the current prediction + /// The index at which the predicate evaluation was + /// triggered. Note that the input stream may be reset to other positions for + /// the actual evaluation of individual predicates. + /// The semantic context which was evaluated + /// The results of evaluating the semantic context + /// The alternative number for the decision which is + /// guarded by the semantic context {@code semctx}. See + /// for more information. + /// {@code true} if the semantic context was + /// evaluated during LL prediction; otherwise, {@code false} if the semantic + /// context was evaluated during SLL prediction + /// + /// + /// + PredicateEvalInfo(size_t decision, TokenStream *input, size_t startIndex, size_t stopIndex, + Ref const& semctx, bool evalResult, size_t predictedAlt, bool fullCtx); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateTransition.h new file mode 100644 index 0000000..4d9b420 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredicateTransition.h @@ -0,0 +1,39 @@ +/* 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. + */ + +#pragma once + +#include "atn/AbstractPredicateTransition.h" +#include "SemanticContext.h" + +namespace antlr4 { +namespace atn { + + /// TODO: this is old comment: + /// A tree of semantic predicates from the grammar AST if label==SEMPRED. + /// In the ATN, labels will always be exactly one predicate, but the DFA + /// may have to combine a bunch of them as it collects predicates from + /// multiple ATN configurations into a single DFA state. + class ANTLR4CPP_PUBLIC PredicateTransition final : public AbstractPredicateTransition { + public: + const size_t ruleIndex; + const size_t predIndex; + const bool isCtxDependent; // e.g., $i ref in pred + + PredicateTransition(ATNState *target, size_t ruleIndex, size_t predIndex, bool isCtxDependent); + + virtual SerializationType getSerializationType() const override; + + virtual bool isEpsilon() const override; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + Ref getPredicate() const; + + virtual std::string toString() const override; + + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h new file mode 100644 index 0000000..e8dfc23 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionContext.h @@ -0,0 +1,266 @@ +/* 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. + */ + +#pragma once + +#include "Recognizer.h" +#include "atn/ATN.h" +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + struct PredictionContextHasher; + struct PredictionContextComparer; + class PredictionContextMergeCache; + + typedef std::unordered_set, PredictionContextHasher, PredictionContextComparer> PredictionContextCache; + + class ANTLR4CPP_PUBLIC PredictionContext { + public: + /// Represents $ in local context prediction, which means wildcard. + /// *+x = *. + static const Ref EMPTY; + + /// Represents $ in an array in full context mode, when $ + /// doesn't mean wildcard: $ + x = [$,x]. Here, + /// $ = EMPTY_RETURN_STATE. + // ml: originally Integer.MAX_VALUE, which would be -1 for us, but this is already used in places where + // -1 is converted to unsigned, so we use a different value here. Any value does the job provided it doesn't + // conflict with real return states. +#if __cplusplus >= 201703L + static constexpr size_t EMPTY_RETURN_STATE = std::numeric_limits::max() - 9; +#else + enum : size_t { + EMPTY_RETURN_STATE = static_cast(-10), // std::numeric_limits::max() - 9; doesn't work in VS 2013 + }; +#endif + + private: +#if __cplusplus >= 201703L + static constexpr size_t INITIAL_HASH = 1; +#else + enum : size_t { + INITIAL_HASH = 1, + }; +#endif + + public: + static size_t globalNodeCount; + const size_t id; + + /// + /// Stores the computed hash code of this . The hash + /// code is computed in parts to match the following reference algorithm. + /// + /// 
+    ///  private int referenceHashCode() {
+    ///      int hash = ();
+    ///
+    ///      for (int i = 0; i < ; i++) {
+    ///          hash = (hash, (i));
+    ///      }
+    ///
+    ///      for (int i = 0; i < ; i++) {
+    ///          hash = (hash, (i));
+    ///      }
+    ///
+    ///      hash = (hash, 2 * );
+    ///      return hash;
+    ///  }
+    ///
+ /// + const size_t cachedHashCode; + + protected: + PredictionContext(size_t cachedHashCode); + ~PredictionContext(); + + public: + /// Convert a RuleContext tree to a PredictionContext graph. + /// Return EMPTY if outerContext is empty. + static Ref fromRuleContext(const ATN &atn, RuleContext *outerContext); + + virtual size_t size() const = 0; + virtual Ref getParent(size_t index) const = 0; + virtual size_t getReturnState(size_t index) const = 0; + + virtual bool operator == (const PredictionContext &o) const = 0; + + /// This means only the EMPTY (wildcard? not sure) context is in set. + virtual bool isEmpty() const; + virtual bool hasEmptyPath() const; + virtual size_t hashCode() const; + + protected: + static size_t calculateEmptyHashCode(); + static size_t calculateHashCode(Ref parent, size_t returnState); + static size_t calculateHashCode(const std::vector> &parents, + const std::vector &returnStates); + + public: + // dispatch + static Ref merge(const Ref &a, const Ref &b, + bool rootIsWildcard, PredictionContextMergeCache *mergeCache); + + /// + /// Merge two instances. + /// + ///

+ /// + /// Stack tops equal, parents merge is same; return left graph.
+ /// + /// + ///

+ /// + /// Same stack top, parents differ; merge parents giving array node, then + /// remainders of those graphs. A new root node is created to point to the + /// merged parents.
+ /// + /// + ///

+ /// + /// Different stack tops pointing to same parent. Make array node for the + /// root where both element in the root point to the same (original) + /// parent.
+ /// + /// + ///

+ /// + /// Different stack tops pointing to different parents. Make array node for + /// the root where each element points to the corresponding original + /// parent.
+ /// + ///

+ /// the first + /// the second + /// {@code true} if this is a local-context merge, + /// otherwise false to indicate a full-context merge + /// + static Ref mergeSingletons(const Ref &a, + const Ref &b, bool rootIsWildcard, PredictionContextMergeCache *mergeCache); + + /** + * Handle case where at least one of {@code a} or {@code b} is + * {@link #EMPTY}. In the following diagrams, the symbol {@code $} is used + * to represent {@link #EMPTY}. + * + *

Local-Context Merges

+ * + *

These local-context merge operations are used when {@code rootIsWildcard} + * is true.

+ * + *

{@link #EMPTY} is superset of any graph; return {@link #EMPTY}.
+ *

+ * + *

{@link #EMPTY} and anything is {@code #EMPTY}, so merged parent is + * {@code #EMPTY}; return left graph.
+ *

+ * + *

Special case of last merge if local context.
+ *

+ * + *

Full-Context Merges

+ * + *

These full-context merge operations are used when {@code rootIsWildcard} + * is false.

+ * + *

+ * + *

Must keep all contexts; {@link #EMPTY} in array is a special value (and + * null parent).
+ *

+ * + *

+ * + * @param a the first {@link SingletonPredictionContext} + * @param b the second {@link SingletonPredictionContext} + * @param rootIsWildcard {@code true} if this is a local-context merge, + * otherwise false to indicate a full-context merge + */ + static Ref mergeRoot(const Ref &a, + const Ref &b, bool rootIsWildcard); + + /** + * Merge two {@link ArrayPredictionContext} instances. + * + *

Different tops, different parents.
+ *

+ * + *

Shared top, same parents.
+ *

+ * + *

Shared top, different parents.
+ *

+ * + *

Shared top, all shared parents.
+ *

+ * + *

Equal tops, merge parents and reduce top to + * {@link SingletonPredictionContext}.
+ *

+ */ + static Ref mergeArrays(const Ref &a, + const Ref &b, bool rootIsWildcard, PredictionContextMergeCache *mergeCache); + + protected: + /// Make pass over all M parents; merge any equal() ones. + /// @returns true if the list has been changed (i.e. duplicates where found). + static bool combineCommonParents(std::vector> &parents); + + public: + static std::string toDOTString(const Ref &context); + + static Ref getCachedContext(const Ref &context, + PredictionContextCache &contextCache, + std::map, Ref> &visited); + + // ter's recursive version of Sam's getAllNodes() + static std::vector> getAllContextNodes(const Ref &context); + static void getAllContextNodes_(const Ref &context, + std::vector> &nodes, std::set &visited); + + virtual std::string toString() const; + virtual std::string toString(Recognizer *recog) const; + + std::vector toStrings(Recognizer *recognizer, int currentState); + std::vector toStrings(Recognizer *recognizer, const Ref &stop, int currentState); + }; + + struct PredictionContextHasher { + size_t operator () (const Ref &k) const { + return k->hashCode(); + } + }; + + struct PredictionContextComparer { + bool operator () (const Ref &lhs, const Ref &rhs) const + { + if (lhs == rhs) // Object identity. + return true; + return (lhs->hashCode() == rhs->hashCode()) && (*lhs == *rhs); + } + }; + + class PredictionContextMergeCache { + public: + Ref put(Ref const& key1, Ref const& key2, + Ref const& value); + Ref get(Ref const& key1, Ref const& key2); + + void clear(); + std::string toString() const; + size_t count() const; + + private: + std::unordered_map, + std::unordered_map, Ref, PredictionContextHasher, PredictionContextComparer>, + PredictionContextHasher, PredictionContextComparer> _data; + + }; + +} // namespace atn +} // namespace antlr4 + diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionMode.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionMode.h new file mode 100644 index 0000000..726f4cf --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/PredictionMode.h @@ -0,0 +1,436 @@ +/* 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. + */ + +#pragma once + +#include "support/BitSet.h" + +namespace antlr4 { +namespace atn { + + /** + * This enumeration defines the prediction modes available in ANTLR 4 along with + * utility methods for analyzing configuration sets for conflicts and/or + * ambiguities. + */ + enum class PredictionMode { + /** + * The SLL(*) prediction mode. This prediction mode ignores the current + * parser context when making predictions. This is the fastest prediction + * mode, and provides correct results for many grammars. This prediction + * mode is more powerful than the prediction mode provided by ANTLR 3, but + * may result in syntax errors for grammar and input combinations which are + * not SLL. + * + *

+ * When using this prediction mode, the parser will either return a correct + * parse tree (i.e. the same parse tree that would be returned with the + * {@link #LL} prediction mode), or it will report a syntax error. If a + * syntax error is encountered when using the {@link #SLL} prediction mode, + * it may be due to either an actual syntax error in the input or indicate + * that the particular combination of grammar and input requires the more + * powerful {@link #LL} prediction abilities to complete successfully.

+ * + *

+ * This prediction mode does not provide any guarantees for prediction + * behavior for syntactically-incorrect inputs.

+ */ + SLL, + + /** + * The LL(*) prediction mode. This prediction mode allows the current parser + * context to be used for resolving SLL conflicts that occur during + * prediction. This is the fastest prediction mode that guarantees correct + * parse results for all combinations of grammars with syntactically correct + * inputs. + * + *

+ * When using this prediction mode, the parser will make correct decisions + * for all syntactically-correct grammar and input combinations. However, in + * cases where the grammar is truly ambiguous this prediction mode might not + * report a precise answer for exactly which alternatives are + * ambiguous.

+ * + *

+ * This prediction mode does not provide any guarantees for prediction + * behavior for syntactically-incorrect inputs.

+ */ + LL, + + /** + * The LL(*) prediction mode with exact ambiguity detection. In addition to + * the correctness guarantees provided by the {@link #LL} prediction mode, + * this prediction mode instructs the prediction algorithm to determine the + * complete and exact set of ambiguous alternatives for every ambiguous + * decision encountered while parsing. + * + *

+ * This prediction mode may be used for diagnosing ambiguities during + * grammar development. Due to the performance overhead of calculating sets + * of ambiguous alternatives, this prediction mode should be avoided when + * the exact results are not necessary.

+ * + *

+ * This prediction mode does not provide any guarantees for prediction + * behavior for syntactically-incorrect inputs.

+ */ + LL_EXACT_AMBIG_DETECTION + }; + + class ANTLR4CPP_PUBLIC PredictionModeClass { + public: + /** + * Computes the SLL prediction termination condition. + * + *

+ * This method computes the SLL prediction termination condition for both of + * the following cases.

+ * + *
    + *
  • The usual SLL+LL fallback upon SLL conflict
    • + *
  • Pure SLL without LL fallback
    • + *
+ * + *

COMBINED SLL+LL PARSING

+ * + *

When LL-fallback is enabled upon SLL conflict, correct predictions are + * ensured regardless of how the termination condition is computed by this + * method. Due to the substantially higher cost of LL prediction, the + * prediction should only fall back to LL when the additional lookahead + * cannot lead to a unique SLL prediction.

+ * + *

Assuming combined SLL+LL parsing, an SLL configuration set with only + * conflicting subsets should fall back to full LL, even if the + * configuration sets don't resolve to the same alternative (e.g. + * {@code {1,2}} and {@code {3,4}}. If there is at least one non-conflicting + * configuration, SLL could continue with the hopes that more lookahead will + * resolve via one of those non-conflicting configurations.

+ * + *

Here's the prediction termination rule them: SLL (for SLL+LL parsing) + * stops when it sees only conflicting configuration subsets. In contrast, + * full LL keeps going when there is uncertainty.

+ * + *

HEURISTIC

+ * + *

As a heuristic, we stop prediction when we see any conflicting subset + * unless we see a state that only has one alternative associated with it. + * The single-alt-state thing lets prediction continue upon rules like + * (otherwise, it would admit defeat too soon):

+ * + *

{@code [12|1|[], 6|2|[], 12|2|[]]. s : (ID | ID ID?) ';' ;}

+ * + *

When the ATN simulation reaches the state before {@code ';'}, it has a + * DFA state that looks like: {@code [12|1|[], 6|2|[], 12|2|[]]}. Naturally + * {@code 12|1|[]} and {@code 12|2|[]} conflict, but we cannot stop + * processing this node because alternative to has another way to continue, + * via {@code [6|2|[]]}.

+ * + *

It also let's us continue for this rule:

+ * + *

{@code [1|1|[], 1|2|[], 8|3|[]] a : A | A | A B ;}

+ * + *

After matching input A, we reach the stop state for rule A, state 1. + * State 8 is the state right before B. Clearly alternatives 1 and 2 + * conflict and no amount of further lookahead will separate the two. + * However, alternative 3 will be able to continue and so we do not stop + * working on this state. In the previous example, we're concerned with + * states associated with the conflicting alternatives. Here alt 3 is not + * associated with the conflicting configs, but since we can continue + * looking for input reasonably, don't declare the state done.

+ * + *

PURE SLL PARSING

+ * + *

To handle pure SLL parsing, all we have to do is make sure that we + * combine stack contexts for configurations that differ only by semantic + * predicate. From there, we can do the usual SLL termination heuristic.

+ * + *

PREDICATES IN SLL+LL PARSING

+ * + *

SLL decisions don't evaluate predicates until after they reach DFA stop + * states because they need to create the DFA cache that works in all + * semantic situations. In contrast, full LL evaluates predicates collected + * during start state computation so it can ignore predicates thereafter. + * This means that SLL termination detection can totally ignore semantic + * predicates.

+ * + *

Implementation-wise, {@link ATNConfigSet} combines stack contexts but not + * semantic predicate contexts so we might see two configurations like the + * following.

+ * + *

{@code (s, 1, x, {}), (s, 1, x', {p})}

+ * + *

Before testing these configurations against others, we have to merge + * {@code x} and {@code x'} (without modifying the existing configurations). + * For example, we test {@code (x+x')==x''} when looking for conflicts in + * the following configurations.

+ * + *

{@code (s, 1, x, {}), (s, 1, x', {p}), (s, 2, x'', {})}

+ * + *

If the configuration set has predicates (as indicated by + * {@link ATNConfigSet#hasSemanticContext}), this algorithm makes a copy of + * the configurations to strip out all of the predicates so that a standard + * {@link ATNConfigSet} will merge everything ignoring predicates.

+ */ + static bool hasSLLConflictTerminatingPrediction(PredictionMode mode, ATNConfigSet *configs); + + /// + /// Checks if any configuration in {@code configs} is in a + /// . Configurations meeting this condition have + /// reached + /// the end of the decision rule (local context) or end of start rule (full + /// context). + /// + /// the configuration set to test + /// {@code true} if any configuration in {@code configs} is in a + /// , otherwise {@code false} + static bool hasConfigInRuleStopState(ATNConfigSet *configs); + + /// + /// Checks if all configurations in {@code configs} are in a + /// . Configurations meeting this condition have + /// reached + /// the end of the decision rule (local context) or end of start rule (full + /// context). + /// + /// the configuration set to test + /// {@code true} if all configurations in {@code configs} are in a + /// , otherwise {@code false} + static bool allConfigsInRuleStopStates(ATNConfigSet *configs); + + /** + * Full LL prediction termination. + * + *

Can we stop looking ahead during ATN simulation or is there some + * uncertainty as to which alternative we will ultimately pick, after + * consuming more input? Even if there are partial conflicts, we might know + * that everything is going to resolve to the same minimum alternative. That + * means we can stop since no more lookahead will change that fact. On the + * other hand, there might be multiple conflicts that resolve to different + * minimums. That means we need more look ahead to decide which of those + * alternatives we should predict.

+ * + *

The basic idea is to split the set of configurations {@code C}, into + * conflicting subsets {@code (s, _, ctx, _)} and singleton subsets with + * non-conflicting configurations. Two configurations conflict if they have + * identical {@link ATNConfig#state} and {@link ATNConfig#context} values + * but different {@link ATNConfig#alt} value, e.g. {@code (s, i, ctx, _)} + * and {@code (s, j, ctx, _)} for {@code i!=j}.

+ * + *

Reduce these configuration subsets to the set of possible alternatives. + * You can compute the alternative subsets in one pass as follows:

+ * + *

{@code A_s,ctx = {i | (s, i, ctx, _)}} for each configuration in + * {@code C} holding {@code s} and {@code ctx} fixed.

+ * + *

Or in pseudo-code, for each configuration {@code c} in {@code C}:

+ * + * 
+     * map[c] U= c.{@link ATNConfig#alt alt} # map hash/equals uses s and x, not
+     * alt and not pred
+     *
+ * + *

The values in {@code map} are the set of {@code A_s,ctx} sets.

+ * + *

If {@code |A_s,ctx|=1} then there is no conflict associated with + * {@code s} and {@code ctx}.

+ * + *

Reduce the subsets to singletons by choosing a minimum of each subset. If + * the union of these alternative subsets is a singleton, then no amount of + * more lookahead will help us. We will always pick that alternative. If, + * however, there is more than one alternative, then we are uncertain which + * alternative to predict and must continue looking for resolution. We may + * or may not discover an ambiguity in the future, even if there are no + * conflicting subsets this round.

+ * + *

The biggest sin is to terminate early because it means we've made a + * decision but were uncertain as to the eventual outcome. We haven't used + * enough lookahead. On the other hand, announcing a conflict too late is no + * big deal; you will still have the conflict. It's just inefficient. It + * might even look until the end of file.

+ * + *

No special consideration for semantic predicates is required because + * predicates are evaluated on-the-fly for full LL prediction, ensuring that + * no configuration contains a semantic context during the termination + * check.

+ * + *

CONFLICTING CONFIGS

+ * + *

Two configurations {@code (s, i, x)} and {@code (s, j, x')}, conflict + * when {@code i!=j} but {@code x=x'}. Because we merge all + * {@code (s, i, _)} configurations together, that means that there are at + * most {@code n} configurations associated with state {@code s} for + * {@code n} possible alternatives in the decision. The merged stacks + * complicate the comparison of configuration contexts {@code x} and + * {@code x'}. Sam checks to see if one is a subset of the other by calling + * merge and checking to see if the merged result is either {@code x} or + * {@code x'}. If the {@code x} associated with lowest alternative {@code i} + * is the superset, then {@code i} is the only possible prediction since the + * others resolve to {@code min(i)} as well. However, if {@code x} is + * associated with {@code j>i} then at least one stack configuration for + * {@code j} is not in conflict with alternative {@code i}. The algorithm + * should keep going, looking for more lookahead due to the uncertainty.

+ * + *

For simplicity, I'm doing a equality check between {@code x} and + * {@code x'} that lets the algorithm continue to consume lookahead longer + * than necessary. The reason I like the equality is of course the + * simplicity but also because that is the test you need to detect the + * alternatives that are actually in conflict.

+ * + *

CONTINUE/STOP RULE

+ * + *

Continue if union of resolved alternative sets from non-conflicting and + * conflicting alternative subsets has more than one alternative. We are + * uncertain about which alternative to predict.

+ * + *

The complete set of alternatives, {@code [i for (_,i,_)]}, tells us which + * alternatives are still in the running for the amount of input we've + * consumed at this point. The conflicting sets let us to strip away + * configurations that won't lead to more states because we resolve + * conflicts to the configuration with a minimum alternate for the + * conflicting set.

+ * + *

CASES

+ * + *
    + * + *
  • no conflicts and more than 1 alternative in set => continue
    • + * + *
  • {@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s, 3, z)}, + * {@code (s', 1, y)}, {@code (s', 2, y)} yields non-conflicting set + * {@code {3}} U conflicting sets {@code min({1,2})} U {@code min({1,2})} = + * {@code {1,3}} => continue + *
    • + * + *
  • {@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 1, y)}, + * {@code (s', 2, y)}, {@code (s'', 1, z)} yields non-conflicting set + * {@code {1}} U conflicting sets {@code min({1,2})} U {@code min({1,2})} = + * {@code {1}} => stop and predict 1
    • + * + *
  • {@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 1, y)}, + * {@code (s', 2, y)} yields conflicting, reduced sets {@code {1}} U + * {@code {1}} = {@code {1}} => stop and predict 1, can announce + * ambiguity {@code {1,2}}
    • + * + *
  • {@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 2, y)}, + * {@code (s', 3, y)} yields conflicting, reduced sets {@code {1}} U + * {@code {2}} = {@code {1,2}} => continue
    • + * + *
  • {@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 3, y)}, + * {@code (s', 4, y)} yields conflicting, reduced sets {@code {1}} U + * {@code {3}} = {@code {1,3}} => continue
    • + * + *
+ * + *

EXACT AMBIGUITY DETECTION

+ * + *

If all states report the same conflicting set of alternatives, then we + * know we have the exact ambiguity set.

+ * + *

|A_i|>1 and + * A_i = A_j for all i, j.

+ * + *

In other words, we continue examining lookahead until all {@code A_i} + * have more than one alternative and all {@code A_i} are the same. If + * {@code A={{1,2}, {1,3}}}, then regular LL prediction would terminate + * because the resolved set is {@code {1}}. To determine what the real + * ambiguity is, we have to know whether the ambiguity is between one and + * two or one and three so we keep going. We can only stop prediction when + * we need exact ambiguity detection when the sets look like + * {@code A={{1,2}}} or {@code {{1,2},{1,2}}}, etc...

+ */ + static size_t resolvesToJustOneViableAlt(const std::vector &altsets); + + /// + /// Determines if every alternative subset in {@code altsets} contains more + /// than one alternative. + /// + /// a collection of alternative subsets + /// {@code true} if every in {@code altsets} + /// has + /// > 1, otherwise {@code + /// false} + static bool allSubsetsConflict(const std::vector &altsets); + + /// + /// Determines if any single alternative subset in {@code altsets} contains + /// exactly one alternative. + /// + /// a collection of alternative subsets + /// {@code true} if {@code altsets} contains a with + /// 1, otherwise {@code false} + /// + static bool hasNonConflictingAltSet(const std::vector &altsets); + + /// + /// Determines if any single alternative subset in {@code altsets} contains + /// more than one alternative. + /// + /// a collection of alternative subsets + /// {@code true} if {@code altsets} contains a with + /// > 1, otherwise {@code + /// false} + static bool hasConflictingAltSet(const std::vector &altsets); + + /// + /// Determines if every alternative subset in {@code altsets} is equivalent. + /// + /// a collection of alternative subsets + /// {@code true} if every member of {@code altsets} is equal to the + /// others, otherwise {@code false} + static bool allSubsetsEqual(const std::vector &altsets); + + /// + /// Returns the unique alternative predicted by all alternative subsets in + /// {@code altsets}. If no such alternative exists, this method returns + /// . + /// + /// a collection of alternative subsets + static size_t getUniqueAlt(const std::vector &altsets); + + /// + /// Gets the complete set of represented alternatives for a collection of + /// alternative subsets. This method returns the union of each + /// in {@code altsets}. + /// + /// a collection of alternative subsets + /// the set of represented alternatives in {@code altsets} + static antlrcpp::BitSet getAlts(const std::vector &altsets); + + /** Get union of all alts from configs. @since 4.5.1 */ + static antlrcpp::BitSet getAlts(ATNConfigSet *configs); + + /// + /// This function gets the conflicting alt subsets from a configuration set. + /// For each configuration {@code c} in {@code configs}: + /// + /// 
+    /// map[c] U= c. # map hash/equals uses s and
+    /// x, not
+    /// alt and not pred
+    ///
+ /// + static std::vector getConflictingAltSubsets(ATNConfigSet *configs); + + /// + /// Get a map from state to alt subset from a configuration set. For each + /// configuration {@code c} in {@code configs}: + /// + /// 
+    /// map[c.] U= c.
+    ///
+ /// + static std::map getStateToAltMap(ATNConfigSet *configs); + + static bool hasStateAssociatedWithOneAlt(ATNConfigSet *configs); + + static size_t getSingleViableAlt(const std::vector &altsets); + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ProfilingATNSimulator.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ProfilingATNSimulator.h new file mode 100644 index 0000000..79ecd00 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/ProfilingATNSimulator.h @@ -0,0 +1,60 @@ +/* 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. + */ + +#pragma once + +#include "atn/ParserATNSimulator.h" +#include "atn/DecisionInfo.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC ProfilingATNSimulator : public ParserATNSimulator { + public: + ProfilingATNSimulator(Parser *parser); + + virtual size_t adaptivePredict(TokenStream *input, size_t decision, ParserRuleContext *outerContext) override; + + virtual std::vector getDecisionInfo() const; + virtual dfa::DFAState* getCurrentState() const; + + protected: + std::vector _decisions; + + int _sllStopIndex = 0; + int _llStopIndex = 0; + + size_t _currentDecision = 0; + dfa::DFAState *_currentState; + + /// + /// At the point of LL failover, we record how SLL would resolve the conflict so that + /// we can determine whether or not a decision / input pair is context-sensitive. + /// If LL gives a different result than SLL's predicted alternative, we have a + /// context sensitivity for sure. The converse is not necessarily true, however. + /// It's possible that after conflict resolution chooses minimum alternatives, + /// SLL could get the same answer as LL. Regardless of whether or not the result indicates + /// an ambiguity, it is not treated as a context sensitivity because LL prediction + /// was not required in order to produce a correct prediction for this decision and input sequence. + /// It may in fact still be a context sensitivity but we don't know by looking at the + /// minimum alternatives for the current input. + /// + size_t conflictingAltResolvedBySLL = 0; + + virtual dfa::DFAState* getExistingTargetState(dfa::DFAState *previousD, size_t t) override; + virtual dfa::DFAState* computeTargetState(dfa::DFA &dfa, dfa::DFAState *previousD, size_t t) override; + virtual std::unique_ptr computeReachSet(ATNConfigSet *closure, size_t t, bool fullCtx) override; + virtual bool evalSemanticContext(Ref const& pred, ParserRuleContext *parserCallStack, + size_t alt, bool fullCtx) override; + virtual void reportAttemptingFullContext(dfa::DFA &dfa, const antlrcpp::BitSet &conflictingAlts, ATNConfigSet *configs, + size_t startIndex, size_t stopIndex) override; + virtual void reportContextSensitivity(dfa::DFA &dfa, size_t prediction, ATNConfigSet *configs, + size_t startIndex, size_t stopIndex) override; + virtual void reportAmbiguity(dfa::DFA &dfa, dfa::DFAState *D, size_t startIndex, size_t stopIndex, bool exact, + const antlrcpp::BitSet &ambigAlts, ATNConfigSet *configs) override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RangeTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RangeTransition.h new file mode 100644 index 0000000..14093e2 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RangeTransition.h @@ -0,0 +1,29 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC RangeTransition final : public Transition { + public: + const size_t from; + const size_t to; + + RangeTransition(ATNState *target, size_t from, size_t to); + + virtual SerializationType getSerializationType() const override; + + virtual misc::IntervalSet label() const override; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStartState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStartState.h new file mode 100644 index 0000000..94ab0e4 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStartState.h @@ -0,0 +1,25 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC RuleStartState final : public ATNState { + public: + RuleStartState(); + + RuleStopState *stopState = nullptr; + bool isLeftRecursiveRule = false; + + virtual size_t getStateType() override; + + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStopState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStopState.h new file mode 100644 index 0000000..8a4a580 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleStopState.h @@ -0,0 +1,25 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + /// The last node in the ATN for a rule, unless that rule is the start symbol. + /// In that case, there is one transition to EOF. Later, we might encode + /// references to all calls to this rule to compute FOLLOW sets for + /// error handling. + class ANTLR4CPP_PUBLIC RuleStopState final : public ATNState { + + public: + virtual size_t getStateType() override; + + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleTransition.h new file mode 100644 index 0000000..50d3d29 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/RuleTransition.h @@ -0,0 +1,40 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC RuleTransition : public Transition { + public: + /// Ptr to the rule definition object for this rule ref. + const size_t ruleIndex; // no Rule object at runtime + + const int precedence; + + /// What node to begin computations following ref to rule. + ATNState *followState; + + /// @deprecated Use + /// instead. + RuleTransition(RuleStartState *ruleStart, size_t ruleIndex, ATNState *followState); + + RuleTransition(RuleStartState *ruleStart, size_t ruleIndex, int precedence, ATNState *followState); + RuleTransition(RuleTransition const&) = delete; + RuleTransition& operator=(RuleTransition const&) = delete; + + virtual SerializationType getSerializationType() const override; + + virtual bool isEpsilon() const override; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SemanticContext.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SemanticContext.h new file mode 100644 index 0000000..7ccc16c --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SemanticContext.h @@ -0,0 +1,222 @@ +/* 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. + */ + +#pragma once + +#include "Recognizer.h" +#include "support/CPPUtils.h" + +namespace antlr4 { +namespace atn { + + /// A tree structure used to record the semantic context in which + /// an ATN configuration is valid. It's either a single predicate, + /// a conjunction "p1 && p2", or a sum of products "p1||p2". + /// + /// I have scoped the AND, OR, and Predicate subclasses of + /// SemanticContext within the scope of this outer class. + class ANTLR4CPP_PUBLIC SemanticContext : public std::enable_shared_from_this { + public: + struct Hasher + { + size_t operator()(Ref const& k) const { + return k->hashCode(); + } + }; + + struct Comparer { + bool operator()(Ref const& lhs, Ref const& rhs) const { + if (lhs == rhs) + return true; + return (lhs->hashCode() == rhs->hashCode()) && (*lhs == *rhs); + } + }; + + + using Set = std::unordered_set, Hasher, Comparer>; + + /** + * The default {@link SemanticContext}, which is semantically equivalent to + * a predicate of the form {@code {true}?}. + */ + static const Ref NONE; + + virtual ~SemanticContext(); + + virtual size_t hashCode() const = 0; + virtual std::string toString() const = 0; + virtual bool operator == (const SemanticContext &other) const = 0; + virtual bool operator != (const SemanticContext &other) const; + + /// + /// For context independent predicates, we evaluate them without a local + /// context (i.e., null context). That way, we can evaluate them without + /// having to create proper rule-specific context during prediction (as + /// opposed to the parser, which creates them naturally). In a practical + /// sense, this avoids a cast exception from RuleContext to myruleContext. + ///

+ /// For context dependent predicates, we must pass in a local context so that + /// references such as $arg evaluate properly as _localctx.arg. We only + /// capture context dependent predicates in the context in which we begin + /// prediction, so we passed in the outer context here in case of context + /// dependent predicate evaluation. + ///

+ virtual bool eval(Recognizer *parser, RuleContext *parserCallStack) = 0; + + /** + * Evaluate the precedence predicates for the context and reduce the result. + * + * @param parser The parser instance. + * @param parserCallStack + * @return The simplified semantic context after precedence predicates are + * evaluated, which will be one of the following values. + *
    + *
  • {@link #NONE}: if the predicate simplifies to {@code true} after + * precedence predicates are evaluated.
    • + *
  • {@code null}: if the predicate simplifies to {@code false} after + * precedence predicates are evaluated.
    • + *
  • {@code this}: if the semantic context is not changed as a result of + * precedence predicate evaluation.
    • + *
  • A non-{@code null} {@link SemanticContext}: the new simplified + * semantic context after precedence predicates are evaluated.
    • + *
+ */ + virtual Ref evalPrecedence(Recognizer *parser, RuleContext *parserCallStack); + + static Ref And(Ref const& a, Ref const& b); + + /// See also: ParserATNSimulator::getPredsForAmbigAlts. + static Ref Or(Ref const& a, Ref const& b); + + class Predicate; + class PrecedencePredicate; + class Operator; + class AND; + class OR; + + private: + static std::vector> filterPrecedencePredicates(const Set &collection); + }; + + class ANTLR4CPP_PUBLIC SemanticContext::Predicate : public SemanticContext { + public: + const size_t ruleIndex; + const size_t predIndex; + const bool isCtxDependent; // e.g., $i ref in pred + + protected: + Predicate(); + + public: + Predicate(size_t ruleIndex, size_t predIndex, bool isCtxDependent); + + virtual bool eval(Recognizer *parser, RuleContext *parserCallStack) override; + virtual size_t hashCode() const override; + virtual bool operator == (const SemanticContext &other) const override; + virtual std::string toString() const override; + }; + + class ANTLR4CPP_PUBLIC SemanticContext::PrecedencePredicate : public SemanticContext { + public: + const int precedence; + + protected: + PrecedencePredicate(); + + public: + PrecedencePredicate(int precedence); + + virtual bool eval(Recognizer *parser, RuleContext *parserCallStack) override; + virtual Ref evalPrecedence(Recognizer *parser, RuleContext *parserCallStack) override; + virtual int compareTo(PrecedencePredicate *o); + virtual size_t hashCode() const override; + virtual bool operator == (const SemanticContext &other) const override; + virtual std::string toString() const override; + }; + + /** + * This is the base class for semantic context "operators", which operate on + * a collection of semantic context "operands". + * + * @since 4.3 + */ + class ANTLR4CPP_PUBLIC SemanticContext::Operator : public SemanticContext { + public: + virtual ~Operator() override; + + /** + * Gets the operands for the semantic context operator. + * + * @return a collection of {@link SemanticContext} operands for the + * operator. + * + * @since 4.3 + */ + + virtual std::vector> getOperands() const = 0; + }; + + /** + * A semantic context which is true whenever none of the contained contexts + * is false. + */ + class ANTLR4CPP_PUBLIC SemanticContext::AND : public SemanticContext::Operator { + public: + std::vector> opnds; + + AND(Ref const& a, Ref const& b) ; + + virtual std::vector> getOperands() const override; + virtual bool operator == (const SemanticContext &other) const override; + virtual size_t hashCode() const override; + + /** + * The evaluation of predicates by this context is short-circuiting, but + * unordered.

+ */ + virtual bool eval(Recognizer *parser, RuleContext *parserCallStack) override; + virtual Ref evalPrecedence(Recognizer *parser, RuleContext *parserCallStack) override; + virtual std::string toString() const override; + }; + + /** + * A semantic context which is true whenever at least one of the contained + * contexts is true. + */ + class ANTLR4CPP_PUBLIC SemanticContext::OR : public SemanticContext::Operator { + public: + std::vector> opnds; + + OR(Ref const& a, Ref const& b); + + virtual std::vector> getOperands() const override; + virtual bool operator == (const SemanticContext &other) const override; + virtual size_t hashCode() const override; + + /** + * The evaluation of predicates by this context is short-circuiting, but + * unordered. + */ + virtual bool eval(Recognizer *parser, RuleContext *parserCallStack) override; + virtual Ref evalPrecedence(Recognizer *parser, RuleContext *parserCallStack) override; + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 + +// Hash function for SemanticContext, used in the MurmurHash::update function + +namespace std { + using antlr4::atn::SemanticContext; + + template <> struct hash + { + size_t operator () (SemanticContext &x) const + { + return x.hashCode(); + } + }; +} diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SetTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SetTransition.h new file mode 100644 index 0000000..044d41a --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SetTransition.h @@ -0,0 +1,30 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + /// + /// A transition containing a set of values. + class ANTLR4CPP_PUBLIC SetTransition : public Transition { + public: + const misc::IntervalSet set; + + SetTransition(ATNState *target, const misc::IntervalSet &set); + + virtual SerializationType getSerializationType() const override; + + virtual misc::IntervalSet label() const override; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SingletonPredictionContext.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SingletonPredictionContext.h new file mode 100644 index 0000000..f1e993b --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/SingletonPredictionContext.h @@ -0,0 +1,36 @@ +/* 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. + */ + +#pragma once + +#include "atn/PredictionContext.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC SingletonPredictionContext : public PredictionContext { + public: + // Usually a parent is linked via a weak ptr. Not so here as we have kinda reverse reference chain. + // There are no child contexts stored here and often the parent context is left dangling when it's + // owning ATNState is released. In order to avoid having this context released as well (leaving all other contexts + // which got this one as parent with a null reference) we use a shared_ptr here instead, to keep those left alone + // parent contexts alive. + const Ref parent; + const size_t returnState; + + SingletonPredictionContext(Ref const& parent, size_t returnState); + virtual ~SingletonPredictionContext(); + + static Ref create(Ref const& parent, size_t returnState); + + virtual size_t size() const override; + virtual Ref getParent(size_t index) const override; + virtual size_t getReturnState(size_t index) const override; + virtual bool operator == (const PredictionContext &o) const override; + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarBlockStartState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarBlockStartState.h new file mode 100644 index 0000000..8fae316 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarBlockStartState.h @@ -0,0 +1,21 @@ +/* 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. + */ + +#pragma once + +#include "atn/BlockStartState.h" + +namespace antlr4 { +namespace atn { + + /// The block that begins a closure loop. + class ANTLR4CPP_PUBLIC StarBlockStartState final : public BlockStartState { + + public: + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopEntryState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopEntryState.h new file mode 100644 index 0000000..a062c58 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopEntryState.h @@ -0,0 +1,35 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionState.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC StarLoopEntryState final : public DecisionState { + public: + StarLoopEntryState(); + + /** + * Indicates whether this state can benefit from a precedence DFA during SLL + * decision making. + * + *

This is a computed property that is calculated during ATN deserialization + * and stored for use in {@link ParserATNSimulator} and + * {@link ParserInterpreter}.

+ * + * @see DFA#isPrecedenceDfa() + */ + bool isPrecedenceDecision = false; + + StarLoopbackState *loopBackState = nullptr; + + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopbackState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopbackState.h new file mode 100644 index 0000000..f5db3ef --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/StarLoopbackState.h @@ -0,0 +1,21 @@ +/* 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. + */ + +#pragma once + +#include "atn/ATNState.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC StarLoopbackState final : public ATNState { + public: + StarLoopEntryState *getLoopEntryState(); + + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/TokensStartState.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/TokensStartState.h new file mode 100644 index 0000000..e534d04 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/TokensStartState.h @@ -0,0 +1,21 @@ +/* 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. + */ + +#pragma once + +#include "atn/DecisionState.h" + +namespace antlr4 { +namespace atn { + + /// The Tokens rule start state linking to each lexer rule start state. + class ANTLR4CPP_PUBLIC TokensStartState final : public DecisionState { + + public: + virtual size_t getStateType() override; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/Transition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/Transition.h new file mode 100644 index 0000000..ffed2f5 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/Transition.h @@ -0,0 +1,76 @@ +/* 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. + */ + +#pragma once + +#include "misc/IntervalSet.h" + +namespace antlr4 { +namespace atn { + + /// + /// An ATN transition between any two ATN states. Subclasses define + /// atom, set, epsilon, action, predicate, rule transitions. + ///

+ /// This is a one way link. It emanates from a state (usually via a list of + /// transitions) and has a target state. + ///

+ /// Since we never have to change the ATN transitions once we construct it, + /// we can fix these transitions as specific classes. The DFA transitions + /// on the other hand need to update the labels as it adds transitions to + /// the states. We'll use the term Edge for the DFA to distinguish them from + /// ATN transitions. + ///

+ class ANTLR4CPP_PUBLIC Transition { + public: + // constants for serialization + enum SerializationType { + EPSILON = 1, + RANGE = 2, + RULE = 3, + PREDICATE = 4, // e.g., {isType(input.LT(1))}? + ATOM = 5, + ACTION = 6, + SET = 7, // ~(A|B) or ~atom, wildcard, which convert to next 2 + NOT_SET = 8, + WILDCARD = 9, + PRECEDENCE = 10, + }; + + static const std::vector serializationNames; + + /// The target of this transition. + // ml: this is a reference into the ATN. + ATNState *target; + + virtual ~Transition(); + + protected: + Transition(ATNState *target); + + public: + virtual SerializationType getSerializationType() const = 0; + + /** + * Determines if the transition is an "epsilon" transition. + * + *

The default implementation returns {@code false}.

+ * + * @return {@code true} if traversing this transition in the ATN does not + * consume an input symbol; otherwise, {@code false} if traversing this + * transition consumes (matches) an input symbol. + */ + virtual bool isEpsilon() const; + virtual misc::IntervalSet label() const; + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const = 0; + + virtual std::string toString() const; + + Transition(Transition const&) = delete; + Transition& operator=(Transition const&) = delete; + }; + +} // namespace atn +} // namespace antlr4 diff --git a/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/WildcardTransition.h b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/WildcardTransition.h new file mode 100644 index 0000000..c47c717 --- /dev/null +++ b/antlr4-cpp-runtime-4.9.2-source/install/include/antlr4-runtime/atn/WildcardTransition.h @@ -0,0 +1,25 @@ +/* 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. + */ + +#pragma once + +#include "atn/Transition.h" + +namespace antlr4 { +namespace atn { + + class ANTLR4CPP_PUBLIC WildcardTransition final : public Transition { + public: + WildcardTransition(ATNState *target); + + virtual SerializationType getSerializationType() const override; + + virtual bool matches(size_t symbol, size_t minVocabSymbol, size_t maxVocabSymbol) const override; + + virtual std::string toString() const override; + }; + +} // namespace atn +} // namespace antlr4 -- cgit v1.2.3