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: import org.antlr.misc.IntSet;
031: import org.antlr.misc.OrderedHashSet;
032: import org.antlr.misc.Utils;
033: import org.antlr.tool.Grammar;
034:
035: import java.util.*;
036:
037: /** A DFA state represents a set of possible NFA configurations.
038: * As Aho, Sethi, Ullman p. 117 says "The DFA uses its state
039: * to keep track of all possible states the NFA can be in after
040: * reading each input symbol. That is to say, after reading
041: * input a1a2..an, the DFA is in a state that represents the
042: * subset T of the states of the NFA that are reachable from the
043: * NFA's start state along some path labeled a1a2..an."
044: * In conventional NFA->DFA conversion, therefore, the subset T
045: * would be a bitset representing the set of states the
046: * NFA could be in. We need to track the alt predicted by each
047: * state as well, however. More importantly, we need to maintain
048: * a stack of states, tracking the closure operations as they
049: * jump from rule to rule, emulating rule invocations (method calls).
050: * Recall that NFAs do not normally have a stack like a pushdown-machine
051: * so I have to add one to simulate the proper lookahead sequences for
052: * the underlying LL grammar from which the NFA was derived.
053: *
054: * I use a list of NFAConfiguration objects. An NFAConfiguration
055: * is both a state (ala normal conversion) and an NFAContext describing
056: * the chain of rules (if any) followed to arrive at that state. There
057: * is also the semantic context, which is the "set" of predicates found
058: * on the path to this configuration.
059: *
060: * A DFA state may have multiple references to a particular state,
061: * but with different NFAContexts (with same or different alts)
062: * meaning that state was reached via a different set of rule invocations.
063: */
064: public class DFAState extends State {
065: public static final int INITIAL_NUM_TRANSITIONS = 4;
066: public static final int PREDICTED_ALT_UNSET = NFA.INVALID_ALT_NUMBER - 1;
067:
068: /** We are part of what DFA? Use this ref to get access to the
069: * context trees for an alt.
070: */
071: public DFA dfa;
072:
073: /** Track the transitions emanating from this DFA state. The List
074: * elements are Transition objects.
075: */
076: protected List transitions = new ArrayList(INITIAL_NUM_TRANSITIONS);
077:
078: /** When doing an acyclic DFA, this is the number of lookahead symbols
079: * consumed to reach this state. This value may be nonzero for most
080: * dfa states, but it is only a valid value if the user has specified
081: * a max fixed lookahead.
082: */
083: protected int k;
084:
085: /** The NFA->DFA algorithm may terminate leaving some states
086: * without a path to an accept state, implying that upon certain
087: * input, the decision is not deterministic--no decision about
088: * predicting a unique alternative can be made. Recall that an
089: * accept state is one in which a unique alternative is predicted.
090: */
091: protected int acceptStateReachable = DFA.REACHABLE_UNKNOWN;
092:
093: /** Rather than recheck every NFA configuration in a DFA state (after
094: * resolving) in findNewDFAStatesAndAddDFATransitions just check
095: * this boolean. Saves a linear walk perhaps DFA state creation.
096: * Every little bit helps.
097: */
098: protected boolean resolvedWithPredicates = false;
099:
100: /** If a closure operation finds that we tried to invoke the same
101: * rule too many times (stack would grow beyond a threshold), it
102: * marks the state has aborted and notifies the DecisionProbe.
103: */
104: protected boolean abortedDueToRecursionOverflow = false;
105:
106: /** If we detect recursion on more than one alt, decision is non-LL(*),
107: * but try to isolate it to only those states whose closure operations
108: * detect recursion. There may be other alts that are cool:
109: *
110: * a : recur '.'
111: * | recur ';'
112: * | X Y // LL(2) decision; don't abort and use k=1 plus backtracking
113: * | X Z
114: * ;
115: */
116: protected boolean abortedDueToMultipleRecursiveAlts = false;
117:
118: /** Build up the hash code for this state as NFA configurations
119: * are added as it's monotonically increasing list of configurations.
120: */
121: protected int cachedHashCode;
122:
123: protected int cachedUniquelyPredicatedAlt = PREDICTED_ALT_UNSET;
124:
125: /** The set of NFA configurations (state,alt,context) for this DFA state */
126: protected Set nfaConfigurations = new HashSet();
127:
128: /** Used to prevent the closure operation from looping to itself and
129: * hence looping forever. Sensitive to the NFA state, the alt, and
130: * the context. This just the nfa config set because we want to
131: * prevent closures only on states contributed by closure not reach
132: * operations.
133: */
134: protected Set closureBusy = new HashSet();
135:
136: /** As this state is constructed (i.e., as NFA states are added), we
137: * can easily check for non-epsilon transitions because the only
138: * transition that could be a valid label is transition(0). When we
139: * process this node eventually, we'll have to walk all states looking
140: * for all possible transitions. That is of the order: size(label space)
141: * times size(nfa states), which can be pretty damn big. It's better
142: * to simply track possible labels.
143: * This is type List<Label>.
144: */
145: protected OrderedHashSet reachableLabels = new OrderedHashSet();
146:
147: public DFAState(DFA dfa) {
148: this .dfa = dfa;
149: }
150:
151: public Transition transition(int i) {
152: return (Transition) transitions.get(i);
153: }
154:
155: public int getNumberOfTransitions() {
156: return transitions.size();
157: }
158:
159: public void addTransition(Transition t) {
160: transitions.add(t);
161: }
162:
163: /** Add a transition from this state to target with label. Return
164: * the transition number from 0..n-1.
165: */
166: public int addTransition(DFAState target, Label label) {
167: transitions.add(new Transition(label, target));
168: return transitions.size() - 1;
169: }
170:
171: public Transition getTransition(int trans) {
172: return (Transition) transitions.get(trans);
173: }
174:
175: public void removeTransition(int trans) {
176: transitions.remove(trans);
177: }
178:
179: /** Add an NFA configuration to this DFA node. Add uniquely
180: * an NFA state/alt/syntactic&semantic context (chain of invoking state(s)
181: * and semantic predicate contexts).
182: *
183: * I don't see how there could be two configurations with same
184: * state|alt|synCtx and different semantic contexts because the
185: * semantic contexts are computed along the path to a particular state
186: * so those two configurations would have to have the same predicate.
187: * Nonetheless, the addition of configurations is unique on all
188: * configuration info. I guess I'm saying that syntactic context
189: * implies semantic context as the latter is computed according to the
190: * former.
191: *
192: * As we add configurations to this DFA state, track the set of all possible
193: * transition labels so we can simply walk it later rather than doing a
194: * loop over all possible labels in the NFA.
195: */
196: public void addNFAConfiguration(NFAState state, NFAConfiguration c) {
197: if (nfaConfigurations.contains(c)) {
198: return;
199: }
200:
201: nfaConfigurations.add(c);
202:
203: // update hashCode; for some reason using context.hashCode() also
204: // makes the GC take like 70% of the CPU and is slow!
205: cachedHashCode += c.state + c.alt;
206:
207: // update reachableLabels
208: if (state.transition(0) != null) {
209: Label label = state.transition(0).label;
210: if (!(label.isEpsilon() || label.isSemanticPredicate())) {
211: if (state.transition(1) == null) {
212: c.singleAtomTransitionEmanating = true;
213: }
214: addReachableLabel(label);
215: }
216: }
217: }
218:
219: public void addNFAConfiguration(NFAState state, int alt,
220: NFAContext context, SemanticContext semanticContext) {
221: NFAConfiguration c = new NFAConfiguration(state.stateNumber,
222: alt, context, semanticContext);
223: addNFAConfiguration(state, c);
224: }
225:
226: /** Add label uniquely and disjointly; intersection with
227: * another set or int/char forces breaking up the set(s).
228: *
229: * Example, if reachable list of labels is [a..z, {k,9}, 0..9],
230: * the disjoint list will be [{a..j,l..z}, k, 9, 0..8].
231: *
232: * As we add NFA configurations to a DFA state, we might as well track
233: * the set of all possible transition labels to make the DFA conversion
234: * more efficient. W/o the reachable labels, we'd need to check the
235: * whole vocabulary space (could be 0..\uFFFF)! The problem is that
236: * labels can be sets, which may overlap with int labels or other sets.
237: * As we need a deterministic set of transitions from any
238: * state in the DFA, we must make the reachable labels set disjoint.
239: * This operation amounts to finding the character classes for this
240: * DFA state whereas with tools like flex, that need to generate a
241: * homogeneous DFA, must compute char classes across all states.
242: * We are going to generate DFAs with heterogeneous states so we
243: * only care that the set of transitions out of a single state are
244: * unique. :)
245: *
246: * The idea for adding a new set, t, is to look for overlap with the
247: * elements of existing list s. Upon overlap, replace
248: * existing set s[i] with two new disjoint sets, s[i]-t and s[i]&t.
249: * (if s[i]-t is nil, don't add). The remainder is t-s[i], which is
250: * what you want to add to the set minus what was already there. The
251: * remainder must then be compared against the i+1..n elements in s
252: * looking for another collision. Each collision results in a smaller
253: * and smaller remainder. Stop when you run out of s elements or
254: * remainder goes to nil. If remainder is non nil when you run out of
255: * s elements, then add remainder to the end.
256: *
257: * Single element labels are treated as sets to make the code uniform.
258: */
259: protected void addReachableLabel(Label label) {
260: /*
261: System.out.println("addReachableLabel to state "+dfa.decisionNumber+"."+stateNumber+": "+label.getSet().toString(dfa.nfa.grammar));
262: System.out.println("start of add to state "+dfa.decisionNumber+"."+stateNumber+": " +
263: "reachableLabels="+reachableLabels.toString());
264: */
265: if (reachableLabels.contains(label)) { // exact label present
266: return;
267: }
268: IntSet t = label.getSet();
269: IntSet remainder = t; // remainder starts out as whole set to add
270: int n = reachableLabels.size(); // only look at initial elements
271: // walk the existing list looking for the collision
272: for (int i = 0; i < n; i++) {
273: Label rl = (Label) reachableLabels.get(i);
274: /*
275: if ( label.equals(rl) ) {
276: // OPTIMIZATION:
277: // exact label already here, just return; previous addition
278: // would have made everything unique/disjoint
279: return;
280: }
281: */
282: IntSet s_i = rl.getSet();
283: IntSet intersection = s_i.and(t);
284: /*
285: System.out.println("comparing ["+i+"]: "+label.toString(dfa.nfa.grammar)+" & "+
286: rl.toString(dfa.nfa.grammar)+"="+
287: intersection.toString(dfa.nfa.grammar));
288: */
289: if (intersection.isNil()) {
290: continue;
291: }
292:
293: // For any (s_i, t) with s_i&t!=nil replace with (s_i-t, s_i&t)
294: // (ignoring s_i-t if nil; don't put in list)
295:
296: // Replace existing s_i with intersection since we
297: // know that will always be a non nil character class
298: reachableLabels.set(i, new Label(intersection));
299:
300: // Compute s_i-t to see what is in current set and not in incoming
301: IntSet existingMinusNewElements = s_i.subtract(t);
302: //System.out.println(s_i+"-"+t+"="+existingMinusNewElements);
303: if (!existingMinusNewElements.isNil()) {
304: // found a new character class, add to the end (doesn't affect
305: // outer loop duration due to n computation a priori.
306: Label newLabel = new Label(existingMinusNewElements);
307: reachableLabels.add(newLabel);
308: }
309:
310: /*
311: System.out.println("after collision, " +
312: "reachableLabels="+reachableLabels.toString());
313: */
314:
315: // anything left to add to the reachableLabels?
316: remainder = t.subtract(s_i);
317: if (remainder.isNil()) {
318: break; // nothing left to add to set. done!
319: }
320:
321: t = remainder;
322: }
323: if (!remainder.isNil()) {
324: /*
325: System.out.println("before add remainder to state "+dfa.decisionNumber+"."+stateNumber+": " +
326: "reachableLabels="+reachableLabels.toString());
327: System.out.println("remainder state "+dfa.decisionNumber+"."+stateNumber+": "+remainder.toString(dfa.nfa.grammar));
328: */
329: Label newLabel = new Label(remainder);
330: reachableLabels.add(newLabel);
331: }
332: /*
333: System.out.println("#END of add to state "+dfa.decisionNumber+"."+stateNumber+": " +
334: "reachableLabels="+reachableLabels.toString());
335: */
336: }
337:
338: public OrderedHashSet getReachableLabels() {
339: return reachableLabels;
340: }
341:
342: public Set getNFAConfigurations() {
343: return this .nfaConfigurations;
344: }
345:
346: public void setNFAConfigurations(Set configs) {
347: this .nfaConfigurations = configs;
348: }
349:
350: /** A decent hash for a DFA state is the sum of the NFA state/alt pairs.
351: * This is used when we add DFAState objects to the DFA.states Map and
352: * when we compare DFA states. Computed in addNFAConfiguration()
353: */
354: public int hashCode() {
355: return cachedHashCode;
356: }
357:
358: /** Two DFAStates are equal if their NFA configuration sets are the
359: * same. This method is used to see if a DFA state already exists.
360: *
361: * Because the number of alternatives and number of NFA configurations are
362: * finite, there is a finite number of DFA states that can be processed.
363: * This is necessary to show that the algorithm terminates.
364: *
365: * Cannot test the state numbers here because in DFA.addState we need
366: * to know if any other state exists that has this exact set of NFA
367: * configurations. The DFAState state number is irrelevant.
368: */
369: public boolean equals(Object o) {
370: DFAState other = (DFAState) o;
371: if (o == null) {
372: return false;
373: }
374: if (this .hashCode() != other.hashCode()) {
375: return false;
376: }
377: // if not same number of NFA configuraitons, cannot be same state
378: if (this .nfaConfigurations.size() != other.nfaConfigurations
379: .size()) {
380: return false;
381: }
382:
383: // compare set of NFA configurations in this set with other
384: Iterator iter = this .nfaConfigurations.iterator();
385: while (iter.hasNext()) {
386: NFAConfiguration myConfig = (NFAConfiguration) iter.next();
387: if (!other.nfaConfigurations.contains(myConfig)) {
388: return false;
389: }
390: }
391: return true;
392: }
393:
394: /** Walk each configuration and if they are all the same alt, return
395: * that alt else return NFA.INVALID_ALT_NUMBER. Ignore resolved
396: * configurations, but don't ignore resolveWithPredicate configs
397: * because this state should not be an accept state. We need to add
398: * this to the work list and then have semantic predicate edges
399: * emanating from it.
400: */
401: public int getUniquelyPredictedAlt() {
402: if (cachedUniquelyPredicatedAlt != PREDICTED_ALT_UNSET) {
403: return cachedUniquelyPredicatedAlt;
404: }
405: int alt = NFA.INVALID_ALT_NUMBER;
406: Iterator iter = nfaConfigurations.iterator();
407: NFAConfiguration configuration;
408: while (iter.hasNext()) {
409: configuration = (NFAConfiguration) iter.next();
410: // ignore anything we resolved; predicates will still result
411: // in transitions out of this state, so must count those
412: // configurations; i.e., don't ignore resolveWithPredicate configs
413: if (configuration.resolved) {
414: continue;
415: }
416: if (alt == NFA.INVALID_ALT_NUMBER) {
417: alt = configuration.alt; // found first nonresolved alt
418: } else if (configuration.alt != alt) {
419: return NFA.INVALID_ALT_NUMBER;
420: }
421: }
422: this .cachedUniquelyPredicatedAlt = alt;
423: return alt;
424: }
425:
426: /** Return the uniquely mentioned alt from the NFA configurations;
427: * Ignore the resolved bit etc... Return INVALID_ALT_NUMBER
428: * if there is more than one alt mentioned.
429: */
430: public int getUniqueAlt() {
431: int alt = NFA.INVALID_ALT_NUMBER;
432: Iterator iter = nfaConfigurations.iterator();
433: NFAConfiguration configuration;
434: while (iter.hasNext()) {
435: configuration = (NFAConfiguration) iter.next();
436: if (alt == NFA.INVALID_ALT_NUMBER) {
437: alt = configuration.alt; // found first alt
438: } else if (configuration.alt != alt) {
439: return NFA.INVALID_ALT_NUMBER;
440: }
441: }
442: return alt;
443: }
444:
445: /** When more than one alternative can match the same input, the first
446: * alternative is chosen to resolve the conflict. The other alts
447: * are "turned off" by setting the "resolved" flag in the NFA
448: * configurations. Return the set of disabled alternatives. For
449: *
450: * a : A | A | A ;
451: *
452: * this method returns {2,3} as disabled. This does not mean that
453: * the alternative is totally unreachable, it just means that for this
454: * DFA state, that alt is disabled. There may be other accept states
455: * for that alt.
456: */
457: public Set getDisabledAlternatives() {
458: Set disabled = new LinkedHashSet();
459: Iterator iter = nfaConfigurations.iterator();
460: NFAConfiguration configuration;
461: while (iter.hasNext()) {
462: configuration = (NFAConfiguration) iter.next();
463: if (configuration.resolved) {
464: disabled.add(Utils.integer(configuration.alt));
465: }
466: }
467: return disabled;
468: }
469:
470: /**
471: public int getNumberOfEOTNFAStates() {
472: int n = 0;
473: Iterator iter = nfaConfigurations.iterator();
474: NFAConfiguration configuration;
475: while (iter.hasNext()) {
476: configuration = (NFAConfiguration) iter.next();
477: NFAState s = dfa.nfa.getState(configuration.state);
478: if ( s.isEOTState() ) {
479: n++;
480: }
481: }
482: return n;
483: }
484: */
485:
486: protected Set getNonDeterministicAlts() {
487: int user_k = dfa.getUserMaxLookahead();
488: if (user_k > 0 && user_k == k) {
489: // if fixed lookahead, then more than 1 alt is a nondeterminism
490: // if we have hit the max lookahead
491: return getAltSet();
492: } else if (abortedDueToMultipleRecursiveAlts
493: || abortedDueToRecursionOverflow) {
494: // if we had to abort for non-LL(*) state assume all alts are a problem
495: return getAltSet();
496: } else {
497: return getConflictingAlts();
498: }
499: }
500:
501: /** Walk each NFA configuration in this DFA state looking for a conflict
502: * where (s|i|ctx) and (s|j|ctx) exist, indicating that state s with
503: * context conflicting ctx predicts alts i and j. Return an Integer set
504: * of the alternative numbers that conflict. Two contexts conflict if
505: * they are equal or one is a stack suffix of the other or one is
506: * the empty context.
507: *
508: * Use a hash table to record the lists of configs for each state
509: * as they are encountered. We need only consider states for which
510: * there is more than one configuration. The configurations' predicted
511: * alt must be different or must have different contexts to avoid a
512: * conflict.
513: *
514: * Don't report conflicts for DFA states that have conflicting Tokens
515: * rule NFA states; they will be resolved in favor of the first rule.
516: */
517: protected Set getConflictingAlts() {
518: // TODO this is called multiple times: cache result?
519: //System.out.println("getNondetAlts for DFA state "+stateNumber);
520: Set nondeterministicAlts = new HashSet();
521:
522: // If only 1 NFA conf then no way it can be nondeterministic;
523: // save the overhead. There are many o-a->o NFA transitions
524: // and so we save a hash map and iterator creation for each
525: // state.
526: if (nfaConfigurations.size() <= 1) {
527: return null;
528: }
529:
530: // First get a list of configurations for each state.
531: // Most of the time, each state will have one associated configuration
532: Iterator iter = nfaConfigurations.iterator();
533: Map stateToConfigListMap = new HashMap();
534: NFAConfiguration configuration;
535: while (iter.hasNext()) {
536: configuration = (NFAConfiguration) iter.next();
537: Integer stateI = Utils.integer(configuration.state);
538: List prevConfigs = (List) stateToConfigListMap.get(stateI);
539: if (prevConfigs == null) {
540: prevConfigs = new ArrayList();
541: stateToConfigListMap.put(stateI, prevConfigs);
542: }
543: prevConfigs.add(configuration);
544: }
545:
546: // potential conflicts are states with > 1 configuration and diff alts
547: Set states = stateToConfigListMap.keySet();
548: int numPotentialConflicts = 0;
549: for (Iterator it = states.iterator(); it.hasNext();) {
550: Integer stateI = (Integer) it.next();
551: boolean this StateHasPotentialProblem = false;
552: List configsForState = (List) stateToConfigListMap
553: .get(stateI);
554: int alt = 0;
555: for (int i = 0; i < configsForState.size()
556: && configsForState.size() > 1; i++) {
557: NFAConfiguration c = (NFAConfiguration) configsForState
558: .get(i);
559: if (alt == 0) {
560: alt = c.alt;
561: } else if (c.alt != alt) {
562: /*
563: System.out.println("potential conflict in state "+stateI+
564: " configs: "+configsForState);
565: */
566: // 11/28/2005: don't report closures that pinch back
567: // together in Tokens rule. We want to silently resolve
568: // to the first token definition ala lex/flex by ignoring
569: // these conflicts.
570: if (dfa.nfa.grammar.type != Grammar.LEXER
571: || !dfa.decisionNFAStartState.enclosingRule
572: .equals(Grammar.ARTIFICIAL_TOKENS_RULENAME)) {
573: numPotentialConflicts++;
574: this StateHasPotentialProblem = true;
575: }
576: }
577: }
578: if (!this StateHasPotentialProblem) {
579: // remove NFA state's configurations from
580: // further checking; no issues with it
581: // (can't remove as it's concurrent modification; set to null)
582: stateToConfigListMap.put(stateI, null);
583: }
584: }
585:
586: // a fast check for potential issues; most states have none
587: if (numPotentialConflicts == 0) {
588: return null;
589: }
590:
591: // we have a potential problem, so now go through config lists again
592: // looking for different alts (only states with potential issues
593: // are left in the states set). Now we will check context.
594: // For example, the list of configs for NFA state 3 in some DFA
595: // state might be:
596: // [3|2|[28 18 $], 3|1|[28 $], 3|1, 3|2]
597: // I want to create a map from context to alts looking for overlap:
598: // [28 18 $] -> 2
599: // [28 $] -> 1
600: // [$] -> 1,2
601: // Indeed a conflict exists as same state 3, same context [$], predicts
602: // alts 1 and 2.
603: // walk each state with potential conflicting configurations
604: for (Iterator it = states.iterator(); it.hasNext();) {
605: Integer stateI = (Integer) it.next();
606: List configsForState = (List) stateToConfigListMap
607: .get(stateI);
608: // compare each configuration pair s, t to ensure:
609: // s.ctx different than t.ctx if s.alt != t.alt
610: for (int i = 0; configsForState != null
611: && i < configsForState.size(); i++) {
612: NFAConfiguration s = (NFAConfiguration) configsForState
613: .get(i);
614: for (int j = i + 1; j < configsForState.size(); j++) {
615: NFAConfiguration t = (NFAConfiguration) configsForState
616: .get(j);
617: // conflicts means s.ctx==t.ctx or s.ctx is a stack
618: // suffix of t.ctx or vice versa (if alts differ).
619: // Also a conflict if s.ctx or t.ctx is empty
620: if (s.alt != t.alt
621: && s.context.conflictsWith(t.context)) {
622: nondeterministicAlts.add(Utils.integer(s.alt));
623: nondeterministicAlts.add(Utils.integer(t.alt));
624: }
625: }
626: }
627: }
628:
629: if (nondeterministicAlts.size() == 0) {
630: return null;
631: }
632: return nondeterministicAlts;
633: }
634:
635: /** Get the set of all alts mentioned by all NFA configurations in this
636: * DFA state.
637: */
638: public Set getAltSet() {
639: Set alts = new HashSet();
640: Iterator iter = nfaConfigurations.iterator();
641: NFAConfiguration configuration;
642: while (iter.hasNext()) {
643: configuration = (NFAConfiguration) iter.next();
644: alts.add(Utils.integer(configuration.alt));
645: }
646: if (alts.size() == 0) {
647: return null;
648: }
649: return alts;
650: }
651:
652: /** Get the set of all states mentioned by all NFA configurations in this
653: * DFA state associated with alt.
654: */
655: public Set getNFAStatesForAlt(int alt) {
656: Set alts = new HashSet();
657: Iterator iter = nfaConfigurations.iterator();
658: NFAConfiguration configuration;
659: while (iter.hasNext()) {
660: configuration = (NFAConfiguration) iter.next();
661: if (configuration.alt == alt) {
662: alts.add(Utils.integer(configuration.state));
663: }
664: }
665: return alts;
666: }
667:
668: /** For gated productions, we need a list of all predicates for the
669: * target of an edge so we can gate the edge based upon the predicates
670: * associated with taking that path (if any).
671: *
672: * experimental 11/29/2005
673: *
674: public Set getGatedPredicatesInNFAConfigurations() {
675: Set preds = new HashSet();
676: Iterator iter = nfaConfigurations.iterator();
677: NFAConfiguration configuration;
678: while (iter.hasNext()) {
679: configuration = (NFAConfiguration) iter.next();
680: if ( configuration.semanticContext.isGated() ) {
681: preds.add(configuration.semanticContext);
682: }
683: }
684: if ( preds.size()==0 ) {
685: return null;
686: }
687: return preds;
688: }
689: */
690:
691: public Set getSyntacticPredicatesInNFAConfigurations() {
692: Set synpreds = new HashSet();
693: Iterator iter = nfaConfigurations.iterator();
694: NFAConfiguration configuration;
695: while (iter.hasNext()) {
696: configuration = (NFAConfiguration) iter.next();
697: SemanticContext gatedPredExpr = configuration.semanticContext
698: .getGatedPredicateContext();
699: // if this is a manual syn pred (gated and syn pred), add
700: if (gatedPredExpr != null
701: && configuration.semanticContext
702: .isSyntacticPredicate()) {
703: synpreds.add(configuration.semanticContext);
704: }
705: }
706: if (synpreds.size() == 0) {
707: return null;
708: }
709: return synpreds;
710: }
711:
712: /** For gated productions, we need an OR'd list of all predicates for the
713: * target of an edge so we can gate the edge based upon the predicates
714: * associated with taking that path (if any).
715: *
716: * For syntactic predicates, we only want to generate predicate
717: * evaluations as it transitions to an accept state; waste to
718: * do it earlier. So, only add gated preds derived from manually-
719: * specified syntactic predicates if this is an accept state.
720: *
721: * Also, since configurations w/o gated predicates are like true
722: * gated predicates, finding a configuration whose alt has no gated
723: * predicate implies we should evaluate the predicate to true. This
724: * means the whole edge has to be ungated. Consider:
725: *
726: * X : ('a' | {p}?=> 'a')
727: * | 'a' 'b'
728: * ;
729: *
730: * Here, you 'a' gets you from s0 to s1 but you can't test p because
731: * plain 'a' is ok. It's also ok for starting alt 2. Hence, you can't
732: * test p. Even on the edge going to accept state for alt 1 of X, you
733: * can't test p. You can get to the same place with and w/o the context.
734: * Therefore, it is never ok to test p in this situation.
735: *
736: * TODO: cache this as it's called a lot; or at least set bit if >1 present in state
737: */
738: public SemanticContext getGatedPredicatesInNFAConfigurations() {
739: Iterator iter = nfaConfigurations.iterator();
740: SemanticContext unionOfPredicatesFromAllAlts = null;
741: NFAConfiguration configuration;
742: while (iter.hasNext()) {
743: configuration = (NFAConfiguration) iter.next();
744: SemanticContext gatedPredExpr = configuration.semanticContext
745: .getGatedPredicateContext();
746: if (gatedPredExpr == null) {
747: // if we ever find a configuration w/o a gated predicate
748: // (even if it's a nongated predicate), we cannot gate
749: // the indident edges.
750: return null;
751: } else if (acceptState
752: || !configuration.semanticContext
753: .isSyntacticPredicate()) {
754: // at this point we have a gated predicate and, due to elseif,
755: // we know it's an accept and not a syn pred. In this case,
756: // it's safe to add the gated predicate to the union. We
757: // only want to add syn preds if it's an accept state. Other
758: // gated preds can be used with edges leading to accept states.
759: if (unionOfPredicatesFromAllAlts == null) {
760: unionOfPredicatesFromAllAlts = gatedPredExpr;
761: } else {
762: unionOfPredicatesFromAllAlts = SemanticContext
763: .or(unionOfPredicatesFromAllAlts,
764: gatedPredExpr);
765: }
766: }
767: }
768: if (unionOfPredicatesFromAllAlts instanceof SemanticContext.TruePredicate) {
769: return null;
770: }
771: return unionOfPredicatesFromAllAlts;
772: }
773:
774: /** Is an accept state reachable from this state? */
775: public int getAcceptStateReachable() {
776: return acceptStateReachable;
777: }
778:
779: public void setAcceptStateReachable(int acceptStateReachable) {
780: this .acceptStateReachable = acceptStateReachable;
781: }
782:
783: public boolean isResolvedWithPredicates() {
784: return resolvedWithPredicates;
785: }
786:
787: /** Print all NFA states plus what alts they predict */
788: public String toString() {
789: StringBuffer buf = new StringBuffer();
790: buf.append(stateNumber + ":{");
791: Iterator iter = nfaConfigurations.iterator();
792: int i = 1;
793: while (iter.hasNext()) {
794: NFAConfiguration configuration = (NFAConfiguration) iter
795: .next();
796: if (i > 1) {
797: buf.append(", ");
798: }
799: buf.append(configuration);
800: i++;
801: }
802: buf.append("}");
803: return buf.toString();
804: }
805:
806: public int getLookaheadDepth() {
807: return k;
808: }
809:
810: public void setLookaheadDepth(int k) {
811: this .k = k;
812: if (k > dfa.max_k) { // track max k for entire DFA
813: dfa.max_k = k;
814: }
815: }
816:
817: }
|