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.Tool; 31 import org.antlr.analysis.Label; 32 import org.antlr.analysis.NFAState; 33 import org.antlr.analysis.RuleClosureTransition; 34 import org.antlr.analysis.Transition; 35 import org.antlr.misc.IntervalSet; 36 import org.antlr.misc.Utils; 37 38 import java.io.BufferedReader; 39 import java.io.FileReader; 40 import java.util.ArrayList; 41 import java.util.List; 42 import java.util.Random; 43 import java.util.Stack; 44 45 /** Generate a random phrase given a grammar. 46 * Usage: 47 * java org.antlr.tool.RandomPhrase grammarFile.g startRule [seed] 48 * 49 * For example: 50 * java org.antlr.tool.RandomPhrase simple.g program 342 51 * 52 * The seed acts like a unique identifier so you can get the same random 53 * phrase back during unit testing, for example. 54 * 55 * If you do not specify a seed then the current time in milliseconds is used 56 * guaranteeing that you'll never see that seed again. 57 * 58 * NOTE: this does not work well for large grammars...it tends to recurse 59 * too much and build really long strings. I need throttle control; later. 60 */ 61 public class RandomPhrase { 62 public static final boolean debug = false; 63 64 protected static Random random; 65 66 /** an experimental method to generate random phrases for a given 67 * grammar given a start rule. Return a list of token types. 68 */ randomPhrase(Grammar g, List<Integer> tokenTypes, String startRule)69 protected static void randomPhrase(Grammar g, List<Integer> tokenTypes, String startRule) { 70 NFAState state = g.getRuleStartState(startRule); 71 NFAState stopState = g.getRuleStopState(startRule); 72 73 Stack ruleInvocationStack = new Stack(); 74 while ( true ) { 75 if ( state==stopState && ruleInvocationStack.size()==0 ) { 76 break; 77 } 78 if ( debug ) System.out.println("state "+state); 79 if ( state.getNumberOfTransitions()==0 ) { 80 if ( debug ) System.out.println("dangling state: "+state); 81 return; 82 } 83 // end of rule node 84 if ( state.isAcceptState() ) { 85 NFAState invokingState = (NFAState)ruleInvocationStack.pop(); 86 if ( debug ) System.out.println("pop invoking state "+invokingState); 87 //System.out.println("leave "+state.enclosingRule.name); 88 RuleClosureTransition invokingTransition = 89 (RuleClosureTransition)invokingState.transition[0]; 90 // move to node after state that invoked this rule 91 state = invokingTransition.followState; 92 continue; 93 } 94 if ( state.getNumberOfTransitions()==1 ) { 95 // no branching, just take this path 96 Transition t0 = state.transition[0]; 97 if ( t0 instanceof RuleClosureTransition ) { 98 ruleInvocationStack.push(state); 99 if ( debug ) System.out.println("push state "+state); 100 //System.out.println("call "+((RuleClosureTransition)t0).rule.name); 101 //System.out.println("stack depth="+ruleInvocationStack.size()); 102 } 103 else if ( t0.label.isSet() || t0.label.isAtom() ) { 104 tokenTypes.add( getTokenType(t0.label) ); 105 } 106 state = (NFAState)t0.target; 107 continue; 108 } 109 110 int decisionNumber = state.getDecisionNumber(); 111 if ( decisionNumber==0 ) { 112 System.out.println("weird: no decision number but a choice node"); 113 continue; 114 } 115 // decision point, pick ith alternative randomly 116 int n = g.getNumberOfAltsForDecisionNFA(state); 117 int randomAlt = random.nextInt(n) + 1; 118 if ( debug ) System.out.println("randomAlt="+randomAlt); 119 NFAState altStartState = 120 g.getNFAStateForAltOfDecision(state, randomAlt); 121 Transition t = altStartState.transition[0]; 122 state = (NFAState)t.target; 123 } 124 } 125 getTokenType(Label label)126 protected static Integer getTokenType(Label label) { 127 if ( label.isSet() ) { 128 // pick random element of set 129 IntervalSet typeSet = (IntervalSet)label.getSet(); 130 int randomIndex = random.nextInt(typeSet.size()); 131 return typeSet.get(randomIndex); 132 } 133 else { 134 return Utils.integer(label.getAtom()); 135 } 136 //System.out.println(t0.label.toString(g)); 137 } 138 139 /** Used to generate random strings */ main(String[] args)140 public static void main(String[] args) { 141 if ( args.length < 2 ) { 142 System.err.println("usage: java org.antlr.tool.RandomPhrase grammarfile startrule"); 143 return; 144 } 145 String grammarFileName = args[0]; 146 String startRule = args[1]; 147 long seed = System.currentTimeMillis(); // use random seed unless spec. 148 if ( args.length==3 ) { 149 String seedStr = args[2]; 150 seed = Long.parseLong(seedStr); 151 } 152 try { 153 random = new Random(seed); 154 155 CompositeGrammar composite = new CompositeGrammar(); 156 Tool tool = new Tool(); 157 Grammar parser = new Grammar(tool, grammarFileName, composite); 158 composite.setDelegationRoot(parser); 159 160 FileReader fr = new FileReader(grammarFileName); 161 BufferedReader br = new BufferedReader(fr); 162 parser.parseAndBuildAST(br); 163 br.close(); 164 165 parser.composite.assignTokenTypes(); 166 parser.composite.defineGrammarSymbols(); 167 parser.composite.createNFAs(); 168 169 List leftRecursiveRules = parser.checkAllRulesForLeftRecursion(); 170 if ( leftRecursiveRules.size()>0 ) { 171 return; 172 } 173 174 if ( parser.getRule(startRule)==null ) { 175 System.out.println("undefined start rule "+startRule); 176 return; 177 } 178 179 String lexerGrammarText = parser.getLexerGrammar(); 180 Grammar lexer = new Grammar(tool); 181 lexer.importTokenVocabulary(parser); 182 lexer.fileName = grammarFileName; 183 if ( lexerGrammarText!=null ) { 184 lexer.setGrammarContent(lexerGrammarText); 185 } 186 else { 187 System.err.println("no lexer grammar found in "+grammarFileName); 188 } 189 lexer.buildNFA(); 190 leftRecursiveRules = lexer.checkAllRulesForLeftRecursion(); 191 if ( leftRecursiveRules.size()>0 ) { 192 return; 193 } 194 //System.out.println("lexer:\n"+lexer); 195 196 List<Integer> tokenTypes = new ArrayList<Integer>(100); 197 randomPhrase(parser, tokenTypes, startRule); 198 System.out.println("token types="+tokenTypes); 199 for (int i = 0; i < tokenTypes.size(); i++) { 200 Integer ttypeI = (Integer) tokenTypes.get(i); 201 int ttype = ttypeI.intValue(); 202 String ttypeDisplayName = parser.getTokenDisplayName(ttype); 203 if ( Character.isUpperCase(ttypeDisplayName.charAt(0)) ) { 204 List<Integer> charsInToken = new ArrayList<Integer>(10); 205 randomPhrase(lexer, charsInToken, ttypeDisplayName); 206 System.out.print(" "); 207 for (int j = 0; j < charsInToken.size(); j++) { 208 java.lang.Integer cI = (java.lang.Integer) charsInToken.get(j); 209 System.out.print((char)cI.intValue()); 210 } 211 } 212 else { // it's a literal 213 String literal = 214 ttypeDisplayName.substring(1,ttypeDisplayName.length()-1); 215 System.out.print(" "+literal); 216 } 217 } 218 System.out.println(); 219 } 220 catch (Error er) { 221 System.err.println("Error walking "+grammarFileName+" rule "+startRule+" seed "+seed); 222 er.printStackTrace(System.err); 223 } 224 catch (Exception e) { 225 System.err.println("Exception walking "+grammarFileName+" rule "+startRule+" seed "+seed); 226 e.printStackTrace(System.err); 227 } 228 } 229 } 230