1 files changed, 151 insertions, 0 deletions
diff --git a/util-tables.c b/util-tables.c
new file mode 100644
index 0000000..0bd227d
--- /dev/null
+++ b/util-tables.c
@@ -0,0 +1,151 @@
+#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
+
+typedef unsigned int symbol;
+extern const size_t total_symbols;
+
+extern struct production {
+    symbol LHS;
+    symbol *RHS;
+    size_t nRHS;
+} grammar[];
+extern const size_t total_productions;
+
+int **follow;
+int **first;
+// int *nullable;
+
+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
+
+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; }
+
+#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