[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: push parser implemenation
|
From: |
Akim Demaille |
|
Subject: |
Re: push parser implemenation |
|
Date: |
Fri, 07 Apr 2006 14:42:29 +0200 |
|
User-agent: |
Gnus/5.110004 (No Gnus v0.4) Emacs/21.4 (gnu/linux) |
Bob,
I'm starting to toy with your implementation, and to try to bench it.
It seems that there is about a 15% performance loss of push.c compared
to yacc.c, both used in pull mode without compiler optimization on my
Mac.
sulaco-eth% PATH=$PWD/_build/tests:$PATH ./bench.pl
push-push
yacc-pure
yacc-yacc
push-pure
push-yacc
calc:
Benchmark: timing 50 iterations of push-pure, push-push, push-yacc, yacc-pure,
yacc-yacc...
push-pure: 64 wallclock secs ( 0.00 usr 0.07 sys + 45.05 cusr 1.36 csys =
46.48 CPU) @ 714.29/s (n=50)
push-push: 77 wallclock secs ( 0.00 usr 0.07 sys + 50.53 cusr 1.56 csys =
52.16 CPU) @ 714.29/s (n=50)
push-yacc: 66 wallclock secs ( 0.00 usr 0.07 sys + 45.51 cusr 1.40 csys =
46.98 CPU) @ 714.29/s (n=50)
yacc-pure: 55 wallclock secs ( 0.00 usr 0.07 sys + 36.98 cusr 1.25 csys =
38.30 CPU) @ 714.29/s (n=50)
yacc-yacc: 54 wallclock secs ( 0.00 usr 0.07 sys + 38.12 cusr 1.23 csys =
39.42 CPU) @ 714.29/s (n=50)
Rate push-push yacc-yacc yacc-pure push-pure push-yacc
push-push 714/s -- 0% 0% 0% -0%
yacc-yacc 714/s 0% -- 0% 0% -0%
yacc-pure 714/s 0% 0% -- 0% -0%
push-pure 714/s 0% 0% 0% -- -0%
push-yacc 714/s 0% 0% 0% 0% --
I confess I don't understand the table output by this Perl module
here. What is this "rate"? What matters is:
push-pure: 64 wallclock secs
push-push: 77 wallclock secs
push-yacc: 66 wallclock secs
yacc-pure: 55 wallclock secs
yacc-yacc: 54 wallclock secs
With optimization (-O2):
sulaco-eth% PATH=$PWD/_build/tests:$PATH ./bench.pl
push-push
yacc-pure
yacc-yacc
push-pure
push-yacc
calc:
Benchmark: timing 50 iterations of push-pure, push-push, push-yacc, yacc-pure,
yacc-yacc...
push-pure: 31 wallclock secs ( 0.00 usr 0.07 sys + 20.95 cusr 0.94 csys =
21.96 CPU) @ 714.29/s (n=50)
push-push: 34 wallclock secs ( 0.00 usr 0.07 sys + 22.96 cusr 0.97 csys =
24.00 CPU) @ 714.29/s (n=50)
push-yacc: 31 wallclock secs ( 0.00 usr 0.07 sys + 21.48 cusr 0.92 csys =
22.47 CPU) @ 714.29/s (n=50)
yacc-pure: 26 wallclock secs ( 0.00 usr 0.07 sys + 17.79 cusr 0.88 csys =
18.74 CPU) @ 714.29/s (n=50)
yacc-yacc: 25 wallclock secs ( 0.00 usr 0.08 sys + 18.51 cusr 0.87 csys =
19.46 CPU) @ 625.00/s (n=50)
Rate yacc-yacc yacc-pure push-pure push-push push-yacc
yacc-yacc 625/s -- -12% -12% -12% -12%
yacc-pure 714/s 14% -- 0% -0% -0%
push-pure 714/s 14% 0% -- -0% -0%
push-push 714/s 14% 0% 0% -- 0%
push-yacc 714/s 14% 0% 0% 0% --
I.e.:
push-pure: 31 wallclock secs
push-push: 34 wallclock secs
push-yacc: 31 wallclock secs
yacc-pure: 26 wallclock secs
yacc-yacc: 25 wallclock secs
More experiments (and more eyes on this script) would help.
I have a few comments.
1. I think you should not change the semantics of yyparse in the push
parser. In fact, I think the push parser should always provide
yyparse as the good old pull interface wrapping the yyparse_push
interface or whatever.
2. What is the way one is expected to pass yylval? I cheated:
#if YYPUSH
static int
yyparse_wrapper ()
{
struct yypvars *ctx = yypvarsinit ();
do {
yyparse (ctx);
set_yychar (ctx, yylex ());
ctx->yylval = yylval;
} while (get_yyresult (ctx) != 0);
free (ctx);
}
#define yyparse yyparse_wrapper
#endif
3. I don't think we should maintain the Cartesian product of all the
badly designed features, so I suggest that push => pure. There are
a couple of place where the (m4) code could be simplified then.
4. Also, YYPARSE_PARAM is bad, does not scale well, etc. Don't bother
with it except to maintain compatibility with the old mode.
Attached is your diff, but this time with a "push.c" skeleton, leaving
yacc.c as it was before. That's easier to bench (alternatively I
could have introduced a yacc.old.c, but that's clearer).
Index: data/Makefile.am
===================================================================
RCS file: /cvsroot/bison/bison/data/Makefile.am,v
retrieving revision 1.12
diff -u -r1.12 Makefile.am
--- data/Makefile.am 14 Nov 2005 08:13:07 -0000 1.12
+++ data/Makefile.am 7 Apr 2006 09:30:31 -0000
@@ -1,4 +1,4 @@
-## Copyright (C) 2002, 2005 Free Software Foundation, Inc.
+## Copyright (C) 2002, 2005, 2006 Free Software Foundation, Inc.
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
@@ -16,7 +16,7 @@
## 02110-1301 USA
dist_pkgdata_DATA = README \
- c.m4 yacc.c glr.c \
+ c.m4 yacc.c glr.c push.c \
c++.m4 location.cc lalr1.cc glr.cc
m4sugardir = $(pkgdatadir)/m4sugar
Index: data/c.m4
===================================================================
RCS file: /cvsroot/bison/bison/data/c.m4,v
retrieving revision 1.53
diff -u -r1.53 c.m4
--- data/c.m4 22 Jan 2006 07:38:49 -0000 1.53
+++ data/c.m4 7 Apr 2006 09:30:31 -0000
@@ -62,6 +62,9 @@
/* Pure parsers. */
[#]define YYPURE b4_pure
+/* Push parsers. */
+[#]define YYPUSH b4_push
+
/* Using locations. */
[#]define YYLSP_NEEDED b4_locations_flag
])
@@ -185,6 +188,15 @@
[$2])])
+# b4_push_if(IF-TRUE, IF-FALSE)
+# -----------------------------
+# Expand IF-TRUE, if %push-parser, IF-FALSE otherwise.
+m4_define([b4_push_if],
+[m4_if(b4_push, [1],
+ [$1],
+ [$2])])
+
+
## ------------------------- ##
## Assigning token numbers. ##
Index: data/push.c
===================================================================
RCS file: data/push.c
diff -N data/push.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ data/push.c 7 Apr 2006 09:30:31 -0000
@@ -0,0 +1,1631 @@
+m4_divert(-1) -*- C -*-
+
+# Yacc compatible skeleton for Bison
+
+# Copyright (C) 1984, 1989, 1990, 2000, 2001, 2002, 2003, 2004, 2005, 2006
+# Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+# 02110-1301 USA
+
+m4_include(b4_pkgdatadir/[c.m4])
+
+## ---------------- ##
+## Default values. ##
+## ---------------- ##
+
+# Stack parameters.
+m4_define_default([b4_stack_depth_max], [10000])
+m4_define_default([b4_stack_depth_init], [200])
+
+
+## ------------------------ ##
+## Pure/impure interfaces. ##
+## ------------------------ ##
+
+
+# b4_yacc_pure_if(IF-TRUE, IF-FALSE)
+# ----------------------------------
+# Expand IF-TRUE, if %pure-parser and %parse-param, IF-FALSE otherwise.
+m4_define([b4_yacc_pure_if],
+[b4_pure_if([m4_ifset([b4_parse_param],
+ [$1], [$2])],
+ [$2])])
+
+
+# b4_yyerror_args
+# ---------------
+# Arguments passed to yyerror: user args plus yylloc.
+m4_define([b4_yyerror_args],
+[b4_yacc_pure_if([b4_location_if([&]b4_yylloc[, ])])dnl
+m4_ifset([b4_parse_param], [b4_c_args(b4_parse_param), ])])
+
+
+# b4_lex_param
+# ------------
+# Accumulate in b4_lex_param all the yylex arguments.
+# b4_lex_param arrives quoted twice, but we want to keep only one level.
+m4_define([b4_lex_param],
+m4_dquote(b4_pure_if([[[[YYSTYPE *]], [[&]b4_yylval[]]][]dnl
+b4_location_if([, [[YYLTYPE *], [&]b4_yylloc[]]])m4_ifdef([b4_lex_param], [,
])])dnl
+m4_ifdef([b4_lex_param], b4_lex_param)))
+
+
+
+## ------------ ##
+## Data Types. ##
+## ------------ ##
+
+# b4_int_type(MIN, MAX)
+# ---------------------
+# Return the smallest int type able to handle numbers ranging from
+# MIN to MAX (included). Overwrite the version from c.m4, which
+# uses only C89 types, so that the user can override the shorter
+# types, and so that pre-C89 compilers are handled correctly.
+m4_define([b4_int_type],
+[m4_if(b4_ints_in($@, [0], [255]), [1], [yytype_uint8],
+ b4_ints_in($@, [-128], [127]), [1], [yytype_int8],
+
+ b4_ints_in($@, [0], [65535]), [1], [yytype_uint16],
+ b4_ints_in($@, [-32768], [32767]), [1], [yytype_int16],
+
+ m4_eval([0 <= $1]), [1], [unsigned int],
+
+ [int])])
+
+
+## ----------------- ##
+## Semantic Values. ##
+## ----------------- ##
+
+
+# b4_lhs_value([TYPE])
+# --------------------
+# Expansion of $<TYPE>$.
+m4_define([b4_lhs_value],
+[(pv->yyval[]m4_ifval([$1], [.$1]))])
+
+
+# b4_rhs_value(RULE-LENGTH, NUM, [TYPE])
+# --------------------------------------
+# Expansion of $<TYPE>NUM, where the current rule has RULE-LENGTH
+# symbols on RHS.
+m4_define([b4_rhs_value],
+[(pv->address@hidden($2) - ($1)@}m4_ifval([$3], [.$3]))])
+
+m4_define([b4_rhs_value_no_pv],
+[(address@hidden($2) - ($1)@}m4_ifval([$3], [.$3]))])
+
+
+## ----------- ##
+## Locations. ##
+## ----------- ##
+
+# b4_lhs_location()
+# -----------------
+# Expansion of @$.
+m4_define([b4_lhs_location],
+[(pv->yyloc)])
+
+
+# b4_rhs_location(RULE-LENGTH, NUM)
+# ---------------------------------
+# Expansion of @NUM, where the current rule has RULE-LENGTH symbols
+# on RHS.
+m4_define([b4_rhs_location],
+[(pv->address@hidden($2) - ($1)@})])
+
+m4_define([b4_rhs_location_no_pv],
+[(address@hidden($2) - ($1)@})])
+
+
+
+## --------------------------------------------------------- ##
+## Defining symbol actions, e.g., printers and destructors. ##
+## --------------------------------------------------------- ##
+
+# We do want M4 expansion after # for CPP macros.
+m4_changecom()
+m4_divert(0)dnl
address@hidden @output_parser_name@
+b4_copyright([Skeleton parser for Yacc-like parsing with Bison],
+ [1984, 1989, 1990, 2000, 2001, 2002, 2003, 2004, 2005, 2006])[
+
+/* As a special exception, when this file is copied by Bison into a
+ Bison output file, you may use that output file without restriction.
+ This special exception was added by the Free Software Foundation
+ in version 1.24 of Bison. */
+
+/* C LALR(1) parser skeleton written by Richard Stallman, by
+ simplifying the original so-called "semantic" parser. */
+
+/* All symbols defined below should begin with yy or YY, to avoid
+ infringing on user name space. This should be done even for local
+ variables, as they might otherwise be expanded by user macros.
+ There are some unavoidable exceptions within include files to
+ define necessary library symbols; they are noted "INFRINGES ON
+ USER NAME SPACE" below. */
+
+]b4_identification
+m4_if(b4_prefix, [yy], [],
+[/* Substitute the variable and function names. */
+#define yyparse b4_prefix[]parse
+#define yypvarsinit b4_prefix[]pvarsinit
+#define yylex b4_prefix[]lex
+#define yyerror b4_prefix[]error
+#define yylval b4_prefix[]lval
+#define yychar b4_prefix[]char
+#define yydebug b4_prefix[]debug
+#define yynerrs b4_prefix[]nerrs
+b4_location_if([#define yylloc b4_prefix[]lloc])])
+m4_define([b4_yychar],[b4_pure_if([(pv->yychar)],b4_push_if([(pv->yychar)],yychar))])
+m4_define([b4_yylval],[b4_pure_if([(pv->yylval)],b4_push_if([(pv->yylval)],yylval))])
+m4_define([b4_yynerrs],[b4_pure_if([(pv->yynerrs)],[b4_push_if([(pv->yynerrs)],[yynerrs])])])
+m4_define([b4_yylloc],[b4_pure_if([(pv->yylloc)],b4_push_if([(pv->yylloc)],yylloc))])[
+
+]b4_token_enums_defines(b4_tokens)[
+
+/* Copy the first part of user declarations. */
+]b4_pre_prologue[
+
+/* Enabling traces. */
+#ifndef YYDEBUG
+# define YYDEBUG ]b4_debug[
+#endif
+
+/* Enabling verbose error messages. */
+#ifdef YYERROR_VERBOSE
+# undef YYERROR_VERBOSE
+# define YYERROR_VERBOSE 1
+#else
+# define YYERROR_VERBOSE ]b4_error_verbose[
+#endif
+
+/* Enabling the token table. */
+#ifndef YYTOKEN_TABLE
+# define YYTOKEN_TABLE ]b4_token_table[
+#endif
+
+#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
+]m4_ifdef([b4_stype],
+[typedef union[]m4_bregexp(b4_stype, [^{], [ YYSTYPE])
+b4_stype
+/* Line __line__ of yacc.c. */
+b4_syncline(address@hidden@], address@hidden@])
+ YYSTYPE;],
+[typedef int YYSTYPE;])[
+# define yystype YYSTYPE /* obsolescent; will be withdrawn */
+# define YYSTYPE_IS_DECLARED 1
+# define YYSTYPE_IS_TRIVIAL 1
+#endif
+
+]b4_location_if([#if ! defined YYLTYPE && ! defined YYLTYPE_IS_DECLARED
+typedef struct YYLTYPE
+{
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;
+} YYLTYPE;
+# define yyltype YYLTYPE /* obsolescent; will be withdrawn */
+# define YYLTYPE_IS_DECLARED 1
+# define YYLTYPE_IS_TRIVIAL 1
+#endif
+])[
+
+/* Copy the second part of user declarations. */
+]b4_post_prologue
+
+/* Line __line__ of yacc.c. */
+b4_syncline(address@hidden@], address@hidden@])[
+
+#ifdef short
+# undef short
+#endif
+
+#ifdef YYTYPE_UINT8
+typedef YYTYPE_UINT8 yytype_uint8;
+#else
+typedef unsigned char yytype_uint8;
+#endif
+
+#ifdef YYTYPE_INT8
+typedef YYTYPE_INT8 yytype_int8;
+#elif ]b4_c_modern[
+typedef signed char yytype_int8;
+#else
+typedef short int yytype_int8;
+#endif
+
+#ifdef YYTYPE_UINT16
+typedef YYTYPE_UINT16 yytype_uint16;
+#else
+typedef unsigned short int yytype_uint16;
+#endif
+
+#ifdef YYTYPE_INT16
+typedef YYTYPE_INT16 yytype_int16;
+#else
+typedef short int yytype_int16;
+#endif
+
+#ifndef YYSIZE_T
+# ifdef __SIZE_TYPE__
+# define YYSIZE_T __SIZE_TYPE__
+# elif defined size_t
+# define YYSIZE_T size_t
+# elif ! defined YYSIZE_T && ]b4_c_modern[
+# include <stddef.h> /* INFRINGES ON USER NAME SPACE */
+# define YYSIZE_T size_t
+# else
+# define YYSIZE_T unsigned int
+# endif
+#endif
+
+#define YYSIZE_MAXIMUM ((YYSIZE_T) -1)
+
+#ifndef YY_
+# if YYENABLE_NLS
+# if ENABLE_NLS
+# include <libintl.h> /* INFRINGES ON USER NAME SPACE */
+# define YY_(msgid) dgettext ("bison-runtime", msgid)
+# endif
+# endif
+# ifndef YY_
+# define YY_(msgid) msgid
+# endif
+#endif
+
+/* Suppress unused-variable warnings by "using" E. */
+#if ! defined lint || defined __GNUC__
+# define YYUSE(e) ((void) (e))
+#else
+# define YYUSE(e) /* empty */
+#endif
+
+/* Identity function, used to suppress warnings about constant conditions. */
+#ifndef lint
+# define YYID(n) (n)
+#else
+]b4_c_function_def([YYID], [static int], [[int i], [i]])[
+{
+ return i;
+}
+#endif
+
+#if ! defined yyoverflow || YYERROR_VERBOSE
+
+/* The parser invokes alloca or malloc; define the necessary symbols. */
+
+# ifdef YYSTACK_USE_ALLOCA
+# if YYSTACK_USE_ALLOCA
+# ifdef __GNUC__
+# define YYSTACK_ALLOC __builtin_alloca
+# elif defined __BUILTIN_VA_ARG_INCR
+# include <alloca.h> /* INFRINGES ON USER NAME SPACE */
+# elif defined _AIX
+# define YYSTACK_ALLOC __alloca
+# elif defined _MSC_VER
+# include <malloc.h> /* INFRINGES ON USER NAME SPACE */
+# define alloca _alloca
+# else
+# define YYSTACK_ALLOC alloca
+# if ! defined _ALLOCA_H && ! defined _STDLIB_H && ]b4_c_modern[
+# include <stdlib.h> /* INFRINGES ON USER NAME SPACE */
+# ifndef _STDLIB_H
+# define _STDLIB_H 1
+# endif
+# endif
+# endif
+# endif
+# endif
+
+# ifdef YYSTACK_ALLOC
+ /* Pacify GCC's `empty if-body' warning. */
+# define YYSTACK_FREE(Ptr) do { /* empty */; } while (YYID (0))
+# ifndef YYSTACK_ALLOC_MAXIMUM
+ /* The OS might guarantee only one guard page at the bottom of the stack,
+ and a page size can be as small as 4096 bytes. So we cannot safely
+ invoke alloca (N) if N exceeds 4096. Use a slightly smaller number
+ to allow for a few compiler-allocated temporary stack slots. */
+# define YYSTACK_ALLOC_MAXIMUM 4032 /* reasonable circa 2006 */
+# endif
+# else
+# define YYSTACK_ALLOC YYMALLOC
+# define YYSTACK_FREE YYFREE
+# ifndef YYSTACK_ALLOC_MAXIMUM
+# define YYSTACK_ALLOC_MAXIMUM YYSIZE_MAXIMUM
+# endif
+# if (defined __cplusplus && ! defined _STDLIB_H \
+ && ! ((defined YYMALLOC || defined malloc) \
+ && (defined YYFREE || defined free)))
+# include <stdlib.h> /* INFRINGES ON USER NAME SPACE */
+# ifndef _STDLIB_H
+# define _STDLIB_H 1
+# endif
+# endif
+# ifndef YYMALLOC
+# define YYMALLOC malloc
+# if ! defined malloc && ! defined _STDLIB_H && ]b4_c_modern[
+void *malloc (YYSIZE_T); /* INFRINGES ON USER NAME SPACE */
+# endif
+# endif
+# ifndef YYFREE
+# define YYFREE free
+# if ! defined free && ! defined _STDLIB_H && ]b4_c_modern[
+void free (void *); /* INFRINGES ON USER NAME SPACE */
+# endif
+# endif
+# endif
+#endif /* ! defined yyoverflow || YYERROR_VERBOSE */
+
+
+#if (! defined yyoverflow \
+ && (! defined __cplusplus \
+ || (]b4_location_if([[defined YYLTYPE_IS_TRIVIAL && YYLTYPE_IS_TRIVIAL
\
+ && ]])[defined YYSTYPE_IS_TRIVIAL && YYSTYPE_IS_TRIVIAL)))
+
+/* A type that is properly aligned for any stack member. */
+union yyalloc
+{
+ yytype_int16 yyss;
+ YYSTYPE yyvs;
+ ]b4_location_if([ YYLTYPE yyls;
+])dnl
+[};
+
+/* The size of the maximum gap between one aligned stack and the next. */
+# define YYSTACK_GAP_MAXIMUM (sizeof (union yyalloc) - 1)
+
+/* The size of an array large to enough to hold all stacks, each with
+ N elements. */
+]b4_location_if(
+[# define YYSTACK_BYTES(N) \
+ ((N) * (sizeof (yytype_int16) + sizeof (YYSTYPE) + sizeof (YYLTYPE)) \
+ + 2 * YYSTACK_GAP_MAXIMUM)],
+[# define YYSTACK_BYTES(N) \
+ ((N) * (sizeof (yytype_int16) + sizeof (YYSTYPE)) \
+ + YYSTACK_GAP_MAXIMUM)])[
+
+/* Copy COUNT objects from FROM to TO. The source and destination do
+ not overlap. */
+# ifndef YYCOPY
+# if defined __GNUC__ && 1 < __GNUC__
+# define YYCOPY(To, From, Count) \
+ __builtin_memcpy (To, From, (Count) * sizeof (*(From)))
+# else
+# define YYCOPY(To, From, Count) \
+ do \
+ { \
+ YYSIZE_T yyi; \
+ for (yyi = 0; yyi < (Count); yyi++) \
+ (To)[yyi] = (From)[yyi]; \
+ } \
+ while (YYID (0))
+# endif
+# endif
+
+/* Relocate STACK from its old location to the new one. The
+ local variables YYSIZE and YYSTACKSIZE give the old and new number of
+ elements in the stack, and YYPTR gives the new location of the
+ stack. Advance YYPTR to a properly aligned location for the next
+ stack. */
+# define YYSTACK_RELOCATE(Stack) \
+ do \
+ {
\
+ YYSIZE_T yynewbytes; \
+ YYCOPY (&yyptr->Stack, pv->Stack, yysize);
\
+ pv->Stack = &yyptr->Stack;
\
+ yynewbytes = pv->yystacksize * sizeof (*Stack) + YYSTACK_GAP_MAXIMUM; \
+ yyptr += yynewbytes / sizeof (*yyptr); \
+ }
\
+ while (YYID (0))
+
+#endif
+
+/* YYFINAL -- State number of the termination state. */
+#define YYFINAL ]b4_final_state_number[
+/* YYLAST -- Last index in YYTABLE. */
+#define YYLAST ]b4_last[
+
+/* YYNTOKENS -- Number of terminals. */
+#define YYNTOKENS ]b4_tokens_number[
+/* YYNNTS -- Number of nonterminals. */
+#define YYNNTS ]b4_nterms_number[
+/* YYNRULES -- Number of rules. */
+#define YYNRULES ]b4_rules_number[
+/* YYNRULES -- Number of states. */
+#define YYNSTATES ]b4_states_number[
+
+/* YYTRANSLATE(YYLEX) -- Bison symbol number corresponding to YYLEX. */
+#define YYUNDEFTOK ]b4_undef_token_number[
+#define YYMAXUTOK ]b4_user_token_number_max[
+
+#define YYTRANSLATE(YYX) \
+ ((unsigned int) (YYX) <= YYMAXUTOK ? yytranslate[YYX] : YYUNDEFTOK)
+
+/* YYTRANSLATE[YYLEX] -- Bison symbol number corresponding to YYLEX. */
+static const ]b4_int_type_for([b4_translate])[ yytranslate[] =
+{
+ ]b4_translate[
+};
+
+#if YYDEBUG
+/* YYPRHS[YYN] -- Index of the first RHS symbol of rule number YYN in
+ YYRHS. */
+static const ]b4_int_type_for([b4_prhs])[ yyprhs[] =
+{
+ ]b4_prhs[
+};
+
+/* YYRHS -- A `-1'-separated list of the rules' RHS. */
+static const ]b4_int_type_for([b4_rhs])[ yyrhs[] =
+{
+ ]b4_rhs[
+};
+
+/* YYRLINE[YYN] -- source line where rule number YYN was defined. */
+static const ]b4_int_type_for([b4_rline])[ yyrline[] =
+{
+ ]b4_rline[
+};
+#endif
+
+#if YYDEBUG || YYERROR_VERBOSE || YYTOKEN_TABLE
+/* YYTNAME[SYMBOL-NUM] -- String name of the symbol SYMBOL-NUM.
+ First, the terminals, then, starting at YYNTOKENS, nonterminals. */
+static const char *const yytname[] =
+{
+ ]b4_tname[
+};
+#endif
+
+# ifdef YYPRINT
+/* YYTOKNUM[YYLEX-NUM] -- Internal token number corresponding to
+ token YYLEX-NUM. */
+static const ]b4_int_type_for([b4_toknum])[ yytoknum[] =
+{
+ ]b4_toknum[
+};
+# endif
+
+/* YYR1[YYN] -- Symbol number of symbol that rule YYN derives. */
+static const ]b4_int_type_for([b4_r1])[ yyr1[] =
+{
+ ]b4_r1[
+};
+
+/* YYR2[YYN] -- Number of symbols composing right hand side of rule YYN. */
+static const ]b4_int_type_for([b4_r2])[ yyr2[] =
+{
+ ]b4_r2[
+};
+
+/* YYDEFACT[STATE-NAME] -- Default rule to reduce with in state
+ STATE-NUM when YYTABLE doesn't specify something else to do. Zero
+ means the default is an error. */
+static const ]b4_int_type_for([b4_defact])[ yydefact[] =
+{
+ ]b4_defact[
+};
+
+/* YYDEFGOTO[NTERM-NUM]. */
+static const ]b4_int_type_for([b4_defgoto])[ yydefgoto[] =
+{
+ ]b4_defgoto[
+};
+
+/* YYPACT[STATE-NUM] -- Index in YYTABLE of the portion describing
+ STATE-NUM. */
+#define YYPACT_NINF ]b4_pact_ninf[
+static const ]b4_int_type_for([b4_pact])[ yypact[] =
+{
+ ]b4_pact[
+};
+
+/* YYPGOTO[NTERM-NUM]. */
+static const ]b4_int_type_for([b4_pgoto])[ yypgoto[] =
+{
+ ]b4_pgoto[
+};
+
+/* YYTABLE[YYPACT[STATE-NUM]]. What to do in state STATE-NUM. If
+ positive, shift that token. If negative, reduce the rule which
+ number is the opposite. If zero, do what YYDEFACT says.
+ If YYTABLE_NINF, syntax error. */
+#define YYTABLE_NINF ]b4_table_ninf[
+static const ]b4_int_type_for([b4_table])[ yytable[] =
+{
+ ]b4_table[
+};
+
+static const ]b4_int_type_for([b4_check])[ yycheck[] =
+{
+ ]b4_check[
+};
+
+/* YYSTOS[STATE-NUM] -- The (internal number of the) accessing
+ symbol of state STATE-NUM. */
+static const ]b4_int_type_for([b4_stos])[ yystos[] =
+{
+ ]b4_stos[
+};
+
+#define yyerrok (pv->yyerrstatus = 0)
+#define yyclearin (]b4_yychar[ = YYEMPTY)
+#define YYEMPTY (-2)
+#define YYEOF 0
+
+#define YYACCEPT goto yyacceptlab
+#define YYABORT goto yyabortlab
+#define YYERROR goto yyerrorlab
+
+
+/* Like YYERROR except do call yyerror. This remains here temporarily
+ to ease the transition to the new meaning of YYERROR, for GCC.
+ Once GCC version 2 has supplanted version 1, this can go. */
+
+#define YYFAIL goto yyerrlab
+
+#define YYRECOVERING() (!!pv->yyerrstatus)
+
+#define YYBACKUP(Token, Value) \
+do \
+ if (]b4_yychar[ == YYEMPTY && yylen == 1) \
+ { \
+ ]b4_yychar[ = (Token); \
+ ]b4_yylval[ = (Value); \
+ yytoken = YYTRANSLATE (]b4_yychar[); \
+ YYPOPSTACK (1); \
+ goto yybackup; \
+ } \
+ else \
+ { \
+ yyerror (]b4_yyerror_args[YY_("syntax error: cannot back up")); \
+ YYERROR; \
+ } \
+while (YYID (0))
+
+
+#define YYTERROR 1
+#define YYERRCODE 256
+
+
+/* YYLLOC_DEFAULT -- Set CURRENT to span from RHS[1] to RHS[N].
+ If N is 0, then set CURRENT to the empty location which ends
+ the previous symbol: RHS[0] (always defined). */
+
+#define YYRHSLOC(Rhs, K) ((Rhs)[K])
+#ifndef YYLLOC_DEFAULT
+# define YYLLOC_DEFAULT(Current, Rhs, N) \
+ do \
+ if (YYID (N)) \
+ { \
+ (Current).first_line = YYRHSLOC (Rhs, 1).first_line; \
+ (Current).first_column = YYRHSLOC (Rhs, 1).first_column; \
+ (Current).last_line = YYRHSLOC (Rhs, N).last_line; \
+ (Current).last_column = YYRHSLOC (Rhs, N).last_column; \
+ } \
+ else \
+ { \
+ (Current).first_line = (Current).last_line = \
+ YYRHSLOC (Rhs, 0).last_line; \
+ (Current).first_column = (Current).last_column = \
+ YYRHSLOC (Rhs, 0).last_column; \
+ } \
+ while (YYID (0))
+#endif
+
+
+/* YY_LOCATION_PRINT -- Print the location on the stream.
+ This macro was not mandated originally: define only if we know
+ we won't break user code: when these are the locations we know. */
+
+#ifndef YY_LOCATION_PRINT
+# if YYLTYPE_IS_TRIVIAL
+# define YY_LOCATION_PRINT(File, Loc) \
+ fprintf (File, "%d.%d-%d.%d", \
+ (Loc).first_line, (Loc).first_column, \
+ (Loc).last_line, (Loc).last_column)
+# else
+# define YY_LOCATION_PRINT(File, Loc) ((void) 0)
+# endif
+#endif
+
+
+/* YYLEX -- calling `yylex' with the right arguments. */
+
+#ifdef YYLEX_PARAM
+# define YYLEX yylex (]b4_pure_if([&]b4_yylval[[]b4_location_if([,
&]b4_yylloc[]), ])[YYLEX_PARAM)
+#else
+# define YYLEX ]b4_c_function_call([yylex], [int], b4_lex_param)[
+#endif
+
+/* Enable debugging if requested. */
+#if YYDEBUG
+
+# ifndef YYFPRINTF
+# include <stdio.h> /* INFRINGES ON USER NAME SPACE */
+# define YYFPRINTF fprintf
+# endif
+
+# define YYDPRINTF(Args) \
+do { \
+ if (yydebug) \
+ YYFPRINTF Args; \
+} while (YYID (0))
+
+# define YY_SYMBOL_PRINT(Title, Type, Value, Location) \
+do { \
+ if (yydebug) \
+ { \
+ YYFPRINTF (stderr, "%s ", Title);
\
+ yy_symbol_print (stderr, \
+ Type, Value]b4_location_if([, Location])[]b4_user_args[); \
+ YYFPRINTF (stderr, "\n");
\
+ } \
+} while (YYID (0))
+
+]b4_yy_symbol_print_generate([b4_c_function_def])[
+
+/*------------------------------------------------------------------.
+| yy_stack_print -- Print the state stack from its BOTTOM up to its |
+| TOP (included). |
+`------------------------------------------------------------------*/
+
+]b4_c_function_def([yy_stack_print], [static void],
+ [[yytype_int16 *bottom], [bottom]],
+ [[yytype_int16 *top], [top]])[
+{
+ YYFPRINTF (stderr, "Stack now");
+ for (; bottom <= top; ++bottom)
+ YYFPRINTF (stderr, " %d", *bottom);
+ YYFPRINTF (stderr, "\n");
+}
+
+# define YY_STACK_PRINT(Bottom, Top) \
+do { \
+ if (yydebug) \
+ yy_stack_print ((Bottom), (Top)); \
+} while (YYID (0))
+
+
+/*------------------------------------------------.
+| Report that the YYRULE is going to be reduced. |
+`------------------------------------------------*/
+
+]b4_c_function_def([yy_reduce_print], [static void],
+ [[YYSTYPE *yyvsp], [yyvsp]],
+ b4_location_if([[[YYLTYPE *yylsp], [yylsp]],])
+ [[int yyrule], [yyrule]]m4_ifset([b4_parse_param], [,])
+ b4_parse_param)[
+{
+ int yynrhs = yyr2[yyrule];
+ int yyi;
+ unsigned long int yylno = yyrline[yyrule];
+ YYFPRINTF (stderr, "Reducing stack by rule %d (line %lu):\n",
+ yyrule - 1, yylno);
+ /* The symbols being reduced. */
+ for (yyi = 0; yyi < yynrhs; yyi++)
+ {
+ fprintf (stderr, " $%d = ", yyi + 1);
+ yy_symbol_print (stderr, yyrhs[yyprhs[yyrule] + yyi],
+ &]b4_rhs_value_no_pv(yynrhs, yyi + 1)[
+ ]b4_location_if([, &]b4_rhs_location_no_pv(yynrhs, yyi +
1))[]dnl
+ b4_user_args[);
+ fprintf (stderr, "\n");
+ }
+}
+
+# define YY_REDUCE_PRINT(Rule) \
+do { \
+ if (yydebug) \
+ yy_reduce_print (pv->yyvsp, ]b4_location_if([pv->yylsp,
])[Rule]b4_user_args[); \
+} while (YYID (0))
+
+/* Nonzero means print parse trace. It is left uninitialized so that
+ multiple parsers can coexist. */
+int yydebug;
+#else /* !YYDEBUG */
+# define YYDPRINTF(Args)
+# define YY_SYMBOL_PRINT(Title, Type, Value, Location)
+# define YY_STACK_PRINT(Bottom, Top)
+# define YY_REDUCE_PRINT(Rule)
+#endif /* !YYDEBUG */
+
+
+/* YYINITDEPTH -- initial size of the parser's stacks. */
+#ifndef YYINITDEPTH
+# define YYINITDEPTH ]b4_stack_depth_init[
+#endif
+
+/* YYMAXDEPTH -- maximum size the stacks can grow to (effective only
+ if the built-in stack extension method is used).
+
+ Do not make this value too large; the results are undefined if
+ YYSTACK_ALLOC_MAXIMUM < YYSTACK_BYTES (YYMAXDEPTH)
+ evaluated with infinite-precision integer arithmetic. */
+
+#ifndef YYMAXDEPTH
+# define YYMAXDEPTH ]b4_stack_depth_max[
+#endif
+
+
+
+#if YYERROR_VERBOSE
+
+# ifndef yystrlen
+# if defined __GLIBC__ && defined _STRING_H
+# define yystrlen strlen
+# else
+/* Return the length of YYSTR. */
+]b4_c_function_def([yystrlen], [static YYSIZE_T],
+ [[const char *yystr], [yystr]])[
+{
+ YYSIZE_T yylen;
+ for (yylen = 0; yystr[yylen]; yylen++)
+ continue;
+ return yylen;
+}
+# endif
+# endif
+
+# ifndef yystpcpy
+# if defined __GLIBC__ && defined _STRING_H && defined _GNU_SOURCE
+# define yystpcpy stpcpy
+# else
+/* Copy YYSRC to YYDEST, returning the address of the terminating '\0' in
+ YYDEST. */
+]b4_c_function_def([yystpcpy], [static char *],
+ [[char *yydest], [yydest]], [[const char *yysrc], [yysrc]])[
+{
+ char *yyd = yydest;
+ const char *yys = yysrc;
+
+ while ((*yyd++ = *yys++) != '\0')
+ continue;
+
+ return yyd - 1;
+}
+# endif
+# endif
+
+# ifndef yytnamerr
+/* Copy to YYRES the contents of YYSTR after stripping away unnecessary
+ quotes and backslashes, so that it's suitable for yyerror. The
+ heuristic is that double-quoting is unnecessary unless the string
+ contains an apostrophe, a comma, or backslash (other than
+ backslash-backslash). YYSTR is taken from yytname. If YYRES is
+ null, do not copy; instead, return the length of what the result
+ would have been. */
+static YYSIZE_T
+yytnamerr (char *yyres, const char *yystr)
+{
+ if (*yystr == '"')
+ {
+ size_t yyn = 0;
+ char const *yyp = yystr;
+
+ for (;;)
+ switch (*++yyp)
+ {
+ case '\'':
+ case ',':
+ goto do_not_strip_quotes;
+
+ case '\\':
+ if (*++yyp != '\\')
+ goto do_not_strip_quotes;
+ /* Fall through. */
+ default:
+ if (yyres)
+ yyres[yyn] = *yyp;
+ yyn++;
+ break;
+
+ case '"':
+ if (yyres)
+ yyres[yyn] = '\0';
+ return yyn;
+ }
+ do_not_strip_quotes: ;
+ }
+
+ if (! yyres)
+ return yystrlen (yystr);
+
+ return yystpcpy (yyres, yystr) - yyres;
+}
+# endif
+
+/* Copy into YYRESULT an error message about the unexpected token
+ YYCHAR while in state YYSTATE. Return the number of bytes copied,
+ including the terminating null byte. If YYRESULT is null, do not
+ copy anything; just return the number of bytes that would be
+ copied. As a special case, return 0 if an ordinary "syntax error"
+ message will do. Return YYSIZE_MAXIMUM if overflow occurs during
+ size calculation. */
+static YYSIZE_T
+yysyntax_error (char *yyresult, int yystate, int yychar)
+{
+ int yyn = yypact[yystate];
+
+ if (! (YYPACT_NINF < yyn && yyn < YYLAST))
+ return 0;
+ else
+ {
+ int yytype = YYTRANSLATE (yychar);
+ YYSIZE_T yysize0 = yytnamerr (0, yytname[yytype]);
+ YYSIZE_T yysize = yysize0;
+ YYSIZE_T yysize1;
+ int yysize_overflow = 0;
+ enum { YYERROR_VERBOSE_ARGS_MAXIMUM = 5 };
+ char const *yyarg[YYERROR_VERBOSE_ARGS_MAXIMUM];
+ int yyx;
+
+# if 0
+ /* This is so xgettext sees the translatable formats that are
+ constructed on the fly. */
+ YY_("syntax error, unexpected %s");
+ YY_("syntax error, unexpected %s, expecting %s");
+ YY_("syntax error, unexpected %s, expecting %s or %s");
+ YY_("syntax error, unexpected %s, expecting %s or %s or %s");
+ YY_("syntax error, unexpected %s, expecting %s or %s or %s or %s");
+# endif
+ char *yyfmt;
+ char const *yyf;
+ static char const yyunexpected[] = "syntax error, unexpected %s";
+ static char const yyexpecting[] = ", expecting %s";
+ static char const yyor[] = " or %s";
+ char yyformat[sizeof yyunexpected
+ + sizeof yyexpecting - 1
+ + ((YYERROR_VERBOSE_ARGS_MAXIMUM - 2)
+ * (sizeof yyor - 1))];
+ char const *yyprefix = yyexpecting;
+
+ /* Start YYX at -YYN if negative to avoid negative indexes in
+ YYCHECK. */
+ int yyxbegin = yyn < 0 ? -yyn : 0;
+
+ /* Stay within bounds of both yycheck and yytname. */
+ int yychecklim = YYLAST - yyn;
+ int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS;
+ int yycount = 1;
+
+ yyarg[0] = yytname[yytype];
+ yyfmt = yystpcpy (yyformat, yyunexpected);
+
+ for (yyx = yyxbegin; yyx < yyxend; ++yyx)
+ if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR)
+ {
+ if (yycount == YYERROR_VERBOSE_ARGS_MAXIMUM)
+ {
+ yycount = 1;
+ yysize = yysize0;
+ yyformat[sizeof yyunexpected - 1] = '\0';
+ break;
+ }
+ yyarg[yycount++] = yytname[yyx];
+ yysize1 = yysize + yytnamerr (0, yytname[yyx]);
+ yysize_overflow |= (yysize1 < yysize);
+ yysize = yysize1;
+ yyfmt = yystpcpy (yyfmt, yyprefix);
+ yyprefix = yyor;
+ }
+
+ yyf = YY_(yyformat);
+ yysize1 = yysize + yystrlen (yyf);
+ yysize_overflow |= (yysize1 < yysize);
+ yysize = yysize1;
+
+ if (yysize_overflow)
+ return YYSIZE_MAXIMUM;
+
+ if (yyresult)
+ {
+ /* Avoid sprintf, as that infringes on the user's name space.
+ Don't have undefined behavior even if the translation
+ produced a string with the wrong number of "%s"s. */
+ char *yyp = yyresult;
+ int yyi = 0;
+ while ((*yyp = *yyf) != '\0')
+ {
+ if (*yyp == '%' && yyf[1] == 's' && yyi < yycount)
+ {
+ yyp += yytnamerr (yyp, yyarg[yyi++]);
+ yyf += 2;
+ }
+ else
+ {
+ yyp++;
+ yyf++;
+ }
+ }
+ }
+ return yysize;
+ }
+}
+#endif /* YYERROR_VERBOSE */
+
+
+]b4_yydestruct_generate([b4_c_function_def])[
+
+
+/* Prevent warnings from -Wmissing-prototypes. */
+
+#ifdef YYPARSE_PARAM
+]b4_c_function_decl([yyparse], [int],
+ [[void *YYPARSE_PARAM], [YYPARSE_PARAM]])[
+#elif YYPUSH
+]b4_c_function_decl([get_yyresult], [int], [[void *PVVOID], [PVVOID]])[
+]b4_c_function_decl([set_yychar], [void], [[void *PVVOID], [PVVOID]], [[int
yychar], [yychar]])[
+]b4_c_function_decl([yypvarsinit], [void *], [[void], []])[
+]b4_c_function_decl([yyparse], [void],
+ [[void *PVVOID], [PVVOID]])[
+#else /* ! YYPARSE_PARAM */
+]b4_c_function_decl([yyparse], [int], b4_parse_param)[
+#endif /* ! YYPARSE_PARAM */
+
+
+]m4_divert_push([KILL])# ======================== M4 code.
+# b4_declare_parser_variables
+# ---------------------------
+# Declare the variables that are global, or local to YYPARSE if
+# pure-parser.
+m4_define([b4_declare_parser_variables],
+[/* The look-ahead symbol. */
+int yychar;
+
+/* The semantic value of the look-ahead symbol. */
+YYSTYPE yylval;
+
+/* Number of syntax errors so far. */
+int yynerrs;b4_location_if([
+/* Location data for the look-ahead symbol. */
+YYLTYPE yylloc;])
+])
+
+m4_define([b4_init_parser_variables],[
+ b4_yychar = YYEMPTY; /* Cause a token to be read. */
+ b4_yynerrs = 0;
+b4_location_if([[
+#if YYLTYPE_IS_TRIVIAL
+ /* Initialize the default location before parsing starts. */
+ ]b4_yylloc[.first_line = ]b4_yylloc[.last_line = 1;
+ ]b4_yylloc[.first_column = ]b4_yylloc[.last_column = 0;
+#endif
+]])])
+
+# b4_declare_yyparse_variables
+# ----------------------------
+# Declare all the variables that are needed local to YYPARSE
+m4_define([b4_declare_yyparse_variables],
+[[struct yypvars
+ {
+]]b4_declare_parser_variables[[
+ int yystate;
+ int yyn;
+ int yyresult;
+ /* Number of tokens to shift before error messages enabled. */
+ int yyerrstatus;
+ /* Look-ahead token as an internal (translated) token number. */
+ int yytoken;
+
+#if YYERROR_VERBOSE
+ /* Buffer for error messages, and its allocated size. */
+ char yymsgbuf[128];
+ char *yymsg;
+ YYSIZE_T yymsg_alloc;
+#endif
+
+ /* Three stacks and their tools:
+ `yyss': related to states,
+ `yyvs': related to semantic values,
+ `yyls': related to locations.
+
+ Refer to the stacks thru separate pointers, to allow yyoverflow
+ to reallocate them elsewhere. */
+
+ /* The state stack. */
+ yytype_int16 yyssa[YYINITDEPTH];
+ yytype_int16 *yyss;
+ yytype_int16 *yyssp;
+
+ /* The semantic value stack. */
+ YYSTYPE yyvsa[YYINITDEPTH];
+ YYSTYPE *yyvs;
+ YYSTYPE *yyvsp;]]b4_location_if([[[
+ /* The location stack. */
+ YYLTYPE yylsa[YYINITDEPTH];
+ YYLTYPE *yyls;
+ YYLTYPE *yylsp;
+ /* The locations where the error started and ended. */
+ YYLTYPE yyerror_range[2];]]])[
+#define YYPOPSTACK(N) (pv->yyvsp -= (N), pv->yyssp -= (N)]b4_location_if([[,
pv->yylsp -= (N)]])[)
+ YYSIZE_T yystacksize;
+ int yylen;
+ /* The variables used to return semantic value and location from the
+ action routines. */
+ YYSTYPE yyval;
+ /* Used to determine if this is the first time this instance has
+ been used. */
+ int yynew;]b4_location_if([YYLTYPE yyloc;])[
+ };
+
+/* Init the parser data structure. Use malloc, should perhaps use a
+ system dependent equivalent function. */
+void*
+yypvarsinit (void)
+{
+ struct yypvars *pv;
+ pv= (struct yypvars *) malloc(sizeof(struct yypvars));
+ pv->yystate = 0;
+ pv->yyresult = -1;
+ pv->yyerrstatus = 0;
+ pv->yytoken = 0;
+
+#if YYERROR_VERBOSE
+ pv->yymsg = pv->yymsgbuf;
+ pv->yymsg_alloc = sizeof pv->yymsgbuf;
+#endif
+
+ pv->yyss = pv->yyssa;
+ pv->yyvs = pv->yyvsa;
+
+ ]b4_location_if([pv->yyls = pv->yylsa;])[
+ pv->yystacksize = YYINITDEPTH;
+
+ pv->yyssp = pv->yyss;
+ pv->yyvsp = pv->yyvs;
+
+ pv->yynew = 1;
+
+]b4_location_if([ pv->yylsp = pv->yyls;])[
+ /* Init parser variables */
+ ]b4_init_parser_variables()[
+
+ return (void*) pv;
+}
+
+int
+get_yyresult (void *PVVOID)
+{
+ struct yypvars *pv = (struct yypvars*)PVVOID;
+ return pv->yyresult;
+}
+
+void
+set_yychar (void *PVVOID, int yychar)
+{
+ struct yypvars *pv = (struct yypvars*)PVVOID;
+ if (pv)
+ pv->yychar = yychar;
+}])
+m4_divert_pop([KILL])dnl# ====================== End of M4 code.
+
+b4_pure_if([], b4_push_if([],
+ [b4_declare_parser_variables]))
+
+b4_declare_yyparse_variables
+
+/*----------.
+| yyparse. |
+`----------*/
+
+#ifdef YYPARSE_PARAM
+b4_c_function_def([yyparse], [int], [[void *YYPARSE_PARAM], [YYPARSE_PARAM]])
+#elif YYPUSH
+b4_c_function_def([yyparse], [void], [[void *PVVOID], [PVVOID]])
+#else /* ! YYPARSE_PARAM */
+b4_c_function_def([yyparse], [int], b4_parse_param)
+#endif
+{[
+ ]b4_pure_if([b4_declare_parser_variables])[
+ struct yypvars *pv;
+
+ /* The number of symbols on the RHS of the reduced rule.
+ Keep to zero when no symbol should be popped. */
+ YYDPRINTF ((stderr, "Starting parse\n"));
+
+ ]b4_push_if([pv = (struct yypvars*)PVVOID;],[pv = yypvarsinit ();])[
+
+ /* Initialize stack pointers.
+ Waste one element of value and location stack
+ so that they stay on the same level as the state stack.
+ The wasted elements are never initialized. */
+ ]b4_push_if([],[b4_init_parser_variables])[
+
+]m4_ifdef([b4_initial_action], [
+m4_pushdef([b4_at_dollar], [m4_define([b4_at_dollar_used])]b4_yylloc[])dnl
+m4_pushdef([b4_dollar_dollar],
[m4_define([b4_dollar_dollar_used])]b4_yylval[])dnl
+ /* User initialization code. */
+b4_initial_action
+m4_popdef([b4_dollar_dollar])dnl
+m4_popdef([b4_at_dollar])dnl
+/* Line __line__ of yacc.c. */
+b4_syncline(address@hidden@], address@hidden@])
+])dnl
+m4_ifdef([b4_dollar_dollar_used],[[ pv->yyvsp[0] = ]b4_yylval[;
+]])dnl
+m4_ifdef([b4_at_dollar_used], [[ pv->yylsp[0] = ]b4_yylloc[;
+]])dnl
+[ ]b4_push_if([
+ if (pv->yynew == 0) goto gottoken;
+ pv->yynew= 0;])[
+
+ goto yysetstate;
+
+/*------------------------------------------------------------.
+| yynewstate -- Push a new state, which is found in yystate. |
+`------------------------------------------------------------*/
+ yynewstate:
+ /* In all cases, when you get here, the value and location stacks
+ have just been pushed. So pushing a state here evens the stacks. */
+ pv->yyssp++;
+
+ yysetstate:
+ *pv->yyssp = pv->yystate;
+
+ if (pv->yyss + pv->yystacksize - 1 <= pv->yyssp)
+ {
+ /* Get the current used size of the three stacks, in elements. */
+ YYSIZE_T yysize = pv->yyssp - pv->yyss + 1;
+
+#ifdef yyoverflow
+ {
+ /* Give user a chance to reallocate the stack. Use copies of
+ these so that the &'s don't force the real ones into
+ memory. */
+ YYSTYPE *yyvs1 = yyvs;
+ yytype_int16 *yyss1 = yyss;
+]b4_location_if([ YYLTYPE *yyls1 = yyls;])[
+
+ /* Each stack pointer address is followed by the size of the
+ data in use in that stack, in bytes. This used to be a
+ conditional around just the two extra args, but that might
+ be undefined if yyoverflow is a macro. */
+ yyoverflow (YY_("memory exhausted"),
+ &yyss1, yysize * sizeof (*yyssp),
+ &yyvs1, yysize * sizeof (*yyvsp),
+]b4_location_if([ &yyls1, yysize * sizeof (*yylsp),])[
+ &pv->yystacksize);
+]b4_location_if([ yyls = yyls1;])[
+ yyss = yyss1;
+ yyvs = yyvs1;
+ }
+#else /* no yyoverflow */
+# ifndef YYSTACK_RELOCATE
+ goto yyexhaustedlab;
+# else
+ /* Extend the stack our own way. */
+ if (YYMAXDEPTH <= pv->yystacksize)
+ goto yyexhaustedlab;
+ pv->yystacksize *= 2;
+ if (YYMAXDEPTH < pv->yystacksize)
+ pv->yystacksize = YYMAXDEPTH;
+
+ {
+ yytype_int16 *yyss;
+ YYSTYPE *yyvs;]b4_location_if([YYLTYPE *yyls;])[
+
+ yytype_int16 *yyss1 = pv->yyss;
+ union yyalloc *yyptr =
+ (union yyalloc *) YYSTACK_ALLOC (YYSTACK_BYTES (pv->yystacksize));
+ if (! yyptr)
+ goto yyexhaustedlab;
+ YYSTACK_RELOCATE (yyss);
+ YYSTACK_RELOCATE (yyvs);
+]b4_location_if([ YYSTACK_RELOCATE (yyls);])[
+# undef YYSTACK_RELOCATE
+ if (yyss1 != pv->yyssa)
+ YYSTACK_FREE (yyss1);
+ }
+# endif
+#endif /* no yyoverflow */
+
+ pv->yyssp = pv->yyss + yysize - 1;
+ pv->yyvsp = pv->yyvs + yysize - 1;
+]b4_location_if([ pv->yylsp = pv->yyls + yysize - 1;])[
+
+ YYDPRINTF ((stderr, "Stack size increased to %lu\n",
+ (unsigned long int) pv->yystacksize));
+
+ if (pv->yyss + pv->yystacksize - 1 <= pv->yyssp)
+ YYABORT;
+ }
+
+ YYDPRINTF ((stderr, "Entering state %d\n", pv->yystate));
+
+ goto yybackup;
+
+/*-----------.
+| yybackup. |
+`-----------*/
+yybackup:
+
+ /* Do appropriate processing given the current state. Read a
+ look-ahead token if we need one and don't already have one. */
+
+ /* First try to decide what to do without reference to look-ahead token. */
+ pv->yyn = yypact[pv->yystate];
+ if (pv->yyn == YYPACT_NINF)
+ goto yydefault;
+
+ /* Not known => get a look-ahead token if don't already have one. */
+
+ /* YYCHAR is either YYEMPTY or YYEOF or a valid look-ahead symbol. */
+ if (]b4_yychar[ == YYEMPTY)
+ {
+ ]b4_push_if([
+ YYDPRINTF ((stderr, "Returns for a new token: "));
+ pv->yyresult= 4;
+ return;
+gottoken:
+ YYDPRINTF((stderr, "\nGot token %d", pv->yychar));],[
+ YYDPRINTF ((stderr, "Reading a token: "));
+ ]b4_yychar[ = YYLEX;])[
+ }
+
+ if (]b4_yychar[ <= YYEOF)
+ {
+ ]b4_yychar[ = pv->yytoken = YYEOF;
+ YYDPRINTF ((stderr, "Now at end of input.\n"));
+ }
+ else
+ {
+ pv->yytoken = YYTRANSLATE (]b4_yychar[);
+ YY_SYMBOL_PRINT ("Next token is", pv->yytoken, &]b4_yylval[,
&]b4_yylloc[);
+ }
+
+ /* If the proper action on seeing token YYTOKEN is to reduce or to
+ detect an error, take that action. */
+ pv->yyn += pv->yytoken;
+ if (pv->yyn < 0 || YYLAST < pv->yyn || yycheck[pv->yyn] != pv->yytoken)
+ goto yydefault;
+ pv->yyn = yytable[pv->yyn];
+ if (pv->yyn <= 0)
+ {
+ if (pv->yyn == 0 || pv->yyn == YYTABLE_NINF)
+ goto yyerrlab;
+ pv->yyn = -pv->yyn;
+ goto yyreduce;
+ }
+
+ if (pv->yyn == YYFINAL)
+ YYACCEPT;
+
+ /* Count tokens shifted since error; after three, turn off error
+ status. */
+ if (pv->yyerrstatus)
+ pv->yyerrstatus--;
+
+ /* Shift the look-ahead token. */
+ YY_SYMBOL_PRINT ("Shifting", pv->yytoken, &]b4_yylval[, &]b4_yylloc[);
+
+ /* Discard the shifted token unless it is eof. */
+ if (]b4_yychar[ != YYEOF)
+ ]b4_yychar[ = YYEMPTY;
+
+ pv->yystate = pv->yyn;
+ *++(pv->yyvsp) = ]b4_yylval[;
+]b4_location_if([ *++(pv->yylsp) = ]b4_yylloc[;])[
+ goto yynewstate;
+
+
+/*-----------------------------------------------------------.
+| yydefault -- do the default action for the current state. |
+`-----------------------------------------------------------*/
+yydefault:
+ pv->yyn = yydefact[pv->yystate];
+ if (pv->yyn == 0)
+ goto yyerrlab;
+ goto yyreduce;
+
+
+/*-----------------------------.
+| yyreduce -- Do a reduction. |
+`-----------------------------*/
+yyreduce:
+ /* yyn is the number of a rule to reduce with. */
+ pv->yylen = yyr2[pv->yyn];
+
+ /* If YYLEN is nonzero, implement the default value of the action:
+ `$$ = $1'.
+
+ Otherwise, the following line sets YYVAL to garbage.
+ This behavior is undocumented and Bison
+ users should not rely upon it. Assigning to YYVAL
+ unconditionally makes the parser a bit smaller, and it avoids a
+ GCC warning that YYVAL may be used uninitialized. */
+ pv->yyval = pv->yyvsp[1-pv->yylen];
+
+]b4_location_if(
+[[ /* Default location. */
+ YYLLOC_DEFAULT (pv->yyloc, (pv->yylsp - pv->yylen), pv->yylen);]])[
+ YY_REDUCE_PRINT (pv->yyn);
+ switch (pv->yyn)
+ {
+ ]b4_actions
+/* Line __line__ of yacc.c. */
+b4_syncline(address@hidden@], address@hidden@])[
+ default: break;
+ }
+ YY_SYMBOL_PRINT ("-> $$ =", yyr1[pv->yyn], &pv->yyval, &pv->yyloc);
+
+ YYPOPSTACK (pv->yylen);
+ pv->yylen = 0;
+ YY_STACK_PRINT (pv->yyss, pv->yyssp);
+
+ *++(pv->yyvsp) = pv->yyval;
+]b4_location_if([ *++(pv->yylsp) = pv->yyloc;])[
+
+ /* Now `shift' the result of the reduction. Determine what state
+ that goes to, based on the state we popped back to and the rule
+ number reduced by. */
+
+ pv->yyn = yyr1[pv->yyn];
+
+ pv->yystate = yypgoto[pv->yyn - YYNTOKENS] + *pv->yyssp;
+ if (0 <= pv->yystate && pv->yystate <= YYLAST && yycheck[pv->yystate] ==
*pv->yyssp)
+ pv->yystate = yytable[pv->yystate];
+ else
+ pv->yystate = yydefgoto[pv->yyn - YYNTOKENS];
+
+ goto yynewstate;
+
+
+/*------------------------------------.
+| yyerrlab -- here on detecting error |
+`------------------------------------*/
+yyerrlab:
+ /* If not already recovering from an error, report this error. */
+ if (!pv->yyerrstatus)
+ {
+ ++]b4_yynerrs[;
+#if ! YYERROR_VERBOSE
+ yyerror (]b4_yyerror_args[YY_("syntax error"));
+#else
+ {
+ YYSIZE_T yysize = yysyntax_error (0, pv->yystate, ]b4_yychar[);
+ if (pv->yymsg_alloc < yysize && pv->yymsg_alloc < YYSTACK_ALLOC_MAXIMUM)
+ {
+ YYSIZE_T yyalloc = 2 * yysize;
+ if (! (yysize <= yyalloc && yyalloc <= YYSTACK_ALLOC_MAXIMUM))
+ yyalloc = YYSTACK_ALLOC_MAXIMUM;
+ if (pv->yymsg != pv->yymsgbuf)
+ YYSTACK_FREE (pv->yymsg);
+ pv->yymsg = (char *) YYSTACK_ALLOC (yyalloc);
+ if (pv->yymsg)
+ pv->yymsg_alloc = yyalloc;
+ else
+ {
+ pv->yymsg = pv->yymsgbuf;
+ pv->yymsg_alloc = sizeof pv->yymsgbuf;
+ }
+ }
+
+ if (0 < yysize && yysize <= pv->yymsg_alloc)
+ {
+ (void) yysyntax_error (pv->yymsg, pv->yystate, ]b4_yychar[);
+ yyerror (]b4_yyerror_args[pv->yymsg);
+ }
+ else
+ {
+ yyerror (]b4_yyerror_args[YY_("syntax error"));
+ if (yysize != 0)
+ goto yyexhaustedlab;
+ }
+ }
+#endif
+ }
+
+]b4_location_if([[ pv->yyerror_range[0] = ]b4_yylloc[;]])[
+
+ if (pv->yyerrstatus == 3)
+ {
+ /* If just tried and failed to reuse look-ahead token after an
+ error, discard it. */
+
+ if (]b4_yychar[ <= YYEOF)
+ {
+ /* Return failure if at end of input. */
+ if (]b4_yychar[ == YYEOF)
+ YYABORT;
+ }
+ else
+ {
+ yydestruct ("Error: discarding",
+ pv->yytoken, &]b4_yylval[]b4_location_if([,
&]b4_yylloc[])[]b4_user_args[);
+ ]b4_yychar[ = YYEMPTY;
+ }
+ }
+
+ /* Else will try to reuse look-ahead token after shifting the error
+ token. */
+ goto yyerrlab1;
+
+
+/*---------------------------------------------------.
+| yyerrorlab -- error raised explicitly by YYERROR. |
+`---------------------------------------------------*/
+yyerrorlab:
+
+ /* Pacify compilers like GCC when the user code never invokes
+ YYERROR and the label yyerrorlab therefore never appears in user
+ code. */
+ if (/*CONSTCOND*/ 0)
+ goto yyerrorlab;
+
+]b4_location_if([[ pv->yyerror_range[0] = pv->yylsp[1-pv->yylen];
+]])[ /* Do not reclaim the symbols of the rule which action triggered
+ this YYERROR. */
+ YYPOPSTACK (pv->yylen);
+ pv->yylen = 0;
+ YY_STACK_PRINT (pv->yyss, pv->yyssp);
+ pv->yystate = *pv->yyssp;
+ goto yyerrlab1;
+
+
+/*-------------------------------------------------------------.
+| yyerrlab1 -- common code for both syntax error and YYERROR. |
+`-------------------------------------------------------------*/
+yyerrlab1:
+ pv->yyerrstatus = 3; /* Each real token shifted decrements this. */
+
+ for (;;)
+ {
+ pv->yyn = yypact[pv->yystate];
+ if (pv->yyn != YYPACT_NINF)
+ {
+ pv->yyn += YYTERROR;
+ if (0 <= pv->yyn && pv->yyn <= YYLAST && yycheck[pv->yyn] == YYTERROR)
+ {
+ pv->yyn = yytable[pv->yyn];
+ if (0 < pv->yyn)
+ break;
+ }
+ }
+
+ /* Pop the current state because it cannot handle the error token. */
+ if (pv->yyssp == pv->yyss)
+ YYABORT;
+
+]b4_location_if([[ pv->yyerror_range[0] = *pv->yylsp;]])[
+ yydestruct ("Error: popping",
+ yystos[pv->yystate], pv->yyvsp]b4_location_if([,
pv->yylsp])[]b4_user_args[);
+ YYPOPSTACK (1);
+ pv->yystate = *pv->yyssp;
+ YY_STACK_PRINT (pv->yyss, pv->yyssp);
+ }
+
+ if (pv->yyn == YYFINAL)
+ YYACCEPT;
+
+ *++(pv->yyvsp) = ]b4_yylval[;
+]b4_location_if([[
+ pv->yyerror_range[1] = ]b4_yylloc[;
+ /* Using YYLLOC is tempting, but would change the location of
+ the look-ahead. YYLOC is available though. */
+ YYLLOC_DEFAULT (pv->yyloc, (pv->yyerror_range - 1), 2);
+ *++(pv->yylsp) = pv->yyloc;]])[
+
+ /* Shift the error token. */
+ YY_SYMBOL_PRINT ("Shifting", yystos[pv->yyn], pv->yyvsp, pv->yylsp);
+
+ pv->yystate = pv->yyn;
+ goto yynewstate;
+
+
+/*-------------------------------------.
+| yyacceptlab -- YYACCEPT comes here. |
+`-------------------------------------*/
+yyacceptlab:
+ pv->yyresult = 0;
+ goto yyreturn;
+
+/*-----------------------------------.
+| yyabortlab -- YYABORT comes here. |
+`-----------------------------------*/
+yyabortlab:
+ pv->yyresult = 1;
+ goto yyreturn;
+
+#ifndef yyoverflow
+/*-------------------------------------------------.
+| yyexhaustedlab -- memory exhaustion comes here. |
+`-------------------------------------------------*/
+yyexhaustedlab:
+ yyerror (]b4_yyerror_args[YY_("memory exhausted"));
+ pv->yyresult = 2;
+ /* Fall through. */
+#endif
+
+yyreturn:
+ if (]b4_yychar[ != YYEOF && ]b4_yychar[ != YYEMPTY)
+ yydestruct ("Cleanup: discarding lookahead",
+ pv->yytoken, &]b4_yylval[]b4_location_if([,
&]b4_yylloc[])[]b4_user_args[);
+ /* Do not reclaim the symbols of the rule which action triggered
+ this YYABORT or YYACCEPT. */
+ YYPOPSTACK (pv->yylen);
+ YY_STACK_PRINT (pv->yyss, pv->yyssp);
+ while (pv->yyssp != pv->yyss)
+ {
+ yydestruct ("Cleanup: popping",
+ yystos[*pv->yyssp], pv->yyvsp]b4_location_if([,
pv->yylsp])[]b4_user_args[);
+ YYPOPSTACK (1);
+ }
+#ifndef yyoverflow
+ if (pv->yyss != pv->yyssa)
+ YYSTACK_FREE (pv->yyss);
+#endif
+#if YYERROR_VERBOSE
+ if (pv->yymsg != pv->yymsgbuf)
+ YYSTACK_FREE (pv->yymsg);
+#endif
+
+ ]b4_push_if([],[{
+ int yyresult = pv->yyresult;
+ free (pv);
+ return yyresult;}])[
+]}
+
+
+b4_epilogue
+m4_if(b4_defines_flag, 0, [],
address@hidden @output_header_name@
+b4_copyright([Skeleton parser for Yacc-like parsing with Bison],
+ [1984, 1989, 1990, 2000, 2001, 2002, 2003, 2004, 2005, 2006])
+
+/* As a special exception, when this file is copied by Bison into a
+ Bison output file, you may use that output file without restriction.
+ This special exception was added by the Free Software Foundation
+ in version 1.24 of Bison. */
+
+b4_token_enums_defines(b4_tokens)
+
+#if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
+m4_ifdef([b4_stype],
+[typedef union[]m4_bregexp(b4_stype, [^{], [ YYSTYPE])
+b4_stype
+/* Line __line__ of yacc.c. */
+b4_syncline(address@hidden@], address@hidden@])
+ YYSTYPE;],
+[typedef int YYSTYPE;])
+# define yystype YYSTYPE /* obsolescent; will be withdrawn */
+# define YYSTYPE_IS_DECLARED 1
+# define YYSTYPE_IS_TRIVIAL 1
+#endif
+
+b4_pure_if([],
+[extern YYSTYPE b4_prefix[]lval;])
+
+b4_location_if(
+[#if ! defined YYLTYPE && ! defined YYLTYPE_IS_DECLARED
+typedef struct YYLTYPE
+{
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;
+} YYLTYPE;
+# define yyltype YYLTYPE /* obsolescent; will be withdrawn */
+# define YYLTYPE_IS_DECLARED 1
+# define YYLTYPE_IS_TRIVIAL 1
+#endif
+
+m4_if(b4_pure, [0],
+[extern YYLTYPE b4_prefix[]lloc;])
+])
+])
Index: src/getargs.c
===================================================================
RCS file: /cvsroot/bison/bison/src/getargs.c,v
retrieving revision 1.66
diff -u -r1.66 getargs.c
--- src/getargs.c 3 Jan 2006 19:12:55 -0000 1.66
+++ src/getargs.c 7 Apr 2006 09:30:31 -0000
@@ -58,6 +58,7 @@
bool nondeterministic_parser = false;
bool glr_parser = false;
bool pure_parser = false;
+bool push_parser = false;
const char *skeleton = NULL;
const char *include = NULL;
Index: src/getargs.h
===================================================================
RCS file: /cvsroot/bison/bison/src/getargs.h,v
retrieving revision 1.28
diff -u -r1.28 getargs.h
--- src/getargs.h 24 Jul 2005 07:24:22 -0000 1.28
+++ src/getargs.h 7 Apr 2006 09:30:31 -0000
@@ -50,6 +50,11 @@
extern bool pure_parser;
+/* PUSH_PARSER is true if should generate a parser that is capble of being
+ called asynchronously. Is must be pure and reentrant. */
+
+extern bool push_parser;
+
/* NONDETERMINISTIC_PARSER is true iff conflicts are accepted. This
is used by the GLR parser, and might be used in BackTracking
parsers too. */
Index: src/output.c
===================================================================
RCS file: /cvsroot/bison/bison/src/output.c,v
retrieving revision 1.245
diff -u -r1.245 output.c
--- src/output.c 21 Jan 2006 04:35:09 -0000 1.245
+++ src/output.c 7 Apr 2006 09:30:31 -0000
@@ -590,6 +590,7 @@
MUSCLE_INSERT_BOOL ("error_verbose", error_verbose);
MUSCLE_INSERT_BOOL ("locations_flag", locations_flag);
MUSCLE_INSERT_BOOL ("pure", pure_parser);
+ MUSCLE_INSERT_BOOL ("push", push_parser);
MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_flag);
/* File names. */
Index: src/parse-gram.y
===================================================================
RCS file: /cvsroot/bison/bison/src/parse-gram.y,v
retrieving revision 1.73
diff -u -r1.73 parse-gram.y
--- src/parse-gram.y 30 Jan 2006 09:00:40 -0000 1.73
+++ src/parse-gram.y 7 Apr 2006 09:30:31 -0000
@@ -78,7 +78,6 @@
%locations
%pure-parser
%error-verbose
-%defines
%name-prefix="gram_"
%initial-action
@@ -149,6 +148,7 @@
PERCENT_OUTPUT "%output"
PERCENT_PARSE_PARAM "%parse-param {...}"
PERCENT_PURE_PARSER "%pure-parser"
+ PERCENT_PUSH_PARSER "%push-parser"
PERCENT_REQUIRE "%require"
PERCENT_SKELETON "%skeleton"
PERCENT_START "%start"
@@ -245,6 +245,7 @@
| "%output" "=" string_content { spec_outfile = $3; }
| "%parse-param {...}" { add_param ("parse_param", $1, @1);
}
| "%pure-parser" { pure_parser = true; }
+| "%push-parser" { push_parser = true; }
| "%require" string_content { version_check (&@2, $2); }
| "%skeleton" string_content { skeleton = $2; }
| "%token-table" { token_table_flag = true; }
Index: src/scan-gram.l
===================================================================
RCS file: /cvsroot/bison/bison/src/scan-gram.l,v
retrieving revision 1.86
diff -u -r1.86 scan-gram.l
--- src/scan-gram.l 3 Apr 2006 13:50:10 -0000 1.86
+++ src/scan-gram.l 7 Apr 2006 09:30:31 -0000
@@ -245,6 +245,7 @@
"%prec" rule_length--; return PERCENT_PREC;
"%printer" token_type = PERCENT_PRINTER; BEGIN SC_PRE_CODE;
"%pure"[-_]"parser" return PERCENT_PURE_PARSER;
+ "%push"[-_]"parser" return PERCENT_PUSH_PARSER;
"%require" return PERCENT_REQUIRE;
"%right" return PERCENT_RIGHT;
"%skeleton" return PERCENT_SKELETON;
If you have this patch installed, then run this benchmarking script
with Bison in your path. To exercise a built non-installed bison, the
easiest is to use the script "bison" in tests/.
#! /usr/bin/perl -w
use IO::File;
use Benchmark qw (:all);
my $bison = $ENV{'BISON'} || 'bison';
##################################################################
sub triangular_grammar ($$$)
{
my ($base, $max, $directives) = @_;
my $out = new IO::File ">$base.y"
or die;
print $out <<EOF;
%error-verbose
%debug
%{
#include <stdio.h>
#include <stdlib.h>
static int yylex (void);
static void yyerror (const char *msg);
%}
%union
{
int val;
};
%token END "end"
%type <val> exp input
EOF
for my $size (1 .. $max)
{
print $out "%token t$size $size \"$size\"\n";
};
print $out <<EOF;
%%
input:
exp { if (\$1 != 0) abort (); \$\$ = \$1; }
| input exp { if (\$2 != \$1 + 1) abort (); \$\$ = \$2; }
;
exp:
END
{ \$\$ = 0; }
EOF
for my $size (1 .. $max)
{
use Text::Wrap;
print $out wrap ("| ", " ",
(map { "\"$_\"" } (1 .. $size)),
" END \n"),
" { \$\$ = $size; }\n";
};
print $out ";\n";
print $out <<EOF;
%%
static int
yylex (void)
{
static int inner = 1;
static int outer = 0;
if (outer > $max)
return 0;
else if (inner > outer)
{
inner = 1;
++outer;
return END;
}
return inner++;
}
static void
yyerror (const char *msg)
{
fprintf (stderr, "%s\\n", msg);
}
int
main (void)
{
yydebug = !!getenv ("YYDEBUG");
return yyparse ();
}
EOF
}
##################################################################
sub calc_input ($$)
{
my ($base, $max) = @_;
my $out = new IO::File ">$base.input"
or die;
foreach (1 .. $max)
{
print $out
"0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99\n";
print $out
"1+1*(2+2*(3+3*(4+4*(5+5*(6+6*(7+7*(8+8*(9+9*(10+10*(11+11*(12+12*(13+13*(14+14*(15+15*(16+16*(17+17*(18+18*(19+19*(20+20*(21+21*(22+22*(23+23*(24+24*(25+25*(26+26*(27+27*(28+28*(29+29*(30+30*(31+31*(32+32*(33+33*(34+34*(35+35*(36+36*(37+37*(38+38*(39+39*(40+40*(41+41*(42+42*(43+43*(44+44*(45+45*(46+46*(47+47*(48+48*(49+49*(50+50*(51+51*(52+52*(53+53*(54+54*(55+55*(56+56*(57+57*(58+58*(59+59*(60+60*(61+61*(62+62*(63+63*(64+64*(65+65*(66+66*(67+67*(68+68*(69+69*(70+70*(71+71*(72+72*(73+73*(74+74*(75+75*(76+76*(77+77*(78+78*(79+79*(80+80*(81+81*(82+82*(83+83*(84+84*(85+85*(86+86*(87+87*(88+88*(89+89*(90+90*(91+91*(92+92*(93+93*(94+94*(95+95*(96+96*(97+97*(98+98*(99+99*(100+100*(101+101*(102+102*(103+103*(104+104*(105+105*(106+106*(107+107*(108+108*(109+109*(110+110*(111+111*(112+112*(113+113*(114+114*(115+115*(116+116*(117+117*(118+118*(119+119*(120+120*(121+121*(122+122*(123+123*(124+124*(125+125*(126+126*(127+127*(128+128*(129+129*(130+130*(131+131*(132+132*(133+133*(134+134*(135+135*(136+136*(137+137*(138+138*(139+139*(140+140*(141+141*(142+142*(143+143*(144+144*(145+145*(146+146*(147+147*(148+148*(149+149*(150+150*(151+151*(152+152*(153+153*(154+154*(155+155*(156+156*(157+157*(158+158*(159+159*(160+160*(161+161*(162+162*(163+163*(164+164*(165+165*(166+166*(167+167*(168+168*(169+169*(170+170*(171+171*(172+172*(173+173*(174+174*(175+175*(176+176*(177+177*(178+178*(179+179*(180+180*(181+181*(182+182*(183+183*(184+184*(185+185*(186+186*(187+187*(188+188*(189+189*(190+190*(191+191*(192+192*(193+193*(194+194*(195+195*(196+196*(197+197*(198+198*(199+199*(200+200*(201+201*(202+202*(203+203*(204+204*(205+205*(206+206*(207+207*(208+208*(209+209*(210+210*(211+211*(212+212*(213+213*(214+214*(215+215*(216+216*(217+217*(218+218*(219+219*(220+220*(221+221*(222+222*(223+223*(224+224*(225+225*(226+226*(227+227*(228+228*(229+229*(230+230*(231+231*(232+232*(233+233*(234+234*(235+235*(236+236*(237+237*(238+238*(239+239*(240+240*(241+241*(242+242*(243+243*(244+244*(245+245*(246+246*(247+247*(248+248*(249+249*(250+250*(251+251*(252+252*(253+253*(254+254*(255+255*(256+256*(257+257*(258+258*(259+259*(260+260*(261+261*(262+262*(263+263*(264+264*(265+265*(266+266*(267+267*(268+268*(269+269*(270+270*(271+271*(272+272*(273+273*(274+274*(275+275*(276+276*(277+277*(278+278*(279+279*(280+280*(281+281*(282+282*(283+283*(284+284*(285+285*(286+286*(287+287*(288+288*(289+289*(290+290*(291+291*(292+292*(293+293*(294+294*(295+295*(296+296*(297+297*(298+298*(299+299*(300+300*(301+301*(302+302*(303+303*(304+304*(305+305*(306+306*(307+307*(308+308*(309+309*(310+310*(311+311*(312+312*(313+313*(314+314*(315+315*(316+316*(317+317*(318+318*(319+319*(320+320*(321+321*(322+322*(323+323*(324+324*(325+325*(326+326*(327+327*(328+328*(329+329*(330+330*(331+331*(332+332*(333+333*(334+334*(335+335*(336+336*(337+337*(338+338*(339+339*(340+340*(341+341*(342+342*(343+343*(344+344*(345+345*(346+346*(347+347*(348+348*(349+349*(350+350*(351+351*(352+352*(353+353*(354+354*(355+355*(356+356*(357+357*(358+358*(359+359*(360+360*(361+361*(362+362*(363+363*(364+364*(365+365*(366+366*(367+367*(368+368*(369+369*(370+370*(371+371*(372+372*(373+373*(374+374*(375+375*(376+376*(377+377*(378+378*(379+379*(380+380*(381+381*(382+382*(383+383*(384+384*(385+385*(386+386*(387+387*(388+388*(389+389*(390+390*(391+391*(392+392*(393+393*(394+394*(395+395*(396+396*(397+397*(398+398*(399+399*(400+400*(401+401*(402+402*(403+403*(404+404*(405+405*(406+406*(407+407*(408+408*(409+409*(410+410*(411+411*(412+412*(413+413*(414+414*(415+415*(416+416*(417+417*(418+418*(419+419*(420+420*(421+421*(422+422*(423+423*(424+424*(425+425*(426+426*(427+427*(428+428*(429+429*(430+430*(431+431*(432+432*(433+433*(434+434*(435+435*(436+436*(437+437*(438+438*(439+439*(440+440*(441+441*(442+442*(443+443*(444+444*(445+445*(446+446*(447+447*(448+448*(449+449*(450+450*(451+451*(452+452*(453+453*(454+454*(455+455*(456+456*(457+457*(458+458*(459+459*(460+460*(461+461*(462+462*(463+463*(464+464*(465+465*(466+466*(467+467*(468+468*(469+469*(470+470*(471+471*(472+472*(473+473*(474+474*(475+475*(476+476*(477+477*(478+478*(479+479*(480+480*(481+481*(482+482*(483+483*(484+484*(485+485*(486+486*(487+487*(488+488*(489+489*(490+490*(491+491*(492+492*(493+493*(494+494*(495+495*(496+496*(497+497*(498+498*(499+499*(500+500*(501+501*(502+502*(503+503*(504+504*(505+505*(506+506*(507+507*(508+508*(509+509*(510+510*(511+511*(512+512*(513+513*(514+514*(515+515*(516+516*(517+517*(518+518*(519+519*(520+520*(521+521*(522+522*(523+523*(524+524*(525+525*(526+526*(527+527*(528+528*(529+529*(530+530*(531+531*(532+532*(533+533*(534+534*(535+535*(536+536*(537+537*(538+538*(539+539*(540+540*(541+541*(542+542*(543+543*(544+544*(545+545*(546+546*(547+547*(548+548*(549+549*(550+550*(551+551*(552+552*(553+553*(554+554*(555+555*(556+556*(557+557*(558+558*(559+559*(560+560*(561+561*(562+562*(563+563*(564+564*(565+565*(566+566*(567+567*(568+568*(569+569*(570+570*(571+571*(572+572*(573+573*(574+574*(575+575*(576+576*(577+577*(578+578*(579+579*(580+580*(581+581*(582+582*(583+583*(584+584*(585+585*(586+586*(587+587*(588+588*(589+589*(590+590*(591+591*(592+592*(593+593*(594+594*(595+595*(596+596*(597+597*(598+598*(599+599*(600+600*(601+601*(602+602*(603+603*(604+604*(605+605*(606+606*(607+607*(608+608*(609+609*(610+610*(611+611*(612+612*(613+613*(614+614*(615+615*(616+616*(617+617*(618+618*(619+619*(620+620*(621+621*(622+622*(623+623*(624+624*(625+625*(626+626*(627+627*(628+628*(629+629*(630+630*(631+631*(632+632*(633+633*(634+634*(635+635*(636+636*(637+637*(638+638*(639+639*(640+640*(641+641*(642+642*(643+643*(644+644*(645+645*(646+646*(647+647*(648+648*(649+649*(650+650*(651+651*(652+652*(653+653*(654+654*(655+655*(656+656*(657+657*(658+658*(659+659*(660+660*(661+661*(662+662*(663+663*(664+664*(665+665*(666+666*(667+667*(668+668*(669+669*(670+670*(671+671*(672+672*(673+673*(674+674*(675+675*(676+676*(677+677*(678+678*(679+679*(680+680*(681+681*(682+682*(683+683*(684+684*(685+685*(686+686*(687+687*(688+688*(689+689*(690+690*(691+691*(692+692*(693+693*(694+694*(695+695*(696+696*(697+697*(698+698*(699+699*(700+700*(701+701*(702+702*(703+703*(704+704*(705+705*(706+706*(707+707*(708+708*(709+709*(710+710*(711+711*(712+712*(713+713*(714+714*(715+715*(716+716*(717+717*(718+718*(719+719*(720+720*(721+721*(722+722*(723+723*(724+724*(725+725*(726+726*(727+727*(728+728*(729+729*(730+730*(731+731*(732+732*(733+733*(734+734*(735+735*(736+736*(737+737*(738+738*(739+739*(740+740*(741+741*(742+742*(743+743*(744+744*(745+745*(746+746*(747+747*(748+748*(749+749*(750+750*(751+751*(752+752*(753+753*(754+754*(755+755*(756+756*(757+757*(758+758*(759+759*(760+760*(761+761*(762+762*(763+763*(764+764*(765+765*(766+766*(767+767*(768+768*(769+769*(770+770*(771+771*(772+772*(773+773*(774+774*(775+775*(776+776*(777+777*(778+778*(779+779*(780+780*(781+781*(782+782*(783+783*(784+784*(785+785*(786+786*(787+787*(788+788*(789+789*(790+790*(791+791*(792+792*(793+793*(794+794*(795+795*(796+796*(797+797*(798+798*(799+799*(800+800*(801+801*(802+802*(803+803*(804+804*(805+805*(806+806*(807+807*(808+808*(809+809*(810+810*(811+811*(812+812*(813+813*(814+814*(815+815*(816+816*(817+817*(818+818*(819+819*(820+820*(821+821*(822+822*(823+823*(824+824*(825+825*(826+826*(827+827*(828+828*(829+829*(830+830*(831+831*(832+832*(833+833*(834+834*(835+835*(836+836*(837+837*(838+838*(839+839*(840+840*(841+841*(842+842*(843+843*(844+844*(845+845*(846+846*(847+847*(848+848*(849+849*(850+850*(851+851*(852+852*(853+853*(854+854*(855+855*(856+856*(857+857*(858+858*(859+859*(860+860*(861+861*(862+862*(863+863*(864+864*(865+865*(866+866*(867+867*(868+868*(869+869*(870+870*(871+871*(872+872*(873+873*(874+874*(875+875*(876+876*(877+877*(878+878*(879+879*(880+880*(881+881*(882+882*(883+883*(884+884*(885+885*(886+886*(887+887*(888+888*(889+889*(890+890*(891+891*(892+892*(893+893*(894+894*(895+895*(896+896*(897+897*(898+898*(899+899*(900+900*(901+901*(902+902*(903+903*(904+904*(905+905*(906+906*(907+907*(908+908*(909+909*(910+910*(911+911*(912+912*(913+913*(914+914*(915+915*(916+916*(917+917*(918+918*(919+919*(920+920*(921+921*(922+922*(923+923*(924+924*(925+925*(926+926*(927+927*(928+928*(929+929*(930+930*(931+931*(932+932*(933+933*(934+934*(935+935*(936+936*(937+937*(938+938*(939+939*(940+940*(941+941*(942+942*(943+943*(944+944*(945+945*(946+946*(947+947*(948+948*(949+949*(950+950*(951+951*(952+952*(953+953*(954+954*(955+955*(956+956*(957+957*(958+958*(959+959*(960+960*(961+961*(962+962*(963+963*(964+964*(965+965*(966+966*(967+967*(968+968*(969+969*(970+970*(971+971*(972+972*(973+973*(974+974*(975+975*(976+976*(977+977*(978+978*(979+979*(980+980*(981+981*(982+982*(983+983*(984+984*(985+985*(986+986*(987+987*(988+988*(989+989*(990+990*(991+991*(992+992*(993+993*(994+994*(995+995*(996+996*(997+997*(998+998*(999+999*(1000+1000*(1001))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))\n";
}
}
##################################################################
sub calc_grammar ($$$)
{
my ($base, $max, $directives) = @_;
my $out = new IO::File ">$base.y"
or die;
print $out <<EOF;
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define USE(Var)
/* Exercise pre-prologue dependency to %union. */
typedef int semantic_value;
static semantic_value global_result = 0;
static int global_count = 0;
%}
/* Exercise %union. */
$directives
%error-verbose
%union
{
semantic_value ival;
};
%{
static int power (int base, int exponent);
/* yyerror receives the location if:
- %location & %pure & %glr
- %location & %pure & %yacc & %parse-param. */
static void yyerror (const char *s);
#if YYPURE
static int yylex (YYSTYPE* yylvalp);
#else
static int yylex (void);
#endif
%}
/* Bison Declarations */
%token CALC_EOF 0 "end of input"
%token <ival> NUM "number"
%type <ival> exp
%nonassoc '=' /* comparison */
%left '-' '+'
%left '*' '/'
%left NEG /* negation--unary minus */
%right '^' /* exponentiation */
/* Grammar follows */
%%
input:
line
| input line
;
line:
'\\n'
| exp '\\n' { USE (\$1); }
;
exp:
NUM { \$\$ = \$1; }
| exp '=' exp
{
if (\$1 != \$3)
fprintf (stderr, "calc: error: %d != %d\\n", \$1, \$3);
\$\$ = \$1;
}
| exp '+' exp { \$\$ = \$1 + \$3; }
| exp '-' exp { \$\$ = \$1 - \$3; }
| exp '*' exp { \$\$ = \$1 * \$3; }
| exp '/' exp { \$\$ = \$1 / \$3; }
| '-' exp %prec NEG { \$\$ = -\$2; }
| exp '^' exp { \$\$ = power (\$1, \$3); }
| '(' exp ')' { \$\$ = \$2; }
| '(' error ')' { \$\$ = 1111; }
| '!' { \$\$ = 0; YYERROR; }
| '-' error { \$\$ = 0; YYERROR; }
;
%%
/* The input. */
static FILE *input;
static void
yyerror (const char *s)
{
fprintf (stderr, "%s\\n", s);
}
static int
get_char (void)
{
return getc (input);
}
static void
unget_char ( int c)
{
ungetc (c, input);
}
static int
read_signed_integer (void)
{
int c = get_char ();
int sign = 1;
int n = 0;
if (c == '-')
{
c = get_char ();
sign = -1;
}
while (isdigit (c))
{
n = 10 * n + (c - '0');
c = get_char ();
}
unget_char (c);
return sign * n;
}
#if YYPUSH
static YYSTYPE yylval;
#endif
static int
#if YYPURE
# define yylval (*yylvalp)
yylex (YYSTYPE* yylvalp)
#else
yylex (void)
#endif
{
int c;
/* Skip white space. */
while ((c = get_char ()) == ' ' || c == '\t')
{
}
/* process numbers */
if (c == '.' || isdigit (c))
{
unget_char ( c);
yylval.ival = read_signed_integer ();
return NUM;
}
/* Return end-of-file. */
if (c == EOF)
return CALC_EOF;
/* Return single chars. */
return c;
}
static int
power (int base, int exponent)
{
int res = 1;
if (exponent < 0)
exit (3);
for (/* Niente */; exponent; --exponent)
res *= base;
return res;
}
#if YYPUSH
static int
yyparse_wrapper ()
{
struct yypvars *ctx = yypvarsinit ();
do {
yyparse (ctx);
set_yychar (ctx, yylex ());
ctx->yylval = yylval;
} while (get_yyresult (ctx) != 0);
free (ctx);
}
#define yyparse yyparse_wrapper
#endif
int
main (int argc, const char **argv)
{
semantic_value result = 0;
int count = 0;
int status;
input = fopen ("calc.input", "r");
if (!input)
{
perror ("calc.input");
return 3;
}
status = yyparse ();
if (global_result != result)
abort ();
if (global_count != count)
abort ();
return status;
}
EOF
}
##################################################################
sub compile ($)
{
my ($base) = @_;
system ("bison $base.y -o $base.c");
system ("gcc -O2 $base.c -o $base");
}
sub bench_grammar ($)
{
my ($gram) = @_;
my %test =
(
"yacc-yacc" => '',
"yacc-pure" => '%pure-parser',
"push-yacc" => '%skeleton "push.c"',
"push-pure" => '%skeleton "push.c" %pure-parser',
"push-push" => '%skeleton "push.c" %push-parser',
);
my %bench;
while (my ($name, $directives) = each %test)
{
print STDERR "$name\n";
my $generator = "$gram" . "_grammar";
&$generator ($name, 200, $directives);
compile ($name);
$bench{$name} = "system ('./$name');"
}
print "$gram:\n";
my $res = timethese (50, \%bench);
cmpthese ($res);
}
calc_input ('calc', 200);
bench_grammar ('calc');
### Setup "GNU" style for perl-mode and cperl-mode.
## Local Variables:
## perl-indent-level: 2
## perl-continued-statement-offset: 2
## perl-continued-brace-offset: 0
## perl-brace-offset: 0
## perl-brace-imaginary-offset: 0
## perl-label-offset: -2
## cperl-indent-level: 2
## cperl-brace-offset: 0
## cperl-continued-brace-offset: 0
## cperl-label-offset: -2
## cperl-extra-newline-before-brace: t
## cperl-merge-trailing-else: nil
## cperl-continued-statement-offset: 2
## End:
- Re: push parser implemenation, (continued)
- Re: push parser implemenation, Frans Englich, 2006/04/05
- Re: push parser implemenation, Bob Rossi, 2006/04/05
- Re: push parser implemenation, Frans Englich, 2006/04/05
- Re: push parser implemenation, Bob Rossi, 2006/04/05
- Re: push parser implemenation, Frans Englich, 2006/04/05
- Re: push parser implemenation, Bob Rossi, 2006/04/05
Re: push parser implemenation,
Akim Demaille <=
- Re: push parser implemenation, Akim Demaille, 2006/04/07
- Re: push parser implemenation, Bob Rossi, 2006/04/07
- Re: push parser implemenation, Akim Demaille, 2006/04/07
- Re: push parser implemenation, Bob Rossi, 2006/04/07
- Re: push parser implemenation, Bob Rossi, 2006/04/07
- Re: push parser implemenation, Akim Demaille, 2006/04/20
- Re: push parser implemenation, Akim Demaille, 2006/04/20
Re: push parser implemenation, Bob Rossi, 2006/04/07
Re: push parser implemenation, Bob Rossi, 2006/04/07