| /* |
| * [The "BSD license"] |
| * Copyright (c) 2010 Terence Parr |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| package org.antlr.tool; |
| |
| import org.antlr.analysis.DFA; |
| import org.antlr.grammar.v3.ANTLRParser; |
| import org.antlr.misc.Utils; |
| import org.antlr.runtime.misc.Stats; |
| |
| import java.lang.reflect.Field; |
| import java.util.*; |
| |
| public class GrammarReport { |
| /** Because I may change the stats, I need to track version for later |
| * computations to be consistent. |
| */ |
| public static final String Version = "5"; |
| public static final String GRAMMAR_STATS_FILENAME = "grammar.stats"; |
| |
| public static class ReportData { |
| String version; |
| String gname; |
| String gtype; |
| String language; |
| int numRules; |
| int numOuterProductions; |
| int numberOfDecisionsInRealRules; |
| int numberOfDecisions; |
| int numberOfCyclicDecisions; |
| int numberOfFixedKDecisions; |
| int numLL1; |
| int mink; |
| int maxk; |
| double avgk; |
| int numTokens; |
| long DFACreationWallClockTimeInMS; |
| int numberOfSemanticPredicates; |
| int numberOfManualLookaheadOptions; // TODO: verify |
| int numNonLLStarDecisions; |
| int numNondeterministicDecisions; |
| int numNondeterministicDecisionNumbersResolvedWithPredicates; |
| int errors; |
| int warnings; |
| int infos; |
| //int num_synpreds; |
| int blocksWithSynPreds; |
| int decisionsWhoseDFAsUsesSynPreds; |
| int blocksWithSemPreds; |
| int decisionsWhoseDFAsUsesSemPreds; |
| String output; |
| String grammarLevelk; |
| String grammarLevelBacktrack; |
| } |
| |
| public static final String newline = System.getProperty("line.separator"); |
| |
| public Grammar grammar; |
| |
| public GrammarReport(Grammar grammar) { |
| this.grammar = grammar; |
| } |
| |
| public static ReportData getReportData(Grammar g) { |
| ReportData data = new ReportData(); |
| data.version = Version; |
| data.gname = g.name; |
| |
| data.gtype = g.getGrammarTypeString(); |
| |
| data.language = (String) g.getOption("language"); |
| data.output = (String) g.getOption("output"); |
| if ( data.output==null ) { |
| data.output = "none"; |
| } |
| |
| String k = (String) g.getOption("k"); |
| if ( k==null ) { |
| k = "none"; |
| } |
| data.grammarLevelk = k; |
| |
| String backtrack = (String) g.getOption("backtrack"); |
| if ( backtrack==null ) { |
| backtrack = "false"; |
| } |
| data.grammarLevelBacktrack = backtrack; |
| |
| int totalNonSynPredProductions = 0; |
| int totalNonSynPredRules = 0; |
| Collection rules = g.getRules(); |
| for (Iterator it = rules.iterator(); it.hasNext();) { |
| Rule r = (Rule) it.next(); |
| if ( !r.name.toUpperCase() |
| .startsWith(Grammar.SYNPRED_RULE_PREFIX.toUpperCase()) ) |
| { |
| totalNonSynPredProductions += r.numberOfAlts; |
| totalNonSynPredRules++; |
| } |
| } |
| |
| data.numRules = totalNonSynPredRules; |
| data.numOuterProductions = totalNonSynPredProductions; |
| |
| int numACyclicDecisions = |
| g.getNumberOfDecisions()- g.getNumberOfCyclicDecisions(); |
| List<Integer> depths = new ArrayList<Integer>(); |
| int[] acyclicDFAStates = new int[numACyclicDecisions]; |
| int[] cyclicDFAStates = new int[g.getNumberOfCyclicDecisions()]; |
| int acyclicIndex = 0; |
| int cyclicIndex = 0; |
| int numLL1 = 0; |
| int blocksWithSynPreds = 0; |
| int dfaWithSynPred = 0; |
| int numDecisions = 0; |
| int numCyclicDecisions = 0; |
| for (int i=1; i<= g.getNumberOfDecisions(); i++) { |
| Grammar.Decision d = g.getDecision(i); |
| if( d.dfa==null ) { |
| //System.out.println("dec "+d.decision+" has no AST"); |
| continue; |
| } |
| Rule r = d.dfa.decisionNFAStartState.enclosingRule; |
| if ( r.name.toUpperCase() |
| .startsWith(Grammar.SYNPRED_RULE_PREFIX.toUpperCase()) ) |
| { |
| //System.out.println("dec "+d.decision+" is a synpred"); |
| continue; |
| } |
| |
| numDecisions++; |
| if ( blockHasSynPred(d.blockAST) ) blocksWithSynPreds++; |
| //if ( g.decisionsWhoseDFAsUsesSynPreds.contains(d.dfa) ) dfaWithSynPred++; |
| if ( d.dfa.hasSynPred() ) dfaWithSynPred++; |
| |
| // NFAState decisionStartState = grammar.getDecisionNFAStartState(d.decision); |
| // int nalts = grammar.getNumberOfAltsForDecisionNFA(decisionStartState); |
| // for (int alt = 1; alt <= nalts; alt++) { |
| // int walkAlt = |
| // decisionStartState.translateDisplayAltToWalkAlt(alt); |
| // NFAState altLeftEdge = grammar.getNFAStateForAltOfDecision(decisionStartState, walkAlt); |
| // } |
| // int nalts = grammar.getNumberOfAltsForDecisionNFA(d.dfa.decisionNFAStartState); |
| // for (int a=1; a<nalts; a++) { |
| // NFAState altStart = |
| // grammar.getNFAStateForAltOfDecision(d.dfa.decisionNFAStartState, a); |
| // } |
| if ( !d.dfa.isCyclic() ) { |
| if ( d.dfa.isClassicDFA() ) { |
| int maxk = d.dfa.getMaxLookaheadDepth(); |
| //System.out.println("decision "+d.dfa.decisionNumber+" k="+maxk); |
| if ( maxk==1 ) numLL1++; |
| depths.add( maxk ); |
| } |
| else { |
| acyclicDFAStates[acyclicIndex] = d.dfa.getNumberOfStates(); |
| acyclicIndex++; |
| } |
| } |
| else { |
| //System.out.println("CYCLIC decision "+d.dfa.decisionNumber); |
| numCyclicDecisions++; |
| cyclicDFAStates[cyclicIndex] = d.dfa.getNumberOfStates(); |
| cyclicIndex++; |
| } |
| } |
| |
| data.numLL1 = numLL1; |
| data.numberOfFixedKDecisions = depths.size(); |
| data.mink = Stats.min(depths); |
| data.maxk = Stats.max(depths); |
| data.avgk = Stats.avg(depths); |
| |
| data.numberOfDecisionsInRealRules = numDecisions; |
| data.numberOfDecisions = g.getNumberOfDecisions(); |
| data.numberOfCyclicDecisions = numCyclicDecisions; |
| |
| // Map synpreds = grammar.getSyntacticPredicates(); |
| // int num_synpreds = synpreds!=null ? synpreds.size() : 0; |
| // data.num_synpreds = num_synpreds; |
| data.blocksWithSynPreds = blocksWithSynPreds; |
| data.decisionsWhoseDFAsUsesSynPreds = dfaWithSynPred; |
| |
| // |
| // data. = Stats.stddev(depths); |
| // |
| // data. = Stats.min(acyclicDFAStates); |
| // |
| // data. = Stats.max(acyclicDFAStates); |
| // |
| // data. = Stats.avg(acyclicDFAStates); |
| // |
| // data. = Stats.stddev(acyclicDFAStates); |
| // |
| // data. = Stats.sum(acyclicDFAStates); |
| // |
| // data. = Stats.min(cyclicDFAStates); |
| // |
| // data. = Stats.max(cyclicDFAStates); |
| // |
| // data. = Stats.avg(cyclicDFAStates); |
| // |
| // data. = Stats.stddev(cyclicDFAStates); |
| // |
| // data. = Stats.sum(cyclicDFAStates); |
| |
| data.numTokens = g.getTokenTypes().size(); |
| |
| data.DFACreationWallClockTimeInMS = g.DFACreationWallClockTimeInMS; |
| |
| // includes true ones and preds in synpreds I think; strip out. |
| data.numberOfSemanticPredicates = g.numberOfSemanticPredicates; |
| |
| data.numberOfManualLookaheadOptions = g.numberOfManualLookaheadOptions; |
| |
| data.numNonLLStarDecisions = g.numNonLLStar; |
| data.numNondeterministicDecisions = g.setOfNondeterministicDecisionNumbers.size(); |
| data.numNondeterministicDecisionNumbersResolvedWithPredicates = |
| g.setOfNondeterministicDecisionNumbersResolvedWithPredicates.size(); |
| |
| data.errors = ErrorManager.getErrorState().errors; |
| data.warnings = ErrorManager.getErrorState().warnings; |
| data.infos = ErrorManager.getErrorState().infos; |
| |
| data.blocksWithSemPreds = g.blocksWithSemPreds.size(); |
| |
| data.decisionsWhoseDFAsUsesSemPreds = g.decisionsWhoseDFAsUsesSemPreds.size(); |
| |
| return data; |
| } |
| |
| /** Create a single-line stats report about this grammar suitable to |
| * send to the notify page at antlr.org |
| */ |
| public String toNotifyString() { |
| StringBuffer buf = new StringBuffer(); |
| ReportData data = getReportData(grammar); |
| Field[] fields = ReportData.class.getDeclaredFields(); |
| int i = 0; |
| for (Field f : fields) { |
| try { |
| Object v = f.get(data); |
| String s = v!=null ? v.toString() : "null"; |
| if (i>0) buf.append('\t'); |
| buf.append(s); |
| } |
| catch (Exception e) { |
| ErrorManager.internalError("Can't get data", e); |
| } |
| i++; |
| } |
| return buf.toString(); |
| } |
| |
| public String getBacktrackingReport() { |
| StringBuffer buf = new StringBuffer(); |
| buf.append("Backtracking report:"); |
| buf.append(newline); |
| buf.append("Number of decisions that backtrack: "); |
| buf.append(grammar.decisionsWhoseDFAsUsesSynPreds.size()); |
| buf.append(newline); |
| buf.append(getDFALocations(grammar.decisionsWhoseDFAsUsesSynPreds)); |
| return buf.toString(); |
| } |
| |
| protected String getDFALocations(Set dfas) { |
| Set decisions = new HashSet(); |
| StringBuffer buf = new StringBuffer(); |
| Iterator it = dfas.iterator(); |
| while ( it.hasNext() ) { |
| DFA dfa = (DFA) it.next(); |
| // if we aborted a DFA and redid with k=1, the backtrackin |
| if ( decisions.contains(Utils.integer(dfa.decisionNumber)) ) { |
| continue; |
| } |
| decisions.add(Utils.integer(dfa.decisionNumber)); |
| buf.append("Rule "); |
| buf.append(dfa.decisionNFAStartState.enclosingRule.name); |
| buf.append(" decision "); |
| buf.append(dfa.decisionNumber); |
| buf.append(" location "); |
| GrammarAST decisionAST = |
| dfa.decisionNFAStartState.associatedASTNode; |
| buf.append(decisionAST.getLine()); |
| buf.append(":"); |
| buf.append(decisionAST.getCharPositionInLine()); |
| buf.append(newline); |
| } |
| return buf.toString(); |
| } |
| |
| /** Given a stats line suitable for sending to the antlr.org site, |
| * return a human-readable version. Return null if there is a |
| * problem with the data. |
| */ |
| public String toString() { |
| return toString(toNotifyString()); |
| } |
| |
| protected static ReportData decodeReportData(String dataS) { |
| ReportData data = new ReportData(); |
| StringTokenizer st = new StringTokenizer(dataS, "\t"); |
| Field[] fields = ReportData.class.getDeclaredFields(); |
| for (Field f : fields) { |
| String v = st.nextToken(); |
| try { |
| if ( f.getType() == String.class ) { |
| f.set(data, v); |
| } |
| else if ( f.getType() == double.class ) { |
| f.set(data, Double.valueOf(v)); |
| } |
| else { |
| f.set(data, Integer.valueOf(v)); |
| } |
| } |
| catch (Exception e) { |
| ErrorManager.internalError("Can't get data", e); |
| } |
| } |
| return data; |
| } |
| |
| public static String toString(String notifyDataLine) { |
| ReportData data = decodeReportData(notifyDataLine); |
| if ( data ==null ) { |
| return null; |
| } |
| StringBuffer buf = new StringBuffer(); |
| buf.append("ANTLR Grammar Report; Stats Version "); |
| buf.append(data.version); |
| buf.append('\n'); |
| buf.append("Grammar: "); |
| buf.append(data.gname); |
| buf.append('\n'); |
| buf.append("Type: "); |
| buf.append(data.gtype); |
| buf.append('\n'); |
| buf.append("Target language: "); |
| buf.append(data.language); |
| buf.append('\n'); |
| buf.append("Output: "); |
| buf.append(data.output); |
| buf.append('\n'); |
| buf.append("Grammar option k: "); |
| buf.append(data.grammarLevelk); |
| buf.append('\n'); |
| buf.append("Grammar option backtrack: "); |
| buf.append(data.grammarLevelBacktrack); |
| buf.append('\n'); |
| buf.append("Rules: "); |
| buf.append(data.numRules); |
| buf.append('\n'); |
| buf.append("Outer productions: "); |
| buf.append(data.numOuterProductions); |
| buf.append('\n'); |
| buf.append("Decisions: "); |
| buf.append(data.numberOfDecisions); |
| buf.append('\n'); |
| buf.append("Decisions (ignoring decisions in synpreds): "); |
| buf.append(data.numberOfDecisionsInRealRules); |
| buf.append('\n'); |
| buf.append("Fixed k DFA decisions: "); |
| buf.append(data.numberOfFixedKDecisions); |
| buf.append('\n'); |
| buf.append("Cyclic DFA decisions: "); |
| buf.append(data.numberOfCyclicDecisions); |
| buf.append('\n'); |
| buf.append("LL(1) decisions: "); buf.append(data.numLL1); |
| buf.append('\n'); |
| buf.append("Min fixed k: "); buf.append(data.mink); |
| buf.append('\n'); |
| buf.append("Max fixed k: "); buf.append(data.maxk); |
| buf.append('\n'); |
| buf.append("Average fixed k: "); buf.append(data.avgk); |
| buf.append('\n'); |
| // buf.append("Standard deviation of fixed k: "); buf.append(fields[12]); |
| // buf.append('\n'); |
| // buf.append("Min acyclic DFA states: "); buf.append(fields[13]); |
| // buf.append('\n'); |
| // buf.append("Max acyclic DFA states: "); buf.append(fields[14]); |
| // buf.append('\n'); |
| // buf.append("Average acyclic DFA states: "); buf.append(fields[15]); |
| // buf.append('\n'); |
| // buf.append("Standard deviation of acyclic DFA states: "); buf.append(fields[16]); |
| // buf.append('\n'); |
| // buf.append("Total acyclic DFA states: "); buf.append(fields[17]); |
| // buf.append('\n'); |
| // buf.append("Min cyclic DFA states: "); buf.append(fields[18]); |
| // buf.append('\n'); |
| // buf.append("Max cyclic DFA states: "); buf.append(fields[19]); |
| // buf.append('\n'); |
| // buf.append("Average cyclic DFA states: "); buf.append(fields[20]); |
| // buf.append('\n'); |
| // buf.append("Standard deviation of cyclic DFA states: "); buf.append(fields[21]); |
| // buf.append('\n'); |
| // buf.append("Total cyclic DFA states: "); buf.append(fields[22]); |
| // buf.append('\n'); |
| buf.append("DFA creation time in ms: "); |
| buf.append(data.DFACreationWallClockTimeInMS); |
| buf.append('\n'); |
| |
| // buf.append("Number of syntactic predicates available (including synpred rules): "); |
| // buf.append(data.num_synpreds); |
| // buf.append('\n'); |
| buf.append("Decisions with available syntactic predicates (ignoring synpred rules): "); |
| buf.append(data.blocksWithSynPreds); |
| buf.append('\n'); |
| buf.append("Decision DFAs using syntactic predicates (ignoring synpred rules): "); |
| buf.append(data.decisionsWhoseDFAsUsesSynPreds); |
| buf.append('\n'); |
| |
| buf.append("Number of semantic predicates found: "); |
| buf.append(data.numberOfSemanticPredicates); |
| buf.append('\n'); |
| buf.append("Decisions with semantic predicates: "); |
| buf.append(data.blocksWithSemPreds); |
| buf.append('\n'); |
| buf.append("Decision DFAs using semantic predicates: "); |
| buf.append(data.decisionsWhoseDFAsUsesSemPreds); |
| buf.append('\n'); |
| |
| buf.append("Number of (likely) non-LL(*) decisions: "); |
| buf.append(data.numNonLLStarDecisions); |
| buf.append('\n'); |
| buf.append("Number of nondeterministic decisions: "); |
| buf.append(data.numNondeterministicDecisions); |
| buf.append('\n'); |
| buf.append("Number of nondeterministic decisions resolved with predicates: "); |
| buf.append(data.numNondeterministicDecisionNumbersResolvedWithPredicates); |
| buf.append('\n'); |
| |
| buf.append("Number of manual or forced fixed lookahead k=value options: "); |
| buf.append(data.numberOfManualLookaheadOptions); |
| buf.append('\n'); |
| |
| buf.append("Vocabulary size: "); |
| buf.append(data.numTokens); |
| buf.append('\n'); |
| buf.append("Number of errors: "); |
| buf.append(data.errors); |
| buf.append('\n'); |
| buf.append("Number of warnings: "); |
| buf.append(data.warnings); |
| buf.append('\n'); |
| buf.append("Number of infos: "); |
| buf.append(data.infos); |
| buf.append('\n'); |
| return buf.toString(); |
| } |
| |
| public static boolean blockHasSynPred(GrammarAST blockAST) { |
| GrammarAST c1 = blockAST.findFirstType(ANTLRParser.SYN_SEMPRED); |
| GrammarAST c2 = blockAST.findFirstType(ANTLRParser.BACKTRACK_SEMPRED); |
| if ( c1!=null || c2!=null ) return true; |
| // System.out.println(blockAST.enclosingRuleName+ |
| // " "+blockAST.getLine()+":"+blockAST.getColumn()+" no preds AST="+blockAST.toStringTree()); |
| return false; |
| } |
| |
| } |