| /* |
| * [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.analysis; |
| |
| import org.antlr.misc.IntSet; |
| import org.antlr.runtime.CommonToken; |
| import org.antlr.runtime.Token; |
| import org.antlr.tool.Grammar; |
| |
| import java.util.ArrayList; |
| import java.util.HashSet; |
| import java.util.List; |
| import java.util.Set; |
| |
| public class MachineProbe { |
| DFA dfa; |
| |
| public MachineProbe(DFA dfa) { |
| this.dfa = dfa; |
| } |
| |
| List<DFAState> getAnyDFAPathToTarget(DFAState targetState) { |
| Set<DFAState> visited = new HashSet<DFAState>(); |
| return getAnyDFAPathToTarget(dfa.startState, targetState, visited); |
| } |
| |
| public List<DFAState> getAnyDFAPathToTarget(DFAState startState, |
| DFAState targetState, Set<DFAState> visited) { |
| List<DFAState> dfaStates = new ArrayList<DFAState>(); |
| visited.add(startState); |
| if (startState.equals(targetState)) { |
| dfaStates.add(targetState); |
| return dfaStates; |
| } |
| // for (Edge e : startState.edges) { // walk edges looking for valid |
| // path |
| for (int i = 0; i < startState.getNumberOfTransitions(); i++) { |
| Transition e = startState.getTransition(i); |
| if (!visited.contains(e.target)) { |
| List<DFAState> path = getAnyDFAPathToTarget( |
| (DFAState) e.target, targetState, visited); |
| if (path != null) { // found path, we're done |
| dfaStates.add(startState); |
| dfaStates.addAll(path); |
| return dfaStates; |
| } |
| } |
| } |
| return null; |
| } |
| |
| /** Return a list of edge labels from start state to targetState. */ |
| public List<IntSet> getEdgeLabels(DFAState targetState) { |
| List<DFAState> dfaStates = getAnyDFAPathToTarget(targetState); |
| List<IntSet> labels = new ArrayList<IntSet>(); |
| for (int i = 0; i < dfaStates.size() - 1; i++) { |
| DFAState d = dfaStates.get(i); |
| DFAState nextState = dfaStates.get(i + 1); |
| // walk looking for edge whose target is next dfa state |
| for (int j = 0; j < d.getNumberOfTransitions(); j++) { |
| Transition e = d.getTransition(j); |
| if (e.target.stateNumber == nextState.stateNumber) { |
| labels.add(e.label.getSet()); |
| } |
| } |
| } |
| return labels; |
| } |
| |
| /** |
| * Given List<IntSet>, return a String with a useful representation of the |
| * associated input string. One could show something different for lexers |
| * and parsers, for example. |
| */ |
| public String getInputSequenceDisplay(Grammar g, List<IntSet> labels) { |
| List<String> tokens = new ArrayList<String>(); |
| for (IntSet label : labels) |
| tokens.add(label.toString(g)); |
| return tokens.toString(); |
| } |
| |
| /** |
| * Given an alternative associated with a DFA state, return the list of |
| * tokens (from grammar) associated with path through NFA following the |
| * labels sequence. The nfaStates gives the set of NFA states associated |
| * with alt that take us from start to stop. One of the NFA states in |
| * nfaStates[i] will have an edge intersecting with labels[i]. |
| */ |
| public List<Token> getGrammarLocationsForInputSequence( |
| List<Set<NFAState>> nfaStates, List<IntSet> labels) { |
| List<Token> tokens = new ArrayList<Token>(); |
| for (int i = 0; i < nfaStates.size() - 1; i++) { |
| Set<NFAState> cur = nfaStates.get(i); |
| Set<NFAState> next = nfaStates.get(i + 1); |
| IntSet label = labels.get(i); |
| // find NFA state with edge whose label matches labels[i] |
| nfaConfigLoop: |
| |
| for (NFAState p : cur) { |
| // walk p's transitions, looking for label |
| for (int j = 0; j < p.getNumberOfTransitions(); j++) { |
| Transition t = p.transition(j); |
| if (!t.isEpsilon() && !t.label.getSet().and(label).isNil() |
| && next.contains(t.target)) { |
| if (p.associatedASTNode != null) { |
| Token oldtoken = p.associatedASTNode.token; |
| CommonToken token = new CommonToken(oldtoken |
| .getType(), oldtoken.getText()); |
| token.setLine(oldtoken.getLine()); |
| token.setCharPositionInLine(oldtoken.getCharPositionInLine()); |
| tokens.add(token); |
| break nfaConfigLoop; // found path, move to next |
| // NFAState set |
| } |
| } |
| } |
| } |
| } |
| return tokens; |
| } |
| |
| // /** Used to find paths through syntactically ambiguous DFA. If we've |
| // * seen statement number before, what did we learn? |
| // */ |
| // protected Map<Integer, Integer> stateReachable; |
| // |
| // public Map<DFAState, Set<DFAState>> getReachSets(Collection<DFAState> |
| // targets) { |
| // Map<DFAState, Set<DFAState>> reaches = new HashMap<DFAState, |
| // Set<DFAState>>(); |
| // // targets can reach themselves |
| // for (final DFAState d : targets) { |
| // reaches.put(d,new HashSet<DFAState>() {{add(d);}}); |
| // } |
| // |
| // boolean changed = true; |
| // while ( changed ) { |
| // changed = false; |
| // for (DFAState d : dfa.states.values()) { |
| // if ( d.getNumberOfEdges()==0 ) continue; |
| // Set<DFAState> r = reaches.get(d); |
| // if ( r==null ) { |
| // r = new HashSet<DFAState>(); |
| // reaches.put(d, r); |
| // } |
| // int before = r.size(); |
| // // add all reaches from all edge targets |
| // for (Edge e : d.edges) { |
| // //if ( targets.contains(e.target) ) r.add(e.target); |
| // r.addAll( reaches.get(e.target) ); |
| // } |
| // int after = r.size(); |
| // if ( after>before) changed = true; |
| // } |
| // } |
| // return reaches; |
| // } |
| |
| } |