diff options
Diffstat (limited to 'lr0.c')
| -rw-r--r-- | lr0.c | 211 |
1 files changed, 154 insertions, 57 deletions
@@ -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; } |