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