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.tool; 29 30import org.antlr.analysis.*; 31import org.antlr.misc.Utils; 32 33import java.util.*; 34 35/** An aspect of FA (finite automata) that knows how to dump them to serialized 36 * strings. 37 */ 38public class FASerializer { 39 /** To prevent infinite recursion when walking state machines, record 40 * which states we've visited. Make a new set every time you start 41 * walking in case you reuse this object. Multiple threads will trash 42 * this shared variable. Use a different FASerializer per thread. 43 */ 44 protected Set markedStates; 45 46 /** Each state we walk will get a new state number for serialization 47 * purposes. This is the variable that tracks state numbers. 48 */ 49 protected int stateCounter = 0; 50 51 /** Rather than add a new instance variable to NFA and DFA just for 52 * serializing machines, map old state numbers to new state numbers 53 * by a State object -> Integer new state number HashMap. 54 */ 55 protected Map stateNumberTranslator; 56 57 protected Grammar grammar; 58 59 /** This aspect is associated with a grammar; used to get token names */ 60 public FASerializer(Grammar grammar) { 61 this.grammar = grammar; 62 } 63 64 public String serialize(State s) { 65 if ( s==null ) { 66 return "<no automaton>"; 67 } 68 return serialize(s, true); 69 } 70 71 /** Return a string representation of a state machine. Two identical 72 * NFAs or DFAs will have identical serialized representations. The 73 * state numbers inside the state are not used; instead, a new number 74 * is computed and because the serialization will walk the two 75 * machines using the same specific algorithm, then the state numbers 76 * will be identical. Accept states are distinguished from regular 77 * states. 78 */ 79 public String serialize(State s, boolean renumber) { 80 markedStates = new HashSet(); 81 stateCounter = 0; 82 if ( renumber ) { 83 stateNumberTranslator = new HashMap(); 84 walkFANormalizingStateNumbers(s); 85 } 86 List lines = new ArrayList(); 87 if ( s.getNumberOfTransitions()>0 ) { 88 walkSerializingFA(lines, s); 89 } 90 else { 91 // special case: s0 is an accept 92 String s0 = getStateString(0, s); 93 lines.add(s0+"\n"); 94 } 95 StringBuffer buf = new StringBuffer(0); 96 // sort lines to normalize; makes states come out ordered 97 // and then ordered by edge labels then by target state number :) 98 Collections.sort(lines); 99 for (int i = 0; i < lines.size(); i++) { 100 String line = (String) lines.get(i); 101 buf.append(line); 102 } 103 return buf.toString(); 104 } 105 106 /** In stateNumberTranslator, get a map from State to new, normalized 107 * state number. Used by walkSerializingFA to make sure any two 108 * identical state machines will serialize the same way. 109 */ 110 protected void walkFANormalizingStateNumbers(State s) { 111 if ( s==null ) { 112 ErrorManager.internalError("null state s"); 113 return; 114 } 115 if ( stateNumberTranslator.get(s)!=null ) { 116 return; // already did this state 117 } 118 // assign a new state number for this node if there isn't one 119 stateNumberTranslator.put(s, Utils.integer(stateCounter)); 120 stateCounter++; 121 122 // visit nodes pointed to by each transition; 123 for (int i = 0; i < s.getNumberOfTransitions(); i++) { 124 Transition edge = (Transition) s.transition(i); 125 walkFANormalizingStateNumbers(edge.target); // keep walkin' 126 // if this transition is a rule reference, the node "following" this state 127 // will not be found and appear to be not in graph. Must explicitly jump 128 // to it, but don't "draw" an edge. 129 if ( edge instanceof RuleClosureTransition ) { 130 walkFANormalizingStateNumbers(((RuleClosureTransition) edge).followState); 131 } 132 } 133 } 134 135 protected void walkSerializingFA(List lines, State s) { 136 if ( markedStates.contains(s) ) { 137 return; // already visited this node 138 } 139 140 markedStates.add(s); // mark this node as completed. 141 142 int normalizedStateNumber = s.stateNumber; 143 if ( stateNumberTranslator!=null ) { 144 Integer normalizedStateNumberI = (Integer)stateNumberTranslator.get(s); 145 normalizedStateNumber = normalizedStateNumberI.intValue(); 146 } 147 148 String stateStr = getStateString(normalizedStateNumber, s); 149 150 // depth first walk each transition, printing its edge first 151 for (int i = 0; i < s.getNumberOfTransitions(); i++) { 152 Transition edge = (Transition) s.transition(i); 153 StringBuffer buf = new StringBuffer(); 154 buf.append(stateStr); 155 if ( edge.isAction() ) { 156 buf.append("-{}->"); 157 } 158 else if ( edge.isEpsilon() ) { 159 buf.append("->"); 160 } 161 else if ( edge.isSemanticPredicate() ) { 162 buf.append("-{"+edge.label.getSemanticContext()+"}?->"); 163 } 164 else { 165 String predsStr = ""; 166 if ( edge.target instanceof DFAState ) { 167 // look for gated predicates; don't add gated to simple sempred edges 168 SemanticContext preds = 169 ((DFAState)edge.target).getGatedPredicatesInNFAConfigurations(); 170 if ( preds!=null ) { 171 predsStr = "&&{"+ 172 preds.genExpr(grammar.generator, 173 grammar.generator.getTemplates(), null).render() 174 +"}?"; 175 } 176 } 177 buf.append("-"+edge.label.toString(grammar)+predsStr+"->"); 178 } 179 180 int normalizedTargetStateNumber = edge.target.stateNumber; 181 if ( stateNumberTranslator!=null ) { 182 Integer normalizedTargetStateNumberI = 183 (Integer)stateNumberTranslator.get(edge.target); 184 normalizedTargetStateNumber = normalizedTargetStateNumberI.intValue(); 185 } 186 buf.append(getStateString(normalizedTargetStateNumber, edge.target)); 187 buf.append("\n"); 188 lines.add(buf.toString()); 189 190 // walk this transition 191 walkSerializingFA(lines, edge.target); 192 193 // if this transition is a rule reference, the node "following" this state 194 // will not be found and appear to be not in graph. Must explicitly jump 195 // to it, but don't "draw" an edge. 196 if ( edge instanceof RuleClosureTransition ) { 197 walkSerializingFA(lines, ((RuleClosureTransition) edge).followState); 198 } 199 } 200 201 } 202 203 private String getStateString(int n, State s) { 204 String stateStr = ".s"+n; 205 if ( s.isAcceptState() ) { 206 if ( s instanceof DFAState ) { 207 stateStr = ":s"+n+"=>"+((DFAState)s).getUniquelyPredictedAlt(); 208 } 209 else { 210 stateStr = ":s"+n; 211 } 212 } 213 return stateStr; 214 } 215 216 217} 218