X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/f693ad146e6e4951662d60903b8512d518cb09da..7215de245c9b1ebb91efb16c91ff21e5f983f6d2:/src/LR0.c diff --git a/src/LR0.c b/src/LR0.c index ff5fdb61..a969abb4 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -30,18 +30,17 @@ #include "complain.h" #include "closure.h" #include "LR0.h" +#include "lalr.h" #include "reduce.h" int nstates; int final_state; state_t *first_state = NULL; shifts *first_shift = NULL; -reductions *first_reduction = NULL; static state_t *this_state = NULL; static state_t *last_state = NULL; static shifts *last_shift = NULL; -static reductions *last_reduction = NULL; static int nshifts; static short *shift_symbol = NULL; @@ -321,8 +320,8 @@ save_shifts (void) shifts *p = shifts_new (nshifts); p->number = this_state->number; - shortcpy (p->shifts, shiftset, nshifts); + this_state->shifts = p; if (last_shift) last_shift->next = p; @@ -335,16 +334,26 @@ save_shifts (void) /*------------------------------------------------------------------. | Subroutine of augment_automaton. Create the next-to-final state, | | to which a shift has already been made in the initial state. | +| | +| The task of this state consists in shifting (actually, it's a | +| goto, but shifts and gotos are both stored in SHIFTS) the start | +| symbols, hence the name. | `------------------------------------------------------------------*/ static void -insert_start_shift (void) +insert_start_shifting_state (void) { state_t *statep; shifts *sp; statep = STATE_ALLOC (0); statep->number = nstates; + + /* The distinctive feature of this state from the + eof_shifting_state, is that it is labeled as post-start-symbol + shifting. I fail to understand why this state, and the + post-start-start can't be merged into one. But it does fail if + you try. --akim */ statep->accessing_symbol = start_symbol; last_state->next = statep; @@ -352,6 +361,7 @@ insert_start_shift (void) /* Make a shift from this state to (what will be) the final state. */ sp = shifts_new (1); + statep->shifts = sp; sp->number = nstates++; sp->shifts[0] = nstates; @@ -360,6 +370,62 @@ insert_start_shift (void) } +/*-----------------------------------------------------------------. +| Subroutine of augment_automaton. Create the final state, which | +| shifts `0', the end of file. The initial state shifts the start | +| symbol, and goes to here. | +`-----------------------------------------------------------------*/ + +static void +insert_eof_shifting_state (void) +{ + state_t *statep; + shifts *sp; + + /* Make the final state--the one that follows a shift from the + next-to-final state. + The symbol for that shift is 0 (end-of-file). */ + statep = STATE_ALLOC (0); + statep->number = nstates; + + last_state->next = statep; + last_state = statep; + + /* Make the shift from the final state to the termination state. */ + sp = shifts_new (1); + statep->shifts = sp; + sp->number = nstates++; + sp->shifts[0] = nstates; + + last_shift->next = sp; + last_shift = sp; +} + + +/*---------------------------------------------------------------. +| Subroutine of augment_automaton. Create the accepting state. | +`---------------------------------------------------------------*/ + +static void +insert_accepting_state (void) +{ + state_t *statep; + + /* Note that the variable `final_state' refers to what we sometimes + call the termination state. */ + final_state = nstates; + + /* Make the termination state. */ + statep = STATE_ALLOC (0); + statep->number = nstates++; + last_state->next = statep; + last_state = statep; +} + + + + + /*------------------------------------------------------------------. | Make sure that the initial state has a shift that accepts the | | grammar's start symbol and goes to the next-to-final state, which | @@ -371,18 +437,13 @@ insert_start_shift (void) static void augment_automaton (void) { - state_t *statep; - shifts *sp; - shifts *sp1 = NULL; - - sp = first_shift; - - if (!sp->nshifts) + if (!first_shift->nshifts) { /* There are no shifts for any state. Make one shift, from the initial state to the next-to-final state. */ - sp = shifts_new (1); + shifts *sp = shifts_new (1); + first_state->shifts = sp; sp->shifts[0] = nstates; /* Initialize the chain of shifts with sp. */ @@ -391,15 +452,16 @@ augment_automaton (void) /* Create the next-to-final state, with shift to what will be the final state. */ - insert_start_shift (); + insert_start_shifting_state (); } - else if (sp->number == 0) + else if (first_shift->number == 0) { - statep = first_state->next; - + state_t *statep = first_state->next; + shifts *sp = first_shift; + shifts *sp1 = NULL; /* The states reached by shifts from FIRST_STATE are numbered 1..(SP->NSHIFTS). Look for one reached by START_SYMBOL. */ - while (statep->accessing_symbol < start_symbol + while (statep->accessing_symbol != start_symbol && statep->number < sp->nshifts) statep = statep->next; @@ -418,6 +480,7 @@ augment_automaton (void) int i; shifts *sp2 = shifts_new (sp->nshifts + 1); sp2->number = statep->number; + statep->shifts = sp2; sp2->shifts[0] = nstates; for (i = sp->nshifts; i > 0; i--) sp2->shifts[i] = sp->shifts[i - 1]; @@ -434,6 +497,7 @@ augment_automaton (void) { shifts *sp2 = shifts_new (1); sp2->number = statep->number; + statep->shifts = sp2; sp2->shifts[0] = nstates; /* Patch sp2 into the chain of shifts between sp1 and sp. */ @@ -447,14 +511,13 @@ augment_automaton (void) { int i, k; shifts *sp2; + sp = first_shift; /* There is no next-to-final state as yet. */ /* Add one more shift in first_shift, going to the next-to-final state (yet to be made). */ - sp = first_shift; - sp2 = shifts_new (sp->nshifts + 1); - + first_state->shifts = sp2; /* Stick this shift into the vector at the proper place. */ statep = first_state->next; for (k = 0, i = 0; i < sp->nshifts; k++, i++) @@ -478,14 +541,15 @@ augment_automaton (void) /* Create the next-to-final state, with shift to what will be the final state. */ - insert_start_shift (); + insert_start_shifting_state (); } } else { /* The initial state didn't even have any shifts. Give it one shift, to the next-to-final state. */ - sp = shifts_new (1); + shifts *sp = shifts_new (1); + first_state->shifts = sp; sp->shifts[0] = nstates; /* Patch sp into the chain of shifts at the beginning. */ @@ -494,33 +558,11 @@ augment_automaton (void) /* Create the next-to-final state, with shift to what will be the final state. */ - insert_start_shift (); + insert_start_shifting_state (); } - /* Make the final state--the one that follows a shift from the - next-to-final state. - The symbol for that shift is 0 (end-of-file). */ - statep = STATE_ALLOC (0); - statep->number = nstates; - last_state->next = statep; - last_state = statep; - - /* Make the shift from the final state to the termination state. */ - sp = shifts_new (1); - sp->number = nstates++; - sp->shifts[0] = nstates; - last_shift->next = sp; - last_shift = sp; - - /* Note that the variable `final_state' refers to what we sometimes call - the termination state. */ - final_state = nstates; - - /* Make the termination state. */ - statep = STATE_ALLOC (0); - statep->number = nstates++; - last_state->next = statep; - last_state = statep; + insert_eof_shifting_state (); + insert_accepting_state (); } @@ -551,17 +593,10 @@ save_reductions (void) if (count) { reductions *p = REDUCTIONS_ALLOC (count); - - p->number = this_state->number; p->nreds = count; - shortcpy (p->rules, redset, count); - if (last_reduction) - last_reduction->next = p; - else - first_reduction = p; - last_reduction = p; + this_state->reductions = p; } }