diff options
Diffstat (limited to 'clr-table.c')
| -rw-r--r-- | clr-table.c | 142 |
1 files changed, 74 insertions, 68 deletions
diff --git a/clr-table.c b/clr-table.c index b6bd47b..68ce3a4 100644 --- a/clr-table.c +++ b/clr-table.c @@ -8,49 +8,24 @@ void *xcalloc(size_t n, size_t size) { void *addr = calloc(n, size); return addr extern void *xcalloc(size_t n, size_t size); #endif -typedef unsigned int symbol; -extern const size_t total_symbols; +// Requirements +#include "parts/symbol.h" +#include "parts/grammar.h" +#include "parts/util-tables.h" -extern int symbol_is_terminal(symbol s); -extern int symbol_is_input_end(symbol s); - -extern struct production { - symbol LHS; - symbol *RHS; - size_t nRHS; -} grammar[]; -extern const size_t total_productions; - -void grammar_print() -{ - for(size_t i = 0; i < total_productions; i++) { - printf("%d --> ", grammar[i].LHS); - for(size_t j = 0; j < grammar[i].nRHS; j++) - printf("%d ", grammar[i].RHS[j]); - printf("\n"); - } -} - -extern int **first; -extern int **follow; - -struct action { - enum action_type { - ACTION_NOT_SET = 0, ACTION_SHIFT, - ACTION_GOTO, ACTION_REDUCE, - ACTION_ACCEPT - } type; - size_t arg; -}; +// Implements +#include "parts/table.h" #define TABLE_CAP 64 struct action *table[TABLE_CAP]; size_t table_states = 0; -void table_allocate() { for(size_t i = 0; i < TABLE_CAP; i++) table[i] = xcalloc(total_symbols, sizeof(*table[i])); } -void table_free() { for(size_t i = 0; i < TABLE_CAP; i++) free(table[i]); } -int table_insert(size_t state, symbol sym, struct action a); -void table_print(); +int table_fill(); +void table_free(); + +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); struct item { size_t prod_idx; @@ -58,7 +33,7 @@ struct item { symbol lookahead; }; -int item_eq(struct item *i1, struct item *i2) { return (i1->dot == i2->dot && i1->prod_idx == i2->prod_idx && i1->lookahead == i2->lookahead) ? 1 : 0; } +static int item_eq(struct item *i1, struct item *i2) { return (i1->dot == i2->dot && i1->prod_idx == i2->prod_idx && i1->lookahead == i2->lookahead) ? 1 : 0; } #define SEEN_SETS_CAP 64 static struct { @@ -68,12 +43,12 @@ static struct { } seen_sets[SEEN_SETS_CAP]; static size_t nseen_sets; -void seen_sets_free() { for(size_t i = 0; i < nseen_sets; i++) free(seen_sets[i].items);} +static void seen_sets_free() { for(size_t i = 0; i < nseen_sets; i++) free(seen_sets[i].items);} -size_t itemset_handle(struct item *set, size_t nset); -int itemset_insert(size_t state, struct item *initial_set, size_t ninitial); -size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout); -void itemset_print(struct item *set, size_t nset) +static size_t itemset_handle(struct item *set, size_t nset); +static int itemset_insert(size_t state, struct item *initial_set, size_t ninitial); +static size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout); +static void itemset_print(struct item *set, size_t nset) { printf("{"); for(size_t i = 0; i < nset; i++) @@ -81,7 +56,7 @@ void itemset_print(struct item *set, size_t nset) printf("}\n"); } -size_t itemset_handle(struct item *set, size_t nset) +static size_t itemset_handle(struct item *set, size_t nset) { // 1. is set in seen_sets for(size_t i = 0; i < nseen_sets; i++) { @@ -125,7 +100,7 @@ size_t itemset_handle(struct item *set, size_t nset) #define CLOSURE_SET_CAP 64 #define GOTO_SET_CAP 32 -int itemset_insert(size_t state, struct item *initial_set, size_t ninitial) +static int itemset_insert(size_t state, struct item *initial_set, size_t ninitial) { struct item closure_set[CLOSURE_SET_CAP]; @@ -179,7 +154,7 @@ int itemset_insert(size_t state, struct item *initial_set, size_t ninitial) return 0; } -size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout_max) +static size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout_max) { size_t nout = nin; @@ -226,7 +201,7 @@ cleanup: return nout; } -int table_insert(size_t state, symbol sym, struct action a) +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); @@ -240,31 +215,28 @@ int table_insert(size_t state, symbol sym, struct action a) return 0; } -void table_print() +int table_fill() { - printf(" "); - for(size_t sym = 0; sym < total_symbols; 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 < table_states; i++) { - printf("%2zu ", i); - for(size_t sym = 0; sym < total_symbols; 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"); - } + table_allocate(); + // Possible bug: wrong lookahead for kernel item of state, + // but it may not really matter + itemset_handle((struct item[]){{0, 0, 0}}, 1); + return 0; } -#ifdef _CLR_TABLE_STANDALONE +void table_free() +{ + seen_sets_free(); + table_deallocate(); +} -#include "util-tables.c" +#ifdef _CLR_TABLE_STANDALONE #ifndef CHOOSE_GRAMMAR -#define CHOOSE_GRAMMAR 1 // 0 or 1 +#define CHOOSE_GRAMMAR 0 // 0 or 1 #endif +// implement symbol.h enum symbol { #if (CHOOSE_GRAMMAR == 0) ID, EQUAL, STAR, @@ -284,6 +256,7 @@ const size_t total_symbols = SYMBOLS_END; int symbol_is_terminal(symbol s) { return s < EP; } 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[] = { #if (CHOOSE_GRAMMAR == 0) @@ -303,17 +276,50 @@ struct production grammar[] = { const size_t total_productions = sizeof(grammar)/sizeof(*grammar); +// implement util-tables.h +#include "util-tables.c" + int main(void) { util_tables_fill(); - table_allocate(); - - itemset_handle((struct item[]){{0, 0, END_INPUT}}, 1); + table_fill(); + table_print(); - seen_sets_free(); table_free(); util_tables_free(); } #endif + +/* +---+------------------------+ + * | - | 0 1 2 3 4 5 | + * +---+------------------------+ + * | 0 | s1 s2 g4 g5 | + * | 1 | s1 s2 g3 | + * | 2 | r3 r3 | + * | 3 | r2 r2 | + * | 4 | a | + * | 5 | s6 s7 g9 | + * | 6 | s6 s7 g8 | + * | 7 | r3 | + * | 8 | r2 | + * | 9 | r1 | + * +---+------------------------+ + + 0 1 2 3 4 5 6 7 + 0 s1 s2 g5 g6 g13 + 1 r4 r4 + 2 s1 s2 g3 g4 + 3 r5 r5 + 4 r3 r3 + 5 a + 6 s7 r5 + 7 s8 s9 g10 g12 + 8 r4 + 9 s8 s9 g10 g11 +10 r5 +11 r3 +12 r1 +13 r2 + */ |