1/* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28package org.antlr.analysis; 29 30import org.antlr.grammar.v3.ANTLRParser; 31import org.antlr.misc.IntervalSet; 32import org.antlr.misc.MultiMap; 33 34import java.util.Collections; 35import java.util.Iterator; 36import java.util.List; 37 38/** A special DFA that is exactly LL(1) or LL(1) with backtracking mode 39 * predicates to resolve edge set collisions. 40 */ 41public class LL1DFA extends DFA { 42 /** From list of lookahead sets (one per alt in decision), create 43 * an LL(1) DFA. One edge per set. 44 * 45 * s0-{alt1}->:o=>1 46 * | \ 47 * | -{alt2}->:o=>2 48 * | 49 * ... 50 */ 51 public LL1DFA(int decisionNumber, NFAState decisionStartState, LookaheadSet[] altLook) { 52 DFAState s0 = newState(); 53 startState = s0; 54 nfa = decisionStartState.nfa; 55 nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(decisionStartState); 56 this.decisionNumber = decisionNumber; 57 this.decisionNFAStartState = decisionStartState; 58 initAltRelatedInfo(); 59 unreachableAlts = null; 60 for (int alt=1; alt<altLook.length; alt++) { 61 DFAState acceptAltState = newState(); 62 acceptAltState.acceptState = true; 63 setAcceptState(alt, acceptAltState); 64 acceptAltState.k = 1; 65 acceptAltState.cachedUniquelyPredicatedAlt = alt; 66 Label e = getLabelForSet(altLook[alt].tokenTypeSet); 67 s0.addTransition(acceptAltState, e); 68 } 69 } 70 71 /** From a set of edgeset->list-of-alts mappings, create a DFA 72 * that uses syn preds for all |list-of-alts|>1. 73 */ 74 public LL1DFA(int decisionNumber, 75 NFAState decisionStartState, 76 MultiMap<IntervalSet, Integer> edgeMap) 77 { 78 DFAState s0 = newState(); 79 startState = s0; 80 nfa = decisionStartState.nfa; 81 nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(decisionStartState); 82 this.decisionNumber = decisionNumber; 83 this.decisionNFAStartState = decisionStartState; 84 initAltRelatedInfo(); 85 unreachableAlts = null; 86 for (Iterator it = edgeMap.keySet().iterator(); it.hasNext();) { 87 IntervalSet edge = (IntervalSet)it.next(); 88 List<Integer> alts = edgeMap.get(edge); 89 Collections.sort(alts); // make sure alts are attempted in order 90 //System.out.println(edge+" -> "+alts); 91 DFAState s = newState(); 92 s.k = 1; 93 Label e = getLabelForSet(edge); 94 s0.addTransition(s, e); 95 if ( alts.size()==1 ) { 96 s.acceptState = true; 97 int alt = alts.get(0); 98 setAcceptState(alt, s); 99 s.cachedUniquelyPredicatedAlt = alt; 100 } 101 else { 102 // resolve with syntactic predicates. Add edges from 103 // state s that test predicates. 104 s.resolvedWithPredicates = true; 105 for (int i = 0; i < alts.size(); i++) { 106 int alt = (int)alts.get(i); 107 s.cachedUniquelyPredicatedAlt = NFA.INVALID_ALT_NUMBER; 108 DFAState predDFATarget = getAcceptState(alt); 109 if ( predDFATarget==null ) { 110 predDFATarget = newState(); // create if not there. 111 predDFATarget.acceptState = true; 112 predDFATarget.cachedUniquelyPredicatedAlt = alt; 113 setAcceptState(alt, predDFATarget); 114 } 115 // add a transition to pred target from d 116 /* 117 int walkAlt = 118 decisionStartState.translateDisplayAltToWalkAlt(alt); 119 NFAState altLeftEdge = nfa.grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt); 120 NFAState altStartState = (NFAState)altLeftEdge.transition[0].target; 121 SemanticContext ctx = nfa.grammar.ll1Analyzer.getPredicates(altStartState); 122 System.out.println("sem ctx = "+ctx); 123 if ( ctx == null ) { 124 ctx = new SemanticContext.TruePredicate(); 125 } 126 s.addTransition(predDFATarget, new Label(ctx)); 127 */ 128 SemanticContext.Predicate synpred = 129 getSynPredForAlt(decisionStartState, alt); 130 if ( synpred == null ) { 131 synpred = new SemanticContext.TruePredicate(); 132 } 133 s.addTransition(predDFATarget, new PredicateLabel(synpred)); 134 } 135 } 136 } 137 //System.out.println("dfa for preds=\n"+this); 138 } 139 140 protected Label getLabelForSet(IntervalSet edgeSet) { 141 Label e = null; 142 int atom = edgeSet.getSingleElement(); 143 if ( atom != Label.INVALID ) { 144 e = new Label(atom); 145 } 146 else { 147 e = new Label(edgeSet); 148 } 149 return e; 150 } 151 152 protected SemanticContext.Predicate getSynPredForAlt(NFAState decisionStartState, 153 int alt) 154 { 155 int walkAlt = 156 decisionStartState.translateDisplayAltToWalkAlt(alt); 157 NFAState altLeftEdge = 158 nfa.grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt); 159 NFAState altStartState = (NFAState)altLeftEdge.transition[0].target; 160 //System.out.println("alt "+alt+" start state = "+altStartState.stateNumber); 161 if ( altStartState.transition[0].isSemanticPredicate() ) { 162 SemanticContext ctx = altStartState.transition[0].label.getSemanticContext(); 163 if ( ctx.isSyntacticPredicate() ) { 164 SemanticContext.Predicate p = (SemanticContext.Predicate)ctx; 165 if ( p.predicateAST.getType() == ANTLRParser.BACKTRACK_SEMPRED ) { 166 /* 167 System.out.println("syn pred for alt "+walkAlt+" "+ 168 ((SemanticContext.Predicate)altStartState.transition[0].label.getSemanticContext()).predicateAST); 169 */ 170 if ( ctx.isSyntacticPredicate() ) { 171 nfa.grammar.synPredUsedInDFA(this, ctx); 172 } 173 return (SemanticContext.Predicate)altStartState.transition[0].label.getSemanticContext(); 174 } 175 } 176 } 177 return null; 178 } 179} 180