Import byacc from invisible island, it brings us lots of compatibilities with

bison, keeping full compatibility with our previous yacc implementation.

Also bring the ability to create reentrant parser

This fix bin/140309 [1]

PR:		bin/140309 [1]
Submitted by:	Philippe Pepiot <ksh@philpep.org> [1]
Approved by:	des (mentor)
MFC after:	1 month

1 files changed, 251 insertions, 0 deletions

diff --git a/contrib/byacc/closure.c b/contrib/byacc/closure.c
new file mode 100644
index 0000000..7573ff5
--- /dev/null
+++ b/contrib/byacc/closure.c
@@ -0,0 +1,251 @@
+/* $Id: closure.c,v 1.9 2010/06/09 08:21:47 tom Exp $ */
+
+#include "defs.h"
+
+Value_t *itemset;
+Value_t *itemsetend;
+unsigned *ruleset;
+
+static unsigned *first_derives;
+static unsigned *EFF;
+
+static void
+set_EFF(void)
+{
+    unsigned *row;
+    int symbol;
+    short *sp;
+    int rowsize;
+    int i;
+    int rule;
+
+    rowsize = WORDSIZE(nvars);
+    EFF = NEW2(nvars * rowsize, unsigned);
+
+    row = EFF;
+    for (i = start_symbol; i < nsyms; i++)
+    {
+	sp = derives[i];
+	for (rule = *sp; rule > 0; rule = *++sp)
+	{
+	    symbol = ritem[rrhs[rule]];
+	    if (ISVAR(symbol))
+	    {
+		symbol -= start_symbol;
+		SETBIT(row, symbol);
+	    }
+	}
+	row += rowsize;
+    }
+
+    reflexive_transitive_closure(EFF, nvars);
+
+#ifdef	DEBUG
+    print_EFF();
+#endif
+}
+
+void
+set_first_derives(void)
+{
+    unsigned *rrow;
+    unsigned *vrow;
+    int j;
+    unsigned k;
+    unsigned cword = 0;
+    short *rp;
+
+    int rule;
+    int i;
+    int rulesetsize;
+    int varsetsize;
+
+    rulesetsize = WORDSIZE(nrules);
+    varsetsize = WORDSIZE(nvars);
+    first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
+
+    set_EFF();
+
+    rrow = first_derives + ntokens * rulesetsize;
+    for (i = start_symbol; i < nsyms; i++)
+    {
+	vrow = EFF + ((i - ntokens) * varsetsize);
+	k = BITS_PER_WORD;
+	for (j = start_symbol; j < nsyms; k++, j++)
+	{
+	    if (k >= BITS_PER_WORD)
+	    {
+		cword = *vrow++;
+		k = 0;
+	    }
+
+	    if (cword & (unsigned)(1 << k))
+	    {
+		rp = derives[j];
+		while ((rule = *rp++) >= 0)
+		{
+		    SETBIT(rrow, rule);
+		}
+	    }
+	}
+
+	rrow += rulesetsize;
+    }
+
+#ifdef	DEBUG
+    print_first_derives();
+#endif
+
+    FREE(EFF);
+}
+
+void
+closure(short *nucleus, int n)
+{
+    unsigned ruleno;
+    unsigned word;
+    unsigned i;
+    Value_t *csp;
+    unsigned *dsp;
+    unsigned *rsp;
+    int rulesetsize;
+
+    Value_t *csend;
+    unsigned *rsend;
+    int symbol;
+    Value_t itemno;
+
+    rulesetsize = WORDSIZE(nrules);
+    rsend = ruleset + rulesetsize;
+    for (rsp = ruleset; rsp < rsend; rsp++)
+	*rsp = 0;
+
+    csend = nucleus + n;
+    for (csp = nucleus; csp < csend; ++csp)
+    {
+	symbol = ritem[*csp];
+	if (ISVAR(symbol))
+	{
+	    dsp = first_derives + symbol * rulesetsize;
+	    rsp = ruleset;
+	    while (rsp < rsend)
+		*rsp++ |= *dsp++;
+	}
+    }
+
+    ruleno = 0;
+    itemsetend = itemset;
+    csp = nucleus;
+    for (rsp = ruleset; rsp < rsend; ++rsp)
+    {
+	word = *rsp;
+	if (word)
+	{
+	    for (i = 0; i < BITS_PER_WORD; ++i)
+	    {
+		if (word & (unsigned)(1 << i))
+		{
+		    itemno = rrhs[ruleno + i];
+		    while (csp < csend && *csp < itemno)
+			*itemsetend++ = *csp++;
+		    *itemsetend++ = itemno;
+		    while (csp < csend && *csp == itemno)
+			++csp;
+		}
+	    }
+	}
+	ruleno += BITS_PER_WORD;
+    }
+
+    while (csp < csend)
+	*itemsetend++ = *csp++;
+
+#ifdef	DEBUG
+    print_closure(n);
+#endif
+}
+
+void
+finalize_closure(void)
+{
+    FREE(itemset);
+    FREE(ruleset);
+    FREE(first_derives + ntokens * WORDSIZE(nrules));
+}
+
+#ifdef	DEBUG
+
+void
+print_closure(int n)
+{
+    short *isp;
+
+    printf("\n\nn = %d\n\n", n);
+    for (isp = itemset; isp < itemsetend; isp++)
+	printf("   %d\n", *isp);
+}
+
+void
+print_EFF(void)
+{
+    int i, j;
+    unsigned *rowp;
+    unsigned word;
+    unsigned k;
+
+    printf("\n\nEpsilon Free Firsts\n");
+
+    for (i = start_symbol; i < nsyms; i++)
+    {
+	printf("\n%s", symbol_name[i]);
+	rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
+	word = *rowp++;
+
+	k = BITS_PER_WORD;
+	for (j = 0; j < nvars; k++, j++)
+	{
+	    if (k >= BITS_PER_WORD)
+	    {
+		word = *rowp++;
+		k = 0;
+	    }
+
+	    if (word & (1 << k))
+		printf("  %s", symbol_name[start_symbol + j]);
+	}
+    }
+}
+
+void
+print_first_derives(void)
+{
+    int i;
+    int j;
+    unsigned *rp;
+    unsigned cword = 0;
+    unsigned k;
+
+    printf("\n\n\nFirst Derives\n");
+
+    for (i = start_symbol; i < nsyms; i++)
+    {
+	printf("\n%s derives\n", symbol_name[i]);
+	rp = first_derives + i * WORDSIZE(nrules);
+	k = BITS_PER_WORD;
+	for (j = 0; j <= nrules; k++, j++)
+	{
+	    if (k >= BITS_PER_WORD)
+	    {
+		cword = *rp++;
+		k = 0;
+	    }
+
+	    if (cword & (1 << k))
+		printf("   %d\n", j);
+	}
+    }
+
+    fflush(stdout);
+}
+
+#endif