1# 2# Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. 3# Use of this file is governed by the BSD 3-clause license that 4# can be found in the LICENSE.txt file in the project root. 5#/ 6from antlr4.IntervalSet import IntervalSet 7from antlr4.Token import Token 8from antlr4.PredictionContext import PredictionContext, SingletonPredictionContext, PredictionContextFromRuleContext 9from antlr4.RuleContext import RuleContext 10from antlr4.atn.ATN import ATN 11from antlr4.atn.ATNConfig import ATNConfig 12from antlr4.atn.ATNState import ATNState, RuleStopState 13from antlr4.atn.Transition import WildcardTransition, NotSetTransition, AbstractPredicateTransition, RuleTransition 14 15 16class LL1Analyzer (object): 17 18 #* Special value added to the lookahead sets to indicate that we hit 19 # a predicate during analysis if {@code seeThruPreds==false}. 20 #/ 21 HIT_PRED = Token.INVALID_TYPE 22 23 def __init__(self, atn:ATN): 24 self.atn = atn 25 26 #* 27 # Calculates the SLL(1) expected lookahead set for each outgoing transition 28 # of an {@link ATNState}. The returned array has one element for each 29 # outgoing transition in {@code s}. If the closure from transition 30 # <em>i</em> leads to a semantic predicate before matching a symbol, the 31 # element at index <em>i</em> of the result will be {@code null}. 32 # 33 # @param s the ATN state 34 # @return the expected symbols for each outgoing transition of {@code s}. 35 #/ 36 def getDecisionLookahead(self, s:ATNState): 37 if s is None: 38 return None 39 40 count = len(s.transitions) 41 look = [] * count 42 for alt in range(0, count): 43 look[alt] = set() 44 lookBusy = set() 45 seeThruPreds = False # fail to get lookahead upon pred 46 self._LOOK(s.transition(alt).target, None, PredictionContext.EMPTY, 47 look[alt], lookBusy, set(), seeThruPreds, False) 48 # Wipe out lookahead for this alternative if we found nothing 49 # or we had a predicate when we !seeThruPreds 50 if len(look[alt])==0 or self.HIT_PRED in look[alt]: 51 look[alt] = None 52 return look 53 54 #* 55 # Compute set of tokens that can follow {@code s} in the ATN in the 56 # specified {@code ctx}. 57 # 58 # <p>If {@code ctx} is {@code null} and the end of the rule containing 59 # {@code s} is reached, {@link Token#EPSILON} is added to the result set. 60 # If {@code ctx} is not {@code null} and the end of the outermost rule is 61 # reached, {@link Token#EOF} is added to the result set.</p> 62 # 63 # @param s the ATN state 64 # @param stopState the ATN state to stop at. This can be a 65 # {@link BlockEndState} to detect epsilon paths through a closure. 66 # @param ctx the complete parser context, or {@code null} if the context 67 # should be ignored 68 # 69 # @return The set of tokens that can follow {@code s} in the ATN in the 70 # specified {@code ctx}. 71 #/ 72 def LOOK(self, s:ATNState, stopState:ATNState=None, ctx:RuleContext=None): 73 r = IntervalSet() 74 seeThruPreds = True # ignore preds; get all lookahead 75 lookContext = PredictionContextFromRuleContext(s.atn, ctx) if ctx is not None else None 76 self._LOOK(s, stopState, lookContext, r, set(), set(), seeThruPreds, True) 77 return r 78 79 #* 80 # Compute set of tokens that can follow {@code s} in the ATN in the 81 # specified {@code ctx}. 82 # 83 # <p>If {@code ctx} is {@code null} and {@code stopState} or the end of the 84 # rule containing {@code s} is reached, {@link Token#EPSILON} is added to 85 # the result set. If {@code ctx} is not {@code null} and {@code addEOF} is 86 # {@code true} and {@code stopState} or the end of the outermost rule is 87 # reached, {@link Token#EOF} is added to the result set.</p> 88 # 89 # @param s the ATN state. 90 # @param stopState the ATN state to stop at. This can be a 91 # {@link BlockEndState} to detect epsilon paths through a closure. 92 # @param ctx The outer context, or {@code null} if the outer context should 93 # not be used. 94 # @param look The result lookahead set. 95 # @param lookBusy A set used for preventing epsilon closures in the ATN 96 # from causing a stack overflow. Outside code should pass 97 # {@code new HashSet<ATNConfig>} for this argument. 98 # @param calledRuleStack A set used for preventing left recursion in the 99 # ATN from causing a stack overflow. Outside code should pass 100 # {@code new BitSet()} for this argument. 101 # @param seeThruPreds {@code true} to true semantic predicates as 102 # implicitly {@code true} and "see through them", otherwise {@code false} 103 # to treat semantic predicates as opaque and add {@link #HIT_PRED} to the 104 # result if one is encountered. 105 # @param addEOF Add {@link Token#EOF} to the result if the end of the 106 # outermost context is reached. This parameter has no effect if {@code ctx} 107 # is {@code null}. 108 #/ 109 def _LOOK(self, s:ATNState, stopState:ATNState , ctx:PredictionContext, look:IntervalSet, lookBusy:set, 110 calledRuleStack:set, seeThruPreds:bool, addEOF:bool): 111 c = ATNConfig(s, 0, ctx) 112 113 if c in lookBusy: 114 return 115 lookBusy.add(c) 116 117 if s == stopState: 118 if ctx is None: 119 look.addOne(Token.EPSILON) 120 return 121 elif ctx.isEmpty() and addEOF: 122 look.addOne(Token.EOF) 123 return 124 125 if isinstance(s, RuleStopState ): 126 if ctx is None: 127 look.addOne(Token.EPSILON) 128 return 129 elif ctx.isEmpty() and addEOF: 130 look.addOne(Token.EOF) 131 return 132 133 if ctx != PredictionContext.EMPTY: 134 # run thru all possible stack tops in ctx 135 for i in range(0, len(ctx)): 136 returnState = self.atn.states[ctx.getReturnState(i)] 137 removed = returnState.ruleIndex in calledRuleStack 138 try: 139 calledRuleStack.discard(returnState.ruleIndex) 140 self._LOOK(returnState, stopState, ctx.getParent(i), look, lookBusy, calledRuleStack, seeThruPreds, addEOF) 141 finally: 142 if removed: 143 calledRuleStack.add(returnState.ruleIndex) 144 return 145 146 for t in s.transitions: 147 if type(t) == RuleTransition: 148 if t.target.ruleIndex in calledRuleStack: 149 continue 150 151 newContext = SingletonPredictionContext.create(ctx, t.followState.stateNumber) 152 153 try: 154 calledRuleStack.add(t.target.ruleIndex) 155 self._LOOK(t.target, stopState, newContext, look, lookBusy, calledRuleStack, seeThruPreds, addEOF) 156 finally: 157 calledRuleStack.remove(t.target.ruleIndex) 158 elif isinstance(t, AbstractPredicateTransition ): 159 if seeThruPreds: 160 self._LOOK(t.target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF) 161 else: 162 look.addOne(self.HIT_PRED) 163 elif t.isEpsilon: 164 self._LOOK(t.target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF) 165 elif type(t) == WildcardTransition: 166 look.addRange( range(Token.MIN_USER_TOKEN_TYPE, self.atn.maxTokenType + 1) ) 167 else: 168 set_ = t.label 169 if set_ is not None: 170 if isinstance(t, NotSetTransition): 171 set_ = set_.complement(Token.MIN_USER_TOKEN_TYPE, self.atn.maxTokenType) 172 look.addSet(set_) 173