001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.analysis;
029:
030: /** An NFA state, predicted alt, and syntactic/semantic context.
031: * The syntactic context is a pointer into the rule invocation
032: * chain used to arrive at the state. The semantic context is
033: * the unordered set semantic predicates encountered before reaching
034: * an NFA state.
035: */
036: public class NFAConfiguration {
037: /** The NFA state associated with this configuration */
038: public int state;
039:
040: /** What alt is predicted by this configuration */
041: public int alt;
042:
043: /** What is the stack of rule invocations that got us to state? */
044: public NFAContext context;
045:
046: /** The set of semantic predicates associated with this NFA
047: * configuration. The predicates were found on the way to
048: * the associated NFA state in this syntactic context.
049: * Set<AST>: track nodes in grammar containing the predicate
050: * for error messages and such (nice to know where the predicate
051: * came from in case of duplicates etc...). By using a set,
052: * the equals() method will correctly show {pred1,pred2} as equals()
053: * to {pred2,pred1}.
054: */
055: public SemanticContext semanticContext = SemanticContext.EMPTY_SEMANTIC_CONTEXT;
056:
057: /** Indicate that this configuration has been resolved and no further
058: * DFA processing should occur with it. Essentially, this is used
059: * as an "ignore" bit so that upon a set of nondeterministic configurations
060: * such as (s|2) and (s|3), I can set (s|3) to resolved=true (and any
061: * other configuration associated with alt 3).
062: */
063: protected boolean resolved;
064:
065: /** This bit is used to indicate a semantic predicate will be
066: * used to resolve the conflict. Method
067: * DFA.findNewDFAStatesAndAddDFATransitions will add edges for
068: * the predicates after it performs the reach operation. The
069: * nondeterminism resolver sets this when it finds a set of
070: * nondeterministic configurations (as it does for "resolved" field)
071: * that have enough predicates to resolve the conflit.
072: */
073: protected boolean resolveWithPredicate;
074:
075: /** Lots of NFA states have only epsilon edges (1 or 2). We can
076: * safely consider only n>0 during closure.
077: */
078: protected int numberEpsilonTransitionsEmanatingFromState;
079:
080: /** Indicates that the NFA state associated with this configuration
081: * has exactly one transition and it's an atom (not epsilon etc...).
082: */
083: protected boolean singleAtomTransitionEmanating;
084:
085: public NFAConfiguration(int state, int alt, NFAContext context,
086: SemanticContext semanticContext) {
087: this .state = state;
088: this .alt = alt;
089: this .context = context;
090: this .semanticContext = semanticContext;
091: }
092:
093: /** An NFA configuration is equal to another if both have
094: * the same state, the predict the same alternative, and
095: * syntactic/semantic contexts are the same. I don't think
096: * the state|alt|ctx could be the same and have two different
097: * semantic contexts, but might as well define equals to be
098: * everything.
099: */
100: public boolean equals(Object o) {
101: if (o == null) {
102: return false;
103: }
104: NFAConfiguration other = (NFAConfiguration) o;
105: return this .state == other.state && this .alt == other.alt
106: && this .context.equals(other.context)
107: && this .semanticContext.equals(other.semanticContext);
108: }
109:
110: public int hashCode() {
111: int h = state + alt + context.hashCode();
112: return h;
113: }
114:
115: public String toString() {
116: return toString(true);
117: }
118:
119: public String toString(boolean showAlt) {
120: StringBuffer buf = new StringBuffer();
121: buf.append(state);
122: if (showAlt) {
123: buf.append("|");
124: buf.append(alt);
125: }
126: if (context.parent != null) {
127: buf.append("|");
128: buf.append(context);
129: }
130: if (semanticContext != null
131: && semanticContext != SemanticContext.EMPTY_SEMANTIC_CONTEXT) {
132: buf.append("|");
133: buf.append(semanticContext);
134: }
135: if (resolved) {
136: buf.append("|resolved");
137: }
138: if (resolveWithPredicate) {
139: buf.append("|resolveWithPredicate");
140: }
141: return buf.toString();
142: }
143: }
|