Package org.antlr.v4.runtime

Class ParserInterpreter

java.lang.Object
org.antlr.v4.runtime.Recognizer<Token,ParserATNSimulator>
org.antlr.v4.runtime.Parser
org.antlr.v4.runtime.ParserInterpreter
Direct Known Subclasses:
GrammarParserInterpreter
public class ParserInterpreter extends Parser
A parser simulator that mimics what ANTLR's generated parser code does. A ParserATNSimulator is used to make predictions via adaptivePredict but this class moves a pointer through the ATN to simulate parsing. ParserATNSimulator just makes us efficient rather than having to backtrack, for example.

This properly creates parse trees even for left recursive rules.

We rely on the left recursive rule invocation and special predicate transitions to make left recursive rules work.

See TestParserInterpreter for examples.

  • Field Details

    • grammarFileName

      protected final String grammarFileName

    • atn

      protected final ATN atn

    • pushRecursionContextStates

      protected final BitSet pushRecursionContextStates
      This identifies StarLoopEntryState's that begin the (...)* precedence loops of left recursive rules.

    • ruleNames

      protected final String[] ruleNames

    • _parentContextStack

      protected final Deque<Pair<ParserRuleContext,Integer>> _parentContextStack
      This stack corresponds to the _parentctx, _parentState pair of locals that would exist on call stack frames with a recursive descent parser; in the generated function for a left-recursive rule you'd see:

      private EContext e(int _p) throws RecognitionException { ParserRuleContext _parentctx = _ctx; // Pair.a int _parentState = getState(); // Pair.b ... }

      Those values are used to create new recursive rule invocation contexts associated with left operand of an alt like "expr '*' expr".

    • overrideDecision

      protected int overrideDecision
      We need a map from (decision,inputIndex)->forced alt for computing ambiguous parse trees. For now, we allow exactly one override.

    • overrideDecisionInputIndex

      protected int overrideDecisionInputIndex

    • overrideDecisionAlt

      protected int overrideDecisionAlt

    • overrideDecisionReached

      protected boolean overrideDecisionReached

    • overrideDecisionRoot

      protected InterpreterRuleContext overrideDecisionRoot
      What is the current context when we override a decisions? This tells us what the root of the parse tree is when using override for an ambiguity/lookahead check.

    • rootContext

      protected InterpreterRuleContext rootContext

  • Constructor Details

    • ParserInterpreter

      public ParserInterpreter(@NotNull ParserInterpreter old)
      A copy constructor that creates a new parser interpreter by reusing the fields of a previous interpreter.
      Parameters:
      old - The interpreter to copy
      Since:
      4.5

    • ParserInterpreter

      public ParserInterpreter(String grammarFileName, @NotNull Vocabulary vocabulary, Collection<String> ruleNames, ATN atn, TokenStream input)

  • Method Details

    • reset

      public void reset()
      Description copied from class: Parser
      reset the parser's state
      Overrides:
      reset in class Parser

    • getATN

      public ATN getATN()
      Description copied from class: Recognizer
      Get the ATN used by the recognizer for prediction.
      Overrides:
      getATN in class Recognizer<Token,ParserATNSimulator>
      Returns:
      The ATN used by the recognizer for prediction.

    • getVocabulary

      public Vocabulary getVocabulary()
      Specified by:
      getVocabulary in class Recognizer<Token,ParserATNSimulator>

    • getRuleNames

      public String[] getRuleNames()
      Specified by:
      getRuleNames in class Recognizer<Token,ParserATNSimulator>

    • getGrammarFileName

      public String getGrammarFileName()
      Specified by:
      getGrammarFileName in class Recognizer<Token,ParserATNSimulator>

    • parse

      public ParserRuleContext parse(int startRuleIndex)
      Begin parsing at startRuleIndex

    • enterRecursionRule

      public void enterRecursionRule(ParserRuleContext localctx, int state, int ruleIndex, int precedence)
      Overrides:
      enterRecursionRule in class Parser

    • getATNState

      protected ATNState getATNState()

    • visitState

      protected void visitState(ATNState p)

    • visitDecisionState

      protected int visitDecisionState(DecisionState p)
      Method visitDecisionState() is called when the interpreter reaches a decision state (instance of DecisionState). It gives an opportunity for subclasses to track interesting things.

    • createInterpreterRuleContext

      protected InterpreterRuleContext createInterpreterRuleContext(ParserRuleContext parent, int invokingStateNumber, int ruleIndex)
      Provide simple "factory" for InterpreterRuleContext's.
      Since:
      4.5.1

    • visitRuleStopState

      protected void visitRuleStopState(ATNState p)

    • addDecisionOverride

      public void addDecisionOverride(int decision, int tokenIndex, int forcedAlt)
      Override this parser interpreters normal decision-making process at a particular decision and input token index. Instead of allowing the adaptive prediction mechanism to choose the first alternative within a block that leads to a successful parse, force it to take the alternative, 1..n for n alternatives.

      As an implementation limitation right now, you can only specify one override. This is sufficient to allow construction of different parse trees for ambiguous input. It means re-parsing the entire input in general because you're never sure where an ambiguous sequence would live in the various parse trees. For example, in one interpretation, an ambiguous input sequence would be matched completely in expression but in another it could match all the way back to the root.

      s : e '!'? ; e : ID | ID '!' ;

      Here, x! can be matched as (s (e ID) !) or (s (e ID !)). In the first case, the ambiguous sequence is fully contained only by the root. In the second case, the ambiguous sequences fully contained within just e, as in: (e ID !).

      Rather than trying to optimize this and make some intelligent decisions for optimization purposes, I settled on just re-parsing the whole input and then using {link Trees#getRootOfSubtreeEnclosingRegion} to find the minimal subtree that contains the ambiguous sequence. I originally tried to record the call stack at the point the parser detected and ambiguity but left recursive rules create a parse tree stack that does not reflect the actual call stack. That impedance mismatch was enough to make it it challenging to restart the parser at a deeply nested rule invocation.

      Only parser interpreters can override decisions so as to avoid inserting override checking code in the critical ALL(*) prediction execution path.

      Since:
      4.5

    • recover

      protected void recover(RecognitionException e)
      Rely on the error handler for this parser but, if no tokens are consumed to recover, add an error node. Otherwise, nothing is seen in the parse tree.

    • recoverInline

      protected Token recoverInline()

    • getOverrideDecisionRoot

      public InterpreterRuleContext getOverrideDecisionRoot()
      What is the current context when we override a decisions? This tells us what the root of the parse tree is when using override for an ambiguity/lookahead check.

    • getRootContext

      public InterpreterRuleContext getRootContext()
      Return the root of the parse, which can be useful if the parser bails out. You still can access the top node. Note that, because of the way left recursive rules add children, it's possible that the root will not have any children if the start rule immediately called and left recursive rule that fails.