001: package org.antlr.tool;
002:
003: import org.antlr.analysis.NFAState;
004: import org.antlr.analysis.RuleClosureTransition;
005: import org.antlr.analysis.Transition;
006: import org.antlr.analysis.Label;
007: import org.antlr.misc.IntSet;
008: import org.antlr.misc.Utils;
009:
010: import java.io.BufferedReader;
011: import java.io.FileReader;
012: import java.util.List;
013: import java.util.ArrayList;
014: import java.util.Stack;
015: import java.util.Random;
016:
017: /** Generate a random phrase given a grammar.
018: * Usage:
019: * java org.antlr.tool.RandomPhrase grammarFile.g startRule [seed]
020: *
021: * For example:
022: * java org.antlr.tool.RandomPhrase simple.g program 342
023: *
024: * The seed acts like a unique identifier so you can get the same random
025: * phrase back during unit testing, for example.
026: *
027: * If you do not specify a seed then the current time in milliseconds is used
028: * guaranteeing that you'll never see that seed again.
029: */
030: public class RandomPhrase {
031: protected static Random random;
032:
033: /** an experimental method to generate random phrases for a given
034: * grammar given a start rule. Return a list of token types.
035: */
036: protected static void randomPhrase(Grammar g, List tokenTypes,
037: String startRule) {
038: NFAState state = g.getRuleStartState(startRule);
039: NFAState stopState = g.getRuleStopState(startRule);
040:
041: Stack ruleInvocationStack = new Stack();
042: while (true) {
043: if (state == stopState && ruleInvocationStack.size() == 0) {
044: break;
045: }
046: //System.out.println("state "+state);
047: if (state.getNumberOfTransitions() == 0) {
048: //System.out.println("dangling state: "+state);
049: return;
050: }
051: // end of rule node
052: if (state.isAcceptState()) {
053: NFAState invokingState = (NFAState) ruleInvocationStack
054: .pop();
055: // System.out.println("pop invoking state "+invokingState);
056: RuleClosureTransition invokingTransition = (RuleClosureTransition) invokingState
057: .transition(0);
058: // move to node after state that invoked this rule
059: state = invokingTransition.getFollowState();
060: continue;
061: }
062: if (state.getNumberOfTransitions() == 1) {
063: // no branching, just take this path
064: Transition t0 = state.transition(0);
065: if (t0 instanceof RuleClosureTransition) {
066: ruleInvocationStack.push(state);
067: // System.out.println("push state "+state);
068: int ruleIndex = ((RuleClosureTransition) t0)
069: .getRuleIndex();
070: //System.out.println("invoke "+g.getRuleName(ruleIndex));
071: } else if (!t0.label.isEpsilon()) {
072: tokenTypes.add(getTokenType(t0.label));
073: //System.out.println(t0.label.toString(g));
074: }
075: state = (NFAState) t0.target;
076: continue;
077: }
078:
079: int decisionNumber = state.getDecisionNumber();
080: if (decisionNumber == 0) {
081: System.out
082: .println("weird: no decision number but a choice node");
083: continue;
084: }
085: // decision point, pick ith alternative randomly
086: int n = g.getNumberOfAltsForDecisionNFA(state);
087: int randomAlt = random.nextInt(n) + 1;
088: //System.out.println("randomAlt="+randomAlt);
089: NFAState altStartState = g.getNFAStateForAltOfDecision(
090: state, randomAlt);
091: Transition t = altStartState.transition(0);
092: /*
093: start of a decision could never be a labeled transition
094: if ( !t.label.isEpsilon() ) {
095: tokenTypes.add( getTokenType(t.label) );
096: }
097: */
098: state = (NFAState) t.target;
099: }
100: }
101:
102: protected static Integer getTokenType(Label label) {
103: if (label.isSet()) {
104: // pick random element of set
105: IntSet typeSet = label.getSet();
106: List typeList = typeSet.toList();
107: int randomIndex = random.nextInt(typeList.size());
108: return (Integer) typeList.get(randomIndex);
109: } else {
110: return Utils.integer(label.getAtom());
111: }
112: //System.out.println(t0.label.toString(g));
113: }
114:
115: /** Used to generate random strings */
116: public static void main(String[] args) throws Exception {
117: String grammarFileName = args[0];
118: String startRule = args[1];
119: long seed = System.currentTimeMillis(); // use random seed unless spec.
120: if (args.length == 3) {
121: String seedStr = args[2];
122: seed = Integer.parseInt(seedStr);
123: }
124: random = new Random(seed);
125:
126: Grammar parser = new Grammar(null, grammarFileName,
127: new BufferedReader(new FileReader(grammarFileName)));
128: parser.createNFAs();
129:
130: List leftRecursiveRules = parser
131: .checkAllRulesForLeftRecursion();
132: if (leftRecursiveRules.size() > 0) {
133: return;
134: }
135:
136: if (parser.getRule(startRule) == null) {
137: System.out.println("undefined start rule " + startRule);
138: return;
139: }
140:
141: String lexerGrammarText = parser.getLexerGrammar();
142: Grammar lexer = new Grammar();
143: lexer.importTokenVocabulary(parser);
144: if (lexerGrammarText != null) {
145: lexer.setGrammarContent(lexerGrammarText);
146: } else {
147: System.err.println("no lexer grammar found in "
148: + grammarFileName);
149: }
150: lexer.createNFAs();
151: leftRecursiveRules = lexer.checkAllRulesForLeftRecursion();
152: if (leftRecursiveRules.size() > 0) {
153: return;
154: }
155:
156: List tokenTypes = new ArrayList(100);
157: randomPhrase(parser, tokenTypes, startRule);
158: //System.out.println("token types="+tokenTypes);
159: for (int i = 0; i < tokenTypes.size(); i++) {
160: Integer ttypeI = (Integer) tokenTypes.get(i);
161: int ttype = ttypeI.intValue();
162: String ttypeDisplayName = parser.getTokenDisplayName(ttype);
163: if (Character.isUpperCase(ttypeDisplayName.charAt(0))) {
164: List charsInToken = new ArrayList(10);
165: randomPhrase(lexer, charsInToken, ttypeDisplayName);
166: System.out.print(" ");
167: for (int j = 0; j < charsInToken.size(); j++) {
168: java.lang.Integer cI = (java.lang.Integer) charsInToken
169: .get(j);
170: System.out.print((char) cI.intValue());
171: }
172: } else { // it's a literal
173: String literal = ttypeDisplayName.substring(1,
174: ttypeDisplayName.length() - 1);
175: System.out.print(" " + literal);
176: }
177: }
178: System.out.println();
179: }
180:
181: }
|