This repository has been archived by the owner on Nov 18, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
automata.h
115 lines (96 loc) · 2.79 KB
/
automata.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#pragma once
#include<iostream>
#include<map>
#include<vector>
using namespace std;
typedef std::pair<int, char> tpair;
/**
* Abstract class for Deterministic Finite Automata.
*/
class AbstractDFA {
protected:
std::vector<int> states; // states vector
std::vector<int> final_states; // final states vector
int n_states; // variable used to store the total number of states
int current_state; // variable used to store the number of the current state
/** Transitions map declaration:
* the map's key will be a tpair (int, char) where the first int is the current state
* the char will be the given letter while the second map's value,
* an int, indicate the next state.
*/
std::map<tpair, int> mappa;
public:
/**
* Constructor for Abstract DFA.
*
* @param noStates
* Number of states in the DFA.
*/
AbstractDFA(int noStates);
/**
* Reset the automaton to the initial state.
*/
void reset();
/**
* Performs one step of the DFA for a given letter. If there is a transition
* for the given letter, then the automaton proceeds to the successor state.
* Otherwise it goes to the sink state. By construction it will stay in the
* sink for every input letter.
*
* @param letter
* The current input.
*/
virtual void doStep(char letter);
/**
* Check if the automaton is currently accepting.
*
* @return True, if the automaton is currently in the accepting state.
*/
bool isAccepting();
/**
* Run the DFA on the input.
*
* @param inputWord
* stream that contains the input word
* @return True, if if the word is accepted by this automaton
*/
bool run(const string &inputWord);
};
/**
* DFA recognizing a given word.
*/
class WordDFA : public AbstractDFA {
public:
/**
* Construct a new DFA that recognizes exactly the given word. Given a word
* "foo" the constructed automaton looks like: -> () -f-> () -o-> () -o-> []
* from every state (including the final one) every other input letter leads
* to a distinguished sink state in which the automaton then remains
*
* @param word
* A String that the automaton should recognize
*/
WordDFA(const string &word);
};
/**
* DFA recognizing comments.
*/
class CommentDFA : public AbstractDFA {
public:
/**
* Construct a new DFA that recognizes comments within source code. There
* are three kinds of comments:
* 1. a single line comment that starts with // and ends with a newline
* 2. a multiline comment that starts with (* and ends with *)
* 3. a multiline comment that starts with { and ends with }
*/
CommentDFA();
/**
* Performs one step of the DFA for a given letter. This method works
* differently than in the superclass AbstractDFA.
*
* @param letter
* The current input.
*/
virtual void doStep(char letter);
};