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: }
|