简单的DFA实现

Type	Reference
Source	SLScanner/FiniteAutomaton.cpp
Source	SLScanner/DeterministicFiniteAutomaton.cpp
Header	SLScanner/FiniteAutomaton.hpp
Header	SLScanner/DeterministicFiniteAutomaton.hpp
Test	SLScanner/TestDeterministicFiniteAutomaton.cpp

Definition

is the finite set of states in the recognizer, along with an error state

is the finite alphabet used by the recognizer. Typically, is the union of the edge labels in the transition diagram.

is the recognizer’s transition function. It maps each state and each character into some next state. In state si with input character , the takes the transition .

is the designated start state.

is the set of accepting states, . Each state in appears as a double circle in the transition diagram.

Design

According to the definition of Finite Automaton, I have designed the class FiniteAutomaton in below structure. Actually, starting state is always , so I didn't describe it explicitly in the class. Before building the class structrue, I decided to define some fundamental types for the internal elements of a finite automaton.

typedef int32_t State;
typedef char Alphabet;
typedef std::pair<State, Alphabet> Move;
typedef std::map<Move, State> TransitionSet;
typedef std::set<State> StateSet;
typedef std::set<Alphabet> AlphabetSet;
typedef enum {
  Accepted = 1, NotAccepted = 0, Trapped = -1
} StateType;

Followings are some necessary elements for a finite automaton.

StateSet states;
TransitionSet transitions;
AlphabetSet alphabets;
StateSet acceptingStates;
State currentState;

And those values has been defined outside the FiniteAutomaton class.

const FiniteAutomaton::State StartState = 0;
const FiniteAutomaton::State TrapState = -1;

The FiniteAutomaton class is a base class for DeterministicFiniteAutomaton. And we can only use DFA to match the strings. So the most important part of the scanner is the fundamental DFA.

So I built the following function to simulate the actions of real DFA.

State transite(Alphabet input);

Silly::DeterministicFiniteAutomaton::State
Silly::DeterministicFiniteAutomaton::transite(Silly::DeterministicFiniteAutomaton::Alphabet input) {
    if (isFinished) {
        reboot();
        isFinished = false;
    }
    if (alphabets.find(input) != alphabets.end() && transitions.find(Move(currentState, input)) != transitions.end()) {
        State nextState = transitions[Move(currentState, input)];
        currentState = nextState;
        currentAlphabet = input;
        return nextState;
    } else {
        currentState = TrapState;
        return TrapState;
    }
}

The transite function needs to check if the DFA has finished a match task executed by match function. And one transition means finding an accessible transition from all transitions. If it does not exist in the transitions, the DFA may cause a trap state to exclaim the match is not successful and it can not move to other states unless reboot is executed.

Actually the structure of a DFA is simple and you must manually set all the elements for the DFA by using the following constructor function.

DeterministicFiniteAutomaton(
  StateSet states_,
  TransitionSet transitions_,
  AlphabetSet alphabets_,
  StateSet acceptingStates_);

Test

So I used following test case to check the availability of the DFA.

DeterministicFiniteAutomaton.SimpleTest:

Test Result:

String	StateType	TestResult
A12345	Accepted	PASS
A	Accepted	PASS
Z3910	Accepted	PASS
Z99999	Accepted	PASS
Z9999D	Trapped	PASS
	Trapped	PASS
3232	Trapped	PASS

DeterministicFiniteAutomaton.FloatNumberTest:

The definition of test DFA is omitted, you can reference it in the SLScanner/TestDeterministicFiniteAutomaton.cpp.

String	StateType	TestResult
0.13423231	Accepted	PASS
0.1342E+213.4	Accepted	PASS
+13	Accepted	PASS
+13e-19	Accepted	PASS
.234144	Trapped	PASS
.234122.21310012.	Trapped	PASS
.234E	NotAccepted	PASS

DeterministicFiniteAutomaton.CamelCaseTest:

The definition of test DFA is omitted, you can reference it in the SLScanner/TestDeterministicFiniteAutomaton.cpp.

String	StateType	TestResult
HelloWorld	Accepted	PASS
GoodBoy	Accepted	PASS
GoodB	NotAccepted	PASS
GoodB8	Trapped	PASS