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.tool;
029:
030: import org.antlr.analysis.*;
031: import org.antlr.misc.Utils;
032:
033: import java.util.*;
034:
035: /** An aspect of FA (finite automata) that knows how to dump them to serialized
036: * strings.
037: */
038: public class FASerializer {
039: /** To prevent infinite recursion when walking state machines, record
040: * which states we've visited. Make a new set every time you start
041: * walking in case you reuse this object. Multiple threads will trash
042: * this shared variable. Use a different FASerializer per thread.
043: */
044: protected Set markedStates;
045:
046: /** Each state we walk will get a new state number for serialization
047: * purposes. This is the variable that tracks state numbers.
048: */
049: protected int stateCounter = 0;
050:
051: /** Rather than add a new instance variable to NFA and DFA just for
052: * serializing machines, map old state numbers to new state numbers
053: * by a State object -> Integer new state number HashMap.
054: */
055: protected Map stateNumberTranslator;
056:
057: protected Grammar grammar;
058:
059: /** This aspect is associated with a grammar; used to get token names */
060: public FASerializer(Grammar grammar) {
061: this .grammar = grammar;
062: }
063:
064: public String serialize(State s) {
065: return serialize(s, true);
066: }
067:
068: /** Return a string representation of a state machine. Two identical
069: * NFAs or DFAs will have identical serialized representations. The
070: * state numbers inside the state are not used; instead, a new number
071: * is computed and because the serialization will walk the two
072: * machines using the same specific algorithm, then the state numbers
073: * will be identical. Accept states are distinguished from regular
074: * states.
075: */
076: public String serialize(State s, boolean renumber) {
077: markedStates = new HashSet();
078: stateCounter = 0;
079: if (renumber) {
080: stateNumberTranslator = new HashMap();
081: walkFANormalizingStateNumbers(s);
082: }
083: List lines = new ArrayList();
084: if (s.getNumberOfTransitions() > 0) {
085: walkSerializingFA(lines, s);
086: } else {
087: // special case: s0 is an accept
088: String s0 = getStateString(0, s);
089: lines.add(s0 + "\n");
090: }
091: StringBuffer buf = new StringBuffer(0);
092: // sort lines to normalize; makes states come out ordered
093: // and then ordered by edge labels then by target state number :)
094: Collections.sort(lines);
095: for (int i = 0; i < lines.size(); i++) {
096: String line = (String) lines.get(i);
097: buf.append(line);
098: }
099: return buf.toString();
100: }
101:
102: /** In stateNumberTranslator, get a map from State to new, normalized
103: * state number. Used by walkSerializingFA to make sure any two
104: * identical state machines will serialize the same way.
105: */
106: protected void walkFANormalizingStateNumbers(State s) {
107: if (s == null) {
108: ErrorManager.internalError("null state s");
109: return;
110: }
111: if (stateNumberTranslator.get(s) != null) {
112: return; // already did this state
113: }
114: // assign a new state number for this node if there isn't one
115: stateNumberTranslator.put(s, Utils.integer(stateCounter));
116: stateCounter++;
117:
118: // visit nodes pointed to by each transition;
119: for (int i = 0; i < s.getNumberOfTransitions(); i++) {
120: Transition edge = (Transition) s.transition(i);
121: walkFANormalizingStateNumbers(edge.target); // keep walkin'
122: // if this transition is a rule reference, the node "following" this state
123: // will not be found and appear to be not in graph. Must explicitly jump
124: // to it, but don't "draw" an edge.
125: if (edge instanceof RuleClosureTransition) {
126: walkFANormalizingStateNumbers(((RuleClosureTransition) edge)
127: .getFollowState());
128: }
129: }
130: }
131:
132: protected void walkSerializingFA(List lines, State s) {
133: if (markedStates.contains(s)) {
134: return; // already visited this node
135: }
136:
137: markedStates.add(s); // mark this node as completed.
138:
139: int normalizedStateNumber = s.stateNumber;
140: if (stateNumberTranslator != null) {
141: Integer normalizedStateNumberI = (Integer) stateNumberTranslator
142: .get(s);
143: normalizedStateNumber = normalizedStateNumberI.intValue();
144: }
145:
146: String stateStr = getStateString(normalizedStateNumber, s);
147:
148: // depth first walk each transition, printing its edge first
149: for (int i = 0; i < s.getNumberOfTransitions(); i++) {
150: Transition edge = (Transition) s.transition(i);
151: StringBuffer buf = new StringBuffer();
152: buf.append(stateStr);
153: if (edge.isEpsilon()) {
154: buf.append("->");
155: } else if (edge.isSemanticPredicate()) {
156: buf.append("-{" + edge.label.getSemanticContext()
157: + "}?->");
158: } else {
159: String predsStr = "";
160: if (edge.target instanceof DFAState) {
161: // look for gated predicates; don't add gated to simple sempred edges
162: SemanticContext preds = ((DFAState) edge.target)
163: .getGatedPredicatesInNFAConfigurations();
164: if (preds != null) {
165: predsStr = "&&{"
166: + preds.genExpr(
167: grammar.generator,
168: grammar.generator
169: .getTemplates(), null)
170: .toString() + "}?";
171: }
172: }
173: buf.append("-" + edge.label.toString(grammar)
174: + predsStr + "->");
175: }
176:
177: int normalizedTargetStateNumber = edge.target.stateNumber;
178: if (stateNumberTranslator != null) {
179: Integer normalizedTargetStateNumberI = (Integer) stateNumberTranslator
180: .get(edge.target);
181: normalizedTargetStateNumber = normalizedTargetStateNumberI
182: .intValue();
183: }
184: buf.append(getStateString(normalizedTargetStateNumber,
185: edge.target));
186: buf.append("\n");
187: lines.add(buf.toString());
188:
189: // walk this transition
190: walkSerializingFA(lines, edge.target);
191:
192: // if this transition is a rule reference, the node "following" this state
193: // will not be found and appear to be not in graph. Must explicitly jump
194: // to it, but don't "draw" an edge.
195: if (edge instanceof RuleClosureTransition) {
196: walkSerializingFA(lines, ((RuleClosureTransition) edge)
197: .getFollowState());
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 + "=>"
208: + ((DFAState) s).getUniquelyPredictedAlt();
209: } else {
210: stateStr = ":s" + n;
211: }
212: }
213: return stateStr;
214: }
215:
216: }
|