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