Import byacc-20121003.
authorPeter Avalos <pavalos@dragonflybsd.org>
Sat, 19 Jan 2013 10:03:58 +0000 (02:03 -0800)
committerPeter Avalos <pavalos@dragonflybsd.org>
Sat, 19 Jan 2013 10:11:39 +0000 (02:11 -0800)
This is a significant update for yacc that's being maintained by Thomas
Dickey at http://invisible-island.net/byacc/.

20 files changed:
contrib/byacc/AUTHORS [new file with mode: 0644]
contrib/byacc/CHANGES [new file with mode: 0644]
contrib/byacc/README [new file with mode: 0644]
contrib/byacc/README.DELETED [new file with mode: 0644]
contrib/byacc/VERSION [new file with mode: 0644]
contrib/byacc/closure.c [new file with mode: 0644]
contrib/byacc/defs.h [new file with mode: 0644]
contrib/byacc/error.c [new file with mode: 0644]
contrib/byacc/graph.c [new file with mode: 0644]
contrib/byacc/lalr.c [new file with mode: 0644]
contrib/byacc/lr0.c [new file with mode: 0644]
contrib/byacc/main.c [new file with mode: 0644]
contrib/byacc/mkpar.c [new file with mode: 0644]
contrib/byacc/output.c [new file with mode: 0644]
contrib/byacc/reader.c [new file with mode: 0644]
contrib/byacc/skeleton.c [new file with mode: 0644]
contrib/byacc/symtab.c [new file with mode: 0644]
contrib/byacc/verbose.c [new file with mode: 0644]
contrib/byacc/warshall.c [new file with mode: 0644]
contrib/byacc/yacc.1 [new file with mode: 0644]

diff --git a/contrib/byacc/AUTHORS b/contrib/byacc/AUTHORS
new file mode 100644 (file)
index 0000000..6d75337
--- /dev/null
@@ -0,0 +1,7 @@
+-- $Id: AUTHORS,v 1.1 2010/06/06 20:31:51 tom Exp $
+-- vile:txtmode
+-- This file is used by a script that collects contributor information and
+-- resolves nicknames vs fullnames.
+dickey Thomas Dickey
+schmitz        Sylvain Schmitz
+unknown        Robert Corbett
diff --git a/contrib/byacc/CHANGES b/contrib/byacc/CHANGES
new file mode 100644 (file)
index 0000000..877b227
--- /dev/null
@@ -0,0 +1,1270 @@
+2012-10-03  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+       * configure: regen
+
+       * configure.in: moved AC_PROG_CC_STDC call into CF_PROG_CC
+
+       * aclocal.m4:
+       moved AC_PROG_CC_STDC call into CF_PROG_CC and (for other uses than byacc)
+       the CF_PROG_CC macro provides the CF_ANSI_CC_REQD for the 2.13 flavor.
+
+       * aclocal.m4, configure.in:
+       Arian's change dropped my check for misused $CC variable - restore that with
+       alternate macro CF_PROG_CC.
+
+2012-10-03  Adrian.Bunk
+
+       * aclocal.m4:
+       suggested patch: drop CF_ANSI_CC_REQD, CF_ANSI_CC_CHECK, CF_PROG_EXT since
+       they are not needed.
+
+2012-10-03  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * aclocal.m4:
+       split-out CF_CC_ENV_FLAGS from CF_ANSI_CC_CHECK to avoid losing it in
+       Adrian's suggested changes.
+
+       * aclocal.m4:
+       CF_CLANG_COMPILER - check if the given compiler is really clang.
+
+       * aclocal.m4:
+       add check for clang to CF_GCC_WARNINGS.  modify CF_GCC_WARNINGS to work around
+       old gcc warning:  ncurses change to (try to) use gnatgcc exposed gnatgcc 2.8.1
+       on my Sarge system (versus 3.3.5 for the normal gcc).  The 2.8.1's
+       pointer-arithmetic checks fell afoul of gcc's misuse of void* in string.h; work
+       around by excluding that check for pre-3.x compilers.
+
+       * aclocal.m4:
+       modify CF_GCC_ATTRIBUTES so that autoheader is able to see the definitions
+       provided by this macro.  use AC_DEFINE_UNQUOTED() in CF_GCC_ATTRIBUTES rather
+       than appending to confdefs.h, since long-ago concern about the ability to
+       pass-through parameterized macros appears to be not a problem, testing with
+       2.13 and 2.52
+
+2012-10-03  Adrian.Bunk
+
+       * aclocal.m4:
+       add parameter to AC_DEFINE_UNQUOTED() to allow it to be recognized by
+       autoheader, updated macros:
+               CF_CHECK_CACHE
+               CF_DISABLE_LEAKS
+               CF_MKSTEMP
+               CF_MIXEDCASE_FILENAMES
+               CF_NO_LEAKS_OPTION
+
+2012-10-03  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * aclocal.m4:
+       move existence-check for mkstemp out of the AC_TRY_RUN, to help with
+       cross-compiles
+
+2012-10-02  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config_h.in:
+       Adrian Bunk request - replace this with the output from autoheader
+
+2012-09-29  Adrian.Bunk
+
+       * configure.in:
+       suggested change: replace CF_ANSI_CC_REQD by AC_PROG_CC_STDC (since no
+       check is needed anymore for standard C compilers), drop AC_CONST (same
+       reason), modify AC_OUTPUT to rely upon template generated by autoheader.
+       bump requirement to autoconf 2.52.20011201 and drop check for CF_PROG_EXT
+       as being obsolete with autoconf 2.52x
+
+       * configure.in, main.c: drop check for atexit, because it is standard C
+
+       * makefile.in: add assignment for datarootdir variable.
+
+2012-05-26  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+       * reader.c:
+       some versions of gcc may warn that bp is not set in mark_symbol, e.g.,
+       if GCC_NORETURN is not handled; appease the compiler.
+
+       * reader.c:
+       use the declared types Assoc_t and Value_t in some places where compiler only
+       cared about char versus short.
+
+       * reader.c:
+       use TMALLOC() and TREALLOC() macros to simplify allocation/reallocation
+       (no object change)
+
+       * defs.h:
+       add fallbacks for GCC_NORETURN and GCC_UNUSED to make it simpler for *BSD
+       packagers to build without configure script.  Also remove duplicate declaration
+       of pure_parser variable (prompted by patch by Baptiste Daroussin).
+
+       Also define new TMALLOC and TREALLOC macros to simplify/replace MALLOC and
+       REALLOC macros.
+
+       * symtab.c:
+       use TMALLOC() and TREALLOC() macros to simplify allocation/reallocation
+       (no object change)
+
+2012-05-25  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * output.c, main.c, verbose.c, mkpar.c, lr0.c:
+       use TMALLOC() and TREALLOC() macros to simplify allocation/reallocation
+       (no object change)
+
+2012-01-15  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/copyright: bump
+
+       * test/run_make.sh: workaround for breakage due to GNU make 3.82
+
+       * test/run_make.sh:
+       tested with Solaris 10 (bison 1.875) and added scripting to exercise
+       the /usr/ccs/bin/yacc executable
+
+       * test/grammar.tab.c: regen
+
+       * test/grammar.y: modify to also build with Solaris yacc
+
+       * VERSION, package/debian/changelog, package/byacc.spec: bump
+
+       * test/calc1.output, test/calc1.tab.c: regen
+
+       * test/calc1.y:
+       undo the change made to appease bison, since it was only a warning.
+
+       * test/pure_calc.tab.c, test/pure_error.tab.c: regen
+
+       * test/run_make.sh: another fix for running from top-level directory
+
+       * makefile.in:
+       ensure that check_make rule depends on having byacc built.
+
+       * test/run_make.sh: fixes for building from parent directory
+
+       * test/pure_error.y, test/pure_calc.y: bison-fixes
+
+       * test/calc2.tab.c, test/calc3.tab.c, test/code_error.code.c, test/ftp.tab.c, test/pure_calc.tab.c, test/pure_error.tab.c:
+       regen
+
+       * test/calc2.y, test/calc3.y, test/code_error.y, test/ftp.y:
+       byacc already declares yyerror
+
+       * test/pure_error.y, test/pure_calc.y:
+       modified to help make the files build with bison
+
+       * test/run_make.sh:
+       supply a "%pure-parser" directive when bison needs it.
+
+       * test/code_calc.code.c: regen
+
+       * test/code_calc.y: modified to help make the files build with bison
+
+       * yacc.1:
+       in testing, found that %expect did not work as documented for bison.
+       do not recommend it for portable code.
+
+       * test/run_make.sh: workaround breakage in bison's %expect directive
+
+       * test/grammar.y: modified to help make the files build with bison
+
+       * test/calc1.output, test/calc1.tab.c, test/grammar.tab.c: regen
+
+       * test/calc1.y: quiet a spurious warning from bison 2.3
+
+       * test/calc1.tab.c: regen
+
+       * test/calc1.y: modified to help make the files build with bison
+
+       * yacc.1: comment on "-y" and "-P" options.
+
+       * yacc.1: comment on portability
+
+       * test/ftp.tab.c, test/quote_calc-s.tab.c, test/quote_calc.tab.c, test/quote_calc2-s.tab.c, test/quote_calc3-s.tab.c:
+       regen
+
+       * test/ftp.y: modified to help make the files build with bison
+       (bison's "-y" option is of no use in providing "yacc" compatibility)
+
+       * test/quote_calc2.tab.c, test/quote_calc3.tab.c, test/quote_calc4-s.tab.c, test/quote_calc4.tab.c:
+       regen
+
+       * test/code_calc.y, test/quote_calc2.y, test/quote_calc.y, test/quote_calc4.y, test/quote_calc3.y:
+       modified to help make the files build with bison
+
+       * test/calc.tab.c: regen
+
+       * test/calc.y: modified to help make the files build with bison
+
+       * test/error.tab.c: regen
+
+       * test/error.y: modified to help make the files build with bison
+
+       * test/calc2.tab.c, test/calc3.tab.c, test/code_error.code.c: regen
+
+       * test/run_make.sh:
+       check for older bisons which (2.3 for instance) do not support pure parsers
+
+       * test/code_error.y, test/calc3.y, test/calc2.y:
+       modified to help make the files build with bison
+
+       * test/run_test.sh: use $opt2 in filenames of the generated files
+
+       * test/quote_calc2-s.tab.c, test/quote_calc3-s.tab.c, test/quote_calc4-s.tab.c, test/quote_calc-s.tab.c, test/quote_calc.tab.c, test/quote_calc2.tab.c, test/quote_calc3.tab.c, test/quote_calc4.tab.c:
+       regen
+
+2012-01-14  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/calc2.tab.c, test/code_calc.code.c, test/code_error.code.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c, test/calc.tab.c, test/calc1.tab.c:
+       regen
+
+       * output.c: Several changes:
+               a) add YYLEX_PARAM_TYPE, like YYPARSE_PARAM_TYPE, but for yylex.
+               b) modify definitions for YYLEX_DECL to be more like YYPARSE_DECL,
+                  using YYLEX_PARAM_TYPE and YYLEX_PARAM.
+               c) add ifdef's around #define's for YYERROR_DECL and YYERROR_CALL,
+                  to help with redefinitions.
+
+       * test/pure_calc.tab.c:
+       modified to help make the files build with bison
+
+       * test/run_make.sh:
+       start work on followup, to check if the generated files build with bison.
+
+       * test/pure_calc.y, test/pure_error.tab.c:
+       modified to help make the files build with bison
+
+       * test/calc3.tab.c: regen
+
+       * test/quote_calc-s.output, test/quote_calc-s.tab.c, test/quote_calc-s.tab.h, test/quote_calc2-s.output, test/quote_calc2-s.tab.c, test/quote_calc2-s.tab.h, test/quote_calc3-s.output, test/quote_calc3-s.tab.c, test/quote_calc3-s.tab.h, test/quote_calc4-s.output, test/quote_calc4-s.tab.c, test/quote_calc4-s.tab.h:
+       RCS_BASE
+
+       * test/run_test.sh: generate/test with "-s" option applied.
+
+2012-01-13  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+       * yacc.1: improve documentation of -s option
+
+       * yacc.1: note that yacc ignores -y
+
+       * main.c: add -s option to usage message.
+
+       * test/quote_calc3.output, test/quote_calc3.tab.c, test/quote_calc4.output, test/quote_calc4.tab.c, test/quote_calc4.tab.h, test/quote_calc3.y, test/quote_calc.tab.h, test/quote_calc.output, test/quote_calc.tab.c, test/quote_calc2.output, test/quote_calc2.tab.c, test/quote_calc2.tab.h, test/quote_calc3.tab.h, test/quote_calc4.y, test/quote_calc.y, test/quote_calc2.y:
+       RCS_BASE
+
+       * configure: regen
+
+       * aclocal.m4: resync with my-autoconf, i.e., fixes for CF_XOPEN_SOURCE
+
+2011-12-19  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+       * yacc.1, output.c, main.c, defs.h:
+       add "-s" option to suppress generating #define's based on string contents
+       in a %token statement.  For instance
+               %token EQLS "Equals"
+       would generate
+               #define EQLS 256
+               #define Equals 257
+       Simply suppressing the second #define makes the behavior closer to yacc.
+       (report by Paulo Andrade).
+
+2011-09-08  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+       * output.c:
+       fix some more interaction between -i and -d flags to ensure YYERRCODE
+       and YYSTYPE are declared, tested with cproto.
+
+2011-09-07  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * yacc.1: document "-i" option.
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+       * output.c: fix an interaction between -i and -d
+
+       * test/code_error.code.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c, test/pure_calc.tab.c, test/pure_error.tab.c, test/calc.tab.c, test/calc1.tab.c, test/calc2.tab.c, test/calc3.tab.c, test/code_calc.code.c:
+       regen - changes for "-i" option move the global/impure variables near the
+       macros that may add a prefix, etc.
+
+       * skeleton.c, output.c, defs.h: changes to support "-i" option.
+
+2011-09-06  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * reader.c: pass explicit file-pointer to write_section()
+
+       * main.c:
+       add "-i" option, to generate interface-file (suggested by Denis M. Wilson)
+
+2011-09-05  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * configure: regen
+
+       * aclocal.m4:
+       resync with my-autoconf: CF_ANSI_CC_CHECK (check for $CFLAGS in $CC)
+       and CF_XOPEN_SOURCE (update aix, cygwin and netbsd checks)
+
+       * defs.h, error.c, reader.c:
+       add check for missing "}" on %parse-param and %lex-param lines (report by Denis M Wilson)
+
+2011-04-01  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.sub: 2011-04-01
+
+2011-02-02  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.guess: 2011-01-01
+
+2010-12-29  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * defs.h, skeleton.c:
+       add const qualifier to skeleton data, per NetBSD changes (report by Christos Zoulas)
+
+       * defs.h:
+       mark all of the error-functions as non-returning (report by Christos Zoulas)
+
+       * test/grammar.tab.c, test/pure_calc.tab.c, test/pure_error.tab.c, test/calc.tab.c, test/calc1.tab.c, test/calc2.tab.c, test/calc3.tab.c, test/code_calc.code.c, test/code_error.code.c, test/error.tab.c, test/ftp.tab.c:
+       regen
+
+       * skeleton.c:
+       use only realloc() rather than realloc+malloc, agree that systems needing this
+       are very rare (prompted by NetBSD change).
+
+       * test/ftp.tab.c: regen
+
+2010-12-29  Christos.Zoulas
+
+       * test/ftp.y:
+       improve example, which was stuck in 19XX and assumed file sizes were longs.
+
+2010-12-29  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/ftp.tab.c, test/grammar.tab.c, test/pure_calc.tab.c, test/pure_error.tab.c, test/calc.tab.c, test/calc1.tab.c, test/calc2.tab.c, test/calc3.tab.c, test/code_calc.code.c, test/code_error.code.c, test/error.tab.c:
+       regen
+
+       * test/pure_error.y, test/pure_calc.y, test/ftp.y, test/error.y, test/code_error.y, test/code_calc.y, test/calc.y, test/calc3.y, test/calc2.y, test/calc1.y:
+       use byacc's YYLEX_DECL/YYERROR_DECL symbols to prototype yylex/yyerror
+
+       * skeleton.c:
+       remove explicit prototype for yylex() via YYLEX_DECL() macro, since that
+       would prevent declaring yylex() static (request by Christos Zoulas).
+
+       * test/calc2.tab.c, test/calc3.tab.c: regen
+
+2010-12-29  Christos.Zoulas
+
+       * output.c: correct definition for YYERROR_DECL()
+
+2010-12-29  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+2010-12-26  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * defs.h, main.c:
+       change return-type of allocate() to avoid warnings of alignment problems
+
+       * main.c: Solaris declares chmod() in <sys/stat.h>
+
+       * configure: regen
+
+       * main.c: ifdef'd use of fcntl.h
+
+       * configure.in: add configure checks for fcntl.h, atexit and mkstemp
+
+       * main.c: for cases where mkstemp() is not available, use tempnam/open
+
+       * aclocal.m4: add CF_MKSTEMP
+
+       * aclocal.m4:
+       improve quoting, deprecate ${name-value} in favor of standard ${name:-value}
+
+2010-12-25  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * main.c:
+       start revising use of tmpfile(), to make this work with MinGW.  Start by
+       implementing a mkstemp() alternative - noting that mkstemp() also is broken
+       for MinGW.
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+2010-11-27  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/byacc.spec, package/debian/changelog, VERSION: bump
+
+       * test/calc2.tab.c, test/calc3.tab.c: regen
+
+       * output.c:
+       corrected use of %parse-param value in yyerror(); it doesn't use &yylval
+       (report by Clifford Yapp)
+
+2010-11-26  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * skeleton.c: typo
+
+       * output.c:
+       correct line-numbering when "-r" option is used; the 'outline' variable
+       should only be incremented when writing to the code-file.
+
+       * test/code_calc.code.c, test/code_error.code.c: regen
+
+       * yacc.1: bump date
+
+       * yacc.1: comment on -b option vs -r
+
+       * test/calc2.tab.c, test/calc2.y, test/calc3.tab.c, test/calc3.y, test/ftp.tab.c, test/grammar.tab.c, test/pure_calc.tab.c, test/pure_error.tab.c, test/calc.tab.c, test/calc1.tab.c, test/code_calc.code.c, test/code_error.code.c, test/error.tab.c:
+       regen
+
+       * output.c:
+       improve on YYERROR_DECL(), adding dummy params which can be used for the
+       actual function declaration.  Also add YYERROR_CALL().  The two macros
+       simplify maintaining sets of grammars which may/may not be pure.
+
+       * test/calc1.y, test/ftp.tab.c, test/grammar.tab.c, test/pure_calc.tab.c, test/pure_error.tab.c, test/calc.tab.c, test/calc1.tab.c, test/calc2.tab.c, test/calc3.tab.c, test/code_calc.code.c, test/code_error.code.c, test/error.tab.c:
+       regen
+
+       * output.c: generate yyerror() calls in output.c
+       This is for compatibility with bison, which passes the yylval to yyerror
+       when the %parse-param feature is used.
+
+       * skeleton.c, defs.h: generate yyerror() calls in output.c
+
+       * output.c: simplified a little, using putc_code() and putl_code()
+
+       * test/calc1.tab.h: regen
+
+       * reader.c:
+       improve ifdef for YYSTYPE union declaration (report by Clifford Yapp)
+
+       * reader.c:
+       accept underscore as a replacement for dash in command names, e.g.,
+       "%pure_parser" vs "%pure-parser".
+
+       * test/calc1.tab.c: regen
+
+       * output.c, reader.c:
+       also ifdef YYSTYPE declaration in the generated code (report by Clifford Yapp)
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+2010-11-24  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * main.c, defs.h, symtab.c, error.c: reduce global variables
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+       * reader.c:
+       amend fix for Redhat #112617 to still call default_action_warning() for
+       empty rules (report by Bruce Cran).
+
+2010-11-22  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * output.c:
+       add ifdef to guard against redefinition of YYSTYPE union (request by Clifford Yapp).
+
+       * test/calc1.tab.c: regen
+
+       * test/calc1.y: cleanup compiler warnings
+
+       * test/grammar.y: add "%expect"
+
+       * test/calc1.tab.h: regen
+
+       * test/calc1.output, test/calc1.tab.c, test/calc1.tab.h: RCS_BASE
+
+       * test/calc2.tab.c, test/calc3.tab.c: regen
+
+       * test/calc1.y:
+       advanced example from Steve Johnson's paper, uses unions
+
+       * test/calc3.y, test/calc2.y: init 'base', so examples can run
+
+       * test/ftp.tab.c, test/ftp.y: tweaks to compile with g++
+
+       * output.c: compensate for fix in reader.c
+
+       * reader.c:
+       add/use putc_both() and puts_both(), incidentally fixing a place where
+       a union copied to the union_file may be missing the end of the last line.
+
+       * package/debian/changelog, package/byacc.spec, VERSION: bump
+
+2010-09-28  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.guess: 2010-09-24
+
+2010-09-10  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.sub: 2010-09-11
+
+2010-06-10  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * yacc.1, package/debian/changelog, package/byacc.spec, VERSION:
+       bump to 2010/06/10
+
+2010-06-09  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * reader.c: free declarations in leak-testing code.
+
+       * main.c: close code_file if -r option used, for leak-testing
+
+       * defs.h, reader.c:
+       improve %lex-param / %parse-param implementation by allowing for arrays to
+       be passed as parameters, e.g., "int regs[26]".
+
+       * test/calc3.tab.c, test/calc3.y, test/calc3.output, test/calc3.tab.h, test/calc2.tab.c, test/calc2.y, test/calc2.tab.h, test/calc2.output:
+       RCS_BASE
+
+       * output.c:
+       improve %lex-param / %parse-param implementation by allowing for arrays to
+       be passed as parameters, e.g., "int regs[26]".
+
+       * test/calc.tab.c, test/calc.y:
+       test-cases and reference files for %lex-param / %parse-param
+
+       * makefile.in: add docs-rule, for html/pdf/txt form of manpage
+
+       * configure: regen
+
+       * aclocal.m4: add CF_XOPEN_SOURCE, etc.
+
+       * configure.in:
+       use CF_XOPEN_SOURCE check to ensure that strdup is in scope, e.g., for c89
+
+       * test/ftp.tab.c, test/ftp.y, reader.c, symtab.c, verbose.c, lr0.c, main.c, mkpar.c, output.c, defs.h, closure.c:
+       fix warnings from clang --analyze
+
+2010-06-08  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * output.c: fix to build with c89, etc.
+
+       * reader.c: gcc warning
+
+       * test/ftp.tab.c, test/ftp.y, test/calc.tab.c, test/code_calc.code.c, test/code_error.code.c, test/code_error.y, test/code_calc.y, test/calc.y, test/pure_error.tab.c, test/error.tab.c, test/error.y, test/pure_error.y, test/pure_calc.tab.c, test/pure_calc.y:
+       modified test-cases to allow them to compile, to validate pure-parser changes.
+       updated reference files to match.
+
+       * output.c:
+       move call for output_stype() earlier since it is used in pure-parser declarations
+
+       * test/grammar.tab.c, test/grammar.y:
+       modified test-cases to allow them to compile, to validate pure-parser changes.
+       updated reference files to match.
+
+       * test/calc.tab.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c:
+       regen
+
+       * yacc.1: document %lex-param and %parse-param
+
+       * test/run_lint.sh, test/run_make.sh: RCS_BASE
+
+       * test/run_test.sh:
+       further modify to allow build-directory to be in a different location by
+       passing this directory's location as a parameter to the script.
+
+       * makefile.in:
+       add check_make and check_lint rules to help validate the generated files
+       in the test-directory
+
+2010-06-07  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/pure_calc.tab.c, test/pure_error.tab.c: RCS_BASE
+
+       * test/run_test.sh:
+       provide for testing -r and -P options by checking if the ".y" filename
+       begins with "code_" or "pure_", respectively.
+
+       * test/code_error.code.c, test/code_error.tab.c, test/code_error.tab.h, test/code_calc.code.c, test/code_calc.tab.c, test/code_calc.tab.h, test/pure_calc.output, test/pure_calc.tab.h, test/pure_error.output, test/pure_error.tab.h, test/code_calc.output, test/code_error.output:
+       RCS_BASE
+
+       * test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c: regen
+
+       * test/run_test.sh:
+       changes to support running "make check" in a separate build-tree
+
+       * main.c: add "-P" to usage message
+
+       * reader.c: use UCH() macro to hide casts.
+
+2010-06-07  Andres.Mejia
+
+       * main.c, output.c, reader.c, defs.h, skeleton.c:
+       Fix the output order of the generated parse code file.  This allows for
+       the use of YYPARSE_PARAM, by having the output that checks for
+       YYPARSE_PARAM to be defined come after the C code block in the
+       definitions section of a yacc file.
+
+       Implement support for YYLEX_PARAM, similar to bison.  This is useful for
+       support for building reentrant lexers with flex.
+
+       Fix a compatibility issue with bison's pure-parser option.  Bison
+       defines yylex as sending at least one parameter, &yylval, as the first
+       parameter and doesn't seem to have an easy way to remove that parameter.
+       This on the other hand is rather convenient to support saving to yylval
+       from flex when building reentrant lexers and parsers.
+
+       Add support for the %parse-param and %lex-param directives used in
+       bison.  This change bears some similarity to NetBSD's changes to byacc
+       at http://www.mail-archive.com/source-changes-full@netbsd.org/msg08143.html
+
+       Bison allows for POSIX yacc emulation via a yacc directive in the yacc
+       file, and also via a command line switch.  Implement this feature as a
+       no-op for byacc, since byacc is designed to be POSIX yacc compatible
+       anyway.  This allows for better compatibility with yacc sources written
+       for bison.
+
+2010-06-07  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * VERSION: bump to 2010/06/07
+
+2010-06-06  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/calc.tab.c, configure: regen
+
+       * skeleton.c:
+       move #include's down into the generated code, to allow user-defined code
+       to override feature definitions, particularly with stdlib.h (request by
+       Marcus Kool).
+
+       * lr0.c, error.c, reader.c, defs.h:
+       strict gcc 3.4.6 warnings on 64-bit platform
+
+       * aclocal.m4, configure.in: add check for lint
+
+       * makefile.in: add lint rule
+
+       * defs.h, closure.c, lr0.c, warshall.c, main.c:
+       fix gcc warnings, mostly for 64-bit platform
+
+       * aclocal.m4:
+       add macros for checking ctags/etags, e.g., to work with NetBSD pkgsrc
+
+       * makefile.in: add etags/TAGS if available
+
+       * configure.in: add configure check for actual ctags and etags programs
+
+       * package/debian/copyright: add copyright notices for non-PD files
+
+       * package/debian/changelog:
+       incorporated scripts in upstream to use for test-builds
+
+       * makefile.in: drop mkdirs.sh, just use "mkdir -p"
+
+       * AUTHORS: nicknames for some contributors (see CHANGES for details)
+
+       * package/byacc.spec: RPM file for byacc
+
+       * VERSION: bump to 2010/06/06
+
+       * aclocal.m4: add copyright notice, from "my-autoconf" macros
+               http://invisible-island.net/autoconf/autoconf.html
+
+       * package/RCS, package/debian/RCS, package/debian/source/RCS, package/pkgsrc/RCS:
+       PERMIT FILE
+
+       * aclocal.m4: resync with my-autoconf.  summary of changes:
+               a) CF_ADD_CFLAGS, etc., improve quoting of ifelse() parameter
+               b) CF_DISABLE_ECHO, change indent-convention for substituted makefile
+               c) CF_GCC_VERSION, ignore stderr
+               d) CF_GCC_WARNINGS, adjust options to work with c89 wrapper of gcc
+
+2010-04-20  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/changelog, package/debian/compat, package/debian/control, package/debian/copyright, package/debian/docs, package/debian/postinst, package/debian/prerm, package/debian/rules, package/debian/watch:
+       scripts from Debian package
+
+2010-02-16  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * yacc.1: document -P and bison-extensions
+
+       * test/ftp.tab.c, test/grammar.tab.c, test/calc.tab.c, test/error.tab.c:
+       regen
+
+       * output.c: implement %pure-parser
+
+       * skeleton.c:
+       implement %pure-parser, like bison.  To help with this, changed the stack
+       variables, putting them into a struct.
+
+       * reader.c: implement %pure-parser
+
+       * defs.h: modified skeleton to support %pure-parser feature
+
+       * main.c: add -P option to set %pure-parser
+
+       * output.c:
+       make -r and -p options work together.  The -r option splits the generated
+       parser into code/table files; for this case we cannot use static data.
+       Also, we have to repeat the #define's used for prefix (-p) as well as the
+       redeclaration of yyparse().  Finally, allow any of the prefixed names to
+       be overridden, e.g., by passing a -D option to the compiler.  Make that
+       a little more readable by putting a blank line before each chunk.
+
+       * defs.h: add definitions for %pure-parser
+
+       * skeleton.c:
+       put blank line before/after the redeclaration of yyparse()
+
+       * output.c: allow for other program redefining yylex()
+
+       * skeleton.c:
+       split-off xdecls[] array, to move declaration of yyparse() after #define's
+
+       * defs.h: split-out xdecls[]
+
+       * VERSION: bump
+
+       * configure: regen
+
+       * aclocal.m4: add CF_REMOVE_DEFINE, needed by CF_ADD_CFLAGS
+
+       * aclocal.m4:
+       resync with my-autoconf CF_ADD_CFLAGS and CF_DISABLE_ECHO changes.
+
+2010-02-16  Ostap.Cherkashi
+
+       * skeleton.c: fix a memory leak in the generated skeleton
+
+2010-01-01  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/debian/source/format: scripts from Debian package
+
+2009-12-31  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.guess: 2009-12-30
+
+       * config.sub: 2009-12-31
+
+2009-10-27  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * VERSION: 20091027
+
+       * output.c, mkpar.c, defs.h, lalr.c, closure.c, graph.c, lr0.c, verbose.c, main.c, reader.c:
+       strict compiler warnings
+
+2009-10-26  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/ftp.tab.c, test/grammar.tab.c, test/calc.tab.c, test/error.tab.c:
+       resync
+
+       * main.c, defs.h: introduce some typedefs for portability, etc.
+
+       * makefile.in:
+       don't remove "*.log" in mostlyclean rule since it interferes with regression
+       script.
+
+       * configure: regen
+
+       * aclocal.m4: resync with my-autoconf
+
+2009-08-25  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.guess, config.sub: 2009-08-19
+
+2009-02-21  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * VERSION: bump
+
+       * output.c: restore "yylval" symbol, omitted in cleanup on 2008/8/25
+
+2008-12-26  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * configure: regen with autoconf-2.52 (patched)
+
+2008-12-25  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c, test/calc.tab.c:
+       regenerated
+
+2008-12-24  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * VERSION: bump
+
+       * skeleton.c:
+       remove ifdef-lint from goto yyerrlab, to quiet gcc warning
+
+2008-11-26  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * verbose.c, main.c, defs.h, mkpar.c, reader.c:
+       completed implementation of "%expect" (report by Perry E. Metzger).
+       add "%expect-rr", which is (unlike bison) allowable in LALR parsers.
+
+2008-11-24  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * closure.c, defs.h, error.c, graph.c, lalr.c, lr0.c, main.c, mkpar.c, output.c, reader.c, skeleton.c, symtab.c, verbose.c, warshall.c:
+       change indent-style (request by Perry E. Metzger)
+
+2008-08-27  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/calc.tab.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c:
+       better implementation of YYPARSE_PARAM, using YYPARSE_DECL() macro
+
+       * VERSION: bump
+
+       * skeleton.c:
+       better implementation of YYPARSE_PARAM, using YYPARSE_DECL() macro
+
+       * test/calc.tab.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c, skeleton.c:
+       change YYRECOVERING to YYRECOVERING(), for compatibility with other yacc's.
+
+       * configure: regen'd
+
+       * configure.in: add -Wwrite-strings to warnings
+
+       * test/ftp.tab.c, test/grammar.tab.c, test/calc.tab.c, test/error.tab.c:
+       add YYPARSE_PARAM and YYPARSE_PARAM_TYPE
+
+       * skeleton.c:
+       add YYPARSE_PARAM (bison) and YYPARSE_PARAM_TYPE (FreeBSD) features.
+
+       * main.c, defs.h, output.c, skeleton.c, symtab.c, error.c, reader.c:
+       fixes for gcc -Wwrite-strings
+
+       * test/calc.tab.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c:
+       generate the tables as static-const (this is an interface change)
+
+       * output.c: realign columns in start_table()
+
+       * output.c:
+       generate the tables as static-const (this is an interface change)
+
+       * output.c: reorder functions to eliminate forward-references
+
+       * test/calc.tab.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c:
+       remove 'register' keywords
+
+2008-08-26  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * warshall.c, verbose.c, symtab.c, skeleton.c, reader.c, output.c, mkpar.c, main.c, lr0.c, lalr.c, graph.c, error.c, closure.c:
+       remove 'register' keywords
+
+2008-08-25  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/ftp.tab.c: regen'd
+
+       * reader.c:
+       improve the left-curly fix by testing after blanks, to avoid having a
+       " {" at the beginning of a line.
+
+       * test/error.tab.c, test/grammar.tab.c: regen'd
+
+       * output.c:
+       move the remaining newline-counting into write_XXX functions.
+
+       * test/calc.tab.c: regen'd
+
+       * output.c:
+       simplify part of the output_file formatting using new functions, e.g.,
+       start_int_table(), output_newline().
+
+       * reader.c:
+       modify copy_action() to indent the first character, it if is is left-curly
+       brace.  That makes the output look more like the original, as well as makes
+       it simpler to edit (not confuse editors which look for a left-curly in the
+       first column as if it were the beginning of a function).
+
+       * skeleton.c: minor fixes to avoid gcc -Wconversion warnings
+
+       * output.c: align the #define's produced for "-p" option
+
+       * test/run_test.sh: use the "-p" option for better coverage.
+
+       * output.c: simplify output_prefix() with new define_prefixed()
+
+       * skeleton.c: include string.h, for memset()
+       change stack size to unsigned to fix gcc -Wconversion warnings.
+
+       * VERSION: bump to 2008/8/25
+
+       * makefile.in: add dependency on VERSION file.
+
+2008-08-24  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * VERSION: bump
+
+       * lalr.c: improved memory-leak checking by freeing data in includes[]
+
+       * test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c, test/calc.tab.c:
+       update to match skeleton-change
+
+       * configure: regen'd
+
+       * skeleton.c: Add fix for stack discussed
+               http://undeadly.org/cgi?action=article&sid=20080708155228
+       and applied
+               http://www.openbsd.org/cgi-bin/cvsweb/src/usr.bin/yacc/skeleton.c.diff?r1=1.28&r2=1.29
+
+       * aclocal.m4: resync with my-autoconf (no major changes)
+
+2008-07-24  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/pkgsrc/Makefile, package/pkgsrc/distinfo:
+       scripts from NetBSD pkgsrc, for test-builds
+
+2008-03-14  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.sub: update to 2008-03-08
+
+       * config.guess: update to 2008-03-12
+
+2007-05-09  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * main.c: close graph, verbose files if opened, on exit.
+
+       * main.c:
+       audit memory leaks - valgrind reported some memory still in use on exit.
+
+       * lalr.c, output.c, reader.c, mkpar.c, lr0.c:
+       add hook for auditing memory leaks
+
+       * defs.h: add hooks for auditing memory leaks
+
+       * configure: regen'd
+
+       * configure.in:
+       use CF_DISABLE_LEAKS, which combines --disable-leaks, --with-valgrind,
+       --with-dbmalloc and --with-dmalloc
+
+       * aclocal.m4: add CF_DISABLE_LEAKS and CF_WITH_VALGRIND
+
+       * aclocal.m4: improve version-checking in CF_GCC_VERSION
+       rework dbmalloc/dmalloc options using CF_NO_LEAKS_OPTION macro
+
+       * VERSION: 2007/5/9
+
+       * main.c: file_prefix did not always have a trailing null.
+
+2007-03-25  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * mkdirs.sh: improved version for "make -j"
+
+2006-12-22  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.guess: 2006/12/22
+
+2006-12-08  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.sub: 2006/12/08
+
+2005-08-13  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * main.c: add -V to usage message
+
+       * makefile.in: remove -t option from ctags
+
+       * VERSION: 2005/8/13
+
+2005-08-13  schmitz
+
+       * main.c: Sylvain Schmitz:
+       modify the '-o' option to work like bison's, which sets the file-prefix.
+
+2005-08-13  Matt.Kraai
+
+       * output.c:
+       Debian #322858 (don't close union_file, which contained data).
+       This feature is used in groff.
+
+2005-08-13  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * configure: regenerated
+
+       * aclocal.m4: improve checks for Intel compiler warnings
+
+2005-06-25  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.sub: 2005/6/2
+
+       * config.guess: 2005/5/27
+
+2005-05-05  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * defs.h: add a fallback for GCC_UNUSED
+
+2005-05-04  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * makefile.in: add "." to include-path to pickup config.h
+
+       * reader.c:
+       apply fix suggested by Steve Dum for end_rule() in Redhat Bugzilla #112617.
+
+       * output.c:
+       correct a limit check in pack_vector() - report/analysis by William Evans
+
+       * main.c:
+       exit after printing version.  Otherwise "yacc -V" will exit with an erro
+       after printing the usage message.
+
+       * test/calc.tab.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c:
+       regenerated after skeleton-changes
+
+       * skeleton.c: replace a few -1's with YYEMPTY
+
+       * skeleton.c:
+       delete yynewerror (no one uses it any more, and it just makes compiler warnings)
+
+       * skeleton.c: adapt yygrowstack() and related definitions from FreeBSD
+
+       * test/run_test.sh:
+       filter out lines with YYPATCH, since that will change with each update
+
+       * yacc.1: add -V option
+
+       * main.c: add -V option to print the version.
+       simplify option-parsing by moving the duplicate logic for setting flags into
+       new function setflag().
+
+       * skeleton.c:
+       move the actual definition of YYMAJOR and YYMINOR to defs.h (as numbers).
+       add YYPATCH here so it can be tested by applications.
+
+       * defs.h:
+       add macros to define VERSION in terms of the (numeric) YYMAJOR, YYMINOR and
+       YYPATCH symbols.
+
+       * lalr.c, lr0.c, mkpar.c, defs.h, closure.c, warshall.c, output.c, verbose.c, graph.c, reader.c, main.c, symtab.c:
+       reduce externs by making static the procedures that are not referenced outside
+       the module in which they are defined.
+
+       * makefile.in:
+       the VERSION file holds the patch-date.  Define YYPATCH, so this will be
+       compiled into the skeleton.
+
+       * VERSION: patch-level for byacc
+
+       * main.c:
+       add "-o" to usage message.  It is too long for a single line; rewrite usage()
+       to show one option per line.
+
+2005-05-03  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * main.c: add -o option, to work with scripts that assume bison.
+       simplify create_file_names() with a macro.
+       simplify done() with a macro.
+       adapt fix from FreeBSD for signal race, e.g., if done() is interrupted by
+       onintr(), do not flush output via exit(), but use _exit() instead.
+
+       * defs.h: remove unnecessary externs for main.c
+
+       * yacc.1: add -o option
+
+       * graph.c: remove unused parameter
+
+       * mkpar.c, defs.h, reader.c:
+       add support for "%expect", a bison feature from FreeBSD sources
+
+       * lr0.c, reader.c, main.c, skeleton.c, graph.c, symtab.c, closure.c, mkpar.c, lalr.c, error.c, warshall.c, verbose.c, output.c:
+       indent'd
+
+       * configure: regenerated for 2005/5/5
+
+       * aclocal.m4: miscellaneous updates (adds CF_INTEL_COMPILER)
+
+2005-04-27  schmitz
+
+       * defs.h, graph.c, lr0.c, main.c, makefile.in, reader.c, yacc.1:
+       Sylvain Schmitz <schmitz@i3s.unice.fr>:
+       add graphical output of the LALR(1) automaton for graphviz,
+       associated with command-line option `-g'
+
+2005-04-16  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.sub: 2005/2/10
+
+       * config.guess: 2005/3/24
+
+2005-04-13  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/pkgsrc/PLIST: scripts from NetBSD pkgsrc, for test-builds
+
+2005-03-21  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * package/pkgsrc/DESCR: scripts from NetBSD pkgsrc, for test-builds
+
+2004-03-28  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/calc.tab.c, test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c:
+       updates due to adding yyparse() prototype
+
+       * configure: RCS_BASE
+
+       * configure.in:
+       add AC_ARG_PROGRAM to make --program-prefix, etc., work.
+
+       * makefile.in: first cut of script to support --program-prefix
+
+       * configure.in:
+       reorder AC_INIT/AC_CONFIG_HEADER to make this "work" with autoconf 2.52
+
+       * makefile.in: modify so DESTDIR works
+
+       * makefile.in: use EXEEXT and OBJEXT
+
+       * configure.in: use CF_PROG_EXT
+       generate a config.h
+
+       * defs.h: make this use the generated config.h
+
+       * skeleton.c: add a forward-reference for yyparse()
+
+       * aclocal.m4: add CF_CHECK_CACHE, needed for CF_PROG_EXT
+
+       * yacc.1: remove the discussion of TMPDIR since it is obsolete
+
+       * skeleton.c: fix a couple of minor compiler-warnings in the skeleton
+
+       * defs.h: remove action_file_name, etc., since we use tmpfile() now.
+
+       * main.c:
+       use tmpfile() for opening the working files.  This quiets a warning
+       advising the use of mkstemp().
+
+       * output.c:
+       Do not close temporary-files here, since they are opened with tmpfile().
+       Just rewind them, and they're ready to read back the data stored in them.
+
+       * test/grammar.output, test/grammar.tab.c, test/grammar.tab.h: RCS_BASE
+
+       * makefile.in: turn on "make check" rule
+
+       * test/calc.output, test/run_test.sh, test/calc.tab.h: RCS_BASE
+
+       * test/ftp.tab.c: yyparse() is now yyparse(void)
+
+       * test/calc.tab.c: RCS_BASE
+
+       * test/error.tab.c: yyparse() is now yyparse(void)
+
+       * test/README: RCS_BASE
+
+       * yacc.1: various typography fixes prompted by Debian #100947
+
+       * aclocal.m4, makefile.in, configure.in: RCS_BASE
+
+       * README: updated to note that this is not the original
+
+2004-03-24  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/grammar.y: RCS_BASE
+
+2004-02-23  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.sub: RCS_BASE
+
+2004-02-17  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config.guess: RCS_BASE
+
+2003-11-29  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * install-sh: improved quoting
+
+2002-06-29  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * mkdirs.sh:
+       don't use character range, since some locales don't work as expected
+
+2001-06-22  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * install-sh: RCS_BASE
+
+2000-11-20  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/calc.y: RCS_BASE
+
+       * test/code_calc.y, test/pure_calc.y: copy of calc.y
+
+       * vmsbuild.com: original version
+
+2000-02-23  Thomas E. Dickey  <dickey@invisible-island.net>
+
+       * test/RCS, RCS: PERMIT FILE
+
+2000-02-14  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * main.c: fix for VMS port - making pathname for temp-file
+
+       * descrip.mms: original version
+
+2000-02-13  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * defs.h, verbose.c, reader.c, main.c, skeleton.c, warshall.c, symtab.c, closure.c, mkpar.c, lalr.c, lr0.c, output.c, error.c:
+       ansify
+
+1999-11-30  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * mkdirs.sh: RCS_BASE
+
+1995-01-01  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * config_h.in: RCS_BASE
+
+1993-12-23  unknown
+
+       * README.DOS, main.c: MSDOS-port
+
+1993-12-22  unknown
+
+       * reader.c, defs.h: MSDOS-port
+
+1993-03-02  unknown
+
+       * README: original version
+
+1993-02-22  unknown
+
+       * test/ftp.output, test/ftp.tab.c, test/ftp.tab.h, test/error.output, test/error.tab.c, test/error.tab.h:
+       RCS_BASE
+
+       * skeleton.c, warshall.c, main.c, output.c, reader.c, closure.c, NOTES:
+       original version
+
+1992-10-12  unknown
+
+       * yacc.1: original version
+
+1992-10-11  unknown
+
+       * defs.h: original version
+
+1991-01-20  unknown
+
+       * mkpar.c, verbose.c: original version
+
+1991-01-14  unknown
+
+       * lr0.c, Makefile, Makefile.old: original version
+
+1990-07-16  unknown
+
+       * NEW_FEATURES: original version
+
+1990-06-03  unknown
+
+       * ACKNOWLEDGEMENTS: original version
+
+1990-02-05  unknown
+
+       * symtab.c, lalr.c, error.c: original version
+
+1990-01-16  Thomas E. Dickey  <tom@invisible-island.net>
+
+       * test/code_error.y, test/pure_error.y: RCS_BASE
+
+1990-01-16  unknown
+
+       * test/error.y: RCS_BASE
+
+1989-11-22  unknown
+
+       * NO_WARRANTY: original version
+
+1989-09-23  unknown
+
+       * test/ftp.y: RCS_BASE
+
diff --git a/contrib/byacc/README b/contrib/byacc/README
new file mode 100644 (file)
index 0000000..391c43b
--- /dev/null
@@ -0,0 +1,29 @@
+-- $Id: README,v 1.2 2004/03/28 17:24:53 tom Exp $
+
+The original README is below.  I've updated this version of Berkeley Yacc
+to make it ANSI C compliant - Thomas Dickey
+
+-------------------------------------------------------------------------------
+    Berkeley Yacc is an LALR(1) parser generator.  Berkeley Yacc has been made
+as compatible as possible with AT&T Yacc.  Berkeley Yacc can accept any input
+specification that conforms to the AT&T Yacc documentation.  Specifications
+that take advantage of undocumented features of AT&T Yacc will probably be
+rejected.
+
+    Berkeley Yacc is distributed with no warranty whatever.  The code is certain
+to contain errors.  Neither the author nor any contributor takes responsibility
+for any consequences of its use.
+
+    Berkeley Yacc is in the public domain.  The data structures and algorithms
+used in Berkeley Yacc are all either taken from documents available to the
+general public or are inventions of the author.  Anyone may freely distribute
+source or binary forms of Berkeley Yacc whether unchanged or modified.
+Distributers may charge whatever fees they can obtain for Berkeley Yacc.
+Programs generated by Berkeley Yacc may be distributed freely.
+
+    Please report bugs to
+
+                       robert.corbett@eng.Sun.COM
+
+Include a small example if possible.  Please include the banner string from
+skeleton.c with the bug report.  Do not expect rapid responses.
diff --git a/contrib/byacc/README.DELETED b/contrib/byacc/README.DELETED
new file mode 100644 (file)
index 0000000..a302a27
--- /dev/null
@@ -0,0 +1,17 @@
+ACKNOWLEDGEMENTS
+Makefile.old
+NEW_FEATURES
+NOTES
+NO_WARRANTY
+aclocal.m4
+config.guess
+config.sub
+config_h.in
+configure
+configure.in
+descrip.mms
+install-sh
+makefile.in
+package/
+test/
+vmsbuild.com
diff --git a/contrib/byacc/VERSION b/contrib/byacc/VERSION
new file mode 100644 (file)
index 0000000..a633358
--- /dev/null
@@ -0,0 +1 @@
+20121003
diff --git a/contrib/byacc/closure.c b/contrib/byacc/closure.c
new file mode 100644 (file)
index 0000000..7573ff5
--- /dev/null
@@ -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
diff --git a/contrib/byacc/defs.h b/contrib/byacc/defs.h
new file mode 100644 (file)
index 0000000..4d1a407
--- /dev/null
@@ -0,0 +1,454 @@
+/* $Id: defs.h,v 1.37 2012/05/26 15:23:00 tom Exp $ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+#include <ctype.h>
+#include <stdio.h>
+
+#if defined(__cplusplus)       /* __cplusplus, etc. */
+#define class myClass
+#endif
+
+#define YYMAJOR 1
+#define YYMINOR 9
+
+#define CONCAT(first,second)    first #second
+#define CONCAT1(string,number)  CONCAT(string, number)
+#define CONCAT2(first,second)   #first "." #second
+
+#ifdef YYPATCH
+#define VSTRING(a,b) CONCAT2(a,b) CONCAT1(" ",YYPATCH)
+#else
+#define VSTRING(a,b) CONCAT2(a,b)
+#endif
+
+#define VERSION VSTRING(YYMAJOR, YYMINOR)
+
+/*  machine-dependent definitions                      */
+/*  the following definitions are for the Tahoe                */
+/*  they might have to be changed for other machines   */
+
+/*  MAXCHAR is the largest unsigned character value    */
+/*  MAXSHORT is the largest value of a C short         */
+/*  MINSHORT is the most negative value of a C short   */
+/*  MAXTABLE is the maximum table size                 */
+/*  BITS_PER_WORD is the number of bits in a C unsigned        */
+/*  WORDSIZE computes the number of words needed to    */
+/*     store n bits                                    */
+/*  BIT returns the value of the n-th bit starting     */
+/*     from r (0-indexed)                              */
+/*  SETBIT sets the n-th bit starting from r           */
+
+#define        MAXCHAR         255
+#define        MAXSHORT        32767
+#define MINSHORT       -32768
+#define MAXTABLE       32500
+#define BITS_PER_WORD  32
+#define        WORDSIZE(n)     (((n)+(BITS_PER_WORD-1))/BITS_PER_WORD)
+#define        BIT(r, n)       ((((r)[(n)>>5])>>((n)&31))&1)
+#define        SETBIT(r, n)    ((r)[(n)>>5]|=((unsigned)1<<((n)&31)))
+
+/*  character names  */
+
+#define        NUL             '\0'    /*  the null character  */
+#define        NEWLINE         '\n'    /*  line feed  */
+#define        SP              ' '     /*  space  */
+#define        BS              '\b'    /*  backspace  */
+#define        HT              '\t'    /*  horizontal tab  */
+#define        VT              '\013'  /*  vertical tab  */
+#define        CR              '\r'    /*  carriage return  */
+#define        FF              '\f'    /*  form feed  */
+#define        QUOTE           '\''    /*  single quote  */
+#define        DOUBLE_QUOTE    '\"'    /*  double quote  */
+#define        BACKSLASH       '\\'    /*  backslash  */
+
+#define UCH(c)          (unsigned char)(c)
+
+/* defines for constructing filenames */
+
+#if defined(VMS)
+#define CODE_SUFFIX    "_code.c"
+#define        DEFINES_SUFFIX  "_tab.h"
+#define        EXTERNS_SUFFIX  "_tab.i"
+#define        OUTPUT_SUFFIX   "_tab.c"
+#else
+#define CODE_SUFFIX    ".code.c"
+#define        DEFINES_SUFFIX  ".tab.h"
+#define        EXTERNS_SUFFIX  ".tab.i"
+#define        OUTPUT_SUFFIX   ".tab.c"
+#endif
+#define        VERBOSE_SUFFIX  ".output"
+#define GRAPH_SUFFIX    ".dot"
+
+/* keyword codes */
+
+#define TOKEN 0
+#define LEFT 1
+#define RIGHT 2
+#define NONASSOC 3
+#define MARK 4
+#define TEXT 5
+#define TYPE 6
+#define START 7
+#define UNION 8
+#define IDENT 9
+#define EXPECT 10
+#define EXPECT_RR 11
+#define PURE_PARSER 12
+#define PARSE_PARAM 13
+#define LEX_PARAM 14
+#define POSIX_YACC 15
+
+/*  symbol classes  */
+
+#define UNKNOWN 0
+#define TERM 1
+#define NONTERM 2
+
+/*  the undefined value  */
+
+#define UNDEFINED (-1)
+
+/*  action codes  */
+
+#define SHIFT 1
+#define REDUCE 2
+
+/*  character macros  */
+
+#define IS_IDENT(c)    (isalnum(c) || (c) == '_' || (c) == '.' || (c) == '$')
+#define        IS_OCTAL(c)     ((c) >= '0' && (c) <= '7')
+#define        NUMERIC_VALUE(c)        ((c) - '0')
+
+/*  symbol macros  */
+
+#define ISTOKEN(s)     ((s) < start_symbol)
+#define ISVAR(s)       ((s) >= start_symbol)
+
+/*  storage allocation macros  */
+
+#define CALLOC(k,n)    (calloc((size_t)(k),(size_t)(n)))
+#define        FREE(x)         (free((char*)(x)))
+#define MALLOC(n)      (malloc((size_t)(n)))
+#define TMALLOC(t,n)   ((t*) malloc((size_t)(n) * sizeof(t)))
+#define        NEW(t)          ((t*)allocate(sizeof(t)))
+#define        NEW2(n,t)       ((t*)allocate(((size_t)(n)*sizeof(t))))
+#define REALLOC(p,n)   (realloc((char*)(p),(size_t)(n)))
+#define TREALLOC(t,p,n)        ((t*)realloc((char*)(p), (size_t)(n) * sizeof(t)))
+
+#define DO_FREE(x)     if (x) { FREE(x); x = 0; }
+
+#define NO_SPACE(p)    if (p == 0) no_space(); assert(p != 0)
+
+/* messages */
+#define PLURAL(n) ((n) > 1 ? "s" : "")
+
+typedef char Assoc_t;
+typedef char Class_t;
+typedef short Index_t;
+typedef short Value_t;
+
+/*  the structure of a symbol table entry  */
+
+typedef struct bucket bucket;
+struct bucket
+{
+    struct bucket *link;
+    struct bucket *next;
+    char *name;
+    char *tag;
+    Value_t value;
+    Index_t index;
+    Value_t prec;
+    Class_t class;
+    Assoc_t assoc;
+};
+
+/*  the structure of the LR(0) state machine  */
+
+typedef struct core core;
+struct core
+{
+    struct core *next;
+    struct core *link;
+    Value_t number;
+    Value_t accessing_symbol;
+    Value_t nitems;
+    Value_t items[1];
+};
+
+/*  the structure used to record shifts  */
+
+typedef struct shifts shifts;
+struct shifts
+{
+    struct shifts *next;
+    Value_t number;
+    Value_t nshifts;
+    Value_t shift[1];
+};
+
+/*  the structure used to store reductions  */
+
+typedef struct reductions reductions;
+struct reductions
+{
+    struct reductions *next;
+    Value_t number;
+    Value_t nreds;
+    Value_t rules[1];
+};
+
+/*  the structure used to represent parser actions  */
+
+typedef struct action action;
+struct action
+{
+    struct action *next;
+    Value_t symbol;
+    Value_t number;
+    Value_t prec;
+    char action_code;
+    Assoc_t assoc;
+    char suppressed;
+};
+
+/*  the structure used to store parse/lex parameters  */
+typedef struct param param;
+struct param
+{
+    struct param *next;
+    char *name;                /* parameter name */
+    char *type;                /* everything before parameter name */
+    char *type2;       /* everything after parameter name */
+};
+
+/* global variables */
+
+extern char dflag;
+extern char gflag;
+extern char iflag;
+extern char lflag;
+extern char rflag;
+extern char sflag;
+extern char tflag;
+extern char vflag;
+extern const char *symbol_prefix;
+
+extern const char *myname;
+extern char *cptr;
+extern char *line;
+extern int lineno;
+extern int outline;
+extern int exit_code;
+extern int pure_parser;
+
+extern const char *const banner[];
+extern const char *const xdecls[];
+extern const char *const tables[];
+extern const char *const global_vars[];
+extern const char *const impure_vars[];
+extern const char *const hdr_defs[];
+extern const char *const hdr_vars[];
+extern const char *const body_1[];
+extern const char *const body_vars[];
+extern const char *const body_2[];
+extern const char *const body_3[];
+extern const char *const trailer[];
+extern const char *const trailer_2[];
+
+extern char *code_file_name;
+extern char *input_file_name;
+extern char *defines_file_name;
+extern char *externs_file_name;
+
+extern FILE *action_file;
+extern FILE *code_file;
+extern FILE *defines_file;
+extern FILE *externs_file;
+extern FILE *input_file;
+extern FILE *output_file;
+extern FILE *text_file;
+extern FILE *union_file;
+extern FILE *verbose_file;
+extern FILE *graph_file;
+
+extern int nitems;
+extern int nrules;
+extern int nsyms;
+extern int ntokens;
+extern int nvars;
+extern int ntags;
+
+extern char unionized;
+extern char line_format[];
+
+extern Value_t start_symbol;
+extern char **symbol_name;
+extern char **symbol_pname;
+extern Value_t *symbol_value;
+extern Value_t *symbol_prec;
+extern char *symbol_assoc;
+
+extern Value_t *ritem;
+extern Value_t *rlhs;
+extern Value_t *rrhs;
+extern Value_t *rprec;
+extern Assoc_t *rassoc;
+
+extern Value_t **derives;
+extern char *nullable;
+
+extern bucket *first_symbol;
+extern bucket *last_symbol;
+
+extern int nstates;
+extern core *first_state;
+extern shifts *first_shift;
+extern reductions *first_reduction;
+extern Value_t *accessing_symbol;
+extern core **state_table;
+extern shifts **shift_table;
+extern reductions **reduction_table;
+extern unsigned *LA;
+extern Value_t *LAruleno;
+extern Value_t *lookaheads;
+extern Value_t *goto_map;
+extern Value_t *from_state;
+extern Value_t *to_state;
+
+extern action **parser;
+extern int SRexpect;
+extern int RRexpect;
+extern int SRtotal;
+extern int RRtotal;
+extern Value_t *SRconflicts;
+extern Value_t *RRconflicts;
+extern Value_t *defred;
+extern Value_t *rules_used;
+extern Value_t nunused;
+extern Value_t final_state;
+
+extern Value_t *itemset;
+extern Value_t *itemsetend;
+extern unsigned *ruleset;
+
+extern param *lex_param;
+extern param *parse_param;
+
+/* global functions */
+
+extern bucket *lookup(const char *);
+extern bucket *make_bucket(const char *);
+
+#ifndef GCC_NORETURN
+#if defined(__dead2)
+#define GCC_NORETURN           __dead2
+#elif defined(__dead)
+#define GCC_NORETURN           __dead
+#else
+#define GCC_NORETURN           /* nothing */
+#endif
+#endif
+
+#ifndef GCC_UNUSED
+#if defined(__unused)
+#define GCC_UNUSED             __unused
+#else
+#define GCC_UNUSED             /* nothing */
+#endif
+#endif
+
+/* closure.c */
+extern void closure(Value_t * nucleus, int n);
+extern void finalize_closure(void);
+extern void set_first_derives(void);
+
+/* error.c */
+extern void default_action_warning(void);
+extern void dollar_error(int a_lineno, char *a_line, char *a_cptr) GCC_NORETURN;
+extern void dollar_warning(int a_lineno, int i);
+extern void fatal(const char *msg) GCC_NORETURN;
+extern void illegal_character(char *c_cptr) GCC_NORETURN;
+extern void illegal_tag(int t_lineno, char *t_line, char *t_cptr) GCC_NORETURN;
+extern void missing_brace(void) GCC_NORETURN;
+extern void no_grammar(void) GCC_NORETURN;
+extern void no_space(void) GCC_NORETURN;
+extern void open_error(const char *filename) GCC_NORETURN;
+extern void over_unionized(char *u_cptr) GCC_NORETURN;
+extern void prec_redeclared(void);
+extern void reprec_warning(char *s);
+extern void restarted_warning(void);
+extern void retyped_warning(char *s);
+extern void revalued_warning(char *s);
+extern void syntax_error(int st_lineno, char *st_line, char *st_cptr) GCC_NORETURN;
+extern void terminal_lhs(int s_lineno) GCC_NORETURN;
+extern void terminal_start(char *s) GCC_NORETURN;
+extern void tokenized_start(char *s) GCC_NORETURN;
+extern void undefined_goal(char *s) GCC_NORETURN;
+extern void undefined_symbol_warning(char *s);
+extern void unexpected_EOF(void) GCC_NORETURN;
+extern void unknown_rhs(int i) GCC_NORETURN;
+extern void unterminated_action(int a_lineno, char *a_line, char *a_cptr) GCC_NORETURN;
+extern void unterminated_comment(int c_lineno, char *c_line, char *c_cptr) GCC_NORETURN;
+extern void unterminated_string(int s_lineno, char *s_line, char *s_cptr) GCC_NORETURN;
+extern void unterminated_text(int t_lineno, char *t_line, char *t_cptr) GCC_NORETURN;
+extern void unterminated_union(int u_lineno, char *u_line, char *u_cptr) GCC_NORETURN;
+extern void untyped_lhs(void) GCC_NORETURN;
+extern void untyped_rhs(int i, char *s) GCC_NORETURN;
+extern void used_reserved(char *s) GCC_NORETURN;
+
+/* graph.c */
+extern void graph(void);
+
+/* lalr.c */
+extern void create_symbol_table(void);
+extern void free_symbol_table(void);
+extern void free_symbols(void);
+
+/* lalr.c */
+extern void lalr(void);
+
+/* lr0.c */
+extern void lr0(void);
+extern void show_cores(void);
+extern void show_ritems(void);
+extern void show_rrhs(void);
+extern void show_shifts(void);
+
+/* main.c */
+extern void *allocate(size_t n);
+extern void done(int k) GCC_NORETURN;
+
+/* mkpar.c */
+extern void free_parser(void);
+extern void make_parser(void);
+
+/* output.c */
+extern void output(void);
+
+/* reader.c */
+extern void reader(void);
+
+/* skeleton.c */
+extern void write_section(FILE * fp, const char *const section[]);
+
+/* verbose.c */
+extern void verbose(void);
+
+/* warshall.c */
+extern void reflexive_transitive_closure(unsigned *R, int n);
+
+#ifdef NO_LEAKS
+extern void lr0_leaks(void);
+extern void lalr_leaks(void);
+extern void mkpar_leaks(void);
+extern void output_leaks(void);
+extern void reader_leaks(void);
+#endif
diff --git a/contrib/byacc/error.c b/contrib/byacc/error.c
new file mode 100644 (file)
index 0000000..3bab31b
--- /dev/null
@@ -0,0 +1,288 @@
+/* $Id: error.c,v 1.9 2011/09/05 23:27:43 tom Exp $ */
+
+/* routines for printing error messages  */
+
+#include "defs.h"
+
+void
+fatal(const char *msg)
+{
+    fprintf(stderr, "%s: f - %s\n", myname, msg);
+    done(2);
+}
+
+void
+no_space(void)
+{
+    fprintf(stderr, "%s: f - out of space\n", myname);
+    done(2);
+}
+
+void
+open_error(const char *filename)
+{
+    fprintf(stderr, "%s: f - cannot open \"%s\"\n", myname, filename);
+    done(2);
+}
+
+void
+missing_brace(void)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", missing '}'\n",
+           myname, lineno, input_file_name);
+    done(1);
+}
+
+void
+unexpected_EOF(void)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", unexpected end-of-file\n",
+           myname, lineno, input_file_name);
+    done(1);
+}
+
+static void
+print_pos(char *st_line, char *st_cptr)
+{
+    char *s;
+
+    if (st_line == 0)
+       return;
+    for (s = st_line; *s != '\n'; ++s)
+    {
+       if (isprint(UCH(*s)) || *s == '\t')
+           putc(*s, stderr);
+       else
+           putc('?', stderr);
+    }
+    putc('\n', stderr);
+    for (s = st_line; s < st_cptr; ++s)
+    {
+       if (*s == '\t')
+           putc('\t', stderr);
+       else
+           putc(' ', stderr);
+    }
+    putc('^', stderr);
+    putc('\n', stderr);
+}
+
+void
+syntax_error(int st_lineno, char *st_line, char *st_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", syntax error\n",
+           myname, st_lineno, input_file_name);
+    print_pos(st_line, st_cptr);
+    done(1);
+}
+
+void
+unterminated_comment(int c_lineno, char *c_line, char *c_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", unmatched /*\n",
+           myname, c_lineno, input_file_name);
+    print_pos(c_line, c_cptr);
+    done(1);
+}
+
+void
+unterminated_string(int s_lineno, char *s_line, char *s_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", unterminated string\n",
+           myname, s_lineno, input_file_name);
+    print_pos(s_line, s_cptr);
+    done(1);
+}
+
+void
+unterminated_text(int t_lineno, char *t_line, char *t_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", unmatched %%{\n",
+           myname, t_lineno, input_file_name);
+    print_pos(t_line, t_cptr);
+    done(1);
+}
+
+void
+unterminated_union(int u_lineno, char *u_line, char *u_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", unterminated %%union \
+declaration\n", myname, u_lineno, input_file_name);
+    print_pos(u_line, u_cptr);
+    done(1);
+}
+
+void
+over_unionized(char *u_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", too many %%union \
+declarations\n", myname, lineno, input_file_name);
+    print_pos(line, u_cptr);
+    done(1);
+}
+
+void
+illegal_tag(int t_lineno, char *t_line, char *t_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", illegal tag\n",
+           myname, t_lineno, input_file_name);
+    print_pos(t_line, t_cptr);
+    done(1);
+}
+
+void
+illegal_character(char *c_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", illegal character\n",
+           myname, lineno, input_file_name);
+    print_pos(line, c_cptr);
+    done(1);
+}
+
+void
+used_reserved(char *s)
+{
+    fprintf(stderr,
+           "%s: e - line %d of \"%s\", illegal use of reserved symbol \
+%s\n", myname, lineno, input_file_name, s);
+    done(1);
+}
+
+void
+tokenized_start(char *s)
+{
+    fprintf(stderr,
+           "%s: e - line %d of \"%s\", the start symbol %s cannot be \
+declared to be a token\n", myname, lineno, input_file_name, s);
+    done(1);
+}
+
+void
+retyped_warning(char *s)
+{
+    fprintf(stderr, "%s: w - line %d of \"%s\", the type of %s has been \
+redeclared\n", myname, lineno, input_file_name, s);
+}
+
+void
+reprec_warning(char *s)
+{
+    fprintf(stderr,
+           "%s: w - line %d of \"%s\", the precedence of %s has been \
+redeclared\n", myname, lineno, input_file_name, s);
+}
+
+void
+revalued_warning(char *s)
+{
+    fprintf(stderr, "%s: w - line %d of \"%s\", the value of %s has been \
+redeclared\n", myname, lineno, input_file_name, s);
+}
+
+void
+terminal_start(char *s)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", the start symbol %s is a \
+token\n", myname, lineno, input_file_name, s);
+    done(1);
+}
+
+void
+restarted_warning(void)
+{
+    fprintf(stderr, "%s: w - line %d of \"%s\", the start symbol has been \
+redeclared\n", myname, lineno, input_file_name);
+}
+
+void
+no_grammar(void)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", no grammar has been \
+specified\n", myname, lineno, input_file_name);
+    done(1);
+}
+
+void
+terminal_lhs(int s_lineno)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", a token appears on the lhs \
+of a production\n", myname, s_lineno, input_file_name);
+    done(1);
+}
+
+void
+prec_redeclared(void)
+{
+    fprintf(stderr, "%s: w - line %d of  \"%s\", conflicting %%prec \
+specifiers\n", myname, lineno, input_file_name);
+}
+
+void
+unterminated_action(int a_lineno, char *a_line, char *a_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", unterminated action\n",
+           myname, a_lineno, input_file_name);
+    print_pos(a_line, a_cptr);
+    done(1);
+}
+
+void
+dollar_warning(int a_lineno, int i)
+{
+    fprintf(stderr, "%s: w - line %d of \"%s\", $%d references beyond the \
+end of the current rule\n", myname, a_lineno, input_file_name, i);
+}
+
+void
+dollar_error(int a_lineno, char *a_line, char *a_cptr)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", illegal $-name\n",
+           myname, a_lineno, input_file_name);
+    print_pos(a_line, a_cptr);
+    done(1);
+}
+
+void
+untyped_lhs(void)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", $$ is untyped\n",
+           myname, lineno, input_file_name);
+    done(1);
+}
+
+void
+untyped_rhs(int i, char *s)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", $%d (%s) is untyped\n",
+           myname, lineno, input_file_name, i, s);
+    done(1);
+}
+
+void
+unknown_rhs(int i)
+{
+    fprintf(stderr, "%s: e - line %d of \"%s\", $%d is untyped\n",
+           myname, lineno, input_file_name, i);
+    done(1);
+}
+
+void
+default_action_warning(void)
+{
+    fprintf(stderr,
+           "%s: w - line %d of \"%s\", the default action assigns an \
+undefined value to $$\n", myname, lineno, input_file_name);
+}
+
+void
+undefined_goal(char *s)
+{
+    fprintf(stderr, "%s: e - the start symbol %s is undefined\n", myname, s);
+    done(1);
+}
+
+void
+undefined_symbol_warning(char *s)
+{
+    fprintf(stderr, "%s: w - the symbol %s is undefined\n", myname, s);
+}
diff --git a/contrib/byacc/graph.c b/contrib/byacc/graph.c
new file mode 100644 (file)
index 0000000..2e31231
--- /dev/null
@@ -0,0 +1,112 @@
+/* $Id: graph.c,v 1.7 2009/10/27 09:25:20 tom Exp $ */
+
+#include "defs.h"
+
+static void graph_state(int stateno);
+static void graph_LA(int ruleno);
+
+static unsigned int larno;
+
+void
+graph(void)
+{
+    int i;
+    int j;
+    shifts *sp;
+    int sn;
+    int as;
+
+    if (!gflag)
+       return;
+
+    for (i = 0; i < nstates; ++i)
+    {
+       closure(state_table[i]->items, state_table[i]->nitems);
+       graph_state(i);
+    }
+
+    fprintf(graph_file, "\n\n");
+    for (i = 0; i < nstates; ++i)
+    {
+
+       sp = shift_table[i];
+       if (sp)
+           for (j = 0; j < sp->nshifts; ++j)
+           {
+               sn = sp->shift[j];
+               as = accessing_symbol[sn];
+               fprintf(graph_file,
+                       "\tq%d -> q%d [label=\"%s\"];\n",
+                       i, sn, symbol_pname[as]);
+           }
+    }
+
+    fprintf(graph_file, "}\n");
+
+    for (i = 0; i < nsyms; ++i)
+       FREE(symbol_pname[i]);
+    FREE(symbol_pname);
+}
+
+static void
+graph_state(int stateno)
+{
+    short *isp;
+    int rule;
+    short *sp;
+    short *sp1;
+
+    larno = (unsigned)lookaheads[stateno];
+    fprintf(graph_file, "\n\tq%d [label=\"%d:\\l", stateno, stateno);
+
+    for (isp = itemset; isp < itemsetend; isp++)
+    {
+       sp1 = sp = ritem + *isp;
+
+       while (*sp >= 0)
+           ++sp;
+       rule = -(*sp);
+       fprintf(graph_file, "  %s -> ", symbol_pname[rlhs[rule]]);
+
+       for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
+           fprintf(graph_file, "%s ", symbol_pname[*sp]);
+
+       putc('.', graph_file);
+
+       while (*sp >= 0)
+       {
+           fprintf(graph_file, " %s", symbol_pname[*sp]);
+           sp++;
+       }
+
+       if (*sp1 < 0)
+           graph_LA(-*sp1);
+
+       fprintf(graph_file, "\\l");
+    }
+    fprintf(graph_file, "\"];");
+}
+
+static void
+graph_LA(int ruleno)
+{
+    int i;
+    unsigned tokensetsize;
+    unsigned *rowp;
+
+    tokensetsize = (unsigned)WORDSIZE(ntokens);
+
+    if (ruleno == LAruleno[larno])
+    {
+       rowp = LA + larno * tokensetsize;
+
+       fprintf(graph_file, " { ");
+       for (i = ntokens - 1; i >= 0; i--)
+       {
+           if (BIT(rowp, i))
+               fprintf(graph_file, "%s ", symbol_pname[i]);
+       }
+       fprintf(graph_file, "}");
+       ++larno;
+    }
+}
diff --git a/contrib/byacc/lalr.c b/contrib/byacc/lalr.c
new file mode 100644 (file)
index 0000000..eb5e309
--- /dev/null
@@ -0,0 +1,655 @@
+/* $Id: lalr.c,v 1.9 2009/10/27 09:49:27 tom Exp $ */
+
+#include "defs.h"
+
+typedef struct shorts
+{
+    struct shorts *next;
+    Value_t value;
+}
+shorts;
+
+static Value_t map_goto(int state, int symbol);
+static Value_t **transpose(Value_t ** R, int n);
+static void add_lookback_edge(int stateno, int ruleno, int gotono);
+static void build_relations(void);
+static void compute_FOLLOWS(void);
+static void compute_lookaheads(void);
+static void digraph(Value_t ** relation);
+static void initialize_F(void);
+static void initialize_LA(void);
+static void set_accessing_symbol(void);
+static void set_goto_map(void);
+static void set_maxrhs(void);
+static void set_reduction_table(void);
+static void set_shift_table(void);
+static void set_state_table(void);
+static void traverse(int i);
+
+static int tokensetsize;
+Value_t *lookaheads;
+Value_t *LAruleno;
+unsigned *LA;
+Value_t *accessing_symbol;
+core **state_table;
+shifts **shift_table;
+reductions **reduction_table;
+Value_t *goto_map;
+Value_t *from_state;
+Value_t *to_state;
+
+static Value_t infinity;
+static int maxrhs;
+static int ngotos;
+static unsigned *F;
+static Value_t **includes;
+static shorts **lookback;
+static Value_t **R;
+static Value_t *INDEX;
+static Value_t *VERTICES;
+static Value_t top;
+
+void
+lalr(void)
+{
+    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();
+}
+
+static void
+set_state_table(void)
+{
+    core *sp;
+
+    state_table = NEW2(nstates, core *);
+    for (sp = first_state; sp; sp = sp->next)
+       state_table[sp->number] = sp;
+}
+
+static void
+set_accessing_symbol(void)
+{
+    core *sp;
+
+    accessing_symbol = NEW2(nstates, Value_t);
+    for (sp = first_state; sp; sp = sp->next)
+       accessing_symbol[sp->number] = sp->accessing_symbol;
+}
+
+static void
+set_shift_table(void)
+{
+    shifts *sp;
+
+    shift_table = NEW2(nstates, shifts *);
+    for (sp = first_shift; sp; sp = sp->next)
+       shift_table[sp->number] = sp;
+}
+
+static void
+set_reduction_table(void)
+{
+    reductions *rp;
+
+    reduction_table = NEW2(nstates, reductions *);
+    for (rp = first_reduction; rp; rp = rp->next)
+       reduction_table[rp->number] = rp;
+}
+
+static void
+set_maxrhs(void)
+{
+    Value_t *itemp;
+    Value_t *item_end;
+    int length;
+    int max;
+
+    length = 0;
+    max = 0;
+    item_end = ritem + nitems;
+    for (itemp = ritem; itemp < item_end; itemp++)
+    {
+       if (*itemp >= 0)
+       {
+           length++;
+       }
+       else
+       {
+           if (length > max)
+               max = length;
+           length = 0;
+       }
+    }
+
+    maxrhs = max;
+}
+
+static void
+initialize_LA(void)
+{
+    int i, j, k;
+    reductions *rp;
+
+    lookaheads = NEW2(nstates + 1, Value_t);
+
+    k = 0;
+    for (i = 0; i < nstates; i++)
+    {
+       lookaheads[i] = (Value_t) k;
+       rp = reduction_table[i];
+       if (rp)
+           k += rp->nreds;
+    }
+    lookaheads[nstates] = (Value_t) k;
+
+    LA = NEW2(k * tokensetsize, unsigned);
+    LAruleno = NEW2(k, Value_t);
+    lookback = NEW2(k, shorts *);
+
+    k = 0;
+    for (i = 0; i < nstates; i++)
+    {
+       rp = reduction_table[i];
+       if (rp)
+       {
+           for (j = 0; j < rp->nreds; j++)
+           {
+               LAruleno[k] = rp->rules[j];
+               k++;
+           }
+       }
+    }
+}
+
+static void
+set_goto_map(void)
+{
+    shifts *sp;
+    int i;
+    int symbol;
+    int k;
+    Value_t *temp_map;
+    Value_t state2;
+    Value_t state1;
+
+    goto_map = NEW2(nvars + 1, Value_t) - ntokens;
+    temp_map = NEW2(nvars + 1, Value_t) - ntokens;
+
+    ngotos = 0;
+    for (sp = first_shift; sp; sp = sp->next)
+    {
+       for (i = sp->nshifts - 1; i >= 0; i--)
+       {
+           symbol = accessing_symbol[sp->shift[i]];
+
+           if (ISTOKEN(symbol))
+               break;
+
+           if (ngotos == MAXSHORT)
+               fatal("too many gotos");
+
+           ngotos++;
+           goto_map[symbol]++;
+       }
+    }
+
+    k = 0;
+    for (i = ntokens; i < nsyms; i++)
+    {
+       temp_map[i] = (Value_t) k;
+       k += goto_map[i];
+    }
+
+    for (i = ntokens; i < nsyms; i++)
+       goto_map[i] = temp_map[i];
+
+    goto_map[nsyms] = (Value_t) ngotos;
+    temp_map[nsyms] = (Value_t) ngotos;
+
+    from_state = NEW2(ngotos, Value_t);
+    to_state = NEW2(ngotos, Value_t);
+
+    for (sp = first_shift; sp; sp = sp->next)
+    {
+       state1 = sp->number;
+       for (i = sp->nshifts - 1; i >= 0; i--)
+       {
+           state2 = sp->shift[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. */
+
+static Value_t
+map_goto(int state, int symbol)
+{
+    int high;
+    int low;
+    int middle;
+    int s;
+
+    low = goto_map[symbol];
+    high = goto_map[symbol + 1];
+
+    for (;;)
+    {
+       assert(low <= high);
+       middle = (low + high) >> 1;
+       s = from_state[middle];
+       if (s == state)
+           return (Value_t) (middle);
+       else if (s < state)
+           low = middle + 1;
+       else
+           high = middle - 1;
+    }
+}
+
+static void
+initialize_F(void)
+{
+    int i;
+    int j;
+    int k;
+    shifts *sp;
+    Value_t *edge;
+    unsigned *rowp;
+    Value_t *rp;
+    Value_t **reads;
+    int nedges;
+    int stateno;
+    int symbol;
+    int nwords;
+
+    nwords = ngotos * tokensetsize;
+    F = NEW2(nwords, unsigned);
+
+    reads = NEW2(ngotos, Value_t *);
+    edge = NEW2(ngotos + 1, Value_t);
+    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->shift[j]];
+               if (ISVAR(symbol))
+                   break;
+               SETBIT(rowp, symbol);
+           }
+
+           for (; j < k; j++)
+           {
+               symbol = accessing_symbol[sp->shift[j]];
+               if (nullable[symbol])
+                   edge[nedges++] = map_goto(stateno, symbol);
+           }
+
+           if (nedges)
+           {
+               reads[i] = rp = NEW2(nedges + 1, Value_t);
+
+               for (j = 0; j < nedges; j++)
+                   rp[j] = edge[j];
+
+               rp[nedges] = -1;
+               nedges = 0;
+           }
+       }
+
+       rowp += tokensetsize;
+    }
+
+    SETBIT(F, 0);
+    digraph(reads);
+
+    for (i = 0; i < ngotos; i++)
+    {
+       if (reads[i])
+           FREE(reads[i]);
+    }
+
+    FREE(reads);
+    FREE(edge);
+}
+
+static void
+build_relations(void)
+{
+    int i;
+    int j;
+    int k;
+    Value_t *rulep;
+    Value_t *rp;
+    shifts *sp;
+    int length;
+    int nedges;
+    int done_flag;
+    Value_t state1;
+    Value_t stateno;
+    int symbol1;
+    int symbol2;
+    Value_t *shortp;
+    Value_t *edge;
+    Value_t *states;
+    Value_t **new_includes;
+
+    includes = NEW2(ngotos, Value_t *);
+    edge = NEW2(ngotos + 1, Value_t);
+    states = NEW2(maxrhs + 1, Value_t);
+
+    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->shift[j];
+                   if (accessing_symbol[stateno] == symbol2)
+                       break;
+               }
+
+               states[length++] = stateno;
+           }
+
+           add_lookback_edge(stateno, *rulep, i);
+
+           length--;
+           done_flag = 0;
+           while (!done_flag)
+           {
+               done_flag = 1;
+               rp--;
+               if (ISVAR(*rp))
+               {
+                   stateno = states[--length];
+                   edge[nedges++] = map_goto(stateno, *rp);
+                   if (nullable[*rp] && length > 0)
+                       done_flag = 0;
+               }
+           }
+       }
+
+       if (nedges)
+       {
+           includes[i] = shortp = NEW2(nedges + 1, Value_t);
+           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);
+}
+
+static void
+add_lookback_edge(int stateno, int ruleno, int gotono)
+{
+    int i, k;
+    int found;
+    shorts *sp;
+
+    i = lookaheads[stateno];
+    k = lookaheads[stateno + 1];
+    found = 0;
+    while (!found && i < k)
+    {
+       if (LAruleno[i] == ruleno)
+           found = 1;
+       else
+           ++i;
+    }
+    assert(found);
+
+    sp = NEW(shorts);
+    sp->next = lookback[i];
+    sp->value = (Value_t) gotono;
+    lookback[i] = sp;
+}
+
+static Value_t **
+transpose(Value_t ** R2, int n)
+{
+    Value_t **new_R;
+    Value_t **temp_R;
+    Value_t *nedges;
+    Value_t *sp;
+    int i;
+    int k;
+
+    nedges = NEW2(n, Value_t);
+
+    for (i = 0; i < n; i++)
+    {
+       sp = R2[i];
+       if (sp)
+       {
+           while (*sp >= 0)
+               nedges[*sp++]++;
+       }
+    }
+
+    new_R = NEW2(n, Value_t *);
+    temp_R = NEW2(n, Value_t *);
+
+    for (i = 0; i < n; i++)
+    {
+       k = nedges[i];
+       if (k > 0)
+       {
+           sp = NEW2(k + 1, Value_t);
+           new_R[i] = sp;
+           temp_R[i] = sp;
+           sp[k] = -1;
+       }
+    }
+
+    FREE(nedges);
+
+    for (i = 0; i < n; i++)
+    {
+       sp = R2[i];
+       if (sp)
+       {
+           while (*sp >= 0)
+               *temp_R[*sp++]++ = (Value_t) i;
+       }
+    }
+
+    FREE(temp_R);
+
+    return (new_R);
+}
+
+static void
+compute_FOLLOWS(void)
+{
+    digraph(includes);
+}
+
+static void
+compute_lookaheads(void)
+{
+    int i, n;
+    unsigned *fp1, *fp2, *fp3;
+    shorts *sp, *next;
+    unsigned *rowp;
+
+    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++)
+       for (sp = lookback[i]; sp; sp = next)
+       {
+           next = sp->next;
+           FREE(sp);
+       }
+
+    FREE(lookback);
+    FREE(F);
+}
+
+static void
+digraph(Value_t ** relation)
+{
+    int i;
+
+    infinity = (Value_t) (ngotos + 2);
+    INDEX = NEW2(ngotos + 1, Value_t);
+    VERTICES = NEW2(ngotos + 1, Value_t);
+    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);
+}
+
+static void
+traverse(int i)
+{
+    unsigned *fp1;
+    unsigned *fp2;
+    unsigned *fp3;
+    int j;
+    Value_t *rp;
+
+    Value_t height;
+    unsigned *base;
+
+    VERTICES[++top] = (Value_t) 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++;
+       }
+    }
+}
+
+#ifdef NO_LEAKS
+void
+lalr_leaks(void)
+{
+    int i;
+
+    if (includes != 0)
+    {
+       for (i = 0; i < ngotos; i++)
+       {
+           free(includes[i]);
+       }
+       DO_FREE(includes);
+    }
+}
+#endif
diff --git a/contrib/byacc/lr0.c b/contrib/byacc/lr0.c
new file mode 100644 (file)
index 0000000..641f9f8
--- /dev/null
@@ -0,0 +1,599 @@
+/* $Id: lr0.c,v 1.13 2012/05/26 00:40:47 tom Exp $ */
+
+#include "defs.h"
+
+static core *new_state(int symbol);
+static Value_t get_state(int symbol);
+static void allocate_itemsets(void);
+static void allocate_storage(void);
+static void append_states(void);
+static void free_storage(void);
+static void generate_states(void);
+static void initialize_states(void);
+static void new_itemsets(void);
+static void save_reductions(void);
+static void save_shifts(void);
+static void set_derives(void);
+static void set_nullable(void);
+
+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 Value_t *redset;
+static Value_t *shiftset;
+
+static Value_t **kernel_base;
+static Value_t **kernel_end;
+static Value_t *kernel_items;
+
+static void
+allocate_itemsets(void)
+{
+    short *itemp;
+    short *item_end;
+    int symbol;
+    int i;
+    int count;
+    int max;
+    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 *);
+}
+
+static void
+allocate_storage(void)
+{
+    allocate_itemsets();
+    shiftset = NEW2(nsyms, short);
+    redset = NEW2(nrules + 1, short);
+    state_set = NEW2(nitems, core *);
+}
+
+static void
+append_states(void)
+{
+    int i;
+    int j;
+    Value_t 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);
+    }
+}
+
+static void
+free_storage(void)
+{
+    FREE(shift_symbol);
+    FREE(redset);
+    FREE(shiftset);
+    FREE(kernel_base);
+    FREE(kernel_end);
+    FREE(kernel_items);
+    FREE(state_set);
+}
+
+static void
+generate_states(void)
+{
+    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;
+    }
+
+    free_storage();
+}
+
+static Value_t
+get_state(int symbol)
+{
+    int key;
+    short *isp1;
+    short *isp2;
+    short *iend;
+    core *sp;
+    int found;
+    int n;
+
+#ifdef TRACE
+    fprintf(stderr, "Entering get_state(%d)\n", symbol);
+#endif
+
+    isp1 = kernel_base[symbol];
+    iend = kernel_end[symbol];
+    n = (int)(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);
+}
+
+static void
+initialize_states(void)
+{
+    unsigned i;
+    short *start_derives;
+    core *p;
+
+    start_derives = derives[start_symbol];
+    for (i = 0; start_derives[i] >= 0; ++i)
+       continue;
+
+    p = (core *)MALLOC(sizeof(core) + i * sizeof(short));
+    NO_SPACE(p);
+
+    p->next = 0;
+    p->link = 0;
+    p->number = 0;
+    p->accessing_symbol = 0;
+    p->nitems = (Value_t) 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;
+}
+
+static void
+new_itemsets(void)
+{
+    Value_t i;
+    int shiftcount;
+    short *isp;
+    short *ksp;
+    Value_t 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++ = (Value_t) (i + 1);
+           kernel_end[symbol] = ksp;
+       }
+    }
+
+    nshifts = shiftcount;
+}
+
+static core *
+new_state(int symbol)
+{
+    unsigned n;
+    core *p;
+    short *isp1;
+    short *isp2;
+    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 = (unsigned)(iend - isp1);
+
+    p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(short)));
+    p->accessing_symbol = (Value_t) symbol;
+    p->number = (Value_t) nstates;
+    p->nitems = (Value_t) n;
+
+    isp2 = p->items;
+    while (isp1 < iend)
+       *isp2++ = *isp1++;
+
+    last_state->next = p;
+    last_state = p;
+
+    nstates++;
+
+    return (p);
+}
+
+/* show_cores is used for debugging */
+
+void
+show_cores(void)
+{
+    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 is used for debugging */
+
+void
+show_ritems(void)
+{
+    int i;
+
+    for (i = 0; i < nitems; ++i)
+       printf("ritem[%d] = %d\n", i, ritem[i]);
+}
+
+/* show_rrhs is used for debugging */
+void
+show_rrhs(void)
+{
+    int i;
+
+    for (i = 0; i < nrules; ++i)
+       printf("rrhs[%d] = %d\n", i, rrhs[i]);
+}
+
+/* show_shifts is used for debugging */
+
+void
+show_shifts(void)
+{
+    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]);
+    }
+}
+
+static void
+save_shifts(void)
+{
+    shifts *p;
+    short *sp1;
+    short *sp2;
+    short *send;
+
+    p = (shifts *)allocate((sizeof(shifts) +
+                             (unsigned)(nshifts - 1) * sizeof(short)));
+
+    p->number = this_state->number;
+    p->nshifts = (Value_t) 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;
+    }
+}
+
+static void
+save_reductions(void)
+{
+    short *isp;
+    short *rp1;
+    short *rp2;
+    int item;
+    Value_t count;
+    reductions *p;
+    short *rend;
+
+    count = 0;
+    for (isp = itemset; isp < itemsetend; isp++)
+    {
+       item = ritem[*isp];
+       if (item < 0)
+       {
+           redset[count++] = (Value_t) - item;
+       }
+    }
+
+    if (count)
+    {
+       p = (reductions *)allocate((sizeof(reductions) +
+                                     (unsigned)(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;
+       }
+    }
+}
+
+static void
+set_derives(void)
+{
+    Value_t i, k;
+    int lhs;
+    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
+}
+
+#ifdef DEBUG
+void
+print_derives(void)
+{
+    int i;
+    short *sp;
+
+    printf("\nDERIVES\n\n");
+
+    for (i = start_symbol; i < nsyms; i++)
+    {
+       printf("%s derives ", symbol_name[i]);
+       for (sp = derives[i]; *sp >= 0; sp++)
+       {
+           printf("  %d", *sp);
+       }
+       putchar('\n');
+    }
+
+    putchar('\n');
+}
+#endif
+
+static void
+set_nullable(void)
+{
+    int i, j;
+    int empty;
+    int done_flag;
+
+    nullable = TMALLOC(char, nsyms);
+    NO_SPACE(nullable);
+
+    for (i = 0; i < nsyms; ++i)
+       nullable[i] = 0;
+
+    done_flag = 0;
+    while (!done_flag)
+    {
+       done_flag = 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_flag = 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
+}
+
+void
+lr0(void)
+{
+    set_derives();
+    set_nullable();
+    generate_states();
+}
+
+#ifdef NO_LEAKS
+void
+lr0_leaks(void)
+{
+    DO_FREE(derives[start_symbol]);
+    DO_FREE(derives);
+    DO_FREE(nullable);
+}
+#endif
diff --git a/contrib/byacc/main.c b/contrib/byacc/main.c
new file mode 100644 (file)
index 0000000..816e154
--- /dev/null
@@ -0,0 +1,660 @@
+/* $Id: main.c,v 1.40 2012/09/29 13:11:00 Adrian.Bunk Exp $ */
+
+#include <signal.h>
+#include <unistd.h>            /* for _exit() */
+
+#include "defs.h"
+
+#ifdef HAVE_MKSTEMP
+# define USE_MKSTEMP 1
+#elif defined(HAVE_FCNTL_H)
+# define USE_MKSTEMP 1
+# include <fcntl.h>            /* for open(), O_EXCL, etc. */
+#else
+# define USE_MKSTEMP 0
+#endif
+
+#if USE_MKSTEMP
+#include <sys/types.h>
+#include <sys/stat.h>
+
+typedef struct _my_tmpfiles
+{
+    struct _my_tmpfiles *next;
+    char *name;
+}
+MY_TMPFILES;
+
+static MY_TMPFILES *my_tmpfiles;
+#endif /* USE_MKSTEMP */
+
+char dflag;
+char gflag;
+char iflag;
+char lflag;
+static char oflag;
+char rflag;
+char sflag;
+char tflag;
+char vflag;
+
+const char *symbol_prefix;
+const char *myname = "yacc";
+
+int lineno;
+int outline;
+
+static char empty_string[] = "";
+static char default_file_prefix[] = "y";
+
+static char *file_prefix = default_file_prefix;
+
+char *code_file_name;
+char *input_file_name = empty_string;
+char *defines_file_name;
+char *externs_file_name;
+
+static char *graph_file_name;
+static char *output_file_name;
+static char *verbose_file_name;
+
+FILE *action_file;     /*  a temp file, used to save actions associated    */
+                       /*  with rules until the parser is written          */
+FILE *code_file;       /*  y.code.c (used when the -r option is specified) */
+FILE *defines_file;    /*  y.tab.h                                         */
+FILE *externs_file;    /*  y.tab.i                                         */
+FILE *input_file;      /*  the input file                                  */
+FILE *output_file;     /*  y.tab.c                                         */
+FILE *text_file;       /*  a temp file, used to save text until all        */
+                       /*  symbols have been defined                       */
+FILE *union_file;      /*  a temp file, used to save the union             */
+                       /*  definition until all symbol have been           */
+                       /*  defined                                         */
+FILE *verbose_file;    /*  y.output                                        */
+FILE *graph_file;      /*  y.dot                                           */
+
+int nitems;
+int nrules;
+int nsyms;
+int ntokens;
+int nvars;
+
+Value_t start_symbol;
+char **symbol_name;
+char **symbol_pname;
+Value_t *symbol_value;
+short *symbol_prec;
+char *symbol_assoc;
+
+int pure_parser;
+int exit_code;
+
+Value_t *ritem;
+Value_t *rlhs;
+Value_t *rrhs;
+Value_t *rprec;
+Assoc_t *rassoc;
+Value_t **derives;
+char *nullable;
+
+/*
+ * Since fclose() is called via the signal handler, it might die.  Don't loop
+ * if there is a problem closing a file.
+ */
+#define DO_CLOSE(fp) \
+       if (fp != 0) { \
+           FILE *use = fp; \
+           fp = 0; \
+           fclose(use); \
+       }
+
+static int got_intr = 0;
+
+void
+done(int k)
+{
+    DO_CLOSE(input_file);
+    DO_CLOSE(output_file);
+
+    DO_CLOSE(action_file);
+    DO_CLOSE(defines_file);
+    DO_CLOSE(graph_file);
+    DO_CLOSE(text_file);
+    DO_CLOSE(union_file);
+    DO_CLOSE(verbose_file);
+
+    if (got_intr)
+       _exit(EXIT_FAILURE);
+
+#ifdef NO_LEAKS
+    if (rflag)
+       DO_FREE(code_file_name);
+
+    if (dflag)
+       DO_FREE(defines_file_name);
+
+    if (iflag)
+       DO_FREE(externs_file_name);
+
+    if (oflag)
+       DO_FREE(output_file_name);
+
+    if (vflag)
+       DO_FREE(verbose_file_name);
+
+    if (gflag)
+       DO_FREE(graph_file_name);
+
+    lr0_leaks();
+    lalr_leaks();
+    mkpar_leaks();
+    output_leaks();
+    reader_leaks();
+#endif
+
+    if (rflag)
+       DO_CLOSE(code_file);
+
+    exit(k);
+}
+
+static void
+onintr(int sig GCC_UNUSED)
+{
+    got_intr = 1;
+    done(EXIT_FAILURE);
+}
+
+static void
+set_signals(void)
+{
+#ifdef SIGINT
+    if (signal(SIGINT, SIG_IGN) != SIG_IGN)
+       signal(SIGINT, onintr);
+#endif
+#ifdef SIGTERM
+    if (signal(SIGTERM, SIG_IGN) != SIG_IGN)
+       signal(SIGTERM, onintr);
+#endif
+#ifdef SIGHUP
+    if (signal(SIGHUP, SIG_IGN) != SIG_IGN)
+       signal(SIGHUP, onintr);
+#endif
+}
+
+static void
+usage(void)
+{
+    static const char *msg[] =
+    {
+       ""
+       ,"Options:"
+       ,"  -b file_prefix        set filename prefix (default \"y.\")"
+       ,"  -d                    write definitions (y.tab.h)"
+       ,"  -i                    write interface (y.tab.i)"
+       ,"  -g                    write a graphical description"
+       ,"  -l                    suppress #line directives"
+       ,"  -o output_file        (default \"y.tab.c\")"
+       ,"  -p symbol_prefix      set symbol prefix (default \"yy\")"
+       ,"  -P                    create a reentrant parser, e.g., \"%pure-parser\""
+       ,"  -r                    produce separate code and table files (y.code.c)"
+       ,"  -s                    suppress #define's for quoted names in %token lines"
+       ,"  -t                    add debugging support"
+       ,"  -v                    write description (y.output)"
+       ,"  -V                    show version information and exit"
+    };
+    unsigned n;
+
+    fflush(stdout);
+    fprintf(stderr, "Usage: %s [options] filename\n", myname);
+    for (n = 0; n < sizeof(msg) / sizeof(msg[0]); ++n)
+       fprintf(stderr, "%s\n", msg[n]);
+
+    exit(1);
+}
+
+static void
+setflag(int ch)
+{
+    switch (ch)
+    {
+    case 'd':
+       dflag = 1;
+       break;
+
+    case 'g':
+       gflag = 1;
+       break;
+
+    case 'i':
+       iflag = 1;
+       break;
+
+    case 'l':
+       lflag = 1;
+       break;
+
+    case 'P':
+       pure_parser = 1;
+       break;
+
+    case 'r':
+       rflag = 1;
+       break;
+
+    case 's':
+       sflag = 1;
+       break;
+
+    case 't':
+       tflag = 1;
+       break;
+
+    case 'v':
+       vflag = 1;
+       break;
+
+    case 'V':
+       printf("%s - %s\n", myname, VERSION);
+       exit(EXIT_SUCCESS);
+
+    case 'y':
+       /* noop for bison compatibility. byacc is already designed to be posix
+        * yacc compatible. */
+       break;
+
+    default:
+       usage();
+    }
+}
+
+static void
+getargs(int argc, char *argv[])
+{
+    int i;
+    char *s;
+    int ch;
+
+    if (argc > 0)
+       myname = argv[0];
+
+    for (i = 1; i < argc; ++i)
+    {
+       s = argv[i];
+       if (*s != '-')
+           break;
+       switch (ch = *++s)
+       {
+       case '\0':
+           input_file = stdin;
+           if (i + 1 < argc)
+               usage();
+           return;
+
+       case '-':
+           ++i;
+           goto no_more_options;
+
+       case 'b':
+           if (*++s)
+               file_prefix = s;
+           else if (++i < argc)
+               file_prefix = argv[i];
+           else
+               usage();
+           continue;
+
+       case 'o':
+           if (*++s)
+               output_file_name = s;
+           else if (++i < argc)
+               output_file_name = argv[i];
+           else
+               usage();
+           continue;
+
+       case 'p':
+           if (*++s)
+               symbol_prefix = s;
+           else if (++i < argc)
+               symbol_prefix = argv[i];
+           else
+               usage();
+           continue;
+
+       default:
+           setflag(ch);
+           break;
+       }
+
+       for (;;)
+       {
+           switch (ch = *++s)
+           {
+           case '\0':
+               goto end_of_option;
+
+           default:
+               setflag(ch);
+               break;
+           }
+       }
+      end_of_option:;
+    }
+
+  no_more_options:;
+    if (i + 1 != argc)
+       usage();
+    input_file_name = argv[i];
+}
+
+void *
+allocate(size_t n)
+{
+    void *p;
+
+    p = NULL;
+    if (n)
+    {
+       p = CALLOC(1, n);
+       NO_SPACE(p);
+    }
+    return (p);
+}
+
+#define CREATE_FILE_NAME(dest, suffix) \
+       dest = TMALLOC(char, len + strlen(suffix) + 1); \
+       NO_SPACE(dest); \
+       strcpy(dest, file_prefix); \
+       strcpy(dest + len, suffix)
+
+static void
+create_file_names(void)
+{
+    size_t len;
+    const char *defines_suffix;
+    const char *externs_suffix;
+    char *prefix;
+
+    prefix = NULL;
+    defines_suffix = DEFINES_SUFFIX;
+    externs_suffix = EXTERNS_SUFFIX;
+
+    /* compute the file_prefix from the user provided output_file_name */
+    if (output_file_name != 0)
+    {
+       if (!(prefix = strstr(output_file_name, ".tab.c"))
+           && (prefix = strstr(output_file_name, ".c")))
+       {
+           defines_suffix = ".h";
+           externs_suffix = ".i";
+       }
+    }
+
+    if (prefix != NULL)
+    {
+       len = (size_t) (prefix - output_file_name);
+       file_prefix = TMALLOC(char, len + 1);
+       NO_SPACE(file_prefix);
+       strncpy(file_prefix, output_file_name, len)[len] = 0;
+    }
+    else
+       len = strlen(file_prefix);
+
+    /* if "-o filename" was not given */
+    if (output_file_name == 0)
+    {
+       oflag = 1;
+       CREATE_FILE_NAME(output_file_name, OUTPUT_SUFFIX);
+    }
+
+    if (rflag)
+    {
+       CREATE_FILE_NAME(code_file_name, CODE_SUFFIX);
+    }
+    else
+       code_file_name = output_file_name;
+
+    if (dflag)
+    {
+       CREATE_FILE_NAME(defines_file_name, defines_suffix);
+    }
+
+    if (iflag)
+    {
+       CREATE_FILE_NAME(externs_file_name, externs_suffix);
+    }
+
+    if (vflag)
+    {
+       CREATE_FILE_NAME(verbose_file_name, VERBOSE_SUFFIX);
+    }
+
+    if (gflag)
+    {
+       CREATE_FILE_NAME(graph_file_name, GRAPH_SUFFIX);
+    }
+
+    if (prefix != NULL)
+    {
+       FREE(file_prefix);
+    }
+}
+
+#if USE_MKSTEMP
+static void
+close_tmpfiles(void)
+{
+    while (my_tmpfiles != 0)
+    {
+       MY_TMPFILES *next = my_tmpfiles->next;
+
+       chmod(my_tmpfiles->name, 0644);
+       unlink(my_tmpfiles->name);
+
+       free(my_tmpfiles->name);
+       free(my_tmpfiles);
+
+       my_tmpfiles = next;
+    }
+}
+
+#ifndef HAVE_MKSTEMP
+static int
+my_mkstemp(char *temp)
+{
+    int fd;
+    char *dname;
+    char *fname;
+    char *name;
+
+    /*
+     * Split-up to use tempnam, rather than tmpnam; the latter (like
+     * mkstemp) is unusable on Windows.
+     */
+    if ((fname = strrchr(temp, '/')) != 0)
+    {
+       dname = strdup(temp);
+       dname[++fname - temp] = '\0';
+    }
+    else
+    {
+       dname = 0;
+       fname = temp;
+    }
+    if ((name = tempnam(dname, fname)) != 0)
+    {
+       fd = open(name, O_CREAT | O_EXCL | O_RDWR);
+       strcpy(temp, name);
+    }
+    else
+    {
+       fd = -1;
+    }
+
+    if (dname != 0)
+       free(dname);
+
+    return fd;
+}
+#define mkstemp(s) my_mkstemp(s)
+#endif
+
+#endif
+
+/*
+ * tmpfile() should be adequate, except that it may require special privileges
+ * to use, e.g., MinGW and Windows 7 where it tries to use the root directory.
+ */
+static FILE *
+open_tmpfile(const char *label)
+{
+    FILE *result;
+#if USE_MKSTEMP
+    int fd;
+    const char *tmpdir;
+    char *name;
+    const char *mark;
+
+    if ((tmpdir = getenv("TMPDIR")) == 0 || access(tmpdir, W_OK) != 0)
+    {
+#ifdef P_tmpdir
+       tmpdir = P_tmpdir;
+#else
+       tmpdir = "/tmp";
+#endif
+       if (access(tmpdir, W_OK) != 0)
+           tmpdir = ".";
+    }
+
+    name = malloc(strlen(tmpdir) + 10 + strlen(label));
+
+    result = 0;
+    if (name != 0)
+    {
+       if ((mark = strrchr(label, '_')) == 0)
+           mark = label + strlen(label);
+
+       sprintf(name, "%s/%.*sXXXXXX", tmpdir, (int)(mark - label), label);
+       fd = mkstemp(name);
+       if (fd >= 0)
+       {
+           result = fdopen(fd, "w+");
+           if (result != 0)
+           {
+               MY_TMPFILES *item;
+
+               if (my_tmpfiles == 0)
+               {
+                   atexit(close_tmpfiles);
+               }
+
+               item = NEW(MY_TMPFILES);
+               NO_SPACE(item);
+
+               item->name = name;
+               NO_SPACE(item->name);
+
+               item->next = my_tmpfiles;
+               my_tmpfiles = item;
+           }
+       }
+    }
+#else
+    result = tmpfile();
+#endif
+
+    if (result == 0)
+       open_error(label);
+    return result;
+}
+
+static void
+open_files(void)
+{
+    create_file_names();
+
+    if (input_file == 0)
+    {
+       input_file = fopen(input_file_name, "r");
+       if (input_file == 0)
+           open_error(input_file_name);
+    }
+
+    action_file = open_tmpfile("action_file");
+    text_file = open_tmpfile("text_file");
+
+    if (vflag)
+    {
+       verbose_file = fopen(verbose_file_name, "w");
+       if (verbose_file == 0)
+           open_error(verbose_file_name);
+    }
+
+    if (gflag)
+    {
+       graph_file = fopen(graph_file_name, "w");
+       if (graph_file == 0)
+           open_error(graph_file_name);
+       fprintf(graph_file, "digraph %s {\n", file_prefix);
+       fprintf(graph_file, "\tedge [fontsize=10];\n");
+       fprintf(graph_file, "\tnode [shape=box,fontsize=10];\n");
+       fprintf(graph_file, "\torientation=landscape;\n");
+       fprintf(graph_file, "\trankdir=LR;\n");
+       fprintf(graph_file, "\t/*\n");
+       fprintf(graph_file, "\tmargin=0.2;\n");
+       fprintf(graph_file, "\tpage=\"8.27,11.69\"; // for A4 printing\n");
+       fprintf(graph_file, "\tratio=auto;\n");
+       fprintf(graph_file, "\t*/\n");
+    }
+
+    if (dflag)
+    {
+       defines_file = fopen(defines_file_name, "w");
+       if (defines_file == 0)
+           open_error(defines_file_name);
+       union_file = open_tmpfile("union_file");
+    }
+
+    if (iflag)
+    {
+       externs_file = fopen(externs_file_name, "w");
+       if (externs_file == 0)
+           open_error(externs_file_name);
+    }
+
+    output_file = fopen(output_file_name, "w");
+    if (output_file == 0)
+       open_error(output_file_name);
+
+    if (rflag)
+    {
+       code_file = fopen(code_file_name, "w");
+       if (code_file == 0)
+           open_error(code_file_name);
+    }
+    else
+       code_file = output_file;
+}
+
+int
+main(int argc, char *argv[])
+{
+    SRexpect = -1;
+    RRexpect = -1;
+    exit_code = EXIT_SUCCESS;
+
+    set_signals();
+    getargs(argc, argv);
+    open_files();
+    reader();
+    lr0();
+    lalr();
+    make_parser();
+    graph();
+    finalize_closure();
+    verbose();
+    output();
+    done(exit_code);
+    /*NOTREACHED */
+}
diff --git a/contrib/byacc/mkpar.c b/contrib/byacc/mkpar.c
new file mode 100644 (file)
index 0000000..b2e36ab
--- /dev/null
@@ -0,0 +1,392 @@
+/* $Id: mkpar.c,v 1.12 2012/05/26 00:42:18 tom Exp $ */
+
+#include "defs.h"
+
+static action *add_reduce(action *actions, int ruleno, int symbol);
+static action *add_reductions(int stateno, action *actions);
+static action *get_shifts(int stateno);
+static action *parse_actions(int stateno);
+static int sole_reduction(int stateno);
+static void defreds(void);
+static void find_final_state(void);
+static void free_action_row(action *p);
+static void remove_conflicts(void);
+static void total_conflicts(void);
+static void unused_rules(void);
+
+action **parser;
+
+int SRexpect;
+int RRexpect;
+
+int SRtotal;
+int RRtotal;
+
+Value_t *SRconflicts;
+Value_t *RRconflicts;
+Value_t *defred;
+Value_t *rules_used;
+Value_t nunused;
+Value_t final_state;
+
+static Value_t SRcount;
+static Value_t RRcount;
+
+void
+make_parser(void)
+{
+    int i;
+
+    parser = NEW2(nstates, action *);
+    for (i = 0; i < nstates; i++)
+       parser[i] = parse_actions(i);
+
+    find_final_state();
+    remove_conflicts();
+    unused_rules();
+    if (SRtotal + RRtotal > 0)
+       total_conflicts();
+    defreds();
+}
+
+static action *
+parse_actions(int stateno)
+{
+    action *actions;
+
+    actions = get_shifts(stateno);
+    actions = add_reductions(stateno, actions);
+    return (actions);
+}
+
+static action *
+get_shifts(int stateno)
+{
+    action *actions, *temp;
+    shifts *sp;
+    Value_t *to_state2;
+    Value_t i, k;
+    Value_t symbol;
+
+    actions = 0;
+    sp = shift_table[stateno];
+    if (sp)
+    {
+       to_state2 = sp->shift;
+       for (i = (Value_t) (sp->nshifts - 1); i >= 0; i--)
+       {
+           k = to_state2[i];
+           symbol = accessing_symbol[k];
+           if (ISTOKEN(symbol))
+           {
+               temp = NEW(action);
+               temp->next = actions;
+               temp->symbol = symbol;
+               temp->number = k;
+               temp->prec = symbol_prec[symbol];
+               temp->action_code = SHIFT;
+               temp->assoc = symbol_assoc[symbol];
+               actions = temp;
+           }
+       }
+    }
+    return (actions);
+}
+
+static action *
+add_reductions(int stateno, action *actions)
+{
+    int i, j, m, n;
+    int ruleno, tokensetsize;
+    unsigned *rowp;
+
+    tokensetsize = WORDSIZE(ntokens);
+    m = lookaheads[stateno];
+    n = lookaheads[stateno + 1];
+    for (i = m; i < n; i++)
+    {
+       ruleno = LAruleno[i];
+       rowp = LA + i * tokensetsize;
+       for (j = ntokens - 1; j >= 0; j--)
+       {
+           if (BIT(rowp, j))
+               actions = add_reduce(actions, ruleno, j);
+       }
+    }
+    return (actions);
+}
+
+static action *
+add_reduce(action *actions,
+          int ruleno,
+          int symbol)
+{
+    action *temp, *prev, *next;
+
+    prev = 0;
+    for (next = actions; next && next->symbol < symbol; next = next->next)
+       prev = next;
+
+    while (next && next->symbol == symbol && next->action_code == SHIFT)
+    {
+       prev = next;
+       next = next->next;
+    }
+
+    while (next && next->symbol == symbol &&
+          next->action_code == REDUCE && next->number < ruleno)
+    {
+       prev = next;
+       next = next->next;
+    }
+
+    temp = NEW(action);
+    temp->next = next;
+    temp->symbol = (Value_t) symbol;
+    temp->number = (Value_t) ruleno;
+    temp->prec = rprec[ruleno];
+    temp->action_code = REDUCE;
+    temp->assoc = rassoc[ruleno];
+
+    if (prev)
+       prev->next = temp;
+    else
+       actions = temp;
+
+    return (actions);
+}
+
+static void
+find_final_state(void)
+{
+    int goal, i;
+    Value_t *to_state2;
+    shifts *p;
+
+    p = shift_table[0];
+    to_state2 = p->shift;
+    goal = ritem[1];
+    for (i = p->nshifts - 1; i >= 0; --i)
+    {
+       final_state = to_state2[i];
+       if (accessing_symbol[final_state] == goal)
+           break;
+    }
+}
+
+static void
+unused_rules(void)
+{
+    int i;
+    action *p;
+
+    rules_used = TMALLOC(Value_t, nrules);
+    NO_SPACE(rules_used);
+
+    for (i = 0; i < nrules; ++i)
+       rules_used[i] = 0;
+
+    for (i = 0; i < nstates; ++i)
+    {
+       for (p = parser[i]; p; p = p->next)
+       {
+           if (p->action_code == REDUCE && p->suppressed == 0)
+               rules_used[p->number] = 1;
+       }
+    }
+
+    nunused = 0;
+    for (i = 3; i < nrules; ++i)
+       if (!rules_used[i])
+           ++nunused;
+
+    if (nunused)
+    {
+       if (nunused == 1)
+           fprintf(stderr, "%s: 1 rule never reduced\n", myname);
+       else
+           fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
+    }
+}
+
+static void
+remove_conflicts(void)
+{
+    int i;
+    int symbol;
+    action *p, *pref = 0;
+
+    SRtotal = 0;
+    RRtotal = 0;
+    SRconflicts = NEW2(nstates, Value_t);
+    RRconflicts = NEW2(nstates, Value_t);
+    for (i = 0; i < nstates; i++)
+    {
+       SRcount = 0;
+       RRcount = 0;
+       symbol = -1;
+       for (p = parser[i]; p; p = p->next)
+       {
+           if (p->symbol != symbol)
+           {
+               pref = p;
+               symbol = p->symbol;
+           }
+           else if (i == final_state && symbol == 0)
+           {
+               SRcount++;
+               p->suppressed = 1;
+           }
+           else if (pref != 0 && pref->action_code == SHIFT)
+           {
+               if (pref->prec > 0 && p->prec > 0)
+               {
+                   if (pref->prec < p->prec)
+                   {
+                       pref->suppressed = 2;
+                       pref = p;
+                   }
+                   else if (pref->prec > p->prec)
+                   {
+                       p->suppressed = 2;
+                   }
+                   else if (pref->assoc == LEFT)
+                   {
+                       pref->suppressed = 2;
+                       pref = p;
+                   }
+                   else if (pref->assoc == RIGHT)
+                   {
+                       p->suppressed = 2;
+                   }
+                   else
+                   {
+                       pref->suppressed = 2;
+                       p->suppressed = 2;
+                   }
+               }
+               else
+               {
+                   SRcount++;
+                   p->suppressed = 1;
+               }
+           }
+           else
+           {
+               RRcount++;
+               p->suppressed = 1;
+           }
+       }
+       SRtotal += SRcount;
+       RRtotal += RRcount;
+       SRconflicts[i] = SRcount;
+       RRconflicts[i] = RRcount;
+    }
+}
+
+static void
+total_conflicts(void)
+{
+    fprintf(stderr, "%s: ", myname);
+    if (SRtotal == 1)
+       fprintf(stderr, "1 shift/reduce conflict");
+    else if (SRtotal > 1)
+       fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
+
+    if (SRtotal && RRtotal)
+       fprintf(stderr, ", ");
+
+    if (RRtotal == 1)
+       fprintf(stderr, "1 reduce/reduce conflict");
+    else if (RRtotal > 1)
+       fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
+
+    fprintf(stderr, ".\n");
+
+    if (SRexpect >= 0 && SRtotal != SRexpect)
+    {
+       fprintf(stderr, "%s: ", myname);
+       fprintf(stderr, "expected %d shift/reduce conflict%s.\n",
+               SRexpect, PLURAL(SRexpect));
+       exit_code = EXIT_FAILURE;
+    }
+    if (RRexpect >= 0 && RRtotal != RRexpect)
+    {
+       fprintf(stderr, "%s: ", myname);
+       fprintf(stderr, "expected %d reduce/reduce conflict%s.\n",
+               RRexpect, PLURAL(RRexpect));
+       exit_code = EXIT_FAILURE;
+    }
+}
+
+static int
+sole_reduction(int stateno)
+{
+    int count, ruleno;
+    action *p;
+
+    count = 0;
+    ruleno = 0;
+    for (p = parser[stateno]; p; p = p->next)
+    {
+       if (p->action_code == SHIFT && p->suppressed == 0)
+           return (0);
+       else if (p->action_code == REDUCE && p->suppressed == 0)
+       {
+           if (ruleno > 0 && p->number != ruleno)
+               return (0);
+           if (p->symbol != 1)
+               ++count;
+           ruleno = p->number;
+       }
+    }
+
+    if (count == 0)
+       return (0);
+    return (ruleno);
+}
+
+static void
+defreds(void)
+{
+    int i;
+
+    defred = NEW2(nstates, Value_t);
+    for (i = 0; i < nstates; i++)
+       defred[i] = (Value_t) sole_reduction(i);
+}
+
+static void
+free_action_row(action *p)
+{
+    action *q;
+
+    while (p)
+    {
+       q = p->next;
+       FREE(p);
+       p = q;
+    }
+}
+
+void
+free_parser(void)
+{
+    int i;
+
+    for (i = 0; i < nstates; i++)
+       free_action_row(parser[i]);
+
+    FREE(parser);
+}
+
+#ifdef NO_LEAKS
+void
+mkpar_leaks(void)
+{
+    DO_FREE(defred);
+    DO_FREE(rules_used);
+    DO_FREE(SRconflicts);
+    DO_FREE(RRconflicts);
+}
+#endif
diff --git a/contrib/byacc/output.c b/contrib/byacc/output.c
new file mode 100644 (file)
index 0000000..331726d
--- /dev/null
@@ -0,0 +1,1507 @@
+/* $Id: output.c,v 1.44 2012/05/26 01:13:02 tom Exp $ */
+
+#include "defs.h"
+
+#define StaticOrR      (rflag ? "" : "static ")
+#define CountLine(fp)   (!rflag || ((fp) == code_file))
+
+static int nvectors;
+static int nentries;
+static Value_t **froms;
+static Value_t **tos;
+static Value_t *tally;
+static Value_t *width;
+static Value_t *state_count;
+static Value_t *order;
+static Value_t *base;
+static Value_t *pos;
+static int maxtable;
+static Value_t *table;
+static Value_t *check;
+static int lowzero;
+static int high;
+
+static void
+putc_code(FILE * fp, int c)
+{
+    if ((c == '\n') && (fp == code_file))
+       ++outline;
+    putc(c, fp);
+}
+
+static void
+putl_code(FILE * fp, const char *s)
+{
+    if (fp == code_file)
+       ++outline;
+    fputs(s, fp);
+}
+
+static void
+puts_code(FILE * fp, const char *s)
+{
+    fputs(s, fp);
+}
+
+static void
+write_code_lineno(FILE * fp)
+{
+    if (!lflag && (fp == code_file))
+    {
+       ++outline;
+       fprintf(fp, line_format, outline, code_file_name);
+    }
+}
+
+static void
+write_input_lineno(void)
+{
+    if (!lflag)
+    {
+       ++outline;
+       fprintf(code_file, line_format, lineno, input_file_name);
+    }
+}
+
+static void
+define_prefixed(FILE * fp, const char *name)
+{
+    int bump_line = CountLine(fp);
+    if (bump_line)
+       ++outline;
+    fprintf(fp, "\n");
+
+    if (bump_line)
+       ++outline;
+    fprintf(fp, "#ifndef %s\n", name);
+
+    if (bump_line)
+       ++outline;
+    fprintf(fp, "#define %-10s %s%s\n", name, symbol_prefix, name + 2);
+
+    if (bump_line)
+       ++outline;
+    fprintf(fp, "#endif /* %s */\n", name);
+}
+
+static void
+output_prefix(FILE * fp)
+{
+    if (symbol_prefix == NULL)
+    {
+       symbol_prefix = "yy";
+    }
+    else
+    {
+       define_prefixed(fp, "yyparse");
+       define_prefixed(fp, "yylex");
+       define_prefixed(fp, "yyerror");
+       define_prefixed(fp, "yychar");
+       define_prefixed(fp, "yyval");
+       define_prefixed(fp, "yylval");
+       define_prefixed(fp, "yydebug");
+       define_prefixed(fp, "yynerrs");
+       define_prefixed(fp, "yyerrflag");
+       define_prefixed(fp, "yylhs");
+       define_prefixed(fp, "yylen");
+       define_prefixed(fp, "yydefred");
+       define_prefixed(fp, "yydgoto");
+       define_prefixed(fp, "yysindex");
+       define_prefixed(fp, "yyrindex");
+       define_prefixed(fp, "yygindex");
+       define_prefixed(fp, "yytable");
+       define_prefixed(fp, "yycheck");
+       define_prefixed(fp, "yyname");
+       define_prefixed(fp, "yyrule");
+    }
+    if (CountLine(fp))
+       ++outline;
+    fprintf(fp, "#define YYPREFIX \"%s\"\n", symbol_prefix);
+}
+
+static void
+output_newline(void)
+{
+    if (!rflag)
+       ++outline;
+    putc('\n', output_file);
+}
+
+static void
+output_line(const char *value)
+{
+    fputs(value, output_file);
+    output_newline();
+}
+
+static void
+output_int(int value)
+{
+    fprintf(output_file, "%5d,", value);
+}
+
+static void
+start_int_table(const char *name, int value)
+{
+    int need = 34 - (int)(strlen(symbol_prefix) + strlen(name));
+
+    if (need < 6)
+       need = 6;
+    fprintf(output_file,
+           "%sconst short %s%s[] = {%*d,",
+           StaticOrR, symbol_prefix, name, need, value);
+}
+
+static void
+start_str_table(const char *name)
+{
+    fprintf(output_file,
+           "%sconst char *%s%s[] = {",
+           StaticOrR, "yy", name);
+    output_newline();
+}
+
+static void
+end_table(void)
+{
+    output_newline();
+    output_line("};");
+}
+
+static void
+output_rule_data(void)
+{
+    int i;
+    int j;
+
+    start_int_table("lhs", symbol_value[start_symbol]);
+
+    j = 10;
+    for (i = 3; i < nrules; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           ++j;
+
+       output_int(symbol_value[rlhs[i]]);
+    }
+    end_table();
+
+    start_int_table("len", 2);
+
+    j = 10;
+    for (i = 3; i < nrules; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           j++;
+
+       output_int(rrhs[i + 1] - rrhs[i] - 1);
+    }
+    end_table();
+}
+
+static void
+output_yydefred(void)
+{
+    int i, j;
+
+    start_int_table("defred", (defred[0] ? defred[0] - 2 : 0));
+
+    j = 10;
+    for (i = 1; i < nstates; i++)
+    {
+       if (j < 10)
+           ++j;
+       else
+       {
+           output_newline();
+           j = 1;
+       }
+
+       output_int((defred[i] ? defred[i] - 2 : 0));
+    }
+
+    end_table();
+}
+
+static void
+token_actions(void)
+{
+    int i, j;
+    Value_t shiftcount, reducecount;
+    int max, min;
+    Value_t *actionrow, *r, *s;
+    action *p;
+
+    actionrow = NEW2(2 * ntokens, Value_t);
+    for (i = 0; i < nstates; ++i)
+    {
+       if (parser[i])
+       {
+           for (j = 0; j < 2 * ntokens; ++j)
+               actionrow[j] = 0;
+
+           shiftcount = 0;
+           reducecount = 0;
+           for (p = parser[i]; p; p = p->next)
+           {
+               if (p->suppressed == 0)
+               {
+                   if (p->action_code == SHIFT)
+                   {
+                       ++shiftcount;
+                       actionrow[p->symbol] = p->number;
+                   }
+                   else if (p->action_code == REDUCE && p->number != defred[i])
+                   {
+                       ++reducecount;
+                       actionrow[p->symbol + ntokens] = p->number;
+                   }
+               }
+           }
+
+           tally[i] = shiftcount;
+           tally[nstates + i] = reducecount;
+           width[i] = 0;
+           width[nstates + i] = 0;
+           if (shiftcount > 0)
+           {
+               froms[i] = r = NEW2(shiftcount, Value_t);
+               tos[i] = s = NEW2(shiftcount, Value_t);
+               min = MAXSHORT;
+               max = 0;
+               for (j = 0; j < ntokens; ++j)
+               {
+                   if (actionrow[j])
+                   {
+                       if (min > symbol_value[j])
+                           min = symbol_value[j];
+                       if (max < symbol_value[j])
+                           max = symbol_value[j];
+                       *r++ = symbol_value[j];
+                       *s++ = actionrow[j];
+                   }
+               }
+               width[i] = (Value_t) (max - min + 1);
+           }
+           if (reducecount > 0)
+           {
+               froms[nstates + i] = r = NEW2(reducecount, Value_t);
+               tos[nstates + i] = s = NEW2(reducecount, Value_t);
+               min = MAXSHORT;
+               max = 0;
+               for (j = 0; j < ntokens; ++j)
+               {
+                   if (actionrow[ntokens + j])
+                   {
+                       if (min > symbol_value[j])
+                           min = symbol_value[j];
+                       if (max < symbol_value[j])
+                           max = symbol_value[j];
+                       *r++ = symbol_value[j];
+                       *s++ = (Value_t) (actionrow[ntokens + j] - 2);
+                   }
+               }
+               width[nstates + i] = (Value_t) (max - min + 1);
+           }
+       }
+    }
+    FREE(actionrow);
+}
+
+static int
+default_goto(int symbol)
+{
+    int i;
+    int m;
+    int n;
+    int default_state;
+    int max;
+
+    m = goto_map[symbol];
+    n = goto_map[symbol + 1];
+
+    if (m == n)
+       return (0);
+
+    for (i = 0; i < nstates; i++)
+       state_count[i] = 0;
+
+    for (i = m; i < n; i++)
+       state_count[to_state[i]]++;
+
+    max = 0;
+    default_state = 0;
+    for (i = 0; i < nstates; i++)
+    {
+       if (state_count[i] > max)
+       {
+           max = state_count[i];
+           default_state = i;
+       }
+    }
+
+    return (default_state);
+}
+
+static void
+save_column(int symbol, int default_state)
+{
+    int i;
+    int m;
+    int n;
+    Value_t *sp;
+    Value_t *sp1;
+    Value_t *sp2;
+    Value_t count;
+    int symno;
+
+    m = goto_map[symbol];
+    n = goto_map[symbol + 1];
+
+    count = 0;
+    for (i = m; i < n; i++)
+    {
+       if (to_state[i] != default_state)
+           ++count;
+    }
+    if (count == 0)
+       return;
+
+    symno = symbol_value[symbol] + 2 * nstates;
+
+    froms[symno] = sp1 = sp = NEW2(count, Value_t);
+    tos[symno] = sp2 = NEW2(count, Value_t);
+
+    for (i = m; i < n; i++)
+    {
+       if (to_state[i] != default_state)
+       {
+           *sp1++ = from_state[i];
+           *sp2++ = to_state[i];
+       }
+    }
+
+    tally[symno] = count;
+    width[symno] = (Value_t) (sp1[-1] - sp[0] + 1);
+}
+
+static void
+goto_actions(void)
+{
+    int i, j, k;
+
+    state_count = NEW2(nstates, Value_t);
+
+    k = default_goto(start_symbol + 1);
+    start_int_table("dgoto", k);
+    save_column(start_symbol + 1, k);
+
+    j = 10;
+    for (i = start_symbol + 2; i < nsyms; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           ++j;
+
+       k = default_goto(i);
+       output_int(k);
+       save_column(i, k);
+    }
+
+    end_table();
+    FREE(state_count);
+}
+
+static void
+sort_actions(void)
+{
+    Value_t i;
+    int j;
+    int k;
+    int t;
+    int w;
+
+    order = NEW2(nvectors, Value_t);
+    nentries = 0;
+
+    for (i = 0; i < nvectors; i++)
+    {
+       if (tally[i] > 0)
+       {
+           t = tally[i];
+           w = width[i];
+           j = nentries - 1;
+
+           while (j >= 0 && (width[order[j]] < w))
+               j--;
+
+           while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
+               j--;
+
+           for (k = nentries - 1; k > j; k--)
+               order[k + 1] = order[k];
+
+           order[j + 1] = i;
+           nentries++;
+       }
+    }
+}
+
+/*  The function matching_vector determines if the vector specified by */
+/*  the input parameter matches a previously considered        vector.  The    */
+/*  test at the start of the function checks if the vector represents  */
+/*  a row of shifts over terminal symbols or a row of reductions, or a */
+/*  column of shifts over a nonterminal symbol.  Berkeley Yacc does not        */
+/*  check if a column of shifts over a nonterminal symbols matches a   */
+/*  previously considered vector.  Because of the nature of LR parsing */
+/*  tables, no two columns can match.  Therefore, the only possible    */
+/*  match would be between a row and a column.  Such matches are       */
+/*  unlikely.  Therefore, to save time, no attempt is made to see if a */
+/*  column matches a previously considered vector.                     */
+/*                                                                     */
+/*  Matching_vector is poorly designed.  The test could easily be made */
+/*  faster.  Also, it depends on the vectors being in a specific       */
+/*  order.                                                             */
+
+static int
+matching_vector(int vector)
+{
+    int i;
+    int j;
+    int k;
+    int t;
+    int w;
+    int match;
+    int prev;
+
+    i = order[vector];
+    if (i >= 2 * nstates)
+       return (-1);
+
+    t = tally[i];
+    w = width[i];
+
+    for (prev = vector - 1; prev >= 0; prev--)
+    {
+       j = order[prev];
+       if (width[j] != w || tally[j] != t)
+           return (-1);
+
+       match = 1;
+       for (k = 0; match && k < t; k++)
+       {
+           if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
+               match = 0;
+       }
+
+       if (match)
+           return (j);
+    }
+
+    return (-1);
+}
+
+static int
+pack_vector(int vector)
+{
+    int i, j, k, l;
+    int t;
+    int loc;
+    int ok;
+    Value_t *from;
+    Value_t *to;
+    int newmax;
+
+    i = order[vector];
+    t = tally[i];
+    assert(t);
+
+    from = froms[i];
+    to = tos[i];
+
+    j = lowzero - from[0];
+    for (k = 1; k < t; ++k)
+       if (lowzero - from[k] > j)
+           j = lowzero - from[k];
+    for (;; ++j)
+    {
+       if (j == 0)
+           continue;
+       ok = 1;
+       for (k = 0; ok && k < t; k++)
+       {
+           loc = j + from[k];
+           if (loc >= maxtable - 1)
+           {
+               if (loc >= MAXTABLE - 1)
+                   fatal("maximum table size exceeded");
+
+               newmax = maxtable;
+               do
+               {
+                   newmax += 200;
+               }
+               while (newmax <= loc);
+
+               table = TREALLOC(Value_t, table, newmax);
+               NO_SPACE(table);
+
+               check = TREALLOC(Value_t, check, newmax);
+               NO_SPACE(check);
+
+               for (l = maxtable; l < newmax; ++l)
+               {
+                   table[l] = 0;
+                   check[l] = -1;
+               }
+               maxtable = newmax;
+           }
+
+           if (check[loc] != -1)
+               ok = 0;
+       }
+       for (k = 0; ok && k < vector; k++)
+       {
+           if (pos[k] == j)
+               ok = 0;
+       }
+       if (ok)
+       {
+           for (k = 0; k < t; k++)
+           {
+               loc = j + from[k];
+               table[loc] = to[k];
+               check[loc] = from[k];
+               if (loc > high)
+                   high = loc;
+           }
+
+           while (check[lowzero] != -1)
+               ++lowzero;
+
+           return (j);
+       }
+    }
+}
+
+static void
+pack_table(void)
+{
+    int i;
+    Value_t place;
+    int state;
+
+    base = NEW2(nvectors, Value_t);
+    pos = NEW2(nentries, Value_t);
+
+    maxtable = 1000;
+    table = NEW2(maxtable, Value_t);
+    check = NEW2(maxtable, Value_t);
+
+    lowzero = 0;
+    high = 0;
+
+    for (i = 0; i < maxtable; i++)
+       check[i] = -1;
+
+    for (i = 0; i < nentries; i++)
+    {
+       state = matching_vector(i);
+
+       if (state < 0)
+           place = (Value_t) pack_vector(i);
+       else
+           place = base[state];
+
+       pos[i] = place;
+       base[order[i]] = place;
+    }
+
+    for (i = 0; i < nvectors; i++)
+    {
+       if (froms[i])
+           FREE(froms[i]);
+       if (tos[i])
+           FREE(tos[i]);
+    }
+
+    FREE(froms);
+    FREE(tos);
+    FREE(pos);
+}
+
+static void
+output_base(void)
+{
+    int i, j;
+
+    start_int_table("sindex", base[0]);
+
+    j = 10;
+    for (i = 1; i < nstates; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           ++j;
+
+       output_int(base[i]);
+    }
+
+    end_table();
+
+    start_int_table("rindex", base[nstates]);
+
+    j = 10;
+    for (i = nstates + 1; i < 2 * nstates; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           ++j;
+
+       output_int(base[i]);
+    }
+
+    end_table();
+
+    start_int_table("gindex", base[2 * nstates]);
+
+    j = 10;
+    for (i = 2 * nstates + 1; i < nvectors - 1; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           ++j;
+
+       output_int(base[i]);
+    }
+
+    end_table();
+    FREE(base);
+}
+
+static void
+output_table(void)
+{
+    int i;
+    int j;
+
+    ++outline;
+    fprintf(code_file, "#define YYTABLESIZE %d\n", high);
+    start_int_table("table", table[0]);
+
+    j = 10;
+    for (i = 1; i <= high; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           ++j;
+
+       output_int(table[i]);
+    }
+
+    end_table();
+    FREE(table);
+}
+
+static void
+output_check(void)
+{
+    int i;
+    int j;
+
+    start_int_table("check", check[0]);
+
+    j = 10;
+    for (i = 1; i <= high; i++)
+    {
+       if (j >= 10)
+       {
+           output_newline();
+           j = 1;
+       }
+       else
+           ++j;
+
+       output_int(check[i]);
+    }
+
+    end_table();
+    FREE(check);
+}
+
+static void
+output_actions(void)
+{
+    nvectors = 2 * nstates + nvars;
+
+    froms = NEW2(nvectors, Value_t *);
+    tos = NEW2(nvectors, Value_t *);
+    tally = NEW2(nvectors, Value_t);
+    width = NEW2(nvectors, Value_t);
+
+    token_actions();
+    FREE(lookaheads);
+    FREE(LA);
+    FREE(LAruleno);
+    FREE(accessing_symbol);
+
+    goto_actions();
+    FREE(goto_map + ntokens);
+    FREE(from_state);
+    FREE(to_state);
+
+    sort_actions();
+    pack_table();
+    output_base();
+    output_table();
+    output_check();
+}
+
+static int
+is_C_identifier(char *name)
+{
+    char *s;
+    int c;
+
+    s = name;
+    c = *s;
+    if (c == '"')
+    {
+       c = *++s;
+       if (!isalpha(c) && c != '_' && c != '$')
+           return (0);
+       while ((c = *++s) != '"')
+       {
+           if (!isalnum(c) && c != '_' && c != '$')
+               return (0);
+       }
+       return (1);
+    }
+
+    if (!isalpha(c) && c != '_' && c != '$')
+       return (0);
+    while ((c = *++s) != 0)
+    {
+       if (!isalnum(c) && c != '_' && c != '$')
+           return (0);
+    }
+    return (1);
+}
+
+static void
+output_defines(FILE * fp)
+{
+    int c, i;
+    char *s;
+
+    for (i = 2; i < ntokens; ++i)
+    {
+       s = symbol_name[i];
+       if (is_C_identifier(s) && (!sflag || *s != '"'))
+       {
+           fprintf(fp, "#define ");
+           c = *s;
+           if (c == '"')
+           {
+               while ((c = *++s) != '"')
+               {
+                   putc(c, fp);
+               }
+           }
+           else
+           {
+               do
+               {
+                   putc(c, fp);
+               }
+               while ((c = *++s) != 0);
+           }
+           if (fp == code_file)
+               ++outline;
+           fprintf(fp, " %d\n", symbol_value[i]);
+       }
+    }
+
+    if (fp == code_file)
+       ++outline;
+    if (fp != defines_file || iflag)
+       fprintf(fp, "#define YYERRCODE %d\n", symbol_value[1]);
+
+    if (fp == defines_file || (iflag && !dflag))
+    {
+       if (unionized)
+       {
+           rewind(union_file);
+           while ((c = getc(union_file)) != EOF)
+               putc(c, fp);
+           fprintf(fp, "extern YYSTYPE %slval;\n", symbol_prefix);
+       }
+    }
+}
+
+static void
+output_stored_text(FILE * fp)
+{
+    int c;
+    FILE *in;
+
+    rewind(text_file);
+    if (text_file == NULL)
+       open_error("text_file");
+    in = text_file;
+    if ((c = getc(in)) == EOF)
+       return;
+    putc_code(fp, c);
+    while ((c = getc(in)) != EOF)
+    {
+       putc_code(fp, c);
+    }
+    write_code_lineno(fp);
+}
+
+static void
+output_debug(void)
+{
+    int i, j, k, max;
+    const char **symnam;
+    const char *s;
+
+    ++outline;
+    fprintf(code_file, "#define YYFINAL %d\n", final_state);
+
+    putl_code(code_file, "#ifndef YYDEBUG\n");
+    ++outline;
+    fprintf(code_file, "#define YYDEBUG %d\n", tflag);
+    putl_code(code_file, "#endif\n");
+
+    if (rflag)
+    {
+       fprintf(output_file, "#ifndef YYDEBUG\n");
+       fprintf(output_file, "#define YYDEBUG %d\n", tflag);
+       fprintf(output_file, "#endif\n");
+    }
+
+    max = 0;
+    for (i = 2; i < ntokens; ++i)
+       if (symbol_value[i] > max)
+           max = symbol_value[i];
+
+    ++outline;
+    fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
+
+    symnam = TMALLOC(const char *, max + 1);
+    NO_SPACE(symnam);
+
+    /* Note that it is  not necessary to initialize the element         */
+    /* symnam[max].                                                     */
+    for (i = 0; i < max; ++i)
+       symnam[i] = 0;
+    for (i = ntokens - 1; i >= 2; --i)
+       symnam[symbol_value[i]] = symbol_name[i];
+    symnam[0] = "end-of-file";
+
+    output_line("#if YYDEBUG");
+
+    start_str_table("name");
+    j = 80;
+    for (i = 0; i <= max; ++i)
+    {
+       if ((s = symnam[i]) != 0)
+       {
+           if (s[0] == '"')
+           {
+               k = 7;
+               while (*++s != '"')
+               {
+                   ++k;
+                   if (*s == '\\')
+                   {
+                       k += 2;
+                       if (*++s == '\\')
+                           ++k;
+                   }
+               }
+               j += k;
+               if (j > 80)
+               {
+                   output_newline();
+                   j = k;
+               }
+               fprintf(output_file, "\"\\\"");
+               s = symnam[i];
+               while (*++s != '"')
+               {
+                   if (*s == '\\')
+                   {
+                       fprintf(output_file, "\\\\");
+                       if (*++s == '\\')
+                           fprintf(output_file, "\\\\");
+                       else
+                           putc(*s, output_file);
+                   }
+                   else
+                       putc(*s, output_file);
+               }
+               fprintf(output_file, "\\\"\",");
+           }
+           else if (s[0] == '\'')
+           {
+               if (s[1] == '"')
+               {
+                   j += 7;
+                   if (j > 80)
+                   {
+                       output_newline();
+                       j = 7;
+                   }
+                   fprintf(output_file, "\"'\\\"'\",");
+               }
+               else
+               {
+                   k = 5;
+                   while (*++s != '\'')
+                   {
+                       ++k;
+                       if (*s == '\\')
+                       {
+                           k += 2;
+                           if (*++s == '\\')
+                               ++k;
+                       }
+                   }
+                   j += k;
+                   if (j > 80)
+                   {
+                       output_newline();
+                       j = k;
+                   }
+                   fprintf(output_file, "\"'");
+                   s = symnam[i];
+                   while (*++s != '\'')
+                   {
+                       if (*s == '\\')
+                       {
+                           fprintf(output_file, "\\\\");
+                           if (*++s == '\\')
+                               fprintf(output_file, "\\\\");
+                           else
+                               putc(*s, output_file);
+                       }
+                       else
+                           putc(*s, output_file);
+                   }
+                   fprintf(output_file, "'\",");
+               }
+           }
+           else
+           {
+               k = (int)strlen(s) + 3;
+               j += k;
+               if (j > 80)
+               {
+                   output_newline();
+                   j = k;
+               }
+               putc('"', output_file);
+               do
+               {
+                   putc(*s, output_file);
+               }
+               while (*++s);
+               fprintf(output_file, "\",");
+           }
+       }
+       else
+       {
+           j += 2;
+           if (j > 80)
+           {
+               output_newline();
+               j = 2;
+           }
+           fprintf(output_file, "0,");
+       }
+    }
+    end_table();
+    FREE(symnam);
+
+    start_str_table("rule");
+    for (i = 2; i < nrules; ++i)
+    {
+       fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
+       for (j = rrhs[i]; ritem[j] > 0; ++j)
+       {
+           s = symbol_name[ritem[j]];
+           if (s[0] == '"')
+           {
+               fprintf(output_file, " \\\"");
+               while (*++s != '"')
+               {
+                   if (*s == '\\')
+                   {
+                       if (s[1] == '\\')
+                           fprintf(output_file, "\\\\\\\\");
+                       else
+                           fprintf(output_file, "\\\\%c", s[1]);
+                       ++s;
+                   }
+                   else
+                       putc(*s, output_file);
+               }
+               fprintf(output_file, "\\\"");
+           }
+           else if (s[0] == '\'')
+           {
+               if (s[1] == '"')
+                   fprintf(output_file, " '\\\"'");
+               else if (s[1] == '\\')
+               {
+                   if (s[2] == '\\')
+                       fprintf(output_file, " '\\\\\\\\");
+                   else
+                       fprintf(output_file, " '\\\\%c", s[2]);
+                   s += 2;
+                   while (*++s != '\'')
+                       putc(*s, output_file);
+                   putc('\'', output_file);
+               }
+               else
+                   fprintf(output_file, " '%c'", s[1]);
+           }
+           else
+               fprintf(output_file, " %s", s);
+       }
+       fprintf(output_file, "\",");
+       output_newline();
+    }
+
+    end_table();
+    output_line("#endif");
+}
+
+static void
+output_pure_parser(FILE * fp)
+{
+    putc_code(fp, '\n');
+
+    if (fp == code_file)
+       outline += 1;
+    fprintf(fp, "#define YYPURE %d\n", pure_parser);
+    putc_code(fp, '\n');
+}
+
+static void
+output_stype(FILE * fp)
+{
+    if (!unionized && ntags == 0)
+    {
+       putc_code(fp, '\n');
+       putl_code(fp, "#ifndef YYSTYPE\n");
+       putl_code(fp, "typedef int YYSTYPE;\n");
+       putl_code(fp, "#endif\n");
+    }
+}
+
+static void
+output_trailing_text(void)
+{
+    int c, last;
+    FILE *in;
+
+    if (line == 0)
+       return;
+
+    in = input_file;
+    c = *cptr;
+    if (c == '\n')
+    {
+       ++lineno;
+       if ((c = getc(in)) == EOF)
+           return;
+       write_input_lineno();
+       putc_code(code_file, c);
+       last = c;
+    }
+    else
+    {
+       write_input_lineno();
+       do
+       {
+           putc_code(code_file, c);
+       }
+       while ((c = *++cptr) != '\n');
+       putc_code(code_file, c);
+       last = '\n';
+    }
+
+    while ((c = getc(in)) != EOF)
+    {
+       putc_code(code_file, c);
+       last = c;
+    }
+
+    if (last != '\n')
+    {
+       putc_code(code_file, '\n');
+    }
+    write_code_lineno(code_file);
+}
+
+static void
+output_semantic_actions(void)
+{
+    int c, last;
+
+    rewind(action_file);
+    if ((c = getc(action_file)) == EOF)
+       return;
+
+    last = c;
+    putc_code(code_file, c);
+    while ((c = getc(action_file)) != EOF)
+    {
+       putc_code(code_file, c);
+       last = c;
+    }
+
+    if (last != '\n')
+    {
+       putc_code(code_file, '\n');
+    }
+
+    write_code_lineno(code_file);
+}
+
+static void
+output_parse_decl(FILE * fp)
+{
+    putl_code(fp, "\n");
+    putl_code(fp, "/* compatibility with bison */\n");
+    putl_code(fp, "#ifdef YYPARSE_PARAM\n");
+    putl_code(fp, "/* compatibility with FreeBSD */\n");
+    putl_code(fp, "# ifdef YYPARSE_PARAM_TYPE\n");
+    putl_code(fp,
+             "#  define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
+    putl_code(fp, "# else\n");
+    putl_code(fp, "#  define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
+    putl_code(fp, "# endif\n");
+    putl_code(fp, "#else\n");
+
+    puts_code(fp, "# define YYPARSE_DECL() yyparse(");
+    if (!parse_param)
+       puts_code(fp, "void");
+    else
+    {
+       param *p;
+       for (p = parse_param; p; p = p->next)
+           fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
+                   p->next ? ", " : "");
+    }
+    putl_code(fp, ")\n");
+
+    putl_code(fp, "#endif\n");
+}
+
+static void
+output_lex_decl(FILE * fp)
+{
+    putl_code(fp, "\n");
+    putl_code(fp, "/* Parameters sent to lex. */\n");
+    putl_code(fp, "#ifdef YYLEX_PARAM\n");
+    if (pure_parser)
+    {
+       putl_code(fp, "# ifdef YYLEX_PARAM_TYPE\n");
+       putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
+                 " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
+       putl_code(fp, "# else\n");
+       putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
+                 " void * YYLEX_PARAM)\n");
+       putl_code(fp, "# endif\n");
+       putl_code(fp, "# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
+    }
+    else
+    {
+       putl_code(fp, "# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
+       putl_code(fp, "# define YYLEX yylex(YYLEX_PARAM)\n");
+    }
+    putl_code(fp, "#else\n");
+    if (pure_parser && lex_param)
+    {
+       param *p;
+       puts_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
+       for (p = lex_param; p; p = p->next)
+           fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
+                   p->next ? ", " : "");
+       putl_code(fp, ")\n");
+
+       puts_code(fp, "# define YYLEX yylex(&yylval, ");
+       for (p = lex_param; p; p = p->next)
+           fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
+       putl_code(fp, ")\n");
+    }
+    else if (pure_parser)
+    {
+       putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
+       putl_code(fp, "# define YYLEX yylex(&yylval)\n");
+    }
+    else if (lex_param)
+    {
+       param *p;
+       puts_code(fp, "# define YYLEX_DECL() yylex(");
+       for (p = lex_param; p; p = p->next)
+           fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
+                   p->next ? ", " : "");
+       putl_code(fp, ")\n");
+
+       puts_code(fp, "# define YYLEX yylex(");
+       for (p = lex_param; p; p = p->next)
+           fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
+       putl_code(fp, ")\n");
+    }
+    else
+    {
+       putl_code(fp, "# define YYLEX_DECL() yylex(void)\n");
+       putl_code(fp, "# define YYLEX yylex()\n");
+    }
+    putl_code(fp, "#endif\n");
+}
+
+static void
+output_error_decl(FILE * fp)
+{
+    putl_code(fp, "\n");
+    putl_code(fp, "/* Parameters sent to yyerror. */\n");
+    if (parse_param)
+    {
+       param *p;
+
+       putl_code(fp, "#ifndef YYERROR_DECL\n");
+       fprintf(fp, "#define YYERROR_DECL() yyerror(");
+       for (p = parse_param; p; p = p->next)
+           fprintf(fp, "%s %s%s, ", p->type, p->name, p->type2);
+       putl_code(fp, "const char *s)\n");
+       putl_code(fp, "#endif\n");
+
+       putl_code(fp, "#ifndef YYERROR_CALL\n");
+       puts_code(fp, "#define YYERROR_CALL(msg) yyerror(");
+
+       for (p = parse_param; p; p = p->next)
+           fprintf(fp, "%s, ", p->name);
+
+       putl_code(fp, "msg)\n");
+       putl_code(fp, "#endif\n");
+    }
+    else
+    {
+       putl_code(fp, "#ifndef YYERROR_DECL\n");
+       putl_code(fp, "#define YYERROR_DECL() yyerror(const char *s)\n");
+       putl_code(fp, "#endif\n");
+       putl_code(fp, "#ifndef YYERROR_CALL\n");
+       putl_code(fp, "#define YYERROR_CALL(msg) yyerror(msg)\n");
+       putl_code(fp, "#endif\n");
+    }
+}
+
+static void
+free_itemsets(void)
+{
+    core *cp, *next;
+
+    FREE(state_table);
+    for (cp = first_state; cp; cp = next)
+    {
+       next = cp->next;
+       FREE(cp);
+    }
+}
+
+static void
+free_shifts(void)
+{
+    shifts *sp, *next;
+
+    FREE(shift_table);
+    for (sp = first_shift; sp; sp = next)
+    {
+       next = sp->next;
+       FREE(sp);
+    }
+}
+
+static void
+free_reductions(void)
+{
+    reductions *rp, *next;
+
+    FREE(reduction_table);
+    for (rp = first_reduction; rp; rp = next)
+    {
+       next = rp->next;
+       FREE(rp);
+    }
+}
+
+static void
+output_yyerror_call(const char *msg)
+{
+    FILE *fp = code_file;
+
+    puts_code(fp, "    yyerror(");
+    if (parse_param)
+    {
+       param *p;
+       for (p = parse_param; p; p = p->next)
+           fprintf(fp, "%s, ", p->name);
+    }
+    puts_code(fp, "\"");
+    puts_code(fp, msg);
+    putl_code(fp, "\");\n");
+}
+
+static void
+output_externs(FILE * fp, const char *const section[])
+{
+    int c;
+    int i;
+    const char *s;
+
+    for (i = 0; (s = section[i]) != 0; ++i)
+    {
+       if (*s && *s != '#')
+           fputs("extern\t", fp);
+       while ((c = *s) != 0)
+       {
+           putc(c, fp);
+           ++s;
+       }
+       if (fp == code_file)
+           ++outline;
+       putc('\n', fp);
+    }
+}
+
+void
+output(void)
+{
+    FILE *fp;
+
+    free_itemsets();
+    free_shifts();
+    free_reductions();
+
+    if (iflag)
+    {
+       ++outline;
+       fprintf(code_file, "#include \"%s\"\n", externs_file_name);
+       fp = externs_file;
+    }
+    else
+       fp = code_file;
+
+    output_prefix(iflag ? externs_file : output_file);
+    output_pure_parser(fp);
+    output_stored_text(fp);
+    output_stype(fp);
+    output_parse_decl(fp);
+    output_lex_decl(fp);
+    output_error_decl(fp);
+    write_section(fp, xdecls);
+
+    if (iflag)
+    {
+       output_externs(externs_file, global_vars);
+       if (!pure_parser)
+           output_externs(externs_file, impure_vars);
+    }
+
+    if (iflag)
+    {
+       ++outline;
+       fprintf(code_file, "#include \"%s\"\n", defines_file_name);
+       if (!dflag)
+           output_defines(externs_file);
+    }
+    else
+    {
+       putc_code(code_file, '\n');
+       output_defines(code_file);
+    }
+
+    if (dflag)
+       output_defines(defines_file);
+
+    output_rule_data();
+    output_yydefred();
+    output_actions();
+    free_parser();
+    output_debug();
+    if (rflag)
+    {
+       output_prefix(code_file);
+       write_section(code_file, xdecls);
+       write_section(code_file, tables);
+    }
+    write_section(code_file, global_vars);
+    if (!pure_parser)
+    {
+       write_section(code_file, impure_vars);
+    }
+    write_section(code_file, hdr_defs);
+    if (!pure_parser)
+    {
+       write_section(code_file, hdr_vars);
+    }
+    output_trailing_text();
+    write_section(code_file, body_1);
+    if (pure_parser)
+    {
+       write_section(code_file, body_vars);
+    }
+    write_section(code_file, body_2);
+    output_yyerror_call("syntax error");
+    write_section(code_file, body_3);
+    output_semantic_actions();
+    write_section(code_file, trailer);
+    output_yyerror_call("yacc stack overflow");
+    write_section(code_file, trailer_2);
+}
+
+#ifdef NO_LEAKS
+void
+output_leaks(void)
+{
+    DO_FREE(tally);
+    DO_FREE(width);
+    DO_FREE(order);
+}
+#endif
diff --git a/contrib/byacc/reader.c b/contrib/byacc/reader.c
new file mode 100644 (file)
index 0000000..124b776
--- /dev/null
@@ -0,0 +1,2251 @@
+/* $Id: reader.c,v 1.36 2012/05/26 16:05:41 tom Exp $ */
+
+#include "defs.h"
+
+/*  The line size must be a positive integer.  One hundred was chosen  */
+/*  because few lines in Yacc input grammars exceed 100 characters.    */
+/*  Note that if a line exceeds LINESIZE characters, the line buffer   */
+/*  will be expanded to accomodate it.                                 */
+
+#define LINESIZE 100
+
+#define L_CURL '{'
+#define R_CURL '}'
+
+static void start_rule(bucket *bp, int s_lineno);
+
+static char *cache;
+static int cinc, cache_size;
+
+int ntags;
+static int tagmax;
+static char **tag_table;
+
+static char saw_eof;
+char unionized;
+char *cptr, *line;
+static int linesize;
+
+static bucket *goal;
+static Value_t prec;
+static int gensym;
+static char last_was_action;
+
+static int maxitems;
+static bucket **pitem;
+
+static int maxrules;
+static bucket **plhs;
+
+static size_t name_pool_size;
+static char *name_pool;
+
+char line_format[] = "#line %d \"%s\"\n";
+
+param *lex_param;
+param *parse_param;
+
+static void
+cachec(int c)
+{
+    assert(cinc >= 0);
+    if (cinc >= cache_size)
+    {
+       cache_size += 256;
+       cache = TREALLOC(char, cache, cache_size);
+       NO_SPACE(cache);
+    }
+    cache[cinc] = (char)c;
+    ++cinc;
+}
+
+static void
+get_line(void)
+{
+    FILE *f = input_file;
+    int c;
+    int i;
+
+    if (saw_eof || (c = getc(f)) == EOF)
+    {
+       if (line)
+       {
+           FREE(line);
+           line = 0;
+       }
+       cptr = 0;
+       saw_eof = 1;
+       return;
+    }
+
+    if (line == 0 || linesize != (LINESIZE + 1))
+    {
+       if (line)
+           FREE(line);
+       linesize = LINESIZE + 1;
+       line = TMALLOC(char, linesize);
+       NO_SPACE(line);
+    }
+
+    i = 0;
+    ++lineno;
+    for (;;)
+    {
+       line[i] = (char)c;
+       if (c == '\n')
+       {
+           cptr = line;
+           return;
+       }
+       if (++i >= linesize)
+       {
+           linesize += LINESIZE;
+           line = TREALLOC(char, line, linesize);
+           NO_SPACE(line);
+       }
+       c = getc(f);
+       if (c == EOF)
+       {
+           line[i] = '\n';
+           saw_eof = 1;
+           cptr = line;
+           return;
+       }
+    }
+}
+
+static char *
+dup_line(void)
+{
+    char *p, *s, *t;
+
+    if (line == 0)
+       return (0);
+    s = line;
+    while (*s != '\n')
+       ++s;
+    p = TMALLOC(char, s - line + 1);
+    NO_SPACE(p);
+
+    s = line;
+    t = p;
+    while ((*t++ = *s++) != '\n')
+       continue;
+    return (p);
+}
+
+static void
+skip_comment(void)
+{
+    char *s;
+
+    int st_lineno = lineno;
+    char *st_line = dup_line();
+    char *st_cptr = st_line + (cptr - line);
+
+    s = cptr + 2;
+    for (;;)
+    {
+       if (*s == '*' && s[1] == '/')
+       {
+           cptr = s + 2;
+           FREE(st_line);
+           return;
+       }
+       if (*s == '\n')
+       {
+           get_line();
+           if (line == 0)
+               unterminated_comment(st_lineno, st_line, st_cptr);
+           s = cptr;
+       }
+       else
+           ++s;
+    }
+}
+
+static int
+nextc(void)
+{
+    char *s;
+
+    if (line == 0)
+    {
+       get_line();
+       if (line == 0)
+           return (EOF);
+    }
+
+    s = cptr;
+    for (;;)
+    {
+       switch (*s)
+       {
+       case '\n':
+           get_line();
+           if (line == 0)
+               return (EOF);
+           s = cptr;
+           break;
+
+       case ' ':
+       case '\t':
+       case '\f':
+       case '\r':
+       case '\v':
+       case ',':
+       case ';':
+           ++s;
+           break;
+
+       case '\\':
+           cptr = s;
+           return ('%');
+
+       case '/':
+           if (s[1] == '*')
+           {
+               cptr = s;
+               skip_comment();
+               s = cptr;
+               break;
+           }
+           else if (s[1] == '/')
+           {
+               get_line();
+               if (line == 0)
+                   return (EOF);
+               s = cptr;
+               break;
+           }
+           /* FALLTHRU */
+
+       default:
+           cptr = s;
+           return (*s);
+       }
+    }
+}
+
+/*
+ * Compare keyword to cached token, treating '_' and '-' the same.  Some
+ * grammars rely upon this misfeature.
+ */
+static int
+matchec(const char *name)
+{
+    const char *p = cache;
+    const char *q = name;
+    int code = 0;      /* assume mismatch */
+
+    while (*p != '\0' && *q != '\0')
+    {
+       char a = *p++;
+       char b = *q++;
+       if (a == '_')
+           a = '-';
+       if (b == '_')
+           b = '-';
+       if (a != b)
+           break;
+       if (*p == '\0' && *q == '\0')
+       {
+           code = 1;
+           break;
+       }
+    }
+    return code;
+}
+
+static int
+keyword(void)
+{
+    int c;
+    char *t_cptr = cptr;
+
+    c = *++cptr;
+    if (isalpha(c))
+    {
+       cinc = 0;
+       for (;;)
+       {
+           if (isalpha(c))
+           {
+               if (isupper(c))
+                   c = tolower(c);
+               cachec(c);
+           }
+           else if (isdigit(c)
+                    || c == '-'
+                    || c == '_'
+                    || c == '.'
+                    || c == '$')
+           {
+               cachec(c);
+           }
+           else
+           {
+               break;
+           }
+           c = *++cptr;
+       }
+       cachec(NUL);
+
+       if (matchec("token") || matchec("term"))
+           return (TOKEN);
+       if (matchec("type"))
+           return (TYPE);
+       if (matchec("left"))
+           return (LEFT);
+       if (matchec("right"))
+           return (RIGHT);
+       if (matchec("nonassoc") || matchec("binary"))
+           return (NONASSOC);
+       if (matchec("start"))
+           return (START);
+       if (matchec("union"))
+           return (UNION);
+       if (matchec("ident"))
+           return (IDENT);
+       if (matchec("expect"))
+           return (EXPECT);
+       if (matchec("expect-rr"))
+           return (EXPECT_RR);
+       if (matchec("pure-parser"))
+           return (PURE_PARSER);
+       if (matchec("parse-param"))
+           return (PARSE_PARAM);
+       if (matchec("lex-param"))
+           return (LEX_PARAM);
+       if (matchec("yacc"))
+           return (POSIX_YACC);
+    }
+    else
+    {
+       ++cptr;
+       if (c == L_CURL)
+           return (TEXT);
+       if (c == '%' || c == '\\')
+           return (MARK);
+       if (c == '<')
+           return (LEFT);
+       if (c == '>')
+           return (RIGHT);
+       if (c == '0')
+           return (TOKEN);
+       if (c == '2')
+           return (NONASSOC);
+    }
+    syntax_error(lineno, line, t_cptr);
+    /*NOTREACHED */
+}
+
+static void
+copy_ident(void)
+{
+    int c;
+    FILE *f = output_file;
+
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (c != '"')
+       syntax_error(lineno, line, cptr);
+    ++outline;
+    fprintf(f, "#ident \"");
+    for (;;)
+    {
+       c = *++cptr;
+       if (c == '\n')
+       {
+           fprintf(f, "\"\n");
+           return;
+       }
+       putc(c, f);
+       if (c == '"')
+       {
+           putc('\n', f);
+           ++cptr;
+           return;
+       }
+    }
+}
+
+static void
+copy_text(void)
+{
+    int c;
+    int quote;
+    FILE *f = text_file;
+    int need_newline = 0;
+    int t_lineno = lineno;
+    char *t_line = dup_line();
+    char *t_cptr = t_line + (cptr - line - 2);
+
+    if (*cptr == '\n')
+    {
+       get_line();
+       if (line == 0)
+           unterminated_text(t_lineno, t_line, t_cptr);
+    }
+    if (!lflag)
+       fprintf(f, line_format, lineno, input_file_name);
+
+  loop:
+    c = *cptr++;
+    switch (c)
+    {
+    case '\n':
+      next_line:
+       putc('\n', f);
+       need_newline = 0;
+       get_line();
+       if (line)
+           goto loop;
+       unterminated_text(t_lineno, t_line, t_cptr);
+
+    case '\'':
+    case '"':
+       {
+           int s_lineno = lineno;
+           char *s_line = dup_line();
+           char *s_cptr = s_line + (cptr - line - 1);
+
+           quote = c;
+           putc(c, f);
+           for (;;)
+           {
+               c = *cptr++;
+               putc(c, f);
+               if (c == quote)
+               {
+                   need_newline = 1;
+                   FREE(s_line);
+                   goto loop;
+               }
+               if (c == '\n')
+                   unterminated_string(s_lineno, s_line, s_cptr);
+               if (c == '\\')
+               {
+                   c = *cptr++;
+                   putc(c, f);
+                   if (c == '\n')
+                   {
+                       get_line();
+                       if (line == 0)
+                           unterminated_string(s_lineno, s_line, s_cptr);
+                   }
+               }
+           }
+       }
+
+    case '/':
+       putc(c, f);
+       need_newline = 1;
+       c = *cptr;
+       if (c == '/')
+       {
+           putc('*', f);
+           while ((c = *++cptr) != '\n')
+           {
+               if (c == '*' && cptr[1] == '/')
+                   fprintf(f, "* ");
+               else
+                   putc(c, f);
+           }
+           fprintf(f, "*/");
+           goto next_line;
+       }
+       if (c == '*')
+       {
+           int c_lineno = lineno;
+           char *c_line = dup_line();
+           char *c_cptr = c_line + (cptr - line - 1);
+
+           putc('*', f);
+           ++cptr;
+           for (;;)
+           {
+               c = *cptr++;
+               putc(c, f);
+               if (c == '*' && *cptr == '/')
+               {
+                   putc('/', f);
+                   ++cptr;
+                   FREE(c_line);
+                   goto loop;
+               }
+               if (c == '\n')
+               {
+                   get_line();
+                   if (line == 0)
+                       unterminated_comment(c_lineno, c_line, c_cptr);
+               }
+           }
+       }
+       need_newline = 1;
+       goto loop;
+
+    case '%':
+    case '\\':
+       if (*cptr == R_CURL)
+       {
+           if (need_newline)
+               putc('\n', f);
+           ++cptr;
+           FREE(t_line);
+           return;
+       }
+       /* FALLTHRU */
+
+    default:
+       putc(c, f);
+       need_newline = 1;
+       goto loop;
+    }
+}
+
+static void
+puts_both(const char *s)
+{
+    fputs(s, text_file);
+    if (dflag)
+       fputs(s, union_file);
+}
+
+static void
+putc_both(int c)
+{
+    putc(c, text_file);
+    if (dflag)
+       putc(c, union_file);
+}
+
+static void
+copy_union(void)
+{
+    int c;
+    int quote;
+    int depth;
+    int u_lineno = lineno;
+    char *u_line = dup_line();
+    char *u_cptr = u_line + (cptr - line - 6);
+
+    if (unionized)
+       over_unionized(cptr - 6);
+    unionized = 1;
+
+    if (!lflag)
+       fprintf(text_file, line_format, lineno, input_file_name);
+
+    puts_both("#ifdef YYSTYPE\n");
+    puts_both("#undef  YYSTYPE_IS_DECLARED\n");
+    puts_both("#define YYSTYPE_IS_DECLARED 1\n");
+    puts_both("#endif\n");
+    puts_both("#ifndef YYSTYPE_IS_DECLARED\n");
+    puts_both("#define YYSTYPE_IS_DECLARED 1\n");
+    puts_both("typedef union");
+
+    depth = 0;
+  loop:
+    c = *cptr++;
+    putc_both(c);
+    switch (c)
+    {
+    case '\n':
+      next_line:
+       get_line();
+       if (line == 0)
+           unterminated_union(u_lineno, u_line, u_cptr);
+       goto loop;
+
+    case L_CURL:
+       ++depth;
+       goto loop;
+
+    case R_CURL:
+       if (--depth == 0)
+       {
+           puts_both(" YYSTYPE;\n");
+           puts_both("#endif /* !YYSTYPE_IS_DECLARED */\n");
+           FREE(u_line);
+           return;
+       }
+       goto loop;
+
+    case '\'':
+    case '"':
+       {
+           int s_lineno = lineno;
+           char *s_line = dup_line();
+           char *s_cptr = s_line + (cptr - line - 1);
+
+           quote = c;
+           for (;;)
+           {
+               c = *cptr++;
+               putc_both(c);
+               if (c == quote)
+               {
+                   FREE(s_line);
+                   goto loop;
+               }
+               if (c == '\n')
+                   unterminated_string(s_lineno, s_line, s_cptr);
+               if (c == '\\')
+               {
+                   c = *cptr++;
+                   putc_both(c);
+                   if (c == '\n')
+                   {
+                       get_line();
+                       if (line == 0)
+                           unterminated_string(s_lineno, s_line, s_cptr);
+                   }
+               }
+           }
+       }
+
+    case '/':
+       c = *cptr;
+       if (c == '/')
+       {
+           putc_both('*');
+           while ((c = *++cptr) != '\n')
+           {
+               if (c == '*' && cptr[1] == '/')
+               {
+                   puts_both("* ");
+               }
+               else
+               {
+                   putc_both(c);
+               }
+           }
+           puts_both("*/\n");
+           goto next_line;
+       }
+       if (c == '*')
+       {
+           int c_lineno = lineno;
+           char *c_line = dup_line();
+           char *c_cptr = c_line + (cptr - line - 1);
+
+           putc_both('*');
+           ++cptr;
+           for (;;)
+           {
+               c = *cptr++;
+               putc_both(c);
+               if (c == '*' && *cptr == '/')
+               {
+                   putc_both('/');
+                   ++cptr;
+                   FREE(c_line);
+                   goto loop;
+               }
+               if (c == '\n')
+               {
+                   get_line();
+                   if (line == 0)
+                       unterminated_comment(c_lineno, c_line, c_cptr);
+               }
+           }
+       }
+       goto loop;
+
+    default:
+       goto loop;
+    }
+}
+
+/*
+ * Keep a linked list of parameters
+ */
+static void
+copy_param(int k)
+{
+    char *buf;
+    int c;
+    param *head, *p;
+    int i;
+    int name, type2;
+
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (c != '{')
+       goto out;
+    cptr++;
+
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (c == '}')
+       goto out;
+
+    buf = TMALLOC(char, linesize);
+    NO_SPACE(buf);
+
+    for (i = 0; (c = *cptr++) != '}'; i++)
+    {
+       if (c == '\0')
+           missing_brace();
+       if (c == EOF)
+           unexpected_EOF();
+       buf[i] = (char)c;
+    }
+
+    if (i == 0)
+       goto out;
+
+    buf[i--] = '\0';
+    while (i >= 0 && isspace(UCH(buf[i])))
+       buf[i--] = '\0';
+
+    if (buf[i] == ']')
+    {
+       int level = 1;
+       while (i >= 0 && level > 0 && buf[i] != '[')
+       {
+           if (buf[i] == ']')
+               ++level;
+           else if (buf[i] == '[')
+               --level;
+           i--;
+       }
+       if (i <= 0)
+           unexpected_EOF();
+       type2 = i--;
+    }
+    else
+    {
+       type2 = i + 1;
+    }
+
+    while (i >= 0 && (isalnum(UCH(buf[i])) ||
+                     UCH(buf[i]) == '_'))
+       i--;
+
+    if (!isspace(UCH(buf[i])) && buf[i] != '*')
+       goto out;
+
+    name = i + 1;
+
+    p = TMALLOC(param, 1);
+    NO_SPACE(p);
+
+    p->type2 = strdup(buf + type2);
+    NO_SPACE(p->type2);
+
+    buf[type2] = '\0';
+
+    p->name = strdup(buf + name);
+    NO_SPACE(p->name);
+
+    buf[name] = '\0';
+    p->type = buf;
+
+    if (k == LEX_PARAM)
+       head = lex_param;
+    else
+       head = parse_param;
+
+    if (head != NULL)
+    {
+       while (head->next)
+           head = head->next;
+       head->next = p;
+    }
+    else
+    {
+       if (k == LEX_PARAM)
+           lex_param = p;
+       else
+           parse_param = p;
+    }
+    p->next = NULL;
+    return;
+
+  out:
+    syntax_error(lineno, line, cptr);
+}
+
+static int
+hexval(int c)
+{
+    if (c >= '0' && c <= '9')
+       return (c - '0');
+    if (c >= 'A' && c <= 'F')
+       return (c - 'A' + 10);
+    if (c >= 'a' && c <= 'f')
+       return (c - 'a' + 10);
+    return (-1);
+}
+
+static bucket *
+get_literal(void)
+{
+    int c, quote;
+    int i;
+    int n;
+    char *s;
+    bucket *bp;
+    int s_lineno = lineno;
+    char *s_line = dup_line();
+    char *s_cptr = s_line + (cptr - line);
+
+    quote = *cptr++;
+    cinc = 0;
+    for (;;)
+    {
+       c = *cptr++;
+       if (c == quote)
+           break;
+       if (c == '\n')
+           unterminated_string(s_lineno, s_line, s_cptr);
+       if (c == '\\')
+       {
+           char *c_cptr = cptr - 1;
+
+           c = *cptr++;
+           switch (c)
+           {
+           case '\n':
+               get_line();
+               if (line == 0)
+                   unterminated_string(s_lineno, s_line, s_cptr);
+               continue;
+
+           case '0':
+           case '1':
+           case '2':
+           case '3':
+           case '4':
+           case '5':
+           case '6':
+           case '7':
+               n = c - '0';
+               c = *cptr;
+               if (IS_OCTAL(c))
+               {
+                   n = (n << 3) + (c - '0');
+                   c = *++cptr;
+                   if (IS_OCTAL(c))
+                   {
+                       n = (n << 3) + (c - '0');
+                       ++cptr;
+                   }
+               }
+               if (n > MAXCHAR)
+                   illegal_character(c_cptr);
+               c = n;
+               break;
+
+           case 'x':
+               c = *cptr++;
+               n = hexval(c);
+               if (n < 0 || n >= 16)
+                   illegal_character(c_cptr);
+               for (;;)
+               {
+                   c = *cptr;
+                   i = hexval(c);
+                   if (i < 0 || i >= 16)
+                       break;
+                   ++cptr;
+                   n = (n << 4) + i;
+                   if (n > MAXCHAR)
+                       illegal_character(c_cptr);
+               }
+               c = n;
+               break;
+
+           case 'a':
+               c = 7;
+               break;
+           case 'b':
+               c = '\b';
+               break;
+           case 'f':
+               c = '\f';
+               break;
+           case 'n':
+               c = '\n';
+               break;
+           case 'r':
+               c = '\r';
+               break;
+           case 't':
+               c = '\t';
+               break;
+           case 'v':
+               c = '\v';
+               break;
+           }
+       }
+       cachec(c);
+    }
+    FREE(s_line);
+
+    n = cinc;
+    s = TMALLOC(char, n);
+    NO_SPACE(s);
+
+    for (i = 0; i < n; ++i)
+       s[i] = cache[i];
+
+    cinc = 0;
+    if (n == 1)
+       cachec('\'');
+    else
+       cachec('"');
+
+    for (i = 0; i < n; ++i)
+    {
+       c = UCH(s[i]);
+       if (c == '\\' || c == cache[0])
+       {
+           cachec('\\');
+           cachec(c);
+       }
+       else if (isprint(c))
+           cachec(c);
+       else
+       {
+           cachec('\\');
+           switch (c)
+           {
+           case 7:
+               cachec('a');
+               break;
+           case '\b':
+               cachec('b');
+               break;
+           case '\f':
+               cachec('f');
+               break;
+           case '\n':
+               cachec('n');
+               break;
+           case '\r':
+               cachec('r');
+               break;
+           case '\t':
+               cachec('t');
+               break;
+           case '\v':
+               cachec('v');
+               break;
+           default:
+               cachec(((c >> 6) & 7) + '0');
+               cachec(((c >> 3) & 7) + '0');
+               cachec((c & 7) + '0');
+               break;
+           }
+       }
+    }
+
+    if (n == 1)
+       cachec('\'');
+    else
+       cachec('"');
+
+    cachec(NUL);
+    bp = lookup(cache);
+    bp->class = TERM;
+    if (n == 1 && bp->value == UNDEFINED)
+       bp->value = UCH(*s);
+    FREE(s);
+
+    return (bp);
+}
+
+static int
+is_reserved(char *name)
+{
+    char *s;
+
+    if (strcmp(name, ".") == 0 ||
+       strcmp(name, "$accept") == 0 ||
+       strcmp(name, "$end") == 0)
+       return (1);
+
+    if (name[0] == '$' && name[1] == '$' && isdigit(UCH(name[2])))
+    {
+       s = name + 3;
+       while (isdigit(UCH(*s)))
+           ++s;
+       if (*s == NUL)
+           return (1);
+    }
+
+    return (0);
+}
+
+static bucket *
+get_name(void)
+{
+    int c;
+
+    cinc = 0;
+    for (c = *cptr; IS_IDENT(c); c = *++cptr)
+       cachec(c);
+    cachec(NUL);
+
+    if (is_reserved(cache))
+       used_reserved(cache);
+
+    return (lookup(cache));
+}
+
+static Value_t
+get_number(void)
+{
+    int c;
+    Value_t n;
+
+    n = 0;
+    for (c = *cptr; isdigit(c); c = *++cptr)
+       n = (Value_t) (10 * n + (c - '0'));
+
+    return (n);
+}
+
+static char *
+get_tag(void)
+{
+    int c;
+    int i;
+    char *s;
+    int t_lineno = lineno;
+    char *t_line = dup_line();
+    char *t_cptr = t_line + (cptr - line);
+
+    ++cptr;
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (!isalpha(c) && c != '_' && c != '$')
+       illegal_tag(t_lineno, t_line, t_cptr);
+
+    cinc = 0;
+    do
+    {
+       cachec(c);
+       c = *++cptr;
+    }
+    while (IS_IDENT(c));
+    cachec(NUL);
+
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (c != '>')
+       illegal_tag(t_lineno, t_line, t_cptr);
+    ++cptr;
+
+    for (i = 0; i < ntags; ++i)
+    {
+       if (strcmp(cache, tag_table[i]) == 0)
+       {
+           FREE(t_line);
+           return (tag_table[i]);
+       }
+    }
+
+    if (ntags >= tagmax)
+    {
+       tagmax += 16;
+       tag_table =
+           (tag_table
+            ? TREALLOC(char *, tag_table, tagmax)
+            : TMALLOC(char *, tagmax));
+       NO_SPACE(tag_table);
+    }
+
+    s = TMALLOC(char, cinc);
+    NO_SPACE(s);
+
+    strcpy(s, cache);
+    tag_table[ntags] = s;
+    ++ntags;
+    FREE(t_line);
+    return (s);
+}
+
+static void
+declare_tokens(int assoc)
+{
+    int c;
+    bucket *bp;
+    Value_t value;
+    char *tag = 0;
+
+    if (assoc != TOKEN)
+       ++prec;
+
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (c == '<')
+    {
+       tag = get_tag();
+       c = nextc();
+       if (c == EOF)
+           unexpected_EOF();
+    }
+
+    for (;;)
+    {
+       if (isalpha(c) || c == '_' || c == '.' || c == '$')
+           bp = get_name();
+       else if (c == '\'' || c == '"')
+           bp = get_literal();
+       else
+           return;
+
+       if (bp == goal)
+           tokenized_start(bp->name);
+       bp->class = TERM;
+
+       if (tag)
+       {
+           if (bp->tag && tag != bp->tag)
+               retyped_warning(bp->name);
+           bp->tag = tag;
+       }
+
+       if (assoc != TOKEN)
+       {
+           if (bp->prec && prec != bp->prec)
+               reprec_warning(bp->name);
+           bp->assoc = (Assoc_t) assoc;
+           bp->prec = prec;
+       }
+
+       c = nextc();
+       if (c == EOF)
+           unexpected_EOF();
+
+       if (isdigit(c))
+       {
+           value = get_number();
+           if (bp->value != UNDEFINED && value != bp->value)
+               revalued_warning(bp->name);
+           bp->value = value;
+           c = nextc();
+           if (c == EOF)
+               unexpected_EOF();
+       }
+    }
+}
+
+/*
+ * %expect requires special handling
+ * as it really isn't part of the yacc
+ * grammar only a flag for yacc proper.
+ */
+static void
+declare_expect(int assoc)
+{
+    int c;
+
+    if (assoc != EXPECT && assoc != EXPECT_RR)
+       ++prec;
+
+    /*
+     * Stay away from nextc - doesn't
+     * detect EOL and will read to EOF.
+     */
+    c = *++cptr;
+    if (c == EOF)
+       unexpected_EOF();
+
+    for (;;)
+    {
+       if (isdigit(c))
+       {
+           if (assoc == EXPECT)
+               SRexpect = get_number();
+           else
+               RRexpect = get_number();
+           break;
+       }
+       /*
+        * Looking for number before EOL.
+        * Spaces, tabs, and numbers are ok,
+        * words, punc., etc. are syntax errors.
+        */
+       else if (c == '\n' || isalpha(c) || !isspace(c))
+       {
+           syntax_error(lineno, line, cptr);
+       }
+       else
+       {
+           c = *++cptr;
+           if (c == EOF)
+               unexpected_EOF();
+       }
+    }
+}
+
+static void
+declare_types(void)
+{
+    int c;
+    bucket *bp;
+    char *tag;
+
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (c != '<')
+       syntax_error(lineno, line, cptr);
+    tag = get_tag();
+
+    for (;;)
+    {
+       c = nextc();
+       if (isalpha(c) || c == '_' || c == '.' || c == '$')
+           bp = get_name();
+       else if (c == '\'' || c == '"')
+           bp = get_literal();
+       else
+           return;
+
+       if (bp->tag && tag != bp->tag)
+           retyped_warning(bp->name);
+       bp->tag = tag;
+    }
+}
+
+static void
+declare_start(void)
+{
+    int c;
+    bucket *bp;
+
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (!isalpha(c) && c != '_' && c != '.' && c != '$')
+       syntax_error(lineno, line, cptr);
+    bp = get_name();
+    if (bp->class == TERM)
+       terminal_start(bp->name);
+    if (goal && goal != bp)
+       restarted_warning();
+    goal = bp;
+}
+
+static void
+read_declarations(void)
+{
+    int c, k;
+
+    cache_size = 256;
+    cache = TMALLOC(char, cache_size);
+    NO_SPACE(cache);
+
+    for (;;)
+    {
+       c = nextc();
+       if (c == EOF)
+           unexpected_EOF();
+       if (c != '%')
+           syntax_error(lineno, line, cptr);
+       switch (k = keyword())
+       {
+       case MARK:
+           return;
+
+       case IDENT:
+           copy_ident();
+           break;
+
+       case TEXT:
+           copy_text();
+           break;
+
+       case UNION:
+           copy_union();
+           break;
+
+       case TOKEN:
+       case LEFT:
+       case RIGHT:
+       case NONASSOC:
+           declare_tokens(k);
+           break;
+
+       case EXPECT:
+       case EXPECT_RR:
+           declare_expect(k);
+           break;
+
+       case TYPE:
+           declare_types();
+           break;
+
+       case START:
+           declare_start();
+           break;
+
+       case PURE_PARSER:
+           pure_parser = 1;
+           break;
+
+       case PARSE_PARAM:
+       case LEX_PARAM:
+           copy_param(k);
+           break;
+
+       case POSIX_YACC:
+           /* noop for bison compatibility. byacc is already designed to be posix
+            * yacc compatible. */
+           break;
+       }
+    }
+}
+
+static void
+initialize_grammar(void)
+{
+    nitems = 4;
+    maxitems = 300;
+
+    pitem = TMALLOC(bucket *, maxitems);
+    NO_SPACE(pitem);
+
+    pitem[0] = 0;
+    pitem[1] = 0;
+    pitem[2] = 0;
+    pitem[3] = 0;
+
+    nrules = 3;
+    maxrules = 100;
+
+    plhs = TMALLOC(bucket *, maxrules);
+    NO_SPACE(plhs);
+
+    plhs[0] = 0;
+    plhs[1] = 0;
+    plhs[2] = 0;
+
+    rprec = TMALLOC(Value_t, maxrules);
+    NO_SPACE(rprec);
+
+    rprec[0] = 0;
+    rprec[1] = 0;
+    rprec[2] = 0;
+
+    rassoc = TMALLOC(Assoc_t, maxrules);
+    NO_SPACE(rassoc);
+
+    rassoc[0] = TOKEN;
+    rassoc[1] = TOKEN;
+    rassoc[2] = TOKEN;
+}
+
+static void
+expand_items(void)
+{
+    maxitems += 300;
+    pitem = TREALLOC(bucket *, pitem, maxitems);
+    NO_SPACE(pitem);
+}
+
+static void
+expand_rules(void)
+{
+    maxrules += 100;
+
+    plhs = TREALLOC(bucket *, plhs, maxrules);
+    NO_SPACE(plhs);
+
+    rprec = TREALLOC(Value_t, rprec, maxrules);
+    NO_SPACE(rprec);
+
+    rassoc = TREALLOC(Assoc_t, rassoc, maxrules);
+    NO_SPACE(rassoc);
+}
+
+static void
+advance_to_start(void)
+{
+    int c;
+    bucket *bp;
+    char *s_cptr;
+    int s_lineno;
+
+    for (;;)
+    {
+       c = nextc();
+       if (c != '%')
+           break;
+       s_cptr = cptr;
+       switch (keyword())
+       {
+       case MARK:
+           no_grammar();
+
+       case TEXT:
+           copy_text();
+           break;
+
+       case START:
+           declare_start();
+           break;
+
+       default:
+           syntax_error(lineno, line, s_cptr);
+       }
+    }
+
+    c = nextc();
+    if (!isalpha(c) && c != '_' && c != '.' && c != '_')
+       syntax_error(lineno, line, cptr);
+    bp = get_name();
+    if (goal == 0)
+    {
+       if (bp->class == TERM)
+           terminal_start(bp->name);
+       goal = bp;
+    }
+
+    s_lineno = lineno;
+    c = nextc();
+    if (c == EOF)
+       unexpected_EOF();
+    if (c != ':')
+       syntax_error(lineno, line, cptr);
+    start_rule(bp, s_lineno);
+    ++cptr;
+}
+
+static void
+start_rule(bucket *bp, int s_lineno)
+{
+    if (bp->class == TERM)
+       terminal_lhs(s_lineno);
+    bp->class = NONTERM;
+    if (nrules >= maxrules)
+       expand_rules();
+    plhs[nrules] = bp;
+    rprec[nrules] = UNDEFINED;
+    rassoc[nrules] = TOKEN;
+}
+
+static void
+end_rule(void)
+{
+    int i;
+
+    if (!last_was_action && plhs[nrules]->tag)
+    {
+       if (pitem[nitems - 1])
+       {
+           for (i = nitems - 1; (i > 0) && pitem[i]; --i)
+               continue;
+           if (pitem[i + 1] == 0 || pitem[i + 1]->tag != plhs[nrules]->tag)
+               default_action_warning();
+       }
+       else
+       {
+           default_action_warning();
+       }
+    }
+
+    last_was_action = 0;
+    if (nitems >= maxitems)
+       expand_items();
+    pitem[nitems] = 0;
+    ++nitems;
+    ++nrules;
+}
+
+static void
+insert_empty_rule(void)
+{
+    bucket *bp, **bpp;
+
+    assert(cache);
+    sprintf(cache, "$$%d", ++gensym);
+    bp = make_bucket(cache);
+    last_symbol->next = bp;
+    last_symbol = bp;
+    bp->tag = plhs[nrules]->tag;
+    bp->class = NONTERM;
+
+    if ((nitems += 2) > maxitems)
+       expand_items();
+    bpp = pitem + nitems - 1;
+    *bpp-- = bp;
+    while ((bpp[0] = bpp[-1]) != 0)
+       --bpp;
+
+    if (++nrules >= maxrules)
+       expand_rules();
+    plhs[nrules] = plhs[nrules - 1];
+    plhs[nrules - 1] = bp;
+    rprec[nrules] = rprec[nrules - 1];
+    rprec[nrules - 1] = 0;
+    rassoc[nrules] = rassoc[nrules - 1];
+    rassoc[nrules - 1] = TOKEN;
+}
+
+static void
+add_symbol(void)
+{
+    int c;
+    bucket *bp;
+    int s_lineno = lineno;
+
+    c = *cptr;
+    if (c == '\'' || c == '"')
+       bp = get_literal();
+    else
+       bp = get_name();
+
+    c = nextc();
+    if (c == ':')
+    {
+       end_rule();
+       start_rule(bp, s_lineno);
+       ++cptr;
+       return;
+    }
+
+    if (last_was_action)
+       insert_empty_rule();
+    last_was_action = 0;
+
+    if (++nitems > maxitems)
+       expand_items();
+    pitem[nitems - 1] = bp;
+}
+
+static char *
+after_blanks(char *s)
+{
+    while (*s != '\0' && isspace(UCH(*s)))
+       ++s;
+    return s;
+}
+
+static void
+copy_action(void)
+{
+    int c;
+    int i, n;
+    int depth;
+    int quote;
+    char *tag;
+    FILE *f = action_file;
+    int a_lineno = lineno;
+    char *a_line = dup_line();
+    char *a_cptr = a_line + (cptr - line);
+
+    if (last_was_action)
+       insert_empty_rule();
+    last_was_action = 1;
+
+    fprintf(f, "case %d:\n", nrules - 2);
+    if (!lflag)
+       fprintf(f, line_format, lineno, input_file_name);
+    if (*cptr == '=')
+       ++cptr;
+
+    /* avoid putting curly-braces in first column, to ease editing */
+    if (*after_blanks(cptr) == L_CURL)
+    {
+       putc('\t', f);
+       cptr = after_blanks(cptr);
+    }
+
+    n = 0;
+    for (i = nitems - 1; pitem[i]; --i)
+       ++n;
+
+    depth = 0;
+  loop:
+    c = *cptr;
+    if (c == '$')
+    {
+       if (cptr[1] == '<')
+       {
+           int d_lineno = lineno;
+           char *d_line = dup_line();
+           char *d_cptr = d_line + (cptr - line);
+
+           ++cptr;
+           tag = get_tag();
+           c = *cptr;
+           if (c == '$')
+           {
+               fprintf(f, "yyval.%s", tag);
+               ++cptr;
+               FREE(d_line);
+               goto loop;
+           }
+           else if (isdigit(c))
+           {
+               i = get_number();
+               if (i > n)
+                   dollar_warning(d_lineno, i);
+               fprintf(f, "yystack.l_mark[%d].%s", i - n, tag);
+               FREE(d_line);
+               goto loop;
+           }
+           else if (c == '-' && isdigit(UCH(cptr[1])))
+           {
+               ++cptr;
+               i = -get_number() - n;
+               fprintf(f, "yystack.l_mark[%d].%s", i, tag);
+               FREE(d_line);
+               goto loop;
+           }
+           else
+               dollar_error(d_lineno, d_line, d_cptr);
+       }
+       else if (cptr[1] == '$')
+       {
+           if (ntags)
+           {
+               tag = plhs[nrules]->tag;
+               if (tag == 0)
+                   untyped_lhs();
+               fprintf(f, "yyval.%s", tag);
+           }
+           else
+               fprintf(f, "yyval");
+           cptr += 2;
+           goto loop;
+       }
+       else if (isdigit(UCH(cptr[1])))
+       {
+           ++cptr;
+           i = get_number();
+           if (ntags)
+           {
+               if (i <= 0 || i > n)
+                   unknown_rhs(i);
+               tag = pitem[nitems + i - n - 1]->tag;
+               if (tag == 0)
+                   untyped_rhs(i, pitem[nitems + i - n - 1]->name);
+               fprintf(f, "yystack.l_mark[%d].%s", i - n, tag);
+           }
+           else
+           {
+               if (i > n)
+                   dollar_warning(lineno, i);
+               fprintf(f, "yystack.l_mark[%d]", i - n);
+           }
+           goto loop;
+       }
+       else if (cptr[1] == '-')
+       {
+           cptr += 2;
+           i = get_number();
+           if (ntags)
+               unknown_rhs(-i);
+           fprintf(f, "yystack.l_mark[%d]", -i - n);
+           goto loop;
+       }
+    }
+    if (isalpha(c) || c == '_' || c == '$')
+    {
+       do
+       {
+           putc(c, f);
+           c = *++cptr;
+       }
+       while (isalnum(c) || c == '_' || c == '$');
+       goto loop;
+    }
+    putc(c, f);
+    ++cptr;
+    switch (c)
+    {
+    case '\n':
+      next_line:
+       get_line();
+       if (line)
+           goto loop;
+       unterminated_action(a_lineno, a_line, a_cptr);
+
+    case ';':
+       if (depth > 0)
+           goto loop;
+       fprintf(f, "\nbreak;\n");
+       free(a_line);
+       return;
+
+    case L_CURL:
+       ++depth;
+       goto loop;
+
+    case R_CURL:
+       if (--depth > 0)
+           goto loop;
+       fprintf(f, "\nbreak;\n");
+       free(a_line);
+       return;
+
+    case '\'':
+    case '"':
+       {
+           int s_lineno = lineno;
+           char *s_line = dup_line();
+           char *s_cptr = s_line + (cptr - line - 1);
+
+           quote = c;
+           for (;;)
+           {
+               c = *cptr++;
+               putc(c, f);
+               if (c == quote)
+               {
+                   FREE(s_line);
+                   goto loop;
+               }
+               if (c == '\n')
+                   unterminated_string(s_lineno, s_line, s_cptr);
+               if (c == '\\')
+               {
+                   c = *cptr++;
+                   putc(c, f);
+                   if (c == '\n')
+                   {
+                       get_line();
+                       if (line == 0)
+                           unterminated_string(s_lineno, s_line, s_cptr);
+                   }
+               }
+           }
+       }
+
+    case '/':
+       c = *cptr;
+       if (c == '/')
+       {
+           putc('*', f);
+           while ((c = *++cptr) != '\n')
+           {
+               if (c == '*' && cptr[1] == '/')
+                   fprintf(f, "* ");
+               else
+                   putc(c, f);
+           }
+           fprintf(f, "*/\n");
+           goto next_line;
+       }
+       if (c == '*')
+       {
+           int c_lineno = lineno;
+           char *c_line = dup_line();
+           char *c_cptr = c_line + (cptr - line - 1);
+
+           putc('*', f);
+           ++cptr;
+           for (;;)
+           {
+               c = *cptr++;
+               putc(c, f);
+               if (c == '*' && *cptr == '/')
+               {
+                   putc('/', f);
+                   ++cptr;
+                   FREE(c_line);
+                   goto loop;
+               }
+               if (c == '\n')
+               {
+                   get_line();
+                   if (line == 0)
+                       unterminated_comment(c_lineno, c_line, c_cptr);
+               }
+           }
+       }
+       goto loop;
+
+    default:
+       goto loop;
+    }
+}
+
+static int
+mark_symbol(void)
+{
+    int c;
+    bucket *bp = NULL;
+
+    c = cptr[1];
+    if (c == '%' || c == '\\')
+    {
+       cptr += 2;
+       return (1);
+    }
+
+    if (c == '=')
+       cptr += 2;
+    else if ((c == 'p' || c == 'P') &&
+            ((c = cptr[2]) == 'r' || c == 'R') &&
+            ((c = cptr[3]) == 'e' || c == 'E') &&
+            ((c = cptr[4]) == 'c' || c == 'C') &&
+            ((c = cptr[5], !IS_IDENT(c))))
+       cptr += 5;
+    else
+       syntax_error(lineno, line, cptr);
+
+    c = nextc();
+    if (isalpha(c) || c == '_' || c == '.' || c == '$')
+       bp = get_name();
+    else if (c == '\'' || c == '"')
+       bp = get_literal();
+    else
+    {
+       syntax_error(lineno, line, cptr);
+       /*NOTREACHED */
+    }
+
+    if (rprec[nrules] != UNDEFINED && bp->prec != rprec[nrules])
+       prec_redeclared();
+
+    rprec[nrules] = bp->prec;
+    rassoc[nrules] = bp->assoc;
+    return (0);
+}
+
+static void
+read_grammar(void)
+{
+    int c;
+
+    initialize_grammar();
+    advance_to_start();
+
+    for (;;)
+    {
+       c = nextc();
+       if (c == EOF)
+           break;
+       if (isalpha(c)
+           || c == '_'
+           || c == '.'
+           || c == '$'
+           || c == '\''
+           || c == '"')
+           add_symbol();
+       else if (c == L_CURL || c == '=')
+           copy_action();
+       else if (c == '|')
+       {
+           end_rule();
+           start_rule(plhs[nrules - 1], 0);
+           ++cptr;
+       }
+       else if (c == '%')
+       {
+           if (mark_symbol())
+               break;
+       }
+       else
+           syntax_error(lineno, line, cptr);
+    }
+    end_rule();
+}
+
+static void
+free_tags(void)
+{
+    int i;
+
+    if (tag_table == 0)
+       return;
+
+    for (i = 0; i < ntags; ++i)
+    {
+       assert(tag_table[i]);
+       FREE(tag_table[i]);
+    }
+    FREE(tag_table);
+}
+
+static void
+pack_names(void)
+{
+    bucket *bp;
+    char *p, *s, *t;
+
+    name_pool_size = 13;       /* 13 == sizeof("$end") + sizeof("$accept") */
+    for (bp = first_symbol; bp; bp = bp->next)
+       name_pool_size += strlen(bp->name) + 1;
+
+    name_pool = TMALLOC(char, name_pool_size);
+    NO_SPACE(name_pool);
+
+    strcpy(name_pool, "$accept");
+    strcpy(name_pool + 8, "$end");
+    t = name_pool + 13;
+    for (bp = first_symbol; bp; bp = bp->next)
+    {
+       p = t;
+       s = bp->name;
+       while ((*t++ = *s++) != 0)
+           continue;
+       FREE(bp->name);
+       bp->name = p;
+    }
+}
+
+static void
+check_symbols(void)
+{
+    bucket *bp;
+
+    if (goal->class == UNKNOWN)
+       undefined_goal(goal->name);
+
+    for (bp = first_symbol; bp; bp = bp->next)
+    {
+       if (bp->class == UNKNOWN)
+       {
+           undefined_symbol_warning(bp->name);
+           bp->class = TERM;
+       }
+    }
+}
+
+static void
+protect_string(char *src, char **des)
+{
+    unsigned len;
+    char *s;
+    char *d;
+
+    *des = src;
+    if (src)
+    {
+       len = 1;
+       s = src;
+       while (*s)
+       {
+           if ('\\' == *s || '"' == *s)
+               len++;
+           s++;
+           len++;
+       }
+
+       *des = d = TMALLOC(char, len);
+       NO_SPACE(d);
+
+       s = src;
+       while (*s)
+       {
+           if ('\\' == *s || '"' == *s)
+               *d++ = '\\';
+           *d++ = *s++;
+       }
+       *d = '\0';
+    }
+}
+
+static void
+pack_symbols(void)
+{
+    bucket *bp;
+    bucket **v;
+    Value_t i, j, k, n;
+
+    nsyms = 2;
+    ntokens = 1;
+    for (bp = first_symbol; bp; bp = bp->next)
+    {
+       ++nsyms;
+       if (bp->class == TERM)
+           ++ntokens;
+    }
+    start_symbol = (Value_t) ntokens;
+    nvars = nsyms - ntokens;
+
+    symbol_name = TMALLOC(char *, nsyms);
+    NO_SPACE(symbol_name);
+
+    symbol_value = TMALLOC(Value_t, nsyms);
+    NO_SPACE(symbol_value);
+
+    symbol_prec = TMALLOC(short, nsyms);
+    NO_SPACE(symbol_prec);
+
+    symbol_assoc = TMALLOC(char, nsyms);
+    NO_SPACE(symbol_assoc);
+
+    v = TMALLOC(bucket *, nsyms);
+    NO_SPACE(v);
+
+    v[0] = 0;
+    v[start_symbol] = 0;
+
+    i = 1;
+    j = (Value_t) (start_symbol + 1);
+    for (bp = first_symbol; bp; bp = bp->next)
+    {
+       if (bp->class == TERM)
+           v[i++] = bp;
+       else
+           v[j++] = bp;
+    }
+    assert(i == ntokens && j == nsyms);
+
+    for (i = 1; i < ntokens; ++i)
+       v[i]->index = i;
+
+    goal->index = (Index_t) (start_symbol + 1);
+    k = (Value_t) (start_symbol + 2);
+    while (++i < nsyms)
+       if (v[i] != goal)
+       {
+           v[i]->index = k;
+           ++k;
+       }
+
+    goal->value = 0;
+    k = 1;
+    for (i = (Value_t) (start_symbol + 1); i < nsyms; ++i)
+    {
+       if (v[i] != goal)
+       {
+           v[i]->value = k;
+           ++k;
+       }
+    }
+
+    k = 0;
+    for (i = 1; i < ntokens; ++i)
+    {
+       n = v[i]->value;
+       if (n > 256)
+       {
+           for (j = k++; j > 0 && symbol_value[j - 1] > n; --j)
+               symbol_value[j] = symbol_value[j - 1];
+           symbol_value[j] = n;
+       }
+    }
+
+    assert(v[1] != 0);
+
+    if (v[1]->value == UNDEFINED)
+       v[1]->value = 256;
+
+    j = 0;
+    n = 257;
+    for (i = 2; i < ntokens; ++i)
+    {
+       if (v[i]->value == UNDEFINED)
+       {
+           while (j < k && n == symbol_value[j])
+           {
+               while (++j < k && n == symbol_value[j])
+                   continue;
+               ++n;
+           }
+           v[i]->value = n;
+           ++n;
+       }
+    }
+
+    symbol_name[0] = name_pool + 8;
+    symbol_value[0] = 0;
+    symbol_prec[0] = 0;
+    symbol_assoc[0] = TOKEN;
+    for (i = 1; i < ntokens; ++i)
+    {
+       symbol_name[i] = v[i]->name;
+       symbol_value[i] = v[i]->value;
+       symbol_prec[i] = v[i]->prec;
+       symbol_assoc[i] = v[i]->assoc;
+    }
+    symbol_name[start_symbol] = name_pool;
+    symbol_value[start_symbol] = -1;
+    symbol_prec[start_symbol] = 0;
+    symbol_assoc[start_symbol] = TOKEN;
+    for (++i; i < nsyms; ++i)
+    {
+       k = v[i]->index;
+       symbol_name[k] = v[i]->name;
+       symbol_value[k] = v[i]->value;
+       symbol_prec[k] = v[i]->prec;
+       symbol_assoc[k] = v[i]->assoc;
+    }
+
+    if (gflag)
+    {
+       symbol_pname = TMALLOC(char *, nsyms);
+       NO_SPACE(symbol_pname);
+
+       for (i = 0; i < nsyms; ++i)
+           protect_string(symbol_name[i], &(symbol_pname[i]));
+    }
+
+    FREE(v);
+}
+
+static void
+pack_grammar(void)
+{
+    int i;
+    Value_t j;
+    Assoc_t assoc;
+    Value_t prec2;
+
+    ritem = TMALLOC(Value_t, nitems);
+    NO_SPACE(ritem);
+
+    rlhs = TMALLOC(Value_t, nrules);
+    NO_SPACE(rlhs);
+
+    rrhs = TMALLOC(Value_t, nrules + 1);
+    NO_SPACE(rrhs);
+
+    rprec = TREALLOC(Value_t, rprec, nrules);
+    NO_SPACE(rprec);
+
+    rassoc = TREALLOC(Assoc_t, rassoc, nrules);
+    NO_SPACE(rassoc);
+
+    ritem[0] = -1;
+    ritem[1] = goal->index;
+    ritem[2] = 0;
+    ritem[3] = -2;
+    rlhs[0] = 0;
+    rlhs[1] = 0;
+    rlhs[2] = start_symbol;
+    rrhs[0] = 0;
+    rrhs[1] = 0;
+    rrhs[2] = 1;
+
+    j = 4;
+    for (i = 3; i < nrules; ++i)
+    {
+       rlhs[i] = plhs[i]->index;
+       rrhs[i] = j;
+       assoc = TOKEN;
+       prec2 = 0;
+       while (pitem[j])
+       {
+           ritem[j] = pitem[j]->index;
+           if (pitem[j]->class == TERM)
+           {
+               prec2 = pitem[j]->prec;
+               assoc = pitem[j]->assoc;
+           }
+           ++j;
+       }
+       ritem[j] = (Value_t) - i;
+       ++j;
+       if (rprec[i] == UNDEFINED)
+       {
+           rprec[i] = prec2;
+           rassoc[i] = assoc;
+       }
+    }
+    rrhs[i] = j;
+
+    FREE(plhs);
+    FREE(pitem);
+}
+
+static void
+print_grammar(void)
+{
+    int i, k;
+    size_t j, spacing = 0;
+    FILE *f = verbose_file;
+
+    if (!vflag)
+       return;
+
+    k = 1;
+    for (i = 2; i < nrules; ++i)
+    {
+       if (rlhs[i] != rlhs[i - 1])
+       {
+           if (i != 2)
+               fprintf(f, "\n");
+           fprintf(f, "%4d  %s :", i - 2, symbol_name[rlhs[i]]);
+           spacing = strlen(symbol_name[rlhs[i]]) + 1;
+       }
+       else
+       {
+           fprintf(f, "%4d  ", i - 2);
+           j = spacing;
+           while (j-- != 0)
+               putc(' ', f);
+           putc('|', f);
+       }
+
+       while (ritem[k] >= 0)
+       {
+           fprintf(f, " %s", symbol_name[ritem[k]]);
+           ++k;
+       }
+       ++k;
+       putc('\n', f);
+    }
+}
+
+void
+reader(void)
+{
+    write_section(code_file, banner);
+    create_symbol_table();
+    read_declarations();
+    read_grammar();
+    free_symbol_table();
+    free_tags();
+    pack_names();
+    check_symbols();
+    pack_symbols();
+    pack_grammar();
+    free_symbols();
+    print_grammar();
+}
+
+#ifdef NO_LEAKS
+static param *
+free_declarations(param * list)
+{
+    while (list != 0)
+    {
+       param *next = list->next;
+       free(list->type);
+       free(list->name);
+       free(list->type2);
+       free(list);
+       list = next;
+    }
+    return list;
+}
+
+void
+reader_leaks(void)
+{
+    lex_param = free_declarations(lex_param);
+    parse_param = free_declarations(parse_param);
+
+    DO_FREE(line);
+    DO_FREE(rrhs);
+    DO_FREE(rlhs);
+    DO_FREE(rprec);
+    DO_FREE(ritem);
+    DO_FREE(rassoc);
+    DO_FREE(cache);
+    DO_FREE(name_pool);
+    DO_FREE(symbol_name);
+    DO_FREE(symbol_prec);
+    DO_FREE(symbol_assoc);
+    DO_FREE(symbol_value);
+}
+#endif
diff --git a/contrib/byacc/skeleton.c b/contrib/byacc/skeleton.c
new file mode 100644 (file)
index 0000000..48ae694
--- /dev/null
@@ -0,0 +1,439 @@
+/* $Id: skeleton.c,v 1.31 2011/09/07 09:37:59 tom Exp $ */
+
+#include "defs.h"
+
+/*  The definition of yysccsid in the banner should be replaced with   */
+/*  a #pragma ident directive if the target C compiler supports                */
+/*  #pragma ident directives.                                          */
+/*                                                                     */
+/*  If the skeleton is changed, the banner should be changed so that   */
+/*  the altered version can be easily distinguished from the original. */
+/*                                                                     */
+/*  The #defines included with the banner are there because they are   */
+/*  useful in subsequent code.  The macros #defined in the header or   */
+/*  the body either are not useful outside of semantic actions or      */
+/*  are conditional.                                                   */
+
+const char *const banner[] =
+{
+    "#ifndef lint",
+    "static const char yysccsid[] = \"@(#)yaccpar      1.9 (Berkeley) 02/21/93\";",
+    "#endif",
+    "",
+    "#define YYBYACC 1",
+    CONCAT1("#define YYMAJOR ", YYMAJOR),
+    CONCAT1("#define YYMINOR ", YYMINOR),
+#ifdef YYPATCH
+    CONCAT1("#define YYPATCH ", YYPATCH),
+#endif
+    "",
+    "#define YYEMPTY        (-1)",
+    "#define yyclearin      (yychar = YYEMPTY)",
+    "#define yyerrok        (yyerrflag = 0)",
+    "#define YYRECOVERING() (yyerrflag != 0)",
+    "",
+    0
+};
+
+const char *const xdecls[] =
+{
+    "",
+    "extern int YYPARSE_DECL();",
+    0
+};
+
+const char *const tables[] =
+{
+    "extern short yylhs[];",
+    "extern short yylen[];",
+    "extern short yydefred[];",
+    "extern short yydgoto[];",
+    "extern short yysindex[];",
+    "extern short yyrindex[];",
+    "extern short yygindex[];",
+    "extern short yytable[];",
+    "extern short yycheck[];",
+    "",
+    "#if YYDEBUG",
+    "extern char *yyname[];",
+    "extern char *yyrule[];",
+    "#endif",
+    0
+};
+
+const char *const global_vars[] =
+{
+    "",
+    "int      yydebug;",
+    "int      yynerrs;",
+    0
+};
+
+const char *const impure_vars[] =
+{
+    "",
+    "int      yyerrflag;",
+    "int      yychar;",
+    "YYSTYPE  yyval;",
+    "YYSTYPE  yylval;",
+    0
+};
+
+const char *const hdr_defs[] =
+{
+    "",
+    "/* define the initial stack-sizes */",
+    "#ifdef YYSTACKSIZE",
+    "#undef YYMAXDEPTH",
+    "#define YYMAXDEPTH  YYSTACKSIZE",
+    "#else",
+    "#ifdef YYMAXDEPTH",
+    "#define YYSTACKSIZE YYMAXDEPTH",
+    "#else",
+    "#define YYSTACKSIZE 500",
+    "#define YYMAXDEPTH  500",
+    "#endif",
+    "#endif",
+    "",
+    "#define YYINITSTACKSIZE 500",
+    "",
+    "typedef struct {",
+    "    unsigned stacksize;",
+    "    short    *s_base;",
+    "    short    *s_mark;",
+    "    short    *s_last;",
+    "    YYSTYPE  *l_base;",
+    "    YYSTYPE  *l_mark;",
+    "} YYSTACKDATA;",
+    0
+};
+
+const char *const hdr_vars[] =
+{
+    "/* variables for the parser stack */",
+    "static YYSTACKDATA yystack;",
+    0
+};
+
+const char *const body_vars[] =
+{
+    "    int      yyerrflag;",
+    "    int      yychar;",
+    "    YYSTYPE  yyval;",
+    "    YYSTYPE  yylval;",
+    "",
+    "    /* variables for the parser stack */",
+    "    YYSTACKDATA yystack;",
+    0
+};
+
+const char *const body_1[] =
+{
+    "",
+    "#if YYDEBUG",
+    "#include <stdio.h>                /* needed for printf */",
+    "#endif",
+    "",
+    "#include <stdlib.h>       /* needed for malloc, etc */",
+    "#include <string.h>       /* needed for memset */",
+    "",
+    "/* allocate initial stack or double stack size, up to YYMAXDEPTH */",
+    "static int yygrowstack(YYSTACKDATA *data)",
+    "{",
+    "    int i;",
+    "    unsigned newsize;",
+    "    short *newss;",
+    "    YYSTYPE *newvs;",
+    "",
+    "    if ((newsize = data->stacksize) == 0)",
+    "        newsize = YYINITSTACKSIZE;",
+    "    else if (newsize >= YYMAXDEPTH)",
+    "        return -1;",
+    "    else if ((newsize *= 2) > YYMAXDEPTH)",
+    "        newsize = YYMAXDEPTH;",
+    "",
+    "    i = data->s_mark - data->s_base;",
+    "    newss = (short *)realloc(data->s_base, newsize * sizeof(*newss));",
+    "    if (newss == 0)",
+    "        return -1;",
+    "",
+    "    data->s_base = newss;",
+    "    data->s_mark = newss + i;",
+    "",
+    "    newvs = (YYSTYPE *)realloc(data->l_base, newsize * sizeof(*newvs));",
+    "    if (newvs == 0)",
+    "        return -1;",
+    "",
+    "    data->l_base = newvs;",
+    "    data->l_mark = newvs + i;",
+    "",
+    "    data->stacksize = newsize;",
+    "    data->s_last = data->s_base + newsize - 1;",
+    "    return 0;",
+    "}",
+    "",
+    "#if YYPURE || defined(YY_NO_LEAKS)",
+    "static void yyfreestack(YYSTACKDATA *data)",
+    "{",
+    "    free(data->s_base);",
+    "    free(data->l_base);",
+    "    memset(data, 0, sizeof(*data));",
+    "}",
+    "#else",
+    "#define yyfreestack(data) /* nothing */",
+    "#endif",
+    "",
+    "#define YYABORT  goto yyabort",
+    "#define YYREJECT goto yyabort",
+    "#define YYACCEPT goto yyaccept",
+    "#define YYERROR  goto yyerrlab",
+    "",
+    "int",
+    "YYPARSE_DECL()",
+    "{",
+    0
+};
+
+const char *const body_2[] =
+{
+    "    int yym, yyn, yystate;",
+    "#if YYDEBUG",
+    "    const char *yys;",
+    "",
+    "    if ((yys = getenv(\"YYDEBUG\")) != 0)",
+    "    {",
+    "        yyn = *yys;",
+    "        if (yyn >= '0' && yyn <= '9')",
+    "            yydebug = yyn - '0';",
+    "    }",
+    "#endif",
+    "",
+    "    yynerrs = 0;",
+    "    yyerrflag = 0;",
+    "    yychar = YYEMPTY;",
+    "    yystate = 0;",
+    "",
+    "#if YYPURE",
+    "    memset(&yystack, 0, sizeof(yystack));",
+    "#endif",
+    "",
+    "    if (yystack.s_base == NULL && yygrowstack(&yystack)) goto yyoverflow;",
+    "    yystack.s_mark = yystack.s_base;",
+    "    yystack.l_mark = yystack.l_base;",
+    "    yystate = 0;",
+    "    *yystack.s_mark = 0;",
+    "",
+    "yyloop:",
+    "    if ((yyn = yydefred[yystate]) != 0) goto yyreduce;",
+    "    if (yychar < 0)",
+    "    {",
+    "        if ((yychar = YYLEX) < 0) yychar = 0;",
+    "#if YYDEBUG",
+    "        if (yydebug)",
+    "        {",
+    "            yys = 0;",
+    "            if (yychar <= YYMAXTOKEN) yys = yyname[yychar];",
+    "            if (!yys) yys = \"illegal-symbol\";",
+    "            printf(\"%sdebug: state %d, reading %d (%s)\\n\",",
+    "                    YYPREFIX, yystate, yychar, yys);",
+    "        }",
+    "#endif",
+    "    }",
+    "    if ((yyn = yysindex[yystate]) && (yyn += yychar) >= 0 &&",
+    "            yyn <= YYTABLESIZE && yycheck[yyn] == yychar)",
+    "    {",
+    "#if YYDEBUG",
+    "        if (yydebug)",
+    "            printf(\"%sdebug: state %d, shifting to state %d\\n\",",
+    "                    YYPREFIX, yystate, yytable[yyn]);",
+    "#endif",
+    "        if (yystack.s_mark >= yystack.s_last && yygrowstack(&yystack))",
+    "        {",
+    "            goto yyoverflow;",
+    "        }",
+    "        yystate = yytable[yyn];",
+    "        *++yystack.s_mark = yytable[yyn];",
+    "        *++yystack.l_mark = yylval;",
+    "        yychar = YYEMPTY;",
+    "        if (yyerrflag > 0)  --yyerrflag;",
+    "        goto yyloop;",
+    "    }",
+    "    if ((yyn = yyrindex[yystate]) && (yyn += yychar) >= 0 &&",
+    "            yyn <= YYTABLESIZE && yycheck[yyn] == yychar)",
+    "    {",
+    "        yyn = yytable[yyn];",
+    "        goto yyreduce;",
+    "    }",
+    "    if (yyerrflag) goto yyinrecovery;",
+    "",
+    0
+};
+
+const char *const body_3[] =
+{
+    "",
+    "    goto yyerrlab;",
+    "",
+    "yyerrlab:",
+    "    ++yynerrs;",
+    "",
+    "yyinrecovery:",
+    "    if (yyerrflag < 3)",
+    "    {",
+    "        yyerrflag = 3;",
+    "        for (;;)",
+    "        {",
+    "            if ((yyn = yysindex[*yystack.s_mark]) && (yyn += YYERRCODE) >= 0 &&",
+    "                    yyn <= YYTABLESIZE && yycheck[yyn] == YYERRCODE)",
+    "            {",
+    "#if YYDEBUG",
+    "                if (yydebug)",
+    "                    printf(\"%sdebug: state %d, error recovery shifting\\",
+    " to state %d\\n\", YYPREFIX, *yystack.s_mark, yytable[yyn]);",
+    "#endif",
+    "                if (yystack.s_mark >= yystack.s_last && yygrowstack(&yystack))",
+    "                {",
+    "                    goto yyoverflow;",
+    "                }",
+    "                yystate = yytable[yyn];",
+    "                *++yystack.s_mark = yytable[yyn];",
+    "                *++yystack.l_mark = yylval;",
+    "                goto yyloop;",
+    "            }",
+    "            else",
+    "            {",
+    "#if YYDEBUG",
+    "                if (yydebug)",
+    "                    printf(\"%sdebug: error recovery discarding state %d\
+\\n\",",
+    "                            YYPREFIX, *yystack.s_mark);",
+    "#endif",
+    "                if (yystack.s_mark <= yystack.s_base) goto yyabort;",
+    "                --yystack.s_mark;",
+    "                --yystack.l_mark;",
+    "            }",
+    "        }",
+    "    }",
+    "    else",
+    "    {",
+    "        if (yychar == 0) goto yyabort;",
+    "#if YYDEBUG",
+    "        if (yydebug)",
+    "        {",
+    "            yys = 0;",
+    "            if (yychar <= YYMAXTOKEN) yys = yyname[yychar];",
+    "            if (!yys) yys = \"illegal-symbol\";",
+    "            printf(\"%sdebug: state %d, error recovery discards token %d\
+ (%s)\\n\",",
+    "                    YYPREFIX, yystate, yychar, yys);",
+    "        }",
+    "#endif",
+    "        yychar = YYEMPTY;",
+    "        goto yyloop;",
+    "    }",
+    "",
+    "yyreduce:",
+    "#if YYDEBUG",
+    "    if (yydebug)",
+    "        printf(\"%sdebug: state %d, reducing by rule %d (%s)\\n\",",
+    "                YYPREFIX, yystate, yyn, yyrule[yyn]);",
+    "#endif",
+    "    yym = yylen[yyn];",
+    "    if (yym)",
+    "        yyval = yystack.l_mark[1-yym];",
+    "    else",
+    "        memset(&yyval, 0, sizeof yyval);",
+    "    switch (yyn)",
+    "    {",
+    0
+};
+
+const char *const trailer[] =
+{
+    "    }",
+    "    yystack.s_mark -= yym;",
+    "    yystate = *yystack.s_mark;",
+    "    yystack.l_mark -= yym;",
+    "    yym = yylhs[yyn];",
+    "    if (yystate == 0 && yym == 0)",
+    "    {",
+    "#if YYDEBUG",
+    "        if (yydebug)",
+    "            printf(\"%sdebug: after reduction, shifting from state 0 to\\",
+    " state %d\\n\", YYPREFIX, YYFINAL);",
+    "#endif",
+    "        yystate = YYFINAL;",
+    "        *++yystack.s_mark = YYFINAL;",
+    "        *++yystack.l_mark = yyval;",
+    "        if (yychar < 0)",
+    "        {",
+    "            if ((yychar = YYLEX) < 0) yychar = 0;",
+    "#if YYDEBUG",
+    "            if (yydebug)",
+    "            {",
+    "                yys = 0;",
+    "                if (yychar <= YYMAXTOKEN) yys = yyname[yychar];",
+    "                if (!yys) yys = \"illegal-symbol\";",
+    "                printf(\"%sdebug: state %d, reading %d (%s)\\n\",",
+    "                        YYPREFIX, YYFINAL, yychar, yys);",
+    "            }",
+    "#endif",
+    "        }",
+    "        if (yychar == 0) goto yyaccept;",
+    "        goto yyloop;",
+    "    }",
+    "    if ((yyn = yygindex[yym]) && (yyn += yystate) >= 0 &&",
+    "            yyn <= YYTABLESIZE && yycheck[yyn] == yystate)",
+    "        yystate = yytable[yyn];",
+    "    else",
+    "        yystate = yydgoto[yym];",
+    "#if YYDEBUG",
+    "    if (yydebug)",
+    "        printf(\"%sdebug: after reduction, shifting from state %d \\",
+    "to state %d\\n\", YYPREFIX, *yystack.s_mark, yystate);",
+    "#endif",
+    "    if (yystack.s_mark >= yystack.s_last && yygrowstack(&yystack))",
+    "    {",
+    "        goto yyoverflow;",
+    "    }",
+    "    *++yystack.s_mark = (short) yystate;",
+    "    *++yystack.l_mark = yyval;",
+    "    goto yyloop;",
+    "",
+    "yyoverflow:",
+    0
+};
+
+const char *const trailer_2[] =
+{
+    "",
+    "yyabort:",
+    "    yyfreestack(&yystack);",
+    "    return (1);",
+    "",
+    "yyaccept:",
+    "    yyfreestack(&yystack);",
+    "    return (0);",
+    "}",
+    0
+};
+
+void
+write_section(FILE * fp, const char *const section[])
+{
+    int c;
+    int i;
+    const char *s;
+
+    for (i = 0; (s = section[i]) != 0; ++i)
+    {
+       while ((c = *s) != 0)
+       {
+           putc(c, fp);
+           ++s;
+       }
+       if (fp == code_file)
+           ++outline;
+       putc('\n', fp);
+    }
+}
diff --git a/contrib/byacc/symtab.c b/contrib/byacc/symtab.c
new file mode 100644 (file)
index 0000000..9839180
--- /dev/null
@@ -0,0 +1,117 @@
+/* $Id: symtab.c,v 1.10 2012/05/26 15:16:12 tom Exp $ */
+
+#include "defs.h"
+
+/* TABLE_SIZE is the number of entries in the symbol table. */
+/* TABLE_SIZE must be a power of two.                      */
+
+#define        TABLE_SIZE 1024
+
+static bucket **symbol_table = 0;
+bucket *first_symbol;
+bucket *last_symbol;
+
+static int
+hash(const char *name)
+{
+    const char *s;
+    int c, k;
+
+    assert(name && *name);
+    s = name;
+    k = *s;
+    while ((c = *++s) != 0)
+       k = (31 * k + c) & (TABLE_SIZE - 1);
+
+    return (k);
+}
+
+bucket *
+make_bucket(const char *name)
+{
+    bucket *bp;
+
+    assert(name != 0);
+
+    bp = TMALLOC(bucket, 1);
+    NO_SPACE(bp);
+
+    bp->link = 0;
+    bp->next = 0;
+
+    bp->name = TMALLOC(char, strlen(name) + 1);
+    NO_SPACE(bp->name);
+
+    bp->tag = 0;
+    bp->value = UNDEFINED;
+    bp->index = 0;
+    bp->prec = 0;
+    bp->class = UNKNOWN;
+    bp->assoc = TOKEN;
+    strcpy(bp->name, name);
+
+    return (bp);
+}
+
+bucket *
+lookup(const char *name)
+{
+    bucket *bp, **bpp;
+
+    bpp = symbol_table + hash(name);
+    bp = *bpp;
+
+    while (bp)
+    {
+       if (strcmp(name, bp->name) == 0)
+           return (bp);
+       bpp = &bp->link;
+       bp = *bpp;
+    }
+
+    *bpp = bp = make_bucket(name);
+    last_symbol->next = bp;
+    last_symbol = bp;
+
+    return (bp);
+}
+
+void
+create_symbol_table(void)
+{
+    int i;
+    bucket *bp;
+
+    symbol_table = TMALLOC(bucket *, TABLE_SIZE);
+    NO_SPACE(symbol_table);
+
+    for (i = 0; i < TABLE_SIZE; i++)
+       symbol_table[i] = 0;
+
+    bp = make_bucket("error");
+    bp->index = 1;
+    bp->class = TERM;
+
+    first_symbol = bp;
+    last_symbol = bp;
+    symbol_table[hash("error")] = bp;
+}
+
+void
+free_symbol_table(void)
+{
+    FREE(symbol_table);
+    symbol_table = 0;
+}
+
+void
+free_symbols(void)
+{
+    bucket *p, *q;
+
+    for (p = first_symbol; p; p = q)
+    {
+       q = p->next;
+       FREE(p);
+    }
+}
diff --git a/contrib/byacc/verbose.c b/contrib/byacc/verbose.c
new file mode 100644 (file)
index 0000000..3e6ea28
--- /dev/null
@@ -0,0 +1,334 @@
+/* $Id: verbose.c,v 1.10 2012/05/26 00:45:17 tom Exp $ */
+
+#include "defs.h"
+
+static void log_conflicts(void);
+static void log_unused(void);
+static void print_actions(int stateno);
+static void print_conflicts(int state);
+static void print_core(int state);
+static void print_gotos(int stateno);
+static void print_nulls(int state);
+static void print_shifts(action *p);
+static void print_state(int state);
+static void print_reductions(action *p, int defred2);
+
+static short *null_rules;
+
+void
+verbose(void)
+{
+    int i;
+
+    if (!vflag)
+       return;
+
+    null_rules = TMALLOC(short, nrules);
+    NO_SPACE(null_rules);
+
+    fprintf(verbose_file, "\f\n");
+    for (i = 0; i < nstates; i++)
+       print_state(i);
+    FREE(null_rules);
+
+    if (nunused)
+       log_unused();
+    if (SRtotal || RRtotal)
+       log_conflicts();
+
+    fprintf(verbose_file, "\n\n%d terminals, %d nonterminals\n", ntokens,
+           nvars);
+    fprintf(verbose_file, "%d grammar rules, %d states\n", nrules - 2, nstates);
+}
+
+static void
+log_unused(void)
+{
+    int i;
+    short *p;
+
+    fprintf(verbose_file, "\n\nRules never reduced:\n");
+    for (i = 3; i < nrules; ++i)
+    {
+       if (!rules_used[i])
+       {
+           fprintf(verbose_file, "\t%s :", symbol_name[rlhs[i]]);
+           for (p = ritem + rrhs[i]; *p >= 0; ++p)
+               fprintf(verbose_file, " %s", symbol_name[*p]);
+           fprintf(verbose_file, "  (%d)\n", i - 2);
+       }
+    }
+}
+
+static void
+log_conflicts(void)
+{
+    int i;
+
+    fprintf(verbose_file, "\n\n");
+    for (i = 0; i < nstates; i++)
+    {
+       if (SRconflicts[i] || RRconflicts[i])
+       {
+           fprintf(verbose_file, "State %d contains ", i);
+           if (SRconflicts[i] > 0)
+               fprintf(verbose_file, "%d shift/reduce conflict%s",
+                       SRconflicts[i],
+                       PLURAL(SRconflicts[i]));
+           if (SRconflicts[i] && RRconflicts[i])
+               fprintf(verbose_file, ", ");
+           if (RRconflicts[i] > 0)
+               fprintf(verbose_file, "%d reduce/reduce conflict%s",
+                       RRconflicts[i],
+                       PLURAL(RRconflicts[i]));
+           fprintf(verbose_file, ".\n");
+       }
+    }
+}
+
+static void
+print_state(int state)
+{
+    if (state)
+       fprintf(verbose_file, "\n\n");
+    if (SRconflicts[state] || RRconflicts[state])
+       print_conflicts(state);
+    fprintf(verbose_file, "state %d\n", state);
+    print_core(state);
+    print_nulls(state);
+    print_actions(state);
+}
+
+static void
+print_conflicts(int state)
+{
+    int symbol, act, number;
+    action *p;
+
+    act = 0;                   /* not shift/reduce... */
+    number = -1;
+    symbol = -1;
+    for (p = parser[state]; p; p = p->next)
+    {
+       if (p->suppressed == 2)
+           continue;
+
+       if (p->symbol != symbol)
+       {
+           symbol = p->symbol;
+           number = p->number;
+           if (p->action_code == SHIFT)
+               act = SHIFT;
+           else
+               act = REDUCE;
+       }
+       else if (p->suppressed == 1)
+       {
+           if (state == final_state && symbol == 0)
+           {
+               fprintf(verbose_file, "%d: shift/reduce conflict \
+(accept, reduce %d) on $end\n", state, p->number - 2);
+           }
+           else
+           {
+               if (act == SHIFT)
+               {
+                   fprintf(verbose_file, "%d: shift/reduce conflict \
+(shift %d, reduce %d) on %s\n", state, number, p->number - 2,
+                           symbol_name[symbol]);
+               }
+               else
+               {
+                   fprintf(verbose_file, "%d: reduce/reduce conflict \
+(reduce %d, reduce %d) on %s\n", state, number - 2, p->number - 2,
+                           symbol_name[symbol]);
+               }
+           }
+       }
+    }
+}
+
+static void
+print_core(int state)
+{
+    int i;
+    int k;
+    int rule;
+    core *statep;
+    short *sp;
+    short *sp1;
+
+    statep = state_table[state];
+    k = statep->nitems;
+
+    for (i = 0; i < k; i++)
+    {
+       sp1 = sp = ritem + statep->items[i];
+
+       while (*sp >= 0)
+           ++sp;
+       rule = -(*sp);
+       fprintf(verbose_file, "\t%s : ", symbol_name[rlhs[rule]]);
+
+       for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
+           fprintf(verbose_file, "%s ", symbol_name[*sp]);
+
+       putc('.', verbose_file);
+
+       while (*sp >= 0)
+       {
+           fprintf(verbose_file, " %s", symbol_name[*sp]);
+           sp++;
+       }
+       fprintf(verbose_file, "  (%d)\n", -2 - *sp);
+    }
+}
+
+static void
+print_nulls(int state)
+{
+    action *p;
+    Value_t i, j, k, nnulls;
+
+    nnulls = 0;
+    for (p = parser[state]; p; p = p->next)
+    {
+       if (p->action_code == REDUCE &&
+           (p->suppressed == 0 || p->suppressed == 1))
+       {
+           i = p->number;
+           if (rrhs[i] + 1 == rrhs[i + 1])
+           {
+               for (j = 0; j < nnulls && i > null_rules[j]; ++j)
+                   continue;
+
+               if (j == nnulls)
+               {
+                   ++nnulls;
+                   null_rules[j] = i;
+               }
+               else if (i != null_rules[j])
+               {
+                   ++nnulls;
+                   for (k = (Value_t) (nnulls - 1); k > j; --k)
+                       null_rules[k] = null_rules[k - 1];
+                   null_rules[j] = i;
+               }
+           }
+       }
+    }
+
+    for (i = 0; i < nnulls; ++i)
+    {
+       j = null_rules[i];
+       fprintf(verbose_file, "\t%s : .  (%d)\n", symbol_name[rlhs[j]],
+               j - 2);
+    }
+    fprintf(verbose_file, "\n");
+}
+
+static void
+print_actions(int stateno)
+{
+    action *p;
+    shifts *sp;
+    int as;
+
+    if (stateno == final_state)
+       fprintf(verbose_file, "\t$end  accept\n");
+
+    p = parser[stateno];
+    if (p)
+    {
+       print_shifts(p);
+       print_reductions(p, defred[stateno]);
+    }
+
+    sp = shift_table[stateno];
+    if (sp && sp->nshifts > 0)
+    {
+       as = accessing_symbol[sp->shift[sp->nshifts - 1]];
+       if (ISVAR(as))
+           print_gotos(stateno);
+    }
+}
+
+static void
+print_shifts(action *p)
+{
+    int count;
+    action *q;
+
+    count = 0;
+    for (q = p; q; q = q->next)
+    {
+       if (q->suppressed < 2 && q->action_code == SHIFT)
+           ++count;
+    }
+
+    if (count > 0)
+    {
+       for (; p; p = p->next)
+       {
+           if (p->action_code == SHIFT && p->suppressed == 0)
+               fprintf(verbose_file, "\t%s  shift %d\n",
+                       symbol_name[p->symbol], p->number);
+       }
+    }
+}
+
+static void
+print_reductions(action *p, int defred2)
+{
+    int k, anyreds;
+    action *q;
+
+    anyreds = 0;
+    for (q = p; q; q = q->next)
+    {
+       if (q->action_code == REDUCE && q->suppressed < 2)
+       {
+           anyreds = 1;
+           break;
+       }
+    }
+
+    if (anyreds == 0)
+       fprintf(verbose_file, "\t.  error\n");
+    else
+    {
+       for (; p; p = p->next)
+       {
+           if (p->action_code == REDUCE && p->number != defred2)
+           {
+               k = p->number - 2;
+               if (p->suppressed == 0)
+                   fprintf(verbose_file, "\t%s  reduce %d\n",
+                           symbol_name[p->symbol], k);
+           }
+       }
+
+       if (defred2 > 0)
+           fprintf(verbose_file, "\t.  reduce %d\n", defred2 - 2);
+    }
+}
+
+static void
+print_gotos(int stateno)
+{
+    int i, k;
+    int as;
+    short *to_state2;
+    shifts *sp;
+
+    putc('\n', verbose_file);
+    sp = shift_table[stateno];
+    to_state2 = sp->shift;
+    for (i = 0; i < sp->nshifts; ++i)
+    {
+       k = to_state2[i];
+       as = accessing_symbol[k];
+       if (ISVAR(as))
+           fprintf(verbose_file, "\t%s  goto %d\n", symbol_name[as], k);
+    }
+}
diff --git a/contrib/byacc/warshall.c b/contrib/byacc/warshall.c
new file mode 100644 (file)
index 0000000..efb7cf4
--- /dev/null
@@ -0,0 +1,82 @@
+/* $Id: warshall.c,v 1.7 2010/06/06 22:48:51 tom Exp $ */
+
+#include "defs.h"
+
+static void
+transitive_closure(unsigned *R, int n)
+{
+    int rowsize;
+    unsigned i;
+    unsigned *rowj;
+    unsigned *rp;
+    unsigned *rend;
+    unsigned *ccol;
+    unsigned *relend;
+    unsigned *cword;
+    unsigned *rowi;
+
+    rowsize = WORDSIZE(n);
+    relend = R + n * rowsize;
+
+    cword = R;
+    i = 0;
+    rowi = R;
+    while (rowi < relend)
+    {
+       ccol = cword;
+       rowj = R;
+
+       while (rowj < relend)
+       {
+           if (*ccol & (unsigned)(1 << i))
+           {
+               rp = rowi;
+               rend = rowj + rowsize;
+               while (rowj < rend)
+                   *rowj++ |= *rp++;
+           }
+           else
+           {
+               rowj += rowsize;
+           }
+
+           ccol += rowsize;
+       }
+
+       if (++i >= BITS_PER_WORD)
+       {
+           i = 0;
+           cword++;
+       }
+
+       rowi += rowsize;
+    }
+}
+
+void
+reflexive_transitive_closure(unsigned *R, int n)
+{
+    int rowsize;
+    unsigned i;
+    unsigned *rp;
+    unsigned *relend;
+
+    transitive_closure(R, n);
+
+    rowsize = WORDSIZE(n);
+    relend = R + n * rowsize;
+
+    i = 0;
+    rp = R;
+    while (rp < relend)
+    {
+       *rp |= (unsigned)(1 << i);
+       if (++i >= BITS_PER_WORD)
+       {
+           i = 0;
+           rp++;
+       }
+
+       rp += rowsize;
+    }
+}
diff --git a/contrib/byacc/yacc.1 b/contrib/byacc/yacc.1
new file mode 100644 (file)
index 0000000..239380a
--- /dev/null
@@ -0,0 +1,242 @@
+.\" $Id: yacc.1,v 1.18 2012/01/15 18:12:28 tom Exp $
+.\"
+.\" .TH YACC 1 "July\ 15,\ 1990"
+.\" .UC 6
+.de ES
+.ne 8
+.nf
+.sp
+.in +4
+..
+.de EE
+.in -4
+.fi
+..
+.\" Bulleted paragraph
+.de bP
+.IP \(bu 4
+..
+.TH YACC 1 "September 7, 2011" "Berkeley Yacc" "User Commands"
+.SH NAME
+Yacc \- an LALR(1) parser generator
+.SH SYNOPSIS
+.B yacc [ -dgilrtv ] [ \-b
+.I file_prefix
+.B ] [ \-p
+.I symbol_prefix
+.B ]
+.I filename
+.SH DESCRIPTION
+.B Yacc
+reads the grammar specification in the file
+.I filename
+and generates an LALR(1) parser for it.
+The parsers consist of a set of LALR(1) parsing tables and a driver routine
+written in the C programming language.
+.B Yacc
+normally writes the parse tables and the driver routine to the file
+.IR y.tab.c.
+.PP
+The following options are available:
+.TP 5
+\fB\-b \fP\fIfile_prefix\fR
+The
+.B \-b
+option changes the prefix prepended to the output file names to
+the string denoted by
+.IR file_prefix.
+The default prefix is the character
+.IR y.
+.TP
+.B \-d
+The \fB-d\fR option causes the header file
+.BR y.tab.h
+to be written.
+It contains #define's for the token identifiers.
+.TP
+.B \-g
+The
+.B \-g
+option causes a graphical description of the generated LALR(1) parser to
+be written to the file
+.BR y.dot
+in graphviz format, ready to be processed by dot(1).
+.TP
+.B \-i
+The \fB-i\fR option causes a supplementary header file
+.BR y.tab.i
+to be written.
+It contains extern declarations
+and supplementary #define's as needed to map the conventional \fIyacc\fP
+\fByy\fP-prefixed names to whatever the \fB-p\fP option may specify.
+The code file, e.g., \fBy.tab.c\fP is modified to #include this file
+as well as the \fBy.tab.h\fP file, enforcing consistent usage of the
+symbols defined in those files.
+.IP
+The supplementary header file makes it simpler to separate compilation
+of lex- and yacc-files.
+.TP
+.B \-l
+If the
+.B \-l
+option is not specified,
+.B yacc
+will insert \fI#line\fP directives in the generated code.
+The \fI#line\fP directives let the C compiler relate errors in the
+generated code to the user's original code.
+If the \fB-l\fR option is specified,
+.B yacc
+will not insert the \fI#line\fP directives.
+\&\fI#line\fP directives specified by the user will be retained.
+.TP
+\fB\-o \fP\fIoutput_file\fR
+specify the filename for the parser file.
+If this option is not given, the output filename is
+the file prefix concatenated with the file suffix, e.g., \fBy.tab.c\fP.
+This overrides the \fB-p\fP option.
+.TP
+\fB\-p \fP\fIsymbol_prefix\fR
+The
+.B \-p
+option changes the prefix prepended to yacc-generated symbols to
+the string denoted by
+.IR symbol_prefix.
+The default prefix is the string
+.BR yy.
+.TP
+.B \-P
+create a reentrant parser, e.g., "%pure-parser".
+.TP
+.B \-r
+The
+.B \-r
+option causes
+.B yacc
+to produce separate files for code and tables.  The code file
+is named
+.IR y.code.c,
+and the tables file is named
+.IR y.tab.c.
+The prefix "\fIy.\fP" can be overridden using the \fB\-b\fP option.
+.TP
+.B \-s
+suppress "\fB#define\fP" statements generated for string literals in
+a "\fB%token\fP" statement, to more closely match original \fByacc\fP behavior.
+.IP
+Normally when \fByacc\fP sees a line such as
+.ES
+%token OP_ADD "ADD"
+.EE
+.IP
+it notices that the quoted "ADD" is a valid C identifier,
+and generates a #define not only for OP_ADD,
+but for ADD as well,
+e.g.,
+.ES
+#define OP_ADD 257
+.br
+#define ADD 258
+.EE
+.IP
+The original \fByacc\fP does not generate the second "\fB#define\fP".
+The \fB\-s\fP option suppresses this "\fB#define\fP".
+.IP
+POSIX (IEEE 1003.1 2004) documents only names and numbers for "\fB%token\fP",
+though original \fByacc\fP and bison also accept string literals.
+.TP
+.B \-t
+The
+.B \-t
+option changes the preprocessor directives generated by
+.B yacc
+so that debugging statements will be incorporated in the compiled code.
+.TP
+.B \-v
+The
+.B \-v
+option causes a human-readable description of the generated parser to
+be written to the file
+.IR y.output.
+.TP
+.B \-V
+print the version number to the standard output.
+.TP
+.B \-y
+\fByacc\fP ignores this option,
+which bison supports for ostensible POSIX compatibility.
+.SH EXTENSIONS
+.B yacc
+provides some extensions for compatibility with bison and other implementations
+of yacc:
+.TP
+\fB %expect\fP \fInumber\fP
+tell \fByacc\fP the expected number of shift/reduce conflicts.
+That makes it only report the number if it differs.
+.TP
+\fB %expect-rr\fP \fInumber\fP
+tell \fByacc\fP the expected number of reduce/reduce conflicts.
+That makes it only report the number if it differs.
+This is (unlike bison) allowable in LALR parsers.
+.TP
+\fB %lex-param\fP { \fIargument-declaration\fP }
+By default, the lexer accepts no parameters, e.g., \fByylex()\fP.
+Use this directive to add parameter declarations for your customized lexer.
+.TP
+\fB %parse-param\fP { \fIargument-declaration\fP }
+By default, the parser accepts no parameters, e.g., \fByyparse()\fP.
+Use this directive to add parameter declarations for your customized parser.
+.TP
+\fB %pure-parser\fP
+Most variables (other than \fByydebug\fP and \fByynerrs\fP) are
+allocated on the stack within \fByyparse\fP, making the parser reasonably
+reentrant.
+.SH PORTABILITY
+According to Robert Corbett,
+.ES
+    Berkeley Yacc is an LALR(1) parser generator.  Berkeley Yacc has been made
+as compatible as possible with AT&T Yacc.  Berkeley Yacc can accept any input
+specification that conforms to the AT&T Yacc documentation.  Specifications
+that take advantage of undocumented features of AT&T Yacc will probably be
+rejected.
+.EE
+.PP
+The rationale in
+.ES
+http://pubs.opengroup.org/onlinepubs/9699919799/utilities/yacc.html
+.EE
+.PP
+documents some features of AT&T yacc which are no longer required for POSIX
+compliance.
+.PP
+That said, you may be interested in reusing grammary files with some
+other implementation which is not strictly compatible with AT&T yacc.
+For instance, there is bison.
+Here are a few differences:
+.bP
+\fBYacc\fP accepts an equals mark preceding the left curly brace
+of an action (as in the original grammar file \fBftp.y\fP):
+.ES
+       |       STAT CRLF
+               = {
+                       statcmd();
+               }
+.EE
+.bP
+\fBYacc\fP and bison emit code in different order, and in particular bison
+makes forward reference to common functions such as yylex, yyparse and
+yyerror without providing prototypes.
+.bP
+Bison's support for "%expect" is broken in more than one release.
+For best results using bison, delete that directive.
+.bP
+Bison has no equivalent for some of \fByacc\fP's commmand-line options,
+relying on directives embedded in the grammar file.
+.bP
+Bison's "\fB\-y\fP" option does not affect bison's lack of support for
+features of AT&T yacc which were deemed obsolescent.
+.
+.SH DIAGNOSTICS
+If there are rules that are never reduced, the number of such rules is
+reported on standard error.
+If there are any LALR(1) conflicts, the number of conflicts is reported
+on standard error.