From 1cbaa39e3cc7e8948cbd5be5f2d18170fcdebfe0 Mon Sep 17 00:00:00 2001 From: kartofen Date: Sat, 21 Jun 2025 23:52:33 +0300 Subject: make lr0 and lexer modular --- build.sh | 6 +- lexer.c | 88 ++++++++-------- lr0-table.c | 326 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lr0.c | 304 -------------------------------------------------------- 4 files changed, 377 insertions(+), 347 deletions(-) create mode 100644 lr0-table.c delete mode 100644 lr0.c diff --git a/build.sh b/build.sh index e1367ca..d69fa83 100755 --- a/build.sh +++ b/build.sh @@ -2,12 +2,12 @@ set -xe -# gcc -Wall -Wextra -g lexer.c -o lexer +# 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.c -o lr0 +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 +valgrind --leak-check=full --show-leak-kinds=all -s ./lr0-table diff --git a/lexer.c b/lexer.c index 6df77c6..2fca9a7 100644 --- a/lexer.c +++ b/lexer.c @@ -10,12 +10,14 @@ // and more characters // - add easier way to write chars to bits (maybe a singe string) +#define ARR_LEN(arr) (sizeof(arr) / sizeof(*arr)) -#define ARR_LENGTH(arr) (sizeof(arr)/sizeof(*arr)) +typedef int token; +extern const char *const token_to_string[]; +extern const struct string_token { char *s; token t;} strings[]; +extern const token separators[]; -#define popcount(x) (__builtin_popcount(x)) - -#define MAPPED_CHARS 32 +#ifdef _LEXER_STANDALONE #define TOKENS(X) \ X(TOKEN_NONE) \ @@ -33,13 +35,13 @@ enum token { TOKENS(TOKEN_ENUM) }; -const char * const to_string[] = { +const char * const token_to_string[] = { TOKENS(TOKEN_STRING) }; -const struct { +const struct string_token { char *s; - enum token t; + token t; } strings[] = { {"test", TOKEN_TEST}, {"retarded", TOKEN_RETARDED}, @@ -47,6 +49,10 @@ const struct { {"tits", TOKEN_TITS}, }; +const token separators[] = {['{'] = TOKEN_LPAREN, ['}'] = TOKEN_RPAREN}; + +#endif + const uint8_t char_to_bit[256] = { ['a'] = 2, ['b'] = 3, ['c'] = 4, ['d'] = 5, ['e'] = 6, ['f'] = 7, ['g'] = 8, ['h'] = 9, ['i'] = 10, ['j'] = 11, ['k'] = 12, ['l'] = 13, @@ -55,26 +61,24 @@ const uint8_t char_to_bit[256] = { ['y'] = 26, ['z'] = 27, [ 0 ] = 1, [' '] = 1 }; -const enum token separators[] = { - ['{'] = TOKEN_LPAREN, - ['}'] = TOKEN_RPAREN -}; - struct level { uint64_t bit_mask; uint64_t *token_masks; }; -struct level start_level = {0}; -struct level *bit_to_ptr[MAPPED_CHARS] = {0}; +#define MAPPED_CHARS 32 +static struct level start_level = {0}; +static struct level *bit_to_ptr[MAPPED_CHARS] = {0}; static size_t num_levels; #define CHAR_TO_PTR(c) (bit_to_ptr[char_to_bit[c]]) -int compile_tables(void) +#define popcount(x) (__builtin_popcount(x)) + +int compile_lextables(void) { // max number of levels - for(size_t i = 0; i < ARR_LENGTH(strings); i++) + for(size_t i = 0; i < ARR_LEN(strings); i++) if(strlen(strings[i].s) > num_levels) num_levels = strlen(strings[i].s); // allocated levels @@ -86,11 +90,11 @@ int compile_tables(void) // BUG: everything is repeated for the start_level // populate bit_masks - for(size_t i = 0; i < ARR_LENGTH(strings); i++) { + for(size_t i = 0; i < ARR_LEN(strings); i++) { struct level *l = &start_level; for(size_t j = 0; j < strlen(strings[i].s)+1; j++) { uint8_t bit = char_to_bit[strings[i].s[j]]; - + l->bit_mask |= 1 << bit; l = &bit_to_ptr[bit][j]; } @@ -105,50 +109,50 @@ int compile_tables(void) * sizeof(*l->token_masks)); memset(l->token_masks, 0, popcount(l->bit_mask) * sizeof(*l->token_masks)); - + l = &bit_to_ptr[i][j]; } } // populate token_masks - for(size_t i = 0; i < ARR_LENGTH(strings); i++) { + for(size_t i = 0; i < ARR_LEN(strings); i++) { struct level *l = &start_level; for(size_t j = 0; j < strlen(strings[i].s)+1; j++) { - uint8_t bit = char_to_bit[strings[i].s[j]]; + uint8_t bit = char_to_bit[strings[i].s[j]]; uint8_t idx = popcount(l->bit_mask & ((1 << bit) - 1)); l->token_masks[idx] |= 1 << strings[i].t; l = &bit_to_ptr[bit][j]; } } - + return 0; } -void print_tables(void) +void print_lextables(void) { - for(size_t i = 0; i < 256; i++) + for(size_t i = 0; i < 256; i++) for(size_t j = 0; j < num_levels; j++) if(CHAR_TO_PTR(i)[j].bit_mask) { - printf("%c, %d, %32b ", (char)i, j, CHAR_TO_PTR(i)[j].bit_mask); + printf("%c, %zu, %32lb ", (char)i, j, CHAR_TO_PTR(i)[j].bit_mask); printf("{ "); for(size_t k = 0; k < popcount(CHAR_TO_PTR(i)[j].bit_mask); k++) - printf("%b ", CHAR_TO_PTR(i)[j].token_masks[k]); + printf("%lb ", CHAR_TO_PTR(i)[j].token_masks[k]); printf(" }\n"); } - - printf(" %32b ", start_level.bit_mask); + + printf(" %32lb ", start_level.bit_mask); printf("{ "); for(size_t k = 0; k < popcount(start_level.bit_mask); k++) - printf("%b ", start_level.token_masks[k]); + printf("%lb ", start_level.token_masks[k]); printf(" }\n"); printf(" %32s\n", "zyxwvutsrqponmlkjihgfedcbaE "); } -int tokenize_string(char *string, enum token *t, size_t t_len) +int tokenize_string(char *string, token *t, size_t t_len) { size_t ntokens = 0; size_t i = 0; @@ -170,14 +174,14 @@ int tokenize_string(char *string, enum token *t, size_t t_len) while(!separators[string[i]] && char_to_bit[string[i]] != 1) i++; break; } - + uint64_t idx = popcount(l->bit_mask & ((1 << bit) - 1)); token_mask &= l->token_masks[idx]; if(bit == 1) break; i++; } - + // BUG: not checking of ntokens is in t_len if(token_mask) t[ntokens++] = __builtin_ctz(token_mask); @@ -188,11 +192,11 @@ int tokenize_string(char *string, enum token *t, size_t t_len) off = ++i; } - + return ntokens; } -void free_tables(void) +void free_lextables(void) { free(start_level.token_masks); for(size_t i = 0; i < MAPPED_CHARS; i++) { @@ -204,22 +208,26 @@ void free_tables(void) } } +#ifdef _LEXER_STANDALONE + // exit with a given code, default is 1 #define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1) int main(void) { - compile_tables() && DIE(); + compile_lextables() && DIE(); - enum token t[120] = {0}; + token t[120] = {0}; size_t ntokens = tokenize_string("tits tits2 retarded wow{tits}test test }}{{test", t, 120); ntokens || DIE(10); - + for(size_t i = 0; i < ntokens; i++) - printf("%s\n", to_string[t[i]]); + printf("%s\n", token_to_string[t[i]]); - print_tables(); - free_tables(); + print_lextables(); + free_lextables(); return 0; } + +#endif diff --git a/lr0-table.c b/lr0-table.c new file mode 100644 index 0000000..721bdb5 --- /dev/null +++ b/lr0-table.c @@ -0,0 +1,326 @@ +#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/lr0.c b/lr0.c deleted file mode 100644 index ecd12b5..0000000 --- a/lr0.c +++ /dev/null @@ -1,304 +0,0 @@ -#include -#include - -#define ARR_LEN(...) (sizeof(__VA_ARGS__) / sizeof(*(__VA_ARGS__))) - -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, -->, LPAREN, E, RPAREN), - PROD(T, -->, N), - PROD(N, -->, N0), - PROD(N, -->, N1), -}; - -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"); - } -} - -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 { - ACTION_NOT_SET = 0, ACTION_SHIFT, - ACTION_GOTO, ACTION_REDUCE, - ACTION_ACCEPT - } type; - size_t arg; -}; - -// 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) { return (i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) ? 1 : 0; } -void print_set(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"); -} - -#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 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 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) -{ - fill_follow_table(); - - handle_set((struct item[]){{0, 0}}, 1); - print_table(); - - free_seen_sets(); -} - -size_t handle_set(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(items_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 = 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); - } - - return new_state; -} - -#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; - } - - for(size_t sym = 0; sym < SYMBOL_COUNT; 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(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); - - if(table_insert(state, sym, (struct action){ - is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO, - new_state})) return 1; - } - - return 0; -} - -size_t 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(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-1] = (struct item){j, 0}; - } - } - -cleanup: - free(is_in_closure); - return nout; -} - -void fill_follow_table() -{ - 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; -} -- cgit v1.2.3