diff options
Diffstat (limited to 'clr-table.c')
| -rw-r--r-- | clr-table.c | 87 |
1 files changed, 51 insertions, 36 deletions
diff --git a/clr-table.c b/clr-table.c index 68ce3a4..37b2cd6 100644 --- a/clr-table.c +++ b/clr-table.c @@ -13,11 +13,12 @@ extern void *xcalloc(size_t n, size_t size); #include "parts/grammar.h" #include "parts/util-tables.h" -// Implements +// Implements #include "parts/table.h" #define TABLE_CAP 64 -struct action *table[TABLE_CAP]; +static struct action *__table[TABLE_CAP]; +struct action **table = __table; size_t table_states = 0; int table_fill(); @@ -33,7 +34,11 @@ struct item { symbol lookahead; }; +#ifndef _LAZY_LALR 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; } +#else +static int item_core_eq(struct item *i1, struct item *i2) { return (i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) ? 1 : 0; } +#endif #define SEEN_SETS_CAP 64 static struct { @@ -60,6 +65,7 @@ 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++) { +#ifndef _LAZY_LALR if(seen_sets[i].nitems != nset) continue; int _seen = 0; @@ -70,6 +76,15 @@ static size_t itemset_handle(struct item *set, size_t nset) if(!_seen) break; } if(_seen) return seen_sets[i].state; +#else + int _same_core = 1; + for(size_t j = 0; j < nset; j++) { + for(size_t k = 0; k < seen_sets[i].nitems; k++) + if(!item_core_eq(&seen_sets[i].items[k], &set[j])) _same_core = 0; + if(!_same_core) break; + } + if(_same_core) return seen_sets[i].state; +#endif } // 2. add set to seen_sets @@ -120,7 +135,7 @@ static int itemset_insert(size_t state, struct item *initial_set, size_t ninitia if(dot == p->nRHS) { if(sym != 0) continue; // do it 1 time - if(table_insert(state, closure_set[j].lookahead, (struct action) { + if(table_insert(state, closure_set[j].lookahead, (struct action){ ACTION_REDUCE, closure_set[j].prod_idx})) return 1; continue; @@ -137,7 +152,7 @@ static int itemset_insert(size_t state, struct item *initial_set, size_t ninitia } if(ngoto == 0) continue; - + if(symbol_is_input_end(sym)) { if(table_insert(state, sym, (struct action){ACTION_ACCEPT, 0})) return 1; @@ -164,13 +179,13 @@ static size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_ 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) + } while(0) for(size_t i = 0; i < nout; i++) { @@ -185,7 +200,7 @@ static size_t itemset_closure(struct item *in_set, size_t nin, struct item *out_ (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; @@ -233,12 +248,12 @@ void table_free() #ifdef _CLR_TABLE_STANDALONE #ifndef CHOOSE_GRAMMAR -#define CHOOSE_GRAMMAR 0 // 0 or 1 +#define CHOOSE_GRAMMAR 1 // 0 or 1 #endif // implement symbol.h enum symbol { -#if (CHOOSE_GRAMMAR == 0) +#if (CHOOSE_GRAMMAR == 0) ID, EQUAL, STAR, END_INPUT, EP, E, L, R, @@ -251,7 +266,7 @@ enum symbol { #endif }; -const size_t total_symbols = SYMBOLS_END; +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; } @@ -292,34 +307,34 @@ int main(void) #endif -/* +---+------------------------+ +/* +----------------------------+ + * | CLR | + * +---+------------------------+ * | - | 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 | + * | 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 + * + * +----------------------------+ + * | LALR | + * +---+------------------------+ + * | - | 0 1 2 3 4 5 | + * +---+------------------------+ + * | 0 | s1 s2 g4 g5 | + * | 1 | s1 s2 g3 | + * | 2 | r3 r3 | + * | 3 | r2 r2 | + * | 4 | a | + * | 5 | s1 s2 g6 | + * | 6 | r1 | + * +---+------------------------+ */ |