C++ || Simple Tokenizer Lexer Using A Finite State Machine

January 29, 2014 admin 1 Comment

The following is sample code which demonstrates the implementation of a simple Lexer using a table driven Finite State Machine.

In its simplest form, a Finite State Machine is a procedure that can: (1) store the status of an event, (2) can operate on new (or existing) input to change the status of an event, and (3) can cause an action to take place (based on the input change) for the particular event being examined.

State machines usually adhere to the following basic principles:

• Has an initial state or record of something stored someplace • Has a set of possible input events • Has a set of new states that may result from the input • Has a set of possible actions or output events that result from a new state

Finite state machines usually have a limited or finite number of possible states. The Finite State Machine implemented on this page has 6 transition states. Those transition states has the ability to isolate tokens from a given input string, based on characteristics defined in the transition state table.

The machine was implemented with compiler construction in mind, resulting in the grammar for the 6 transition states to resemble that of many popular programming languages.

The transition table defined in this program can be further fine tuned by allowing the states to accept or reject different parameters, and/or by adding more transition states. Tuning the parameters in the state transition table allows you to change the behavior of the state machine without having the need to alter the Finite State Machine Algorithm (the “Lexer” function) much at all.

NOTE: The example on this page uses a sample input file. Click here to download the file.





		
		
			Simple Lexer Using A Finite State Machine
			
C++
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 29, 2014
//    Taken From: http://programmingnotes.org/
//    File: FSM.cpp
//    Description: The following demonstrates the implementation of a simple
//      Lexer using a table driven Finite State Machine.
// ============================================================================
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

/* This holds the transition states for our Finite State Machine
    -- They are placed in numerical order for easy understanding within
        the FSM array, which is located below */

enum FSM_TRANSITIONS
{
    REJECT = 0,
    INTEGER,
    REAL,
    OPERATOR,
    STRING,
    UNKNOWN,
    SPACE
};

/* This is the Finite State Machine Table
    -- The zero represents a place holder, so the row in the array starts on
      row 1 instead of 0.

    -- You can tune this table to make the states accept or reject different
      parameters, thus changing its behavior. More states can be added to
      this table.
                           integer,  real,  operator,  string,  unknown,  space */
int stateTable[][7] = {{0, INTEGER,  REAL,  OPERATOR,  STRING, UNKNOWN,  SPACE},
/* STATE 1 */   {INTEGER,  INTEGER,  REAL,   REJECT,   REJECT,  REJECT,  REJECT},
/* STATE 2 */   {REAL,       REAL,  UNKNOWN, REJECT,   REJECT,  REJECT,  REJECT},
/* STATE 3 */   {OPERATOR,  REJECT, REJECT,  REJECT,   STRING,  REJECT,  REJECT},
/* STATE 4 */   {STRING,    STRING, REJECT,  STRING,   STRING,  REJECT,  REJECT},
/* STATE 5 */   {UNKNOWN,  UNKNOWN, UNKNOWN, UNKNOWN,  UNKNOWN, UNKNOWN, REJECT},
/* STATE 6 */   {SPACE,     REJECT, REJECT,  REJECT,   REJECT,  REJECT,  REJECT}};


// struct to hold token information
struct TokenType
{
    string token;
    int lexeme;
    string lexemeName;
};

// function prototypes
vector<TokenType> Lexer(string expression);
int Get_FSM_Col(char currentChar);
string GetLexemeName(int lexeme);

int main()
{
    // declare variables
    ifstream infile;
    string fileName = "";
    string expression = "";
    vector<TokenType> tokens;

    // get data from user
    cout<<"\nPlease enter the name of the file: ";
    getline(cin, fileName);

    infile.open(fileName.c_str());

    if(infile.fail())
    {
        cout<<"\n** ERROR - the file \""<<fileName<<"\" cannot be found!\n\n";
        exit(1);
    }

    // use a loop to scan each line in the file
    while(getline(infile, expression))
    {
        // use the "Lexer" function to isolate integer, real, operator,
        // string, and unknown tokens
        tokens = Lexer(expression);

        // display the tokens to the screen
        for(unsigned x = 0; x < tokens.size(); ++x)
        {
            cout<<tokens[x].lexemeName<<"  \t"
                <<tokens[x].token<<endl;
        }
    }

    infile.close();

    return 0;
}// end of main

