diff options
Diffstat (limited to 'lr0.c')
| -rw-r--r-- | lr0.c | 207 |
1 files changed, 207 insertions, 0 deletions
@@ -0,0 +1,207 @@ +#include <stdio.h> +#include <stdlib.h> + +#define ARR_LEN(a) (sizeof(a) / sizeof(*a)) + +enum symbol { + PLUS = 0, + MINUS, + LPAREN, + RPAREN, + N0, N1, + END_INPUT, + + EP, E, T, N, + SYMBOL_COUNT, +}; + +static inline int is_terminal(enum symbol s) { return s < E; } +static inline int is_nonterminal(enum symbol s) { return s >= E; } + +struct production { + enum symbol LHS; + enum symbol *RHS; + size_t nRHS; +}; + +#define PROD(LHS, _, ...) {LHS, (enum symbol[]){__VA_ARGS__}, sizeof((enum symbol[]){__VA_ARGS__})/sizeof(enum symbol)} + +static struct production grammar[] = { + PROD(EP, ->, E, END_INPUT), + PROD(E, -->, E, PLUS, T), + PROD(E, -->, E, MINUS, T), + PROD(E, -->, T), + PROD(T, -->, 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++) + { + printf("%d --> ", grammar[i].LHS); + for(size_t j = 0; j < grammar[i].nRHS; j++) + printf("%d ", grammar[i].RHS[j]); + printf("\n"); + } +} + + +struct action { + enum action_type { + ACTION_NOT_SET = 0, ACTION_SHIFT, + ACTION_GOTO, ACTION_REDUCE, + ACTION_ACCEPT + } type; + size_t arg; +}; + +static struct action *(table[SYMBOL_COUNT]); +static size_t states; + + +struct item { + size_t prod_idx; + size_t dot; +}; + +int items_eq(struct item *i1, struct item *i2) +{ + if(i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) return 1; +} + +// TODO: check bounds +static struct { + struct item *items; + size_t nitems; + size_t state; +} seen_sets[100]; +static size_t nseen_sets; + +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 main(void) +{ + struct item i[] = {{1, 2}}; + struct item o[16]; + size_t no = ARR_LEN(o); + + 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); + } +} + +size_t handle_set(struct item *set, size_t nset) +{ + // is set in seen_sets + for(size_t i = 0; i < nseen_sets; i++) { + if(seen_sets[i].nitems != nset) continue; + + int _seen = 0; + 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(!_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)); + seen_sets[nseen_sets].nitems = nset; + for(size_t i = 0; i < nset; i++) + seen_sets[nseen_sets].items[i] = set[i]; + + size_t new_state = seen_sets[nseen_sets++].state = states++; + + 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; + + 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]; + size_t ngoto = 0; + + for(size_t j = 0; j < nclosure; j++) { + struct production *p = &grammar[closure_set[j].prod_idx]; + size_t dot = closure_set[j].dot; + + if(dot == p->nRHS) { + // if(follow[p->LHS][sym]) { + // //add reduction + // } + continue; + } + + if(p->RHS[dot] == sym) { + goto_set[ngoto] = closure_set[j]; + goto_set[ngoto++].dot++; + } + } + + 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}; + } +} + +void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout) +{ + size_t nout_max = *nout; + *nout = nin; + + if(*nout > nout_max) return; + 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++) + { + struct production *p = &grammar[out_set[i].prod_idx]; + if(out_set[i].dot == p->nRHS) continue; + enum symbol sym = p->RHS[out_set[i].dot]; + + for(size_t j = 0; j < ARR_LEN(grammar); j++) + if(grammar[j].LHS == sym) { + if(is_in_closure[j]) continue; + is_in_closure[j] = 1; + + if(*nout >= nout_max) goto cleanup; + out_set[(*nout)++] = (struct item){j, 0}; + } + } + +cleanup: + free(is_in_closure); +} + +void fill_follow_table() +{ + 1 && DIE(); +} |