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 */ 28 package org.antlr.tool; 29 30 import org.antlr.analysis.DFA; 31 import org.antlr.grammar.v3.ANTLRParser; 32 import org.antlr.misc.Utils; 33 import org.antlr.runtime.misc.Stats; 34 35 import java.lang.reflect.Field; 36 import java.util.*; 37 38 public class GrammarReport { 39 /** Because I may change the stats, I need to track version for later 40 * computations to be consistent. 41 */ 42 public static final String Version = "5"; 43 public static final String GRAMMAR_STATS_FILENAME = "grammar.stats"; 44 45 public static class ReportData { 46 String version; 47 String gname; 48 String gtype; 49 String language; 50 int numRules; 51 int numOuterProductions; 52 int numberOfDecisionsInRealRules; 53 int numberOfDecisions; 54 int numberOfCyclicDecisions; 55 int numberOfFixedKDecisions; 56 int numLL1; 57 int mink; 58 int maxk; 59 double avgk; 60 int numTokens; 61 long DFACreationWallClockTimeInMS; 62 int numberOfSemanticPredicates; 63 int numberOfManualLookaheadOptions; // TODO: verify 64 int numNonLLStarDecisions; 65 int numNondeterministicDecisions; 66 int numNondeterministicDecisionNumbersResolvedWithPredicates; 67 int errors; 68 int warnings; 69 int infos; 70 //int num_synpreds; 71 int blocksWithSynPreds; 72 int decisionsWhoseDFAsUsesSynPreds; 73 int blocksWithSemPreds; 74 int decisionsWhoseDFAsUsesSemPreds; 75 String output; 76 String grammarLevelk; 77 String grammarLevelBacktrack; 78 } 79 80 public static final String newline = System.getProperty("line.separator"); 81 82 public Grammar grammar; 83 GrammarReport(Grammar grammar)84 public GrammarReport(Grammar grammar) { 85 this.grammar = grammar; 86 } 87 getReportData(Grammar g)88 public static ReportData getReportData(Grammar g) { 89 ReportData data = new ReportData(); 90 data.version = Version; 91 data.gname = g.name; 92 93 data.gtype = g.getGrammarTypeString(); 94 95 data.language = (String) g.getOption("language"); 96 data.output = (String) g.getOption("output"); 97 if ( data.output==null ) { 98 data.output = "none"; 99 } 100 101 String k = (String) g.getOption("k"); 102 if ( k==null ) { 103 k = "none"; 104 } 105 data.grammarLevelk = k; 106 107 String backtrack = (String) g.getOption("backtrack"); 108 if ( backtrack==null ) { 109 backtrack = "false"; 110 } 111 data.grammarLevelBacktrack = backtrack; 112 113 int totalNonSynPredProductions = 0; 114 int totalNonSynPredRules = 0; 115 Collection rules = g.getRules(); 116 for (Iterator it = rules.iterator(); it.hasNext();) { 117 Rule r = (Rule) it.next(); 118 if ( !r.name.toUpperCase() 119 .startsWith(Grammar.SYNPRED_RULE_PREFIX.toUpperCase()) ) 120 { 121 totalNonSynPredProductions += r.numberOfAlts; 122 totalNonSynPredRules++; 123 } 124 } 125 126 data.numRules = totalNonSynPredRules; 127 data.numOuterProductions = totalNonSynPredProductions; 128 129 int numACyclicDecisions = 130 g.getNumberOfDecisions()- g.getNumberOfCyclicDecisions(); 131 List<Integer> depths = new ArrayList<Integer>(); 132 int[] acyclicDFAStates = new int[numACyclicDecisions]; 133 int[] cyclicDFAStates = new int[g.getNumberOfCyclicDecisions()]; 134 int acyclicIndex = 0; 135 int cyclicIndex = 0; 136 int numLL1 = 0; 137 int blocksWithSynPreds = 0; 138 int dfaWithSynPred = 0; 139 int numDecisions = 0; 140 int numCyclicDecisions = 0; 141 for (int i=1; i<= g.getNumberOfDecisions(); i++) { 142 Grammar.Decision d = g.getDecision(i); 143 if( d.dfa==null ) { 144 //System.out.println("dec "+d.decision+" has no AST"); 145 continue; 146 } 147 Rule r = d.dfa.decisionNFAStartState.enclosingRule; 148 if ( r.name.toUpperCase() 149 .startsWith(Grammar.SYNPRED_RULE_PREFIX.toUpperCase()) ) 150 { 151 //System.out.println("dec "+d.decision+" is a synpred"); 152 continue; 153 } 154 155 numDecisions++; 156 if ( blockHasSynPred(d.blockAST) ) blocksWithSynPreds++; 157 //if ( g.decisionsWhoseDFAsUsesSynPreds.contains(d.dfa) ) dfaWithSynPred++; 158 if ( d.dfa.hasSynPred() ) dfaWithSynPred++; 159 160 // NFAState decisionStartState = grammar.getDecisionNFAStartState(d.decision); 161 // int nalts = grammar.getNumberOfAltsForDecisionNFA(decisionStartState); 162 // for (int alt = 1; alt <= nalts; alt++) { 163 // int walkAlt = 164 // decisionStartState.translateDisplayAltToWalkAlt(alt); 165 // NFAState altLeftEdge = grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt); 166 // } 167 // int nalts = grammar.getNumberOfAltsForDecisionNFA(d.dfa.decisionNFAStartState); 168 // for (int a=1; a<nalts; a++) { 169 // NFAState altStart = 170 // grammar.getNFAStateForAltOfDecision(d.dfa.decisionNFAStartState, a); 171 // } 172 if ( !d.dfa.isCyclic() ) { 173 if ( d.dfa.isClassicDFA() ) { 174 int maxk = d.dfa.getMaxLookaheadDepth(); 175 //System.out.println("decision "+d.dfa.decisionNumber+" k="+maxk); 176 if ( maxk==1 ) numLL1++; 177 depths.add( maxk ); 178 } 179 else { 180 acyclicDFAStates[acyclicIndex] = d.dfa.getNumberOfStates(); 181 acyclicIndex++; 182 } 183 } 184 else { 185 //System.out.println("CYCLIC decision "+d.dfa.decisionNumber); 186 numCyclicDecisions++; 187 cyclicDFAStates[cyclicIndex] = d.dfa.getNumberOfStates(); 188 cyclicIndex++; 189 } 190 } 191 192 data.numLL1 = numLL1; 193 data.numberOfFixedKDecisions = depths.size(); 194 data.mink = Stats.min(depths); 195 data.maxk = Stats.max(depths); 196 data.avgk = Stats.avg(depths); 197 198 data.numberOfDecisionsInRealRules = numDecisions; 199 data.numberOfDecisions = g.getNumberOfDecisions(); 200 data.numberOfCyclicDecisions = numCyclicDecisions; 201 202 // Map synpreds = grammar.getSyntacticPredicates(); 203 // int num_synpreds = synpreds!=null ? synpreds.size() : 0; 204 // data.num_synpreds = num_synpreds; 205 data.blocksWithSynPreds = blocksWithSynPreds; 206 data.decisionsWhoseDFAsUsesSynPreds = dfaWithSynPred; 207 208 // 209 // data. = Stats.stddev(depths); 210 // 211 // data. = Stats.min(acyclicDFAStates); 212 // 213 // data. = Stats.max(acyclicDFAStates); 214 // 215 // data. = Stats.avg(acyclicDFAStates); 216 // 217 // data. = Stats.stddev(acyclicDFAStates); 218 // 219 // data. = Stats.sum(acyclicDFAStates); 220 // 221 // data. = Stats.min(cyclicDFAStates); 222 // 223 // data. = Stats.max(cyclicDFAStates); 224 // 225 // data. = Stats.avg(cyclicDFAStates); 226 // 227 // data. = Stats.stddev(cyclicDFAStates); 228 // 229 // data. = Stats.sum(cyclicDFAStates); 230 231 data.numTokens = g.getTokenTypes().size(); 232 233 data.DFACreationWallClockTimeInMS = g.DFACreationWallClockTimeInMS; 234 235 // includes true ones and preds in synpreds I think; strip out. 236 data.numberOfSemanticPredicates = g.numberOfSemanticPredicates; 237 238 data.numberOfManualLookaheadOptions = g.numberOfManualLookaheadOptions; 239 240 data.numNonLLStarDecisions = g.numNonLLStar; 241 data.numNondeterministicDecisions = g.setOfNondeterministicDecisionNumbers.size(); 242 data.numNondeterministicDecisionNumbersResolvedWithPredicates = 243 g.setOfNondeterministicDecisionNumbersResolvedWithPredicates.size(); 244 245 data.errors = ErrorManager.getErrorState().errors; 246 data.warnings = ErrorManager.getErrorState().warnings; 247 data.infos = ErrorManager.getErrorState().infos; 248 249 data.blocksWithSemPreds = g.blocksWithSemPreds.size(); 250 251 data.decisionsWhoseDFAsUsesSemPreds = g.decisionsWhoseDFAsUsesSemPreds.size(); 252 253 return data; 254 } 255 256 /** Create a single-line stats report about this grammar suitable to 257 * send to the notify page at antlr.org 258 */ toNotifyString()259 public String toNotifyString() { 260 StringBuffer buf = new StringBuffer(); 261 ReportData data = getReportData(grammar); 262 Field[] fields = ReportData.class.getDeclaredFields(); 263 int i = 0; 264 for (Field f : fields) { 265 try { 266 Object v = f.get(data); 267 String s = v!=null ? v.toString() : "null"; 268 if (i>0) buf.append('\t'); 269 buf.append(s); 270 } 271 catch (Exception e) { 272 ErrorManager.internalError("Can't get data", e); 273 } 274 i++; 275 } 276 return buf.toString(); 277 } 278 getBacktrackingReport()279 public String getBacktrackingReport() { 280 StringBuffer buf = new StringBuffer(); 281 buf.append("Backtracking report:"); 282 buf.append(newline); 283 buf.append("Number of decisions that backtrack: "); 284 buf.append(grammar.decisionsWhoseDFAsUsesSynPreds.size()); 285 buf.append(newline); 286 buf.append(getDFALocations(grammar.decisionsWhoseDFAsUsesSynPreds)); 287 return buf.toString(); 288 } 289 getDFALocations(Set dfas)290 protected String getDFALocations(Set dfas) { 291 Set decisions = new HashSet(); 292 StringBuffer buf = new StringBuffer(); 293 Iterator it = dfas.iterator(); 294 while ( it.hasNext() ) { 295 DFA dfa = (DFA) it.next(); 296 // if we aborted a DFA and redid with k=1, the backtrackin 297 if ( decisions.contains(Utils.integer(dfa.decisionNumber)) ) { 298 continue; 299 } 300 decisions.add(Utils.integer(dfa.decisionNumber)); 301 buf.append("Rule "); 302 buf.append(dfa.decisionNFAStartState.enclosingRule.name); 303 buf.append(" decision "); 304 buf.append(dfa.decisionNumber); 305 buf.append(" location "); 306 GrammarAST decisionAST = 307 dfa.decisionNFAStartState.associatedASTNode; 308 buf.append(decisionAST.getLine()); 309 buf.append(":"); 310 buf.append(decisionAST.getCharPositionInLine()); 311 buf.append(newline); 312 } 313 return buf.toString(); 314 } 315 316 /** Given a stats line suitable for sending to the antlr.org site, 317 * return a human-readable version. Return null if there is a 318 * problem with the data. 319 */ toString()320 public String toString() { 321 return toString(toNotifyString()); 322 } 323 decodeReportData(String dataS)324 protected static ReportData decodeReportData(String dataS) { 325 ReportData data = new ReportData(); 326 StringTokenizer st = new StringTokenizer(dataS, "\t"); 327 Field[] fields = ReportData.class.getDeclaredFields(); 328 for (Field f : fields) { 329 String v = st.nextToken(); 330 try { 331 if ( f.getType() == String.class ) { 332 f.set(data, v); 333 } 334 else if ( f.getType() == double.class ) { 335 f.set(data, Double.valueOf(v)); 336 } 337 else { 338 f.set(data, Integer.valueOf(v)); 339 } 340 } 341 catch (Exception e) { 342 ErrorManager.internalError("Can't get data", e); 343 } 344 } 345 return data; 346 } 347 toString(String notifyDataLine)348 public static String toString(String notifyDataLine) { 349 ReportData data = decodeReportData(notifyDataLine); 350 if ( data ==null ) { 351 return null; 352 } 353 StringBuffer buf = new StringBuffer(); 354 buf.append("ANTLR Grammar Report; Stats Version "); 355 buf.append(data.version); 356 buf.append('\n'); 357 buf.append("Grammar: "); 358 buf.append(data.gname); 359 buf.append('\n'); 360 buf.append("Type: "); 361 buf.append(data.gtype); 362 buf.append('\n'); 363 buf.append("Target language: "); 364 buf.append(data.language); 365 buf.append('\n'); 366 buf.append("Output: "); 367 buf.append(data.output); 368 buf.append('\n'); 369 buf.append("Grammar option k: "); 370 buf.append(data.grammarLevelk); 371 buf.append('\n'); 372 buf.append("Grammar option backtrack: "); 373 buf.append(data.grammarLevelBacktrack); 374 buf.append('\n'); 375 buf.append("Rules: "); 376 buf.append(data.numRules); 377 buf.append('\n'); 378 buf.append("Outer productions: "); 379 buf.append(data.numOuterProductions); 380 buf.append('\n'); 381 buf.append("Decisions: "); 382 buf.append(data.numberOfDecisions); 383 buf.append('\n'); 384 buf.append("Decisions (ignoring decisions in synpreds): "); 385 buf.append(data.numberOfDecisionsInRealRules); 386 buf.append('\n'); 387 buf.append("Fixed k DFA decisions: "); 388 buf.append(data.numberOfFixedKDecisions); 389 buf.append('\n'); 390 buf.append("Cyclic DFA decisions: "); 391 buf.append(data.numberOfCyclicDecisions); 392 buf.append('\n'); 393 buf.append("LL(1) decisions: "); buf.append(data.numLL1); 394 buf.append('\n'); 395 buf.append("Min fixed k: "); buf.append(data.mink); 396 buf.append('\n'); 397 buf.append("Max fixed k: "); buf.append(data.maxk); 398 buf.append('\n'); 399 buf.append("Average fixed k: "); buf.append(data.avgk); 400 buf.append('\n'); 401 // buf.append("Standard deviation of fixed k: "); buf.append(fields[12]); 402 // buf.append('\n'); 403 // buf.append("Min acyclic DFA states: "); buf.append(fields[13]); 404 // buf.append('\n'); 405 // buf.append("Max acyclic DFA states: "); buf.append(fields[14]); 406 // buf.append('\n'); 407 // buf.append("Average acyclic DFA states: "); buf.append(fields[15]); 408 // buf.append('\n'); 409 // buf.append("Standard deviation of acyclic DFA states: "); buf.append(fields[16]); 410 // buf.append('\n'); 411 // buf.append("Total acyclic DFA states: "); buf.append(fields[17]); 412 // buf.append('\n'); 413 // buf.append("Min cyclic DFA states: "); buf.append(fields[18]); 414 // buf.append('\n'); 415 // buf.append("Max cyclic DFA states: "); buf.append(fields[19]); 416 // buf.append('\n'); 417 // buf.append("Average cyclic DFA states: "); buf.append(fields[20]); 418 // buf.append('\n'); 419 // buf.append("Standard deviation of cyclic DFA states: "); buf.append(fields[21]); 420 // buf.append('\n'); 421 // buf.append("Total cyclic DFA states: "); buf.append(fields[22]); 422 // buf.append('\n'); 423 buf.append("DFA creation time in ms: "); 424 buf.append(data.DFACreationWallClockTimeInMS); 425 buf.append('\n'); 426 427 // buf.append("Number of syntactic predicates available (including synpred rules): "); 428 // buf.append(data.num_synpreds); 429 // buf.append('\n'); 430 buf.append("Decisions with available syntactic predicates (ignoring synpred rules): "); 431 buf.append(data.blocksWithSynPreds); 432 buf.append('\n'); 433 buf.append("Decision DFAs using syntactic predicates (ignoring synpred rules): "); 434 buf.append(data.decisionsWhoseDFAsUsesSynPreds); 435 buf.append('\n'); 436 437 buf.append("Number of semantic predicates found: "); 438 buf.append(data.numberOfSemanticPredicates); 439 buf.append('\n'); 440 buf.append("Decisions with semantic predicates: "); 441 buf.append(data.blocksWithSemPreds); 442 buf.append('\n'); 443 buf.append("Decision DFAs using semantic predicates: "); 444 buf.append(data.decisionsWhoseDFAsUsesSemPreds); 445 buf.append('\n'); 446 447 buf.append("Number of (likely) non-LL(*) decisions: "); 448 buf.append(data.numNonLLStarDecisions); 449 buf.append('\n'); 450 buf.append("Number of nondeterministic decisions: "); 451 buf.append(data.numNondeterministicDecisions); 452 buf.append('\n'); 453 buf.append("Number of nondeterministic decisions resolved with predicates: "); 454 buf.append(data.numNondeterministicDecisionNumbersResolvedWithPredicates); 455 buf.append('\n'); 456 457 buf.append("Number of manual or forced fixed lookahead k=value options: "); 458 buf.append(data.numberOfManualLookaheadOptions); 459 buf.append('\n'); 460 461 buf.append("Vocabulary size: "); 462 buf.append(data.numTokens); 463 buf.append('\n'); 464 buf.append("Number of errors: "); 465 buf.append(data.errors); 466 buf.append('\n'); 467 buf.append("Number of warnings: "); 468 buf.append(data.warnings); 469 buf.append('\n'); 470 buf.append("Number of infos: "); 471 buf.append(data.infos); 472 buf.append('\n'); 473 return buf.toString(); 474 } 475 blockHasSynPred(GrammarAST blockAST)476 public static boolean blockHasSynPred(GrammarAST blockAST) { 477 GrammarAST c1 = blockAST.findFirstType(ANTLRParser.SYN_SEMPRED); 478 GrammarAST c2 = blockAST.findFirstType(ANTLRParser.BACKTRACK_SEMPRED); 479 if ( c1!=null || c2!=null ) return true; 480 // System.out.println(blockAST.enclosingRuleName+ 481 // " "+blockAST.getLine()+":"+blockAST.getColumn()+" no preds AST="+blockAST.toStringTree()); 482 return false; 483 } 484 485 } 486