/**
* FUNCTION: Lexer
* USE: Parses the "expression" string using the Finite State Machine to
*     isolate each individual token and lexeme name in the expression.
* @param expression - A std::string containing text.
* @return - Returns a vector containing the tokens found in the string
*/
vector<TokenType> Lexer(string expression)
{
    TokenType access;
    vector<TokenType> tokens;
    char currentChar = ' ';
    int col = REJECT;
    int currentState = REJECT;
    int prevState = REJECT;
    string currentToken = "";

    // use an FSM to parse the expression
    for(unsigned x = 0; x < expression.length();)
    {
        currentChar = expression[x];

        // get the column number for the current character
        col = Get_FSM_Col(currentChar);

        /* ========================================================

            THIS IS WHERE WE CHECK THE FINITE STATE MACHINE TABLE
               USING THE "col" VARIABLE FROM ABOVE ^

          ========================================================= */

        // get the current state of the expression
        currentState = stateTable[currentState][col];

        /* ===================================================

          THIS IS WHERE WE CHECK FOR A SUCESSFUL PARSE
           - If the current state of the expression == REJECT
             (the starting state), then we have sucessfully parsed
             a token.

            - ELSE we continue trying to find a sucessful token

            =================================================== */
        if(currentState == REJECT)
        {
            if(prevState != SPACE) // we dont care about whitespace
            {
                access.token = currentToken;
                access.lexeme = prevState;
                access.lexemeName = GetLexemeName(access.lexeme);
                tokens.push_back(access);
            }
            currentToken = "";
        }
        else
        {
            currentToken += currentChar;
            ++x;
        }
        prevState = currentState;

    }
    // this ensures the last token gets saved when
    // we reach the end of the loop (if a valid token exists)
    if(currentState != SPACE && currentToken != "")
    {// ^^ we dont care about whitespace
        access.token = currentToken;
        access.lexeme = currentState;
        access.lexemeName = GetLexemeName(access.lexeme);
        tokens.push_back(access);
    }
    return tokens;
}// end of Lexer

/**
* FUNCTION: Get_FSM_Col
* USE: Determines the state of the type of character being examined.
* @param currentChar - A character.
* @return - Returns the state of the type of character being examined.
*/
int Get_FSM_Col(char currentChar)
{
    // check for whitespace
    if(isspace(currentChar))
    {
        return SPACE;
    }

    // check for integer numbers
    else if(isdigit(currentChar))
    {
        return INTEGER;
    }

    // check for real numbers
    else if(currentChar == '.')
    {
        return REAL;
    }

    // check for characters
    else if(isalpha(currentChar))
    {
        return STRING;
    }

    // check for operators
    else if(ispunct(currentChar))
    {
        return OPERATOR;
    }
    return UNKNOWN;
}// end of Get_FSM_Col

