summaryrefslogtreecommitdiffstats
path: root/contrib/byacc/lr0.c
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/byacc/lr0.c')
-rw-r--r--contrib/byacc/lr0.c599
1 files changed, 599 insertions, 0 deletions
diff --git a/contrib/byacc/lr0.c b/contrib/byacc/lr0.c
new file mode 100644
index 0000000..641f9f8
--- /dev/null
+++ b/contrib/byacc/lr0.c
@@ -0,0 +1,599 @@
+/* $Id: lr0.c,v 1.13 2012/05/26 00:40:47 tom Exp $ */
+
+#include "defs.h"
+
+static core *new_state(int symbol);
+static Value_t get_state(int symbol);
+static void allocate_itemsets(void);
+static void allocate_storage(void);
+static void append_states(void);
+static void free_storage(void);
+static void generate_states(void);
+static void initialize_states(void);
+static void new_itemsets(void);
+static void save_reductions(void);
+static void save_shifts(void);
+static void set_derives(void);
+static void set_nullable(void);
+
+int nstates;
+core *first_state;
+shifts *first_shift;
+reductions *first_reduction;
+
+static core **state_set;
+static core *this_state;
+static core *last_state;
+static shifts *last_shift;
+static reductions *last_reduction;
+
+static int nshifts;
+static short *shift_symbol;
+
+static Value_t *redset;
+static Value_t *shiftset;
+
+static Value_t **kernel_base;
+static Value_t **kernel_end;
+static Value_t *kernel_items;
+
+static void
+allocate_itemsets(void)
+{
+ short *itemp;
+ short *item_end;
+ int symbol;
+ int i;
+ int count;
+ int max;
+ short *symbol_count;
+
+ count = 0;
+ symbol_count = NEW2(nsyms, short);
+
+ item_end = ritem + nitems;
+ for (itemp = ritem; itemp < item_end; itemp++)
+ {
+ symbol = *itemp;
+ if (symbol >= 0)
+ {
+ count++;
+ symbol_count[symbol]++;
+ }
+ }
+
+ kernel_base = NEW2(nsyms, short *);
+ kernel_items = NEW2(count, short);
+
+ count = 0;
+ 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];
+ }
+
+ shift_symbol = symbol_count;
+ kernel_end = NEW2(nsyms, short *);
+}
+
+static void
+allocate_storage(void)
+{
+ allocate_itemsets();
+ shiftset = NEW2(nsyms, short);
+ redset = NEW2(nrules + 1, short);
+ state_set = NEW2(nitems, core *);
+}
+
+static void
+append_states(void)
+{
+ int i;
+ int j;
+ Value_t symbol;
+
+#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;
+ }
+
+ for (i = 0; i < nshifts; i++)
+ {
+ symbol = shift_symbol[i];
+ shiftset[i] = get_state(symbol);
+ }
+}
+
+static void
+free_storage(void)
+{
+ FREE(shift_symbol);
+ FREE(redset);
+ FREE(shiftset);
+ FREE(kernel_base);
+ FREE(kernel_end);
+ FREE(kernel_items);
+ FREE(state_set);
+}
+
+static void
+generate_states(void)
+{
+ allocate_storage();
+ itemset = NEW2(nitems, short);
+ ruleset = NEW2(WORDSIZE(nrules), unsigned);
+ set_first_derives();
+ initialize_states();
+
+ while (this_state)
+ {
+ closure(this_state->items, this_state->nitems);
+ save_reductions();
+ new_itemsets();
+ append_states();
+
+ if (nshifts > 0)
+ save_shifts();
+
+ this_state = this_state->next;
+ }
+
+ free_storage();
+}
+
+static Value_t
+get_state(int symbol)
+{
+ int key;
+ short *isp1;
+ short *isp2;
+ short *iend;
+ core *sp;
+ int found;
+ int n;
+
+#ifdef TRACE
+ fprintf(stderr, "Entering get_state(%d)\n", symbol);
+#endif
+
+ isp1 = kernel_base[symbol];
+ iend = kernel_end[symbol];
+ n = (int)(iend - isp1);
+
+ key = *isp1;
+ assert(0 <= key && key < nitems);
+ 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;
+ }
+ }
+ }
+ }
+ else
+ {
+ state_set[key] = sp = new_state(symbol);
+ }
+
+ return (sp->number);
+}
+
+static void
+initialize_states(void)
+{
+ unsigned i;
+ short *start_derives;
+ core *p;
+
+ start_derives = derives[start_symbol];
+ for (i = 0; start_derives[i] >= 0; ++i)
+ continue;
+
+ p = (core *)MALLOC(sizeof(core) + i * sizeof(short));
+ NO_SPACE(p);
+
+ p->next = 0;
+ p->link = 0;
+ p->number = 0;
+ p->accessing_symbol = 0;
+ p->nitems = (Value_t) i;
+
+ for (i = 0; start_derives[i] >= 0; ++i)
+ p->items[i] = rrhs[start_derives[i]];
+
+ first_state = last_state = this_state = p;
+ nstates = 1;
+}
+
+static void
+new_itemsets(void)
+{
+ Value_t i;
+ int shiftcount;
+ short *isp;
+ short *ksp;
+ Value_t symbol;
+
+ for (i = 0; i < nsyms; i++)
+ 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++ = (Value_t) (i + 1);
+ kernel_end[symbol] = ksp;
+ }
+ }
+
+ nshifts = shiftcount;
+}
+
+static core *
+new_state(int symbol)
+{
+ unsigned n;
+ core *p;
+ short *isp1;
+ short *isp2;
+ short *iend;
+
+#ifdef TRACE
+ fprintf(stderr, "Entering new_state(%d)\n", symbol);
+#endif
+
+ if (nstates >= MAXSHORT)
+ fatal("too many states");
+
+ isp1 = kernel_base[symbol];
+ iend = kernel_end[symbol];
+ n = (unsigned)(iend - isp1);
+
+ p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(short)));
+ p->accessing_symbol = (Value_t) symbol;
+ p->number = (Value_t) nstates;
+ p->nitems = (Value_t) n;
+
+ isp2 = p->items;
+ while (isp1 < iend)
+ *isp2++ = *isp1++;
+
+ last_state->next = p;
+ last_state = p;
+
+ nstates++;
+
+ return (p);
+}
+
+/* show_cores is used for debugging */
+
+void
+show_cores(void)
+{
+ core *p;
+ int i, j, k, n;
+ int itemno;
+
+ 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);
+ }
+ }
+}
+
+/* show_ritems is used for debugging */
+
+void
+show_ritems(void)
+{
+ int i;
+
+ for (i = 0; i < nitems; ++i)
+ printf("ritem[%d] = %d\n", i, ritem[i]);
+}
+
+/* show_rrhs is used for debugging */
+void
+show_rrhs(void)
+{
+ int i;
+
+ for (i = 0; i < nrules; ++i)
+ printf("rrhs[%d] = %d\n", i, rrhs[i]);
+}
+
+/* show_shifts is used for debugging */
+
+void
+show_shifts(void)
+{
+ shifts *p;
+ int i, j, k;
+
+ 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]);
+ }
+}
+
+static void
+save_shifts(void)
+{
+ shifts *p;
+ short *sp1;
+ short *sp2;
+ short *send;
+
+ p = (shifts *)allocate((sizeof(shifts) +
+ (unsigned)(nshifts - 1) * sizeof(short)));
+
+ p->number = this_state->number;
+ p->nshifts = (Value_t) nshifts;
+
+ sp1 = shiftset;
+ sp2 = p->shift;
+ send = shiftset + nshifts;
+
+ while (sp1 < send)
+ *sp2++ = *sp1++;
+
+ if (last_shift)
+ {
+ last_shift->next = p;
+ last_shift = p;
+ }
+ else
+ {
+ first_shift = p;
+ last_shift = p;
+ }
+}
+
+static void
+save_reductions(void)
+{
+ short *isp;
+ short *rp1;
+ short *rp2;
+ int item;
+ Value_t count;
+ reductions *p;
+ short *rend;
+
+ count = 0;
+ for (isp = itemset; isp < itemsetend; isp++)
+ {
+ item = ritem[*isp];
+ if (item < 0)
+ {
+ redset[count++] = (Value_t) - item;
+ }
+ }
+
+ if (count)
+ {
+ p = (reductions *)allocate((sizeof(reductions) +
+ (unsigned)(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;
+ }
+ }
+}
+
+static void
+set_derives(void)
+{
+ Value_t i, k;
+ int lhs;
+ short *rules;
+
+ derives = NEW2(nsyms, short *);
+ rules = NEW2(nvars + nrules, short);
+
+ 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++;
+ }
+
+#ifdef DEBUG
+ print_derives();
+#endif
+}
+
+#ifdef DEBUG
+void
+print_derives(void)
+{
+ int i;
+ short *sp;
+
+ printf("\nDERIVES\n\n");
+
+ 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');
+ }
+
+ putchar('\n');
+}
+#endif
+
+static void
+set_nullable(void)
+{
+ int i, j;
+ int empty;
+ int done_flag;
+
+ nullable = TMALLOC(char, nsyms);
+ NO_SPACE(nullable);
+
+ for (i = 0; i < nsyms; ++i)
+ nullable[i] = 0;
+
+ done_flag = 0;
+ while (!done_flag)
+ {
+ done_flag = 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_flag = 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]);
+ }
+#endif
+}
+
+void
+lr0(void)
+{
+ set_derives();
+ set_nullable();
+ generate_states();
+}
+
+#ifdef NO_LEAKS
+void
+lr0_leaks(void)
+{
+ DO_FREE(derives[start_symbol]);
+ DO_FREE(derives);
+ DO_FREE(nullable);
+}
+#endif
OpenPOWER on IntegriCloud