Simplified Compiled Regex [PoliTo APA Lab4 Es3]

regexp.c

/**
 *                                               Lab4 Es3:
 *                                  Valutazione di espressioni regolari
 *  I problemi di ricerca di stringe all’interno di testi e/o collezioni di stringhe (solitamente di
 *  dimensione maggiore rispetto alla stringa cercata) si basano raramente su un confronto esatto, ma
 *  molto spesso necessitano di rappresentare in modo compatto non una, ma un insieme di stringhe
 *  cercate, evitandone per quanto possibile l’enumerazione esplicita.
 *  Le espressioni regolari sono una notazione molto utilizzata per rappresentare (in modo compatto)
 *  insiemi di stringhe correlate tra loro (ad esempio aventi una parte comune).
 *  Una espressione regolare (o regexp) è una sequenza di simboli (quindi una stringa) che identifica
 *  un insieme di stringhe. Si scriva una funzione in C in grado di individuare (cercare) eventuali
 *  occorrenze di una data regexp all'interno di una stringa di input.
 *
 *  La funzione sia caratterizzata dal seguente prototipo:
 *      char *cercaRegexp(char *src, char *regexp);
 *  dove:
 *      - il parametro src rappresenta la stringa sorgente in cui cercare.
 *      - il parametro regexp rappresenta l'espressione regolare da cercare.
 *      - il valore di ritorno della funzione è un puntatore alla prima occorrenza di regexp in src
 *        (NULL se non trovata).
 *
 *  Ai fini dell'esercizio si consideri di valutare solamente stringhe composte da caratteri alfabetici. Si
 *  considerino inoltre solamente espressioni regolari composte da caratteri alfabetici e dai seguenti
 *  metacaratteri:
 *      - . trova un singolo carattere (cioè qualunque carattere può corrispondere a un punto)
 *      - [] trova un singolo carattere contenuto nelle parentesi (cioè uno qualsiasi dei caratteri tra
 *        parentesi va bene)
 *      - [^ ] trova ogni singolo carattere non contenuto nelle parentesi (cioè tutti i caratteri tra
 *        parentesi non vanno bene)
 *      - \a trova un carattere minuscolo
 *      - \A trova un carattere maiuscolo
 *
 *  Esempi di espressioni regolari:
 *      - .oto corrisponde a ogni stringa di quattro caratteri terminante con “oto”, es. "voto", "noto",
 *        "foto", ...
 *      - [mn]oto rappresenta solamente "moto" e "noto"
 *      - [^f]oto rappresenta tutte le stringhe terminanti in “oto” ad eccezione di "foto"
 *      - \aoto rappresenta ogni stringa di quattro caratteri (come "voto", "noto", "foto", ... ) iniziante
 *        per lettere minuscola e terminante in “oto”
 *      - \Aoto rappresenta ogni stringa di quattro caratteri (come "Voto", "Noto", "Foto", ...) iniziante
 *        per lettere maiuscola e terminante in “oto”.
 *  NOTA: i metacaratteri possono apparire in qualsiasi punto dell'espressione regolare. I casi qui sopra
 *  sono solo una minima parte a titolo di esempio. Sono quindi espressioni regolari valide:
 *      A[^f]\anR.d, \A[aeiou]5t[123], ecc.
 *
 *  @author Marco Montanari (08/04/2022)
 */

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

#define MAX_REGEX 50
#define MAX_MATCH_LITERALS 50
#define MAX_MATCH_WORD 50

/**
 * Types:
 *       - 0: (literal) match di $value
 *       - 1: (.) match di qualunque carattere
 *       - 2: ([abc]) match di uno dei caratteri in $value
 *       - 3: ([^abc]) anti match di uno dei caratteri in $value
 *       - 4: (\a o \A) carattere minuscolo se $value = 'a', maiuscolo se $value = 'A'
 */
struct regexp {
    int type;
    char *value;
};

int compile(struct regexp *dest, const char *src);

char *find(const char *src, struct regexp *exps, int length);

// Come lo vuole l'esercizio
char *cercaRegexp(char *src, char *regexp) {
    struct regexp exps[MAX_REGEX];
    int length = compile(exps, regexp);
    return find(src, exps, length);
}

void printRegex(struct regexp *exps, int length);

void testRegexp(const char *src, const char *string);

