Deterministic Finite Automata Implementation in C

DFA.c

#include "DFA.h"
#include <stdlib.h>
#include <string.h>

void dfa_makeNextTransition(DFA* dfa, char c)
{
	int transitionID;
	DFAState* pCurrentState = dfa->states[dfa->currentStateID];
	for (transitionID = 0; transitionID < pCurrentState->numberOfTransitions; transitionID++)
	{
		if (pCurrentState->transitions[transitionID].condition(c))
		{
			dfa->currentStateID = pCurrentState->transitions[transitionID].toStateID;
			return;
		}
	}

	//take the default transition
	dfa->currentStateID = pCurrentState->defaultToStateID;
}

void dfa_addState(DFA* pDFA, DFAState* newState)
{	
	newState->ID = pDFA->numberOfStates;
	pDFA->states[pDFA->numberOfStates] = newState;
	pDFA->numberOfStates++;
}

void dfa_addTransition(DFA* dfa, int fromStateID, int(*condition)(char), int toStateID)
{
	DFAState* state = dfa->states[fromStateID];
	state->transitions[state->numberOfTransitions].condition = condition;
	state->transitions[state->numberOfTransitions].toStateID = toStateID;
	state->numberOfTransitions++;

}

DFAState* dfa_createState(int hasAction, char* actionName)
{
	DFAState* newState = (DFAState*)malloc(sizeof(DFAState));
	strcpy(newState->actionName, actionName);
	newState->defaultToStateID = -1;
	newState->hasAction = hasAction;
	newState->ID = -1;
	newState->numberOfTransitions = 0;

	return newState;
	
}

DFA* dfa_createDFA()
{
	DFA* dfa = (DFA*)malloc(sizeof(DFA));
	dfa->numberOfStates = 0;
	dfa->startStateID = -1;
	dfa->currentStateID = -1;
	return dfa;
}

void dfa_reset(DFA* dfa)
{
	dfa->currentStateID = dfa->startStateID;
}

DFA.h

#ifndef _DFA_H_
#define _DFA_H_

#define MAX_TRANSITIONS 50
#define MAX_STATES 100


typedef struct
{
	int (*condition)(char); //a bool-returning and char-taking function pointer which is used to test whether this transition is to be taken.
	int toStateID;
} DFATransition;

typedef struct
{
	int ID; //unique ID associated with every state
	int hasAction; //indicates whether any action should be taken when DFA is in this state
	int numberOfTransitions; //number of outgoing transitions excluding the default (other) transition
	char actionName[256]; //the string based on which action is taken
	DFATransition transitions[MAX_TRANSITIONS]; //list of outgoing transitions
	int defaultToStateID; //the default (other) transition. This is taken when no other transition is possible
} DFAState;

typedef struct
{
	int startStateID;
	int currentStateID;
	int numberOfStates;
	DFAState* states[MAX_STATES];
} DFA;

DFA* dfa_createDFA();
void dfa_reset(DFA* dfa); //makes the dfa ready for consumption. i.e. sets the current state to start state.
void dfa_makeNextTransition(DFA* dfa, char c);
void dfa_addState(DFA* pDFA, DFAState* newState);
DFAState* dfa_createState(int hasAction, char* actionName);
void dfa_addTransition(DFA* dfa, int fromStateID, int(*condition)(char), int toStateID);

#endif