public class NFAToDFAConverter extends Object
Modifier and Type | Field | 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<DFAState> |
work |
A list of DFA states we still need to process during NFA conversion
|
Constructor | Description |
---|---|
NFAToDFAConverter(DFA dfa) |
Modifier and Type | Method | 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<Integer,Transition> 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<Integer> nondeterministicAlts) |
Return a mapping from nondeterministc alt to combined list of predicates.
|
protected static SemanticContext |
getUnionOfPredicates(Map<?,SemanticContext> altToPredMap) |
OR together all predicates from the alts.
|
protected void |
initContextTrees(int numberOfAlts) |
|
static int |
max(Set<Integer> 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<Integer> nondeterministicAlts) |
|
protected int |
resolveByPickingExitAlt(DFAState d,
Set<Integer> nondeterministicAlts) |
Resolve state d by choosing exit alt, which is same value as the
number of alternatives.
|
protected int |
resolveByPickingMinAlt(DFAState d,
Set<Integer> 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<Integer> 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)
|
protected List<DFAState> work
protected NFAContext[] contextTrees
protected DFA dfa
public static boolean debug
public static boolean SINGLE_THREADED_NFA_CONVERSION
protected boolean computingStartState
public NFAToDFAConverter(DFA dfa)
public void convert()
protected DFAState computeStartState()
protected void findNewDFAStatesAndAddDFATransitions(DFAState d)
protected static int addTransition(DFAState d, Label label, DFAState targetState, Map<Integer,Transition> targetToLabelMap)
public void closure(DFAState d)
public void closure(NFAState p, int alt, NFAContext context, SemanticContext semanticContext, DFAState d, boolean collectPredicates)
public static boolean closureIsBusy(DFAState d, NFAConfiguration proposedNFAConfiguration)
public DFAState reach(DFAState d, Label label)
protected void convertToEOTAcceptState(DFAState d)
protected DFAState addDFAStateToWorkList(DFAState d)
public void resolveNonDeterminisms(DFAState d)
protected int resolveByChoosingFirstAlt(DFAState d, Set<Integer> nondeterministicAlts)
protected int resolveByPickingMinAlt(DFAState d, Set<Integer> nondeterministicAlts)
protected int resolveByPickingExitAlt(DFAState d, Set<Integer> nondeterministicAlts)
protected static void turnOffOtherAlts(DFAState d, int min, Set<Integer> nondeterministicAlts)
protected boolean tryToResolveWithSemanticPredicates(DFAState d, Set<Integer> nondeterministicAlts)
protected Map<Integer,SemanticContext> getPredicatesPerNonDeterministicAlt(DFAState d, Set<Integer> nondeterministicAlts)
protected static SemanticContext getUnionOfPredicates(Map<?,SemanticContext> altToPredMap)
protected void addPredicateTransitions(DFAState d)
protected void initContextTrees(int numberOfAlts)
Copyright © 1992–2019 ANTLR. All rights reserved.