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

#ifndef XCALLOC_IMPLEMENTED
#define XCALLOC_IMPLEMENTED
void *xcalloc(size_t n, size_t size) { void *addr = calloc(n, size); return addr ? addr : (exit(1), NULL); }
#else
extern void *xcalloc(size_t n, size_t size);
#endif

// Requirements
#include "parts/symbol.h"
#include "parts/grammar.h"

// Implements
#include "parts/util-tables.h"

int **follow;
int **first;

void util_tables_fill()
{
    follow = calloc(total_symbols, sizeof(*follow));
    first = calloc(total_symbols, sizeof(*follow));
    for(size_t i = 0; i < total_symbols; i++) {
        follow[i] = xcalloc(total_symbols, sizeof(*follow[i]));
        first[i] = xcalloc(total_symbols, sizeof(*follow[i]));
    }
    
    for(size_t sym = 0; sym < total_symbols; sym++) {
        first[sym][sym] = 1;
    }
        
    for(size_t i = 0; i < total_productions; i++) {
        struct production *p = &grammar[i];
        
        first[p->LHS][p->RHS[0]] = 1;
        
        for(size_t j = 1; j < p->nRHS; j++)
            follow[p->RHS[j-1]][p->RHS[j]] = 1;
    }
    
#define set(e) if((e) != 1) changed = (e) = 1

    int changed;
    do {
        changed = 0;
        for(size_t i = 0; i < total_productions; i++)
            for(size_t sym = 0; sym < total_symbols; sym++) {
                struct production *p = &grammar[i];
                if(first[sym][p->LHS])
                    for(size_t j = 0; j < total_symbols; j++)
                        if(first[p->LHS][j]) set(first[sym][j]);
                if(follow[p->LHS][sym])
                    set(follow[p->RHS[p->nRHS-1]][sym]);
                if(follow[sym][p->LHS])
                    set(follow[sym][p->RHS[0]]);
            }
    } while(changed);
}

void util_tables_free()
{
    for(size_t i = 0; i < total_symbols; i++) {
        free(follow[i]);
        free(first[i]);
    }
    
    free(follow);
    free(first);
}

void util_tables_print()
{
    char *s1 = "-- FIRST --";
    printf("    %*s%s\n", (int)((total_symbols*3) - strlen(s1))/2, "", s1);
    
    printf("    ");
    for(size_t i = 0; i < total_symbols; i++) printf("%2zu ", i);
    printf("\n");

    for(size_t i = 0; i < total_symbols; i++) {
        printf("%2zu  ", i);
        for(size_t j = 0; j < total_symbols; j++)
            printf(" %s ", first[i][j] ? "x" : " ");
        printf("\n");
    }

    printf("\n");
    
    char *s2 = "-- FOLLOW --";
    printf("    %*s%s\n", (int)((total_symbols*3) - strlen(s2))/2, "", s2);

    printf("    ");
    for(size_t i = 0; i < total_symbols; i++) printf("%2zu ", i);
    printf("\n");

    for(size_t i = 0; i < total_symbols; i++) {
        printf("%2zu  ", i);
        for(size_t j = 0; j < total_symbols; j++)
            printf(" %s ", follow[i][j] ? "x" : " ");
        printf("\n");
    }
}

#ifdef _UTIL_TABLES_STANDALONE

// implement symbol.h
enum symbol {
    PLUS = 0,
    MINUS,
    LPAREN,
    RPAREN,
    N0, N1,
    END_INPUT,

    EP, E, T, N,
    SYMBOLS_END,
};

const size_t total_symbols = SYMBOLS_END;

int symbol_is_terminal(symbol s)    { return s < E; }
int symbol_is_nonterminal(symbol s) { return s >= E; }
int symbol_is_input_end(symbol s)   { return s == END_INPUT; }

// implement grammar.h
#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol)}
struct production grammar[] = {
    PROD(EP, ->, E, END_INPUT),
    PROD(E, -->, E, PLUS, T),
    PROD(E, -->, E, MINUS, T),
    PROD(E, -->, T),
    PROD(T, -->, LPAREN, E, RPAREN),
    PROD(T, -->, N),
    PROD(N, -->, N0),
    PROD(N, -->, N1),
};

const size_t total_productions = sizeof(grammar)/sizeof(*grammar);

int main(void)
{
    util_tables_fill();
    util_tables_print();
    util_tables_free();
    return 0;
}

#endif