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.analysis; 29 30 import org.antlr.misc.Utils; 31 32 /** An NFA state, predicted alt, and syntactic/semantic context. 33 * The syntactic context is a pointer into the rule invocation 34 * chain used to arrive at the state. The semantic context is 35 * the unordered set semantic predicates encountered before reaching 36 * an NFA state. 37 */ 38 public class NFAConfiguration { 39 /** The NFA state associated with this configuration */ 40 public int state; 41 42 /** What alt is predicted by this configuration */ 43 public int alt; 44 45 /** What is the stack of rule invocations that got us to state? */ 46 public NFAContext context; 47 48 /** The set of semantic predicates associated with this NFA 49 * configuration. The predicates were found on the way to 50 * the associated NFA state in this syntactic context. 51 * Set<AST>: track nodes in grammar containing the predicate 52 * for error messages and such (nice to know where the predicate 53 * came from in case of duplicates etc...). By using a set, 54 * the equals() method will correctly show {pred1,pred2} as equals() 55 * to {pred2,pred1}. 56 */ 57 public SemanticContext semanticContext = SemanticContext.EMPTY_SEMANTIC_CONTEXT; 58 59 /** Indicate that this configuration has been resolved and no further 60 * DFA processing should occur with it. Essentially, this is used 61 * as an "ignore" bit so that upon a set of nondeterministic configurations 62 * such as (s|2) and (s|3), I can set (s|3) to resolved=true (and any 63 * other configuration associated with alt 3). 64 */ 65 protected boolean resolved; 66 67 /** This bit is used to indicate a semantic predicate will be 68 * used to resolve the conflict. Method 69 * DFA.findNewDFAStatesAndAddDFATransitions will add edges for 70 * the predicates after it performs the reach operation. The 71 * nondeterminism resolver sets this when it finds a set of 72 * nondeterministic configurations (as it does for "resolved" field) 73 * that have enough predicates to resolve the conflit. 74 */ 75 protected boolean resolveWithPredicate; 76 77 /** Lots of NFA states have only epsilon edges (1 or 2). We can 78 * safely consider only n>0 during closure. 79 */ 80 protected int numberEpsilonTransitionsEmanatingFromState; 81 82 /** Indicates that the NFA state associated with this configuration 83 * has exactly one transition and it's an atom (not epsilon etc...). 84 */ 85 protected boolean singleAtomTransitionEmanating; 86 87 //protected boolean addedDuringClosure = true; 88 89 public NFAConfiguration(int state, 90 int alt, 91 NFAContext context, 92 SemanticContext semanticContext) 93 { 94 this.state = state; 95 this.alt = alt; 96 this.context = context; 97 this.semanticContext = semanticContext; 98 } 99 100 /** An NFA configuration is equal to another if both have 101 * the same state, the predict the same alternative, and 102 * syntactic/semantic contexts are the same. I don't think 103 * the state|alt|ctx could be the same and have two different 104 * semantic contexts, but might as well define equals to be 105 * everything. 106 */ 107 public boolean equals(Object o) { 108 if ( o==null ) { 109 return false; 110 } 111 NFAConfiguration other = (NFAConfiguration)o; 112 return this.state==other.state && 113 this.alt==other.alt && 114 this.context.equals(other.context)&& 115 this.semanticContext.equals(other.semanticContext); 116 } 117 118 public int hashCode() { 119 int h = state + alt + context.hashCode(); 120 return h; 121 } 122 123 public String toString() { 124 return toString(true); 125 } 126 127 public String toString(boolean showAlt) { 128 StringBuffer buf = new StringBuffer(); 129 buf.append(state); 130 if ( showAlt ) { 131 buf.append("|"); 132 buf.append(alt); 133 } 134 if ( context.parent!=null ) { 135 buf.append("|"); 136 buf.append(context); 137 } 138 if ( semanticContext!=null && 139 semanticContext!=SemanticContext.EMPTY_SEMANTIC_CONTEXT ) { 140 buf.append("|"); 141 String escQuote = Utils.replace(semanticContext.toString(), "\"", "\\\""); 142 buf.append(escQuote); 143 } 144 if ( resolved ) { 145 buf.append("|resolved"); 146 } 147 if ( resolveWithPredicate ) { 148 buf.append("|resolveWithPredicate"); 149 } 150 return buf.toString(); 151 } 152 } 153
