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 */ 28 package org.antlr.codegen; 29 30 import org.antlr.analysis.*; 31 import org.antlr.misc.Utils; 32 import org.stringtemplate.v4.ST; 33 import org.stringtemplate.v4.STGroup; 34 35 import java.util.List; 36 37 public class ACyclicDFACodeGenerator { 38 protected CodeGenerator parentGenerator; 39 ACyclicDFACodeGenerator(CodeGenerator parent)40 public ACyclicDFACodeGenerator(CodeGenerator parent) { 41 this.parentGenerator = parent; 42 } 43 genFixedLookaheadDecision(STGroup templates, DFA dfa)44 public ST genFixedLookaheadDecision(STGroup templates, 45 DFA dfa) 46 { 47 return walkFixedDFAGeneratingStateMachine(templates, dfa, dfa.startState, 1); 48 } 49 walkFixedDFAGeneratingStateMachine( STGroup templates, DFA dfa, DFAState s, int k)50 protected ST walkFixedDFAGeneratingStateMachine( 51 STGroup templates, 52 DFA dfa, 53 DFAState s, 54 int k) 55 { 56 //System.out.println("walk "+s.stateNumber+" in dfa for decision "+dfa.decisionNumber); 57 if ( s.isAcceptState() ) { 58 ST dfaST = templates.getInstanceOf("dfaAcceptState"); 59 dfaST.add("alt", Utils.integer(s.getUniquelyPredictedAlt())); 60 return dfaST; 61 } 62 63 // the default templates for generating a state and its edges 64 // can be an if-then-else structure or a switch 65 String dfaStateName = "dfaState"; 66 String dfaLoopbackStateName = "dfaLoopbackState"; 67 String dfaOptionalBlockStateName = "dfaOptionalBlockState"; 68 String dfaEdgeName = "dfaEdge"; 69 if ( parentGenerator.canGenerateSwitch(s) ) { 70 dfaStateName = "dfaStateSwitch"; 71 dfaLoopbackStateName = "dfaLoopbackStateSwitch"; 72 dfaOptionalBlockStateName = "dfaOptionalBlockStateSwitch"; 73 dfaEdgeName = "dfaEdgeSwitch"; 74 } 75 76 ST dfaST = templates.getInstanceOf(dfaStateName); 77 if ( dfa.getNFADecisionStartState().decisionStateType==NFAState.LOOPBACK ) { 78 dfaST = templates.getInstanceOf(dfaLoopbackStateName); 79 } 80 else if ( dfa.getNFADecisionStartState().decisionStateType==NFAState.OPTIONAL_BLOCK_START ) { 81 dfaST = templates.getInstanceOf(dfaOptionalBlockStateName); 82 } 83 dfaST.add("k", Utils.integer(k)); 84 dfaST.add("stateNumber", Utils.integer(s.stateNumber)); 85 dfaST.add("semPredState", 86 Boolean.valueOf(s.isResolvedWithPredicates())); 87 /* 88 String description = dfa.getNFADecisionStartState().getDescription(); 89 description = parentGenerator.target.getTargetStringLiteralFromString(description); 90 //System.out.println("DFA: "+description+" associated with AST "+dfa.getNFADecisionStartState()); 91 if ( description!=null ) { 92 dfaST.add("description", description); 93 } 94 */ 95 int EOTPredicts = NFA.INVALID_ALT_NUMBER; 96 DFAState EOTTarget = null; 97 //System.out.println("DFA state "+s.stateNumber); 98 for (int i = 0; i < s.getNumberOfTransitions(); i++) { 99 Transition edge = (Transition) s.transition(i); 100 //System.out.println("edge "+s.stateNumber+"-"+edge.label.toString()+"->"+edge.target.stateNumber); 101 if ( edge.label.getAtom()==Label.EOT ) { 102 // don't generate a real edge for EOT; track alt EOT predicts 103 // generate that prediction in the else clause as default case 104 EOTTarget = (DFAState)edge.target; 105 EOTPredicts = EOTTarget.getUniquelyPredictedAlt(); 106 /* 107 System.out.println("DFA s"+s.stateNumber+" EOT goes to s"+ 108 edge.target.stateNumber+" predicates alt "+ 109 EOTPredicts); 110 */ 111 continue; 112 } 113 ST edgeST = templates.getInstanceOf(dfaEdgeName); 114 // If the template wants all the label values delineated, do that 115 if ( edgeST.impl.formalArguments.get("labels")!=null ) { 116 List labels = edge.label.getSet().toList(); 117 for (int j = 0; j < labels.size(); j++) { 118 Integer vI = (Integer) labels.get(j); 119 String label = 120 parentGenerator.getTokenTypeAsTargetLabel(vI.intValue()); 121 labels.set(j, label); // rewrite List element to be name 122 } 123 edgeST.add("labels", labels); 124 } 125 else { // else create an expression to evaluate (the general case) 126 edgeST.add("labelExpr", 127 parentGenerator.genLabelExpr(templates,edge,k)); 128 } 129 130 // stick in any gated predicates for any edge if not already a pred 131 if ( !edge.label.isSemanticPredicate() ) { 132 DFAState target = (DFAState)edge.target; 133 SemanticContext preds = 134 target.getGatedPredicatesInNFAConfigurations(); 135 if ( preds!=null ) { 136 //System.out.println("preds="+target.getGatedPredicatesInNFAConfigurations()); 137 ST predST = preds.genExpr(parentGenerator, 138 parentGenerator.getTemplates(), 139 dfa); 140 edgeST.add("predicates", predST); 141 } 142 } 143 144 ST targetST = 145 walkFixedDFAGeneratingStateMachine(templates, 146 dfa, 147 (DFAState)edge.target, 148 k+1); 149 edgeST.add("targetState", targetST); 150 dfaST.add("edges", edgeST); 151 /* 152 System.out.println("back to DFA "+ 153 dfa.decisionNumber+"."+s.stateNumber); 154 */ 155 } 156 157 // HANDLE EOT EDGE 158 if ( EOTPredicts!=NFA.INVALID_ALT_NUMBER ) { 159 // EOT unique predicts an alt 160 dfaST.add("eotPredictsAlt", Utils.integer(EOTPredicts)); 161 } 162 else if ( EOTTarget!=null && EOTTarget.getNumberOfTransitions()>0 ) { 163 // EOT state has transitions so must split on predicates. 164 // Generate predicate else-if clauses and then generate 165 // NoViableAlt exception as else clause. 166 // Note: these predicates emanate from the EOT target state 167 // rather than the current DFAState s so the error message 168 // might be slightly misleading if you are looking at the 169 // state number. Predicates emanating from EOT targets are 170 // hoisted up to the state that has the EOT edge. 171 for (int i = 0; i < EOTTarget.getNumberOfTransitions(); i++) { 172 Transition predEdge = (Transition)EOTTarget.transition(i); 173 ST edgeST = templates.getInstanceOf(dfaEdgeName); 174 edgeST.add("labelExpr", 175 parentGenerator.genSemanticPredicateExpr(templates,predEdge)); 176 // the target must be an accept state 177 //System.out.println("EOT edge"); 178 ST targetST = 179 walkFixedDFAGeneratingStateMachine(templates, 180 dfa, 181 (DFAState)predEdge.target, 182 k+1); 183 edgeST.add("targetState", targetST); 184 dfaST.add("edges", edgeST); 185 } 186 } 187 return dfaST; 188 } 189 } 190 191