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.Tool;
031: import org.antlr.analysis.*;
032: import org.antlr.misc.Utils;
033: import org.antlr.stringtemplate.StringTemplate;
034: import org.antlr.stringtemplate.StringTemplateGroup;
035: import org.antlr.stringtemplate.language.AngleBracketTemplateLexer;
036:
037: import java.util.*;
038:
039: /** The DOT (part of graphviz) generation aspect. */
040: public class DOTGenerator {
041: public static final boolean STRIP_NONREDUCED_STATES = false;
042:
043: protected String arrowhead = "normal";
044: protected String rankdir = "LR";
045:
046: /** Library of output templates; use <attrname> format */
047: public static StringTemplateGroup stlib = new StringTemplateGroup(
048: "toollib", AngleBracketTemplateLexer.class);
049:
050: /** To prevent infinite recursion when walking state machines, record
051: * which states we've visited. Make a new set every time you start
052: * walking in case you reuse this object.
053: */
054: protected Set markedStates = null;
055:
056: protected Grammar grammar;
057:
058: /** This aspect is associated with a grammar */
059: public DOTGenerator(Grammar grammar) {
060: this .grammar = grammar;
061: }
062:
063: /** Return a String containing a DOT description that, when displayed,
064: * will show the incoming state machine visually. All nodes reachable
065: * from startState will be included.
066: */
067: public String getDOT(State startState) {
068: // The output DOT graph for visualization
069: StringTemplate dot = null;
070: markedStates = new HashSet();
071: if (startState instanceof DFAState) {
072: dot = stlib
073: .getInstanceOf("org/antlr/tool/templates/dot/dfa");
074: dot.setAttribute("startState", Utils
075: .integer(startState.stateNumber));
076: dot.setAttribute("useBox", Boolean
077: .valueOf(Tool.internalOption_ShowNFConfigsInDFA));
078: walkCreatingDFADOT(dot, (DFAState) startState);
079: } else {
080: dot = stlib
081: .getInstanceOf("org/antlr/tool/templates/dot/nfa");
082: dot.setAttribute("startState", Utils
083: .integer(startState.stateNumber));
084: walkRuleNFACreatingDOT(dot, startState);
085: }
086: dot.setAttribute("rankdir", rankdir);
087: return dot.toString();
088: }
089:
090: /** Return a String containing a DOT description that, when displayed,
091: * will show the incoming state machine visually. All nodes reachable
092: * from startState will be included.
093: public String getRuleNFADOT(State startState) {
094: // The output DOT graph for visualization
095: StringTemplate dot = stlib.getInstanceOf("org/antlr/tool/templates/dot/nfa");
096:
097: markedStates = new HashSet();
098: dot.setAttribute("startState",
099: Utils.integer(startState.stateNumber));
100: walkRuleNFACreatingDOT(dot, startState);
101: return dot.toString();
102: }
103: */
104:
105: /** Do a depth-first walk of the state machine graph and
106: * fill a DOT description template. Keep filling the
107: * states and edges attributes.
108: */
109: protected void walkCreatingDFADOT(StringTemplate dot, DFAState s) {
110: if (markedStates.contains(Utils.integer(s.stateNumber))) {
111: return; // already visited this node
112: }
113:
114: markedStates.add(Utils.integer(s.stateNumber)); // mark this node as completed.
115:
116: // first add this node
117: StringTemplate st;
118: if (s.isAcceptState()) {
119: st = stlib
120: .getInstanceOf("org/antlr/tool/templates/dot/stopstate");
121: } else {
122: st = stlib
123: .getInstanceOf("org/antlr/tool/templates/dot/state");
124: }
125: st.setAttribute("name", getStateLabel(s));
126: dot.setAttribute("states", st);
127:
128: // make a DOT edge for each transition
129: for (int i = 0; i < s.getNumberOfTransitions(); i++) {
130: Transition edge = (Transition) s.transition(i);
131: /*
132: System.out.println("dfa "+s.dfa.decisionNumber+
133: " edge from s"+s.stateNumber+" ["+i+"] of "+s.getNumberOfTransitions());
134: */
135: if (STRIP_NONREDUCED_STATES) {
136: if (edge.target instanceof DFAState
137: && ((DFAState) edge.target)
138: .getAcceptStateReachable() != DFA.REACHABLE_YES) {
139: continue; // don't generate nodes for terminal states
140: }
141: }
142: st = stlib
143: .getInstanceOf("org/antlr/tool/templates/dot/edge");
144: st.setAttribute("label", getEdgeLabel(edge));
145: st.setAttribute("src", getStateLabel(s));
146: st.setAttribute("target", getStateLabel(edge.target));
147: st.setAttribute("arrowhead", arrowhead);
148: dot.setAttribute("edges", st);
149: walkCreatingDFADOT(dot, (DFAState) edge.target); // keep walkin'
150: }
151: }
152:
153: /** Do a depth-first walk of the state machine graph and
154: * fill a DOT description template. Keep filling the
155: * states and edges attributes. We know this is an NFA
156: * for a rule so don't traverse edges to other rules and
157: * don't go past rule end state.
158: */
159: protected void walkRuleNFACreatingDOT(StringTemplate dot, State s) {
160: if (markedStates.contains(s)) {
161: return; // already visited this node
162: }
163:
164: markedStates.add(s); // mark this node as completed.
165:
166: // first add this node
167: StringTemplate stateST;
168: if (s.isAcceptState()) {
169: stateST = stlib
170: .getInstanceOf("org/antlr/tool/templates/dot/stopstate");
171: } else {
172: stateST = stlib
173: .getInstanceOf("org/antlr/tool/templates/dot/state");
174: }
175: stateST.setAttribute("name", getStateLabel(s));
176: dot.setAttribute("states", stateST);
177:
178: if (s.isAcceptState()) {
179: return; // don't go past end of rule node to the follow states
180: }
181:
182: // special case: if decision point, then line up the alt start states
183: // unless it's an end of block
184: if (((NFAState) s).isDecisionState()) {
185: GrammarAST n = ((NFAState) s).getAssociatedASTNode();
186: if (n != null && n.getType() != ANTLRParser.EOB) {
187: StringTemplate rankST = stlib
188: .getInstanceOf("org/antlr/tool/templates/dot/decision-rank");
189: NFAState alt = (NFAState) s;
190: while (alt != null) {
191: rankST.setAttribute("states", getStateLabel(alt));
192: if (alt.transition(1) != null) {
193: alt = (NFAState) alt.transition(1).target;
194: } else {
195: alt = null;
196: }
197: }
198: dot.setAttribute("decisionRanks", rankST);
199: }
200: }
201:
202: // make a DOT edge for each transition
203: StringTemplate edgeST = null;
204: for (int i = 0; i < s.getNumberOfTransitions(); i++) {
205: Transition edge = (Transition) s.transition(i);
206: if (edge instanceof RuleClosureTransition) {
207: RuleClosureTransition rr = ((RuleClosureTransition) edge);
208: // don't jump to other rules, but display edge to follow node
209: edgeST = stlib
210: .getInstanceOf("org/antlr/tool/templates/dot/edge");
211: edgeST.setAttribute("label", "<"
212: + grammar.getRuleName(rr.getRuleIndex()) + ">");
213: edgeST.setAttribute("src", getStateLabel(s));
214: edgeST.setAttribute("target", getStateLabel(rr
215: .getFollowState()));
216: edgeST.setAttribute("arrowhead", arrowhead);
217: dot.setAttribute("edges", edgeST);
218: walkRuleNFACreatingDOT(dot, rr.getFollowState());
219: continue;
220: }
221: if (edge.isEpsilon()) {
222: edgeST = stlib
223: .getInstanceOf("org/antlr/tool/templates/dot/epsilon-edge");
224: } else {
225: edgeST = stlib
226: .getInstanceOf("org/antlr/tool/templates/dot/edge");
227: }
228: edgeST.setAttribute("label", getEdgeLabel(edge));
229: edgeST.setAttribute("src", getStateLabel(s));
230: edgeST.setAttribute("target", getStateLabel(edge.target));
231: edgeST.setAttribute("arrowhead", arrowhead);
232: dot.setAttribute("edges", edgeST);
233: walkRuleNFACreatingDOT(dot, edge.target); // keep walkin'
234: }
235: }
236:
237: /*
238: public void writeDOTFilesForAllRuleNFAs() throws IOException {
239: Collection rules = grammar.getRules();
240: for (Iterator itr = rules.iterator(); itr.hasNext();) {
241: Grammar.Rule r = (Grammar.Rule) itr.next();
242: String ruleName = r.name;
243: writeDOTFile(
244: ruleName,
245: getRuleNFADOT(grammar.getRuleStartState(ruleName)));
246: }
247: }
248: */
249:
250: /*
251: public void writeDOTFilesForAllDecisionDFAs() throws IOException {
252: // for debugging, create a DOT file for each decision in
253: // a directory named for the grammar.
254: File grammarDir = new File(grammar.name+"_DFAs");
255: grammarDir.mkdirs();
256: List decisionList = grammar.getDecisionNFAStartStateList();
257: if ( decisionList==null ) {
258: return;
259: }
260: int i = 1;
261: Iterator iter = decisionList.iterator();
262: while (iter.hasNext()) {
263: NFAState decisionState = (NFAState)iter.next();
264: DFA dfa = decisionState.getDecisionASTNode().getLookaheadDFA();
265: if ( dfa!=null ) {
266: String dot = getDOT( dfa.startState );
267: writeDOTFile(grammarDir+"/dec-"+i, dot);
268: }
269: i++;
270: }
271: }
272: */
273:
274: /** Fix edge strings so they print out in DOT properly;
275: * generate any gated predicates on edge too.
276: */
277: protected String getEdgeLabel(Transition edge) {
278: String label = edge.label.toString(grammar);
279: label = Utils.replace(label, "\\", "\\\\");
280: label = Utils.replace(label, "\"", "\\\"");
281: if (label.equals(Label.EPSILON_STR)) {
282: label = "e";
283: }
284: State target = edge.target;
285: if (!edge.isSemanticPredicate() && target instanceof DFAState) {
286: // look for gated predicates; don't add gated to simple sempred edges
287: SemanticContext preds = ((DFAState) target)
288: .getGatedPredicatesInNFAConfigurations();
289: if (preds != null) {
290: String predsStr = "";
291: predsStr = "&&{"
292: + preds.genExpr(grammar.generator,
293: grammar.generator.getTemplates(), null)
294: .toString() + "}?";
295: label += predsStr;
296: }
297: }
298: return label;
299: }
300:
301: protected String getStateLabel(State s) {
302: if (s == null) {
303: return "null";
304: }
305: String stateLabel = String.valueOf(s.stateNumber);
306: if (s instanceof DFAState) {
307: StringBuffer buf = new StringBuffer(250);
308: buf.append('s');
309: buf.append(s.stateNumber);
310: if (Tool.internalOption_ShowNFConfigsInDFA) {
311: buf.append("\\n");
312: // separate alts
313: Set alts = ((DFAState) s).getAltSet();
314: List altList = new ArrayList();
315: altList.addAll(alts);
316: Collections.sort(altList);
317: Set configurations = ((DFAState) s)
318: .getNFAConfigurations();
319: for (int altIndex = 0; altIndex < altList.size(); altIndex++) {
320: Integer altI = (Integer) altList.get(altIndex);
321: int alt = altI.intValue();
322: if (altIndex > 0) {
323: buf.append("\\n");
324: }
325: buf.append("alt");
326: buf.append(alt);
327: buf.append(':');
328: // get a list of configs for just this alt
329: // it will help us print better later
330: List configsInAlt = new ArrayList();
331: for (Iterator it = configurations.iterator(); it
332: .hasNext();) {
333: NFAConfiguration c = (NFAConfiguration) it
334: .next();
335: if (c.alt != alt)
336: continue;
337: configsInAlt.add(c);
338: }
339: int n = 0;
340: for (int cIndex = 0; cIndex < configsInAlt.size(); cIndex++) {
341: NFAConfiguration c = (NFAConfiguration) configsInAlt
342: .get(cIndex);
343: n++;
344: buf.append(c.toString(false));
345: if ((cIndex + 1) < configsInAlt.size()) {
346: buf.append(", ");
347: }
348: if (n % 5 == 0
349: && (configsInAlt.size() - cIndex) > 3) {
350: buf.append("\\n");
351: }
352: }
353: }
354: }
355: stateLabel = buf.toString();
356: }
357: if ((s instanceof NFAState) && ((NFAState) s).isDecisionState()) {
358: stateLabel = stateLabel + ",d="
359: + ((NFAState) s).getDecisionNumber();
360: if (((NFAState) s).endOfBlockStateNumber != State.INVALID_STATE_NUMBER) {
361: stateLabel += ",eob="
362: + ((NFAState) s).endOfBlockStateNumber;
363: }
364: } else if ((s instanceof NFAState)
365: && ((NFAState) s).endOfBlockStateNumber != State.INVALID_STATE_NUMBER) {
366: NFAState n = ((NFAState) s);
367: stateLabel = stateLabel + ",eob=" + n.endOfBlockStateNumber;
368: } else if (s instanceof DFAState
369: && ((DFAState) s).isAcceptState()) {
370: stateLabel = stateLabel + "=>"
371: + ((DFAState) s).getUniquelyPredictedAlt();
372: }
373: return '"' + stateLabel + '"';
374: }
375:
376: public String getArrowheadType() {
377: return arrowhead;
378: }
379:
380: public void setArrowheadType(String arrowhead) {
381: this .arrowhead = arrowhead;
382: }
383:
384: public String getRankdir() {
385: return rankdir;
386: }
387:
388: public void setRankdir(String rankdir) {
389: this.rankdir = rankdir;
390: }
391: }
|