Re: push parser

[Bob Rossi]

On Tue, Oct 10, 2006 at 09:55:54AM -0700, Paul Eggert wrote:
> Bob Rossi <address@hidden> writes:
> 
> > Should I modify the test suite somehow so that tests 90 and 96 
> > explicitly use the push.c skeleton?
> 
> I'd rather just get rid of push.c and copy its contents to yacc.c.
> That should be fairly safe, no?

Here is an annotated difference between yacc and push. It may have
been unnecessary, but at least I took the time to check out all 
the differences and at least sanity check that everything looks good.

Bob Rossi

--- yacc.c      2006-10-10 14:06:22.000000000 -0400
+++ push.c      2006-10-10 10:49:23.000000000 -0400
    @@ -152,6 +152,9 @@
     m4_if(b4_prefix, [yy], [],
     [/* Substitute the variable and function names.  */
     #define yyparse b4_prefix[]parse
    +#define yypushparse b4_prefix[]pushparse
    +#define yypvarsinit b4_prefix[]pvarsinit
    +#define yypvars b4_prefix[]pvars
     #define yylex   b4_prefix[]lex
     #define yyerror b4_prefix[]error
     #define yylval  b4_prefix[]lval

These are 3 new symbols that get defined depending on the prefix.

    @@ -964,6 +967,16 @@
     ]b4_c_function_decl([yyparse], [int], b4_parse_param)[
     #endif /* ! YYPARSE_PARAM */
     
    +]b4_push_if([
    +struct yypvars;
    +enum { YYPUSH_MORE = 4 };
    +]b4_c_function_decl([yypvarsinit], [void *], [[void], []])[
    +]b4_c_function_decl([yypushparse], [int],
    +   [[struct yypvars *yypvars], [yypvars]],
    +   [[int yynchar], [yynchar]],
    +   [[YYSTYPE *yynlval], [yynlval]]
    +   b4_locations_if([,[[YYLTYPE *yynlloc], [yynlloc]]]))[
    +])[
     
     ]m4_divert_push([KILL])# ======================== M4 code.
     # b4_declare_parser_variables

In push mode, these are new declarations.

    @@ -978,27 +991,126 @@
     YYSTYPE yylval;
     
     /* Number of syntax errors so far.  */
    -int yynerrs;b4_locations_if([
    +]b4_push_if([],[
    +int yynerrs;])[b4_locations_if([
     /* Location data for the lookahead symbol.  */
     YYLTYPE yylloc;])
     ])

In push mode, there is no yynerrs. I could remove this part of the 
diff and just leave yynerrs, but it's never used.

    +# b4_declare_yyparse_variables
    +# ----------------------------
    +# Declare all the variables that are needed local to YYPARSE
    +m4_define([b4_declare_yyparse_variables],
    +[[struct yypvars
    +  {
    +    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 *yymsgbuf_ptr;
    +    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 *yyssa_ptr;
    +    yytype_int16 *yyss;
    +    yytype_int16 *yyssp;
    +
    +    /* The semantic value stack.  */
    +    YYSTYPE yyvsa[YYINITDEPTH];
    +    YYSTYPE *yyvs;
    +    YYSTYPE *yyvsp;]]b4_locations_if([[[
    +    /* The location stack.  */
    +    YYLTYPE yylsa[YYINITDEPTH];
    +    YYLTYPE *yyls;
    +    YYLTYPE *yylsp;
    +    /* The locations where the error started and ended.  */
    +    YYLTYPE yyerror_range[2];
    +    YYLTYPE *yyerror_range_ptr;]]])[
    +    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_locations_if([YYLTYPE yyloc;])[
    +  };
    +
    +/* Initialize the parser data structure.  */
    +void *
    +yypvarsinit (void)
    +{
    +  struct yypvars *pv = (struct yypvars *) malloc (sizeof *pv);
    +  pv->yystate = 0;
    +  pv->yyresult = -1;
    +  pv->yyerrstatus = 0;
    +  pv->yytoken = 0;
     
    +#if YYERROR_VERBOSE
    +  pv->yymsgbuf_ptr = pv->yymsgbuf;
    +  pv->yymsg = pv->yymsgbuf;
    +  pv->yymsg_alloc = sizeof pv->yymsgbuf;
    +#endif
    +
    +  pv->yyssa_ptr = pv->yyssa;
    +  pv->yyss = pv->yyssa;
    +  pv->yyvs = pv->yyvsa;
    +
    +  ]b4_locations_if([
    +    pv->yyls = pv->yylsa;])[
    +  pv->yystacksize = YYINITDEPTH;
    +
    +  pv->yyssp = pv->yyss;
    +  pv->yyvsp = pv->yyvs;
    +
    +  pv->yynew = 1;
    +
    +]b4_locations_if([  pv->yylsp = pv->yyls;])[
    +
    +  return (void *) pv;
    +}])
 
Declaring the 'struct yypvars' and the yypvarsinit function.

    -/*----------.
    -| yyparse.  |
    -`----------*/
    +b4_push_if([],[b4_pure_if([],
    +      [b4_declare_parser_variables])])

Only declare the parser variables in global scope for the normal parser,
not the push or pure parser.
 
    +b4_push_if([b4_declare_yyparse_variables])

Actually declare yypvars and yypvarsinit. This probably didn't have to
be in a macro. Not sure why I did it this way.

    +/*-------------------------.
    +| yyparse or yypushparse.  |
    +`-------------------------*/
    +
    +b4_push_if([
    +b4_c_function_def([yypushparse], [int], [[struct yypvars *yypvars], 
[yypvars]], 
    +                  [[int yynchar], [yynchar]], [[YYSTYPE *yynlval], 
[yynlval]]
    +             b4_locations_if([,[[YYLTYPE *yynlloc], [yynlloc]]]))],[
     #ifdef YYPARSE_PARAM
     b4_c_function_def([yyparse], [int], [[void *YYPARSE_PARAM], 
[YYPARSE_PARAM]])
     #else /* ! YYPARSE_PARAM */
     b4_c_function_def([yyparse], [int], b4_parse_param)
    -#endif
    +#endif])

Declare the main function to be yypushparse or yyparse depending on
if %push-parser is specified.

     {[
       ]b4_pure_if([b4_declare_parser_variables])[
    +  ]b4_push_if([b4_declare_parser_variables])[
    +  ]b4_push_if([struct yypvars *pv;])[

Declare the parser variables for push just like pure. Also, add the 
handle to the yypvars structure. I'm not sure why I did this in two
different b4_push_if macros.

    @@ -1009,6 +1121,7 @@
     #if YYERROR_VERBOSE
       /* Buffer for error messages, and its allocated size.  */
       char yymsgbuf[128];
    +  char *yymsgbuf_ptr = yymsgbuf;
       char *yymsg = yymsgbuf;
       YYSIZE_T yymsg_alloc = sizeof yymsgbuf;
     #endif

yymsgbuf_ptr is added. This is probably the first confusing difference
between the 2 patches. You will see this solution used in at least 2 
other places. Essentially, yacc.c was using yymsgbuf in yyparse. So,
the yypvars structure also has a 'char yymsgbuf[128];'. However, when
the pull parse is being used, it wants yymsgbuf to refer to the local 
stack variable, and when the push parser is being used, it wants 
yymsgbuf to refer to the variable in the yypvars structure. I couldn't 
'copy' the array's like I did the rest of the data elements on the 
stack in yyparse, because copying arrays isn't legal. So, I created 
an extra pointer variable, and essentially used that, instead of using 
yymsgbuf directly. Now I can copy the pointer instead.  Besides, even
if I could copy  the entire array, it would be a waste of CPU cycles.

One other note, even though the 'char yymsgbuf[128];' isn't needed in
push mode, it is still declared on the stack. I suppose I could clean
that up... if you'd like.

     
    @@ -1023,6 +1136,7 @@
     
       /* The state stack.  */
       yytype_int16 yyssa[YYINITDEPTH];
    +  yytype_int16 *yyssa_ptr = yyssa;
       yytype_int16 *yyss = yyssa;
       yytype_int16 *yyssp;

Same idea as above here.
 
    @@ -1037,7 +1151,9 @@
       YYLTYPE *yyls = yylsa;
       YYLTYPE *yylsp;
       /* The locations where the error started and ended.  */
    -  YYLTYPE yyerror_range[2];]])[
    +  YYLTYPE yyerror_range[2];
    +  YYLTYPE *yyerror_range_ptr = yyerror_range;
    +  ]])[

Again, same idea.
 
    @@ -1056,8 +1172,13 @@
     
       yystate = 0;
       yyerrstatus = 0;
    -  yynerrs = 0;
    -  yychar = YYEMPTY;                /* Cause a token to be read.  */
    +]b4_push_if([  yychar = yynchar;
    +  pv = yypvars;
    +  if (yynlval)
    +    yylval = *yynlval;
    +]b4_locations_if([  if (yynlloc)
    +     yylloc = *yynlloc;])[],[yynerrs = 0;
    +  yychar = YYEMPTY; /* Cause a token to be read.  */])[

Assign the parameters in push mode to the local variables, otherwise, 
do what was done before.
 
    @@ -1067,11 +1188,12 @@
       yyssp = yyss;
       yyvsp = yyvs;
     ]b4_locations_if([[  yylsp = yyls;
    +]b4_push_if([],[
     #if YYLTYPE_IS_TRIVIAL
       /* Initialize the default location before parsing starts.  */
       yylloc.first_line   = yylloc.last_line   = ]b4_location_initial_line[;
       yylloc.first_column = yylloc.last_column = ]b4_location_initial_column[;
    -#endif
    +#endif])[

No need to do this in push mode, it's done in yypvarsinit.
    @@ -1084,7 +1206,41 @@
     ]])dnl
     m4_ifdef([b4_at_dollar_used], [[  yylsp[0] = yylloc;
     ]])dnl
    -[  goto yysetstate;
    +[  ]b4_push_if([
    +   /* Initialize the locals to the current context. */
    +   yystate = pv->yystate;
    +   yyn = pv->yyn;
    +   yyresult = pv->yyresult;
    +   yyerrstatus = pv->yyerrstatus;
    +   yytoken = pv->yytoken;
    +#if YYERROR_VERBOSE
    +   yymsgbuf_ptr = pv->yymsgbuf_ptr;
    +   yymsg = pv->yymsg;;
    +   yymsg_alloc = pv->yymsg_alloc;
    +#endif
    +   yyssa_ptr = pv->yyssa_ptr;
    +   yyss = pv->yyss;
    +   yyssp = pv->yyssp;
    +
    +   yyvs = pv->yyvs;
    +   yyvsp = pv->yyvsp;
    +
    +   ]b4_locations_if([[  /* The location stack.  */
    +   yyls = pv->yyls;
    +   yylsp = pv->yylsp;
    +
    +   yyerror_range_ptr = pv->yyerror_range_ptr;]])[
    +
    +   yystacksize = pv->yystacksize;
    +   yylen = pv->yylen;
    +   yyval = pv->yyval;
    +   ]b4_locations_if([yyloc = pv->yyloc;])[
    +      if (pv->yynew == 0)
    +      {
    +   goto gottoken;
    +      }
    +      pv->yynew= 0;])[
    +  goto yysetstate;

Ok, this copies all of the data in the push parser context onto the 
varaibles on the stack. At the end, if the context is new, it goes
and reads a token, and marks that the context is no longer new.
 
     /*------------------------------------------------------------.
     | yynewstate -- Push a new state, which is found in yystate.  |
    @@ -1145,7 +1301,7 @@
            YYSTACK_RELOCATE (yyvs);
     ]b4_locations_if([ YYSTACK_RELOCATE (yyls);])[
     #  undef YYSTACK_RELOCATE
    -   if (yyss1 != yyssa)
    +   if (yyss1 != yyssa_ptr)
              YYSTACK_FREE (yyss1);
           }
     # endif

Use new pointer variable.

    @@ -1187,8 +1343,41 @@
       /* YYCHAR is either YYEMPTY or YYEOF or a valid lookahead symbol.  */
       if (yychar == YYEMPTY)
         {
    +      ]b4_push_if([
    +   YYDPRINTF ((stderr, "Return for a new token:\n"));
    +   yyresult = YYPUSH_MORE;
    +   /* Initialize the locals to the current context. */
    +   pv->yystate = yystate;
    +   pv->yyn = yyn;
    +   pv->yyresult = yyresult;
    +   pv->yyerrstatus = yyerrstatus;
    +   pv->yytoken = yytoken;
    +#if YYERROR_VERBOSE
    +   pv->yymsgbuf_ptr = yymsgbuf_ptr;
    +   pv->yymsg = yymsg;;
    +   pv->yymsg_alloc = yymsg_alloc;
    +#endif
    +   pv->yyssa_ptr = yyssa_ptr;
    +   pv->yyss = yyss;
    +   pv->yyssp = yyssp;
    +
    +   pv->yyvs = yyvs;
    +   pv->yyvsp = yyvsp;
    +
    +   ]b4_locations_if([[  /* The location stack.  */
    +   pv->yyls = yyls;
    +   pv->yylsp = yylsp;
    +   pv->yyerror_range_ptr = yyerror_range_ptr;]])[
    +
    +   pv->yystacksize = yystacksize;
    +   pv->yylen = yylen;
    +   pv->yyval = yyval;
    +   ]b4_locations_if([pv->yyloc = yyloc;])[
    +   return yyresult;
    +gottoken:
    +   YYDPRINTF((stderr, "Reading a token: "));],[
           YYDPRINTF ((stderr, "Reading a token: "));
    -      yychar = YYLEX;
    +   yychar = YYLEX;])[
         }

Copies all the data on the stack into the push parser before returning
out of yypushparse.
 
    @@ -1300,7 +1489,7 @@
       /* If not already recovering from an error, report this error.  */
       if (!yyerrstatus)
         {
    -      ++yynerrs;
    +]b4_push_if([],[ ++yynerrs;])[
     #if ! YYERROR_VERBOSE
           yyerror (]b4_yyerror_args[YY_("syntax error"));
     #else

Only update yynerrs in non push mode. If you want me to leave yynerrs in
in push mode, this can go back in too.

    @@ -1311,14 +1500,14 @@
                YYSIZE_T yyalloc = 2 * yysize;
                if (! (yysize <= yyalloc && yyalloc <= YYSTACK_ALLOC_MAXIMUM))
                  yyalloc = YYSTACK_ALLOC_MAXIMUM;
    -       if (yymsg != yymsgbuf)
    +       if (yymsg != yymsgbuf_ptr)
                  YYSTACK_FREE (yymsg);
                yymsg = (char *) YYSTACK_ALLOC (yyalloc);
                if (yymsg)
                  yymsg_alloc = yyalloc;
                else
                  {
    -           yymsg = yymsgbuf;
    +           yymsg = yymsgbuf_ptr;
                    yymsg_alloc = sizeof yymsgbuf;
                  }
              }

Use new pointer variables.
    @@ -1471,18 +1660,18 @@
           YYPOPSTACK (1);
         }
     #ifndef yyoverflow
    -  if (yyss != yyssa)
    +  if (yyss != yyssa_ptr)
         YYSTACK_FREE (yyss);
     #endif
     #if YYERROR_VERBOSE
    -  if (yymsg != yymsgbuf)
    +  if (yymsg != yymsgbuf_ptr)
         YYSTACK_FREE (yymsg);
     #endif

Use new pointer variables.
    +  ]b4_push_if([pv->yyresult = YYID (yyresult);])[
       /* Make sure YYID is used.  */
       return YYID (yyresult);
     ]}

Before returning from the pushparser, copy the result into the push
parser context.
 
    @@ -1525,6 +1714,8 @@
     # define YYLTYPE_IS_TRIVIAL 1
     #endif
     
    +]b4_push_if([struct ]b4_prefix[pvars;
    +enum { YYPUSH_MORE = 4 };])[

Some extra declaratoins.