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