Path: utzoo!attcan!uunet!husc6!bloom-beacon!gatech!purdue!decwrl!hplabs!felix!dhw68k!macintosh
From: wetter@tybalt.caltech.edu (Pierce T. Wetter)
Newsgroups: comp.sources.mac
Subject: Bison Macintosh Sources (part 3 of 6)
Message-ID: <8034@dhw68k.cts.com>
Date: 16 May 88 03:24:49 GMT
References: <7986@dhw68k.cts.com> <8002@dhw68k.cts.com>
Sender: macintosh@dhw68k.cts.com
Organization: California Institute of Technology
Lines: 1889
Approved: bytebug@dhw68k.cts.com (Roger L. Long)

[Bison Macintosh Sources - part 3 of 6]

---
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	Bison/lalr.c
#	Bison/lex.c
#	Bison/lro.c
# This archive created: Sat May 14 02:41:51 1988
# By:	Roger L. Long (bytebug@dhw68k.cts.com)
export PATH; PATH=/bin:$PATH
echo shar: extracting "'lalr.c'" '(13469 characters)'
if test -f 'lalr.c'
then
	echo shar: will not over-write existing file "'lalr.c'"
else
sed 's/^X//' << \SHAR_EOF > 'lalr.c'
X/* Compute look-ahead criteria for bison,
X   Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
X
XBISON is distributed in the hope that it will be useful, but WITHOUT ANY
XWARRANTY.  No author or distributor accepts responsibility to anyone
Xfor the consequences of using it or for whether it serves any
Xparticular purpose or works at all, unless he says so in writing.
XRefer to the BISON General Public License for full details.
X
XEveryone is granted permission to copy, modify and redistribute BISON,
Xbut only under the conditions described in the BISON General Public
XLicense.  A copy of this license is supposed to have been given to you
Xalong with BISON so you can know your rights and responsibilities.  It
Xshould be in a file named COPYING.  Among other things, the copyright
Xnotice and this notice must be preserved on all copies.
X
X In other words, you are welcome to use, share and improve this program.
X You are forbidden to forbid anyone else to use, share and improve
X what you give them.   Help stamp out software-hoarding!  */
X
X/* Compute how to make the finite state machine deterministic;
X find which rules need lookahead in each state, and which lookahead tokens they accept.
X
Xlalr(), the entry point, builds these data structures:
X
Xgoto_map, from_state and to_state 
X record each shift transition which accepts a variable (a nonterminal).
Xngotos is the number of such transitions.
Xfrom_state[t] is the state number which a transition leads from
Xand to_state[t] is the state number it leads to.
XAll the transitions that accept a particular variable are grouped together and
Xgoto_map[i - ntokens] is the index in from_state and to_state of the first of them.
X
Xconsistent[s] is nonzero if no lookahead is needed to decide what to do in state s.
X
XLAruleno is a vector which records the rules that need lookahead in various states.
XThe elements of LAruleno that apply to state s are those from
X lookaheads[s] through lookaheads[s+1]-1.
XEach element of LAruleno is a rule number.
X
XIf lr is the length of LAruleno, then a number from 0 to lr-1 
Xcan specify both a rule and a state where the rule might be applied.
X
XLA is a lr by ntokens matrix of bits.
XLA[l, i] is 1 if the rule LAruleno[l] is applicable in the appropriate state
X when the next token is symbol i.
XIf LA[l, i] and LA[l, j] are both 1 for i != j, it is a conflict.
X*/
X
X#include <stdio.h>
X#include "machine.h"
X#include "types.h"
X#include "state.h"
X#include "new.h"
X#include "gram.h"
X
X
Xextern short **derives;
Xextern char *nullable;
X
X
Xint tokensetsize;
Xshort *lookaheads;
Xshort *LAruleno;
Xunsigned *LA;
Xshort *accessing_symbol;
Xchar *consistent;
Xcore **state_table;
Xshifts **shift_table;
Xreductions **reduction_table;
Xshort *goto_map;
Xshort *from_state;
Xshort *to_state;
X
Xshort **transpose();
X
X
Xstatic int infinity;
Xstatic int maxrhs;
Xstatic int ngotos;
Xstatic unsigned *F;
Xstatic short **includes;
Xstatic shorts **lookback;
Xstatic short **R;
Xstatic short *INDEX;
Xstatic short *VERTICES;
Xstatic int top;
X
X
X
Xlalr()
X{
X  tokensetsize = WORDSIZE(ntokens);
X
X  set_state_table();
X  set_accessing_symbol();
X  set_shift_table();
X  set_reduction_table();
X  set_maxrhs();
X  initialize_LA();
X  set_goto_map();
X  initialize_F();
X  build_relations();
X  compute_FOLLOWS();
X  compute_lookaheads();
X}
X
X
X
Xset_state_table()
X{
X  register core *sp;
X
X  state_table = NEW2(nstates, core *);
X
X  for (sp = first_state; sp; sp = sp->next)
X    state_table[sp->number] = sp;
X}
X
X
X
Xset_accessing_symbol()
X{
X  register core *sp;
X
X  accessing_symbol = NEW2(nstates, short);
X
X  for (sp = first_state; sp; sp = sp->next)
X    accessing_symbol[sp->number] = sp->accessing_symbol;
X}
X
X
X
Xset_shift_table()
X{
X  register shifts *sp;
X
X  shift_table = NEW2(nstates, shifts *);
X
X  for (sp = first_shift; sp; sp = sp->next)
X    shift_table[sp->number] = sp;
X}
X
X
X
Xset_reduction_table()
X{
X  register reductions *rp;
X
X  reduction_table = NEW2(nstates, reductions *);
X
X  for (rp = first_reduction; rp; rp = rp->next)
X    reduction_table[rp->number] = rp;
X}
X
X
X
Xset_maxrhs()
X{
X  register short *itemp;
X  register int length;
X  register int max;
X
X  length = 0;
X  max = 0;
X  for (itemp = ritem; *itemp; itemp++)
X    {
X      if (*itemp > 0)
X	{
X	  length++;
X	}
X      else
X	{
X	  if (length > max) max = length;
X	  length = 0;
X	}
X    }
X
X  maxrhs = max;
X}
X
X
X
Xinitialize_LA()
X{
X  register int i;
X  register int j;
X  register int count;
X  register reductions *rp;
X  register shifts *sp;
X  register short *np;
X
X  consistent = NEW2(nstates, char);
X  lookaheads = NEW2(nstates + 1, short);
X
X  count = 0;
X  for (i = 0; i < nstates; i++)
X    {
X      register int j;
X
X      lookaheads[i] = count;
X
X      rp = reduction_table[i];
X      sp = shift_table[i];
X      if (rp && (rp->nreds > 1
X          || (sp && ! ISVAR(accessing_symbol[sp->shifts[0]]))))
X	count += rp->nreds;
X      else
X	consistent[i] = 1;
X
X      if (sp)
X	for (j = 0; j < sp->nshifts; j++)
X	  {
X	    if (accessing_symbol[sp->shifts[j]] == error_token_number)
X	      {
X		consistent[i] = 0;
X		break;
X	      }
X	  }
X    }
X
X  lookaheads[nstates] = count;
X
X  LA = NEW2(count * tokensetsize, unsigned);
X  LAruleno = NEW2(count, short);
X  lookback = NEW2(count, shorts *);
X
X  np = LAruleno;
X  for (i = 0; i < nstates; i++)
X    {
X      if (!consistent[i])
X	{
X	  if (rp = reduction_table[i])
X	    for (j = 0; j < rp->nreds; j++)
X	      *np++ = rp->rules[j];
X	}
X    }
X}
X
X
X
Xset_goto_map()
X{
X  register shifts *sp;
X  register int i;
X  register int symbol;
X  register int k;
X  register short *temp_map;
X  register int state2;
X  register int state1;
X
X  goto_map = NEW2(nvars + 1, short) - ntokens;
X  temp_map = NEW2(nvars + 1, short) - ntokens;
X
X  ngotos = 0;
X  for (sp = first_shift; sp; sp = sp->next)
X    {
X      for (i = sp->nshifts - 1; i >= 0; i--)
X	{
X	  symbol = accessing_symbol[sp->shifts[i]];
X
X	  if (ISTOKEN(symbol)) break;
X
X	  if (ngotos == MAXSHORT)
X	    toomany("gotos");
X
X	  ngotos++;
X	  goto_map[symbol]++;
X        }
X    }
X
X  k = 0;
X  for (i = ntokens; i < nsyms; i++)
X    {
X      temp_map[i] = k;
X      k += goto_map[i];
X    }
X
X  for (i = ntokens; i < nsyms; i++)
X    goto_map[i] = temp_map[i];
X
X  goto_map[nsyms] = ngotos;
X  temp_map[nsyms] = ngotos;
X
X  from_state = NEW2(ngotos, short);
X  to_state = NEW2(ngotos, short);
X
X  for (sp = first_shift; sp; sp = sp->next)
X    {
X      state1 = sp->number;
X      for (i = sp->nshifts - 1; i >= 0; i--)
X	{
X	  state2 = sp->shifts[i];
X	  symbol = accessing_symbol[state2];
X
X	  if (ISTOKEN(symbol)) break;
X
X	  k = temp_map[symbol]++;
X	  from_state[k] = state1;
X	  to_state[k] = state2;
X	}
X    }
X
X  FREE(temp_map + ntokens);
X}
X
X
X
X/*  Map_goto maps a state/symbol pair into its numeric representation.	*/
X
Xint
Xmap_goto(state, symbol)
Xint state;
Xint symbol;
X{
X  register int high;
X  register int low;
X  register int middle;
X  register int s;
X
X  low = goto_map[symbol];
X  high = goto_map[symbol + 1];
X
X  while (low <= high)
X    {
X      middle = (low + high) / 2;
X      s = from_state[middle];
X      if (s == state)
X	return (middle);
X      else if (s < state)
X	low = middle + 1;
X      else
X	high = middle - 1;
X    }
X
X  berror("map_goto");
X
X/* NOTREACHED */
X}
X
X
X
Xinitialize_F()
X{
X  register int i;
X  register int j;
X  register int k;
X  register shifts *sp;
X  register short *edge;
X  register unsigned *rowp;
X  register short *rp;
X  register short **reads;
X  register int nedges;
X  register int stateno;
X  register int symbol;
X  register int nwords;
X
X  nwords = ngotos * tokensetsize;
X  F = NEW2(nwords, unsigned);
X
X  reads = NEW2(ngotos, short *);
X  edge = NEW2(ngotos + 1, short);
X  nedges = 0;
X
X  rowp = F;
X  for (i = 0; i < ngotos; i++)
X    {
X      stateno = to_state[i];
X      sp = shift_table[stateno];
X
X      if (sp)
X	{
X	  k = sp->nshifts;
X
X	  for (j = 0; j < k; j++)
X	    {
X	      symbol = accessing_symbol[sp->shifts[j]];
X	      if (ISVAR(symbol))
X		break;
X	      SETBIT(rowp, symbol);
X	    }
X
X	  for (; j < k; j++)
X	    {
X	      symbol = accessing_symbol[sp->shifts[j]];
X	      if (nullable[symbol])
X		edge[nedges++] = map_goto(stateno, symbol);
X	    }
X	
X	  if (nedges)
X	    {
X	      reads[i] = rp = NEW2(nedges + 1, short);
X
X	      for (j = 0; j < nedges; j++)
X		rp[j] = edge[j];
X
X	      rp[nedges] = -1;
X	      nedges = 0;
X	    }
X	}
X
X      rowp += tokensetsize;
X    }
X
X  digraph(reads);
X
X  for (i = 0; i < ngotos; i++)
X    {
X      if (reads[i])
X	FREE(reads[i]);
X    }
X
X  FREE(reads);
X  FREE(edge);
X}
X
X
X
Xbuild_relations()
X{
X  register int i;
X  register int j;
X  register int k;
X  register short *rulep;
X  register short *rp;
X  register shifts *sp;
X  register int length;
X  register int nedges;
X  register int done;
X  register int state1;
X  register int stateno;
X  register int symbol1;
X  register int symbol2;
X  register short *shortp;
X  register short *edge;
X  register short *states;
X  register short **new_includes;
X
X  includes = NEW2(ngotos, short *);
X  edge = NEW2(ngotos + 1, short);
X  states = NEW2(maxrhs + 1, short);
X
X  for (i = 0; i < ngotos; i++)
X    {
X      nedges = 0;
X      state1 = from_state[i];
X      symbol1 = accessing_symbol[to_state[i]];
X
X      for (rulep = derives[symbol1]; *rulep > 0; rulep++)
X	{
X	  length = 1;
X	  states[0] = state1;
X	  stateno = state1;
X
X	  for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
X	    {
X	      symbol2 = *rp;
X	      sp = shift_table[stateno];
X	      k = sp->nshifts;
X
X	      for (j = 0; j < k; j++)
X		{
X		  stateno = sp->shifts[j];
X		  if (accessing_symbol[stateno] == symbol2) break;
X		}
X
X	      states[length++] = stateno;
X	    }
X
X	  if (!consistent[stateno])
X	    add_lookback_edge(stateno, *rulep, i);
X
X	  length--;
X	  done = 0;
X	  while (!done)
X	    {
X	      done = 1;
X	      rp--;
X			/* JF added rp>=ritem &&   I hope to god its right! */
X	      if (rp>=ritem && ISVAR(*rp))
X		{
X		  stateno = states[--length];
X		  edge[nedges++] = map_goto(stateno, *rp);
X		  if (nullable[*rp]) done = 0;
X		}
X	    }
X	}
X
X      if (nedges)
X	{
X	  includes[i] = shortp = NEW2(nedges + 1, short);
X	  for (j = 0; j < nedges; j++)
X	    shortp[j] = edge[j];
X	  shortp[nedges] = -1;
X	}
X    }
X
X  new_includes = transpose(includes, ngotos);
X
X  for (i = 0; i < ngotos; i++)
X    if (includes[i])
X      FREE(includes[i]);
X
X  FREE(includes);
X
X  includes = new_includes;
X
X  FREE(edge);
X  FREE(states);
X}
X
X
X
Xadd_lookback_edge(stateno, ruleno, gotono)
Xint stateno;
Xint ruleno;
Xint gotono;
X{
X  register int i;
X  register int k;
X  register int found;
X  register shorts *sp;
X
X  i = lookaheads[stateno];
X  k = lookaheads[stateno + 1];
X  found = 0;
X  while (!found && i < k)
X    {
X      if (LAruleno[i] == ruleno)
X	found = 1;
X      else
X	i++;
X    }
X
X  if (found == 0)
X    berror("add_lookback_edge");
X
X  sp = NEW(shorts);
X  sp->next = lookback[i];
X  sp->value = gotono;
X  lookback[i] = sp;
X}
X
X
X
Xshort **
Xtranspose(R, n)
Xshort **R;
Xint n;
X{
X  register short **new_R;
X  register short **temp_R;
X  register short *nedges;
X  register short *sp;
X  register int i;
X  register int k;
X
X  nedges = NEW2(n, short);
X
X  for (i = 0; i < n; i++)
X    {
X      sp = R[i];
X      if (sp)
X	{
X	  while (*sp >= 0)
X	    nedges[*sp++]++;
X	}
X    }
X
X  new_R = NEW2(n, short *);
X  temp_R = NEW2(n, short *);
X
X  for (i = 0; i < n; i++)
X    {
X      k = nedges[i];
X      if (k > 0)
X	{
X	  sp = NEW2(k + 1, short);
X	  new_R[i] = sp;
X	  temp_R[i] = sp;
X	  sp[k] = -1;
X	}
X    }
X
X  FREE(nedges);
X
X  for (i = 0; i < n; i++)
X    {
X      sp = R[i];
X      if (sp)
X	{
X	  while (*sp >= 0)
X	    *temp_R[*sp++]++ = i;
X	}
X    }
X
X  FREE(temp_R);
X
X  return (new_R);
X}
X
X
X
Xcompute_FOLLOWS()
X{
X  register int i;
X
X  digraph(includes);
X
X  for (i = 0; i < ngotos; i++)
X    {
X      if (includes[i]) FREE(includes[i]);
X    }
X
X  FREE(includes);
X}
X
X
X
Xcompute_lookaheads()
X{
X  register int i;
X  register int n;
X  register unsigned *fp1;
X  register unsigned *fp2;
X  register unsigned *fp3;
X  register shorts *sp;
X  register unsigned *rowp;
X/*   register short *rulep; JF unused */
X/*  register int count; JF unused */
X  register shorts *sptmp;/* JF */
X
X  rowp = LA;
X  n = lookaheads[nstates];
X  for (i = 0; i < n; i++)
X    {
X      fp3 = rowp + tokensetsize;
X      for (sp = lookback[i]; sp; sp = sp->next)
X	{
X	  fp1 = rowp;
X	  fp2 = F + tokensetsize * sp->value;
X	  while (fp1 < fp3)
X	    *fp1++ |= *fp2++;
X	}
X
X      rowp = fp3;
X    }
X
X  for (i = 0; i < n; i++)
X    {/* JF removed ref to freed storage */
X      for (sp = lookback[i]; sp; sp = sptmp) {
X	sptmp=sp->next;
X	FREE(sp);
X      }
X    }
X
X  FREE(lookback);
X  FREE(F);
X}
X
X
X
Xdigraph(relation)
Xshort **relation;
X{
X  register int i;
X
X  infinity = ngotos + 2;
X  INDEX = NEW2(ngotos + 1, short);
X  VERTICES = NEW2(ngotos + 1, short);
X  top = 0;
X
X  R = relation;
X
X  for (i = 0; i < ngotos; i++)
X    INDEX[i] = 0;
X
X  for (i = 0; i < ngotos; i++)
X    {
X      if (INDEX[i] == 0 && R[i])
X	traverse(i);
X    }
X
X  FREE(INDEX);
X  FREE(VERTICES);
X}
X
X
X
Xtraverse(i)
Xregister int i;
X{
X  register unsigned *fp1;
X  register unsigned *fp2;
X  register unsigned *fp3;
X  register int j;
X  register short *rp;
X
X  int height;
X  unsigned *base;
X
X  VERTICES[++top] = i;
X  INDEX[i] = height = top;
X
X  base = F + i * tokensetsize;
X  fp3 = base + tokensetsize;
X
X  rp = R[i];
X  if (rp)
X    {
X      while ((j = *rp++) >= 0)
X	{
X	  if (INDEX[j] == 0)
X	    traverse(j);
X
X	  if (INDEX[i] > INDEX[j])
X	    INDEX[i] = INDEX[j];
X
X	  fp1 = base;
X	  fp2 = F + j * tokensetsize;
X
X	  while (fp1 < fp3)
X	    *fp1++ |= *fp2++;
X	}
X    }
X
X  if (INDEX[i] == height)
X    {
X      for (;;)
X	{
X	  j = VERTICES[top--];
X	  INDEX[j] = infinity;
X
X	  if (i == j)
X	    break;
X
X	  fp1 = base;
X	  fp2 = F + j * tokensetsize;
X
X	  while (fp1 < fp3)
X	    *fp2++ = *fp1++;
X	}
X    }
X}
SHAR_EOF
if test 13469 -ne "`wc -c < 'lalr.c'`"
then
	echo shar: error transmitting "'lalr.c'" '(should have been 13469 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'lex.c'" '(8811 characters)'
if test -f 'lex.c'
then
	echo shar: will not over-write existing file "'lex.c'"
else
sed 's/^X//' << \SHAR_EOF > 'lex.c'
X/* Token-reader for Bison's input parser,
X   Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
X
XBISON is distributed in the hope that it will be useful, but WITHOUT ANY
XWARRANTY.  No author or distributor accepts responsibility to anyone
Xfor the consequences of using it or for whether it serves any
Xparticular purpose or works at all, unless he says so in writing.
XRefer to the BISON General Public License for full details.
X
XEveryone is granted permission to copy, modify and redistribute BISON,
Xbut only under the conditions described in the BISON General Public
XLicense.  A copy of this license is supposed to have been given to you
Xalong with BISON so you can know your rights and responsibilities.  It
Xshould be in a file named COPYING.  Among other things, the copyright
Xnotice and this notice must be preserved on all copies.
X
X In other words, you are welcome to use, share and improve this program.
X You are forbidden to forbid anyone else to use, share and improve
X what you give them.   Help stamp out software-hoarding!  */
X
X/* 
X   lex() is the entry point.  It is called from reader.c.
X   It returns one of the token-type codes defined in lex.h.
X   When an identifier is seen, the code IDENTIFIER is returned
X   and the name is looked up in the symbol table using symtab.c;
X   symval is set to a pointer to the entry found.  */
X
X#include <stdio.h>
X#include <ctype.h>
X#include "file.h"
X#include "symtab.h"
X#include "lex.h"
X
X
Xextern int lineno;
Xextern int translations;
X
X
Xchar token_buffer[MAXTOKEN + 1];
Xbucket *symval;
Xint numval;
X
Xstatic int unlexed;		/* these two describe a token to be reread */
Xstatic bucket *unlexed_symval;	/* by the next call to lex */
X
X
X
Xinit_lex()
X{
X  unlexed = -1;
X}
X
X
X
Xint
Xskip_white_space()
X{
X  register int c;
X  register int inside;
X
X  c = getc(finput);
X
X  for (;;)
X    {
X      switch (c)
X	{
X	case '/':
X	  c = getc(finput);
X	  if (c != '*')
X	    fatals("unexpected '/%c' found",c);
X
X	  c = getc(finput);
X
X	  inside = 1;
X	  while (inside)
X	    {
X	      if (c == '*')
X		{
X		  while (c == '*')
X		    c = getc(finput);
X
X		  if (c == '/')
X		    {
X		      inside = 0;
X		      c = getc(finput);
X		    }
X		}
X	      else if (c == '\n')
X		{
X		  lineno++;
X		  c = getc(finput);
X		}
X	      else if (c == EOF)
X		fatal("unterminated comment");
X	      else
X		c = getc(finput);
X	    }
X
X	  break;
X
X	case '\n':
X	  lineno++;
X
X	case ' ':
X	case '\t':
X	case '\f':
X	  c = getc(finput);
X	  break;
X
X	default:
X	  return (c);
X	}
X    }
X}
X
X
X
Xunlex(token)
Xint token;
X{
X  unlexed = token;
X  unlexed_symval = symval;
X}
X
X
X
Xint
Xlex()
X{
X  register int c;
X  register char *p;
X
X  if (unlexed >= 0)
X    {
X      symval = unlexed_symval;
X      c = unlexed;
X      unlexed = -1;
X      return (c);
X    }
X
X  c = skip_white_space();
X
X  switch (c)
X    {
X    case EOF:
X      return (ENDFILE);
X
X    case 'A':  case 'B':  case 'C':  case 'D':  case 'E':
X    case 'F':  case 'G':  case 'H':  case 'I':  case 'J':
X    case 'K':  case 'L':  case 'M':  case 'N':  case 'O':
X    case 'P':  case 'Q':  case 'R':  case 'S':  case 'T':
X    case 'U':  case 'V':  case 'W':  case 'X':  case 'Y':
X    case 'Z':
X    case 'a':  case 'b':  case 'c':  case 'd':  case 'e':
X    case 'f':  case 'g':  case 'h':  case 'i':  case 'j':
X    case 'k':  case 'l':  case 'm':  case 'n':  case 'o':
X    case 'p':  case 'q':  case 'r':  case 's':  case 't':
X    case 'u':  case 'v':  case 'w':  case 'x':  case 'y':
X    case 'z':
X    case '.':  case '_':
X      p = token_buffer;
X      while (isalnum(c) || c == '_' || c == '.')
X	{
X	  if (p < token_buffer + MAXTOKEN)
X	    *p++ = c;
X	  c = getc(finput);
X	}
X
X      *p = 0;
X      ungetc(c, finput);
X      symval = getsym(token_buffer);
X      return (IDENTIFIER);
X
X    case '0':  case '1':  case '2':  case '3':  case '4':
X    case '5':  case '6':  case '7':  case '8':  case '9':
X      {
X	numval = 0;
X
X	while (isdigit(c))
X	  {
X	    numval = numval*10 + c - '0';
X	    c = getc(finput);
X	  }
X	ungetc(c, finput);
X	return (NUMBER);
X      }
X
X    case '\'':
X      translations = -1;
X
X      /* parse the literal token and compute character code in  code  */
X
X      c = getc(finput);
X      {
X	register int code = 0;
X
X	if (c == '\\')
X	  {
X	    c = getc(finput);
X
X	    if (c <= '7' && c >= '0')
X	      {
X		while (c <= '7' && c >= '0')
X		  {
X		    code = (code * 8) + (c - '0');
X		    c = getc(finput);
X		  }
X		if (code >= 128 || code<0)/* JF this said if(c>=128) */
X		  fatals("malformatted literal token '\\%03o'",code);
X	      }
X	    else
X	      {
X		if (c == 't')
X		  code = '\t';
X		else if (c == 'n')
X		  code = '\n';
X		else if (c == 'r')
X		  code = '\r';
X		else if (c == 'f')
X		  code = '\f';
X		else if (c == 'b')
X		  code = '\b';
X		else if (c == '\\')
X		  code = '\\';
X		else if (c == '\'')
X		  code = '\'';
X		else if (c == '\"')	/* JF this is a good idea */
X		  code = '\"';
X		else fatals("invalid literal token '\\%c'",c);
X		c = getc(finput);
X	      }
X	  }
X	else
X	  {
X	    code = c;
X	    c = getc(finput);
X	  }
X	if (c != '\'')
X	  fatal("multicharacter literal tokens NOT supported");
X
X	/* now fill token_buffer with the canonical name for this character
X	   as a literal token.  Do not use what the user typed,
X	   so that '\012' and '\n' can be interchangeable.  */
X
X	p = token_buffer;
X	*p++ = '\'';
X	if (code == '\\')
X	  {
X	    p = token_buffer + 1;
X	    *p++ = '\\';
X	    *p++ = '\\';
X	  }
X	else if (code == '\'')
X	  {
X	    p = token_buffer + 1;
X	    *p++ = '\\';
X	    *p++ = '\'';
X	  }
X	else if (code >= 040 && code != 0177)
X	  *p++ = code;
X	else if (code == '\t')
X	  {
X	    p = token_buffer + 1;
X	    *p++ = '\\';
X	    *p++ = 't';
X	  }
X	else if (code == '\n')
X	  {
X	    p = token_buffer + 1;
X	    *p++ = '\\';
X	    *p++ = 'n';
X	  }
X	else if (code == '\r')
X	  {
X	    p = token_buffer + 1;
X	    *p++ = '\\';
X	    *p++ = 'r';
X	  }
X	else if (code == '\b')
X	  {
X	    p = token_buffer + 1;
X	    *p++ = '\\';
X	    *p++ = 'b';
X	  }
X	else if (code == '\f')
X	  {
X	    p = token_buffer + 1;
X	    *p++ = '\\';
X	    *p++ = 'f';
X	  }
X        else
X	  {
X	    *p++ = code / 0100 + '0';
X	    *p++ = ((code / 010) & 07) + '0';
X	    *p++ = (code & 07) + '0';
X	  }
X	*p++ = '\'';
X	*p = 0;
X	symval = getsym(token_buffer);
X	symval->class = STOKEN;
X	if (! symval->user_token_number)
X	  symval->user_token_number = code;
X	return (IDENTIFIER);
X      }
X
X    case ',':
X      return (COMMA);
X
X    case ':':
X      return (COLON);
X
X    case ';':
X      return (SEMICOLON);
X
X    case '|':
X      return (BAR);
X
X    case '{':
X      return (LEFT_CURLY);
X
X    case '=':
X      do c = getc(finput);
X      while(c==' ' || c=='\n' || c=='\t');
X      if (c == '{')
X      	return(LEFT_CURLY);
X      else
X	{
X	  ungetc(c, finput);
X	  return(ILLEGAL);
X	}
X
X    case '<':
X      p = token_buffer;
X      c = getc(finput);
X      while (c != '>')
X	{
X	  if (c == '\n' || c == EOF)
X	    fatal("unterminated type name");
X
X	  if (p >= token_buffer + MAXTOKEN - 1)
X	    fatals("type name too long (%d max)",MAXTOKEN-1);
X
X	  *p++ = c;
X	  c = getc(finput);
X	}
X      *p = 0;
X      return (TYPENAME);
X	    
X
X    case '%':
X      return (parse_percent_token());
X
X    default:
X      return (ILLEGAL);
X    }
X}
X
X
X/* parse a token which starts with %.  Assumes the % has already been read and discarded.  */
X
Xint
Xparse_percent_token ()
X{
X  register int c;
X  register char *p;
X
X  p = token_buffer;
X  c = getc(finput);
X
X  switch (c)
X    {
X    case '%':
X      return (TWO_PERCENTS);
X
X    case '{':
X      return (PERCENT_LEFT_CURLY);
X
X    case '<':
X      return (LEFT);
X
X    case '>':
X      return (RIGHT);
X
X    case '2':
X      return (NONASSOC);
X
X    case '0':
X      return (TOKEN);
X
X    case '=':
X      return (PREC);
X    }
X  if (!isalpha(c))
X    return (ILLEGAL);
X
X  while (isalpha(c) || c == '_')
X    {
X      if (p < token_buffer + MAXTOKEN)
X	*p++ = c;
X      c = getc(finput);
X    }
X
X  ungetc(c, finput);
X
X  *p = 0;
X
X  if (strcmp(token_buffer, "token") == 0
X      ||
X      strcmp(token_buffer, "term") == 0)
X    return (TOKEN);
X  else if (strcmp(token_buffer, "nterm") == 0)
X    return (NTERM);
X  else if (strcmp(token_buffer, "type") == 0)
X    return (TYPE);
X  else if (strcmp(token_buffer, "guard") == 0)
X    return (GUARD);
X  else if (strcmp(token_buffer, "union") == 0)
X    return (UNION);
X  else if (strcmp(token_buffer, "expect") == 0)
X    return (EXPECT);
X  else if (strcmp(token_buffer, "start") == 0)
X    return (START);
X  else if (strcmp(token_buffer, "left") == 0)
X    return (LEFT);
X  else if (strcmp(token_buffer, "right") == 0)
X    return (RIGHT);
X  else if (strcmp(token_buffer, "nonassoc") == 0
X	   ||
X	   strcmp(token_buffer, "binary") == 0)
X    return (NONASSOC);
X  else if (strcmp(token_buffer, "semantic_parser") == 0)
X    return (SEMANTIC_PARSER);
X  else if (strcmp(token_buffer, "pure_parser") == 0)
X    return (PURE_PARSER);
X  else if (strcmp(token_buffer, "prec") == 0)
X    return (PREC);
X  else return (ILLEGAL);
X}
SHAR_EOF
if test 8811 -ne "`wc -c < 'lex.c'`"
then
	echo shar: error transmitting "'lex.c'" '(should have been 8811 characters)'
