org.antlr.analysis

Class NFAToDFAConverter

java.lang.Object

org.antlr.analysis.NFAToDFAConverter

public class NFAToDFAConverter
extends Object

Code that embodies the NFA conversion to DFA. A new object is needed per DFA (also required for thread safety if multiple conversions launched).

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	computingStartState
protected NFAContext[]	contextTrees While converting NFA, we must track states that reference other rule's NFAs so we know what to do at the end of a rule.
static boolean	debug
protected DFA	dfa We are converting which DFA?
static boolean	SINGLE_THREADED_NFA_CONVERSION Should ANTLR launch multiple threads to convert NFAs to DFAs? With a 2-CPU box, I note that it's about the same single or multithreaded.
protected List	work A list of DFA states we still need to process during NFA conversion

Constructor Summary

Constructors

Constructor and Description
NFAToDFAConverter(DFA dfa)

Method Summary

Methods

Modifier and Type	Method and Description
protected DFAState	addDFAStateToWorkList(DFAState d) Add a new DFA state to the DFA if not already present.
protected void	addPredicateTransitions(DFAState d) for each NFA config in d, look for "predicate required" sign set during nondeterminism resolution.
protected static int	addTransition(DFAState d, Label label, DFAState targetState, Map targetToLabelMap) Add a transition from state d to targetState with label in normal case.
void	closure(DFAState d) For all NFA states (configurations) merged in d, compute the epsilon closure; that is, find all NFA states reachable from the NFA states in d via purely epsilon transitions.
void	closure(NFAState p, int alt, NFAContext context, SemanticContext semanticContext, DFAState d, boolean collectPredicates) Where can we get from NFA state p traversing only epsilon transitions? Add new NFA states + context to DFA state d.
static boolean	closureIsBusy(DFAState d, NFAConfiguration proposedNFAConfiguration) A closure operation should abort if that computation has already been done or a computation with a conflicting context has already been done.
protected DFAState	computeStartState() From this first NFA state of a decision, create a DFA.
void	convert()
protected DFAState	convertToAcceptState(DFAState d, int alt)
protected void	convertToEOTAcceptState(DFAState d) Walk the configurations of this DFA state d looking for the configuration, c, that has a transition on EOT.
protected void	findNewDFAStatesAndAddDFATransitions(DFAState d) From this node, add a d--a-->t transition for all labels 'a' where t is a DFA node created from the set of NFA states reachable from any NFA state in DFA state d.
protected static int	getMinAlt(Set<Integer> nondeterministicAlts)
protected Map<Integer,SemanticContext>	getPredicatesPerNonDeterministicAlt(DFAState d, Set nondeterministicAlts) Return a mapping from nondeterministc alt to combined list of predicates.
protected static SemanticContext	getUnionOfPredicates(Map altToPredMap) OR together all predicates from the alts.
protected void	initContextTrees(int numberOfAlts)
static int	max(Set s)
DFAState	reach(DFAState d, Label label) Given the set of NFA states in DFA state d, find all NFA states reachable traversing label arcs.
protected int	resolveByChoosingFirstAlt(DFAState d, Set nondeterministicAlts)
protected int	resolveByPickingExitAlt(DFAState d, Set nondeterministicAlts) Resolve state d by choosing exit alt, which is same value as the number of alternatives.
protected int	resolveByPickingMinAlt(DFAState d, Set nondeterministicAlts) Turn off all configurations associated with the set of incoming nondeterministic alts except the min alt number.
void	resolveNonDeterminisms(DFAState d) If > 1 NFA configurations within this DFA state have identical NFA state and context, but differ in their predicted TODO update for new context suffix stuff 3-9-2005 alternative then a single input sequence predicts multiple alts.
protected boolean	tryToResolveWithSemanticPredicates(DFAState d, Set nondeterministicAlts) See if a set of nondeterministic alternatives can be disambiguated with the semantic predicate contexts of the alternatives.
protected static void	turnOffOtherAlts(DFAState d, int min, Set<Integer> nondeterministicAlts) turn off all states associated with alts other than the good one (as long as they are one of the nondeterministic ones)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

