#include "defs.h"

Include dependency graph for lr0.c:

Functions
int	get_state ()

core *	new_state ()

	allocate_itemsets ()

	allocate_storage ()

	append_states ()

	free_storage ()

	generate_states ()

int	get_state (int symbol)

	initialize_states ()

	new_itemsets ()

core *	new_state (int symbol)

	show_cores ()

	show_ritems ()

	show_rrhs ()

	show_shifts ()

	save_shifts ()

	save_reductions ()

	set_derives ()

	free_derives ()

	set_nullable ()

	free_nullable ()

	lr0 ()

Variables
short *	itemset

short *	itemsetend

unsigned *	ruleset
	Bitset of closure items for the current state. More...

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 short *	redset

static short *	shiftset

static short **	kernel_base

static short **	kernel_end

static short *	kernel_items

Function Documentation

allocate_itemsets ( )

Definition at line 33 of file lr0.c.

References kernel_base, kernel_end, kernel_items, NEW2, nitems, nsyms, ritem, and shift_symbol.

Referenced by allocate_storage().

 {
     register short *itemp;
     register short *item_end;
     register int symbol;
     register int i;
     register int count;
     register int max;
     register 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 *);
 }

Here is the caller graph for this function:

allocate_storage ( )

Definition at line 75 of file lr0.c.

References allocate_itemsets(), NEW2, nitems, nrules, nsyms, redset, and shiftset.

Referenced by generate_states().

 {
     allocate_itemsets();
     shiftset = NEW2(nsyms, short);
     redset = NEW2(nrules + 1, short);
     state_set = NEW2(nitems, core *);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

append_states ( )

Definition at line 84 of file lr0.c.

References get_state(), nshifts, shift_symbol, and shiftset.

Referenced by generate_states().

 {
     register int i;
     register int j;
     register int 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);
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

free_derives ( )

Definition at line 509 of file lr0.c.

References derives, FREE, and start_symbol.

 {
     FREE(derives[start_symbol]);
     FREE(derives);
 }

free_nullable ( )

Definition at line 587 of file lr0.c.

References FREE, and nullable.

 {
     FREE(nullable);
 }

free_storage ( )

Definition at line 113 of file lr0.c.

References FREE, kernel_base, kernel_end, kernel_items, redset, shift_symbol, and shiftset.

Referenced by generate_states().

 {
     FREE(shift_symbol);
     FREE(redset);
     FREE(shiftset);
     FREE(kernel_base);
     FREE(kernel_end);
     FREE(kernel_items);
     FREE(state_set);
 }

Here is the caller graph for this function:

generate_states ( )

Definition at line 126 of file lr0.c.

References allocate_storage(), append_states(), closure(), finalize_closure(), free_storage(), initialize_states(), core::items, itemset, NEW2, new_itemsets(), core::next, core::nitems, nitems, nrules, nshifts, ruleset, save_reductions(), save_shifts(), set_first_derives(), and WORDSIZE.

Referenced by lr0().

 {
     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;
     }
 
     finalize_closure();
     free_storage();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

int get_state ( )

Referenced by append_states().

Here is the caller graph for this function:

int get_state ( int symbol )

Definition at line 154 of file lr0.c.

References core::items, kernel_base, kernel_end, core::link, new_state(), core::nitems, nitems, and core::number.

 {
     register int key;
     register short *isp1;
     register short *isp2;
     register short *iend;
     register core *sp;
     register int found;
     register int n;
 
 #ifdef TRACE
     fprintf(stderr, "Entering get_state(%d)\n", symbol);
 #endif
 
     isp1 = kernel_base[symbol];
     iend = kernel_end[symbol];
     n = 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);
 }

Here is the call graph for this function:

initialize_states ( )

Definition at line 218 of file lr0.c.

References core::accessing_symbol, derives, core::items, core::link, MALLOC, core::next, core::nitems, no_space(), nstates, core::number, rrhs, and start_symbol.

Referenced by generate_states().

 {
     register int i;
     register short *start_derives;
     register core *p;
 
     start_derives = derives[start_symbol];
     for (i = 0; start_derives[i] >= 0; ++i)
         continue;
 
     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
     if (p == 0) no_space();
 
     p->next = 0;
     p->link = 0;
     p->number = 0;
     p->accessing_symbol = 0;
     p->nitems = 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;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

lr0 ( )

Definition at line 593 of file lr0.c.

References generate_states(), set_derives(), and set_nullable().

Referenced by main().

 {
     set_derives();
     set_nullable();
     generate_states();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

new_itemsets ( )

Definition at line 245 of file lr0.c.

References itemset, itemsetend, kernel_base, kernel_end, nshifts, nsyms, ritem, and shift_symbol.

Referenced by generate_states().

 {
     register int i;
     register int shiftcount;
     register short *isp;
     register short *ksp;
     register int 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++ = i + 1;
             kernel_end[symbol] = ksp;
         }
     }
 
     nshifts = shiftcount;
 }

Here is the caller graph for this function:

core* new_state ( )

Referenced by get_state().

Here is the caller graph for this function:

core* new_state ( int symbol )

Definition at line 282 of file lr0.c.

References core::accessing_symbol, allocate(), fatal(), core::items, kernel_base, kernel_end, MAXSHORT, core::next, core::nitems, nstates, and core::number.

 {
     register int n;
     register core *p;
     register short *isp1;
     register short *isp2;
     register 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 = iend - isp1;
 
     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
     p->accessing_symbol = symbol;
     p->number = nstates;
     p->nitems = n;
 
     isp2 = p->items;
     while (isp1 < iend)
         *isp2++ = *isp1++;
 
     last_state->next = p;
     last_state = p;
 
     nstates++;
 
     return (p);
 }

