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