work

protected List work

A list of DFA states we still need to process during NFA conversion

contextTrees

protected NFAContext[] contextTrees

While converting NFA, we must track states that reference other rule's NFAs so we know what to do at the end of a rule. We need to know what context invoked this rule so we can know where to continue looking for NFA states. I'm tracking a context tree (record of rule invocation stack trace) for each alternative that could be predicted.

dfa

protected DFA dfa

We are converting which DFA?

debug

public static boolean debug

SINGLE_THREADED_NFA_CONVERSION

public static boolean SINGLE_THREADED_NFA_CONVERSION

Should ANTLR launch multiple threads to convert NFAs to DFAs? With a 2-CPU box, I note that it's about the same single or multithreaded. Both CPU meters are going even when single-threaded so I assume the GC is killing us. Could be the compiler. When I run java -Xint mode, I get about 15% speed improvement with multiple threads.

computingStartState

protected boolean computingStartState

Constructor Detail

NFAToDFAConverter

public NFAToDFAConverter(DFA dfa)

Method Detail

convert

public void convert()

computeStartState

protected DFAState computeStartState()

From this first NFA state of a decision, create a DFA. Walk each alt in decision and compute closure from the start of that rule, making sure that the closure does not include other alts within that same decision. The idea is to associate a specific alt number with the starting closure so we can trace the alt number for all states derived from this. At a stop state in the DFA, we can return this alt number, indicating which alt is predicted. If this DFA is derived from an loop back NFA state, then the first transition is actually the exit branch of the loop. Rather than make this alternative one, let's make this alt n+1 where n is the number of alts in this block. This is nice to keep the alts of the block 1..n; helps with error messages. I handle nongreedy in findNewDFAStatesAndAddDFATransitions when nongreedy and EOT transition. Make state with EOT emanating from it the accept state.

findNewDFAStatesAndAddDFATransitions

protected void findNewDFAStatesAndAddDFATransitions(DFAState d)

From this node, add a d--a-->t transition for all labels 'a' where t is a DFA node created from the set of NFA states reachable from any NFA state in DFA state d.

addTransition

protected static int addTransition(DFAState d,
                Label label,
                DFAState targetState,
                Map targetToLabelMap)

Add a transition from state d to targetState with label in normal case. if COLLAPSE_ALL_INCIDENT_EDGES, however, try to merge all edges from d to targetState; this means merging their labels. Another optimization is to reduce to a single EOT edge any set of edges from d to targetState where there exists an EOT state. EOT is like the wildcard so don't bother to test any other edges. Example: NUM_INT : '1'..'9' ('0'..'9')* ('l'|'L')? | '0' ('x'|'X') ('0'..'9'|'a'..'f'|'A'..'F')+ ('l'|'L')? | '0' ('0'..'7')* ('l'|'L')? ; The normal decision to predict alts 1, 2, 3 is: if ( (input.LA(1)>='1' && input.LA(1)<='9') ) { alt7=1; } else if ( input.LA(1)=='0' ) { if ( input.LA(2)=='X'||input.LA(2)=='x' ) { alt7=2; } else if ( (input.LA(2)>='0' && input.LA(2)<='7') ) { alt7=3; } else if ( input.LA(2)=='L'||input.LA(2)=='l' ) { alt7=3; } else { alt7=3; } } else error Clearly, alt 3 is predicted with extra work since it tests 0..7 and [lL] before finally realizing that any character is actually ok at k=2. A better decision is as follows: if ( (input.LA(1)>='1' && input.LA(1)<='9') ) { alt7=1; } else if ( input.LA(1)=='0' ) { if ( input.LA(2)=='X'||input.LA(2)=='x' ) { alt7=2; } else { alt7=3; } } The DFA originally has 3 edges going to the state the predicts alt 3, but upon seeing the EOT edge (the "else"-clause), this method replaces the old merged label (which would have (0..7|l|L)) with EOT. The code generator then leaves alt 3 predicted with a simple else- clause. :) The only time the EOT optimization makes no sense is in the Tokens rule. We want EOT to truly mean you have matched an entire token so don't bother actually rewinding to execute that rule unless there are actions in that rule. For now, since I am not preventing backtracking from Tokens rule, I will simply allow the optimization.