int main() {
//    struct regexp exps[MAX_REGEX];
//    int length = compile(exps, ".oto");
//
//    printRegex(exps, length);

    //.oto corrisponde a ogni stringa di quattro caratteri terminante con “oto”, es. "voto", "noto",
    //"foto", ...
    testRegexp(".oto", "voto");
    testRegexp(".oto", "moto");
    testRegexp(".oto", "noto");
    testRegexp(".oto", "foto");
    //[mn]oto rappresenta solamente "moto" e "noto"
    testRegexp("[mn]oto", "voto");
    testRegexp("[mn]oto", "moto");
    testRegexp("[mn]oto", "noto");
    testRegexp("[mn]oto", "foto");
    //[^f]oto rappresenta tutte le stringhe terminanti in “oto” ad eccezione di "foto"
    testRegexp("[^f]oto", "voto");
    testRegexp("[^f]oto", "moto");
    testRegexp("[^f]oto", "noto");
    testRegexp("[^f]oto", "foto");
    //\aoto rappresenta ogni stringa di quattro caratteri (come "voto", "noto", "foto", ... ) iniziante
    //per lettere minuscola e terminante in “oto”
    testRegexp("\\aoto", "voto");
    testRegexp("\\aoto", "moto");
    testRegexp("\\aoto", "Noto");
    testRegexp("\\aoto", "Foto");
    //\Aoto rappresenta ogni stringa di quattro caratteri (come "Voto", "Noto", "Foto", ...) iniziante
    //per lettere maiuscola e terminante in “oto”.
    testRegexp("\\Aoto", "voto");
    testRegexp("\\Aoto", "moto");
    testRegexp("\\Aoto", "Noto");
    testRegexp("\\Aoto", "Foto");

    return 0;
}

void testRegexp(const char *src, const char *string) {
    struct regexp exps[MAX_REGEX];
    int length = compile(exps, src);

    char *result = find(string, exps, length);
    if (result) {
        printf("'%s' found in '%s': '%s'\n", src, string, result);
    } else {
        printf("'%s' not found in '%s'\n", src, string);
    }
}

void printRegex(struct regexp *exps, int length) {
    for (int i = 0; i < length; ++i) {
        printf("[%d]: %s\n", exps[i].type, exps[i].value ? exps[i].value : "NULL");
    }
}

int compile(struct regexp *dest, const char *src) {
    int length = 0;
    struct regexp *builder = NULL;
    for (int p = 0; src[p] != '\0'; ++p) {
        char c = src[p];

        if (builder) {
            switch (builder->type) {
                case 2:
                case 3:
                    switch (c) {
                        case ']':
                            dest[length] = *builder;
                            builder = NULL;

                            ++length;

                            break;
                        case '^':
                            builder->type = 3;

                            break;
                        default: {
                            int lastLiteral = strlen(builder->value);
                            builder->value[lastLiteral] = c;
                            builder->value[lastLiteral + 1] = '\0';
                        }
                    }

                    break;
                case 4:
                    // 4: (\a o \A) carattere minuscolo se $value = 'a', maiuscolo se $value = 'A'
                    builder->value = malloc(sizeof(char) * 2);
                    builder->value[0] = c;
                    builder->value[1] = '\0';

                    dest[length] = *builder;
                    builder = NULL;

                    ++length;

                    break;
            }

            continue;
        }

        switch (c) {
            case '.':
                // 1: (.) match di qualunque carattere
                dest[length].type = 1;

                ++length;

                break;
            case '[':
                // 2: ([abc]) match di uno dei caratteri in $value
                // 3: ([^abc]) anti match di uno dei caratteri in $value
                builder = malloc(sizeof(struct regexp));
                builder->type = 2;
                builder->value = malloc(sizeof(char) * MAX_MATCH_LITERALS);
                builder->value[0] = '\0';

                break;
            case '\\':
                // 4: (\a o \A) carattere minuscolo se $value = 'a', maiuscolo se $value = 'A'
                builder = malloc(sizeof(struct regexp));
                builder->type = 4;

                break;
            default:
                // 0: (literal) match di $value
                dest[length].type = 0;
                dest[length].value = malloc(sizeof(char) * 2);
                dest[length].value[0] = c;
                dest[length].value[1] = '\0';

                ++length;
        }
    }

    return length;
}

char *find(const char *src, struct regexp *exps, int length) {
    if (length == 0) {
        return NULL;
    }

    int occurrences = 0;
    char *match = malloc(sizeof(char) * MAX_MATCH_WORD);
    int matchLength = 0;
    for (int p = 0; src[p] != '\0'; ++p) {
        char c = src[p];
        struct regexp exp = exps[occurrences];
        int found = 0;
        switch (exp.type) {
            case 0:
                // 0: (literal) match di $value
                found = c == exp.value[0];

                break;
            case 1:
                // 1: (.) match di qualunque carattere
                found = 1;

                break;
            case 2:
                // 2: ([abc]) match di uno dei caratteri in $value
                for (int v = 0; exp.value[v] != '\0'; ++v) {
                    if (c == exp.value[v]) {
                        found = 1;
                        break;
                    }
                }

                break;
            case 3:
                // 3: ([^abc]) anti match di uno dei caratteri in $value
                found = 1;
                for (int v = 0; exp.value[v] != '\0'; ++v) {
                    if (c == exp.value[v]) {
                        found = 0;
                        break;
                    }
                }

                break;
            case 4:
                // 4: (\a o \A) carattere minuscolo se $value = 'a', maiuscolo se $value = 'A'
                found = exp.value[0] == 'a' ? islower(c) : isupper(c);

                break;
            default:
                printf("ERROR: RegExp type '%d' not valid.\n", exp.type);
                exit(1);
        }

        if (!found) {
            occurrences = 0;
            matchLength = 0;
            match[0] = '\0';
            continue;
        }

        match[matchLength++] = c;
        if (++occurrences == length) {
            match[matchLength] = '\0';
            return match;
        }
    }

    return NULL;
}