Source Code Cross Referenced for DecisionProbe.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.tool.ErrorManager;
031:        import org.antlr.tool.Grammar;
032:        import org.antlr.tool.GrammarAST;
033:        import org.antlr.tool.ANTLRParser;
034:        import org.antlr.misc.Utils;
035:
036:        import java.util.*;
037:
038:        /** Collection of information about what is wrong with a decision as
039:         *  discovered while building the DFA predictor.
040:         *
041:         *  The information is collected during NFA->DFA conversion and, while
042:         *  some of this is available elsewhere, it is nice to have it all tracked
043:         *  in one spot so a great error message can be easily had.  I also like
044:         *  the fact that this object tracks it all for later perusing to make an
045:         *  excellent error message instead of lots of imprecise on-the-fly warnings
046:         *  (during conversion).
047:         *
048:         *  A decision normally only has one problem; e.g., some input sequence
049:         *  can be matched by multiple alternatives.  Unfortunately, some decisions
050:         *  such as
051:         *
052:         *  a : ( A | B ) | ( A | B ) | A ;
053:         *
054:         *  have multiple problems.  So in general, you should approach a decision
055:         *  as having multiple flaws each one uniquely identified by a DFAState.
056:         *  For example, statesWithSyntacticallyAmbiguousAltsSet tracks the set of
057:         *  all DFAStates where ANTLR has discovered a problem.  Recall that a decision
058:         *  is represented internall with a DFA comprised of multiple states, each of
059:         *  which could potentially have problems.
060:         *
061:         *  Because of this, you need to iterate over this list of DFA states.  You'll
062:         *  note that most of the informational methods like
063:         *  getSampleNonDeterministicInputSequence() require a DFAState.  This state
064:         *  will be one of the iterated states from stateToSyntacticallyAmbiguousAltsSet.
065:         *
066:         *  This class is not thread safe due to shared use of visited maps etc...
067:         *  Only one thread should really need to access one DecisionProbe anyway.
068:         */
069:        public class DecisionProbe {
070:            public DFA dfa;
071:
072:            /** Track all DFA states with nondeterministic alternatives.
073:             *  By reaching the same DFA state, a path through the NFA for some input
074:             *  is able to reach the same NFA state by starting at more than one
075:             *  alternative's left edge.  Though, later, we may find that predicates
076:             *  resolve the issue, but track info anyway.
077:             *  Set<DFAState>.  Note that from the DFA state, you can ask for
078:             *  which alts are nondeterministic.
079:             */
080:            protected Set statesWithSyntacticallyAmbiguousAltsSet = new HashSet();
081:
082:            /** Track just like stateToSyntacticallyAmbiguousAltsMap, but only
083:             *  for nondeterminisms that arise in the Tokens rule such as keyword vs
084:             *  ID rule.  The state maps to the list of Tokens rule alts that are
085:             *  in conflict.
086:             *  Map<DFAState, Set<int>>
087:             */
088:            protected Map stateToSyntacticallyAmbiguousTokensRuleAltsMap = new HashMap();
089:
090:            /** Was a syntactic ambiguity resolved with predicates?  Any DFA
091:             *  state that predicts more than one alternative, must be resolved
092:             *  with predicates or it should be reported to the user.
093:             *  Set<DFAState>
094:             */
095:            protected Set statesResolvedWithSemanticPredicatesSet = new HashSet();
096:
097:            /** Track the predicates for each alt per DFA state;
098:             *  more than one DFA state might have syntactically ambig alt prediction.
099:             *  This is Map<DFAState, Map<int,SemanticContext>>; that is, it
100:             *  maps DFA state to another map, mapping alt number to a
101:             *  SemanticContext (pred(s) to execute to resolve syntactic ambiguity).
102:             */
103:            protected Map stateToAltSetWithSemanticPredicatesMap = new HashMap();
104:
105:            /** Map<DFAState,List<int>> Tracks alts insufficiently covered.
106:             *  For example, p1||true gets reduced to true and so leaves
107:             *  whole alt uncovered.  This maps DFA state to the set of alts
108:             */
109:            protected Map stateToIncompletelyCoveredAltsMap = new HashMap();
110:
111:            /** The set of states w/o emanating edges and w/o resolving sem preds. */
112:            protected Set danglingStates = new HashSet();
113:
114:            /** The overall list of alts within the decision that have at least one
115:             *  conflicting input sequence.
116:             */
117:            protected Set altsWithProblem = new HashSet();
118:
119:            /** If decision with > 1 alt has recursion in > 1 alt, it's nonregular
120:             *  lookahead.  The decision cannot be made with a DFA.
121:             *  the alts are stored in altsWithProblem.
122:             */
123:            protected boolean nonLLStarDecision = false;
124:
125:            /** Recursion is limited to a particular depth.  If that limit is exceeded
126:             *  the proposed new NFAConfiguration is recorded for the associated DFA state.
127:             *  Map<Integer DFA state number,List<NFAConfiguration>>.
128:             */
129:            protected Map stateToRecursiveOverflowConfigurationsMap = new HashMap();
130:
131:            /** Left recursion discovered.  The proposed new NFAConfiguration
132:             *  is recorded for the associated DFA state.
133:             *  Map<DFAState,List<NFAConfiguration>>.
134:             */
135:            protected Map stateToLeftRecursiveConfigurationsMap = new HashMap();
136:
137:            /** Did ANTLR have to terminate early on the analysis of this decision? */
138:            protected boolean terminated = false;
139:
140:            /** Used to find paths through syntactically ambiguous DFA. */
141:            protected Map stateReachable;
142:            public static final Integer REACHABLE_BUSY = Utils.integer(-1);
143:            public static final Integer REACHABLE_NO = Utils.integer(0);
144:            public static final Integer REACHABLE_YES = Utils.integer(1);
145:
146:            /** Used while finding a path through an NFA whose edge labels match
147:             *  an input sequence.  Tracks the input position
148:             *  we were at the last time at this node.  If same input position, then
149:             *  we'd have reached same state without consuming input...probably an
150:             *  infinite loop.  Stop.  Set<String>.  The strings look like
151:             *  stateNumber_labelIndex.
152:             */
153:            protected Set statesVisitedAtInputDepth;
154:
155:            protected Set statesVisitedDuringSampleSequence;
156:
157:            public static boolean verbose = false;
158:
159:            public DecisionProbe(DFA dfa) {
160:                this .dfa = dfa;
161:            }
162:
163:            // I N F O R M A T I O N  A B O U T  D E C I S I O N
164:
165:            /** Return a string like "3:22: ( A {;} | B )" that describes this
166:             *  decision.
167:             */
168:            public String getDescription() {
169:                return dfa.getNFADecisionStartState().getDescription();
170:            }
171:
172:            public boolean isReduced() {
173:                return dfa.isReduced();
174:            }
175:
176:            public boolean isCyclic() {
177:                return dfa.isCyclic();
178:            }
179:
180:            /** If no states are dead-ends, no alts are unreachable, there are
181:             *  no nondeterminisms unresolved by syn preds, all is ok with decision.
182:             */
183:            public boolean isDeterministic() {
184:                if (danglingStates.size() == 0
185:                        && statesWithSyntacticallyAmbiguousAltsSet.size() == 0
186:                        && dfa.getUnreachableAlts().size() == 0) {
187:                    return true;
188:                }
189:
190:                if (statesWithSyntacticallyAmbiguousAltsSet.size() > 0) {
191:                    Iterator it = statesWithSyntacticallyAmbiguousAltsSet
192:                            .iterator();
193:                    while (it.hasNext()) {
194:                        DFAState d = (DFAState) it.next();
195:                        if (!statesResolvedWithSemanticPredicatesSet
196:                                .contains(d)) {
197:                            return false;
198:                        }
199:                    }
200:                    // no syntactically ambig alts were left unresolved by predicates
201:                    return true;
202:                }
203:                return false;
204:            }
205:
206:            /** Did the analysis complete it's work? */
207:            public boolean analysisAborted() {
208:                return terminated;
209:            }
210:
211:            public boolean analysisOverflowed() {
212:                return stateToRecursiveOverflowConfigurationsMap.size() > 0;
213:            }
214:
215:            public boolean isNonLLStarDecision() {
216:                return nonLLStarDecision;
217:            }
218:
219:            /** How many states does the DFA predictor have? */
220:            public int getNumberOfStates() {
221:                return dfa.getNumberOfStates();
222:            }
223:
224:            /** Get a list of all unreachable alternatives for this decision.  There
225:             *  may be multiple alternatives with ambiguous input sequences, but this
226:             *  is the overall list of unreachable alternatives (either due to
227:             *  conflict resolution or alts w/o accept states).
228:             */
229:            public List getUnreachableAlts() {
230:                return dfa.getUnreachableAlts();
231:            }
232:
233:            /** return set of states w/o emanating edges and w/o resolving sem preds.
234:             *  These states come about because the analysis algorithm had to
235:             *  terminate early to avoid infinite recursion for example (due to
236:             *  left recursion perhaps).
237:             */
238:            public Set getDanglingStates() {
239:                return danglingStates;
240:            }
241:
242:            public Set getNonDeterministicAlts() {
243:                return altsWithProblem;
244:            }
245:
246:            /** Return the sorted list of alts that conflict within a single state.
247:             *  Note that predicates may resolve the conflict.
248:             */
249:            public List getNonDeterministicAltsForState(DFAState targetState) {
250:                Set nondetAlts = targetState.getNonDeterministicAlts();
251:                if (nondetAlts == null) {
252:                    return null;
253:                }
254:                List sorted = new LinkedList();
255:                sorted.addAll(nondetAlts);
256:                Collections.sort(sorted); // make sure it's 1, 2, ...
257:                return sorted;
258:            }
259:
260:            /** Return all DFA states in this DFA that have NFA configurations that
261:             *  conflict.  You must report a problem for each state in this set
262:             *  because each state represents a different input sequence.
263:             */
264:            public Set getDFAStatesWithSyntacticallyAmbiguousAlts() {
265:                return statesWithSyntacticallyAmbiguousAltsSet;
266:            }
267:
268:            /** Which alts were specifically turned off to resolve nondeterminisms?
269:             *  This is different than the unreachable alts.  Disabled doesn't mean that
270:             *  the alternative is totally unreachable necessarily, it just means
271:             *  that for this DFA state, that alt is disabled.  There may be other
272:             *  accept states for that alt that make an alt reachable.
273:             */
274:            public Set getDisabledAlternatives(DFAState d) {
275:                return d.getDisabledAlternatives();
276:            }
277:
278:            /** If a recursion overflow is resolve with predicates, then we need
279:             *  to shut off the warning that would be generated.
280:             */
281:            public void removeRecursiveOverflowState(DFAState d) {
282:                Integer stateI = Utils.integer(d.stateNumber);
283:                stateToRecursiveOverflowConfigurationsMap.remove(stateI);
284:            }
285:
286:            /*
287:            public boolean dfaStateHasRecursionOverflow(DFAState d) {
288:            	Integer stateI = Utils.integer(d.stateNumber);
289:            	return stateToRecursiveOverflowConfigurationsMap.get(stateI)!=null;
290:            }
291:             */
292:
293:            /** Return a List<Label> indicating an input sequence that can be matched
294:             *  from the start state of the DFA to the targetState (which is known
295:             *  to have a problem).
296:             */
297:            public List getSampleNonDeterministicInputSequence(
298:                    DFAState targetState) {
299:                Set dfaStates = getDFAPathStatesToTarget(targetState);
300:                statesVisitedDuringSampleSequence = new HashSet();
301:                List labels = new ArrayList(); // may access ith element; use array
302:                getSampleInputSequenceUsingStateSet(dfa.startState,
303:                        targetState, dfaStates, labels);
304:                return labels;
305:            }
306:
307:            /** Given List<Label>, return a String with a useful representation
308:             *  of the associated input string.  One could show something different
309:             *  for lexers and parsers, for example.
310:             */
311:            public String getInputSequenceDisplay(List labels) {
312:                Grammar g = dfa.nfa.grammar;
313:                StringBuffer buf = new StringBuffer();
314:                for (Iterator it = labels.iterator(); it.hasNext();) {
315:                    Label label = (Label) it.next();
316:                    buf.append(label.toString(g));
317:                    if (it.hasNext() && g.type != Grammar.LEXER) {
318:                        buf.append(' ');
319:                    }
320:                }
321:                return buf.toString();
322:            }
323:
324:            /** Given an alternative associated with a nondeterministic DFA state,
325:             *  find the path of NFA states associated with the labels sequence.
326:             *  Useful tracing where in the NFA, a single input sequence can be
327:             *  matched.  For different alts, you should get different NFA paths.
328:             *
329:             *  The first NFA state for all NFA paths will be the same: the starting
330:             *  NFA state of the first nondeterministic alt.  Imagine (A|B|A|A):
331:             *
332:             * 	5->9-A->o
333:             *  |
334:             *  6->10-B->o
335:             *  |
336:             *  7->11-A->o
337:             *  |
338:             *  8->12-A->o
339:             *
340:             *  There are 3 nondeterministic alts.  The paths should be:
341:             *  5 9 ...
342:             *  5 6 7 11 ...
343:             *  5 6 7 8 12 ...
344:             *
345:             *  The NFA path matching the sample input sequence (labels) is computed
346:             *  using states 9, 11, and 12 rather than 5, 7, 8 because state 5, for
347:             *  example can get to all ambig paths.  Must isolate for each alt (hence,
348:             *  the extra state beginning each alt in my NFA structures).  Here,
349:             *  firstAlt=1.
350:             */
351:            public List getNFAPathStatesForAlt(int firstAlt, int alt,
352:                    List labels) {
353:                NFAState nfaStart = dfa.getNFADecisionStartState();
354:                List path = new LinkedList();
355:                // first add all NFA states leading up to altStart state
356:                for (int a = firstAlt; a <= alt; a++) {
357:                    NFAState s = dfa.nfa.grammar.getNFAStateForAltOfDecision(
358:                            nfaStart, a);
359:                    path.add(s);
360:                }
361:
362:                // add first state of actual alt
363:                NFAState altStart = dfa.nfa.grammar
364:                        .getNFAStateForAltOfDecision(nfaStart, alt);
365:                NFAState isolatedAltStart = (NFAState) altStart.transition(0).target;
366:                path.add(isolatedAltStart);
367:
368:                // add the actual path now
369:                statesVisitedAtInputDepth = new HashSet();
370:                getNFAPath(isolatedAltStart, 0, labels, path);
371:                return path;
372:            }
373:
374:            /** Each state in the DFA represents a different input sequence for an
375:             *  alt of the decision.  Given a DFA state, what is the semantic
376:             *  predicate context for a particular alt.
377:             */
378:            public SemanticContext getSemanticContextForAlt(DFAState d, int alt) {
379:                Map altToPredMap = (Map) stateToAltSetWithSemanticPredicatesMap
380:                        .get(d);
381:                if (altToPredMap == null) {
382:                    return null;
383:                }
384:                return (SemanticContext) altToPredMap.get(Utils.integer(alt));
385:            }
386:
387:            public Set getNondeterministicStatesResolvedWithSemanticPredicate() {
388:                return statesResolvedWithSemanticPredicatesSet;
389:            }
390:
391:            /** Return a list of alts whose predicate context was insufficient to
392:             *  resolve a nondeterminism for state d.
393:             */
394:            public List getIncompletelyCoveredAlts(DFAState d) {
395:                return (List) stateToIncompletelyCoveredAltsMap.get(d);
396:            }
397:
398:            public void issueWarnings() {
399:                // NONREGULAR DUE TO RECURSION > 1 ALTS
400:                // Issue this before aborted analysis, which might also occur
401:                // if we take too long to terminate
402:                if (nonLLStarDecision && !dfa.getAutoBacktrackMode()) {
403:                    ErrorManager.nonLLStarDecision(this );
404:                }
405:
406:                if (analysisAborted()) {
407:                    // only report early termination errors if !backtracking
408:                    if (!dfa.getAutoBacktrackMode()) {
409:                        ErrorManager.analysisAborted(this );
410:                    }
411:                    // now just return...if we bailed out, don't spew other messages
412:                    return;
413:                }
414:
415:                issueRecursionWarnings();
416:
417:                // generate a separate message for each problem state in DFA
418:                Set resolvedStates = getNondeterministicStatesResolvedWithSemanticPredicate();
419:                Set problemStates = getDFAStatesWithSyntacticallyAmbiguousAlts();
420:                if (problemStates.size() > 0) {
421:                    Iterator it = problemStates.iterator();
422:                    while (it.hasNext()
423:                            && !dfa.nfa.grammar
424:                                    .NFAToDFAConversionExternallyAborted()) {
425:                        DFAState d = (DFAState) it.next();
426:                        // don't report problem if resolved
427:                        if (resolvedStates == null
428:                                || !resolvedStates.contains(d)) {
429:                            // first strip last alt from disableAlts if it's wildcard
430:                            // then don't print error if no more disable alts
431:                            Set disabledAlts = getDisabledAlternatives(d);
432:                            stripWildCardAlts(disabledAlts);
433:                            if (disabledAlts.size() > 0) {
434:                                ErrorManager.nondeterminism(this , d);
435:                            }
436:                        }
437:                        List insufficientAlts = getIncompletelyCoveredAlts(d);
438:                        if (insufficientAlts != null
439:                                && insufficientAlts.size() > 0) {
440:                            ErrorManager.insufficientPredicates(this ,
441:                                    insufficientAlts);
442:                        }
443:                    }
444:                }
445:
446:                Set danglingStates = getDanglingStates();
447:                if (danglingStates.size() > 0) {
448:                    //System.err.println("no emanating edges for states: "+danglingStates);
449:                    for (Iterator it = danglingStates.iterator(); it.hasNext();) {
450:                        DFAState d = (DFAState) it.next();
451:                        ErrorManager.danglingState(this , d);
452:                    }
453:                }
454:
455:                if (!nonLLStarDecision) {
456:                    List unreachableAlts = dfa.getUnreachableAlts();
457:                    if (unreachableAlts != null && unreachableAlts.size() > 0) {
458:                        ErrorManager.unreachableAlts(this , unreachableAlts);
459:                    }
460:                }
461:            }
462:
463:            /** Get the last disabled alt number and check in the grammar to see
464:             *  if that alt is a simple wildcard.  If so, treat like an else clause
465:             *  and don't emit the error.  Strip out the last alt if it's wildcard.
466:             */
467:            protected void stripWildCardAlts(Set disabledAlts) {
468:                List sortedDisableAlts = new ArrayList(disabledAlts);
469:                Collections.sort(sortedDisableAlts);
470:                Integer lastAlt = (Integer) sortedDisableAlts
471:                        .get(sortedDisableAlts.size() - 1);
472:                GrammarAST blockAST = dfa.nfa.grammar
473:                        .getDecisionBlockAST(dfa.decisionNumber);
474:                //System.out.println("block with error = "+blockAST.toStringTree());
475:                GrammarAST lastAltAST = null;
476:                if (blockAST.getChild(0).getType() == ANTLRParser.OPTIONS) {
477:                    // if options, skip first child: ( options { ( = greedy false ) )
478:                    lastAltAST = blockAST.getChild(lastAlt.intValue());
479:                } else {
480:                    lastAltAST = blockAST.getChild(lastAlt.intValue() - 1);
481:                }
482:                //System.out.println("last alt is "+lastAltAST.toStringTree());
483:                // if last alt looks like ( ALT . <end-of-alt> ) then wildcard
484:                // Avoid looking at optional blocks etc... that have last alt
485:                // as the EOB:
486:                // ( BLOCK ( ALT 'else' statement <end-of-alt> ) <end-of-block> )
487:                if (lastAltAST.getType() != ANTLRParser.EOB
488:                        && lastAltAST.getChild(0).getType() == ANTLRParser.WILDCARD
489:                        && lastAltAST.getChild(1).getType() == ANTLRParser.EOA) {
490:                    //System.out.println("wildcard");
491:                    disabledAlts.remove(lastAlt);
492:                }
493:            }
494:
495:            protected void issueRecursionWarnings() {
496:                // RECURSION OVERFLOW
497:                Set dfaStatesWithRecursionProblems = stateToRecursiveOverflowConfigurationsMap
498:                        .keySet();
499:                // now walk truly unique (unaliased) list of dfa states with inf recur
500:                // Goal: create a map from alt to map<target,List<callsites>>
501:                // Map<Map<String target, List<NFAState call sites>>
502:                Map altToTargetToCallSitesMap = new HashMap();
503:                // track a single problem DFA state for each alt
504:                Map altToDFAState = new HashMap();
505:                computeAltToProblemMaps(dfaStatesWithRecursionProblems,
506:                        stateToRecursiveOverflowConfigurationsMap,
507:                        altToTargetToCallSitesMap, // output param
508:                        altToDFAState); // output param
509:                //System.out.println("altToTargetToCallSitesMap="+altToTargetToCallSitesMap);
510:
511:                // walk each alt with recursion overflow problems and generate error
512:                Set alts = altToTargetToCallSitesMap.keySet();
513:                List sortedAlts = new ArrayList(alts);
514:                Collections.sort(sortedAlts);
515:                for (Iterator altsIt = sortedAlts.iterator(); altsIt.hasNext();) {
516:                    Integer altI = (Integer) altsIt.next();
517:                    Map targetToCallSiteMap = (Map) altToTargetToCallSitesMap
518:                            .get(altI);
519:                    Set targetRules = targetToCallSiteMap.keySet();
520:                    Collection callSiteStates = targetToCallSiteMap.values();
521:                    DFAState sampleBadState = (DFAState) altToDFAState
522:                            .get(altI);
523:                    ErrorManager.recursionOverflow(this , sampleBadState, altI
524:                            .intValue(), targetRules, callSiteStates);
525:                }
526:
527:                /* All  recursion determines now before analysis
528:                // LEFT RECURSION
529:                // TODO: hideous cut/paste of code; try to refactor
530:
531:                Set dfaStatesWithLeftRecursionProblems =
532:                	stateToLeftRecursiveConfigurationsMap.keySet();
533:                Set dfaStatesUnaliased =
534:                	getUnaliasedDFAStateSet(dfaStatesWithLeftRecursionProblems);
535:
536:                // now walk truly unique (unaliased) list of dfa states with inf recur
537:                // Goal: create a map from alt to map<target,List<callsites>>
538:                // Map<Map<String target, List<NFAState call sites>>
539:                altToTargetToCallSitesMap = new HashMap();
540:                // track a single problem DFA state for each alt
541:                altToDFAState = new HashMap();
542:                computeAltToProblemMaps(dfaStatesUnaliased,
543:                						stateToLeftRecursiveConfigurationsMap,
544:                						altToTargetToCallSitesMap, // output param
545:                						altToDFAState);            // output param
546:
547:                // walk each alt with recursion overflow problems and generate error
548:                alts = altToTargetToCallSitesMap.keySet();
549:                sortedAlts = new ArrayList(alts);
550:                Collections.sort(sortedAlts);
551:                for (Iterator altsIt = sortedAlts.iterator(); altsIt.hasNext();) {
552:                	Integer altI = (Integer) altsIt.next();
553:                	Map targetToCallSiteMap =
554:                		(Map)altToTargetToCallSitesMap.get(altI);
555:                	Set targetRules = targetToCallSiteMap.keySet();
556:                	Collection callSiteStates = targetToCallSiteMap.values();
557:                	ErrorManager.leftRecursion(this,
558:                							   altI.intValue(),
559:                							   targetRules,
560:                							   callSiteStates);
561:                }
562:                 */
563:            }
564:
565:            private void computeAltToProblemMaps(Set dfaStatesUnaliased,
566:                    Map configurationsMap, Map altToTargetToCallSitesMap,
567:                    Map altToDFAState) {
568:                for (Iterator it = dfaStatesUnaliased.iterator(); it.hasNext();) {
569:                    Integer stateI = (Integer) it.next();
570:                    // walk this DFA's config list
571:                    List configs = (List) configurationsMap.get(stateI);
572:                    for (int i = 0; i < configs.size(); i++) {
573:                        NFAConfiguration c = (NFAConfiguration) configs.get(i);
574:                        NFAState ruleInvocationState = dfa.nfa
575:                                .getState(c.state);
576:                        Transition transition0 = ruleInvocationState
577:                                .transition(0);
578:                        RuleClosureTransition ref = (RuleClosureTransition) transition0;
579:                        String targetRule = ((NFAState) ref.target)
580:                                .getEnclosingRule();
581:                        Integer altI = Utils.integer(c.alt);
582:                        Map targetToCallSiteMap = (Map) altToTargetToCallSitesMap
583:                                .get(altI);
584:                        if (targetToCallSiteMap == null) {
585:                            targetToCallSiteMap = new HashMap();
586:                            altToTargetToCallSitesMap.put(altI,
587:                                    targetToCallSiteMap);
588:                        }
589:                        Set callSites = (HashSet) targetToCallSiteMap
590:                                .get(targetRule);
591:                        if (callSites == null) {
592:                            callSites = new HashSet();
593:                            targetToCallSiteMap.put(targetRule, callSites);
594:                        }
595:                        callSites.add(ruleInvocationState);
596:                        // track one problem DFA state per alt
597:                        if (altToDFAState.get(altI) == null) {
598:                            DFAState sampleBadState = dfa.getState(stateI
599:                                    .intValue());
600:                            altToDFAState.put(altI, sampleBadState);
601:                        }
602:                    }
603:                }
604:            }
605:
606:            private Set getUnaliasedDFAStateSet(
607:                    Set dfaStatesWithRecursionProblems) {
608:                Set dfaStatesUnaliased = new HashSet();
609:                for (Iterator it = dfaStatesWithRecursionProblems.iterator(); it
610:                        .hasNext();) {
611:                    Integer stateI = (Integer) it.next();
612:                    DFAState d = dfa.getState(stateI.intValue());
613:                    dfaStatesUnaliased.add(Utils.integer(d.stateNumber));
614:                }
615:                return dfaStatesUnaliased;
616:            }
617:
618:            // T R A C K I N G  M E T H O D S
619:
620:            /** Report the fact that DFA state d is not a state resolved with
621:             *  predicates and yet it has no emanating edges.  Usually this
622:             *  is a result of the closure/reach operations being unable to proceed
623:             */
624:            public void reportDanglingState(DFAState d) {
625:                danglingStates.add(d);
626:            }
627:
628:            public void reportEarlyTermination() {
629:                terminated = true;
630:                dfa.nfa.grammar.setOfDFAWhoseConversionTerminatedEarly.add(dfa);
631:            }
632:
633:            /** Report that at least 2 alts have recursive constructs.  There is
634:             *  no way to build a DFA so we terminated.
635:             */
636:            public void reportNonLLStarDecision(DFA dfa) {
637:                //System.out.println("non-LL(*) DFA "+dfa.decisionNumber);
638:                nonLLStarDecision = true;
639:                altsWithProblem.addAll(dfa.recursiveAltSet.toList());
640:            }
641:
642:            public void reportRecursiveOverflow(DFAState d,
643:                    NFAConfiguration recursiveNFAConfiguration) {
644:                // track the state number rather than the state as d will change
645:                // out from underneath us; hash wouldn't return any value
646:                Integer stateI = Utils.integer(d.stateNumber);
647:                List configs = (List) stateToRecursiveOverflowConfigurationsMap
648:                        .get(stateI);
649:                if (configs == null) {
650:                    configs = new ArrayList();
651:                    configs.add(recursiveNFAConfiguration);
652:                    stateToRecursiveOverflowConfigurationsMap.put(stateI,
653:                            configs);
654:                } else {
655:                    configs.add(recursiveNFAConfiguration);
656:                }
657:            }
658:
659:            public void reportLeftRecursion(DFAState d,
660:                    NFAConfiguration leftRecursiveNFAConfiguration) {
661:                // track the state number rather than the state as d will change
662:                // out from underneath us; hash wouldn't return any value
663:                Integer stateI = Utils.integer(d.stateNumber);
664:                List configs = (List) stateToLeftRecursiveConfigurationsMap
665:                        .get(stateI);
666:                if (configs == null) {
667:                    configs = new ArrayList();
668:                    configs.add(leftRecursiveNFAConfiguration);
669:                    stateToLeftRecursiveConfigurationsMap.put(stateI, configs);
670:                } else {
671:                    configs.add(leftRecursiveNFAConfiguration);
672:                }
673:            }
674:
675:            public void reportNondeterminism(DFAState d,
676:                    Set nondeterministicAlts) {
677:                altsWithProblem.addAll(nondeterministicAlts); // track overall list
678:                statesWithSyntacticallyAmbiguousAltsSet.add(d);
679:                dfa.nfa.grammar.setOfNondeterministicDecisionNumbers.add(Utils
680:                        .integer(dfa.getDecisionNumber()));
681:            }
682:
683:            /** Currently the analysis reports issues between token definitions, but
684:             *  we don't print out warnings in favor of just picking the first token
685:             *  definition found in the grammar ala lex/flex.
686:             */
687:            public void reportLexerRuleNondeterminism(DFAState d,
688:                    Set nondeterministicAlts) {
689:                stateToSyntacticallyAmbiguousTokensRuleAltsMap.put(d,
690:                        nondeterministicAlts);
691:            }
692:
693:            public void reportNondeterminismResolvedWithSemanticPredicate(
694:                    DFAState d) {
695:                statesResolvedWithSemanticPredicatesSet.add(d);
696:                //System.out.println("resolved with pred: "+d);
697:                dfa.nfa.grammar.setOfNondeterministicDecisionNumbersResolvedWithPredicates
698:                        .add(Utils.integer(dfa.getDecisionNumber()));
699:            }
700:
701:            /** Report the list of predicates found for each alternative; copy
702:             *  the list because this set gets altered later by the method
703:             *  tryToResolveWithSemanticPredicates() while flagging NFA configurations
704:             *  in d as resolved.
705:             */
706:            public void reportAltPredicateContext(DFAState d,
707:                    Map altPredicateContext) {
708:                Map copy = new HashMap();
709:                copy.putAll(altPredicateContext);
710:                stateToAltSetWithSemanticPredicatesMap.put(d, copy);
711:            }
712:
713:            public void reportIncompletelyCoveredAlts(DFAState d, List alts) {
714:                stateToIncompletelyCoveredAltsMap.put(d, alts);
715:            }
716:
717:            // S U P P O R T
718:
719:            /** Given a start state and a target state, return true if start can reach
720:             *  target state.  Also, compute the set of DFA states
721:             *  that are on a path from start to target; return in states parameter.
722:             */
723:            protected boolean reachesState(DFAState startState,
724:                    DFAState targetState, Set states) {
725:                if (startState == targetState) {
726:                    states.add(targetState);
727:                    //System.out.println("found target DFA state "+targetState.getStateNumber());
728:                    stateReachable.put(startState, REACHABLE_YES);
729:                    return true;
730:                }
731:
732:                DFAState s = startState;
733:                // avoid infinite loops
734:                stateReachable.put(s, REACHABLE_BUSY);
735:
736:                // look for a path to targetState among transitions for this state
737:                // stop when you find the first one; I'm pretty sure there is
738:                // at most one path to any DFA state with conflicting predictions
739:                for (int i = 0; i < s.getNumberOfTransitions(); i++) {
740:                    Transition t = s.transition(i);
741:                    DFAState edgeTarget = (DFAState) t.target;
742:                    Integer targetStatus = (Integer) stateReachable
743:                            .get(edgeTarget);
744:                    if (targetStatus == REACHABLE_BUSY) { // avoid cycles; they say nothing
745:                        continue;
746:                    }
747:                    if (targetStatus == REACHABLE_YES) { // return success!
748:                        stateReachable.put(s, REACHABLE_YES);
749:                        return true;
750:                    }
751:                    if (targetStatus == REACHABLE_NO) { // try another transition
752:                        continue;
753:                    }
754:                    // if null, target must be REACHABLE_UNKNOWN (i.e., unvisited)
755:                    if (reachesState(edgeTarget, targetState, states)) {
756:                        states.add(s);
757:                        stateReachable.put(s, REACHABLE_YES);
758:                        return true;
759:                    }
760:                }
761:
762:                stateReachable.put(s, REACHABLE_NO);
763:                return false; // no path to targetState found.
764:            }
765:
766:            protected Set getDFAPathStatesToTarget(DFAState targetState) {
767:                Set dfaStates = new HashSet();
768:                stateReachable = new HashMap();
769:                boolean reaches = reachesState(dfa.startState, targetState,
770:                        dfaStates);
771:                return dfaStates;
772:            }
773:
774:            /** Given a set of DFA states, return a set of NFA states associated
775:             *  with alt collected from all DFA states.  If alt==0 then collect
776:             *  all NFA states regardless of alt.
777:            protected Set getNFAStatesFromDFAStatesForAlt(Set dfaStates, int alt) {
778:            	Set nfaStates = new LinkedHashSet();
779:            	for (Iterator it = dfaStates.iterator(); it.hasNext();) {
780:            		DFAState d = (DFAState) it.next();
781:            		Set configs = d.getNFAConfigurations();
782:            		for (Iterator configIter = configs.iterator(); configIter.hasNext();) {
783:            			NFAConfiguration c = (NFAConfiguration) configIter.next();
784:            			if ( alt==0 || c.alt==alt ) {
785:            				nfaStates.add(Utils.integer(c.state));
786:            			}
787:            		}
788:            	}
789:            	return nfaStates;
790:            }
791:             */
792:
793:            /** Given a start state and a final state, find a list of edge labels
794:             *  between the two ignoring epsilon.  Limit your scan to a set of states
795:             *  passed in.  This is used to show a sample input sequence that is
796:             *  nondeterministic with respect to this decision.  Return List<Label> as
797:             *  a parameter.  The incoming states set must be all states that lead
798:             *  from startState to targetState and no others so this algorithm doesn't
799:             *  take a path that eventually leads to a state other than targetState.
800:             *  Don't follow loops, leading to short (possibly shortest) path.
801:             */
802:            protected void getSampleInputSequenceUsingStateSet(
803:                    State startState, State targetState, Set states, List labels) {
804:                statesVisitedDuringSampleSequence.add(startState);
805:
806:                // pick the first edge in states as the one to traverse
807:                for (int i = 0; i < startState.getNumberOfTransitions(); i++) {
808:                    Transition t = startState.transition(i);
809:                    DFAState edgeTarget = (DFAState) t.target;
810:                    if (states.contains(edgeTarget)
811:                            && !statesVisitedDuringSampleSequence
812:                                    .contains(edgeTarget)) {
813:                        labels.add(t.label); // traverse edge and track label
814:                        if (edgeTarget != targetState) {
815:                            // get more labels if not at target
816:                            getSampleInputSequenceUsingStateSet(edgeTarget,
817:                                    targetState, states, labels);
818:                        }
819:                        // done with this DFA state as we've found a good path to target
820:                        return;
821:                    }
822:                }
823:                labels.add(new Label(Label.EPSILON)); // indicate no input found
824:                // this happens on a : {p1}? a | A ;
825:                //ErrorManager.error(ErrorManager.MSG_CANNOT_COMPUTE_SAMPLE_INPUT_SEQ);
826:            }
827:
828:            /** Given a sample input sequence, you usually would like to know the
829:             *  path taken through the NFA.  Return the list of NFA states visited
830:             *  while matching a list of labels.  This cannot use the usual
831:             *  interpreter, which does a deterministic walk.  We need to be able to
832:             *  take paths that are turned off during nondeterminism resolution. So,
833:             *  just do a depth-first walk traversing edges labeled with the current
834:             *  label.  Return true if a path was found emanating from state s.
835:             */
836:            protected boolean getNFAPath(NFAState s, // starting where?
837:                    int labelIndex, // 0..labels.size()-1
838:                    List labels, // input sequence
839:                    List path) // output list of NFA states
840:            {
841:                // track a visit to state s at input index labelIndex if not seen
842:                String this StateKey = getStateLabelIndexKey(s.stateNumber,
843:                        labelIndex);
844:                if (statesVisitedAtInputDepth.contains(this StateKey)) {
845:                    /*
846:                    System.out.println("### already visited "+s.stateNumber+" previously at index "+
847:                    			   labelIndex);
848:                     */
849:                    return false;
850:                }
851:                statesVisitedAtInputDepth.add(this StateKey);
852:
853:                /*
854:                System.out.println("enter state "+s.stateNumber+" visited states: "+
855:                				   statesVisitedAtInputDepth);
856:                 */
857:
858:                // pick the first edge whose target is in states and whose
859:                // label is labels[labelIndex]
860:                for (int i = 0; i < s.getNumberOfTransitions(); i++) {
861:                    Transition t = s.transition(i);
862:                    NFAState edgeTarget = (NFAState) t.target;
863:                    Label label = (Label) labels.get(labelIndex);
864:                    /*
865:                    System.out.println(s.stateNumber+"-"+
866:                    				   t.label.toString(dfa.nfa.grammar)+"->"+
867:                    				   edgeTarget.stateNumber+" =="+
868:                    				   label.toString(dfa.nfa.grammar)+"?");
869:                     */
870:                    if (t.label.isEpsilon()) {
871:                        // nondeterministically backtrack down epsilon edges
872:                        path.add(edgeTarget);
873:                        boolean found = getNFAPath(edgeTarget, labelIndex,
874:                                labels, path);
875:                        if (found) {
876:                            statesVisitedAtInputDepth.remove(this StateKey);
877:                            return true; // return to "calling" state
878:                        }
879:                        path.remove(path.size() - 1); // remove; didn't work out
880:                        continue; // look at the next edge
881:                    }
882:                    if (t.label.matches(label)) {
883:                        path.add(edgeTarget);
884:                        /*
885:                        System.out.println("found label "+
886:                        				   t.label.toString(dfa.nfa.grammar)+
887:                        				   " at state "+s.stateNumber+"; labelIndex="+labelIndex);
888:                         */
889:                        if (labelIndex == labels.size() - 1) {
890:                            // found last label; done!
891:                            statesVisitedAtInputDepth.remove(this StateKey);
892:                            return true;
893:                        }
894:                        // otherwise try to match remaining input
895:                        boolean found = getNFAPath(edgeTarget, labelIndex + 1,
896:                                labels, path);
897:                        if (found) {
898:                            statesVisitedAtInputDepth.remove(this StateKey);
899:                            return true;
900:                        }
901:                        /*
902:                        System.out.println("backtrack; path from "+s.stateNumber+"->"+
903:                        				   t.label.toString(dfa.nfa.grammar)+" didn't work");
904:                         */
905:                        path.remove(path.size() - 1); // remove; didn't work out
906:                        continue; // keep looking for a path for labels
907:                    }
908:                }
909:                //System.out.println("no epsilon or matching edge; removing "+thisStateKey);
910:                // no edge was found matching label; is ok, some state will have it
911:                statesVisitedAtInputDepth.remove(this StateKey);
912:                return false;
913:            }
914:
915:            protected String getStateLabelIndexKey(int s, int i) {
916:                StringBuffer buf = new StringBuffer();
917:                buf.append(s);
918:                buf.append('_');
919:                buf.append(i);
920:                return buf.toString();
921:            }
922:
923:            /** From an alt number associated with artificial Tokens rule, return
924:             *  the name of the token that is associated with that alt.
925:             */
926:            public String getTokenNameForTokensRuleAlt(int alt) {
927:                NFAState decisionState = dfa.getNFADecisionStartState();
928:                NFAState altState = dfa.nfa.grammar
929:                        .getNFAStateForAltOfDecision(decisionState, alt);
930:                NFAState decisionLeft = (NFAState) altState.transition(0).target;
931:                RuleClosureTransition ruleCallEdge = (RuleClosureTransition) decisionLeft
932:                        .transition(0);
933:                NFAState ruleStartState = (NFAState) ruleCallEdge.target;
934:                //System.out.println("alt = "+decisionLeft.getEnclosingRule());
935:                return ruleStartState.getEnclosingRule();
936:            }
937:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.