1 files changed, 190 insertions, 0 deletions
diff --git a/tool/src/main/java/org/antlr/codegen/ACyclicDFACodeGenerator.java b/tool/src/main/java/org/antlr/codegen/ACyclicDFACodeGenerator.java
new file mode 100644
index 0000000..6bc5fd3
--- /dev/null
+++ b/tool/src/main/java/org/antlr/codegen/ACyclicDFACodeGenerator.java
@@ -0,0 +1,190 @@
+/*
+ * [The "BSD license"]
+ *  Copyright (c) 2010 Terence Parr
+ *  All rights reserved.
+ *
+ *  Redistribution and use in source and binary forms, with or without
+ *  modification, are permitted provided that the following conditions
+ *  are met:
+ *  1. Redistributions of source code must retain the above copyright
+ *      notice, this list of conditions and the following disclaimer.
+ *  2. Redistributions in binary form must reproduce the above copyright
+ *      notice, this list of conditions and the following disclaimer in the
+ *      documentation and/or other materials provided with the distribution.
+ *  3. The name of the author may not be used to endorse or promote products
+ *      derived from this software without specific prior written permission.
+ *
+ *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.antlr.codegen;
+
+import org.antlr.analysis.*;
+import org.antlr.misc.Utils;
+import org.stringtemplate.v4.ST;
+import org.stringtemplate.v4.STGroup;
+
+import java.util.List;
+
+public class ACyclicDFACodeGenerator {
+	protected CodeGenerator parentGenerator;
+
+	public ACyclicDFACodeGenerator(CodeGenerator parent) {
+		this.parentGenerator = parent;
+	}
+
+	public ST genFixedLookaheadDecision(STGroup templates,
+													DFA dfa)
+	{
+		return walkFixedDFAGeneratingStateMachine(templates, dfa, dfa.startState, 1);
+	}
+
+	protected ST walkFixedDFAGeneratingStateMachine(
+			STGroup templates,
+			DFA dfa,
+			DFAState s,
+			int k)
+	{
+		//System.out.println("walk "+s.stateNumber+" in dfa for decision "+dfa.decisionNumber);
+		if ( s.isAcceptState() ) {
+			ST dfaST = templates.getInstanceOf("dfaAcceptState");
+			dfaST.add("alt", Utils.integer(s.getUniquelyPredictedAlt()));
+			return dfaST;
+		}
+
+		// the default templates for generating a state and its edges
+		// can be an if-then-else structure or a switch
+		String dfaStateName = "dfaState";
+		String dfaLoopbackStateName = "dfaLoopbackState";
+		String dfaOptionalBlockStateName = "dfaOptionalBlockState";
+		String dfaEdgeName = "dfaEdge";
+		if ( parentGenerator.canGenerateSwitch(s) ) {
+			dfaStateName = "dfaStateSwitch";
+			dfaLoopbackStateName = "dfaLoopbackStateSwitch";
+			dfaOptionalBlockStateName = "dfaOptionalBlockStateSwitch";
+			dfaEdgeName = "dfaEdgeSwitch";
+		}
+
+		ST dfaST = templates.getInstanceOf(dfaStateName);
+		if ( dfa.getNFADecisionStartState().decisionStateType==NFAState.LOOPBACK ) {
+			dfaST = templates.getInstanceOf(dfaLoopbackStateName);
+		}
+		else if ( dfa.getNFADecisionStartState().decisionStateType==NFAState.OPTIONAL_BLOCK_START ) {
+			dfaST = templates.getInstanceOf(dfaOptionalBlockStateName);
+		}
+		dfaST.add("k", Utils.integer(k));
+		dfaST.add("stateNumber", Utils.integer(s.stateNumber));
+		dfaST.add("semPredState",
+						   Boolean.valueOf(s.isResolvedWithPredicates()));
+		/*
+		String description = dfa.getNFADecisionStartState().getDescription();
+		description = parentGenerator.target.getTargetStringLiteralFromString(description);
+		//System.out.println("DFA: "+description+" associated with AST "+dfa.getNFADecisionStartState());
+		if ( description!=null ) {
+			dfaST.add("description", description);
+		}
+		*/
+		int EOTPredicts = NFA.INVALID_ALT_NUMBER;
+		DFAState EOTTarget = null;
+		//System.out.println("DFA state "+s.stateNumber);
+		for (int i = 0; i < s.getNumberOfTransitions(); i++) {
+			Transition edge = (Transition) s.transition(i);
+			//System.out.println("edge "+s.stateNumber+"-"+edge.label.toString()+"->"+edge.target.stateNumber);
+			if ( edge.label.getAtom()==Label.EOT ) {
+				// don't generate a real edge for EOT; track alt EOT predicts
+				// generate that prediction in the else clause as default case
+				EOTTarget = (DFAState)edge.target;
+				EOTPredicts = EOTTarget.getUniquelyPredictedAlt();
+				/*
+				System.out.println("DFA s"+s.stateNumber+" EOT goes to s"+
+								   edge.target.stateNumber+" predicates alt "+
+								   EOTPredicts);
+				*/
+				continue;
+			}
+			ST edgeST = templates.getInstanceOf(dfaEdgeName);
+			// If the template wants all the label values delineated, do that
+			if ( edgeST.impl.formalArguments.get("labels")!=null ) {
+				List labels = edge.label.getSet().toList();
+				for (int j = 0; j < labels.size(); j++) {
+					Integer vI = (Integer) labels.get(j);
+					String label =
+						parentGenerator.getTokenTypeAsTargetLabel(vI.intValue());
+					labels.set(j, label); // rewrite List element to be name
+				}
+				edgeST.add("labels", labels);
+			}
+			else { // else create an expression to evaluate (the general case)
+				edgeST.add("labelExpr",
+									parentGenerator.genLabelExpr(templates,edge,k));
+			}
+
+			// stick in any gated predicates for any edge if not already a pred
+			if ( !edge.label.isSemanticPredicate() ) {
+				DFAState target = (DFAState)edge.target;
+				SemanticContext preds =
+					target.getGatedPredicatesInNFAConfigurations();
+				if ( preds!=null ) {
+					//System.out.println("preds="+target.getGatedPredicatesInNFAConfigurations());
+					ST predST = preds.genExpr(parentGenerator,
+														  parentGenerator.getTemplates(),
+														  dfa);
+					edgeST.add("predicates", predST);
+				}
+			}
+
+			ST targetST =
+				walkFixedDFAGeneratingStateMachine(templates,
+												   dfa,
+												   (DFAState)edge.target,
+												   k+1);
+			edgeST.add("targetState", targetST);
+			dfaST.add("edges", edgeST);
+			/*
+			System.out.println("back to DFA "+
+							   dfa.decisionNumber+"."+s.stateNumber);
+							   */
+		}
+
+		// HANDLE EOT EDGE
+		if ( EOTPredicts!=NFA.INVALID_ALT_NUMBER ) {
+			// EOT unique predicts an alt
+			dfaST.add("eotPredictsAlt", Utils.integer(EOTPredicts));
+		}
+		else if ( EOTTarget!=null && EOTTarget.getNumberOfTransitions()>0 ) {
+			// EOT state has transitions so must split on predicates.
+			// Generate predicate else-if clauses and then generate
+			// NoViableAlt exception as else clause.
+			// Note: these predicates emanate from the EOT target state
+			// rather than the current DFAState s so the error message
+			// might be slightly misleading if you are looking at the
+			// state number.  Predicates emanating from EOT targets are
+			// hoisted up to the state that has the EOT edge.
+			for (int i = 0; i < EOTTarget.getNumberOfTransitions(); i++) {
+				Transition predEdge = (Transition)EOTTarget.transition(i);
+				ST edgeST = templates.getInstanceOf(dfaEdgeName);
+				edgeST.add("labelExpr",
+									parentGenerator.genSemanticPredicateExpr(templates,predEdge));
+				// the target must be an accept state
+				//System.out.println("EOT edge");
+				ST targetST =
+					walkFixedDFAGeneratingStateMachine(templates,
+													   dfa,
+													   (DFAState)predEdge.target,
+													   k+1);
+				edgeST.add("targetState", targetST);
+				dfaST.add("edges", edgeST);
+			}
+		}
+		return dfaST;
+	}
+}
+