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.IntervalSet; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.MultiMap; 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Collections; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.Iterator; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.List; 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** A special DFA that is exactly LL(1) or LL(1) with backtracking mode 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicates to resolve edge set collisions. 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class LL1DFA extends DFA { 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** From list of lookahead sets (one per alt in decision), create 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * an LL(1) DFA. One edge per set. 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * s0-{alt1}->:o=>1 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | \ 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | -{alt2}->:o=>2 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ... 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LL1DFA(int decisionNumber, NFAState decisionStartState, LookaheadSet[] altLook) { 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState s0 = newState(); 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver startState = s0; 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nfa = decisionStartState.nfa; 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(decisionStartState); 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.decisionNumber = decisionNumber; 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.decisionNFAStartState = decisionStartState; 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver initAltRelatedInfo(); 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver unreachableAlts = null; 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int alt=1; alt<altLook.length; alt++) { 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState acceptAltState = newState(); 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver acceptAltState.acceptState = true; 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver setAcceptState(alt, acceptAltState); 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver acceptAltState.k = 1; 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver acceptAltState.cachedUniquelyPredicatedAlt = alt; 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label e = getLabelForSet(altLook[alt].tokenTypeSet); 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s0.addTransition(acceptAltState, e); 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** From a set of edgeset->list-of-alts mappings, create a DFA 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that uses syn preds for all |list-of-alts|>1. 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public LL1DFA(int decisionNumber, 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState decisionStartState, 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver MultiMap<IntervalSet, Integer> edgeMap) 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState s0 = newState(); 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver startState = s0; 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nfa = decisionStartState.nfa; 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(decisionStartState); 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.decisionNumber = decisionNumber; 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.decisionNFAStartState = decisionStartState; 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver initAltRelatedInfo(); 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver unreachableAlts = null; 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = edgeMap.keySet().iterator(); it.hasNext();) { 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IntervalSet edge = (IntervalSet)it.next(); 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<Integer> alts = edgeMap.get(edge); 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Collections.sort(alts); // make sure alts are attempted in order 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println(edge+" -> "+alts); 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState s = newState(); 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.k = 1; 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label e = getLabelForSet(edge); 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s0.addTransition(s, e); 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( alts.size()==1 ) { 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.acceptState = true; 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt = alts.get(0); 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver setAcceptState(alt, s); 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.cachedUniquelyPredicatedAlt = alt; 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // resolve with syntactic predicates. Add edges from 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // state s that test predicates. 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.resolvedWithPredicates = true; 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < alts.size(); i++) { 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt = (int)alts.get(i); 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.cachedUniquelyPredicatedAlt = NFA.INVALID_ALT_NUMBER; 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState predDFATarget = getAcceptState(alt); 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( predDFATarget==null ) { 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predDFATarget = newState(); // create if not there. 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predDFATarget.acceptState = true; 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predDFATarget.cachedUniquelyPredicatedAlt = alt; 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver setAcceptState(alt, predDFATarget); 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add a transition to pred target from d 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int walkAlt = 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver decisionStartState.translateDisplayAltToWalkAlt(alt); 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState altLeftEdge = nfa.grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt); 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState altStartState = (NFAState)altLeftEdge.transition[0].target; 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext ctx = nfa.grammar.ll1Analyzer.getPredicates(altStartState); 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("sem ctx = "+ctx); 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( ctx == null ) { 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ctx = new SemanticContext.TruePredicate(); 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.addTransition(predDFATarget, new Label(ctx)); 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.Predicate synpred = 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getSynPredForAlt(decisionStartState, alt); 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( synpred == null ) { 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver synpred = new SemanticContext.TruePredicate(); 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.addTransition(predDFATarget, new PredicateLabel(synpred)); 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("dfa for preds=\n"+this); 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Label getLabelForSet(IntervalSet edgeSet) { 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label e = null; 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int atom = edgeSet.getSingleElement(); 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( atom != Label.INVALID ) { 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver e = new Label(atom); 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver e = new Label(edgeSet); 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return e; 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected SemanticContext.Predicate getSynPredForAlt(NFAState decisionStartState, 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt) 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int walkAlt = 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver decisionStartState.translateDisplayAltToWalkAlt(alt); 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState altLeftEdge = 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nfa.grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt); 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState altStartState = (NFAState)altLeftEdge.transition[0].target; 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("alt "+alt+" start state = "+altStartState.stateNumber); 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( altStartState.transition[0].isSemanticPredicate() ) { 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext ctx = altStartState.transition[0].label.getSemanticContext(); 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( ctx.isSyntacticPredicate() ) { 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.Predicate p = (SemanticContext.Predicate)ctx; 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( p.predicateAST.getType() == ANTLRParser.BACKTRACK_SEMPRED ) { 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("syn pred for alt "+walkAlt+" "+ 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ((SemanticContext.Predicate)altStartState.transition[0].label.getSemanticContext()).predicateAST); 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( ctx.isSyntacticPredicate() ) { 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nfa.grammar.synPredUsedInDFA(this, ctx); 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return (SemanticContext.Predicate)altStartState.transition[0].label.getSemanticContext(); 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 180