/**
* FUNCTION: GetLexemeName
* USE: Returns the string equivalent of an integer lexeme token type.
* @param lexeme - An integer lexeme token type.
* @return - An std::string string representing the name of the integer
*        lexeme token type.
*/
string GetLexemeName(int lexeme)
{
    switch(lexeme)
    {
        case INTEGER:
           return "INTEGER";
           break;
        case REAL:
           return "REAL  ";
           break;
        case OPERATOR:
           return "OPERATOR";
           break;
        case STRING:
           return "STRING";
           break;
        case UNKNOWN:
           return "UNKNOWN";
           break;
        case SPACE:
           return "SPACE";
           break;
        default:
           return "ERROR";
           break;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 29, 2014
//    Taken From: http://programmingnotes.org/
//    File: FSM.cpp
//    Description: The following demonstrates the implementation of a simple
//      Lexer using a table driven Finite State Machine.
// ============================================================================
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
 
/* This holds the transition states for our Finite State Machine
    -- They are placed in numerical order for easy understanding within
        the FSM array, which is located below */
 
enum FSM_TRANSITIONS
{
    REJECT = 0,
    INTEGER,
    REAL,
    OPERATOR,
    STRING,
    UNKNOWN,
    SPACE
};
 
/* This is the Finite State Machine Table
    -- The zero represents a place holder, so the row in the array starts on
      row 1 instead of 0.
 
    -- You can tune this table to make the states accept or reject different
      parameters, thus changing its behavior. More states can be added to
      this table.
                           integer,  real,  operator,  string,  unknown,  space */
int stateTable[][7] = {{0, INTEGER,  REAL,  OPERATOR,  STRING, UNKNOWN,  SPACE},
/* STATE 1 */   {INTEGER,  INTEGER,  REAL,   REJECT,   REJECT,  REJECT,  REJECT},
/* STATE 2 */   {REAL,       REAL,  UNKNOWN, REJECT,   REJECT,  REJECT,  REJECT},
/* STATE 3 */   {OPERATOR,  REJECT, REJECT,  REJECT,   STRING,  REJECT,  REJECT},
/* STATE 4 */   {STRING,    STRING, REJECT,  STRING,   STRING,  REJECT,  REJECT},
/* STATE 5 */   {UNKNOWN,  UNKNOWN, UNKNOWN, UNKNOWN,  UNKNOWN, UNKNOWN, REJECT},
/* STATE 6 */   {SPACE,     REJECT, REJECT,  REJECT,   REJECT,  REJECT,  REJECT}};
 
 
// struct to hold token information
struct TokenType
{
    string token;
    int lexeme;
    string lexemeName;
};
 
// function prototypes
vector<TokenType> Lexer(string expression);
int Get_FSM_Col(char currentChar);
string GetLexemeName(int lexeme);
 
int main()
{
    // declare variables
    ifstream infile;
    string fileName = "";
    string expression = "";
    vector<TokenType> tokens;
 
    // get data from user
    cout<<"\nPlease enter the name of the file: ";
    getline(cin, fileName);
 
    infile.open(fileName.c_str());
 
    if(infile.fail())
    {
        cout<<"\n** ERROR - the file \""<<fileName<<"\" cannot be found!\n\n";
        exit(1);
    }
 
    // use a loop to scan each line in the file
    while(getline(infile, expression))
    {
        // use the "Lexer" function to isolate integer, real, operator,
        // string, and unknown tokens
        tokens = Lexer(expression);
 
        // display the tokens to the screen
        for(unsigned x = 0; x < tokens.size(); ++x)
        {
            cout<<tokens[x].lexemeName<<"  \t"
                <<tokens[x].token<<endl;
        }
    }
 
    infile.close();
 
    return 0;
}// end of main
 
/**
* FUNCTION: Lexer
* USE: Parses the "expression" string using the Finite State Machine to
*     isolate each individual token and lexeme name in the expression.
* @param expression - A std::string containing text.
* @return - Returns a vector containing the tokens found in the string
*/
vector<TokenType> Lexer(string expression)
{
    TokenType access;
    vector<TokenType> tokens;
    char currentChar = ' ';
    int col = REJECT;
    int currentState = REJECT;
    int prevState = REJECT;
    string currentToken = "";
 
    // use an FSM to parse the expression
    for(unsigned x = 0; x < expression.length();)
    {
        currentChar = expression[x];
 
        // get the column number for the current character
        col = Get_FSM_Col(currentChar);
 
        /* ========================================================
 
            THIS IS WHERE WE CHECK THE FINITE STATE MACHINE TABLE
               USING THE "col" VARIABLE FROM ABOVE ^
 
          ========================================================= */
 
        // get the current state of the expression
        currentState = stateTable[currentState][col];
 
        /* ===================================================
 
          THIS IS WHERE WE CHECK FOR A SUCESSFUL PARSE
           - If the current state of the expression == REJECT
             (the starting state), then we have sucessfully parsed
             a token.
 
            - ELSE we continue trying to find a sucessful token
 
            =================================================== */
        if(currentState == REJECT)
        {
            if(prevState != SPACE) // we dont care about whitespace
            {
                access.token = currentToken;
                access.lexeme = prevState;
                access.lexemeName = GetLexemeName(access.lexeme);
                tokens.push_back(access);
            }
            currentToken = "";
        }
        else
        {
            currentToken += currentChar;
            ++x;
        }
        prevState = currentState;
 
    }
    // this ensures the last token gets saved when
    // we reach the end of the loop (if a valid token exists)
    if(currentState != SPACE && currentToken != "")
    {// ^^ we dont care about whitespace
        access.token = currentToken;
        access.lexeme = currentState;
        access.lexemeName = GetLexemeName(access.lexeme);
        tokens.push_back(access);
    }
    return tokens;
}// end of Lexer
 
/**
* FUNCTION: Get_FSM_Col
* USE: Determines the state of the type of character being examined.
* @param currentChar - A character.
* @return - Returns the state of the type of character being examined.
*/
int Get_FSM_Col(char currentChar)
{
    // check for whitespace
    if(isspace(currentChar))
    {
        return SPACE;
    }
 
    // check for integer numbers
    else if(isdigit(currentChar))
    {
        return INTEGER;
    }
 
    // check for real numbers
    else if(currentChar == '.')
    {
        return REAL;
    }
 
    // check for characters
    else if(isalpha(currentChar))
    {
        return STRING;
    }
 
    // check for operators
    else if(ispunct(currentChar))
    {
        return OPERATOR;
    }
    return UNKNOWN;
}// end of Get_FSM_Col
 
/**
* FUNCTION: GetLexemeName
* USE: Returns the string equivalent of an integer lexeme token type.
* @param lexeme - An integer lexeme token type.
* @return - An std::string string representing the name of the integer
*        lexeme token type.
*/
string GetLexemeName(int lexeme)
{
    switch(lexeme)
    {
        case INTEGER:
           return "INTEGER";
           break;
        case REAL:
           return "REAL  ";
           break;
        case OPERATOR:
           return "OPERATOR";
           break;
        case STRING:
           return "STRING";
           break;
        case UNKNOWN:
           return "UNKNOWN";
           break;
        case SPACE:
           return "SPACE";
           break;
        default:
           return "ERROR";
           break;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

NOTE: The example on this page uses a sample input file. Click here to download the file.

The following is sample output.





		
		
			Please enter the name of the file: FiniteStateMachine_programmingnotes_freeweq_com.txt

STRING  	Rat12F
STRING  	Function
STRING  	function
STRING  	Identifier
OPERATOR  	(
OPERATOR  	)
OPERATOR  	:
OPERATOR  	:
OPERATOR  	;
OPERATOR  	,
OPERATOR  	{
OPERATOR  	}
OPERATOR  	=
OPERATOR  	[
OPERATOR  	]
STRING  	int
STRING  	boolean
STRING  	real
STRING  	If
STRING  	if
STRING  	else
STRING  	fi
STRING  	while
STRING  	Return
STRING  	return
OPERATOR  	;
STRING  	printf
STRING  	scanf
OPERATOR  	(
STRING  	IDs
OPERATOR  	)
OPERATOR  	;
OPERATOR  	=
OPERATOR  	=
OPERATOR  	!
OPERATOR  	=
OPERATOR  	>
OPERATOR  	>
OPERATOR  	<
OPERATOR  	=
OPERATOR  	>
OPERATOR  	<
OPERATOR  	=
OPERATOR  	+
OPERATOR  	-
OPERATOR  	*
OPERATOR  	/
OPERATOR  	/
OPERATOR  	-
STRING  	true
STRING  	false
INTEGER  	123
INTEGER  	0000
REAL    	13.456
REAL    	.567
UNKNOWN  	12.45.67.
STRING  	a_c__4t
STRING  	a____t
STRING  	x
STRING  	x56
STRING  	_fgt
OPERATOR  	%
OPERATOR  	&
OPERATOR  	/
OPERATOR  	*
STRING  	Middle
OPERATOR  	*
OPERATOR  	/
OPERATOR  	/
OPERATOR  	*
STRING  	end
OPERATOR  	*
OPERATOR  	/
INTEGER  	67
STRING  	yu
			
				
					
				
					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
				
						Please enter the name of the file: FiniteStateMachine_programmingnotes_freeweq_com.txt
 
STRING  	Rat12F
STRING  	Function
STRING  	function
STRING  	Identifier
OPERATOR  	(
OPERATOR  	)
OPERATOR  	:
OPERATOR  	:
OPERATOR  	;
OPERATOR  	,
OPERATOR  	{
OPERATOR  	}
OPERATOR  	=
OPERATOR  	[
OPERATOR  	]
STRING  	int
STRING  	boolean
STRING  	real
STRING  	If
STRING  	if
STRING  	else
STRING  	fi
STRING  	while
STRING  	Return
STRING  	return
OPERATOR  	;
STRING  	printf
STRING  	scanf
OPERATOR  	(
STRING  	IDs
OPERATOR  	)
OPERATOR  	;
OPERATOR  	=
OPERATOR  	=
OPERATOR  	!
OPERATOR  	=
OPERATOR  	>
OPERATOR  	>
OPERATOR  	<
OPERATOR  	=
OPERATOR  	>
OPERATOR  	<
OPERATOR  	=
OPERATOR  	+
OPERATOR  	-
OPERATOR  	*
OPERATOR  	/
OPERATOR  	/
OPERATOR  	-
STRING  	true
STRING  	false
INTEGER  	123
INTEGER  	0000
REAL    	13.456
REAL    	.567
UNKNOWN  	12.45.67.
STRING  	a_c__4t
STRING  	a____t
STRING  	x
STRING  	x56
STRING  	_fgt
OPERATOR  	%
OPERATOR  	&
OPERATOR  	/
OPERATOR  	*
STRING  	Middle
OPERATOR  	*
OPERATOR  	/
OPERATOR  	/
OPERATOR  	*
STRING  	end
OPERATOR  	*
OPERATOR  	/
INTEGER  	67
STRING  	yu

Was this article helpful?

👍 YesNo

Posted in: Advanced, C++, C++, Snippets Tags: compilers, cpsc 323, finite state machine, fsm, lexer, rat12f

One Response to C++ || Simple Tokenizer Lexer Using A Finite State Machine

Ihor says:

December 29, 2016 at 4:43 am

Thanks for article !

Reply

C++ || Simple Tokenizer Lexer Using A Finite State Machine

Related

One Response to C++ || Simple Tokenizer Lexer Using A Finite State Machine

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories