mcnaughton_yamada_thompson.c File Reference

McNaughton–Yamada–Thompson algorithm More...

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

Include dependency graph for mcnaughton_yamada_thompson.c:

Data Structures
struct	ASTNode
	for assert() More...
struct	transRule
	Definition for a NFA state transition rule. More...
struct	NFAState
	Definition for a NFA state. More...
struct	NFA
	Definition for the NFA itself. More...

Functions
struct ASTNode *	createNode (const char content)
	creates and initializes a AST node
void	destroyNode (struct ASTNode *node)
	recursively destroys a AST
char *	preProcessing (const char *input)
	performs preprocessing on a regex string, making all implicit concatenations explicit
struct ASTNode *	buildAST (const char *input)
	recursively constructs a AST from a preprocessed regex string
struct transRule *	createRule (struct NFAState *state, char c)
	creates and initializes a transition rule
void	destroyRule (struct transRule *rule)
	destroys a transition rule object
struct NFAState *	createState (void)
	creates and initializes a NFA state
void	destroyState (struct NFAState *state)
	destroys a NFA state
struct NFA *	createNFA (void)
	creates and initializes a NFA
void	destroyNFA (struct NFA *nfa)
	recursively destroys a NFA
void	addState (struct NFA *nfa, struct NFAState *state)
	adds a state to a NFA
void	addRule (struct NFA *nfa, struct transRule *rule, int loc)
	adds a transition rule to a NFA
void	postProcessing (struct NFA *nfa)
	performs postprocessing on a compiled NFA, add circular empty character transition rules where it's needed for the NFA to function correctly
void	transit (struct NFA *nfa, char input)
	moves a NFA forward
int	isAccepting (const struct NFA *nfa)
	determines whether the NFA is currently in its accepting state
int	isLiteral (const char ch)
	helper function to determine whether a character should be considered a character literal
size_t	indexOf (const char *str, char key)
	utility function to locate the first occurrence of a character in a string while respecting parentheses
char *	subString (const char *str, size_t begin, size_t end)
	utility function to create a subString
void	redirect (struct NFA *nfa, struct NFAState *src, struct NFAState *dest)
	helper function to recursively redirect transition rule targets
struct NFA *	compileFromAST (struct ASTNode *root)
int	contains (struct NFAState **states, int len, struct NFAState *state)
	helper function to determine an element's presence in an array
void	findEmpty (struct NFAState *target, struct NFAState **states, int *sc)
	helper function to manage empty character transitions
void	testHelper (const char *regex, const char *string, const int expected)
	Testing helper function.
static void	test (void)
	Self-test implementations.
int	main (void)
	Main function.

Detailed Description

McNaughton–Yamada–Thompson algorithm

From Wikipedia: In computer science, Thompson's construction algorithm, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This implementation implements the all three operations (implicit concatenation, '|' for union, '*' for Kleene star) required by the formal definition of regular expressions.

Author

Sharon Cassidy

Function Documentation

addRule()

void addRule	(	struct NFA *	nfa,
		struct transRule *	rule,
		int	loc
	)

adds a transition rule to a NFA

Parameters

nfa	target NFA
rule	the rule to be added
loc	which state this rule should be added to

Returns

void

                                                               {
    nfa->rulePool[nfa->ruleCount++] = rule;
    struct NFAState* state = nfa->statePool[loc];
    state->rules[state->ruleCount++] = rule;
}

addState()

void addState	(	struct NFA *	nfa,
		struct NFAState *	state
	)

adds a state to a NFA

Parameters

nfa	target NFA
state	the NFA state to be added

Returns

void

                                                       {
    nfa->statePool[nfa->stateCount++] = state;
}

buildAST()

struct ASTNode * buildAST

(

const char *

input

)

recursively constructs a AST from a preprocessed regex string

Parameters

input

regex

Returns

pointer to the resulting tree

                                            {
 
    struct ASTNode* node = createNode('\0');
    node->left = NULL;
    node->right = NULL;
    const size_t len = strlen(input);
    size_t index;
 
    // Empty input
    if(len == 0) return node;
 
    // Character literals
    if(len == 1) {
        node->content = input[0];
        return node;
    }
 
    // Discard parentheses
    if(input[0] == '(' && input[len - 1] == ')') {
        char* temp = subString(input, 1, len - 2);
        destroyNode(node);
        node = buildAST(temp);
 
        free(temp);
        return node;
    }
 
    // Union
    index = indexOf(input, '|');
    if(index) {
        node->content = '|';
 
        char* temp1 = subString(input, 0, index - 1);
        char* temp2 = subString(input, index + 1, len - 1);
        node->left = buildAST(temp1);
        node->right = buildAST(temp2);
 
        free(temp2);
        free(temp1);
        return node;
    }
 
    // Concatenation
    index = indexOf(input, '\n');
    if(index) {
        node->content = '\n';
 
        char* temp1 = subString(input, 0, index - 1);
        char* temp2 = subString(input, index + 1, len - 1);
        node->left = buildAST(temp1);
        node->right = buildAST(temp2);
 
        free(temp2);
        free(temp1);
        return node;
    }
 
    // Kleene star
    // Testing with indexOf() is unnecessary here,
    // Since all other possibilities have been exhausted
    node->content = '*';
    char* temp = subString(input, 0, len - 2);
    node->left = buildAST(temp);
    node->right = NULL;
 
    free(temp);
    return node;
}

Here is the call graph for this function:

compileFromAST()

struct NFA * compileFromAST

(

struct ASTNode *

root

)

                                                 {
 
    struct NFA* nfa = createNFA();
 
    // Empty input
    if (root->content == '\0') {
        addRule(nfa, createRule(nfa->statePool[1], '\0'), 0);
        return nfa;
    }
 
    // Character literals
    if (isLiteral(root->content)) {
        addRule(nfa, createRule(nfa->statePool[1], root->content), 0);
        return nfa;
    }
 
    switch (root->content) {
 
        case '\n': {
            struct NFA* ln = compileFromAST(root->left);
            struct NFA* rn = compileFromAST(root->right);
 
            // Redirects all rules targeting ln's accepting state to
            // target rn's starting state
            redirect(ln, ln->statePool[1], rn->statePool[0]);
 
            // Manually creates and initializes a special
            // "wrapper" NFA
            destroyNFA(nfa);
            struct NFA* wrapper = malloc(sizeof(struct NFA));
            wrapper->stateCount = 2;
            wrapper->statePool = malloc(sizeof(struct NFAState*) * 2);
            wrapper->subCount = 0;
            wrapper->subs = malloc(sizeof(struct NFA*) * 2);
            wrapper->ruleCount = 0;
            wrapper->rulePool = malloc(sizeof(struct transRule*) * 3);
            wrapper->CSCount = 0;
            wrapper->currentStates = malloc(sizeof(struct NFAState*) * 2);
            wrapper->wrapperFlag = 1;
            wrapper->subs[wrapper->subCount++] = ln;
            wrapper->subs[wrapper->subCount++] = rn;
 
            // Maps the wrapper NFA's starting and ending states
            // to its sub NFAs
            wrapper->statePool[0] = ln->statePool[0];
            wrapper->statePool[1] = rn->statePool[1];
 
            return wrapper;
        }
        case '|': {
 
            struct NFA* ln = compileFromAST(root->left);
            struct NFA* rn = compileFromAST(root->right);
            nfa->subs[nfa->subCount++] = ln;
            nfa->subs[nfa->subCount++] = rn;
 
            // Adds empty character transition rules
            addRule(nfa, createRule(ln->statePool[0], '\0'), 0);
            addRule(ln, createRule(nfa->statePool[1], '\0'), 1);
            addRule(nfa, createRule(rn->statePool[0], '\0'), 0);
            addRule(rn, createRule(nfa->statePool[1], '\0'), 1);
 
            return nfa;
        }
        case '*': {
            struct NFA* ln = compileFromAST(root->left);
            nfa->subs[nfa->subCount++] = ln;
 
            addRule(ln, createRule(ln->statePool[0], '\0'), 1);
            addRule(nfa, createRule(ln->statePool[0], '\0'), 0);
            addRule(ln, createRule(nfa->statePool[1], '\0'), 1);
            addRule(nfa, createRule(nfa->statePool[1], '\0'), 0);
 
            return nfa;
        }
    }
 
    // Fallback, shouldn't happen in normal operation
    destroyNFA(nfa);
    return NULL;
}

contains()

int contains	(	struct NFAState **	states,
		int	len,
		struct NFAState *	state
	)

helper function to determine an element's presence in an array

Parameters

states	target array
len	length of the target array
state	the element to search for

Returns

1 if the element is present, 0 otherwise

                                                                        {
    int f = 0;
    for (int i = 0; i < len; ++i) {
        if(states[i] == state) {
            f = 1;
            break;
        }
    }
    return f;
}

createNFA()

struct NFA * createNFA

(

void

)

creates and initializes a NFA

Returns

pointer to the newly created NFA

                            {
    struct NFA* nfa = malloc(sizeof(struct NFA));
 
    nfa->stateCount = 0;
    nfa->statePool = malloc(sizeof(struct NFAState*) * 5);
    nfa->ruleCount = 0;
    nfa->rulePool = malloc(sizeof(struct transRule*) * 10);
    nfa->CSCount = 0;
    nfa->currentStates = malloc(sizeof(struct NFAState*) * 5);
    nfa->subCount = 0;
    nfa->subs = malloc(sizeof(struct NFA*) * 5);
    nfa->wrapperFlag = 0;
 
    addState(nfa, createState());
    addState(nfa, createState());
    return nfa;
}

Here is the call graph for this function:

createNode()

struct ASTNode * createNode

(

const char

content

)

creates and initializes a AST node

Parameters

content

data to initializes the node with

Returns

pointer to the newly created node

                                               {
    struct ASTNode* node = malloc(sizeof(struct ASTNode));
    node->content = content;
    node->left = NULL;
    node->right = NULL;
    return node;
}

createRule()

struct transRule * createRule	(	struct NFAState *	state,
		char	c
	)

creates and initializes a transition rule

Parameters

state	transition target
c	transition condition

Returns

pointer to the newly created rule

                                                             {
    struct transRule* rule = malloc(sizeof(struct transRule));
    rule->target = state;
    rule->cond = c;
    return rule;
}

createState()

struct NFAState * createState

(

void

)

creates and initializes a NFA state

Returns

pointer to the newly created NFA state

                                   {
    struct NFAState* state = malloc(sizeof(struct NFAState));
    state->ruleCount = 0;
    state->rules = malloc(sizeof(struct transRule*) * 3);
    return state;
}

destroyNFA()

void destroyNFA

(

struct NFA *

nfa

)

recursively destroys a NFA

Parameters

nfa	pointer to the object to be deleted

Returns

void

                                 {
    for (int i = 0; i < nfa->subCount; ++i) {
        destroyNFA(nfa->subs[i]);
    }
 
    // In case of a wrapper NFA, do not free its states
    // because it doesn't really have any states of its own
    if (!nfa->wrapperFlag) {
        for (int i = 0; i < nfa->stateCount; ++i) {
            destroyState(nfa->statePool[i]);
        }
    }
    for (int i = 0; i < nfa->ruleCount; ++i) {
        destroyRule(nfa->rulePool[i]);
    }
    free(nfa->statePool);
    free(nfa->currentStates);
    free(nfa->rulePool);
    free(nfa->subs);
    free(nfa);
}

Here is the call graph for this function:

destroyNode()

void destroyNode

(

struct ASTNode *

node

)

recursively destroys a AST

Parameters

node	the root node of the tree to be deleted

Returns

void

                                       {
    if(node->left != NULL) {
        destroyNode(node->left);
    }
 
    if(node->right != NULL) {
        destroyNode(node->right);
    }
 
    free(node);
}

Here is the call graph for this function:

destroyRule()

void destroyRule

(

struct transRule *

rule

)

destroys a transition rule object

Parameters

rule	pointer to the object to be deleted

Returns

void

                                         {
    free(rule);
}

destroyState()

void destroyState

(

struct NFAState *

state

)

destroys a NFA state

Parameters

state

pointer to the object to be deleted

Returns

void

                                          {
    free(state->rules);
    free(state);
}

findEmpty()

void findEmpty	(	struct NFAState *	target,
		struct NFAState **	states,
		int *	sc
	)

helper function to manage empty character transitions

Parameters

target	target NFA
states	pointer to results storage location
sc	pointer to results count storage location

Returns

void

                                                                           {
    for (int i = 0; i < target->ruleCount; ++i) {
        const struct transRule *pRule = target->rules[i];
 
        if (pRule->cond == '\0' && !contains(states, *sc, pRule->target)) {
            states[(*sc)++] = pRule->target;
            // the use of `states` and `sc` is necessary
            // to sync data across recursion levels
            findEmpty(pRule->target, states, sc);
        }
    }
}

Here is the call graph for this function:

indexOf()

size_t indexOf	(	const char *	str,
		char	key
	)

utility function to locate the first occurrence of a character in a string while respecting parentheses

Parameters

str	target string
key	the character to be located

Returns

the index of its first occurrence, 0 if it could not be found

                                          {
    int depth = 0;
 
    for (size_t i = 0; i < strlen(str); ++i) {
        const char c = str[i];
 
        if(depth == 0 && c == key) {
            return i;
        }
        if(c == '(') depth++;
        if(c == ')') depth--;
    }
    // Due to the way this function is intended to be used,
    // it's safe to assume the character will not appear as
    // the string's first character
    // thus `0` is used as the `not found` value
    return 0;
}

isAccepting()

int isAccepting

(

const struct NFA *

nfa

)

determines whether the NFA is currently in its accepting state

Parameters

nfa	target NFA

Returns

1 if the NFA is in its accepting state

0 otherwise

                                       {
    for (int i = 0; i < nfa->CSCount; ++i) {
        if(nfa->currentStates[i] == nfa->statePool[1]) {
            return 1;
        }
    }
    return 0;
}

isLiteral()

int isLiteral

(

const char

ch

)

helper function to determine whether a character should be considered a character literal

Parameters

ch	the character to be tested

Returns

1 if it is a character literal

0 otherwise

                             {
    return !(ch == '(' || ch == ')' || ch == '*' || ch == '\n' || ch == '|');
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

               {
    test(); // run self-test implementations
    return 0;
}

Here is the call graph for this function:

postProcessing()

void postProcessing

(

struct NFA *

nfa

)

performs postprocessing on a compiled NFA, add circular empty character transition rules where it's needed for the NFA to function correctly

Parameters

nfa	target NFA

Returns

void

                                     {
    // Since the sub NFA's states and rules are managed
    // through their own pools, recursion is necessary
    for (int i = 0; i < nfa->subCount; ++i) {
        postProcessing(nfa->subs[i]);
    }
 
    // If a state does not have any empty character accepting rule,
    // we add a rule that circles back to itself
    // So this state will be preserved when
    // empty characters are inputted
    for (int i = 0; i < nfa->stateCount; ++i) {
 
        struct NFAState* pState = nfa->statePool[i];
        int f = 0;
        for (int j = 0; j < pState->ruleCount; ++j) {
            if(pState->rules[j]->cond == '\0') {
                f = 1;
                break;
            }
        }
 
        if (!f) {
            addRule(nfa, createRule(pState, '\0'), i);
        }
    }
}

Here is the call graph for this function:

preProcessing()

char * preProcessing

(

const char *

input

)

performs preprocessing on a regex string, making all implicit concatenations explicit

Parameters

input

target regex string

Returns

pointer to the processing result

                                       {
    const size_t len = strlen(input);
    if(len == 0) {
        char* str = malloc(1);
        str[0] = '\0';
        return str;
    }
 
    char* str = malloc(len * 2);
    size_t op = 0;
 
    for (size_t i = 0; i < len - 1; ++i) {
        char c = input[i];
        str[op++] = c;
        // one character lookahead
        char c1 = input[i + 1];
 
        if( (isLiteral(c) && isLiteral(c1)) ||
            (isLiteral(c) && c1 == '(') ||
            (c == ')' && c1 == '(') ||
            (c == ')' && isLiteral(c1)) ||
            (c == '*' && isLiteral(c1)) ||
            (c == '*' && c1 == '(')
                ) {
            // '\n' is used to represent concatenation
            // in this implementation
            str[op++] = '\n';
        }
    }
 
    str[op++] = input[len - 1];
    str[op] = '\0';
    return str;
}

Here is the call graph for this function:

redirect()

void redirect	(	struct NFA *	nfa,
		struct NFAState *	src,
		struct NFAState *	dest
	)

helper function to recursively redirect transition rule targets

Parameters

nfa	target NFA
src	the state to redirect away from
dest	the state to redirect to

Returns

void

                                                                            {
    for (int i = 0; i < nfa->subCount; ++i) {
        redirect(nfa->subs[i], src, dest);
    }
    for (int i = 0; i < nfa->ruleCount; ++i) {
        struct transRule* rule = nfa->rulePool[i];
        if (rule->target == src) {
            rule->target = dest;
        }
    }
}

Here is the call graph for this function:

subString()

char * subString	(	const char *	str,
		size_t	begin,
		size_t	end
	)

utility function to create a subString

Parameters

str	target string
begin	starting index, inclusive
end	ending index, inclusive

Returns

pointer to the newly created subString

                                                           {
    char* res = malloc(end - begin + 2);
    strncpy(res, str + begin, end - begin + 1);
    res[end - begin + 1] = '\0';
    return res;
}

Here is the call graph for this function:

test()

static void test ( void  )

static

Self-test implementations.

Returns

void

                       {
    testHelper("(c|a*b)", "c", 1);
    testHelper("(c|a*b)", "aab", 1);
    testHelper("(c|a*b)", "ca", 0);
    testHelper("(c|a*b)*", "caaab", 1);
    testHelper("(c|a*b)*", "caba", 0);
    testHelper("", "", 1);
    testHelper("", "1", 0);
    testHelper("(0|(1(01*(00)*0)*1)*)*","11",1);
    testHelper("(0|(1(01*(00)*0)*1)*)*","110",1);
    testHelper("(0|(1(01*(00)*0)*1)*)*","1100",1);
    testHelper("(0|(1(01*(00)*0)*1)*)*","10000",0);
    testHelper("(0|(1(01*(00)*0)*1)*)*","00000",1);
 
    printf("All tests have successfully passed!\n");
}

Here is the call graph for this function:

testHelper()

void testHelper	(	const char *	regex,
		const char *	string,
		const int	expected
	)

Testing helper function.

Parameters

regex	the regular expression to be used
string	the string to match against
expected	expected results

Returns

void

                                                                           {
    char* temp = preProcessing(regex);
    struct ASTNode* node = buildAST(temp);
 
    struct NFA* nfa = compileFromAST(node);
    postProcessing(nfa);
 
    // reallocates the outermost NFA's current states pool
    // because it will actually be used to store all the states
    nfa->currentStates = realloc(nfa->currentStates, sizeof(struct NFAState*) * 100);
    // Starts the NFA by adding its starting state to the pool
    nfa->currentStates[nfa->CSCount++] = nfa->statePool[0];
 
    // feeds empty characters into the NFA before and after
    // every normal character
    for (size_t i = 0; i < strlen(string); ++i) {
        transit(nfa, '\0');
        transit(nfa, string[i]);
    }
    transit(nfa, '\0');
 
    assert(isAccepting(nfa) == expected);
 
    destroyNFA(nfa);
    destroyNode(node);
    free(temp);
}

Here is the call graph for this function:

transit()

void transit	(	struct NFA *	nfa,
		char	input
	)

moves a NFA forward

Parameters

nfa	target NFA
input	the character to be fed into the NFA

Returns

void

                                          {
    struct NFAState** newStates = malloc(sizeof(struct NFAState*) * 10);
    int NSCount = 0;
 
    if (input == '\0') {
        // In case of empty character input, it's possible for
        // a state to transit to another state that's more than
        // one rule away, we need to take that into account
        for (int i = nfa->CSCount - 1; i > -1; --i) {
            struct NFAState *pState = nfa->currentStates[i];
            nfa->CSCount--;
 
            struct NFAState** states = malloc(sizeof(struct NFAState*) * 10);
            int sc = 0;
            findEmpty(pState, states, &sc);
 
            for (int j = 0; j < sc; ++j) {
                if(!contains(newStates,NSCount, states[j])) {
                    newStates[NSCount++] = states[j];
                }
            }
            free(states);
        }
    } else {
        // Iterates through all current states
        for (int i = nfa->CSCount - 1; i > -1; --i) {
            struct NFAState *pState = nfa->currentStates[i];
            // Gradually empties the current states pool, so
            // it can be refilled
            nfa->CSCount--;
 
            // Iterates through rules of this state
            for (int j = 0; j < pState->ruleCount; ++j) {
                const struct transRule *pRule = pState->rules[j];
 
                if(pRule->cond == input) {
                    if(!contains(newStates, NSCount, pRule->target)) {
                        newStates[NSCount++] = pRule->target;
                    }
                }
            }
        }
    }
 
    nfa->CSCount = NSCount;
    for (int i = 0; i < NSCount; ++i) {
        nfa->currentStates[i] = newStates[i];
    }
    free(newStates);
}

Here is the call graph for this function: