working lr0 table generation

1 files changed, 154 insertions, 57 deletions

diff --git a/lr0.c b/lr0.c
index 34b7a22..ecd12b5 100644
--- a/lr0.c
+++ b/lr0.c
@@ -1,7 +1,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 
-#define ARR_LEN(a) (sizeof(a) / sizeof(*a))
+#define ARR_LEN(...) (sizeof(__VA_ARGS__) / sizeof(*(__VA_ARGS__)))
 
 enum symbol {
     PLUS = 0,
@@ -31,19 +31,15 @@ static struct production grammar[] = {
     PROD(E, -->, E, PLUS, T),
     PROD(E, -->, E, MINUS, T),
     PROD(E, -->, T),
-    PROD(T, -->, T, LPAREN, E, RPAREN),
+    PROD(T, -->, LPAREN, E, RPAREN),
     PROD(T, -->, N),
     PROD(N, -->, N0),
     PROD(N, -->, N1),
 };
 
-static int follow[SYMBOL_COUNT][SYMBOL_COUNT];
-void fill_follow_table();
-
 void print_grammar()
 {
-    for(size_t i = 0; i < ARR_LEN(grammar); i++)
-    {
+    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]);
@@ -51,6 +47,21 @@ void print_grammar()
     }
 }
 
+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 {
@@ -61,51 +72,75 @@ struct action {
     size_t arg;
 };
 
-static struct action *(table[SYMBOL_COUNT]);
+// 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)
+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)
 {
-    if(i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) return 1;
+    printf("{");
+    for(size_t i = 0; i < nset; i++)
+        printf("{%zu, %zu}, ", set[i].prod_idx, set[i].dot);
+    printf("}\n");
 }
 
-// TODO: check bounds
+#define SEEN_SETS_CAP 64
 static struct {
     struct item *items;
     size_t nitems;
     size_t state;
-} seen_sets[100];
+} 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 fill_table(size_t state, struct item *initial_set, size_t ninitial);
-void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout);
-    
-#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1)
+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)
 {
-    struct item i[] = {{1, 2}};
-    struct item o[16];
-    size_t no = ARR_LEN(o);
+    fill_follow_table();
     
-    closure(i, ARR_LEN(i), o, &no);
-    (no > ARR_LEN(o)) && DIE();
-
-    for(int i = 0; i < no; i++) {
-        printf("%d %d\n", o[i].prod_idx, o[i].dot);
-    }
+    handle_set((struct item[]){{0, 0}}, 1);
+    print_table();
+    
+    free_seen_sets();
 }
 
 size_t handle_set(struct item *set, size_t nset)
 {
-    // is set in seen_sets
+    // 1. is set in seen_sets
     for(size_t i = 0; i < nseen_sets; i++) {
         if(seen_sets[i].nitems != nset) continue;
         
@@ -113,36 +148,52 @@ size_t handle_set(struct item *set, size_t nset)
         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[j], &set[k])) _seen = 1;
+                if(items_eq(&seen_sets[i].items[k], &set[j])) _seen = 1;
             if(!_seen) break;
         }
         if(_seen) return seen_sets[i].state;
     }
 
-    // add set to seen_sets
-    // TODO: check calloc
-    seen_sets[nseen_sets].items = calloc(nset, sizeof(*set));
+    // 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);
+    }
     
-    fill_table(new_state, set, nset) && DIE();
     return new_state;
 }
 
-int fill_table(size_t state, struct item *initial_set, size_t ninitial)
-{    
-    struct item closure_set[100];
-    size_t nclosure = 100;
+#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;
+    }
     
-    closure(initial_set, ninitial, closure_set, &nclosure);
-    if(nclosure > 100) return 1;
-
     for(size_t sym = 0; sym < SYMBOL_COUNT; sym++) {
-        // TOOD: check goto bounds
-        struct item goto_set[100];
+        struct item goto_set[GOTO_SET_CAP];
         size_t ngoto = 0; 
         
         for(size_t j = 0; j < nclosure; j++) {
@@ -150,38 +201,50 @@ int fill_table(size_t state, struct item *initial_set, size_t ninitial)
             size_t dot = closure_set[j].dot;
             
             if(dot == p->nRHS) {
-                // if(follow[p->LHS][sym]) {
-                //     //add reduction
-                // }
+                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);
 
-        // TODO: check table bounds
-        // TODO: check if table state is already set
-        table[state][sym] = (struct action){
-            is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO,
-            new_state};
+        if(table_insert(state, sym, (struct action){
+                    is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO,
+                    new_state})) return 1;
     }
+    
+    return 0;
 }
 
-void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout)
+size_t closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout_max)
 {
-    size_t nout_max = *nout;
-    *nout = nin;
+    size_t nout = nin;
     
-    if(*nout > nout_max) return;
+    if(nout > nout_max) return nout;
     for(size_t i = 0; i < nin; i++) out_set[i] = in_set[i];
 
-    int *is_in_closure = calloc(ARR_LEN(grammar), sizeof(int));
-    for(size_t i = 0; i < *nout; 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;
@@ -192,16 +255,50 @@ void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout
                 if(is_in_closure[j]) continue;
                 is_in_closure[j] = 1;
 
-                if(*nout >= nout_max) goto cleanup;
-                out_set[(*nout)++] = (struct item){j, 0};
+                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()
 {
-    1 && DIE();
+    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;
 }