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