fi
fi # end of overwriting check
echo shar: extracting "'lro.c'" '(13509 characters)'
if test -f 'lro.c'
then
	echo shar: will not over-write existing file "'lro.c'"
else
sed 's/^X//' << \SHAR_EOF > 'lro.c'
X/* Generate the nondeterministic finite state machine for bison,
X   Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
X
XBISON is distributed in the hope that it will be useful, but WITHOUT ANY
XWARRANTY.  No author or distributor accepts responsibility to anyone
Xfor the consequences of using it or for whether it serves any
Xparticular purpose or works at all, unless he says so in writing.
XRefer to the BISON General Public License for full details.
X
XEveryone is granted permission to copy, modify and redistribute BISON,
Xbut only under the conditions described in the BISON General Public
XLicense.  A copy of this license is supposed to have been given to you
Xalong with BISON so you can know your rights and responsibilities.  It
Xshould be in a file named COPYING.  Among other things, the copyright
Xnotice and this notice must be preserved on all copies.
X
X In other words, you are welcome to use, share and improve this program.
X You are forbidden to forbid anyone else to use, share and improve
X what you give them.   Help stamp out software-hoarding!  */
X
X/* See comments in state.h for the data structures that represent it.
X   The entry point is generate_states.  */
X
X#include <stdio.h>
X#include "machine.h"
X#include "new.h"
X#include "gram.h"
X#include "state.h"
X
X
Xextern char *nullable;
Xextern short *itemset;
Xextern short *itemsetend;
X
X
Xint nstates;
Xint final_state;
Xcore *first_state;
Xshifts *first_shift;
Xreductions *first_reduction;
X
Xint get_state();
Xcore *new_state();
X
Xstatic core *this_state;
Xstatic core *last_state;
Xstatic shifts *last_shift;
Xstatic reductions *last_reduction;
X
Xstatic int nshifts;
Xstatic short *shift_symbol;
X
Xstatic short *redset;
Xstatic short *shiftset;
X
Xstatic short **kernel_base;
Xstatic short **kernel_end;
Xstatic short *kernel_items;
X
X/* hash table for states, to recognize equivalent ones.  */
X
X#define	STATE_TABLE_SIZE	1009
Xstatic core **state_table;
X
X
X
Xallocate_itemsets()
X{
X  register short *itemp;
X  register int symbol;
X  register int i;
X  register count;
X  register int max;
X  register short *symbol_count;
X
X  count = 0;
X  symbol_count = NEW2(nsyms, short);
X
X  itemp = ritem;
X  symbol = *itemp++;
X  while (symbol)
X    {
X      if (symbol > 0)
X	{
X	  count++;
X	  symbol_count[symbol]++;
X	}
X      symbol = *itemp++;
X    }
X
X  /* see comments before new-itemset.  All the vectors of items
X     live inside kernel_items.  The number of active items after
X     some symbol cannot be more than the number of times that symbol
X     appears as an item, which is symbol_count[symbol].
X     We allocate that much space for each symbol.  */
X
X  kernel_base = NEW2(nsyms, short *);
X  kernel_items = NEW2(count, short);
X
X  count = 0;
X  max = 0;
X  for (i = 0; i < nsyms; i++)
X    {
X      kernel_base[i] = kernel_items + count;
X      count += symbol_count[i];
X      if (max < symbol_count[i])
X	max = symbol_count[i];
X    }
X
X  shift_symbol = symbol_count;
X  kernel_end = NEW2(nsyms, short *);
X}
X
X
X
Xallocate_storage()
X{
X  allocate_itemsets();
X
X  shiftset = NEW2(nsyms, short);
X  redset = NEW2(nrules + 1, short);
X  state_table = NEW2(STATE_TABLE_SIZE, core *);
X}
X
X
X
Xfree_storage()
X{
X  FREE(shift_symbol);
X  FREE(redset);
X  FREE(shiftset);
X  FREE(kernel_base);
X  FREE(kernel_end);
X  FREE(kernel_items);
X  FREE(state_table);
X}
X
X
X
X/* compute the nondeterministic finite state machine (see state.h for details)
Xfrom the grammar.  */
X
Xgenerate_states()
X{
X  allocate_storage();
X  initialize_closure(nitems);
X  initialize_states();
X
X  while (this_state)
X    {
X      /* Set up ruleset and itemset for the transitions out of this state.
X         ruleset gets a 1 bit for each rule that could reduce now.
X	 itemset gets a vector of all the items that could be accepted next.  */
X      closure(this_state->items, this_state->nitems);
X      /* record the reductions allowed out of this state */
X      save_reductions();
X      /* find the itemsets of the states that shifts can reach */
X      new_itemsets();
X      /* find or create the core structures for those states */
X      append_states();
X
X      /* create the shifts structures for the shifts to those states,
X         now that the state numbers transitioning to are known */
X      if (nshifts > 0)
X        save_shifts();
X
X      /* states are queued when they are created; process them all */
X      this_state = this_state->next;
X    }
X
X  /* discard various storage */
X  finalize_closure();
X  free_storage();
X
X  /* set up initial and final states as parser wants them */
X  augment_automaton();
X}
X
X
X
X/* Find which symbols can be shifted in the current state,
X   and for each one record which items would be active after that shift.
X   Uses the contents of itemset.
X   shift_symbol is set to a vector of the symbols that can be shifted.
X   For each symbol in the grammer, kernel_base[symbol] points to
X   a vector of item numbers activated if that symbol is shifted,
X   and kernel_end[symbol] points after the end of that vector.  */
X
Xnew_itemsets()
X{
X  register int i;
X  register int shiftcount;
X  register short *isp;
X  register short *ksp;
X  register int symbol;
X
X#ifdef	TRACE
X  fprintf(stderr, "Entering new_itemsets\n");
X#endif
X
X  for (i = 0; i < nsyms; i++)
X    kernel_end[i] = NULL;
X
X  shiftcount = 0;
X
X  isp = itemset;
X
X  while (isp < itemsetend)
X    {
X      i = *isp++;
X      symbol = ritem[i];
X      if (symbol > 0)
X	{
X          ksp = kernel_end[symbol];
X
X          if (!ksp)
X	    {
X	      shift_symbol[shiftcount++] = symbol;
X	      ksp = kernel_base[symbol];
X	    }
X
X          *ksp++ = i + 1;
X          kernel_end[symbol] = ksp;
X	}
X    }
X
X  nshifts = shiftcount;
X}
X
X
X
X/* Use the information computed by new_itemset to find the state numbers
X   reached by each shift transition from the current state.
X
X   shiftset is set up as a vector of state numbers of those states.  */
X
Xappend_states()
X{
X  register int i;
X  register int j;
X  register int symbol;
X
X#ifdef	TRACE
X  fprintf(stderr, "Entering append_states\n");
X#endif
X
X  /* first sort shift_symbol into increasing order */
X
X  for (i = 1; i < nshifts; i++)
X    {
X      symbol = shift_symbol[i];
X      j = i;
X      while (j > 0 && shift_symbol[j - 1] > symbol)
X	{
X	  shift_symbol[j] = shift_symbol[j - 1];
X	  j--;
X	}
X      shift_symbol[j] = symbol;
X    }
X
X  for (i = 0; i < nshifts; i++)
X    {
X      symbol = shift_symbol[i];
X      shiftset[i] = get_state(symbol);
X    }
X}
X
X
X
X/* find the state number for the state we would get to
X(from the current state) by shifting symbol.
XCreate a new state if no equivalent one exists already.
XUsed by append_states  */
X
Xint
Xget_state(symbol)
Xint symbol;
X{
X  register int key;
X  register short *isp1;
X  register short *isp2;
X  register short *iend;
X  register core *sp;
X  register int found;
X
X  int n;
X
X#ifdef	TRACE
X  fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
X#endif
X
X  isp1 = kernel_base[symbol];
X  iend = kernel_end[symbol];
X  n = iend - isp1;
X
X  /* add up the target state's active item numbers to get a hash key */
X  key = 0;
X  while (isp1 < iend)
X    key += *isp1++;
X
X  key = key % STATE_TABLE_SIZE;
X
X  sp = state_table[key];
X
X  if (sp)
X    {
X      found = 0;
X      while (!found)
X	{
X	  if (sp->nitems == n)
X	    {
X	      found = 1;
X	      isp1 = kernel_base[symbol];
X	      isp2 = sp->items;
X
X	      while (found && isp1 < iend)
X		{
X		  if (*isp1++ != *isp2++)
X		    found = 0;
X		}
X	    }
X
X	  if (!found)
X	    {
X	      if (sp->link)
X		{
X		  sp = sp->link;
X		}
X	      else   /* bucket exhausted and no match */
X		{
X		  sp = sp->link = new_state(symbol);
X		  found = 1;
X		}
X	    }
X	}
X    }
X  else      /* bucket is empty */
X    {
X      state_table[key] = sp = new_state(symbol);
X    }
X
X  return (sp->number);
X}
X
X
X
X/* subroutine of get_state.  create a new state for those items, if necessary.  */
X
Xcore *
Xnew_state(symbol)
Xint symbol;
X{
X  register int n;
X  register core *p;
X  register short *isp1;
X  register short *isp2;
X  register short *iend;
X
X#ifdef	TRACE
X  fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
X#endif
X
X  if (nstates >= MAXSHORT)
X    toomany("states");
X
X  isp1 = kernel_base[symbol];
X  iend = kernel_end[symbol];
X  n = iend - isp1;
X
X  p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
X  p->accessing_symbol = symbol;
X  p->number = nstates;
X  p->nitems = n;
X
X  isp2 = p->items;
X  while (isp1 < iend)
X    *isp2++ = *isp1++;
X
X  last_state->next = p;
X  last_state = p;
X
X  nstates++;
X
X  return (p);
X}
X
X
X
Xinitialize_states()
X{
X  register core *p;
X/*  register unsigned *rp1; JF unused */
X/*  register unsigned *rp2; JF unused */
X/*  register unsigned *rend; JF unused */
X
X  p = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
X  first_state = last_state = this_state = p;
X  nstates = 1;
X}
X
X
X
Xsave_shifts()
X{
X  register shifts *p;
X  register short *sp1;
X  register short *sp2;
X  register short *send;
X
X  p = (shifts *) allocate((unsigned) (sizeof(shifts) +
X			(nshifts - 1) * sizeof(short)));
X
X  p->number = this_state->number;
X  p->nshifts = nshifts;
X
X  sp1 = shiftset;
X  sp2 = p->shifts;
X  send = shiftset + nshifts;
X
X  while (sp1 < send)
X    *sp2++ = *sp1++;
X
X  if (last_shift)
X    {
X      last_shift->next = p;
X      last_shift = p;
X    }
X  else
X    {
X      first_shift = p;
X      last_shift = p;
X    }
X}
X
X
X
X/* find which rules can be used for reduction transitions from the current state
X   and make a reductions structure for the state to record their rule numbers.  */
X
Xsave_reductions()
X{
X  register short *isp;
X  register short *rp1;
X  register short *rp2;
X  register int item;
X  register int count;
X  register reductions *p;
X
X  short *rend;
X
X  /* find and count the active items that represent ends of rules */
X
X  count = 0;
X  for (isp = itemset; isp < itemsetend; isp++)
X    {
X      item = ritem[*isp];
X      if (item < 0)
X	{
X	  redset[count++] = -item;
X	}
X    }
X
X  /* make a reductions structure and copy the data into it.  */
X
X  if (count)
X    {
X      p = (reductions *) allocate((unsigned) (sizeof(reductions) +
X					(count - 1) * sizeof(short)));
X
X      p->number = this_state->number;
X      p->nreds = count;
X
X      rp1 = redset;
X      rp2 = p->rules;
X      rend = rp1 + count;
X
X      while (rp1 < rend)
X	*rp2++ = *rp1++;
X
X      if (last_reduction)
X	{
X	  last_reduction->next = p;
X	  last_reduction = p;
X	}
X      else
X	{
X	  first_reduction = p;
X	  last_reduction = p;
X	}
X    }
X}
X
X
X
X/* Make sure that the initial state has a shift that accepts the
Xgrammar's start symbol and goes to the next-to-final state,
Xwhich has a shift going to the final state, which has a shift
Xto the termination state.
XCreate such states and shifts if they don't happen to exist already.  */
X
Xaugment_automaton()
X{
X  register int i;
X  register int k;
X/*  register int found; JF unused */
X  register core *statep;
X  register shifts *sp;
X  register shifts *sp2;
X  register shifts *sp1;
X
X  sp = first_shift;
X
X  if (sp)
X    {
X      if (sp->number == 0)
X	{
X	  k = sp->nshifts;
X	  statep = first_state->next;
X
X	  while (statep->accessing_symbol < start_symbol
X		  && statep->number < k)
X	    statep = statep->next;
X
X	  if (statep->accessing_symbol == start_symbol)
X	    {
X	      k = statep->number;
X
X	      while (sp->number < k)
X		{
X		  sp1 = sp;
X		  sp = sp->next;
X		}
X
X	      if (sp->number == k)
X		{
X		  sp2 = (shifts *) allocate((unsigned) (sizeof(shifts)
X					+ sp->nshifts * sizeof(short)));
X		  sp2->next = sp->next;
X		  sp2->number = k;
X		  sp2->nshifts = sp->nshifts + 1;
X		  sp2->shifts[0] = nstates;
X		  for (i = sp->nshifts; i > 0; i--)
X		    sp2->shifts[i] = sp->shifts[i - 1];
X
X		  sp1->next = sp2;
X		  FREE(sp);
X		}
X	      else
X		{
X		  sp2 = NEW(shifts);
X		  sp2->next = sp;
X		  sp2->number = k;
X		  sp2->nshifts = 1;
X		  sp2->shifts[0] = nstates;
X
X		  sp1->next = sp2;
X		  if (!sp)
X		    last_shift = sp2;
X		}
X	    }
X	  else
X	    {
X	      k = statep->number;
X	      sp = first_shift;
X
X	      sp2 = (shifts *) allocate((unsigned) (sizeof(shifts)
X					+ sp->nshifts * sizeof(short)));
X	      sp2->next = sp->next;
X	      sp2->nshifts = sp->nshifts + 1;
X
X	      for (i = 0; i < k; i++)
X		sp2->shifts[i] = sp->shifts[i];
X
X	      sp2->shifts[k] = nstates;
X
X	      for (i = k; i < sp->nshifts; i++)
X		sp2->shifts[i + 1] = sp->shifts[i];
X
X	      first_shift = sp2;
X	      if (last_shift == sp)
X		last_shift = sp2;
X
X	      FREE(sp);
X
X	      insert_start_shift();
X	    }
X	}
X      else
X	{
X	  sp = NEW(shifts);
X	  sp->next = first_shift;
X	  sp->nshifts = 1;
X	  sp->shifts[0] = nstates;
X
X	  first_shift = sp;
X
X	  insert_start_shift();
X	}
X    }
X  else
X    {
X      sp = NEW(shifts);
X      sp->nshifts = 1;
X      sp->shifts[0] = nstates;
X
X      first_shift = sp;
X      last_shift = sp;
X
X      insert_start_shift();
X    }
X
X  statep = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
X  statep->number = nstates;
X  last_state->next = statep;
X  last_state = statep;
X
X  sp = NEW(shifts);
X  sp->number = nstates++;
X  sp->nshifts = 1;
X  sp->shifts[0] = nstates;
X  last_shift->next = sp;
X  last_shift = sp;
X
X  final_state = nstates;
X
X  statep = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
X  statep->number = nstates++;
X  last_state->next = statep;
X  last_state = statep;
X}
X
X
X/* subroutine of augment_automaton */
X
Xinsert_start_shift()
X{
X  register core *statep;
X  register shifts *sp;
X
X  statep = (core *) allocate((unsigned) (sizeof(core) - sizeof(short)));
X  statep->number = nstates;
X  statep->accessing_symbol = start_symbol;
X
X  last_state->next = statep;
X  last_state = statep;
X
X  sp = NEW(shifts);
X  sp->number = nstates++;
X  sp->nshifts = 1;
X  sp->shifts[0] = nstates;
X
X  last_shift->next = sp;
X  last_shift = sp;
X}
SHAR_EOF
if test 13509 -ne "`wc -c < 'lro.c'`"
then
	echo shar: error transmitting "'lro.c'" '(should have been 13509 characters)'
fi
fi # end of overwriting check
#	End of shell archive
exit 0
--- end of part 3 ---