简单的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.

1
2
3
4
5
6
7
8
9
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.

1
2
3
4
5
StateSet states;
TransitionSet transitions;
AlphabetSet alphabets;
StateSet acceptingStates;
State currentState;

And those values has been defined outside the FiniteAutomaton class.

1
2
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.

1
State transite(Alphabet input);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.

1
2
3
4
5
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

简单的DFA实现
https://waterch.cn/2017/09/02/SillyCompiler-Scanner-DFA/
作者
Runze Chen
发布于
2017年9月2日
许可协议