Home | History | Annotate | Download | only in analysis 
      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 
     29 package org.antlr.analysis;
     30 
     31 import org.antlr.misc.IntSet;
     32 import org.antlr.runtime.CommonToken;
     33 import org.antlr.runtime.Token;
     34 import org.antlr.tool.Grammar;
     35 
     36 import java.util.ArrayList;
     37 import java.util.HashSet;
     38 import java.util.List;
     39 import java.util.Set;
     40 
     41 public class MachineProbe {
     42 	DFA dfa;
     43 
     44 	public MachineProbe(DFA dfa) {
     45 		this.dfa = dfa;
     46 	}
     47 
     48 	List<DFAState> getAnyDFAPathToTarget(DFAState targetState) {
     49 		Set<DFAState> visited = new HashSet<DFAState>();
     50 		return getAnyDFAPathToTarget(dfa.startState, targetState, visited);
     51 	}
     52 
     53 	public List<DFAState> getAnyDFAPathToTarget(DFAState startState,
     54 			DFAState targetState, Set<DFAState> visited) {
     55 		List<DFAState> dfaStates = new ArrayList<DFAState>();
     56 		visited.add(startState);
     57 		if (startState.equals(targetState)) {
     58 			dfaStates.add(targetState);
     59 			return dfaStates;
     60 		}
     61 		// for (Edge e : startState.edges) { // walk edges looking for valid
     62 		// path
     63 		for (int i = 0; i < startState.getNumberOfTransitions(); i++) {
     64 			Transition e = startState.getTransition(i);
     65 			if (!visited.contains(e.target)) {
     66 				List<DFAState> path = getAnyDFAPathToTarget(
     67 						(DFAState) e.target, targetState, visited);
     68 				if (path != null) { // found path, we're done
     69 					dfaStates.add(startState);
     70 					dfaStates.addAll(path);
     71 					return dfaStates;
     72 				}
     73 			}
     74 		}
     75 		return null;
     76 	}
     77 
     78 	/** Return a list of edge labels from start state to targetState. */
     79 	public List<IntSet> getEdgeLabels(DFAState targetState) {
     80 		List<DFAState> dfaStates = getAnyDFAPathToTarget(targetState);
     81 		List<IntSet> labels = new ArrayList<IntSet>();
     82 		for (int i = 0; i < dfaStates.size() - 1; i++) {
     83 			DFAState d = dfaStates.get(i);
     84 			DFAState nextState = dfaStates.get(i + 1);
     85 			// walk looking for edge whose target is next dfa state
     86 			for (int j = 0; j < d.getNumberOfTransitions(); j++) {
     87 				Transition e = d.getTransition(j);
     88 				if (e.target.stateNumber == nextState.stateNumber) {
     89 					labels.add(e.label.getSet());
     90 				}
     91 			}
     92 		}
     93 		return labels;
     94 	}
     95 
     96 	/**
     97 	 * Given List<IntSet>, return a String with a useful representation of the
     98 	 * associated input string. One could show something different for lexers
     99 	 * and parsers, for example.
    100 	 */
    101 	public String getInputSequenceDisplay(Grammar g, List<IntSet> labels) {
    102 		List<String> tokens = new ArrayList<String>();
    103 		for (IntSet label : labels)
    104 			tokens.add(label.toString(g));
    105 		return tokens.toString();
    106 	}
    107 
    108 	/**
    109 	 * Given an alternative associated with a DFA state, return the list of
    110 	 * tokens (from grammar) associated with path through NFA following the
    111 	 * labels sequence. The nfaStates gives the set of NFA states associated
    112 	 * with alt that take us from start to stop. One of the NFA states in
    113 	 * nfaStates[i] will have an edge intersecting with labels[i].
    114 	 */
    115 	public List<Token> getGrammarLocationsForInputSequence(
    116 			List<Set<NFAState>> nfaStates, List<IntSet> labels) {
    117 		List<Token> tokens = new ArrayList<Token>();
    118 		for (int i = 0; i < nfaStates.size() - 1; i++) {
    119 			Set<NFAState> cur = nfaStates.get(i);
    120 			Set<NFAState> next = nfaStates.get(i + 1);
    121 			IntSet label = labels.get(i);
    122 			// find NFA state with edge whose label matches labels[i]
    123 			nfaConfigLoop:
    124 
    125 			for (NFAState p : cur) {
    126 				// walk p's transitions, looking for label
    127 				for (int j = 0; j < p.getNumberOfTransitions(); j++) {
    128 					Transition t = p.transition(j);
    129 					if (!t.isEpsilon() && !t.label.getSet().and(label).isNil()
    130 							&& next.contains(t.target)) {
    131 						if (p.associatedASTNode != null) {
    132 							Token oldtoken = p.associatedASTNode.token;
    133 							CommonToken token = new CommonToken(oldtoken
    134 									.getType(), oldtoken.getText());
    135 							token.setLine(oldtoken.getLine());
    136 							token.setCharPositionInLine(oldtoken.getCharPositionInLine());
    137 							tokens.add(token);
    138 							break nfaConfigLoop; // found path, move to next
    139 													// NFAState set
    140 						}
    141 					}
    142 				}
    143 			}
    144 		}
    145 		return tokens;
    146 	}
    147 
    148 	// /** Used to find paths through syntactically ambiguous DFA. If we've
    149 	// * seen statement number before, what did we learn?
    150 	// */
    151 	// protected Map<Integer, Integer> stateReachable;
    152 	//
    153 	// public Map<DFAState, Set<DFAState>> getReachSets(Collection<DFAState>
    154 	// targets) {
    155 	// Map<DFAState, Set<DFAState>> reaches = new HashMap<DFAState,
    156 	// Set<DFAState>>();
    157 	// // targets can reach themselves
    158 	// for (final DFAState d : targets) {
    159 	// reaches.put(d,new HashSet<DFAState>() {{add(d);}});
    160 	// }
    161 	//
    162 	// boolean changed = true;
    163 	// while ( changed ) {
    164 	// changed = false;
    165 	// for (DFAState d : dfa.states.values()) {
    166 	// if ( d.getNumberOfEdges()==0 ) continue;
    167 	// Set<DFAState> r = reaches.get(d);
    168 	// if ( r==null ) {
    169 	// r = new HashSet<DFAState>();
    170 	// reaches.put(d, r);
    171 	// }
    172 	// int before = r.size();
    173 	// // add all reaches from all edge targets
    174 	// for (Edge e : d.edges) {
    175 	// //if ( targets.contains(e.target) ) r.add(e.target);
    176 	// r.addAll( reaches.get(e.target) );
    177 	// }
    178 	// int after = r.size();
    179 	// if ( after>before) changed = true;
    180 	// }
    181 	// }
    182 	// return reaches;
    183 	// }
    184 
    185 }
    186