From b260537536ee1e645f6139e67cf5b6b968668868 Mon Sep 17 00:00:00 2001 From: Peter Avalos Date: Sat, 19 Jan 2013 02:03:58 -0800 Subject: [PATCH] Import byacc-20121003. This is a significant update for yacc that's being maintained by Thomas Dickey at http://invisible-island.net/byacc/. --- contrib/byacc/AUTHORS | 7 + contrib/byacc/CHANGES | 1270 +++++++++++++++++++ contrib/byacc/README | 29 + contrib/byacc/README.DELETED | 17 + contrib/byacc/VERSION | 1 + contrib/byacc/closure.c | 251 ++++ contrib/byacc/defs.h | 454 +++++++ contrib/byacc/error.c | 288 +++++ contrib/byacc/graph.c | 112 ++ contrib/byacc/lalr.c | 655 ++++++++++ contrib/byacc/lr0.c | 599 +++++++++ contrib/byacc/main.c | 660 ++++++++++ contrib/byacc/mkpar.c | 392 ++++++ contrib/byacc/output.c | 1507 +++++++++++++++++++++++ contrib/byacc/reader.c | 2251 ++++++++++++++++++++++++++++++++++ contrib/byacc/skeleton.c | 439 +++++++ contrib/byacc/symtab.c | 117 ++ contrib/byacc/verbose.c | 334 +++++ contrib/byacc/warshall.c | 82 ++ contrib/byacc/yacc.1 | 242 ++++ 20 files changed, 9707 insertions(+) create mode 100644 contrib/byacc/AUTHORS create mode 100644 contrib/byacc/CHANGES create mode 100644 contrib/byacc/README create mode 100644 contrib/byacc/README.DELETED create mode 100644 contrib/byacc/VERSION create mode 100644 contrib/byacc/closure.c create mode 100644 contrib/byacc/defs.h create mode 100644 contrib/byacc/error.c create mode 100644 contrib/byacc/graph.c create mode 100644 contrib/byacc/lalr.c create mode 100644 contrib/byacc/lr0.c create mode 100644 contrib/byacc/main.c create mode 100644 contrib/byacc/mkpar.c create mode 100644 contrib/byacc/output.c create mode 100644 contrib/byacc/reader.c create mode 100644 contrib/byacc/skeleton.c create mode 100644 contrib/byacc/symtab.c create mode 100644 contrib/byacc/verbose.c create mode 100644 contrib/byacc/warshall.c create mode 100644 contrib/byacc/yacc.1 diff --git a/contrib/byacc/AUTHORS b/contrib/byacc/AUTHORS new file mode 100644 index 0000000000..6d75337909 --- /dev/null +++ b/contrib/byacc/AUTHORS @@ -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 index 0000000000..877b227cea --- /dev/null +++ b/contrib/byacc/CHANGES @@ -0,0 +1,1270 @@ +2012-10-03 Thomas E. Dickey + + * 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 + + * 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 + + * aclocal.m4: + move existence-check for mkstemp out of the AC_TRY_RUN, to help with + cross-compiles + +2012-10-02 Thomas E. Dickey + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * config.sub: 2011-04-01 + +2011-02-02 Thomas E. Dickey + + * config.guess: 2011-01-01 + +2010-12-29 Thomas E. Dickey + + * 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 + + * 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 + + * package/debian/changelog, package/byacc.spec, VERSION: bump + +2010-12-26 Thomas E. Dickey + + * defs.h, main.c: + change return-type of allocate() to avoid warnings of alignment problems + + * main.c: Solaris declares chmod() in + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * config.guess: 2010-09-24 + +2010-09-10 Thomas E. Dickey + + * config.sub: 2010-09-11 + +2010-06-10 Thomas E. Dickey + + * yacc.1, package/debian/changelog, package/byacc.spec, VERSION: + bump to 2010/06/10 + +2010-06-09 Thomas E. Dickey + + * 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 + + * 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 + + * 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 + + * VERSION: bump to 2010/06/07 + +2010-06-06 Thomas E. Dickey + + * 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 + + * 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 + + * 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 + + * package/debian/source/format: scripts from Debian package + +2009-12-31 Thomas E. Dickey + + * config.guess: 2009-12-30 + + * config.sub: 2009-12-31 + +2009-10-27 Thomas E. Dickey + + * 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 + + * 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 + + * config.guess, config.sub: 2009-08-19 + +2009-02-21 Thomas E. Dickey + + * VERSION: bump + + * output.c: restore "yylval" symbol, omitted in cleanup on 2008/8/25 + +2008-12-26 Thomas E. Dickey + + * configure: regen with autoconf-2.52 (patched) + +2008-12-25 Thomas E. Dickey + + * test/error.tab.c, test/ftp.tab.c, test/grammar.tab.c, test/calc.tab.c: + regenerated + +2008-12-24 Thomas E. Dickey + + * VERSION: bump + + * skeleton.c: + remove ifdef-lint from goto yyerrlab, to quiet gcc warning + +2008-11-26 Thomas E. Dickey + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * 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 + + * package/pkgsrc/Makefile, package/pkgsrc/distinfo: + scripts from NetBSD pkgsrc, for test-builds + +2008-03-14 Thomas E. Dickey + + * config.sub: update to 2008-03-08 + + * config.guess: update to 2008-03-12 + +2007-05-09 Thomas E. Dickey + + * 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 + + * mkdirs.sh: improved version for "make -j" + +2006-12-22 Thomas E. Dickey + + * config.guess: 2006/12/22 + +2006-12-08 Thomas E. Dickey + + * config.sub: 2006/12/08 + +2005-08-13 Thomas E. Dickey + + * 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 + + * configure: regenerated + + * aclocal.m4: improve checks for Intel compiler warnings + +2005-06-25 Thomas E. Dickey + + * config.sub: 2005/6/2 + + * config.guess: 2005/5/27 + +2005-05-05 Thomas E. Dickey + + * defs.h: add a fallback for GCC_UNUSED + +2005-05-04 Thomas E. Dickey + + * 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 + + * 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 : + add graphical output of the LALR(1) automaton for graphviz, + associated with command-line option `-g' + +2005-04-16 Thomas E. Dickey + + * config.sub: 2005/2/10 + + * config.guess: 2005/3/24 + +2005-04-13 Thomas E. Dickey + + * package/pkgsrc/PLIST: scripts from NetBSD pkgsrc, for test-builds + +2005-03-21 Thomas E. Dickey + + * package/pkgsrc/DESCR: scripts from NetBSD pkgsrc, for test-builds + +2004-03-28 Thomas E. Dickey + + * 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 + + * test/grammar.y: RCS_BASE + +2004-02-23 Thomas E. Dickey + + * config.sub: RCS_BASE + +2004-02-17 Thomas E. Dickey + + * config.guess: RCS_BASE + +2003-11-29 Thomas E. Dickey + + * install-sh: improved quoting + +2002-06-29 Thomas E. Dickey + + * mkdirs.sh: + don't use character range, since some locales don't work as expected + +2001-06-22 Thomas E. Dickey + + * install-sh: RCS_BASE + +2000-11-20 Thomas E. Dickey + + * 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 + + * test/RCS, RCS: PERMIT FILE + +2000-02-14 Thomas E. Dickey + + * main.c: fix for VMS port - making pathname for temp-file + + * descrip.mms: original version + +2000-02-13 Thomas E. Dickey + + * 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 + + * mkdirs.sh: RCS_BASE + +1995-01-01 Thomas E. Dickey + + * 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 + + * 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 index 0000000000..391c43bd70 --- /dev/null +++ b/contrib/byacc/README @@ -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 index 0000000000..a302a27242 --- /dev/null +++ b/contrib/byacc/README.DELETED @@ -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 index 0000000000..a63335804c --- /dev/null +++ b/contrib/byacc/VERSION @@ -0,0 +1 @@ +20121003 diff --git a/contrib/byacc/closure.c b/contrib/byacc/closure.c new file mode 100644 index 0000000000..7573ff5bbd --- /dev/null +++ b/contrib/byacc/closure.c @@ -0,0 +1,251 @@ +/* $Id: closure.c,v 1.9 2010/06/09 08:21:47 tom Exp $ */ + +#include "defs.h" + +Value_t *itemset; +Value_t *itemsetend; +unsigned *ruleset; + +static unsigned *first_derives; +static unsigned *EFF; + +static void +set_EFF(void) +{ + unsigned *row; + int symbol; + short *sp; + int rowsize; + int i; + int rule; + + rowsize = WORDSIZE(nvars); + EFF = NEW2(nvars * rowsize, unsigned); + + row = EFF; + for (i = start_symbol; i < nsyms; i++) + { + sp = derives[i]; + for (rule = *sp; rule > 0; rule = *++sp) + { + symbol = ritem[rrhs[rule]]; + if (ISVAR(symbol)) + { + symbol -= start_symbol; + SETBIT(row, symbol); + } + } + row += rowsize; + } + + reflexive_transitive_closure(EFF, nvars); + +#ifdef DEBUG + print_EFF(); +#endif +} + +void +set_first_derives(void) +{ + unsigned *rrow; + unsigned *vrow; + int j; + unsigned k; + unsigned cword = 0; + short *rp; + + int rule; + int i; + int rulesetsize; + int varsetsize; + + rulesetsize = WORDSIZE(nrules); + varsetsize = WORDSIZE(nvars); + first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; + + set_EFF(); + + rrow = first_derives + ntokens * rulesetsize; + for (i = start_symbol; i < nsyms; i++) + { + vrow = EFF + ((i - ntokens) * varsetsize); + k = BITS_PER_WORD; + for (j = start_symbol; j < nsyms; k++, j++) + { + if (k >= BITS_PER_WORD) + { + cword = *vrow++; + k = 0; + } + + if (cword & (unsigned)(1 << k)) + { + rp = derives[j]; + while ((rule = *rp++) >= 0) + { + SETBIT(rrow, rule); + } + } + } + + rrow += rulesetsize; + } + +#ifdef DEBUG + print_first_derives(); +#endif + + FREE(EFF); +} + +void +closure(short *nucleus, int n) +{ + unsigned ruleno; + unsigned word; + unsigned i; + Value_t *csp; + unsigned *dsp; + unsigned *rsp; + int rulesetsize; + + Value_t *csend; + unsigned *rsend; + int symbol; + Value_t itemno; + + rulesetsize = WORDSIZE(nrules); + rsend = ruleset + rulesetsize; + for (rsp = ruleset; rsp < rsend; rsp++) + *rsp = 0; + + csend = nucleus + n; + for (csp = nucleus; csp < csend; ++csp) + { + symbol = ritem[*csp]; + if (ISVAR(symbol)) + { + dsp = first_derives + symbol * rulesetsize; + rsp = ruleset; + while (rsp < rsend) + *rsp++ |= *dsp++; + } + } + + ruleno = 0; + itemsetend = itemset; + csp = nucleus; + for (rsp = ruleset; rsp < rsend; ++rsp) + { + word = *rsp; + if (word) + { + for (i = 0; i < BITS_PER_WORD; ++i) + { + if (word & (unsigned)(1 << i)) + { + itemno = rrhs[ruleno + i]; + while (csp < csend && *csp < itemno) + *itemsetend++ = *csp++; + *itemsetend++ = itemno; + while (csp < csend && *csp == itemno) + ++csp; + } + } + } + ruleno += BITS_PER_WORD; + } + + while (csp < csend) + *itemsetend++ = *csp++; + +#ifdef DEBUG + print_closure(n); +#endif +} + +void +finalize_closure(void) +{ + FREE(itemset); + FREE(ruleset); + FREE(first_derives + ntokens * WORDSIZE(nrules)); +} + +#ifdef DEBUG + +void +print_closure(int n) +{ + short *isp; + + printf("\n\nn = %d\n\n", n); + for (isp = itemset; isp < itemsetend; isp++) + printf(" %d\n", *isp); +} + +void +print_EFF(void) +{ + int i, j; + unsigned *rowp; + unsigned word; + unsigned k; + + printf("\n\nEpsilon Free Firsts\n"); + + for (i = start_symbol; i < nsyms; i++) + { + printf("\n%s", symbol_name[i]); + rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); + word = *rowp++; + + k = BITS_PER_WORD; + for (j = 0; j < nvars; k++, j++) + { + if (k >= BITS_PER_WORD) + { + word = *rowp++; + k = 0; + } + + if (word & (1 << k)) + printf(" %s", symbol_name[start_symbol + j]); + } + } +} + +void +print_first_derives(void) +{ + int i; + int j; + unsigned *rp; + unsigned cword = 0; + unsigned k; + + printf("\n\n\nFirst Derives\n"); + + for (i = start_symbol; i < nsyms; i++) + { + printf("\n%s derives\n", symbol_name[i]); + rp = first_derives + i * WORDSIZE(nrules); + k = BITS_PER_WORD; + for (j = 0; j <= nrules; k++, j++) + { + if (k >= BITS_PER_WORD) + { + cword = *rp++; + k = 0; + } + + if (cword & (1 << k)) + printf(" %d\n", j); + } + } + + fflush(stdout); +} + +#endif diff --git a/contrib/byacc/defs.h b/contrib/byacc/defs.h new file mode 100644 index 0000000000..4d1a407072 --- /dev/null +++ b/contrib/byacc/defs.h @@ -0,0 +1,454 @@ +/* $Id: defs.h,v 1.37 2012/05/26 15:23:00 tom Exp $ */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include +#include +#include +#include + +#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 index 0000000000..3bab31b8ad --- /dev/null +++ b/contrib/byacc/error.c @@ -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 index 0000000000..2e312314d7 --- /dev/null +++ b/contrib/byacc/graph.c @@ -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 index 0000000000..eb5e309b00 --- /dev/null +++ b/contrib/byacc/lalr.c @@ -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 index 0000000000..641f9f8007 --- /dev/null +++ b/contrib/byacc/lr0.c @@ -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 index 0000000000..816e1547f8 --- /dev/null +++ b/contrib/byacc/main.c @@ -0,0 +1,660 @@ +/* $Id: main.c,v 1.40 2012/09/29 13:11:00 Adrian.Bunk Exp $ */ + +#include +#include /* for _exit() */ + +#include "defs.h" + +#ifdef HAVE_MKSTEMP +# define USE_MKSTEMP 1 +#elif defined(HAVE_FCNTL_H) +# define USE_MKSTEMP 1 +# include /* for open(), O_EXCL, etc. */ +#else +# define USE_MKSTEMP 0 +#endif + +#if USE_MKSTEMP +#include +#include + +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 index 0000000000..b2e36ab774 --- /dev/null +++ b/contrib/byacc/mkpar.c @@ -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 index 0000000000..331726d78e --- /dev/null +++ b/contrib/byacc/output.c @@ -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 index 0000000000..124b77639d --- /dev/null +++ b/contrib/byacc/reader.c @@ -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 index 0000000000..48ae6949aa --- /dev/null +++ b/contrib/byacc/skeleton.c @@ -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 /* needed for printf */", + "#endif", + "", + "#include /* needed for malloc, etc */", + "#include /* 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 index 0000000000..9839180936 --- /dev/null +++ b/contrib/byacc/symtab.c @@ -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 index 0000000000..3e6ea28528 --- /dev/null +++ b/contrib/byacc/verbose.c @@ -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 index 0000000000..efb7cf4479 --- /dev/null +++ b/contrib/byacc/warshall.c @@ -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 index 0000000000..239380a360 --- /dev/null +++ b/contrib/byacc/yacc.1 @@ -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. -- 2.41.0