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.DFA;
031: import org.antlr.runtime.misc.Stats;
032: import org.antlr.misc.Utils;
033:
034: import java.util.*;
035:
036: public class GrammarReport {
037: /** Because I may change the stats, I need to track that for later
038: * computations to be consistent.
039: */
040: public static final String Version = "4";
041: public static final String GRAMMAR_STATS_FILENAME = "grammar.stats";
042: public static final int NUM_GRAMMAR_STATS = 41;
043:
044: public static final String newline = System
045: .getProperty("line.separator");
046:
047: public Grammar grammar;
048:
049: public GrammarReport(Grammar grammar) {
050: this .grammar = grammar;
051: }
052:
053: /** Create a single-line stats report about this grammar suitable to
054: * send to the notify page at antlr.org
055: */
056: public String toNotifyString() {
057: StringBuffer buf = new StringBuffer();
058: buf.append(Version);
059: buf.append('\t');
060: buf.append(grammar.name);
061: buf.append('\t');
062: buf.append(Grammar.grammarTypeToString[grammar.type]);
063: buf.append('\t');
064: buf.append(grammar.getOption("language"));
065: int totalNonSynPredProductions = 0;
066: int totalNonSynPredRules = 0;
067: Collection rules = grammar.getRules();
068: for (Iterator it = rules.iterator(); it.hasNext();) {
069: Rule r = (Rule) it.next();
070: if (!r.name.toUpperCase().startsWith(
071: Grammar.SYNPRED_RULE_PREFIX.toUpperCase())) {
072: totalNonSynPredProductions += r.numberOfAlts;
073: totalNonSynPredRules++;
074: }
075: }
076: buf.append('\t');
077: buf.append(totalNonSynPredRules);
078: buf.append('\t');
079: buf.append(totalNonSynPredProductions);
080: int numACyclicDecisions = grammar.getNumberOfDecisions()
081: - grammar.getNumberOfCyclicDecisions();
082: int[] depths = new int[numACyclicDecisions];
083: int[] acyclicDFAStates = new int[numACyclicDecisions];
084: int[] cyclicDFAStates = new int[grammar
085: .getNumberOfCyclicDecisions()];
086: int acyclicIndex = 0;
087: int cyclicIndex = 0;
088: int numLL1 = 0;
089: int numDec = 0;
090: for (int i = 1; i <= grammar.getNumberOfDecisions(); i++) {
091: Grammar.Decision d = grammar.getDecision(i);
092: if (d.dfa == null) {
093: continue;
094: }
095: numDec++;
096: if (!d.dfa.isCyclic()) {
097: int maxk = d.dfa.getMaxLookaheadDepth();
098: if (maxk == 1) {
099: numLL1++;
100: }
101: depths[acyclicIndex] = maxk;
102: acyclicDFAStates[acyclicIndex] = d.dfa
103: .getNumberOfStates();
104: acyclicIndex++;
105: } else {
106: cyclicDFAStates[cyclicIndex] = d.dfa
107: .getNumberOfStates();
108: cyclicIndex++;
109: }
110: }
111: buf.append('\t');
112: buf.append(numDec);
113: buf.append('\t');
114: buf.append(grammar.getNumberOfCyclicDecisions());
115: buf.append('\t');
116: buf.append(numLL1);
117: buf.append('\t');
118: buf.append(Stats.min(depths));
119: buf.append('\t');
120: buf.append(Stats.max(depths));
121: buf.append('\t');
122: buf.append(Stats.avg(depths));
123: buf.append('\t');
124: buf.append(Stats.stddev(depths));
125: buf.append('\t');
126: buf.append(Stats.min(acyclicDFAStates));
127: buf.append('\t');
128: buf.append(Stats.max(acyclicDFAStates));
129: buf.append('\t');
130: buf.append(Stats.avg(acyclicDFAStates));
131: buf.append('\t');
132: buf.append(Stats.stddev(acyclicDFAStates));
133: buf.append('\t');
134: buf.append(Stats.sum(acyclicDFAStates));
135: buf.append('\t');
136: buf.append(Stats.min(cyclicDFAStates));
137: buf.append('\t');
138: buf.append(Stats.max(cyclicDFAStates));
139: buf.append('\t');
140: buf.append(Stats.avg(cyclicDFAStates));
141: buf.append('\t');
142: buf.append(Stats.stddev(cyclicDFAStates));
143: buf.append('\t');
144: buf.append(Stats.sum(cyclicDFAStates));
145: buf.append('\t');
146: buf.append(grammar.getTokenTypes().size());
147: buf.append('\t');
148: buf.append(grammar.DFACreationWallClockTimeInMS);
149: buf.append('\t');
150: buf.append(grammar.numberOfSemanticPredicates);
151: buf.append('\t');
152: buf.append(grammar.numberOfManualLookaheadOptions);
153: buf.append('\t');
154: buf.append(grammar.setOfNondeterministicDecisionNumbers.size());
155: buf.append('\t');
156: buf
157: .append(grammar.setOfNondeterministicDecisionNumbersResolvedWithPredicates
158: .size());
159: buf.append('\t');
160: buf.append(grammar.setOfDFAWhoseConversionTerminatedEarly
161: .size());
162: buf.append('\t');
163: buf.append(ErrorManager.getErrorState().errors);
164: buf.append('\t');
165: buf.append(ErrorManager.getErrorState().warnings);
166: buf.append('\t');
167: buf.append(ErrorManager.getErrorState().infos);
168: buf.append('\t');
169: Map synpreds = grammar.getSyntacticPredicates();
170: int num_synpreds = synpreds != null ? synpreds.size() : 0;
171: buf.append(num_synpreds);
172: buf.append('\t');
173: buf.append(grammar.blocksWithSynPreds.size());
174: buf.append('\t');
175: buf.append(grammar.decisionsWhoseDFAsUsesSynPreds.size());
176: buf.append('\t');
177: buf.append(grammar.blocksWithSemPreds.size());
178: buf.append('\t');
179: buf.append(grammar.decisionsWhoseDFAsUsesSemPreds.size());
180: buf.append('\t');
181: String output = (String) grammar.getOption("output");
182: if (output == null) {
183: output = "none";
184: }
185: buf.append(output);
186: buf.append('\t');
187: Object k = grammar.getOption("k");
188: if (k == null) {
189: k = "none";
190: }
191: buf.append(k);
192: buf.append('\t');
193: String backtrack = (String) grammar.getOption("backtrack");
194: if (backtrack == null) {
195: backtrack = "false";
196: }
197: buf.append(backtrack);
198: return buf.toString();
199: }
200:
201: public String getBacktrackingReport() {
202: StringBuffer buf = new StringBuffer();
203: buf.append("Backtracking report:");
204: buf.append(newline);
205: buf.append("Number of decisions that backtrack: ");
206: buf.append(grammar.decisionsWhoseDFAsUsesSynPreds.size());
207: buf.append(newline);
208: buf
209: .append(getDFALocations(grammar.decisionsWhoseDFAsUsesSynPreds));
210: return buf.toString();
211: }
212:
213: public String getEarlyTerminationReport() {
214: StringBuffer buf = new StringBuffer();
215: buf.append("NFA conversion early termination report:");
216: buf.append(newline);
217: buf.append("Number of NFA conversions that terminated early: ");
218: buf.append(grammar.setOfDFAWhoseConversionTerminatedEarly
219: .size());
220: buf.append(newline);
221: buf
222: .append(getDFALocations(grammar.setOfDFAWhoseConversionTerminatedEarly));
223: return buf.toString();
224: }
225:
226: protected String getDFALocations(Set dfas) {
227: Set decisions = new HashSet();
228: StringBuffer buf = new StringBuffer();
229: Iterator it = dfas.iterator();
230: while (it.hasNext()) {
231: DFA dfa = (DFA) it.next();
232: // if we aborted a DFA and redid with k=1, the backtrackin
233: if (decisions.contains(Utils.integer(dfa.decisionNumber))) {
234: continue;
235: }
236: decisions.add(Utils.integer(dfa.decisionNumber));
237: buf.append("Rule ");
238: buf.append(dfa.decisionNFAStartState.getEnclosingRule());
239: buf.append(" decision ");
240: buf.append(dfa.decisionNumber);
241: buf.append(" location ");
242: GrammarAST decisionAST = dfa.decisionNFAStartState
243: .getAssociatedASTNode();
244: buf.append(decisionAST.getLine());
245: buf.append(":");
246: buf.append(decisionAST.getColumn());
247: buf.append(newline);
248: }
249: return buf.toString();
250: }
251:
252: /** Given a stats line suitable for sending to the antlr.org site,
253: * return a human-readable version. Return null if there is a
254: * problem with the data.
255: */
256: public String toString() {
257: return toString(toNotifyString());
258: }
259:
260: protected static String[] decodeReportData(String data) {
261: String[] fields = new String[NUM_GRAMMAR_STATS];
262: StringTokenizer st = new StringTokenizer(data, "\t");
263: int i = 0;
264: while (st.hasMoreTokens()) {
265: fields[i] = st.nextToken();
266: i++;
267: }
268: if (i != NUM_GRAMMAR_STATS) {
269: return null;
270: }
271: return fields;
272: }
273:
274: public static String toString(String notifyDataLine) {
275: String[] fields = decodeReportData(notifyDataLine);
276: if (fields == null) {
277: return null;
278: }
279: StringBuffer buf = new StringBuffer();
280: buf.append("ANTLR Grammar Report; Stats Version ");
281: buf.append(fields[0]);
282: buf.append('\n');
283: buf.append("Grammar: ");
284: buf.append(fields[1]);
285: buf.append('\n');
286: buf.append("Type: ");
287: buf.append(fields[2]);
288: buf.append('\n');
289: buf.append("Target language: ");
290: buf.append(fields[3]);
291: buf.append('\n');
292: buf.append("Output: ");
293: buf.append(fields[38]);
294: buf.append('\n');
295: buf.append("Grammar option k: ");
296: buf.append(fields[39]);
297: buf.append('\n');
298: buf.append("Grammar option backtrack: ");
299: buf.append(fields[40]);
300: buf.append('\n');
301: buf.append("Rules: ");
302: buf.append(fields[4]);
303: buf.append('\n');
304: buf.append("Productions: ");
305: buf.append(fields[5]);
306: buf.append('\n');
307: buf.append("Decisions: ");
308: buf.append(fields[6]);
309: buf.append('\n');
310: buf.append("Cyclic DFA decisions: ");
311: buf.append(fields[7]);
312: buf.append('\n');
313: buf.append("LL(1) decisions: ");
314: buf.append(fields[8]);
315: buf.append('\n');
316: buf.append("Min fixed k: ");
317: buf.append(fields[9]);
318: buf.append('\n');
319: buf.append("Max fixed k: ");
320: buf.append(fields[10]);
321: buf.append('\n');
322: buf.append("Average fixed k: ");
323: buf.append(fields[11]);
324: buf.append('\n');
325: buf.append("Standard deviation of fixed k: ");
326: buf.append(fields[12]);
327: buf.append('\n');
328: buf.append("Min acyclic DFA states: ");
329: buf.append(fields[13]);
330: buf.append('\n');
331: buf.append("Max acyclic DFA states: ");
332: buf.append(fields[14]);
333: buf.append('\n');
334: buf.append("Average acyclic DFA states: ");
335: buf.append(fields[15]);
336: buf.append('\n');
337: buf.append("Standard deviation of acyclic DFA states: ");
338: buf.append(fields[16]);
339: buf.append('\n');
340: buf.append("Total acyclic DFA states: ");
341: buf.append(fields[17]);
342: buf.append('\n');
343: buf.append("Min cyclic DFA states: ");
344: buf.append(fields[18]);
345: buf.append('\n');
346: buf.append("Max cyclic DFA states: ");
347: buf.append(fields[19]);
348: buf.append('\n');
349: buf.append("Average cyclic DFA states: ");
350: buf.append(fields[20]);
351: buf.append('\n');
352: buf.append("Standard deviation of cyclic DFA states: ");
353: buf.append(fields[21]);
354: buf.append('\n');
355: buf.append("Total cyclic DFA states: ");
356: buf.append(fields[22]);
357: buf.append('\n');
358: buf.append("Vocabulary size: ");
359: buf.append(fields[23]);
360: buf.append('\n');
361: buf.append("DFA creation time in ms: ");
362: buf.append(fields[24]);
363: buf.append('\n');
364: buf.append("Number of semantic predicates found: ");
365: buf.append(fields[25]);
366: buf.append('\n');
367: buf
368: .append("Number of manual fixed lookahead k=value options: ");
369: buf.append(fields[26]);
370: buf.append('\n');
371: buf.append("Number of nondeterministic decisions: ");
372: buf.append(fields[27]);
373: buf.append('\n');
374: buf
375: .append("Number of nondeterministic decisions resolved with predicates: ");
376: buf.append(fields[28]);
377: buf.append('\n');
378: buf.append("Number of DFA conversions terminated early: ");
379: buf.append(fields[29]);
380: buf.append('\n');
381: buf.append("Number of errors: ");
382: buf.append(fields[30]);
383: buf.append('\n');
384: buf.append("Number of warnings: ");
385: buf.append(fields[31]);
386: buf.append('\n');
387: buf.append("Number of infos: ");
388: buf.append(fields[32]);
389: buf.append('\n');
390: buf.append("Number of syntactic predicates found: ");
391: buf.append(fields[33]);
392: buf.append('\n');
393: buf.append("Decisions with syntactic predicates: ");
394: buf.append(fields[34]);
395: buf.append('\n');
396: buf.append("Decision DFAs using syntactic predicates: ");
397: buf.append(fields[35]);
398: buf.append('\n');
399: buf.append("Decisions with semantic predicates: ");
400: buf.append(fields[36]);
401: buf.append('\n');
402: buf.append("Decision DFAs using semantic predicates: ");
403: buf.append(fields[37]);
404: buf.append('\n');
405: return buf.toString();
406: }
407:
408: }
|