Implementação enxuta de um parser

parser.c

/*
 * Curso de Bacharelado em Ciência da Computação - IFSul Passo Fundo
 * Compiladores - 2021/1
 * Willian R. Schuck
 * Construção de parser para a gramática:
 *     A' -> A
 *     A  -> (A) | a
 * */

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

/* Definição de estruturas para a manipulação das informações */

typedef struct Entry Entry;
typedef struct State State;
typedef struct Transition Transition;
typedef struct Stack Stack;
typedef struct StackEntry StackEntry;

// O tipo que um nó da pilha pode assumir
typedef enum {
    TERMINAL,
    NON_TERMINAL,
    ACCEPT
} EntryType;

// As ações que o parser pode executar
typedef enum {
    LOAD,
    REDUCE
} Action;

struct Entry {
    EntryType type;
    char data;
};

// String para simplificar a exibição do enum de tipos no terminal
char* sEntryType[] = {
        "TERMINAL",
        "NON_TERMINAL",
        "ACCEPT"
};

// Informações sobre uma transição
struct Transition {
    char onChar;
    EntryType type;
    int toState;
};

// Informações do estado, como suas transições
struct State {
    Transition* transitions;
    int n_of_transitions;
    Entry* reduction;
    int n_of_reduction;
    Entry reduceTo;
    Action action;
};

// Pilha
struct Stack {
    int capacity;
    int current;
    StackEntry* entries;
};

// Entrada da pilha
struct StackEntry {
    int state;
    Entry entry;
};

// Funções para a manipulação da pilha

void InitStack(Stack* stack, StackEntry* entries, int capacity) {
    stack->entries = entries;
    stack->capacity = capacity;
    stack->current = -1;
}

StackEntry* PopStack(Stack* stack) {
    if (stack->current >= 0) {
        StackEntry* e = stack->entries + stack->current;
        stack->current--;
        return e;
    }
    return 0;
}

StackEntry* PeekStack(Stack* stack) {
    if (stack->current >= 0) {
        return stack->entries + stack->current;
    }
    return 0;
}

int PushStack(Stack* stack, Entry* e, int s) {
    if (stack->current == stack->capacity) {
        return 0;
    }
    stack->current++;
    stack->entries[stack->current].entry = *e;
    stack->entries[stack->current].state = s;
    return 1;
}

// Verifica se é possível reduzir a pilha baseado no estado atual
int CanReduce(State *state, Stack *stack) {

    Entry* r = state->reduction; // Entradas da redução, são os caracteres tipados na ordem da regra
    int n_of_r = state->n_of_reduction;

    if (n_of_r-1 > stack->current) {
        return 0;
    }

    // A posição inicial para ser comparado com as entradas da redução
    int pos = stack->current - (n_of_r - 1); // se há apenas uma redução queremos comparar somente o topo ...

    for (int i = 0; i < n_of_r; ++i) {
        Entry e1 = stack->entries[pos+i].entry;
        Entry e2 = r[i];
        if (e1.type != e2.type || e1.data != e2.data) {
            return 0;
        }
    }

    return 1;

}

// Obtém a transição correspondente a entrada, retorna 0 caso não encontre a transição
Transition* TransitionFor(State* state, Entry* entry) {
    Transition* t = state->transitions;
    int size = state->n_of_transitions;
    for (int i = 0; i < size; ++i) {
        if (entry->type == t[i].type && entry->data == t[i].onChar) {
            return (t + i);
        }
    }
    return 0;
}

void PrintStack(Stack *stack) {
    int q = stack->current;
    StackEntry *se = stack->entries;
    for (int i = 0; i <= q; ++i) {
        printf("%c", se[i].entry.data);
        if (se[i].entry.type == ACCEPT) {
            printf("'");
        }
    }
    printf("\n");
}

void PrintReductionRule(State *state) {
    printf("%c%s -> ", state->reduceTo.data, state->reduceTo.type == ACCEPT ? "'" : "" );
    int max = state->n_of_reduction;
    for (int i = 0; i < max; ++i) {
        printf("%c", state->reduction[i].data);
    }
    printf("\n");
}

