Package icyllis.arc3d.compiler.lex

Class NFAtoDFA

java.lang.Object

icyllis.arc3d.compiler.lex.NFAtoDFA

public class NFAtoDFA
extends Object

Converts a nondeterministic finite automaton to a deterministic finite automaton. Since NFAs and DFAs differ only in that an NFA allows multiple states at the same time, we can find each possible combination of simultaneous NFA states and give this combination a label. These labelled nodes are our DFA nodes, since we can only be in one such unique set of NFA states at a time.

As an NFA can end up in multiple accept states at the same time (for instance, the token "while" is valid for both WHILE and IDENTIFIER), we disambiguate by preferring the first matching regex (in terms of the order in which they were added to the NFA).

Field Summary

Fields

Modifier and Type	Field	Description
static final char	END_CHAR
static final char	START_CHAR

Constructor Summary

Constructors

Constructor	Description
NFAtoDFA(NFA NFA)

Method Summary

Modifier and Type	Method	Description
DFA	convert()	Returns a DFA created from the NFA.

Methods inherited from class java.lang.Object

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

Field Details

START_CHAR

public static final char START_CHAR

See Also:

• Constant Field Values

END_CHAR

public static final char END_CHAR

See Also:

• Constant Field Values

Constructor Details

NFAtoDFA

public NFAtoDFA(NFA NFA)

Method Details

convert

@Nonnull
public DFA convert()

Returns a DFA created from the NFA.