untested precednece lol

12 files changed, 129 insertions, 64 deletions

diff --git a/build.sh b/build.sh
index 8150542..c909bce 100755
--- a/build.sh
+++ b/build.sh
@@ -30,14 +30,14 @@ function leak
 # cc util/dict -D_DICT_STANDALONE
 # leak dict
 
-# cc demos/lexer -D_LEXER_STANDALONE
+# cc demos/lexer util/dict.c
 # leak lexer
 
-# leak recursive-ascent
 # cc recursive/recursive-ascent
+# leak recursive-ascent
 
-# leak recursive-ascent-descent
 # cc recursive/recursive-ascent-descent
+# leak recursive-ascent-descent
 
 # cc util-tables -D_UTIL_TABLES_STANDALONE
 # leak util-tables
@@ -61,10 +61,10 @@ function leak
 
 cc demos/generate-parser "-rdynamic"
 
-shared slr-table
-shared clr-table
+# shared slr-table
+# shared clr-table
 shared clr-table -D_LAZY_LALR lalr-table
-shared demos/sample-files/lalr-defs
+# shared demos/sample-files/lalr-defs
 
 # --- Arithemitc example ---
 # shared demos/sample-files/arithmetic-defs
diff --git a/clr-table.c b/clr-table.c
index 892facf..8f09ef1 100644
--- a/clr-table.c
+++ b/clr-table.c
@@ -29,7 +29,7 @@ static jmp_buf fail_jmpbuf;
 
 static void table_allocate() { for(size_t i = 0; i < TABLE_CAP; i++) table[i] = xcalloc(total_symbols, sizeof(*table[i])); }
 static void table_deallocate() { for(size_t i = 0; i < TABLE_CAP; i++) free(table[i]); }
-static int table_insert(size_t state, symbol sym, struct action a);
+// static int table_insert(size_t state, symbol sym, struct action a); // in table.h
 
 struct item {
     size_t prod_idx;
@@ -84,13 +84,14 @@ static size_t itemset_handle(struct item *set, size_t nset)
         }
 
 #ifdef _LAZY_LALR
-        int _same_core = 1;
+        int _same_core = 0;
         for(size_t j = 0; j < nset; j++) {
+            _same_core = 0;
             for(size_t k = 0; k < seen_sets[i].nitems; k++)
-                if(!item_core_eq(&seen_sets[i].items[k], &set[j])) _same_core = 0;
+                if(item_core_eq(&seen_sets[i].items[k], &set[j])) _same_core = 1;
             if(!_same_core) break;
         }
-        if(_same_core) { use_state = seen_sets[i].state; /*break;*/ }
+        if(_same_core) { (use_state != SIZE_MAX) && (exit(15), 1); use_state = seen_sets[i].state; }
 #endif
     }
 
@@ -227,25 +228,6 @@ cleanup:
     return nout;
 }
 
-static int table_insert(size_t state, symbol sym, struct action a)
-{
-    if(table[state][sym].type != ACTION_NOT_SET)
-#ifdef _LAZY_LALR
-        if(table[state][sym].type != a.type &&
-           table[state][sym].arg != a.arg)
-#endif
-    {
-        fprintf(stderr, "TABLE COLLISION on state '%zu' sym '%d'\n", state, sym);
-        fprintf(stderr, "\t{%d %zu} vs {%d %zu}\n",
-                table[state][sym].type, table[state][sym].arg,
-                a.type, a.arg);
-        return 1;
-    }
-
-    table[state][sym] = a;
-    return 0;
-}
-
 IMPLEMENT_FUNCPTR(int, table_fill, ())
 {
     table_allocate();
@@ -290,7 +272,7 @@ IMPLEMENT_FUNCPTR(int, symbol_is_terminal,  (symbol s)) { return s < EP; }
 IMPLEMENT_FUNCPTR(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)}
