1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD license"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2010 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.analysis; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.grammar.v3.ANTLRParser; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.IntSet; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.IntervalSet; 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.Grammar; 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.Rule; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.HashMap; 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.HashSet; 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Map; 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Set; 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Created by IntelliJ IDEA. 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * User: parrt 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Date: Dec 31, 2007 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Time: 1:31:16 PM 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * To change this template use File | Settings | File Templates. 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class LL1Analyzer { 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 0 if we hit end of rule and invoker should keep going (epsilon) */ 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int DETECT_PRED_EOR = 0; 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 1 if we found a nonautobacktracking pred */ 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int DETECT_PRED_FOUND = 1; 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 2 if we didn't find such a pred */ 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int DETECT_PRED_NOT_FOUND = 2; 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Grammar grammar; 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Used during LOOK to detect computation cycles */ 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set<NFAState> lookBusy = new HashSet<NFAState>(); 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Map<NFAState, LookaheadSet> FIRSTCache = new HashMap<NFAState, LookaheadSet>(); 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Map<Rule, LookaheadSet> FOLLOWCache = new HashMap<Rule, LookaheadSet>(); 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LL1Analyzer(Grammar grammar) { 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.grammar = grammar; 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void computeRuleFIRSTSets() { 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( getNumberOfDecisions()==0 ) { 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver createNFAs(); 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = getRules().iterator(); it.hasNext();) { 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Rule r = (Rule)it.next(); 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( r.isSynPred ) { 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet s = FIRST(r); 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("FIRST("+r.name+")="+s); 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Set<String> getOverriddenRulesWithDifferentFIRST() { 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk every rule in this grammar and compare FIRST set with 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // those in imported grammars. 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<String> rules = new HashSet(); 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = getRules().iterator(); it.hasNext();) { 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Rule r = (Rule)it.next(); 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println(r.name+" FIRST="+r.FIRST); 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < delegates.size(); i++) { 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Grammar g = delegates.get(i); 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Rule importedRule = g.getRule(r.name); 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( importedRule != null ) { // exists in imported grammar 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // System.out.println(r.name+" exists in imported grammar: FIRST="+importedRule.FIRST); 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !r.FIRST.equals(importedRule.FIRST) ) { 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver rules.add(r.name); 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return rules; 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Set<Rule> getImportedRulesSensitiveToOverriddenRulesDueToLOOK() { 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<String> diffFIRSTs = getOverriddenRulesWithDifferentFIRST(); 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<Rule> rules = new HashSet(); 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = diffFIRSTs.iterator(); it.hasNext();) { 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String r = (String) it.next(); 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < delegates.size(); i++) { 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Grammar g = delegates.get(i); 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<Rule> callers = g.ruleSensitivity.get(r); 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // somebody invokes rule whose FIRST changed in subgrammar? 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( callers!=null ) { 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver rules.addAll(callers); 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println(g.name+" rules "+callers+" sensitive to "+r+"; dup 'em"); 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return rules; 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver*/ 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LookaheadSet LOOK(Rule r) { 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( r.FIRST==null ) { 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver r.FIRST = FIRST(r.startState); 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return r.FIRST; 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver*/ 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** From an NFA state, s, find the set of all labels reachable from s. 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Used to compute follow sets for error recovery. Never computes 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a FOLLOW operation. FIRST stops at end of rules, returning EOR, unless 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * invoked from another rule. I.e., routine properly handles 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : b A ; 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * where b is nullable. 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * We record with EOR_TOKEN_TYPE if we hit the end of a rule so we can 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * know at runtime (when these sets are used) to start walking up the 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * follow chain to compute the real, correct follow set (as opposed to 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the FOLLOW, which is a superset). 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This routine will only be used on parser and tree parser grammars. 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LookaheadSet FIRST(NFAState s) { 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("> FIRST("+s.enclosingRule.name+") in rule "+s.enclosingRule); 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lookBusy.clear(); 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet look = _FIRST(s, false); 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("< FIRST("+s.enclosingRule.name+") in rule "+s.enclosingRule+"="+look.toString(this.grammar)); 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return look; 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LookaheadSet FOLLOW(Rule r) { 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("> FOLLOW("+r.name+") in rule "+r.startState.enclosingRule); 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet f = FOLLOWCache.get(r); 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( f!=null ) { 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return f; 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver f = _FIRST(r.stopState, true); 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver FOLLOWCache.put(r, f); 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("< FOLLOW("+r+") in rule "+r.startState.enclosingRule+"="+f.toString(this.grammar)); 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return f; 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LookaheadSet LOOK(NFAState s) { 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( NFAToDFAConverter.debug ) { 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("> LOOK("+s+")"); 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lookBusy.clear(); 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet look = _FIRST(s, true); 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // FOLLOW makes no sense (at the moment!) for lexical rules. 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( grammar.type!=Grammar.LEXER && look.member(Label.EOR_TOKEN_TYPE) ) { 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // avoid altering FIRST reset as it is cached 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet f = FOLLOW(s.enclosingRule); 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver f.orInPlace(look); 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver f.remove(Label.EOR_TOKEN_TYPE); 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver look = f; 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //look.orInPlace(FOLLOW(s.enclosingRule)); 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( grammar.type==Grammar.LEXER && look.member(Label.EOT) ) { 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if this has EOT, lookahead is all char (all char can follow rule) 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //look = new LookaheadSet(Label.EOT); 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver look = new LookaheadSet(IntervalSet.COMPLETE_SET); 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( NFAToDFAConverter.debug ) { 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("< LOOK("+s+")="+look.toString(grammar)); 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return look; 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected LookaheadSet _FIRST(NFAState s, boolean chaseFollowTransitions) { 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("_LOOK("+s+") in rule "+s.enclosingRule); 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s.transition[0] instanceof RuleClosureTransition ) { 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("go to rule "+((NFAState)s.transition[0].target).enclosingRule); 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !chaseFollowTransitions && s.isAcceptState() ) { 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( grammar.type==Grammar.LEXER ) { 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // FOLLOW makes no sense (at the moment!) for lexical rules. 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // assume all char can follow 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new LookaheadSet(IntervalSet.COMPLETE_SET); 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new LookaheadSet(Label.EOR_TOKEN_TYPE); 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( lookBusy.contains(s) ) { 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // return a copy of an empty set; we may modify set inline 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new LookaheadSet(); 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lookBusy.add(s); 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition0 = s.transition[0]; 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0==null ) { 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0.label.isAtom() ) { 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int atom = transition0.label.getAtom(); 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new LookaheadSet(atom); 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0.label.isSet() ) { 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntSet sl = transition0.label.getSet(); 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new LookaheadSet(sl); 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // compute FIRST of transition 0 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet tset = null; 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if transition 0 is a rule call and we don't want FOLLOW, check cache 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !chaseFollowTransitions && transition0 instanceof RuleClosureTransition ) { 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tset = FIRSTCache.get((NFAState)transition0.target); 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if not in cache, must compute 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( tset==null ) { 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tset = _FIRST((NFAState)transition0.target, chaseFollowTransitions); 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // save FIRST cache for transition 0 if rule call 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !chaseFollowTransitions && transition0 instanceof RuleClosureTransition ) { 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver FIRSTCache.put((NFAState)transition0.target, tset); 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet tsetCached = tset; // tset is stored in cache. We can't return the same instance 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // did we fall off the end? 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( grammar.type!=Grammar.LEXER && tset.member(Label.EOR_TOKEN_TYPE) ) { 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0 instanceof RuleClosureTransition ) { 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // we called a rule that found the end of the rule. 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // That means the rule is nullable and we need to 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // keep looking at what follows the rule ref. E.g., 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // a : b A ; where b is nullable means that LOOK(a) 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // should include A. 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver RuleClosureTransition ruleInvocationTrans = 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (RuleClosureTransition)transition0; 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // remove the EOR and get what follows 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //tset.remove(Label.EOR_TOKEN_TYPE); 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState following = (NFAState) ruleInvocationTrans.followState; 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet fset = _FIRST(following, chaseFollowTransitions); 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver fset.orInPlace(tset); // tset cached; or into new set 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver fset.remove(Label.EOR_TOKEN_TYPE); 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tset = fset; 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition1 = s.transition[1]; 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition1!=null ) { 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver LookaheadSet tset1 = 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _FIRST((NFAState)transition1.target, chaseFollowTransitions); 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tset1.orInPlace(tset); 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tset = tset1; 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // never return a cached set; clone 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return tset==tsetCached ? new LookaheadSet(tset) : tset; 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Is there a non-syn-pred predicate visible from s that is not in 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the rule enclosing s? This accounts for most predicate situations 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and lets ANTLR do a simple LL(1)+pred computation. 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO: what about gated vs regular preds? 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean detectConfoundingPredicates(NFAState s) { 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lookBusy.clear(); 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Rule r = s.enclosingRule; 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _detectConfoundingPredicates(s, r, false) == DETECT_PRED_FOUND; 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int _detectConfoundingPredicates(NFAState s, 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Rule enclosingRule, 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean chaseFollowTransitions) 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("_detectNonAutobacktrackPredicates("+s+")"); 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !chaseFollowTransitions && s.isAcceptState() ) { 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( grammar.type==Grammar.LEXER ) { 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // FOLLOW makes no sense (at the moment!) for lexical rules. 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // assume all char can follow 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_NOT_FOUND; 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_EOR; 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( lookBusy.contains(s) ) { 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // return a copy of an empty set; we may modify set inline 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_NOT_FOUND; 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lookBusy.add(s); 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition0 = s.transition[0]; 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0==null ) { 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_NOT_FOUND; 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !(transition0.label.isSemanticPredicate()|| 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver transition0.label.isEpsilon()) ) { 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_NOT_FOUND; 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0.label.isSemanticPredicate() ) { 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("pred "+transition0.label); 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext ctx = transition0.label.getSemanticContext(); 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.Predicate p = (SemanticContext.Predicate)ctx; 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( p.predicateAST.getType() != ANTLRParser.BACKTRACK_SEMPRED ) { 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_FOUND; 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0.label.isSemanticPredicate() ) { 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("pred "+transition0.label); 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext ctx = transition0.label.getSemanticContext(); 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.Predicate p = (SemanticContext.Predicate)ctx; 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if a non-syn-pred found not in enclosingRule, say we found one 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( p.predicateAST.getType() != ANTLRParser.BACKTRACK_SEMPRED && 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver !p.predicateAST.enclosingRuleName.equals(enclosingRule.name) ) 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("found pred "+p+" not in "+enclosingRule.name); 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_FOUND; 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int result = _detectConfoundingPredicates((NFAState)transition0.target, 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver enclosingRule, 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver chaseFollowTransitions); 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( result == DETECT_PRED_FOUND ) { 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_FOUND; 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( result == DETECT_PRED_EOR ) { 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0 instanceof RuleClosureTransition ) { 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // we called a rule that found the end of the rule. 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // That means the rule is nullable and we need to 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // keep looking at what follows the rule ref. E.g., 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // a : b A ; where b is nullable means that LOOK(a) 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // should include A. 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver RuleClosureTransition ruleInvocationTrans = 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (RuleClosureTransition)transition0; 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState following = (NFAState) ruleInvocationTrans.followState; 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int afterRuleResult = 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _detectConfoundingPredicates(following, 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver enclosingRule, 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver chaseFollowTransitions); 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( afterRuleResult == DETECT_PRED_FOUND ) { 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_FOUND; 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition1 = s.transition[1]; 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition1!=null ) { 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int t1Result = 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _detectConfoundingPredicates((NFAState)transition1.target, 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver enclosingRule, 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver chaseFollowTransitions); 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t1Result == DETECT_PRED_FOUND ) { 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_FOUND; 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return DETECT_PRED_NOT_FOUND; 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return predicate expression found via epsilon edges from s. Do 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * not look into other rules for now. Do something simple. Include 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * backtracking synpreds. 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public SemanticContext getPredicates(NFAState altStartState) { 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lookBusy.clear(); 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _getPredicates(altStartState, altStartState); 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected SemanticContext _getPredicates(NFAState s, NFAState altStartState) { 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("_getPredicates("+s+")"); 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s.isAcceptState() ) { 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // avoid infinite loops from (..)* etc... 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( lookBusy.contains(s) ) { 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lookBusy.add(s); 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition0 = s.transition[0]; 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no transitions 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0==null ) { 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // not a predicate and not even an epsilon 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !(transition0.label.isSemanticPredicate()|| 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver transition0.label.isEpsilon()) ) { 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext p = null; 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext p0 = null; 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext p1 = null; 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0.label.isSemanticPredicate() ) { 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("pred "+transition0.label); 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver p = transition0.label.getSemanticContext(); 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // ignore backtracking preds not on left edge for this decision 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( ((SemanticContext.Predicate)p).predicateAST.getType() == 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLRParser.BACKTRACK_SEMPRED && 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s == altStartState.transition[0].target ) 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver p = null; // don't count 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // get preds from beyond this state 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver p0 = _getPredicates((NFAState)transition0.target, altStartState); 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // get preds from other transition 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition1 = s.transition[1]; 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition1!=null ) { 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver p1 = _getPredicates((NFAState)transition1.target, altStartState); 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // join this&following-right|following-down 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return SemanticContext.and(p,SemanticContext.or(p0,p1)); 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 450