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 /// 6 7 8 public class LL1Analyzer { 9 /// 10 /// Special value added to the lookahead sets to indicate that we hit 11 /// a predicate during analysis if `seeThruPreds==false`. 12 /// 13 public let HIT_PRED: Int = CommonToken.INVALID_TYPE 14 15 public let atn: ATN 16 17 public init(_ atn: ATN) { 18 self.atn = atn 19 } 20 21 /// 22 /// Calculates the SLL(1) expected lookahead set for each outgoing transition 23 /// of an _org.antlr.v4.runtime.atn.ATNState_. The returned array has one element for each 24 /// outgoing transition in `s`. If the closure from transition 25 /// __i__ leads to a semantic predicate before matching a symbol, the 26 /// element at index __i__ of the result will be `null`. 27 /// 28 /// - parameter s: the ATN state 29 /// - returns: the expected symbols for each outgoing transition of `s`. 30 /// getDecisionLookaheadnull31 public func getDecisionLookahead(_ s: ATNState?) -> [IntervalSet?]? { 32 33 guard let s = s else { 34 return nil 35 } 36 let length = s.getNumberOfTransitions() 37 var look = [IntervalSet?](repeating: nil, count: length) 38 for alt in 0..<length { 39 look[alt] = IntervalSet() 40 var lookBusy = Set<ATNConfig>() 41 let seeThruPreds = false // fail to get lookahead upon pred 42 _LOOK(s.transition(alt).target, nil, PredictionContext.EMPTY, 43 look[alt]!, &lookBusy, BitSet(), seeThruPreds, false) 44 // Wipe out lookahead for this alternative if we found nothing 45 // or we had a predicate when we !seeThruPreds 46 if look[alt]!.size() == 0 || look[alt]!.contains(HIT_PRED) { 47 look[alt] = nil 48 } 49 } 50 return look 51 } 52 53 /// 54 /// Compute set of tokens that can follow `s` in the ATN in the 55 /// specified `ctx`. 56 /// 57 /// If `ctx` is `null` and the end of the rule containing 58 /// `s` is reached, _org.antlr.v4.runtime.Token#EPSILON_ is added to the result set. 59 /// If `ctx` is not `null` and the end of the outermost rule is 60 /// reached, _org.antlr.v4.runtime.Token#EOF_ is added to the result set. 61 /// 62 /// - parameter s: the ATN state 63 /// - parameter ctx: the complete parser context, or `null` if the context 64 /// should be ignored 65 /// 66 /// - returns: The set of tokens that can follow `s` in the ATN in the 67 /// specified `ctx`. 68 /// LOOKnull69 public func LOOK(_ s: ATNState, _ ctx: RuleContext?) -> IntervalSet { 70 return LOOK(s, nil, ctx) 71 } 72 73 /// 74 /// Compute set of tokens that can follow `s` in the ATN in the 75 /// specified `ctx`. 76 /// 77 /// If `ctx` is `null` and the end of the rule containing 78 /// `s` is reached, _org.antlr.v4.runtime.Token#EPSILON_ is added to the result set. 79 /// If `ctx` is not `null` and the end of the outermost rule is 80 /// reached, _org.antlr.v4.runtime.Token#EOF_ is added to the result set. 81 /// 82 /// - parameter s: the ATN state 83 /// - parameter stopState: the ATN state to stop at. This can be a 84 /// _org.antlr.v4.runtime.atn.BlockEndState_ to detect epsilon paths through a closure. 85 /// - parameter ctx: the complete parser context, or `null` if the context 86 /// should be ignored 87 /// 88 /// - returns: The set of tokens that can follow `s` in the ATN in the 89 /// specified `ctx`. 90 /// 91 LOOKnull92 public func LOOK(_ s: ATNState, _ stopState: ATNState?, _ ctx: RuleContext?) -> IntervalSet { 93 let r = IntervalSet() 94 let seeThruPreds = true // ignore preds; get all lookahead 95 let lookContext = ctx != nil ? PredictionContext.fromRuleContext(s.atn!, ctx) : nil 96 var config = Set<ATNConfig>() 97 _LOOK(s, stopState, lookContext, r, &config, BitSet(), seeThruPreds, true) 98 return r 99 } 100 101 /// 102 /// Compute set of tokens that can follow `s` in the ATN in the 103 /// specified `ctx`. 104 /// 105 /// If `ctx` is `null` and `stopState` or the end of the 106 /// rule containing `s` is reached, _org.antlr.v4.runtime.Token#EPSILON_ is added to 107 /// the result set. If `ctx` is not `null` and `addEOF` is 108 /// `true` and `stopState` or the end of the outermost rule is 109 /// reached, _org.antlr.v4.runtime.Token#EOF_ is added to the result set. 110 /// 111 /// - parameter s: the ATN state. 112 /// - parameter stopState: the ATN state to stop at. This can be a 113 /// _org.antlr.v4.runtime.atn.BlockEndState_ to detect epsilon paths through a closure. 114 /// - parameter ctx: The outer context, or `null` if the outer context should 115 /// not be used. 116 /// - parameter look: The result lookahead set. 117 /// - parameter lookBusy: A set used for preventing epsilon closures in the ATN 118 /// from causing a stack overflow. Outside code should pass 119 /// `new HashSet<ATNConfig>` for this argument. 120 /// - parameter calledRuleStack: A set used for preventing left recursion in the 121 /// ATN from causing a stack overflow. Outside code should pass 122 /// `new BitSet()` for this argument. 123 /// - parameter seeThruPreds: `true` to true semantic predicates as 124 /// implicitly `true` and "see through them", otherwise `false` 125 /// to treat semantic predicates as opaque and add _#HIT_PRED_ to the 126 /// result if one is encountered. 127 /// - parameter addEOF: Add _org.antlr.v4.runtime.Token#EOF_ to the result if the end of the 128 /// outermost context is reached. This parameter has no effect if `ctx` 129 /// is `null`. 130 /// 131 internal func _LOOK(_ s: ATNState, 132 _ stopState: ATNState?, 133 _ ctx: PredictionContext?, 134 _ look: IntervalSet, 135 _ lookBusy: inout Set<ATNConfig>, 136 _ calledRuleStack: BitSet, 137 _ seeThruPreds: Bool, 138 _ addEOF: Bool) { 139 // print ("_LOOK(\(s.stateNumber), ctx=\(ctx)"); 140 let c = ATNConfig(s, 0, ctx) 141 if lookBusy.contains(c) { 142 return 143 } else { 144 lookBusy.insert(c) 145 } 146 147 if s == stopState { 148 guard let ctx = ctx else { 149 try! look.add(CommonToken.EPSILON) 150 return 151 } 152 153 if ctx.isEmpty() && addEOF { 154 try! look.add(CommonToken.EOF) 155 return 156 } 157 158 } 159 160 if s is RuleStopState { 161 guard let ctx = ctx else { 162 try! look.add(CommonToken.EPSILON) 163 return 164 } 165 166 if ctx.isEmpty() && addEOF { 167 try! look.add(CommonToken.EOF) 168 return 169 } 170 171 if ctx != PredictionContext.EMPTY { 172 // run thru all possible stack tops in ctx 173 let length = ctx.size() 174 for i in 0..<length { 175 let returnState = atn.states[(ctx.getReturnState(i))]! 176 let removed = try! calledRuleStack.get(returnState.ruleIndex!) 177 try! calledRuleStack.clear(returnState.ruleIndex!) 178 _LOOK(returnState, stopState, ctx.getParent(i), look, &lookBusy, calledRuleStack, seeThruPreds, addEOF) 179 if removed { 180 try! calledRuleStack.set(returnState.ruleIndex!) 181 } 182 } 183 return 184 } 185 } 186 187 let n = s.getNumberOfTransitions() 188 for i in 0..<n { 189 let t = s.transition(i) 190 if let rt = t as? RuleTransition { 191 if try! calledRuleStack.get(rt.target.ruleIndex!) { 192 continue 193 } 194 195 let newContext = SingletonPredictionContext.create(ctx, rt.followState.stateNumber) 196 try! calledRuleStack.set(rt.target.ruleIndex!) 197 _LOOK(t.target, stopState, newContext, look, &lookBusy, calledRuleStack, seeThruPreds, addEOF) 198 try! calledRuleStack.clear(rt.target.ruleIndex!) 199 } 200 else if t is AbstractPredicateTransition { 201 if seeThruPreds { 202 _LOOK(t.target, stopState, ctx, look, &lookBusy, calledRuleStack, seeThruPreds, addEOF) 203 } else { 204 try! look.add(HIT_PRED) 205 } 206 } 207 else if t.isEpsilon() { 208 _LOOK(t.target, stopState, ctx, look, &lookBusy, calledRuleStack, seeThruPreds, addEOF) 209 } 210 else if t is WildcardTransition { 211 try! look.addAll(IntervalSet.of(CommonToken.MIN_USER_TOKEN_TYPE, atn.maxTokenType)) 212 } 213 else { 214 var set = t.labelIntervalSet() 215 if set != nil { 216 if t is NotSetTransition { 217 set = set!.complement(IntervalSet.of(CommonToken.MIN_USER_TOKEN_TYPE, atn.maxTokenType)) as? IntervalSet 218 } 219 try! look.addAll(set) 220 } 221 } 222 } 223 } 224 } 225