make lr0 and lexer modular

1 files changed, 0 insertions, 304 deletions

diff --git a/lr0.c b/lr0.c
deleted file mode 100644
index ecd12b5..0000000
--- a/lr0.c
+++ /dev/null
@@ -1,304 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-
-#define ARR_LEN(...) (sizeof(__VA_ARGS__) / sizeof(*(__VA_ARGS__)))
-
-enum symbol {
-    PLUS = 0,
-    MINUS,
-    LPAREN,
-    RPAREN,
-    N0, N1,
-    END_INPUT,
-    
-    EP, E, T, N,
-    SYMBOL_COUNT,
-};
-
-static inline int is_terminal(enum symbol s)    { return s < E; }
-static inline int is_nonterminal(enum symbol s) { return s >= E; }
-
-struct production {
-    enum symbol LHS;
-    enum symbol *RHS;
-    size_t nRHS;
-};
-
-#define PROD(LHS, _, ...) {LHS, (enum symbol[]){__VA_ARGS__}, sizeof((enum symbol[]){__VA_ARGS__})/sizeof(enum symbol)}
-
-static 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),
-};
-
-void print_grammar()
-{
-    for(size_t i = 0; i < ARR_LEN(grammar); i++) {
-        printf("%d --> ", grammar[i].LHS);
-        for(size_t j = 0; j < grammar[i].nRHS; j++)
-            printf("%d ", grammar[i].RHS[j]);
-        printf("\n");
-    }
-}
-
-static int follow[SYMBOL_COUNT][SYMBOL_COUNT];
-void fill_follow_table();
-void print_follow_table()
-{
-    printf("    ");
-    for(size_t i = 0; i < SYMBOL_COUNT; i++) printf("%2zu ", i);
-    printf("\n");
-    
-    for(size_t i = 0; i < SYMBOL_COUNT; i++) {
-        printf("%2zu  ", i);
-        for(size_t j = 0; j < SYMBOL_COUNT; j++)
-            printf(" %s ", follow[i][j] ? "x" : " ");
-        printf("\n");
-    }    
-}
-
-struct action {
-    enum action_type {
-        ACTION_NOT_SET = 0, ACTION_SHIFT,
-        ACTION_GOTO, ACTION_REDUCE,
-        ACTION_ACCEPT
-    } type;
-    size_t arg;
-};
-
-// THIS IS BAD, DONT DO IT LIKE THAT
-#define TABLE_CAP 64
-static struct action table[TABLE_CAP][SYMBOL_COUNT];
-// DO IT LIKE THAT
-// static struct action *(table[SYMBOL_COUNT]);
-static size_t states;
-
-int table_insert(size_t state, enum symbol sym, struct action a);
-void print_table()
-{
-    printf("    ");
-    for(size_t sym = 0; sym < SYMBOL_COUNT; sym++) printf("%2zu  ", sym);
-    printf("\n");
-
-    char action_to_char[] = {[ACTION_SHIFT] = 's', [ACTION_REDUCE] = 'r', [ACTION_GOTO] = 'g'};
-    for(size_t i = 0; i < states; i++) {
-        printf("%2zu  ", i);
-        for(size_t sym = 0; sym < SYMBOL_COUNT; sym++)
-            if(table[i][sym].type == ACTION_ACCEPT) printf(" a  ");
-            else if(table[i][sym].type) printf("%c%-2zu ", action_to_char[table[i][sym].type], table[i][sym].arg);
-            else printf("    ");
-        printf("\n");
-    }
-}
-
-
-struct item {
-    size_t prod_idx;
-    size_t dot;
-};
-
-int items_eq(struct item *i1, struct item *i2) { return (i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) ? 1 : 0; }
-void print_set(struct item *set, size_t nset)
-{
-    printf("{");
-    for(size_t i = 0; i < nset; i++)
-        printf("{%zu, %zu}, ", set[i].prod_idx, set[i].dot);
-    printf("}\n");
-}
-
-#define SEEN_SETS_CAP 64
-static struct {
-    struct item *items;
-    size_t nitems;
-    size_t state;
-} seen_sets[SEEN_SETS_CAP];
-static size_t nseen_sets;
-
-void free_seen_sets() { for(size_t i = 0; i < nseen_sets; i++) free(seen_sets[i].items);}
-
-size_t handle_set(struct item *set, size_t nset);
-int insert_set(size_t state, struct item *initial_set, size_t ninitial);
-size_t closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout);
-
-void *xcalloc(size_t n, size_t size) { void *addr = calloc(n, size); return addr ? addr : (exit(1), NULL); }
-
-int main(void)
-{
-    fill_follow_table();
-    
-    handle_set((struct item[]){{0, 0}}, 1);
-    print_table();
-    
-    free_seen_sets();
-}
-
-size_t handle_set(struct item *set, size_t nset)
-{
-    // 1. is set in seen_sets
-    for(size_t i = 0; i < nseen_sets; i++) {
-        if(seen_sets[i].nitems != nset) continue;
-        
-        int _seen = 0;
-        for(size_t j = 0; j < nset; j++) {
-            _seen = 0;
-            for(size_t k = 0; k < nset; k++)
-                if(items_eq(&seen_sets[i].items[k], &set[j])) _seen = 1;
-            if(!_seen) break;
-        }
-        if(_seen) return seen_sets[i].state;
-    }
-
-    // 2. add set to seen_sets
-    if(nseen_sets >= SEEN_SETS_CAP) {
-        fprintf(stderr, "ERROR: SEEN_SET_CAP exceeded\n");
-        exit(1);                 
-    }
-    
-    seen_sets[nseen_sets].items = xcalloc(nset, sizeof(*set));
-    seen_sets[nseen_sets].nitems = nset;
-    for(size_t i = 0; i < nset; i++)
-        seen_sets[nseen_sets].items[i] = set[i];
-
-    // 3. insert new state
-    size_t new_state = seen_sets[nseen_sets++].state = states++;
-    if(new_state >= TABLE_CAP) {
-        fprintf(stderr, "ERROR: TABLE_CAP exceeded\n");
-        exit(1);
-    }
-
-    if(insert_set(new_state, set, nset)) {
-        fprintf(stderr, "ERROR: insert_set failed\n");
-        exit(1);
-    }
-    
-    return new_state;
-}
-
-#define CLOSURE_SET_CAP 64
-#define GOTO_SET_CAP 32
-int insert_set(size_t state, struct item *initial_set, size_t ninitial)
-{
-    struct item closure_set[CLOSURE_SET_CAP];
-    
-    size_t nclosure = closure(initial_set, ninitial, closure_set, CLOSURE_SET_CAP);
-    if(nclosure > CLOSURE_SET_CAP) {
-        fprintf(stderr, "ERROR: CLOSURE_SET_CAP exceeded\n");
-        return 1;
-    }
-    
-    for(size_t sym = 0; sym < SYMBOL_COUNT; sym++) {
-        struct item goto_set[GOTO_SET_CAP];
-        size_t ngoto = 0; 
-        
-        for(size_t j = 0; j < nclosure; j++) {
-            struct production *p = &grammar[closure_set[j].prod_idx];
-            size_t dot = closure_set[j].dot;
-            
-            if(dot == p->nRHS) {
-                if(!follow[p->LHS][sym]) continue;
-                if(table_insert(state, sym, (struct action){
-                            ACTION_REDUCE, closure_set[j].prod_idx}))
-                    return 1;
-                continue;
-            }
-            
-            if(p->RHS[dot] == sym) {
-                if(ngoto >= GOTO_SET_CAP) {
-                    fprintf(stderr, "ERROR: GOTO_SET_CAP exceeded\n");
-                    return 1;
-                } 
-                goto_set[ngoto] = closure_set[j];
-                goto_set[ngoto++].dot++;
-            }
-        }
-
-        if(ngoto == 0) continue;
-        
-        if(sym == END_INPUT) {
-            if(table_insert(state, sym, (struct action){ACTION_ACCEPT, 0}))
-                return 1;
-            continue;
-        }
-        
-        size_t new_state = handle_set(goto_set, ngoto);
-
-        if(table_insert(state, sym, (struct action){
-                    is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO,
-                    new_state})) return 1;
-    }
-    
-    return 0;
-}
-
-size_t closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout_max)
-{
-    size_t nout = nin;
-    
-    if(nout > nout_max) return nout;
-    for(size_t i = 0; i < nin; i++) out_set[i] = in_set[i];
-
-    int *is_in_closure = xcalloc(ARR_LEN(grammar), sizeof(int));
-    for(size_t i = 0; i < nout; i++)
-    {
-        struct production *p = &grammar[out_set[i].prod_idx];
-        if(out_set[i].dot == p->nRHS) continue;
-        enum symbol sym = p->RHS[out_set[i].dot];
-        
-        for(size_t j = 0; j < ARR_LEN(grammar); j++)
-            if(grammar[j].LHS == sym) {
-                if(is_in_closure[j]) continue;
-                is_in_closure[j] = 1;
-
-                if(nout++ >= nout_max) goto cleanup;
-                out_set[nout-1] = (struct item){j, 0};
-            }
-    }
-
-cleanup:
-    free(is_in_closure);
-    return nout;
-}
-
-void fill_follow_table()
-{
-    for(size_t i = 0; i < ARR_LEN(grammar); i++) {
-        struct production *p = &grammar[i];
-        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 < ARR_LEN(grammar); i++) 
-            for(size_t sym = 0; sym < SYMBOL_COUNT; sym++) {
-                struct production *p = &grammar[i];
-                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);
-}
-
-int table_insert(size_t state, enum symbol sym, struct action a)
-{
-    if(table[state][sym].type != ACTION_NOT_SET) {
-        fprintf(stderr, "TABLE COLLISION on state '%zu' sym '%d'\n", state, sym);
-        fprintf(stderr, "\t{%d %zu} vs {%d %zu}",
-                table[state][sym].type, table[state][sym].arg,
-                a.type, a.arg);
-        return 1;
-    }
-    
-    table[state][sym] = a;
-    return 0;
-}