int main(int argc, char** argv) {

    if (argc != 2) {
        printf("Valor inesperado de argumentos recebidos.\n");
        return 0;
    }

    char* entrada = argv[1];
    int len_entrada = (int) strlen(entrada);
    Entry entries[len_entrada];

    StackEntry stack_entries[len_entrada];
    Stack stack;
    InitStack(&stack, stack_entries, len_entrada);

    int cur_state = 0;
    int cur_entry = 0;

    // Inicialização dos estados

    State state[6];

    Transition t_0[] = {
            {'(', TERMINAL, 3},
            {'a', TERMINAL, 2},
            {'A', NON_TERMINAL, 1}
    };
    state[0].action = LOAD;
    state[0].transitions = t_0;
    state[0].n_of_transitions = sizeof(t_0)/sizeof(Transition);


    state[1].action = REDUCE;
    Entry r_1[] = {
            { NON_TERMINAL, 'A'}
    };
    Entry rto_1 = {ACCEPT, 'A'};
    state[1].reduction = r_1;
    state[1].reduceTo = rto_1;
    state[1].n_of_reduction = sizeof(r_1)/sizeof(Entry);


    state[2].action = REDUCE;
    Entry r_2[] = {
            {TERMINAL, 'a'}
    };
    Entry rto_2 = {NON_TERMINAL, 'A'};
    state[2].reduction = r_2;
    state[2].n_of_reduction = sizeof(r_2)/sizeof(Entry);
    state[2].reduceTo = rto_2;


    Transition t_3[] = {
            {'(', TERMINAL, 3},
            {'a', TERMINAL, 2},
            {'A', NON_TERMINAL, 4}
    };
    state[3].action = LOAD;
    state[3].transitions = t_3;
    state[3].n_of_transitions = sizeof(t_3)/sizeof(Transition);


    Transition t_4[] = {
            {')', TERMINAL, 5}
    };
    state[4].action = LOAD;
    state[4].transitions = t_4;
    state[4].n_of_transitions = sizeof(t_4)/sizeof(Transition);


    state[5].action = REDUCE;
    Entry r_5[] = {
            {TERMINAL, '('},
            {NON_TERMINAL, 'A'},
            {TERMINAL, ')'}
    };
    Entry rto_5 = {NON_TERMINAL, 'A'};
    state[5].reduction = r_5;
    state[5].n_of_reduction = sizeof(r_5)/sizeof(Entry);
    state[5].reduceTo = rto_5;

    // Converte os caracteres para terminais de entrada;

    for (int i = 0; i < len_entrada; ++i) {
        entries[i].type = TERMINAL;
        entries[i].data = entrada[i];
    }

    int passo = 1;

    // Loop de processamento

    while (1) {

        printf("PASSO: %d\n", passo++);

        if (cur_state >5 || cur_state < 0) {
            printf("ERRO FATAL: Estado inválido (%d)", cur_state);
            printf("ENTRADA: %s\n", entrada);
            break;
        }

        switch (state[cur_state].action) {
            case LOAD: {

                if (cur_entry == len_entrada) {
                    printf("ERRO: Não foi possível realizar o LOAD pois o fim da cadeia de entrada foi atingido\n");
                    printf("ENTRADA: %s\n", entrada);
                    return 1;
                }

                Transition *t = TransitionFor(&state[cur_state], &entries[cur_entry]);
                if (t) { // Se encontrou uma transição adiciona a entrada na stack
                    printf("LOAD: Saindo do estado %d e carregando o estado %d com a entrada ('%c', %s) na pilha.\n", cur_state, t->toState, entries[cur_entry].data, sEntryType[entries[cur_entry].type]);
                    PushStack(&stack, &entries[cur_entry++], (cur_state = t->toState));
                } else { // Caso não encontre a transição exibe o erro
                    printf("ERRO: Caractere inesperado %c na posição %d\n", entries[cur_entry].data, cur_entry);
                    printf("ENTRADA: %s\n", entrada);
                    return 1;
                }
                break;
            }

            case REDUCE: {

                int can_reduce = CanReduce(&state[cur_state], &stack); // Verifica se pode reduzir

                if (can_reduce) {

                    printf("REDUCE: Reduzindo a pilha através da regra: ");
                    PrintReductionRule(&state[cur_state]); // Exibe a regra de redução deste estado

                    Entry reduceTo = state[cur_state].reduceTo; // Entrada resultante da redução

                    int r = state[cur_state].n_of_reduction;
                    for (int i = 0; i < r; ++i) { // Sabemos que é possível reduzir, portanto podemos eliminar os r nós da stack
                        PopStack(&stack);
                    }

                    StackEntry* topo = PeekStack(&stack);
                    cur_state = topo ? topo->state : 0; // Obtém o estado do topo da stack, 0 caso a stack estiver vazia

                    if (reduceTo.type == ACCEPT) {
                        if (cur_entry == len_entrada) { // Se chegou na aceitação e não há mais nada na entrada, o processamento foi concluído com sucesso
                            PushStack(&stack, &reduceTo, (cur_state));
                            printf("ACEITA\nSTACK: ");
                            printf("ENTRADA: %s\n", entrada);
                            PrintStack(&stack); // Exibe a stack
                            return 0;
                        }
                        printf("ERRO: Cadeia foi reduzida completamente porém restaram valores na entrada a partir da posição %d\n", cur_entry);
                        printf("ENTRADA: %s\n", entrada);
                        return 1;
                    }

                    // Verifica se o estado atual possui a transição para a entrada resultante
                    Transition *t = TransitionFor(&state[cur_state], &reduceTo);
                    if (t) {
                        PushStack(&stack, &reduceTo, (cur_state = t->toState));
                    } else {
                        printf("ERRO: Caractere inesperado %c na posição %d\n", entries[cur_entry].data, cur_entry);
                        printf("ENTRADA: %s\n", entrada);
                        return 3;
                    }

                } else {
                    printf("ERRO: Não foi possível realizar a redução.\n");
                    PrintReductionRule(&state[cur_state]);
                    return 2;
                }

                break;
            }

        }

    }

    return 0;
}