| /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. |
| * Use of this file is governed by the BSD 3-clause license that |
| * can be found in the LICENSE.txt file in the project root. |
| */ |
| using System.Collections.Generic; |
| using Antlr4.Runtime.Misc; |
| using Antlr4.Runtime.Sharpen; |
| |
| namespace Antlr4.Runtime.Atn |
| { |
| public class LL1Analyzer |
| { |
| /** Special value added to the lookahead sets to indicate that we hit |
| * a predicate during analysis if {@code seeThruPreds==false}. |
| */ |
| public const int HitPred = TokenConstants.InvalidType; |
| |
| [NotNull] |
| public readonly ATN atn; |
| |
| public LL1Analyzer(ATN atn) |
| { |
| this.atn = atn; |
| } |
| |
| /** |
| * Calculates the SLL(1) expected lookahead set for each outgoing transition |
| * of an {@link ATNState}. The returned array has one element for each |
| * outgoing transition in {@code s}. If the closure from transition |
| * <em>i</em> leads to a semantic predicate before matching a symbol, the |
| * element at index <em>i</em> of the result will be {@code null}. |
| * |
| * @param s the ATN state |
| * @return the expected symbols for each outgoing transition of {@code s}. |
| */ |
| [return: Nullable] |
| public virtual IntervalSet[] GetDecisionLookahead(ATNState s) |
| { |
| // System.out.println("LOOK("+s.stateNumber+")"); |
| if (s == null) |
| { |
| return null; |
| } |
| IntervalSet[] look = new IntervalSet[s.NumberOfTransitions]; |
| for (int alt = 0; alt < s.NumberOfTransitions; alt++) |
| { |
| look[alt] = new IntervalSet(); |
| HashSet<ATNConfig> lookBusy = new HashSet<ATNConfig>(); |
| bool seeThruPreds = false; |
| // fail to get lookahead upon pred |
| Look_(s.Transition(alt).target, null, EmptyPredictionContext.Instance, look[alt], lookBusy, new BitSet(), seeThruPreds, false); |
| // Wipe out lookahead for this alternative if we found nothing |
| // or we had a predicate when we !seeThruPreds |
| if (look[alt].Count == 0 || look[alt].Contains(HitPred)) |
| { |
| look[alt] = null; |
| } |
| } |
| return look; |
| } |
| |
| /** |
| * Compute set of tokens that can follow {@code s} in the ATN in the |
| * specified {@code ctx}. |
| * |
| * <p>If {@code ctx} is {@code null} and the end of the rule containing |
| * {@code s} is reached, {@link Token#EPSILON} is added to the result set. |
| * If {@code ctx} is not {@code null} and the end of the outermost rule is |
| * reached, {@link Token#EOF} is added to the result set.</p> |
| * |
| * @param s the ATN state |
| * @param ctx the complete parser context, or {@code null} if the context |
| * should be ignored |
| * |
| * @return The set of tokens that can follow {@code s} in the ATN in the |
| * specified {@code ctx}. |
| */ |
| [return: NotNull] |
| public virtual IntervalSet Look(ATNState s, RuleContext ctx) |
| { |
| return Look(s, null, ctx); |
| } |
| |
| /** |
| * Compute set of tokens that can follow {@code s} in the ATN in the |
| * specified {@code ctx}. |
| * |
| * <p>If {@code ctx} is {@code null} and the end of the rule containing |
| * {@code s} is reached, {@link Token#EPSILON} is added to the result set. |
| * If {@code ctx} is not {@code null} and the end of the outermost rule is |
| * reached, {@link Token#EOF} is added to the result set.</p> |
| * |
| * @param s the ATN state |
| * @param stopState the ATN state to stop at. This can be a |
| * {@link BlockEndState} to detect epsilon paths through a closure. |
| * @param ctx the complete parser context, or {@code null} if the context |
| * should be ignored |
| * |
| * @return The set of tokens that can follow {@code s} in the ATN in the |
| * specified {@code ctx}. |
| */ |
| [return: NotNull] |
| public virtual IntervalSet Look(ATNState s, ATNState stopState, RuleContext ctx) |
| { |
| IntervalSet r = new IntervalSet(); |
| bool seeThruPreds = true; |
| PredictionContext lookContext = ctx != null ? PredictionContext.FromRuleContext(s.atn, ctx) : null; |
| Look_(s, stopState, lookContext, r, new HashSet<ATNConfig>(), new BitSet(), seeThruPreds, true); |
| return r; |
| } |
| |
| /** |
| * Compute set of tokens that can follow {@code s} in the ATN in the |
| * specified {@code ctx}. |
| * |
| * <p>If {@code ctx} is {@code null} and {@code stopState} or the end of the |
| * rule containing {@code s} is reached, {@link Token#EPSILON} is added to |
| * the result set. If {@code ctx} is not {@code null} and {@code addEOF} is |
| * {@code true} and {@code stopState} or the end of the outermost rule is |
| * reached, {@link Token#EOF} is added to the result set.</p> |
| * |
| * @param s the ATN state. |
| * @param stopState the ATN state to stop at. This can be a |
| * {@link BlockEndState} to detect epsilon paths through a closure. |
| * @param ctx The outer context, or {@code null} if the outer context should |
| * not be used. |
| * @param look The result lookahead set. |
| * @param lookBusy A set used for preventing epsilon closures in the ATN |
| * from causing a stack overflow. Outside code should pass |
| * {@code new HashSet<ATNConfig>} for this argument. |
| * @param calledRuleStack A set used for preventing left recursion in the |
| * ATN from causing a stack overflow. Outside code should pass |
| * {@code new BitSet()} for this argument. |
| * @param seeThruPreds {@code true} to true semantic predicates as |
| * implicitly {@code true} and "see through them", otherwise {@code false} |
| * to treat semantic predicates as opaque and add {@link #HIT_PRED} to the |
| * result if one is encountered. |
| * @param addEOF Add {@link Token#EOF} to the result if the end of the |
| * outermost context is reached. This parameter has no effect if {@code ctx} |
| * is {@code null}. |
| */ |
| protected internal virtual void Look_(ATNState s, ATNState stopState, PredictionContext ctx, IntervalSet look, HashSet<ATNConfig> lookBusy, BitSet calledRuleStack, bool seeThruPreds, bool addEOF) |
| { |
| ATNConfig c = new ATNConfig(s, 0, ctx); |
| if (!lookBusy.Add(c)) |
| { |
| return; |
| } |
| if (s == stopState) |
| { |
| if (ctx == null) |
| { |
| look.Add(TokenConstants.EPSILON); |
| return; |
| } |
| else if (ctx.IsEmpty && addEOF) |
| { |
| look.Add(TokenConstants.EOF); |
| return; |
| } |
| } |
| if (s is RuleStopState) |
| { |
| if (ctx == null) |
| { |
| look.Add(TokenConstants.EPSILON); |
| return; |
| } |
| else if (ctx.IsEmpty && addEOF) |
| { |
| look.Add(TokenConstants.EOF); |
| return; |
| } |
| if (ctx != EmptyPredictionContext.Instance) |
| { |
| bool removed = calledRuleStack.Get(s.ruleIndex); |
| try |
| { |
| calledRuleStack.Clear(s.ruleIndex); |
| for (int i = 0; i < ctx.Size; i++) |
| { |
| ATNState returnState = atn.states[ctx.GetReturnState(i)]; |
| Look_(returnState, stopState, ctx.GetParent(i), look, lookBusy, calledRuleStack, seeThruPreds, addEOF); |
| } |
| } |
| finally |
| { |
| if (removed) |
| { |
| calledRuleStack.Set(s.ruleIndex); |
| } |
| } |
| return; |
| } |
| } |
| int n = s.NumberOfTransitions; |
| for (int i_1 = 0; i_1 < n; i_1++) |
| { |
| Transition t = s.Transition(i_1); |
| if (t.GetType() == typeof(RuleTransition)) |
| { |
| RuleTransition ruleTransition = (RuleTransition)t; |
| if (calledRuleStack.Get(ruleTransition.ruleIndex)) |
| { |
| continue; |
| } |
| PredictionContext newContext = SingletonPredictionContext.Create(ctx, ruleTransition.followState.stateNumber); |
| try |
| { |
| calledRuleStack.Set(ruleTransition.target.ruleIndex); |
| Look_(t.target, stopState, newContext, look, lookBusy, calledRuleStack, seeThruPreds, addEOF); |
| } |
| finally |
| { |
| calledRuleStack.Clear(ruleTransition.target.ruleIndex); |
| } |
| } |
| else if (t is AbstractPredicateTransition) |
| { |
| if (seeThruPreds) |
| { |
| Look_(t.target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF); |
| } |
| else |
| { |
| look.Add(HitPred); |
| } |
| } |
| else if (t.IsEpsilon) |
| { |
| Look_(t.target, stopState, ctx, look, lookBusy, calledRuleStack, seeThruPreds, addEOF); |
| } |
| else if (t.GetType() == typeof(WildcardTransition)) |
| { |
| look.AddAll(IntervalSet.Of(TokenConstants.MinUserTokenType, atn.maxTokenType)); |
| } |
| else |
| { |
| IntervalSet set = t.Label; |
| if (set != null) |
| { |
| if (t is NotSetTransition) |
| { |
| set = set.Complement(IntervalSet.Of(TokenConstants.MinUserTokenType, atn.maxTokenType)); |
| } |
| look.AddAll(set); |
| } |
| } |
| } |
| } |
| } |
| } |