+#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol), 0}
 static struct production _grammar[] = {
 #if (CHOOSE_GRAMMAR == 0)
     PROD(EP, ->, E, END_INPUT),
diff --git a/demos/lexer.c b/demos/lexer.c
index a206066..01ec950 100644
--- a/demos/lexer.c
+++ b/demos/lexer.c
@@ -3,7 +3,8 @@
 #include <ctype.h>
 #include <string.h>
 
-#include "dict.c"
+#include "util/dict.h"
+static struct dict d;
 
 struct token {
     enum symbol {
@@ -77,7 +78,7 @@ static char *next_token(char *str)
             }
         } else if(isalpha(c0)) { // iden or named symbol
             char *substr = substring(str, off);
-            if((tok.sym = dict_check(substr)) == -1) {
+            if((tok.sym = dict_check(&d, substr)) == -1) {
                 tok.sym = IDEN;
                 tok.iden = strdup(substr);
             }
@@ -92,7 +93,11 @@ static char *next_token(char *str)
 
 int main(void)
 {
-    dict_compile();
+    d.strings = strings;
+    d.nstrings = nstrings;
+    d.char_to_bit = char_to_bit;
+
+    dict_compile(&d);
 
     char *str = "blah 0 1 443 test{here}13}{1\"fdlkfjakl{fher}  fdsfj\" here {therern{there{tok {wow} {";
     while((str = next_token(str)))
@@ -111,6 +116,6 @@ int main(void)
 
     printf("\n");
 
-    dict_free();
+    dict_free(&d);
     return 0;
 }
diff --git a/demos/sample-files/calc-defs.c b/demos/sample-files/calc-defs.c
index ba22877..656ab1c 100644
--- a/demos/sample-files/calc-defs.c
+++ b/demos/sample-files/calc-defs.c
@@ -20,7 +20,7 @@ IMPLEMENT_FUNCPTR(int, symbol_is_input_end, (symbol s)) { return s == END_INPUT;
 IMPLEMENT_FUNCPTR(int, symbol_is_valid, (symbol s)) { return s < SYMBOLS_END; }
 
 #include "parts/grammar.h"
-#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol)}
+#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol), 0}
 static struct production _grammar[] = {
     PROD(EP, ->, E, END_INPUT),
     PROD(E, -->, E, PLUS, T),
diff --git a/lr-parser.c b/lr-parser.c
index ad7dae5..827b502 100644
--- a/lr-parser.c
+++ b/lr-parser.c
@@ -93,7 +93,7 @@ size_t total_symbols = SYMBOLS_END;
 IMPLEMENT_FUNCPTR(int, symbol_is_valid, (symbol s)) { return s < SYMBOLS_END; }
 
 // implement grammar.h
-#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol)}
+#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol), 0}
 static struct production _grammar[] = {
     PROD(EP, ->, E, END_INPUT),
     PROD(E, -->, E, PLUS, T),
diff --git a/parts/grammar.h b/parts/grammar.h
index d1bf176..4505b1a 100644
--- a/parts/grammar.h
+++ b/parts/grammar.h
@@ -3,10 +3,20 @@
 
 #include <stddef.h> // size_t
 
+enum precedence_flag {
+    PRECEDENCE_NO_ASSOC,
+    PRECEDENCE_RIGHT_ASSOC,
+    PRECEDENCE_LEFT_ASSOC,
+};
+
+#define PRECEDENCE_NUM(prec) ((prec) >> 2)
+#define PRECEDENCE_FLAG(prec) ((prec) & 0x3)
+
 extern struct production {
     symbol LHS;
     symbol *RHS;
     size_t nRHS;
+    unsigned int precedence;
 } *grammar;
 
 extern size_t total_productions;
@@ -29,7 +39,7 @@ void grammar_print_cstyle()
         printf("{%d, (symbol[]){", grammar[i].LHS);
         for(size_t j = 0; j < grammar[i].nRHS; j++)
             printf("%d, ", grammar[i].RHS[j]);
-        printf("}, %zu},\n", grammar[i].nRHS);
+        printf("}, %zu, %d},\n", grammar[i].nRHS, grammar[i].precedence);
     }
 }
 
diff --git a/parts/symbol.h b/parts/symbol.h
index 2190eca..c7314f4 100644
--- a/parts/symbol.h
+++ b/parts/symbol.h
@@ -11,10 +11,6 @@ extern int (*symbol_is_terminal)(symbol s);
 extern int (*symbol_is_input_end)(symbol s);
 extern int (*symbol_is_valid)(symbol s);
 
-// helper macro
-#define IMPLEMENT_FUNCPTR(type, name, args)  \
-    type __##name args;                      \
-    type (*name) args = __##name;            \
-    type __##name args
+#include "util/util.h" //temp
 
 #endif
diff --git a/parts/table.h b/parts/table.h
index f3099fe..ff4601f 100644
--- a/parts/table.h
+++ b/parts/table.h
@@ -2,13 +2,21 @@
 #define TABLE_H
 
 #include <stddef.h> // size_t
+#include "util/util.h"
+
+#define ACTION_TYPE(X) \
+    X(ACTION_NOT_SET)  \
+    X(ACTION_SHIFT)    \
+    X(ACTION_GOTO)     \
+    X(ACTION_REDUCE)   \
+    X(ACTION_ACCEPT)
+
+const char * const action_type_to_char[] = {
+    ACTION_TYPE(X_TO_STR)
+};
 
 extern struct action {
-    enum action_type {
-        ACTION_NOT_SET = 0, ACTION_SHIFT,
-        ACTION_GOTO, ACTION_REDUCE,
-        ACTION_ACCEPT
-    } type;
+    enum action_type { ACTION_TYPE(X_TO_ENUM) } type;
     size_t arg;
 } **table;
 
@@ -19,6 +27,7 @@ extern void (*table_free)();
 
 void table_print();
 void table_print_cstyle();
+int table_insert(size_t state, symbol sym, struct action a); // should it be here??
 
 #include "symbol.h"
 
@@ -51,4 +60,67 @@ void table_print_cstyle()
     }
 }
 
+#include "grammar.h"
+int table_insert(size_t state, symbol sym, struct action a)
+{
+    struct action *tbl_a = &table[state][sym];
+    struct action *new_a = &a;
+
+    if(tbl_a->type == new_a->type && tbl_a->arg == new_a->arg) return 0;
+    if(tbl_a->type == ACTION_NOT_SET) {
+        *tbl_a = *new_a;
+        return 0;
+    }
+
+    int r = 0, report = 0, set_tbl_a = 0,
+    reduce_reduce = 0, shift_reduce = 0;
+    struct action *shift_a;
+
+    if((tbl_a->type == ACTION_REDUCE && new_a->type == ACTION_REDUCE))       reduce_reduce = 1;
+    else if((tbl_a->type == ACTION_REDUCE && new_a->type == ACTION_SHIFT))   { shift_reduce = 1;
+        shift_a = new_a;
+    } else if((tbl_a->type == ACTION_SHIFT && new_a->type == ACTION_REDUCE)) { shift_reduce = 1;
+        shift_a = tbl_a;
+    }
+
+#define prec_num(a)  PRECEDENCE_NUM(grammar[(a)->arg].precedence)
+#define prec_flag(a) PRECEDENCE_FLAG(grammar[(a)->arg].precedence)
+
+    if(reduce_reduce || shift_reduce) {
+        if(prec_num(tbl_a) == 0 || prec_num(new_a) == 0) report = 1;
+
+        if(prec_num(tbl_a) > prec_num(new_a))      set_tbl_a = 0;
+        else if(prec_num(tbl_a) < prec_num(new_a)) set_tbl_a = 1;
+        else if(reduce_reduce) {
+            report = 1;
+            if(new_a->arg > tbl_a->arg) set_tbl_a = 1;
+        } else {
+            if(prec_flag(tbl_a) == PRECEDENCE_NO_ASSOC && tbl_a->arg == new_a->arg) {
+                report = 1; r = 2;
+            } else if(prec_flag(shift_a) == PRECEDENCE_LEFT_ASSOC) {
+                if(shift_a == tbl_a) set_tbl_a = 1; // favor reduce
+            }else {
+                if(shift_a == new_a) set_tbl_a = 1; // favor shift
+            }
+        }
+    } else {
+        r = 1; report = 1;
+    }
+
+    if(report) {
+        struct action *a0 = (set_tbl_a) ? new_a: tbl_a;
+        struct action *a1 = (set_tbl_a) ? tbl_a: new_a;
+
+        fprintf(stderr, "REPORT: table collission on state '%zu' sym '%d'\n", state, sym);
+        fprintf(stderr, "\t%s resolve: {%s %zu} %s {%s %zu}\n",
+                (r == 0) ? "SUCCESSFULLY" : "COULD NOT",
+                action_type_to_char[a0->type], a0->arg,
+                (r == 0) ? "over" : "vs",
+                action_type_to_char[a1->type], a1->arg);
+    }
+
+    if(!r && set_tbl_a) *tbl_a = *new_a;
+    return r;
+}
+
 #endif
diff --git a/slr-table.c b/slr-table.c
index 4e12efd..ac90755 100644
--- a/slr-table.c
+++ b/slr-table.c
@@ -28,7 +28,7 @@ static jmp_buf fail_jmpbuf;
 
 static void table_allocate() { for(size_t i = 0; i < TABLE_CAP; i++) table[i] = xcalloc(total_symbols, sizeof(*table[i])); }
 static void table_deallocate() { for(size_t i = 0; i < TABLE_CAP; i++) free(table[i]); }
-static int table_insert(size_t state, symbol sym, struct action a);
+// static int table_insert(size_t state, symbol sym, struct action a); // in table.h
 
 struct item {
     size_t prod_idx;
@@ -185,20 +185,6 @@ cleanup:
     return nout;
 }
 
-static int table_insert(size_t state, 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}\n",
-                table[state][sym].type, table[state][sym].arg,
-                a.type, a.arg);
-        return 1;
-    }
-
-    table[state][sym] = a;
-    return 0;
-}
-
 IMPLEMENT_FUNCPTR(int, table_fill, ())
 {
     table_allocate();
@@ -235,7 +221,7 @@ IMPLEMENT_FUNCPTR(int, symbol_is_terminal,  (symbol s)) { return s < EP; }
 IMPLEMENT_FUNCPTR(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)}
