Re: push parser

[Joel E. Denny]

On Fri, 15 Dec 2006, Joel E. Denny wrote:

> 3. Why don't we "Initialize the default location before parsing starts" 
> for push parsers?  Also, %initial-action does not play well with the 
> location passed to yypush_parse.  If @$ is set in %initial-action, @$ 
> overwrites the location of every token.  %initial-action ought to be 
> performed only the first time yypush_parse is called and each time the 
> parse starts over; that would be consistent with how it works for yyparse.  
> Moreover, the location passed to yypush_parse ought to be assigned to 
> yylloc only when it's time to read a token (where YYLEX is invoked).  
> Otherwise, @$ in %initial-action and it clobber each other.  I'm guessing 
> $$ has the same problem and solution.  I haven't fixed any of this.

Attached is a rather large patch that I believe fixes all the above... and 
does a lot more.  I have not yet committed it.

Here's a short description of this patch:

For push mode, I've defined a yyparse that effectively wraps yypush_parse.  
Push parsers can now be either pure (you must declare %pure-parser) or 
impure.  Now, if you trick the test suite into using push.c and 
effectively declaring %push-parser wherever it currently uses yacc.c, the 
entire test suite still passes make maintainer-check... except for some 
push-specific debugging output.

Here's a long description of this patch:

1. Don't read the push.c section of this patch.  It should be much more 
informative to apply the patch and then do: diff -u yacc.c push.c

2. yynerrs is back for push parsers.  Yes, I know we don't care, but the 
only effect I see in getting rid of it is more M4 differences between push 
and pull mode.

3. Impure push parsers are now possible, and you must declare %pure-parser 
with %push-parser to get pure push parsers instead.  Yes, I know we don't 
care about impure push parsers, but I have two reasons for supporting 
them:

a. Most importantly, it let's me run the impure pull tests from the test 
suite to make sure push-mode's yyparse works correctly.

b. It helps prove the point that push/pull is an almost completely 
orthogonal dimension from pure/impure.  As well as I can remember, there 
are only two places where these two dimensions actually interact 
noticeably: (1) yynerrs placement and (2) collisions between yylex and the 
first yypush_parse invocation since they both write to the global yychar, 
yylval, and yylloc.  Both places were easy to resolve.  Neither place 
would be relevant if neither yynerrs nor impurity were supported for push 
parsers.

4. Using M4 and #define's (maybe M4 would be better in both places... 
maybe later... maybe not), I've eliminated a lot of repeated code.

5. I've been careful to make repeated calls to yypush_parse ultimately 
behave like yyparse in pull mode.  This solves at least the 
%initial-action problem quoted at the top of this email.

6. Akim wanted there to be a yyparse in push mode.  Bob and Paul have 
noticed that this would create a dependence on yylex even when the user 
isn't interested in using yyparse.  I've defined yyparse as a macro to 
solve this:

  #define yyparse() yypull_parse (NULL, &yylex)

I've defined yypull_parse as the function wrapping yypush_parse.  This 
way, yylex is never referenced unless the user invokes yyparse.  However, 
the user must either define yyparse correctly himself or #include the 
Bison-generated header to get it.  For this reason, I had to make a couple 
of tweaks to a few test cases in the test suite to get them to pass under 
push mode.

The first argument to yypull_parse is a yypstate.  Thus, the user can now 
combine yypush_parse and yypull_parse.  For example, the user can 
yypush_parse a token to select a sub-grammar and then yypull_parse the 
input stream.

Passing NULL for the yypstate argument instructs yypull_parse to construct 
and destroy a yypstate internally.  This allows us to maintain the usual 
prototype of yyparse as Akim wanted... of course, it's actually a #define 
now instead of a function... oh well.

7. The test suite now passes in pull mode.  To see what I mean, do this:

a. Apply this patch and recompile Bison.

b. cp push.c yacc.c

c. In yacc.c, look for this line:

  m4_include(b4_pkgdatadir/[c.m4])

Add this line afterwards:

  m4_define([b4_push_if], [$1])

c. Now look for this line in yacc.c:

   YYDPRINTF ((stderr, "Return for a new token:\n"));

Delete it.

d. Run make maintainer-check.

8. Here are a few issues I have not yet explored:

a. Whether more members can be moved from yypstate to yyparse.

b. For yacc.c, you can invoke yyparse multiple times.  For push.c's push 
mode, I haven't thought this through.  yypush_parse should probably set 
yyps->yynew = 1 whenever it returns with a parse error or success.

c. I'm not sure why yypstate_new needs to set yyresult = -1.

Ok to commit this patch?

push-patch
Description: Text document