Source Code Cross Referenced for DFAState.java in  » Parser » antlr-3.0.1 » org » antlr » analysis » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Parser » antlr 3.0.1 » org.antlr.analysis 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.