+#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol), 0}
 static struct production _grammar[] = {
     PROD(EP, ->, E, END_INPUT),
     PROD(E, -->, E, PLUS, T),
diff --git a/util/dict.c b/util/dict.c
index 56ed6c9..75fcf3b 100644
--- a/util/dict.c
+++ b/util/dict.c
@@ -1,6 +1,5 @@
 #include <stdio.h>
 #include <stdlib.h>
-#include <stdint.h>
 #include <string.h>
 
 #include "util/dict.h"
diff --git a/util/dict.h b/util/dict.h
index ecaf53a..109c07a 100644
--- a/util/dict.h
+++ b/util/dict.h
@@ -1,6 +1,9 @@
 #ifndef DICT_H
 #define DICT_H
 
+#include <stddef.h>
+#include <stdint.h>
+
 struct level {
     uint64_t bit_mask;
     uint64_t *token_masks;
diff --git a/util/util.h b/util/util.h
new file mode 100644
index 0000000..9dc29d8
--- /dev/null
+++ b/util/util.h
@@ -0,0 +1,12 @@
+#ifndef UTIL_H
+#define UTIL_H
+
+#define IMPLEMENT_FUNCPTR(type, name, args)  \
+    type __##name args;                      \
+    type (*name) args = __##name;            \
+    type __##name args
+
+#define X_TO_STR(s) #s,
+#define X_TO_ENUM(s) s,
+
+#endif