001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.codegen;
029:
030: import org.antlr.analysis.*;
031: import org.antlr.misc.Utils;
032: import org.antlr.stringtemplate.StringTemplate;
033: import org.antlr.stringtemplate.StringTemplateGroup;
034:
035: import java.util.List;
036:
037: public class ACyclicDFACodeGenerator {
038: protected CodeGenerator parentGenerator;
039:
040: public ACyclicDFACodeGenerator(CodeGenerator parent) {
041: this .parentGenerator = parent;
042: }
043:
044: public StringTemplate genFixedLookaheadDecision(
045: StringTemplateGroup templates, DFA dfa) {
046: return walkFixedDFAGeneratingStateMachine(templates, dfa,
047: dfa.startState, 1);
048: }
049:
050: protected StringTemplate walkFixedDFAGeneratingStateMachine(
051: StringTemplateGroup templates, DFA dfa, DFAState s, int k) {
052: if (s.isAcceptState()) {
053: StringTemplate dfaST = templates
054: .getInstanceOf("dfaAcceptState");
055: dfaST.setAttribute("alt", Utils.integer(s
056: .getUniquelyPredictedAlt()));
057: return dfaST;
058: }
059:
060: // the default templates for generating a state and its edges
061: // can be an if-then-else structure or a switch
062: String dfaStateName = "dfaState";
063: String dfaLoopbackStateName = "dfaLoopbackState";
064: String dfaOptionalBlockStateName = "dfaOptionalBlockState";
065: String dfaEdgeName = "dfaEdge";
066: if (parentGenerator.canGenerateSwitch(s)) {
067: dfaStateName = "dfaStateSwitch";
068: dfaLoopbackStateName = "dfaLoopbackStateSwitch";
069: dfaOptionalBlockStateName = "dfaOptionalBlockStateSwitch";
070: dfaEdgeName = "dfaEdgeSwitch";
071: }
072:
073: StringTemplate dfaST = templates.getInstanceOf(dfaStateName);
074: if (dfa.getNFADecisionStartState().decisionStateType == NFAState.LOOPBACK) {
075: dfaST = templates.getInstanceOf(dfaLoopbackStateName);
076: } else if (dfa.getNFADecisionStartState().decisionStateType == NFAState.OPTIONAL_BLOCK_START) {
077: dfaST = templates.getInstanceOf(dfaOptionalBlockStateName);
078: }
079: dfaST.setAttribute("k", Utils.integer(k));
080: dfaST.setAttribute("stateNumber", Utils.integer(s.stateNumber));
081: dfaST.setAttribute("semPredState", Boolean.valueOf(s
082: .isResolvedWithPredicates()));
083: String description = dfa.getNFADecisionStartState()
084: .getDescription();
085: description = parentGenerator.target
086: .getTargetStringLiteralFromString(description);
087: //System.out.println("DFA: "+description+" associated with AST "+decisionASTNode);
088: if (description != null) {
089: dfaST.setAttribute("description", description);
090: }
091: int EOTPredicts = NFA.INVALID_ALT_NUMBER;
092: DFAState EOTTarget = null;
093: //System.out.println("DFA state "+s.stateNumber);
094: for (int i = 0; i < s.getNumberOfTransitions(); i++) {
095: Transition edge = (Transition) s.transition(i);
096: //System.out.println("edge label "+edge.label.toString());
097: if (edge.label.getAtom() == Label.EOT) {
098: // don't generate a real edge for EOT; track alt EOT predicts
099: // generate that prediction in the else clause as default case
100: EOTTarget = (DFAState) edge.target;
101: EOTPredicts = EOTTarget.getUniquelyPredictedAlt();
102: /*
103: System.out.println("DFA s"+s.stateNumber+" EOT goes to s"+
104: edge.target.stateNumber+" predicates alt "+
105: EOTPredicts);
106: */
107: continue;
108: }
109: StringTemplate edgeST = templates
110: .getInstanceOf(dfaEdgeName);
111: // If the template wants all the label values delineated, do that
112: if (edgeST.getFormalArgument("labels") != null) {
113: List labels = edge.label.getSet().toList();
114: for (int j = 0; j < labels.size(); j++) {
115: Integer vI = (Integer) labels.get(j);
116: String label = parentGenerator
117: .getTokenTypeAsTargetLabel(vI.intValue());
118: labels.set(j, label); // rewrite List element to be name
119: }
120: edgeST.setAttribute("labels", labels);
121: } else { // else create an expression to evaluate (the general case)
122: edgeST.setAttribute("labelExpr", parentGenerator
123: .genLabelExpr(templates, edge, k));
124: }
125:
126: // stick in any gated predicates for any edge if not already a pred
127: if (!edge.label.isSemanticPredicate()) {
128: DFAState target = (DFAState) edge.target;
129: SemanticContext preds = target
130: .getGatedPredicatesInNFAConfigurations();
131: if (preds != null) {
132: //System.out.println("preds="+target.getGatedPredicatesInNFAConfigurations());
133: StringTemplate predST = preds.genExpr(
134: parentGenerator, parentGenerator
135: .getTemplates(), dfa);
136: edgeST
137: .setAttribute("predicates", predST
138: .toString());
139: }
140: }
141:
142: StringTemplate targetST = walkFixedDFAGeneratingStateMachine(
143: templates, dfa, (DFAState) edge.target, k + 1);
144: edgeST.setAttribute("targetState", targetST);
145: dfaST.setAttribute("edges", edgeST);
146: /*
147: System.out.println("back to DFA "+
148: dfa.decisionNumber+"."+s.stateNumber);
149: */
150: }
151:
152: // HANDLE EOT EDGE
153: if (EOTPredicts != NFA.INVALID_ALT_NUMBER) {
154: // EOT unique predicts an alt
155: dfaST.setAttribute("eotPredictsAlt", Utils
156: .integer(EOTPredicts));
157: } else if (EOTTarget != null
158: && EOTTarget.getNumberOfTransitions() > 0) {
159: // EOT state has transitions so must split on predicates.
160: // Generate predicate else-if clauses and then generate
161: // NoViableAlt exception as else clause.
162: // Note: these predicates emanate from the EOT target state
163: // rather than the current DFAState s so the error message
164: // might be slightly misleading if you are looking at the
165: // state number. Predicates emanating from EOT targets are
166: // hoisted up to the state that has the EOT edge.
167: for (int i = 0; i < EOTTarget.getNumberOfTransitions(); i++) {
168: Transition predEdge = (Transition) EOTTarget
169: .transition(i);
170: StringTemplate edgeST = templates
171: .getInstanceOf(dfaEdgeName);
172: edgeST.setAttribute("labelExpr", parentGenerator
173: .genSemanticPredicateExpr(templates, predEdge));
174: // the target must be an accept state
175: StringTemplate targetST = walkFixedDFAGeneratingStateMachine(
176: templates, dfa, (DFAState) predEdge.target,
177: k + 1);
178: edgeST.setAttribute("targetState", targetST);
179: dfaST.setAttribute("edges", edgeST);
180: }
181: }
182: return dfaST;
183: }
184: }
|