diff options
Diffstat (limited to 'yacc/lr0.c')
| -rw-r--r-- | yacc/lr0.c | 370 |
1 files changed, 185 insertions, 185 deletions
diff --git a/yacc/lr0.c b/yacc/lr0.c index f4f0a4cd8..e05fcb072 100644 --- a/yacc/lr0.c +++ b/yacc/lr0.c @@ -70,12 +70,12 @@ void allocate_itemsets(void) item_end = ritem + nitems; for (itemp = ritem; itemp < item_end; itemp++) { - symbol = *itemp; - if (symbol >= 0) - { - count++; - symbol_count[symbol]++; - } + symbol = *itemp; + if (symbol >= 0) + { + count++; + symbol_count[symbol]++; + } } kernel_base = NEW2(nsyms, short *); @@ -85,10 +85,10 @@ void allocate_itemsets(void) max = 0; for (i = 0; i < nsyms; i++) { - kernel_base[i] = kernel_items + count; - count += symbol_count[i]; - if (max < symbol_count[i]) - max = symbol_count[i]; + kernel_base[i] = kernel_items + count; + count += symbol_count[i]; + if (max < symbol_count[i]) + max = symbol_count[i]; } shift_symbol = symbol_count; @@ -111,25 +111,25 @@ void append_states(void) register int j; register int symbol; -#ifdef TRACE +#ifdef TRACE fprintf(stderr, "Entering append_states()\n"); #endif for (i = 1; i < nshifts; i++) { - symbol = shift_symbol[i]; - j = i; - while (j > 0 && shift_symbol[j - 1] > symbol) - { - shift_symbol[j] = shift_symbol[j - 1]; - j--; - } - shift_symbol[j] = symbol; + symbol = shift_symbol[i]; + j = i; + while (j > 0 && shift_symbol[j - 1] > symbol) + { + shift_symbol[j] = shift_symbol[j - 1]; + j--; + } + shift_symbol[j] = symbol; } for (i = 0; i < nshifts; i++) { - symbol = shift_symbol[i]; - shiftset[i] = get_state(symbol); + symbol = shift_symbol[i]; + shiftset[i] = get_state(symbol); } } @@ -157,15 +157,15 @@ void generate_states(void) while (this_state) { - closure(this_state->items, this_state->nitems); - save_reductions(); - new_itemsets(); - append_states(); + closure(this_state->items, this_state->nitems); + save_reductions(); + new_itemsets(); + append_states(); - if (nshifts > 0) - save_shifts(); + if (nshifts > 0) + save_shifts(); - this_state = this_state->next; + this_state = this_state->next; } finalize_closure(); @@ -185,7 +185,7 @@ get_state(int symbol) register int found; register int n; -#ifdef TRACE +#ifdef TRACE fprintf(stderr, "Entering get_state(%d)\n", symbol); #endif @@ -198,39 +198,39 @@ get_state(int symbol) sp = state_set[key]; if (sp) { - found = 0; - while (!found) - { - if (sp->nitems == n) - { - found = 1; - isp1 = kernel_base[symbol]; - isp2 = sp->items; - - while (found && isp1 < iend) - { - if (*isp1++ != *isp2++) - found = 0; - } - } - - if (!found) - { - if (sp->link) - { - sp = sp->link; - } - else - { - sp = sp->link = new_state(symbol); - found = 1; - } - } - } + found = 0; + while (!found) + { + if (sp->nitems == n) + { + found = 1; + isp1 = kernel_base[symbol]; + isp2 = sp->items; + + while (found && isp1 < iend) + { + if (*isp1++ != *isp2++) + found = 0; + } + } + + if (!found) + { + if (sp->link) + { + sp = sp->link; + } + else + { + sp = sp->link = new_state(symbol); + found = 1; + } + } + } } else { - state_set[key] = sp = new_state(symbol); + state_set[key] = sp = new_state(symbol); } return (sp->number); @@ -246,7 +246,7 @@ void initialize_states(void) start_derives = derives[start_symbol]; for (i = 0; start_derives[i] >= 0; ++i) - continue; + continue; p = (core *) MALLOC(sizeof(core) + i*sizeof(short)); if (p == 0) no_space(); @@ -258,7 +258,7 @@ void initialize_states(void) p->nitems = i; for (i = 0; start_derives[i] >= 0; ++i) - p->items[i] = rrhs[start_derives[i]]; + p->items[i] = rrhs[start_derives[i]]; first_state = last_state = this_state = p; nstates = 1; @@ -274,26 +274,26 @@ void new_itemsets(void) register int symbol; for (i = 0; i < nsyms; i++) - kernel_end[i] = 0; + kernel_end[i] = 0; shiftcount = 0; isp = itemset; while (isp < itemsetend) { - i = *isp++; - symbol = ritem[i]; - if (symbol > 0) - { - ksp = kernel_end[symbol]; - if (!ksp) - { - shift_symbol[shiftcount++] = symbol; - ksp = kernel_base[symbol]; - } - - *ksp++ = i + 1; - kernel_end[symbol] = ksp; - } + i = *isp++; + symbol = ritem[i]; + if (symbol > 0) + { + ksp = kernel_end[symbol]; + if (!ksp) + { + shift_symbol[shiftcount++] = symbol; + ksp = kernel_base[symbol]; + } + + *ksp++ = i + 1; + kernel_end[symbol] = ksp; + } } nshifts = shiftcount; @@ -310,12 +310,12 @@ new_state(int symbol) register short *isp2; register short *iend; -#ifdef TRACE +#ifdef TRACE fprintf(stderr, "Entering new_state(%d)\n", symbol); #endif if (nstates >= MAXSHORT) - fatal("too many states"); + fatal("too many states"); isp1 = kernel_base[symbol]; iend = kernel_end[symbol]; @@ -328,7 +328,7 @@ new_state(int symbol) isp2 = p->items; while (isp1 < iend) - *isp2++ = *isp1++; + *isp2++ = *isp1++; last_state->next = p; last_state = p; @@ -350,26 +350,26 @@ void show_cores(void) k = 0; for (p = first_state; p; ++k, p = p->next) { - if (k) printf("\n"); - printf("state %d, number = %d, accessing symbol = %s\n", - k, p->number, symbol_name[p->accessing_symbol]); - n = p->nitems; - for (i = 0; i < n; ++i) - { - itemno = p->items[i]; - printf("%4d ", itemno); - j = itemno; - while (ritem[j] >= 0) ++j; - printf("%s :", symbol_name[rlhs[-ritem[j]]]); - j = rrhs[-ritem[j]]; - while (j < itemno) - printf(" %s", symbol_name[ritem[j++]]); - printf(" ."); - while (ritem[j] >= 0) - printf(" %s", symbol_name[ritem[j++]]); - printf("\n"); - fflush(stdout); - } + if (k) printf("\n"); + printf("state %d, number = %d, accessing symbol = %s\n", + k, p->number, symbol_name[p->accessing_symbol]); + n = p->nitems; + for (i = 0; i < n; ++i) + { + itemno = p->items[i]; + printf("%4d ", itemno); + j = itemno; + while (ritem[j] >= 0) ++j; + printf("%s :", symbol_name[rlhs[-ritem[j]]]); + j = rrhs[-ritem[j]]; + while (j < itemno) + printf(" %s", symbol_name[ritem[j++]]); + printf(" ."); + while (ritem[j] >= 0) + printf(" %s", symbol_name[ritem[j++]]); + printf("\n"); + fflush(stdout); + } } } @@ -381,7 +381,7 @@ void show_ritems(void) int i; for (i = 0; i < nitems; ++i) - printf("ritem[%d] = %d\n", i, ritem[i]); + printf("ritem[%d] = %d\n", i, ritem[i]); } @@ -392,7 +392,7 @@ void show_rrhs(void) int i; for (i = 0; i < nrules; ++i) - printf("rrhs[%d] = %d\n", i, rrhs[i]); + printf("rrhs[%d] = %d\n", i, rrhs[i]); } @@ -406,12 +406,12 @@ void show_shifts(void) k = 0; for (p = first_shift; p; ++k, p = p->next) { - if (k) printf("\n"); - printf("shift %d, number = %d, nshifts = %d\n", k, p->number, - p->nshifts); - j = p->nshifts; - for (i = 0; i < j; ++i) - printf("\t%d\n", p->shift[i]); + if (k) printf("\n"); + printf("shift %d, number = %d, nshifts = %d\n", k, p->number, + p->nshifts); + j = p->nshifts; + for (i = 0; i < j; ++i) + printf("\t%d\n", p->shift[i]); } } @@ -424,7 +424,7 @@ void save_shifts(void) register short *send; p = (shifts *) allocate((unsigned) (sizeof(shifts) + - (nshifts - 1) * sizeof(short))); + (nshifts - 1) * sizeof(short))); p->number = this_state->number; p->nshifts = nshifts; @@ -434,17 +434,17 @@ void save_shifts(void) send = shiftset + nshifts; while (sp1 < send) - *sp2++ = *sp1++; + *sp2++ = *sp1++; if (last_shift) { - last_shift->next = p; - last_shift = p; + last_shift->next = p; + last_shift = p; } else { - first_shift = p; - last_shift = p; + first_shift = p; + last_shift = p; } } @@ -463,38 +463,38 @@ void save_reductions(void) count = 0; for (isp = itemset; isp < itemsetend; isp++) { - item = ritem[*isp]; - if (item < 0) - { - redset[count++] = -item; - } + item = ritem[*isp]; + if (item < 0) + { + redset[count++] = -item; + } } if (count) { - p = (reductions *) allocate((unsigned) (sizeof(reductions) + - (count - 1) * sizeof(short))); - - p->number = this_state->number; - p->nreds = count; - - rp1 = redset; - rp2 = p->rules; - rend = rp1 + count; - - while (rp1 < rend) - *rp2++ = *rp1++; - - if (last_reduction) - { - last_reduction->next = p; - last_reduction = p; - } - else - { - first_reduction = p; - last_reduction = p; - } + p = (reductions *) allocate((unsigned) (sizeof(reductions) + + (count - 1) * sizeof(short))); + + p->number = this_state->number; + p->nreds = count; + + rp1 = redset; + rp2 = p->rules; + rend = rp1 + count; + + while (rp1 < rend) + *rp2++ = *rp1++; + + if (last_reduction) + { + last_reduction->next = p; + last_reduction = p; + } + else + { + first_reduction = p; + last_reduction = p; + } } } @@ -511,20 +511,20 @@ void set_derives(void) k = 0; for (lhs = start_symbol; lhs < nsyms; lhs++) { - derives[lhs] = rules + k; - for (i = 0; i < nrules; i++) - { - if (rlhs[i] == lhs) - { - rules[k] = i; - k++; - } - } - rules[k] = -1; - k++; + derives[lhs] = rules + k; + for (i = 0; i < nrules; i++) + { + if (rlhs[i] == lhs) + { + rules[k] = i; + k++; + } + } + rules[k] = -1; + k++; } -#ifdef DEBUG +#ifdef DEBUG print_derives(); #endif } @@ -535,7 +535,7 @@ void free_derives(void) FREE(derives); } -#ifdef DEBUG +#ifdef DEBUG void print_derives(void) { register int i; @@ -545,12 +545,12 @@ void print_derives(void) for (i = start_symbol; i < nsyms; i++) { - printf("%s derives ", symbol_name[i]); - for (sp = derives[i]; *sp >= 0; sp++) - { - printf(" %d", *sp); - } - putchar('\n'); + printf("%s derives ", symbol_name[i]); + for (sp = derives[i]; *sp >= 0; sp++) + { + printf(" %d", *sp); + } + putchar('\n'); } putchar('\n'); @@ -568,40 +568,40 @@ void set_nullable(void) if (nullable == 0) no_space(); for (i = 0; i < nsyms; ++i) - nullable[i] = 0; + nullable[i] = 0; done = 0; while (!done) { - done = 1; - for (i = 1; i < nitems; i++) - { - empty = 1; - while ((j = ritem[i]) >= 0) - { - if (!nullable[j]) - empty = 0; - ++i; - } - if (empty) - { - j = rlhs[-j]; - if (!nullable[j]) - { - nullable[j] = 1; - done = 0; - } - } - } + done = 1; + for (i = 1; i < nitems; i++) + { + empty = 1; + while ((j = ritem[i]) >= 0) + { + if (!nullable[j]) + empty = 0; + ++i; + } + if (empty) + { + j = rlhs[-j]; + if (!nullable[j]) + { + nullable[j] = 1; + done = 0; + } + } + } } #ifdef DEBUG for (i = 0; i < nsyms; i++) { - if (nullable[i]) - printf("%s is nullable\n", symbol_name[i]); - else - printf("%s is not nullable\n", symbol_name[i]); + if (nullable[i]) + printf("%s is nullable\n", symbol_name[i]); + else + printf("%s is not nullable\n", symbol_name[i]); } #endif } |