Here is the call graph for this function:

save_reductions ( )

Definition at line 430 of file lr0.c.

References allocate(), itemset, itemsetend, reductions::next, reductions::nreds, core::number, reductions::number, redset, ritem, and reductions::rules.

Referenced by generate_states().

 {
     register short *isp;
     register short *rp1;
     register short *rp2;
     register int item;
     register int count;
     register reductions *p;
     register short *rend;
 
     count = 0;
     for (isp = itemset; isp < itemsetend; isp++)
     {
         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;
         }
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

save_shifts ( )

Definition at line 396 of file lr0.c.

References allocate(), shifts::next, nshifts, shifts::nshifts, core::number, shifts::number, shifts::shift, and shiftset.

Referenced by generate_states().

 {
     register shifts *p;
     register short *sp1;
     register short *sp2;
     register short *send;
 
     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
                         (nshifts - 1) * sizeof(short)));
 
     p->number = this_state->number;
     p->nshifts = 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;
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

set_derives ( )

Definition at line 479 of file lr0.c.

References derives, NEW2, nrules, nsyms, nvars, rlhs, and start_symbol.

Referenced by lr0().

 {
     register int i, k;
     register int lhs;
     register 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
 }

Here is the caller graph for this function:

set_nullable ( )

Definition at line 538 of file lr0.c.

References done(), MALLOC, nitems, no_space(), nsyms, nullable, ritem, rlhs, and symbol_name.

Referenced by lr0().

 {
     register int i, j;
     register int empty;
     int done;
 
     nullable = MALLOC(nsyms);
     if (nullable == 0) no_space();
 
     for (i = 0; i < nsyms; ++i)
         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;
                 }
             }
         }
     }
 
 #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
 }

Here is the call graph for this function:

Here is the caller graph for this function:

show_cores ( )

Definition at line 322 of file lr0.c.

References core::next, ritem, rlhs, rrhs, and symbol_name.

 {
     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 ( )

Definition at line 357 of file lr0.c.

References nitems, and ritem.

 {
     int i;
 
     for (i = 0; i < nitems; ++i)
         printf("ritem[%d] = %d\n", i, ritem[i]);
 }

show_rrhs ( )

Definition at line 367 of file lr0.c.

References nrules, and rrhs.

 {
     int i;
 
     for (i = 0; i < nrules; ++i)
         printf("rrhs[%d] = %d\n", i, rrhs[i]);
 }

show_shifts ( )

Definition at line 378 of file lr0.c.

References shifts::next.

 {
     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]);
     }
 }

Variable Documentation

reductions* first_reduction

Definition at line 11 of file lr0.c.

Referenced by free_reductions(), and set_reduction_table().

shifts* first_shift

Definition at line 10 of file lr0.c.

Referenced by free_shifts(), set_goto_map(), and set_shift_table().

core* first_state

Definition at line 9 of file lr0.c.

Referenced by free_itemsets(), set_accessing_symbol(), and set_state_table().

short* itemset

Definition at line 3 of file closure.c.

Referenced by closure(), finalize_closure(), generate_states(), new_itemsets(), and save_reductions().

short* itemsetend

Definition at line 4 of file closure.c.

Referenced by closure(), new_itemsets(), and save_reductions().

short** kernel_base

static

Definition at line 28 of file lr0.c.

Referenced by allocate_itemsets(), free_storage(), get_state(), new_itemsets(), and new_state().

short** kernel_end

static

Definition at line 29 of file lr0.c.

Referenced by allocate_itemsets(), free_storage(), get_state(), new_itemsets(), and new_state().

short* kernel_items

static

Definition at line 30 of file lr0.c.

Referenced by allocate_itemsets(), and free_storage().

reductions* last_reduction

static

Definition at line 20 of file lr0.c.

shifts* last_shift

static

Definition at line 19 of file lr0.c.

core* last_state

static

Definition at line 18 of file lr0.c.

int nshifts

static

Definition at line 22 of file lr0.c.

Referenced by append_states(), generate_states(), new_itemsets(), and save_shifts().

int nstates

Definition at line 8 of file lr0.c.

Referenced by compute_lookaheads(), default_goto(), defreds(), free_parser(), goto_actions(), initialize_LA(), initialize_states(), log_conflicts(), make_parser(), matching_vector(), new_state(), output_actions(), output_base(), output_yydefred(), remove_conflicts(), save_column(), set_accessing_symbol(), set_reduction_table(), set_shift_table(), set_state_table(), token_actions(), unused_rules(), and verbose().

short* redset

static

Definition at line 25 of file lr0.c.

Referenced by allocate_storage(), free_storage(), and save_reductions().

unsigned* ruleset

Bitset of closure items for the current state.

The n-th bit is set if and only if the n-th rule is part of the closure of the currently analyzed state. This variable is allocated in generate_states(), overwritten by each iteration of closure() and deleted in finalize_closure().

Definition at line 13 of file closure.c.

Referenced by closure(), finalize_closure(), and generate_states().

short* shift_symbol

static

Definition at line 23 of file lr0.c.

Referenced by allocate_itemsets(), append_states(), free_storage(), and new_itemsets().

short* shiftset

static

Definition at line 26 of file lr0.c.

Referenced by allocate_storage(), append_states(), free_storage(), and save_shifts().