closure

public void closure(DFAState d)

For all NFA states (configurations) merged in d, compute the epsilon closure; that is, find all NFA states reachable from the NFA states in d via purely epsilon transitions.

closure

public void closure(NFAState p,
           int alt,
           NFAContext context,
           SemanticContext semanticContext,
           DFAState d,
           boolean collectPredicates)

Where can we get from NFA state p traversing only epsilon transitions? Add new NFA states + context to DFA state d. Also add semantic predicates to semantic context if collectPredicates is set. We only collect predicates at hoisting depth 0, meaning before any token/char have been recognized. This corresponds, during analysis, to the initial DFA start state construction closure() invocation. There are four cases of interest (the last being the usual transition): 1. Traverse an edge that takes us to the start state of another rule, r. We must push this state so that if the DFA conversion hits the end of rule r, then it knows to continue the conversion at state following state that "invoked" r. By construction, there is a single transition emanating from a rule ref node. 2. Reach an NFA state associated with the end of a rule, r, in the grammar from which it was built. We must add an implicit (i.e., don't actually add an epsilon transition) epsilon transition from r's end state to the NFA state following the NFA state that transitioned to rule r's start state. Because there are many states that could reach r, the context for a rule invocation is part of a call tree not a simple stack. When we fall off end of rule, "pop" a state off the call tree and add that state's "following" node to d's NFA configuration list. The context for this new addition will be the new "stack top" in the call tree. 3. Like case 2, we reach an NFA state associated with the end of a rule, r, in the grammar from which NFA was built. In this case, however, we realize that during this NFA->DFA conversion, no state invoked the current rule's NFA. There is no choice but to add all NFA states that follow references to r's start state. This is analogous to computing the FOLLOW(r) in the LL(k) world. By construction, even rule stop state has a chain of nodes emanating from it that points to every possible following node. This case is conveniently handled then by the 4th case. 4. Normal case. If p can reach another NFA state q, then add q to d's configuration list, copying p's context for q's context. If there is a semantic predicate on the transition, then AND it with any existing semantic context. Current state p is always added to d's configuration list as it's part of the closure as well. When is a closure operation in a cycle condition? While it is very possible to have the same NFA state mentioned twice within the same DFA state, there are two situations that would lead to nontermination of closure operation: o Whenever closure reaches a configuration where the same state with same or a suffix context already exists. This catches the IF-THEN-ELSE tail recursion cycle and things like a : A a | B ; the context will be $ (empty stack). We have to check larger context stacks because of (...)+ loops. For example, the context of a (...)+ can be nonempty if the surrounding rule is invoked by another rule: a : b A | X ; b : (B|)+ ; // nondeterministic by the way The context of the (B|)+ loop is "invoked from item a : . b A ;" and then the empty alt of the loop can reach back to itself. The context stack will have one "return address" element and so we must check for same state, same context for arbitrary context stacks. Idea: If we've seen this configuration before during closure, stop. We also need to avoid reaching same state with conflicting context. Ultimately analysis would stop and we'd find the conflict, but we should stop the computation. Previously I only checked for exact config. Need to check for same state, suffix context not just exact context. o Whenever closure reaches a configuration where state p is present in its own context stack. This means that p is a rule invocation state and the target rule has been called before. NFAContext.MAX_RECURSIVE_INVOCATIONS (See the comment there also) determines how many times it's possible to recurse; clearly we cannot recurse forever. Some grammars such as the following actually require at least one recursive call to correctly compute the lookahead: a : L ID R | b ; b : ID | L a R ; Input L ID R is ambiguous but to figure this out, ANTLR needs to go a->b->a->b to find the L ID sequence. Do not allow closure to add a configuration that would allow too much recursion. This case also catches infinite left recursion.

closureIsBusy

public static boolean closureIsBusy(DFAState d,
                    NFAConfiguration proposedNFAConfiguration)

A closure operation should abort if that computation has already been done or a computation with a conflicting context has already been done. If proposed NFA config's state and alt are the same there is potentially a problem. If the stack context is identical then clearly the exact same computation is proposed. If a context is a suffix of the other, then again the computation is in an identical context. ?$ and ??$ are considered the same stack. We could walk configurations linearly doing the comparison instead of a set for exact matches but it's much slower because you can't do a Set lookup. I use exact match as ANTLR always detect the conflict later when checking for context suffixes... I check for left-recursive stuff and terminate before analysis to avoid need to do this more expensive computation. 12-31-2007: I had to use the loop again rather than simple closureBusy.contains(proposedNFAConfiguration) lookup. The semantic context should not be considered when determining if a closure operation is busy. I saw a FOLLOW closure operation spin until time out because the predicate context kept increasing in size even though it's same boolean value. This seems faster also because I'm not doing String.equals on the preds all the time. 05-05-2008: Hmm...well, i think it was a mistake to remove the sem ctx check below...adding back in. Coincides with report of ANTLR getting super slow: http://www.antlr.org:8888/browse/ANTLR-235 This could be because it doesn't properly compute then resolve a predicate expression. Seems to fix unit test: TestSemanticPredicates.testSemanticContextPreventsEarlyTerminationOfClosure() Changing back to Set from List. Changed a large grammar from 8 minutes to 11 seconds. Cool. Closing ANTLR-235.

reach

public DFAState reach(DFAState d,
             Label label)

Given the set of NFA states in DFA state d, find all NFA states reachable traversing label arcs. By definition, there can be only one DFA state reachable by an atom from DFA state d so we must find and merge all NFA states reachable via label. Return a new DFAState that has all of those NFA states with their context (i.e., which alt do they predict and where to return to if they fall off end of a rule). Because we cannot jump to another rule nor fall off the end of a rule via a non-epsilon transition, NFA states reachable from d have the same configuration as the NFA state in d. So if NFA state 7 in d's configurations can reach NFA state 13 then 13 will be added to the new DFAState (labelDFATarget) with the same configuration as state 7 had. This method does not see EOT transitions off the end of token rule accept states if the rule was invoked by somebody.

convertToEOTAcceptState

protected void convertToEOTAcceptState(DFAState d)

Walk the configurations of this DFA state d looking for the configuration, c, that has a transition on EOT. State d should be converted to an accept state predicting the c.alt. Blast d's current configuration set and make it just have config c. TODO: can there be more than one config with EOT transition? That would mean that two NFA configurations could reach the end of the token with possibly different predicted alts. Seems like that would be rare or impossible. Perhaps convert this routine to find all such configs and give error if >1.

addDFAStateToWorkList

protected DFAState addDFAStateToWorkList(DFAState d)

Add a new DFA state to the DFA if not already present. If the DFA state uniquely predicts a single alternative, it becomes a stop state; don't add to work list. Further, if there exists an NFA state predicted by > 1 different alternatives and with the same syn and sem context, the DFA is nondeterministic for at least one input sequence reaching that NFA state.

convertToAcceptState

protected DFAState convertToAcceptState(DFAState d,
                            int alt)

resolveNonDeterminisms

public void resolveNonDeterminisms(DFAState d)

If > 1 NFA configurations within this DFA state have identical NFA state and context, but differ in their predicted TODO update for new context suffix stuff 3-9-2005 alternative then a single input sequence predicts multiple alts. The NFA decision is therefore syntactically indistinguishable from the left edge upon at least one input sequence. We may terminate the NFA to DFA conversion for these paths since no paths emanating from those NFA states can possibly separate these conjoined twins once interwined to make things deterministic (unless there are semantic predicates; see below). Upon a nondeterministic set of NFA configurations, we should report a problem to the grammar designer and resolve the issue by aribitrarily picking the first alternative (this usually ends up producing the most natural behavior). Pick the lowest alt number and just turn off all NFA configurations associated with the other alts. Rather than remove conflicting NFA configurations, I set the "resolved" bit so that future computations will ignore them. In this way, we maintain the complete DFA state with all its configurations, but prevent future DFA conversion operations from pursuing undesirable paths. Remember that we want to terminate DFA conversion as soon as we know the decision is deterministic *or* nondeterministic. [BTW, I have convinced myself that there can be at most one set of nondeterministic configurations in a DFA state. Only NFA configurations arising from the same input sequence can appear in a DFA state. There is no way to have another complete set of nondeterministic NFA configurations without another input sequence, which would reach a different DFA state. Therefore, the two nondeterministic NFA configuration sets cannot collide in the same DFA state.] Consider DFA state {(s|1),(s|2),(s|3),(t|3),(v|4)} where (s|a) is state 's' and alternative 'a'. Here, configuration set {(s|1),(s|2),(s|3)} predicts 3 different alts. Configurations (s|2) and (s|3) are "resolved", leaving {(s|1),(t|3),(v|4)} as items that must still be considered by the DFA conversion algorithm in DFA.findNewDFAStatesAndAddDFATransitions(). Consider the following grammar where alts 1 and 2 are no problem because of the 2nd lookahead symbol. Alts 3 and 4 are identical and will therefore reach the rule end NFA state but predicting 2 different alts (no amount of future lookahead will render them deterministic/separable): a : A B | A C | A | A ; Here is a (slightly reduced) NFA of this grammar: (1)-A->(2)-B->(end)-EOF->(8) | ^ (2)-A->(3)-C----| | ^ (4)-A->(5)------| | ^ (6)-A->(7)------| where (n) is NFA state n. To begin DFA conversion, the start state is created: {(1|1),(2|2),(4|3),(6|4)} Upon A, all NFA configurations lead to new NFA states yielding new DFA state: {(2|1),(3|2),(5|3),(7|4),(end|3),(end|4)} where the configurations with state end in them are added during the epsilon closure operation. State end predicts both alts 3 and 4. An error is reported, the latter configuration is flagged as resolved leaving the DFA state as: {(2|1),(3|2),(5|3),(7|4|resolved),(end|3),(end|4|resolved)} As NFA configurations are added to a DFA state during its construction, the reachable set of labels is computed. Here reachable is {B,C,EOF} because there is at least one NFA state in the DFA state that can transition upon those symbols. The final DFA looks like: {(1|1),(2|2),(4|3),(6|4)} | v {(2|1),(3|2),(5|3),(7|4),(end|3),(end|4)} -B-> (end|1) | | C ----EOF-> (8,3) | v (end|2) Upon AB, alt 1 is predicted. Upon AC, alt 2 is predicted. Upon A EOF, alt 3 is predicted. Alt 4 is not a viable alternative. The algorithm is essentially to walk all the configurations looking for a conflict of the form (s|i) and (s|j) for i!=j. Use a hash table to track state+context pairs for collisions so that we have O(n) to walk the n configurations looking for a conflict. Upon every conflict, track the alt number so we have a list of all nondeterministically predicted alts. Also track the minimum alt. Next go back over the configurations, setting the "resolved" bit for any that have an alt that is a member of the nondeterministic set. This will effectively remove any alts but the one we want from future consideration. See resolveWithSemanticPredicates() AMBIGUOUS TOKENS With keywords and ID tokens, there is an inherit ambiguity in that "int" can be matched by ID also. Each lexer rule has an EOT transition emanating from it which is used whenever the end of a rule is reached and another token rule did not invoke it. EOT is the only thing that can be seen next. If two rules are identical like "int" and "int" then the 2nd def is unreachable and you'll get a warning. We prevent a warning though for the keyword/ID issue as ID is still reachable. This can be a bit weird. '+' rule then a '+'|'+=' rule will fail to match '+' for the 2nd rule. If all NFA states in this DFA state are targets of EOT transitions, (and there is more than one state plus no unique alt is predicted) then DFA conversion will leave this state as a dead state as nothing can be reached from this state. To resolve the ambiguity, just do what flex and friends do: pick the first rule (alt in this case) to win. This means you should put keywords before the ID rule. If the DFA state has only one NFA state then there is no issue: it uniquely predicts one alt. :) Problem states will look like this during conversion: DFA 1:{9|1, 19|2, 14|3, 20|2, 23|2, 24|2, ...}-->5:{41|3, 42|2} Worse, when you have two identical literal rules, you will see 3 alts in the EOT state (one for ID and one each for the identical rules).

resolveByChoosingFirstAlt

protected int resolveByChoosingFirstAlt(DFAState d,
                            Set nondeterministicAlts)

resolveByPickingMinAlt

protected int resolveByPickingMinAlt(DFAState d,
                         Set nondeterministicAlts)

Turn off all configurations associated with the set of incoming nondeterministic alts except the min alt number. There may be many alts among the configurations but only turn off the ones with problems (other than the min alt of course). If nondeterministicAlts is null then turn off all configs 'cept those associated with the minimum alt. Return the min alt found.

resolveByPickingExitAlt

protected int resolveByPickingExitAlt(DFAState d,
                          Set nondeterministicAlts)

Resolve state d by choosing exit alt, which is same value as the number of alternatives. Return that exit alt.

turnOffOtherAlts

protected static void turnOffOtherAlts(DFAState d,
                    int min,
                    Set<Integer> nondeterministicAlts)

turn off all states associated with alts other than the good one (as long as they are one of the nondeterministic ones)

getMinAlt

protected static int getMinAlt(Set<Integer> nondeterministicAlts)

tryToResolveWithSemanticPredicates

protected boolean tryToResolveWithSemanticPredicates(DFAState d,
                                         Set nondeterministicAlts)

See if a set of nondeterministic alternatives can be disambiguated with the semantic predicate contexts of the alternatives. Without semantic predicates, syntactic conflicts are resolved by simply choosing the first viable alternative. In the presence of semantic predicates, you can resolve the issue by evaluating boolean expressions at run time. During analysis, this amounts to suppressing grammar error messages to the developer. NFA configurations are always marked as "to be resolved with predicates" so that DFA.findNewDFAStatesAndAddDFATransitions() will know to ignore these configurations and add predicate transitions to the DFA after adding token/char labels. During analysis, we can simply make sure that for n ambiguously predicted alternatives there are at least n-1 unique predicate sets. The nth alternative can be predicted with "not" the "or" of all other predicates. NFA configurations without predicates are assumed to have the default predicate of "true" from a user point of view. When true is combined via || with another predicate, the predicate is a tautology and must be removed from consideration for disambiguation: a : b | B ; // hoisting p1||true out of rule b, yields no predicate b : {p1}? B | B ; This is done down in getPredicatesPerNonDeterministicAlt().

getPredicatesPerNonDeterministicAlt

protected Map<Integer,SemanticContext> getPredicatesPerNonDeterministicAlt(DFAState d,
                                                               Set nondeterministicAlts)

Return a mapping from nondeterministc alt to combined list of predicates. If both (s|i|semCtx1) and (t|i|semCtx2) exist, then the proper predicate for alt i is semCtx1||semCtx2 because you have arrived at this single DFA state via two NFA paths, both of which have semantic predicates. We ignore deterministic alts because syntax alone is sufficient to predict those. Do not include their predicates. Alts with no predicate are assumed to have {true}? pred. When combining via || with "true", all predicates are removed from consideration since the expression will always be true and hence not tell us how to resolve anything. So, if any NFA configuration in this DFA state does not have a semantic context, the alt cannot be resolved with a predicate. If nonnull, incidentEdgeLabel tells us what NFA transition label we did a reach on to compute state d. d may have insufficient preds, so we really want this for the error message.

getUnionOfPredicates

protected static SemanticContext getUnionOfPredicates(Map altToPredMap)

OR together all predicates from the alts. Note that the predicate for an alt could itself be a combination of predicates.

addPredicateTransitions

protected void addPredicateTransitions(DFAState d)

for each NFA config in d, look for "predicate required" sign set during nondeterminism resolution. Add the predicate edges sorted by the alternative number; I'm fairly sure that I could walk the configs backwards so they are added to the predDFATarget in the right order, but it's best to make sure. Predicates succeed in the order they are specifed. Alt i wins over alt i+1 if both predicates are true.

initContextTrees

protected void initContextTrees(int numberOfAlts)

max

public static int max(Set s)