aboutsummaryrefslogtreecommitdiff
path: root/tools/bison++/lalr.cc
diff options
context:
space:
mode:
authormarha <marha@users.sourceforge.net>2010-11-19 13:18:48 +0000
committermarha <marha@users.sourceforge.net>2010-11-19 13:18:48 +0000
commit12f606ce06ef926f366a03079c5e3107c23f18af (patch)
tree28d7be4328bca9c31c1ab0f7cb5924c196be23a0 /tools/bison++/lalr.cc
parent773752eab55047c33bad0d88006bb69f5c601502 (diff)
downloadvcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.tar.gz
vcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.tar.bz2
vcxsrv-12f606ce06ef926f366a03079c5e3107c23f18af.zip
Added tool bison++-1.21.11
Diffstat (limited to 'tools/bison++/lalr.cc')
-rw-r--r--tools/bison++/lalr.cc761
1 files changed, 761 insertions, 0 deletions
diff --git a/tools/bison++/lalr.cc b/tools/bison++/lalr.cc
new file mode 100644
index 000000000..f79f16d98
--- /dev/null
+++ b/tools/bison++/lalr.cc
@@ -0,0 +1,761 @@
+/* Compute look-ahead criteria for bison,
+ Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.
+
+This file is part of Bison, the GNU Compiler Compiler.
+
+Bison is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+Bison is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with Bison; see the file COPYING. If not, write to
+the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+
+
+/* Compute how to make the finite state machine deterministic;
+ find which rules need lookahead in each state, and which lookahead tokens they accept.
+
+lalr(), the entry point, builds these data structures:
+
+goto_map, from_state and to_state
+ record each shift transition which accepts a variable (a nonterminal).
+ngotos is the number of such transitions.
+from_state[t] is the state number which a transition leads from
+and to_state[t] is the state number it leads to.
+All the transitions that accept a particular variable are grouped together and
+goto_map[i - ntokens] is the index in from_state and to_state of the first of them.
+
+consistent[s] is nonzero if no lookahead is needed to decide what to do in state s.
+
+LAruleno is a vector which records the rules that need lookahead in various states.
+The elements of LAruleno that apply to state s are those from
+ lookaheads[s] through lookaheads[s+1]-1.
+Each element of LAruleno is a rule number.
+
+If lr is the length of LAruleno, then a number from 0 to lr-1
+can specify both a rule and a state where the rule might be applied.
+
+LA is a lr by ntokens matrix of bits.
+LA[l, i] is 1 if the rule LAruleno[l] is applicable in the appropriate state
+ when the next token is symbol i.
+If LA[l, i] and LA[l, j] are both 1 for i != j, it is a conflict.
+*/
+
+#include <stdio.h>
+#include "system.h"
+#include "machine.h"
+#include "types.h"
+#include "state.h"
+#include "new.h"
+#include "gram.h"
+
+
+extern short **derives;
+extern char *nullable;
+
+
+int tokensetsize;
+short *lookaheads;
+short *LAruleno;
+unsigned *LA;
+short *accessing_symbol;
+char *consistent;
+core **state_table;
+shifts **shift_table;
+reductions **reduction_table;
+short *goto_map;
+short *from_state;
+short *to_state;
+
+short **transpose(short**,int);
+void set_state_table();
+void set_accessing_symbol();
+void set_shift_table();
+void set_reduction_table();
+void set_maxrhs();
+void initialize_LA();
+void set_goto_map();
+void initialize_F();
+void build_relations();
+void add_lookback_edge(int,int,int);
+void compute_FOLLOWS();
+void compute_lookaheads();
+void digraph(short**);
+void traverse(int);
+
+extern void toomany(char*);
+extern void berror(char*);
+
+static int infinity;
+static int maxrhs;
+static int ngotos;
+static unsigned *F;
+static short **includes;
+static shorts **lookback;
+static short **R;
+static short *INDEX;
+static short *VERTICES;
+static int top;
+
+
+void
+lalr()
+{
+ tokensetsize = WORDSIZE(ntokens);
+
+ set_state_table();
+ set_accessing_symbol();
+ set_shift_table();
+ set_reduction_table();
+ set_maxrhs();
+ initialize_LA();
+ set_goto_map();
+ initialize_F();
+ build_relations();
+ compute_FOLLOWS();
+ compute_lookaheads();
+}
+
+
+void
+set_state_table()
+{
+ register core *sp;
+
+ state_table = NEW2(nstates, core *);
+
+ for (sp = first_state; sp; sp = sp->next)
+ state_table[sp->number] = sp;
+}
+
+
+void
+set_accessing_symbol()
+{
+ register core *sp;
+
+ accessing_symbol = NEW2(nstates, short);
+
+ for (sp = first_state; sp; sp = sp->next)
+ accessing_symbol[sp->number] = sp->accessing_symbol;
+}
+
+
+void
+set_shift_table()
+{
+ register shifts *sp;
+
+ shift_table = NEW2(nstates, shifts *);
+
+ for (sp = first_shift; sp; sp = sp->next)
+ shift_table[sp->number] = sp;
+}
+
+
+void
+set_reduction_table()
+{
+ register reductions *rp;
+
+ reduction_table = NEW2(nstates, reductions *);
+
+ for (rp = first_reduction; rp; rp = rp->next)
+ reduction_table[rp->number] = rp;
+}
+
+
+void
+set_maxrhs()
+{
+ register short *itemp;
+ register int length;
+ register int max;
+
+ length = 0;
+ max = 0;
+ for (itemp = ritem; *itemp; itemp++)
+ {
+ if (*itemp > 0)
+ {
+ length++;
+ }
+ else
+ {
+ if (length > max) max = length;
+ length = 0;
+ }
+ }
+
+ maxrhs = max;
+}
+
+
+void
+initialize_LA()
+{
+ register int i;
+ register int j;
+ register int count;
+ register reductions *rp;
+ register shifts *sp;
+ register short *np;
+
+ consistent = NEW2(nstates, char);
+ lookaheads = NEW2(nstates + 1, short);
+
+ count = 0;
+ for (i = 0; i < nstates; i++)
+ {
+ register int k;
+
+ lookaheads[i] = count;
+
+ rp = reduction_table[i];
+ sp = shift_table[i];
+ if (rp && (rp->nreds > 1
+ || (sp && ! ISVAR(accessing_symbol[sp->internalShifts[0]]))))
+ count += rp->nreds;
+ else
+ consistent[i] = 1;
+
+ if (sp)
+ for (k = 0; k < sp->nshifts; k++)
+ {
+ if (accessing_symbol[sp->internalShifts[k]] == error_token_number)
+ {
+ consistent[i] = 0;
+ break;
+ }
+ }
+ }
+
+ lookaheads[nstates] = count;
+
+ if (count == 0)
+ {
+ LA = NEW2(1 * tokensetsize, unsigned);
+ LAruleno = NEW2(1, short);
+ lookback = NEW2(1, shorts *);
+ }
+ else
+ {
+ LA = NEW2(count * tokensetsize, unsigned);
+ LAruleno = NEW2(count, short);
+ lookback = NEW2(count, shorts *);
+ }
+
+ np = LAruleno;
+ for (i = 0; i < nstates; i++)
+ {
+ if (!consistent[i])
+ {
+ if (rp = reduction_table[i])
+ for (j = 0; j < rp->nreds; j++)
+ *np++ = rp->rules[j];
+ }
+ }
+}
+
+
+void
+set_goto_map()
+{
+ register shifts *sp;
+ register int i;
+ register int symbol;
+ register int k;
+ register short *temp_map;
+ register int state2;
+ register int state1;
+
+ goto_map = NEW2(nvars + 1, short) - ntokens;
+ temp_map = NEW2(nvars + 1, short) - ntokens;
+
+ ngotos = 0;
+ for (sp = first_shift; sp; sp = sp->next)
+ {
+ for (i = sp->nshifts - 1; i >= 0; i--)
+ {
+ symbol = accessing_symbol[sp->internalShifts[i]];
+
+ if (ISTOKEN(symbol)) break;
+
+ if (ngotos == MAXSHORT)
+ toomany("gotos");
+
+ ngotos++;
+ goto_map[symbol]++;
+ }
+ }
+
+ k = 0;
+ for (i = ntokens; i < nsyms; i++)
+ {
+ temp_map[i] = k;
+ k += goto_map[i];
+ }
+
+ for (i = ntokens; i < nsyms; i++)
+ goto_map[i] = temp_map[i];
+
+ goto_map[nsyms] = ngotos;
+ temp_map[nsyms] = ngotos;
+
+ from_state = NEW2(ngotos, short);
+ to_state = NEW2(ngotos, short);
+
+ for (sp = first_shift; sp; sp = sp->next)
+ {
+ state1 = sp->number;
+ for (i = sp->nshifts - 1; i >= 0; i--)
+ {
+ state2 = sp->internalShifts[i];
+ symbol = accessing_symbol[state2];
+
+ if (ISTOKEN(symbol)) break;
+
+ k = temp_map[symbol]++;
+ from_state[k] = state1;
+ to_state[k] = state2;
+ }
+ }
+
+ FREE(temp_map + ntokens);
+}
+
+
+
+/* Map_goto maps a state/symbol pair into its numeric representation. */
+
+int
+map_goto(int state, int symbol)
+{
+ register int high;
+ register int low;
+ register int middle;
+ register int s;
+
+ low = goto_map[symbol];
+ high = goto_map[symbol + 1] - 1;
+
+ while (low <= high)
+ {
+ middle = (low + high) / 2;
+ s = from_state[middle];
+ if (s == state)
+ return (middle);
+ else if (s < state)
+ low = middle + 1;
+ else
+ high = middle - 1;
+ }
+
+ berror("map_goto");
+/* NOTREACHED */
+ return 0;
+}
+
+
+void
+initialize_F()
+{
+ register int i;
+ register int j;
+ register int k;
+ register shifts *sp;
+ register short *edge;
+ register unsigned *rowp;
+ register short *rp;
+ register short **reads;
+ register int nedges;
+ register int stateno;
+ register int symbol;
+ register int nwords;
+
+ nwords = ngotos * tokensetsize;
+ F = NEW2(nwords, unsigned);
+
+ reads = NEW2(ngotos, short *);
+ edge = NEW2(ngotos + 1, short);
+ nedges = 0;
+
+ rowp = F;
+ for (i = 0; i < ngotos; i++)
+ {
+ stateno = to_state[i];
+ sp = shift_table[stateno];
+
+ if (sp)
+ {
+ k = sp->nshifts;
+
+ for (j = 0; j < k; j++)
+ {
+ symbol = accessing_symbol[sp->internalShifts[j]];
+ if (ISVAR(symbol))
+ break;
+ SETBIT(rowp, symbol);
+ }
+
+ for (; j < k; j++)
+ {
+ symbol = accessing_symbol[sp->internalShifts[j]];
+ if (nullable[symbol])
+ edge[nedges++] = map_goto(stateno, symbol);
+ }
+
+ if (nedges)
+ {
+ reads[i] = rp = NEW2(nedges + 1, short);
+
+ for (j = 0; j < nedges; j++)
+ rp[j] = edge[j];
+
+ rp[nedges] = -1;
+ nedges = 0;
+ }
+ }
+
+ rowp += tokensetsize;
+ }
+
+ digraph(reads);
+
+ for (i = 0; i < ngotos; i++)
+ {
+ if (reads[i])
+ FREE(reads[i]);
+ }
+
+ FREE(reads);
+ FREE(edge);
+}
+
+
+void
+build_relations()
+{
+ register int i;
+ register int j;
+ register int k;
+ register short *rulep;
+ register short *rp;
+ register shifts *sp;
+ register int length;
+ register int nedges;
+ register int done;
+ register int state1;
+ register int stateno;
+ register int symbol1;
+ register int symbol2;
+ register short *shortp;
+ register short *edge;
+ register short *states;
+ register short **new_includes;
+
+ includes = NEW2(ngotos, short *);
+ edge = NEW2(ngotos + 1, short);
+ states = NEW2(maxrhs + 1, short);
+
+ for (i = 0; i < ngotos; i++)
+ {
+ nedges = 0;
+ state1 = from_state[i];
+ symbol1 = accessing_symbol[to_state[i]];
+
+ for (rulep = derives[symbol1]; *rulep > 0; rulep++)
+ {
+ length = 1;
+ states[0] = state1;
+ stateno = state1;
+
+ for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
+ {
+ symbol2 = *rp;
+ sp = shift_table[stateno];
+ k = sp->nshifts;
+
+ for (j = 0; j < k; j++)
+ {
+ stateno = sp->internalShifts[j];
+ if (accessing_symbol[stateno] == symbol2) break;
+ }
+
+ states[length++] = stateno;
+ }
+
+ if (!consistent[stateno])
+ add_lookback_edge(stateno, *rulep, i);
+
+ length--;
+ done = 0;
+ while (!done)
+ {
+ done = 1;
+ rp--;
+ /* JF added rp>=ritem && I hope to god its right! */
+ if (rp>=ritem && ISVAR(*rp))
+ {
+ stateno = states[--length];
+ edge[nedges++] = map_goto(stateno, *rp);
+ if (nullable[*rp]) done = 0;
+ }
+ }
+ }
+
+ if (nedges)
+ {
+ includes[i] = shortp = NEW2(nedges + 1, short);
+ for (j = 0; j < nedges; j++)
+ shortp[j] = edge[j];
+ shortp[nedges] = -1;
+ }
+ }
+
+ new_includes = transpose(includes, ngotos);
+
+ for (i = 0; i < ngotos; i++)
+ if (includes[i])
+ FREE(includes[i]);
+
+ FREE(includes);
+
+ includes = new_includes;
+
+ FREE(edge);
+ FREE(states);
+}
+
+
+void
+add_lookback_edge(int stateno, int ruleno, int gotono)
+{
+ register int i;
+ register int k;
+ register int found;
+ register shorts *sp;
+
+ i = lookaheads[stateno];
+ k = lookaheads[stateno + 1];
+ found = 0;
+ while (!found && i < k)
+ {
+ if (LAruleno[i] == ruleno)
+ found = 1;
+ else
+ i++;
+ }
+
+ if (found == 0)
+ berror("add_lookback_edge");
+
+ sp = NEW(shorts);
+ sp->next = lookback[i];
+ sp->value = gotono;
+ lookback[i] = sp;
+}
+
+
+
+short **
+transpose(short** R_arg, int n)
+{
+ register short **new_R;
+ register short **temp_R;
+ register short *nedges;
+ register short *sp;
+ register int i;
+ register int k;
+
+ nedges = NEW2(n, short);
+
+ for (i = 0; i < n; i++)
+ {
+ sp = R_arg[i];
+ if (sp)
+ {
+ while (*sp >= 0)
+ nedges[*sp++]++;
+ }
+ }
+
+ new_R = NEW2(n, short *);
+ temp_R = NEW2(n, short *);
+
+ for (i = 0; i < n; i++)
+ {
+ k = nedges[i];
+ if (k > 0)
+ {
+ sp = NEW2(k + 1, short);
+ new_R[i] = sp;
+ temp_R[i] = sp;
+ sp[k] = -1;
+ }
+ }
+
+ FREE(nedges);
+
+ for (i = 0; i < n; i++)
+ {
+ sp = R_arg[i];
+ if (sp)
+ {
+ while (*sp >= 0)
+ *temp_R[*sp++]++ = i;
+ }
+ }
+
+ FREE(temp_R);
+
+ return (new_R);
+}
+
+
+void
+compute_FOLLOWS()
+{
+ register int i;
+
+ digraph(includes);
+
+ for (i = 0; i < ngotos; i++)
+ {
+ if (includes[i]) FREE(includes[i]);
+ }
+
+ FREE(includes);
+}
+
+
+void
+compute_lookaheads()
+{
+ register int i;
+ register int n;
+ register unsigned *fp1;
+ register unsigned *fp2;
+ register unsigned *fp3;
+ register shorts *sp;
+ register unsigned *rowp;
+/* register short *rulep; JF unused */
+/* register int count; JF unused */
+ register shorts *sptmp;/* JF */
+
+ rowp = LA;
+ n = lookaheads[nstates];
+ for (i = 0; i < n; i++)
+ {
+ fp3 = rowp + tokensetsize;
+ for (sp = lookback[i]; sp; sp = sp->next)
+ {
+ fp1 = rowp;
+ fp2 = F + tokensetsize * sp->value;
+ while (fp1 < fp3)
+ *fp1++ |= *fp2++;
+ }
+
+ rowp = fp3;
+ }
+
+ for (i = 0; i < n; i++)
+ {/* JF removed ref to freed storage */
+ for (sp = lookback[i]; sp; sp = sptmp) {
+ sptmp=sp->next;
+ FREE(sp);
+ }
+ }
+
+ FREE(lookback);
+ FREE(F);
+}
+
+
+void
+digraph(short** relation)
+{
+ register int i;
+
+ infinity = ngotos + 2;
+ INDEX = NEW2(ngotos + 1, short);
+ VERTICES = NEW2(ngotos + 1, short);
+ top = 0;
+
+ R = relation;
+
+ for (i = 0; i < ngotos; i++)
+ INDEX[i] = 0;
+
+ for (i = 0; i < ngotos; i++)
+ {
+ if (INDEX[i] == 0 && R[i])
+ traverse(i);
+ }
+
+ FREE(INDEX);
+ FREE(VERTICES);
+}
+
+
+void
+traverse(int i)
+{
+ register unsigned *fp1;
+ register unsigned *fp2;
+ register unsigned *fp3;
+ register int j;
+ register short *rp;
+
+ int height;
+ unsigned *base;
+
+ VERTICES[++top] = i;
+ INDEX[i] = height = top;
+
+ base = F + i * tokensetsize;
+ fp3 = base + tokensetsize;
+
+ rp = R[i];
+ if (rp)
+ {
+ while ((j = *rp++) >= 0)
+ {
+ if (INDEX[j] == 0)
+ traverse(j);
+
+ if (INDEX[i] > INDEX[j])
+ INDEX[i] = INDEX[j];
+
+ fp1 = base;
+ fp2 = F + j * tokensetsize;
+
+ while (fp1 < fp3)
+ *fp1++ |= *fp2++;
+ }
+ }
+
+ if (INDEX[i] == height)
+ {
+ for (;;)
+ {
+ j = VERTICES[top--];
+ INDEX[j] = infinity;
+
+ if (i == j)
+ break;
+
+ fp1 = base;
+ fp2 = F + j * tokensetsize;
+
+ while (fp1 < fp3)
+ *fp2++ = *fp1++;
+ }
+ }
+}