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