| /* |
| * [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.tool; |
| |
| import org.antlr.analysis.*; |
| import org.antlr.misc.Utils; |
| |
| import java.util.*; |
| |
| /** An aspect of FA (finite automata) that knows how to dump them to serialized |
| * strings. |
| */ |
| public class FASerializer { |
| /** To prevent infinite recursion when walking state machines, record |
| * which states we've visited. Make a new set every time you start |
| * walking in case you reuse this object. Multiple threads will trash |
| * this shared variable. Use a different FASerializer per thread. |
| */ |
| protected Set markedStates; |
| |
| /** Each state we walk will get a new state number for serialization |
| * purposes. This is the variable that tracks state numbers. |
| */ |
| protected int stateCounter = 0; |
| |
| /** Rather than add a new instance variable to NFA and DFA just for |
| * serializing machines, map old state numbers to new state numbers |
| * by a State object -> Integer new state number HashMap. |
| */ |
| protected Map stateNumberTranslator; |
| |
| protected Grammar grammar; |
| |
| /** This aspect is associated with a grammar; used to get token names */ |
| public FASerializer(Grammar grammar) { |
| this.grammar = grammar; |
| } |
| |
| public String serialize(State s) { |
| if ( s==null ) { |
| return "<no automaton>"; |
| } |
| return serialize(s, true); |
| } |
| |
| /** Return a string representation of a state machine. Two identical |
| * NFAs or DFAs will have identical serialized representations. The |
| * state numbers inside the state are not used; instead, a new number |
| * is computed and because the serialization will walk the two |
| * machines using the same specific algorithm, then the state numbers |
| * will be identical. Accept states are distinguished from regular |
| * states. |
| */ |
| public String serialize(State s, boolean renumber) { |
| markedStates = new HashSet(); |
| stateCounter = 0; |
| if ( renumber ) { |
| stateNumberTranslator = new HashMap(); |
| walkFANormalizingStateNumbers(s); |
| } |
| List lines = new ArrayList(); |
| if ( s.getNumberOfTransitions()>0 ) { |
| walkSerializingFA(lines, s); |
| } |
| else { |
| // special case: s0 is an accept |
| String s0 = getStateString(0, s); |
| lines.add(s0+"\n"); |
| } |
| StringBuffer buf = new StringBuffer(0); |
| // sort lines to normalize; makes states come out ordered |
| // and then ordered by edge labels then by target state number :) |
| Collections.sort(lines); |
| for (int i = 0; i < lines.size(); i++) { |
| String line = (String) lines.get(i); |
| buf.append(line); |
| } |
| return buf.toString(); |
| } |
| |
| /** In stateNumberTranslator, get a map from State to new, normalized |
| * state number. Used by walkSerializingFA to make sure any two |
| * identical state machines will serialize the same way. |
| */ |
| protected void walkFANormalizingStateNumbers(State s) { |
| if ( s==null ) { |
| ErrorManager.internalError("null state s"); |
| return; |
| } |
| if ( stateNumberTranslator.get(s)!=null ) { |
| return; // already did this state |
| } |
| // assign a new state number for this node if there isn't one |
| stateNumberTranslator.put(s, Utils.integer(stateCounter)); |
| stateCounter++; |
| |
| // visit nodes pointed to by each transition; |
| for (int i = 0; i < s.getNumberOfTransitions(); i++) { |
| Transition edge = (Transition) s.transition(i); |
| walkFANormalizingStateNumbers(edge.target); // keep walkin' |
| // if this transition is a rule reference, the node "following" this state |
| // will not be found and appear to be not in graph. Must explicitly jump |
| // to it, but don't "draw" an edge. |
| if ( edge instanceof RuleClosureTransition ) { |
| walkFANormalizingStateNumbers(((RuleClosureTransition) edge).followState); |
| } |
| } |
| } |
| |
| protected void walkSerializingFA(List lines, State s) { |
| if ( markedStates.contains(s) ) { |
| return; // already visited this node |
| } |
| |
| markedStates.add(s); // mark this node as completed. |
| |
| int normalizedStateNumber = s.stateNumber; |
| if ( stateNumberTranslator!=null ) { |
| Integer normalizedStateNumberI = (Integer)stateNumberTranslator.get(s); |
| normalizedStateNumber = normalizedStateNumberI.intValue(); |
| } |
| |
| String stateStr = getStateString(normalizedStateNumber, s); |
| |
| // depth first walk each transition, printing its edge first |
| for (int i = 0; i < s.getNumberOfTransitions(); i++) { |
| Transition edge = (Transition) s.transition(i); |
| StringBuffer buf = new StringBuffer(); |
| buf.append(stateStr); |
| if ( edge.isAction() ) { |
| buf.append("-{}->"); |
| } |
| else if ( edge.isEpsilon() ) { |
| buf.append("->"); |
| } |
| else if ( edge.isSemanticPredicate() ) { |
| buf.append("-{"+edge.label.getSemanticContext()+"}?->"); |
| } |
| else { |
| String predsStr = ""; |
| if ( edge.target instanceof DFAState ) { |
| // look for gated predicates; don't add gated to simple sempred edges |
| SemanticContext preds = |
| ((DFAState)edge.target).getGatedPredicatesInNFAConfigurations(); |
| if ( preds!=null ) { |
| predsStr = "&&{"+ |
| preds.genExpr(grammar.generator, |
| grammar.generator.getTemplates(), null).render() |
| +"}?"; |
| } |
| } |
| buf.append("-"+edge.label.toString(grammar)+predsStr+"->"); |
| } |
| |
| int normalizedTargetStateNumber = edge.target.stateNumber; |
| if ( stateNumberTranslator!=null ) { |
| Integer normalizedTargetStateNumberI = |
| (Integer)stateNumberTranslator.get(edge.target); |
| normalizedTargetStateNumber = normalizedTargetStateNumberI.intValue(); |
| } |
| buf.append(getStateString(normalizedTargetStateNumber, edge.target)); |
| buf.append("\n"); |
| lines.add(buf.toString()); |
| |
| // walk this transition |
| walkSerializingFA(lines, edge.target); |
| |
| // if this transition is a rule reference, the node "following" this state |
| // will not be found and appear to be not in graph. Must explicitly jump |
| // to it, but don't "draw" an edge. |
| if ( edge instanceof RuleClosureTransition ) { |
| walkSerializingFA(lines, ((RuleClosureTransition) edge).followState); |
| } |
| } |
| |
| } |
| |
| private String getStateString(int n, State s) { |
| String stateStr = ".s"+n; |
| if ( s.isAcceptState() ) { |
| if ( s instanceof DFAState ) { |
| stateStr = ":s"+n+"=>"+((DFAState)s).getUniquelyPredictedAlt(); |
| } |
| else { |
| stateStr = ":s"+n; |
| } |
| } |
| return stateStr; |
| } |
| |
| |
| } |