From 7f796bc571941a9c14eeb3a65d349d628f022275 Mon Sep 17 00:00:00 2001 From: kartofen Date: Mon, 30 Jun 2025 00:26:51 +0300 Subject: CLR yesss --- build.sh | 33 +++- clr-table.c | 319 ++++++++++++++++++++++++++++++++++ lr0-table.c | 326 ----------------------------------- recursive-ascent-descent.c | 197 --------------------- recursive-ascent.c | 316 --------------------------------- recursive/recursive-ascent-descent.c | 197 +++++++++++++++++++++ recursive/recursive-ascent.c | 316 +++++++++++++++++++++++++++++++++ slr-table.c | 288 +++++++++++++++++++++++++++++++ util-tables.c | 151 ++++++++++++++++ 9 files changed, 1295 insertions(+), 848 deletions(-) create mode 100644 clr-table.c delete mode 100644 lr0-table.c delete mode 100644 recursive-ascent-descent.c delete mode 100644 recursive-ascent.c create mode 100644 recursive/recursive-ascent-descent.c create mode 100644 recursive/recursive-ascent.c create mode 100644 slr-table.c create mode 100644 util-tables.c diff --git a/build.sh b/build.sh index d69fa83..855d574 100755 --- a/build.sh +++ b/build.sh @@ -2,12 +2,27 @@ set -xe -# gcc -Wall -Wextra -g -D_LEXER_STANDALONE lexer.c -o lexer -# gcc -Wall -Wextra -g recursive-ascent.c -o recursive-ascent -# gcc -Wall -Wextra -g recursive-ascent-descent.c -o recursive-ascent-descent -gcc -Wall -Wextra -g lr0-table.c -D_LR0_TABLE_STANDALONE -o lr0-table - -# valgrind --leak-check=full --show-leak-kinds=all -s ./lexer -# valgrind --leak-check=full --show-leak-kinds=all -s ./recursive-ascent -# valgrind --leak-check=full --show-leak-kinds=all -s ./recursive-ascent-descent -valgrind --leak-check=full --show-leak-kinds=all -s ./lr0-table +function cc +{ + mkdir -p bin + gcc -Wall -Wextra -Wpedantic -g $2 $1.c -o bin/$(basename $1) +} + +function leak +{ + valgrind --leak-check=full --show-leak-kinds=all -s bin/$1 +} + +# cc lexer -D_LEXER_STANDALONE +# cc recursive/recursive-ascent +# cc recursive/recursive-ascent-descent +# cc util-tables -D_UTIL_TABLES_STANDALONE +# cc slr-table -D_SLR_TABLE_STANDALONE +cc clr-table -D_CLR_TABLE_STANDALONE + +# leak lexer +# leak recursive-ascent +# leak recursive-ascent-descent +# leak util-tables +# leak slr-table +leak clr-table diff --git a/clr-table.c b/clr-table.c new file mode 100644 index 0000000..92e415f --- /dev/null +++ b/clr-table.c @@ -0,0 +1,319 @@ +#include +#include + +#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 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; +}; + +#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(); + +struct item { + size_t prod_idx; + size_t dot; + 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; } + +#define SEEN_SETS_CAP 64 +static struct { + struct item *items; + size_t nitems; + size_t state; +} 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);} + +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) +{ + printf("{"); + for(size_t i = 0; i < nset; i++) + printf("{%zu, %zu, %d}, ", set[i].prod_idx, set[i].dot, set[i].lookahead); + printf("}\n"); +} + +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++) { + 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(item_eq(&seen_sets[i].items[k], &set[j])) _seen = 1; + if(!_seen) break; + } + if(_seen) return seen_sets[i].state; + } + + // 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 = table_states++; + if(new_state >= TABLE_CAP) { + fprintf(stderr, "ERROR: TABLE_CAP exceeded\n"); + exit(1); + } + + if(itemset_insert(new_state, set, nset)) { + fprintf(stderr, "ERROR: itemset_insert failed\n"); + exit(1); + } + + return new_state; +} + +#define CLOSURE_SET_CAP 64 +#define GOTO_SET_CAP 32 +int itemset_insert(size_t state, struct item *initial_set, size_t ninitial) +{ + struct item closure_set[CLOSURE_SET_CAP]; + + size_t nclosure = itemset_closure(initial_set, ninitial, closure_set, CLOSURE_SET_CAP); + if(nclosure > CLOSURE_SET_CAP) { + fprintf(stderr, "ERROR: CLOSURE_SET_CAP exceeded\n"); + return 1; + } + + for(size_t sym = 0; sym < total_symbols; sym++) { + struct item goto_set[GOTO_SET_CAP]; + 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(sym != 0) continue; + if(table_insert(state, closure_set[j].lookahead, (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(symbol_is_input_end(sym)) { + if(table_insert(state, sym, (struct action){ACTION_ACCEPT, 0})) + return 1; + continue; + } + + size_t new_state = itemset_handle(goto_set, ngoto); + + if(table_insert(state, sym, (struct action){ + symbol_is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO, + new_state})) return 1; + } + + return 0; +} + +size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout_max) +{ + size_t nout = nin; + + if(nout > nout_max) return nout; + for(size_t i = 0; i < nin; i++) out_set[i] = in_set[i]; + + int **is_in_closure = xcalloc(total_productions, sizeof(*is_in_closure)); + for(size_t i = 0; i < total_productions; i++) + is_in_closure[i] = xcalloc(total_symbols, sizeof(**is_in_closure)); + +#define add_item(prod_idx, lookahead, ...) do { \ + if(is_in_closure[prod_idx][lookahead]) break; \ + is_in_closure[prod_idx][lookahead] = 1; \ + if(nout++ >= nout_max) goto cleanup; \ + out_set[nout-1] = __VA_ARGS__; \ + } while(0) + + 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; + symbol sym = p->RHS[out_set[i].dot]; + + for(size_t j = 0; j < total_productions; j++) + if(grammar[j].LHS == sym) { + if(out_set[i].dot + 1 == p->nRHS) { + add_item(j, out_set[i].lookahead, + (struct item){j, 0, out_set[i].lookahead}); + continue; + } + + symbol next_symbol = p->RHS[out_set[i].dot+1]; + for(size_t terminal = 0; terminal < total_symbols; terminal++) { + if(!symbol_is_terminal(terminal)) continue; + if(first[next_symbol][terminal]) + add_item(j, terminal, (struct item){j, 0, terminal}); + } + } + } + +cleanup: + for(size_t i = 0; i < total_productions; i++) free(is_in_closure[i]); + free(is_in_closure); + return nout; +} + +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; +} + +void table_print() +{ + 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"); + } +} + +#ifdef _CLR_TABLE_STANDALONE + +#include "util-tables.c" + +#ifndef CHOOSE_GRAMMAR +#define CHOOSE_GRAMMAR 1 // 0 or 1 +#endif + +enum symbol { +#if (CHOOSE_GRAMMAR == 0) + ID, EQUAL, STAR, + END_INPUT, + EP, E, L, R, + SYMBOLS_END, +#else + SC, SD, + END_INPUT, + EP, E, C, + SYMBOLS_END +#endif +}; + +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; } + +#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol)} +struct production grammar[] = { +#if (CHOOSE_GRAMMAR == 0) + PROD(EP, ->, E, END_INPUT), + PROD(E, -->, L, EQUAL, R), + PROD(E, -->, R), + PROD(L, -->, STAR, R), + PROD(L, -->, ID), + PROD(R, -->, L), +#else + PROD(EP, ->, E, END_INPUT), + PROD(E, -->, C, C), + PROD(C, -->, SC, C), + PROD(C, -->, SD), +#endif +}; + +const size_t total_productions = sizeof(grammar)/sizeof(*grammar); + +int main(void) +{ + util_tables_fill(); + table_allocate(); + + itemset_handle((struct item[]){{0, 0, END_INPUT}}, 1); + table_print(); + + seen_sets_free(); + table_free(); + util_tables_free(); +} + +#endif diff --git a/lr0-table.c b/lr0-table.c deleted file mode 100644 index 721bdb5..0000000 --- a/lr0-table.c +++ /dev/null @@ -1,326 +0,0 @@ -#include -#include - -#ifndef MAX_SYMBOLS -#define MAX_SYMBOLS 64 -#endif - -#ifdef XCALLOC_IMPLEMENTED -extern void *xcalloc(size_t n, size_t size); -#else -void *xcalloc(size_t n, size_t size) { void *addr = calloc(n, size); return addr ? addr : (exit(1), NULL); } -#endif - -typedef unsigned int symbol; - -extern const size_t total_symbols; -extern int symbol_is_terminal(symbol s); -extern int symbol_is_nonterminal(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"); - } -} - -static int follow[MAX_SYMBOLS][MAX_SYMBOLS]; - -void follow_table_fill(); -void follow_table_print(); - -struct action { - enum action_type { - ACTION_NOT_SET = 0, ACTION_SHIFT, - ACTION_GOTO, ACTION_REDUCE, - ACTION_ACCEPT - } type; - size_t arg; -}; - -#define TABLE_CAP 64 -static struct action table[TABLE_CAP][MAX_SYMBOLS]; // *(table[total_symbols]); -static size_t table_states; - -int table_insert(size_t state, symbol sym, struct action a); -void table_print(); - -struct item { - size_t prod_idx; - size_t dot; -}; - -int item_eq(struct item *i1, struct item *i2) { return (i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) ? 1 : 0; } - -#define SEEN_SETS_CAP 64 -static struct { - struct item *items; - size_t nitems; - size_t state; -} 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);} - -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) -{ - printf("{"); - for(size_t i = 0; i < nset; i++) - printf("{%zu, %zu}, ", set[i].prod_idx, set[i].dot); - printf("}\n"); -} - -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++) { - 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(item_eq(&seen_sets[i].items[k], &set[j])) _seen = 1; - if(!_seen) break; - } - if(_seen) return seen_sets[i].state; - } - - // 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 = table_states++; - if(new_state >= TABLE_CAP) { - fprintf(stderr, "ERROR: TABLE_CAP exceeded\n"); - exit(1); - } - - if(itemset_insert(new_state, set, nset)) { - fprintf(stderr, "ERROR: itemset_insert failed\n"); - exit(1); - } - - return new_state; -} - -#define CLOSURE_SET_CAP 64 -#define GOTO_SET_CAP 32 -int itemset_insert(size_t state, struct item *initial_set, size_t ninitial) -{ - struct item closure_set[CLOSURE_SET_CAP]; - - size_t nclosure = itemset_closure(initial_set, ninitial, closure_set, CLOSURE_SET_CAP); - if(nclosure > CLOSURE_SET_CAP) { - fprintf(stderr, "ERROR: CLOSURE_SET_CAP exceeded\n"); - return 1; - } - - for(size_t sym = 0; sym < total_symbols; sym++) { - struct item goto_set[GOTO_SET_CAP]; - 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]) 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(symbol_is_input_end(sym)) { - if(table_insert(state, sym, (struct action){ACTION_ACCEPT, 0})) - return 1; - continue; - } - - size_t new_state = itemset_handle(goto_set, ngoto); - - if(table_insert(state, sym, (struct action){ - symbol_is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO, - new_state})) return 1; - } - - return 0; -} - -size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout_max) -{ - size_t nout = nin; - - if(nout > nout_max) return nout; - for(size_t i = 0; i < nin; i++) out_set[i] = in_set[i]; - - int *is_in_closure = xcalloc(total_productions, 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; - symbol sym = p->RHS[out_set[i].dot]; - - for(size_t j = 0; j < total_productions; 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-1] = (struct item){j, 0}; - } - } - -cleanup: - free(is_in_closure); - return nout; -} - -void follow_table_fill() -{ - for(size_t i = 0; i < total_productions; 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 < total_productions; i++) - for(size_t sym = 0; sym < total_symbols; 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); -} - -void follow_table_print() -{ - 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"); - } -} - -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}", - table[state][sym].type, table[state][sym].arg, - a.type, a.arg); - return 1; - } - - table[state][sym] = a; - return 0; -} - -void table_print() -{ - 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"); - } -} - -#ifdef _LR0_TABLE_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) -{ - follow_table_fill(); - - itemset_handle((struct item[]){{0, 0}}, 1); - table_print(); - - seen_sets_free(); -} - -#endif diff --git a/recursive-ascent-descent.c b/recursive-ascent-descent.c deleted file mode 100644 index 628540d..0000000 --- a/recursive-ascent-descent.c +++ /dev/null @@ -1,197 +0,0 @@ -#include // printf(char *, ...) -#include // exit(int) - -/* - * For grammar: (https://en.wikipedia.org/wiki/Recursive_ascent_parser) - * (R1) expr : expr _ '+' term { $$ = $1 + $3; } - * (R2) | expr _ '-' term { $$ = $1 - $3; } - * (R3) | _ term { $$ = $1; } - * ; - * - * (R4) term : _ '(' expr ')' { $$ = $2; } - * (R5) | _ num { $$ = $1; } - * ; - * - * (R6) num : _ '0' { $$ = 0; } - * (R7) | _ '1' { $$ = 1; } - * ; - */ - -#pragma GCC diagnostic ignored "-Wunused-value" -#pragma GCC diagnostic ignored "-Wunused-parameter" - -#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1) - -enum nonterminal { INVAILID, EXPR, TERM, NUM }; -struct result { enum nonterminal nonterm; int value; int depth; char *s; }; - -struct args { int args[2]; }; -#define new_arg(...) (struct args){{__VA_ARGS__}} -#define get_arg(a, n) ((a).args[n]) - -// top-down -struct result rule0(char *s, struct args a); -struct result rule1(char *s, struct args a); -struct result rule2(char *s, struct args a); -struct result rule3(char *s, struct args a); -struct result rule4(char *s, struct args a); -struct result rule5(char *s, struct args a); -struct result rule6(char *s, struct args a); -struct result rule7(char *s, struct args a); - -// bottom-up -struct result accept(char *s, struct args a); -struct result expr(char *s, struct args a); -struct result expr2(char *s, struct args a); -struct result term(char *s, struct args a); -struct result num(char *s, struct args a); - -int main(void) -{ - char *s = "1-((0-1)+1+1+1+1+1)-0+1-(((1)))+1+1+1-1+0+(1-0+1)-1-0"; - struct result r = accept(s, new_arg(0)); - printf("%s = %d\n", s, r.value); - return 0; -} - -char *eat(char *s, char c) -{ - if(*s == c) - return s + 1; - else DIE(); -} - -struct result rule0(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r = expr(r.s, a); - r.s = eat(r.s, '\0'); - return r; -} - -struct result rule1(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r.s = eat(r.s, '+'); - r = term(r.s, a); - return (struct result){EXPR, get_arg(a, 0) + r.value, 0, r.s}; -} - -struct result rule2(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r.s = eat(r.s, '-'); - r = term(r.s, a); - return (struct result){EXPR, get_arg(a, 0) - r.value, 0, r.s}; -} - -struct result rule3(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r = term(r.s, a); - return (struct result){EXPR, r.value, 0, r.s}; -} - -struct result rule4(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r.s = eat(r.s, '('); - r = expr(r.s, a); - r.s = eat(r.s, ')'); - return (struct result){EXPR, r.value, 1, r.s}; -} - -struct result rule5(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r = num(r.s, a); - return (struct result){TERM, r.value, 0, r.s}; -} - -struct result rule6(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r.s = eat(r.s, '0'); - return (struct result){NUM, 0, 0, r.s}; -} - -struct result rule7(char *s, struct args a) -{ - struct result r = {0, 0, 0, s}; - r.s = eat(r.s, '1'); - return (struct result){NUM, 1, 0, r.s}; -} - -struct result accept(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '(': - case '0': - case '1': r = rule0(s, a); break; - default: DIE(); - } - - return r; -} - -struct result expr(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '(': - case '0': - case '1': r = rule3(s, a); break; - default: DIE(); - } - - struct result r2 = r; - while(r2.depth == 0) { - r = r2; - switch(r.nonterm) { - case EXPR: r2 = expr2(r.s, new_arg(r.value)); break; - default: DIE(); - } - } - - r.depth--; - return r; -} - -struct result expr2(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '+': r = rule1(s, a); break; - case '-': r = rule2(s, a); break; - default: r.depth = 1; - } - - return r; -} - -struct result term(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '(': r = rule4(s, a); break; - case '0': r = rule5(s, a); break; - case '1': r = rule5(s, a); break; - default: DIE(); - } - - return r; -} - -struct result num(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '0': r = rule6(s, a); break; - case '1': r = rule7(s, a); break; - default: DIE(); - } - - return r; -} - diff --git a/recursive-ascent.c b/recursive-ascent.c deleted file mode 100644 index 7f69e57..0000000 --- a/recursive-ascent.c +++ /dev/null @@ -1,316 +0,0 @@ -#include -#include - -/* - * For grammar: (https://en.wikipedia.org/wiki/Recursive_ascent_parser) - * expr : expr '+' term { $$ = $1 + $3; } - * | expr '-' term { $$ = $1 - $3; } - * | term { $$ = $1; } - * ; - * - * term : '(' expr ')' { $$ = $2; } - * | num { $$ = $1; } - * ; - * - * num : '0' { $$ = 0; } - * | '1' { $$ = 1; } - * ; - */ - -#pragma GCC diagnostic ignored "-Wunused-value" - -#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1) - -enum nonterminal { EXPR, TERM, NUM }; -struct result { enum nonterminal nonterm; int value; int depth; char *s; }; - -struct args { int args[2]; }; -#define new_arg(...) (struct args){{__VA_ARGS__}} -#define get_arg(a, n) ((a).args[n]) - -struct result state0(char *s, struct args a); -struct result state1(char *s, struct args a); -struct result state2(char *s, struct args a); -struct result state3(char *s, struct args a); -struct result state4(char *s, struct args a); -struct result state5(char *s, struct args a); -struct result state6(char *s, struct args a); -struct result state7(char *s, struct args a); -struct result state8(char *s, struct args a); -struct result state9(char *s, struct args a); -struct result state10(char *s, struct args a); -struct result state11(char *s, struct args a); -struct result state12(char *s, struct args a); -struct result state13(char *s, struct args a); - -int main(void) -{ - char *s = "1-((0-1)+1+1+1+1+1)-0+1-(((1)))+1+1+1-1+0+(1-0+1)-1-0"; - struct result r = state0(s, new_arg(0)); - printf("%s = %d\n", s, r.value); - return 0; -} - -/* - * 0 $accept: . expr $end - * - * '(' shift, and go to state 1 - * '0' shift, and go to state 2 - * '1' shift, and go to state 3 - * - * expr go to state 4 - * term go to state 5 - * num go to state 6 - */ -struct result state0(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '(': r = state1(s+1, a); break; - case '0': r = state2(s+1, a); break; - case '1': r = state3(s+1, a); break; - default: DIE(); - } - - while(r.depth == 0) { - switch(r.nonterm) { - case EXPR: r = state4(r.s, new_arg(r.value)); break; - case TERM: r = state5(r.s, new_arg(r.value)); break; - case NUM: r = state6(r.s, new_arg(r.value)); break; - default: DIE(); - } - } - - r.depth--; - return r; -} - -/* - * 4 term: '(' . expr ')' - * - * '(' shift, and go to state 1 - * '0' shift, and go to state 2 - * '1' shift, and go to state 3 - * - * expr go to state 7 - * term go to state 5 - * num go to state 6 - */ -struct result state1(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '(': r = state1(s+1, a); break; - case '0': r = state2(s+1, a); break; - case '1': r = state3(s+1, a); break; - default: DIE(); - } - - while(r.depth == 0) { - switch(r.nonterm) { - case EXPR: r = state7(r.s, new_arg(r.value)); break; - case TERM: r = state5(r.s, new_arg(r.value)); break; - case NUM: r = state6(r.s, new_arg(r.value)); break; - default: DIE(); - } - } - - r.depth--; - return r; -} - -/* - * 6 num: '0' . - * - * $default reduce using rule 6 (num) - */ -struct result state2(char *s, struct args a) -{ - (void)a; - return (struct result){NUM, 0, 0, s}; -} - -/* - * 7 num: '1' . - * - * $default reduce using rule 7 (num) - */ -struct result state3(char *s, struct args a) -{ - (void)a; - return (struct result){NUM, 1, 0, s}; -} - -/* - * 0 $accept: expr . $end - * 1 expr: expr . '+' term - * 2 | expr . '-' term - * - * $end shift, and go to state 8 - * '+' shift, and go to state 9 - * '-' shift, and go to state 10 - */ -struct result state4(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '\0': r = state8(s+1, a); break; - case '+': r = state9(s+1, a); break; - case '-': r = state10(s+1, a); break; - default: DIE(); - } - - (r.depth == 0) && DIE(); - - r.depth--; - return r; -} - -/* - * 3 expr: term . - * - * $default reduce using rule 3 (expr) - */ -struct result state5(char *s, struct args a) -{ - return (struct result){EXPR, get_arg(a, 0), 0, s}; -} - -/* - * 5 term: num . - * - * $default reduce using rule 5 (term) - */ -struct result state6(char *s, struct args a) -{ - return (struct result){TERM, get_arg(a, 0), 0, s}; -} - -/* - * 1 expr: expr . '+' term - * 2 | expr . '-' term - * 4 term: '(' expr . ')' - * - * '+' shift, and go to state 9 - * '-' shift, and go to state 10 - * ')' shift, and go to state 11 - */ -struct result state7(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '+': r = state9(s+1, a); break; - case '-': r = state10(s+1, a); break; - case ')': r = state11(s+1, a); break; - default: DIE(); - } - - (r.depth == 0) && DIE(); - - r.depth--; - return r; -} - -/* - * 0 $accept: expr $end . - * - * $default accept - */ -struct result state8(char *s, struct args a) -{ - return (struct result){EXPR, a.args[0], 2, s}; -} - -/* - * 1 expr: expr '+' . term - * - * '(' shift, and go to state 1 - * '0' shift, and go to state 2 - * '1' shift, and go to state 3 - * - * term go to state 12 - * num go to state 6 - */ -struct result state9(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '(': r = state1(s+1, a); break; - case '0': r = state2(s+1, a); break; - case '1': r = state3(s+1, a); break; - default: DIE(); - } - - while(r.depth == 0) { - switch(r.nonterm) { - case TERM: r = state12(r.s, new_arg(r.value, get_arg(a, 0))); break; - case NUM: r = state6(r.s, new_arg(r.value)); break; - default: DIE(); - } - } - - r.depth--; - return r; -} - -/* - * 2 expr: expr '-' . term - * - * '(' shift, and go to state 1 - * '0' shift, and go to state 2 - * '1' shift, and go to state 3 - * - * term go to state 13 - * num go to state 6 - */ -struct result state10(char *s, struct args a) -{ - struct result r = {0}; - switch(*s) { - case '(': r = state1(s+1, a); break; - case '0': r = state2(s+1, a); break; - case '1': r = state3(s+1, a); break; - default: DIE(); - } - - while(r.depth == 0) { - switch(r.nonterm) { - case TERM: r = state13(r.s, new_arg(get_arg(a, 0), r.value)); break; - case NUM: r = state6(r.s, new_arg(r.value)); break; - default: DIE(); - } - } - - r.depth--; - return r; -} - -/* - * 4 term: '(' expr ')' . - * - * $default reduce using rule 4 (term) - */ -struct result state11(char *s, struct args a) -{ - return (struct result){TERM, get_arg(a, 0), 2, s}; -} - -/* - * 1 expr: expr '+' term . - * - * $default reduce using rule 1 (expr) - */ -struct result state12(char *s, struct args a) -{ - return (struct result){EXPR, get_arg(a, 0) + get_arg(a, 1), 2, s}; -} - -/* - * 2 expr: expr '-' term . - * - * $default reduce using rule 2 (expr) - */ -struct result state13(char *s, struct args a) -{ - return (struct result){EXPR, get_arg(a, 0) - get_arg(a, 1), 2, s}; -} diff --git a/recursive/recursive-ascent-descent.c b/recursive/recursive-ascent-descent.c new file mode 100644 index 0000000..628540d --- /dev/null +++ b/recursive/recursive-ascent-descent.c @@ -0,0 +1,197 @@ +#include // printf(char *, ...) +#include // exit(int) + +/* + * For grammar: (https://en.wikipedia.org/wiki/Recursive_ascent_parser) + * (R1) expr : expr _ '+' term { $$ = $1 + $3; } + * (R2) | expr _ '-' term { $$ = $1 - $3; } + * (R3) | _ term { $$ = $1; } + * ; + * + * (R4) term : _ '(' expr ')' { $$ = $2; } + * (R5) | _ num { $$ = $1; } + * ; + * + * (R6) num : _ '0' { $$ = 0; } + * (R7) | _ '1' { $$ = 1; } + * ; + */ + +#pragma GCC diagnostic ignored "-Wunused-value" +#pragma GCC diagnostic ignored "-Wunused-parameter" + +#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1) + +enum nonterminal { INVAILID, EXPR, TERM, NUM }; +struct result { enum nonterminal nonterm; int value; int depth; char *s; }; + +struct args { int args[2]; }; +#define new_arg(...) (struct args){{__VA_ARGS__}} +#define get_arg(a, n) ((a).args[n]) + +// top-down +struct result rule0(char *s, struct args a); +struct result rule1(char *s, struct args a); +struct result rule2(char *s, struct args a); +struct result rule3(char *s, struct args a); +struct result rule4(char *s, struct args a); +struct result rule5(char *s, struct args a); +struct result rule6(char *s, struct args a); +struct result rule7(char *s, struct args a); + +// bottom-up +struct result accept(char *s, struct args a); +struct result expr(char *s, struct args a); +struct result expr2(char *s, struct args a); +struct result term(char *s, struct args a); +struct result num(char *s, struct args a); + +int main(void) +{ + char *s = "1-((0-1)+1+1+1+1+1)-0+1-(((1)))+1+1+1-1+0+(1-0+1)-1-0"; + struct result r = accept(s, new_arg(0)); + printf("%s = %d\n", s, r.value); + return 0; +} + +char *eat(char *s, char c) +{ + if(*s == c) + return s + 1; + else DIE(); +} + +struct result rule0(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r = expr(r.s, a); + r.s = eat(r.s, '\0'); + return r; +} + +struct result rule1(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r.s = eat(r.s, '+'); + r = term(r.s, a); + return (struct result){EXPR, get_arg(a, 0) + r.value, 0, r.s}; +} + +struct result rule2(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r.s = eat(r.s, '-'); + r = term(r.s, a); + return (struct result){EXPR, get_arg(a, 0) - r.value, 0, r.s}; +} + +struct result rule3(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r = term(r.s, a); + return (struct result){EXPR, r.value, 0, r.s}; +} + +struct result rule4(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r.s = eat(r.s, '('); + r = expr(r.s, a); + r.s = eat(r.s, ')'); + return (struct result){EXPR, r.value, 1, r.s}; +} + +struct result rule5(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r = num(r.s, a); + return (struct result){TERM, r.value, 0, r.s}; +} + +struct result rule6(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r.s = eat(r.s, '0'); + return (struct result){NUM, 0, 0, r.s}; +} + +struct result rule7(char *s, struct args a) +{ + struct result r = {0, 0, 0, s}; + r.s = eat(r.s, '1'); + return (struct result){NUM, 1, 0, r.s}; +} + +struct result accept(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '(': + case '0': + case '1': r = rule0(s, a); break; + default: DIE(); + } + + return r; +} + +struct result expr(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '(': + case '0': + case '1': r = rule3(s, a); break; + default: DIE(); + } + + struct result r2 = r; + while(r2.depth == 0) { + r = r2; + switch(r.nonterm) { + case EXPR: r2 = expr2(r.s, new_arg(r.value)); break; + default: DIE(); + } + } + + r.depth--; + return r; +} + +struct result expr2(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '+': r = rule1(s, a); break; + case '-': r = rule2(s, a); break; + default: r.depth = 1; + } + + return r; +} + +struct result term(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '(': r = rule4(s, a); break; + case '0': r = rule5(s, a); break; + case '1': r = rule5(s, a); break; + default: DIE(); + } + + return r; +} + +struct result num(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '0': r = rule6(s, a); break; + case '1': r = rule7(s, a); break; + default: DIE(); + } + + return r; +} + diff --git a/recursive/recursive-ascent.c b/recursive/recursive-ascent.c new file mode 100644 index 0000000..7f69e57 --- /dev/null +++ b/recursive/recursive-ascent.c @@ -0,0 +1,316 @@ +#include +#include + +/* + * For grammar: (https://en.wikipedia.org/wiki/Recursive_ascent_parser) + * expr : expr '+' term { $$ = $1 + $3; } + * | expr '-' term { $$ = $1 - $3; } + * | term { $$ = $1; } + * ; + * + * term : '(' expr ')' { $$ = $2; } + * | num { $$ = $1; } + * ; + * + * num : '0' { $$ = 0; } + * | '1' { $$ = 1; } + * ; + */ + +#pragma GCC diagnostic ignored "-Wunused-value" + +#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1) + +enum nonterminal { EXPR, TERM, NUM }; +struct result { enum nonterminal nonterm; int value; int depth; char *s; }; + +struct args { int args[2]; }; +#define new_arg(...) (struct args){{__VA_ARGS__}} +#define get_arg(a, n) ((a).args[n]) + +struct result state0(char *s, struct args a); +struct result state1(char *s, struct args a); +struct result state2(char *s, struct args a); +struct result state3(char *s, struct args a); +struct result state4(char *s, struct args a); +struct result state5(char *s, struct args a); +struct result state6(char *s, struct args a); +struct result state7(char *s, struct args a); +struct result state8(char *s, struct args a); +struct result state9(char *s, struct args a); +struct result state10(char *s, struct args a); +struct result state11(char *s, struct args a); +struct result state12(char *s, struct args a); +struct result state13(char *s, struct args a); + +int main(void) +{ + char *s = "1-((0-1)+1+1+1+1+1)-0+1-(((1)))+1+1+1-1+0+(1-0+1)-1-0"; + struct result r = state0(s, new_arg(0)); + printf("%s = %d\n", s, r.value); + return 0; +} + +/* + * 0 $accept: . expr $end + * + * '(' shift, and go to state 1 + * '0' shift, and go to state 2 + * '1' shift, and go to state 3 + * + * expr go to state 4 + * term go to state 5 + * num go to state 6 + */ +struct result state0(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '(': r = state1(s+1, a); break; + case '0': r = state2(s+1, a); break; + case '1': r = state3(s+1, a); break; + default: DIE(); + } + + while(r.depth == 0) { + switch(r.nonterm) { + case EXPR: r = state4(r.s, new_arg(r.value)); break; + case TERM: r = state5(r.s, new_arg(r.value)); break; + case NUM: r = state6(r.s, new_arg(r.value)); break; + default: DIE(); + } + } + + r.depth--; + return r; +} + +/* + * 4 term: '(' . expr ')' + * + * '(' shift, and go to state 1 + * '0' shift, and go to state 2 + * '1' shift, and go to state 3 + * + * expr go to state 7 + * term go to state 5 + * num go to state 6 + */ +struct result state1(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '(': r = state1(s+1, a); break; + case '0': r = state2(s+1, a); break; + case '1': r = state3(s+1, a); break; + default: DIE(); + } + + while(r.depth == 0) { + switch(r.nonterm) { + case EXPR: r = state7(r.s, new_arg(r.value)); break; + case TERM: r = state5(r.s, new_arg(r.value)); break; + case NUM: r = state6(r.s, new_arg(r.value)); break; + default: DIE(); + } + } + + r.depth--; + return r; +} + +/* + * 6 num: '0' . + * + * $default reduce using rule 6 (num) + */ +struct result state2(char *s, struct args a) +{ + (void)a; + return (struct result){NUM, 0, 0, s}; +} + +/* + * 7 num: '1' . + * + * $default reduce using rule 7 (num) + */ +struct result state3(char *s, struct args a) +{ + (void)a; + return (struct result){NUM, 1, 0, s}; +} + +/* + * 0 $accept: expr . $end + * 1 expr: expr . '+' term + * 2 | expr . '-' term + * + * $end shift, and go to state 8 + * '+' shift, and go to state 9 + * '-' shift, and go to state 10 + */ +struct result state4(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '\0': r = state8(s+1, a); break; + case '+': r = state9(s+1, a); break; + case '-': r = state10(s+1, a); break; + default: DIE(); + } + + (r.depth == 0) && DIE(); + + r.depth--; + return r; +} + +/* + * 3 expr: term . + * + * $default reduce using rule 3 (expr) + */ +struct result state5(char *s, struct args a) +{ + return (struct result){EXPR, get_arg(a, 0), 0, s}; +} + +/* + * 5 term: num . + * + * $default reduce using rule 5 (term) + */ +struct result state6(char *s, struct args a) +{ + return (struct result){TERM, get_arg(a, 0), 0, s}; +} + +/* + * 1 expr: expr . '+' term + * 2 | expr . '-' term + * 4 term: '(' expr . ')' + * + * '+' shift, and go to state 9 + * '-' shift, and go to state 10 + * ')' shift, and go to state 11 + */ +struct result state7(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '+': r = state9(s+1, a); break; + case '-': r = state10(s+1, a); break; + case ')': r = state11(s+1, a); break; + default: DIE(); + } + + (r.depth == 0) && DIE(); + + r.depth--; + return r; +} + +/* + * 0 $accept: expr $end . + * + * $default accept + */ +struct result state8(char *s, struct args a) +{ + return (struct result){EXPR, a.args[0], 2, s}; +} + +/* + * 1 expr: expr '+' . term + * + * '(' shift, and go to state 1 + * '0' shift, and go to state 2 + * '1' shift, and go to state 3 + * + * term go to state 12 + * num go to state 6 + */ +struct result state9(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '(': r = state1(s+1, a); break; + case '0': r = state2(s+1, a); break; + case '1': r = state3(s+1, a); break; + default: DIE(); + } + + while(r.depth == 0) { + switch(r.nonterm) { + case TERM: r = state12(r.s, new_arg(r.value, get_arg(a, 0))); break; + case NUM: r = state6(r.s, new_arg(r.value)); break; + default: DIE(); + } + } + + r.depth--; + return r; +} + +/* + * 2 expr: expr '-' . term + * + * '(' shift, and go to state 1 + * '0' shift, and go to state 2 + * '1' shift, and go to state 3 + * + * term go to state 13 + * num go to state 6 + */ +struct result state10(char *s, struct args a) +{ + struct result r = {0}; + switch(*s) { + case '(': r = state1(s+1, a); break; + case '0': r = state2(s+1, a); break; + case '1': r = state3(s+1, a); break; + default: DIE(); + } + + while(r.depth == 0) { + switch(r.nonterm) { + case TERM: r = state13(r.s, new_arg(get_arg(a, 0), r.value)); break; + case NUM: r = state6(r.s, new_arg(r.value)); break; + default: DIE(); + } + } + + r.depth--; + return r; +} + +/* + * 4 term: '(' expr ')' . + * + * $default reduce using rule 4 (term) + */ +struct result state11(char *s, struct args a) +{ + return (struct result){TERM, get_arg(a, 0), 2, s}; +} + +/* + * 1 expr: expr '+' term . + * + * $default reduce using rule 1 (expr) + */ +struct result state12(char *s, struct args a) +{ + return (struct result){EXPR, get_arg(a, 0) + get_arg(a, 1), 2, s}; +} + +/* + * 2 expr: expr '-' term . + * + * $default reduce using rule 2 (expr) + */ +struct result state13(char *s, struct args a) +{ + return (struct result){EXPR, get_arg(a, 0) - get_arg(a, 1), 2, s}; +} diff --git a/slr-table.c b/slr-table.c new file mode 100644 index 0000000..2454a65 --- /dev/null +++ b/slr-table.c @@ -0,0 +1,288 @@ +#include +#include + +#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 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 **follow; + +struct action { + enum action_type { + ACTION_NOT_SET = 0, ACTION_SHIFT, + ACTION_GOTO, ACTION_REDUCE, + ACTION_ACCEPT + } type; + size_t arg; +}; + +#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(); + +struct item { + size_t prod_idx; + size_t dot; +}; + +int item_eq(struct item *i1, struct item *i2) { return (i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) ? 1 : 0; } + +#define SEEN_SETS_CAP 64 +static struct { + struct item *items; + size_t nitems; + size_t state; +} 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);} + +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) +{ + printf("{"); + for(size_t i = 0; i < nset; i++) + printf("{%zu, %zu}, ", set[i].prod_idx, set[i].dot); + printf("}\n"); +} + +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++) { + 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(item_eq(&seen_sets[i].items[k], &set[j])) _seen = 1; + if(!_seen) break; + } + if(_seen) return seen_sets[i].state; + } + + // 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 = table_states++; + if(new_state >= TABLE_CAP) { + fprintf(stderr, "ERROR: TABLE_CAP exceeded\n"); + exit(1); + } + + if(itemset_insert(new_state, set, nset)) { + fprintf(stderr, "ERROR: itemset_insert failed\n"); + exit(1); + } + + return new_state; +} + +#define CLOSURE_SET_CAP 64 +#define GOTO_SET_CAP 32 +int itemset_insert(size_t state, struct item *initial_set, size_t ninitial) +{ + struct item closure_set[CLOSURE_SET_CAP]; + + size_t nclosure = itemset_closure(initial_set, ninitial, closure_set, CLOSURE_SET_CAP); + if(nclosure > CLOSURE_SET_CAP) { + fprintf(stderr, "ERROR: CLOSURE_SET_CAP exceeded\n"); + return 1; + } + + for(size_t sym = 0; sym < total_symbols; sym++) { + struct item goto_set[GOTO_SET_CAP]; + 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]) 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(symbol_is_input_end(sym)) { + if(table_insert(state, sym, (struct action){ACTION_ACCEPT, 0})) + return 1; + continue; + } + + size_t new_state = itemset_handle(goto_set, ngoto); + + if(table_insert(state, sym, (struct action){ + symbol_is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO, + new_state})) return 1; + } + + return 0; +} + +size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_set, size_t nout_max) +{ + size_t nout = nin; + + if(nout > nout_max) return nout; + for(size_t i = 0; i < nin; i++) out_set[i] = in_set[i]; + + int *is_in_closure = xcalloc(total_productions, 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; + symbol sym = p->RHS[out_set[i].dot]; + + for(size_t j = 0; j < total_productions; 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-1] = (struct item){j, 0}; + } + } + +cleanup: + free(is_in_closure); + return nout; +} + +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; +} + +void table_print() +{ + 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"); + } +} + +#ifdef _SLR_TABLE_STANDALONE + +#include "util-tables.c" + +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 < EP; } +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(); + table_allocate(); + + itemset_handle((struct item[]){{0, 0}}, 1); + table_print(); + + seen_sets_free(); + table_free(); + util_tables_free(); +} + +#endif 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 +#include +#include + +#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 -- cgit v1.2.3