Re: [RFA] GLR parsing

[Paul Hilfinger]

Thanks for all the comments.  A few responses:

 > | +and like this for GLR parsers:
 > | +
 > | address@hidden
 > | address@hidden
 > | +#define YYLLOC_DEFAULT(Current, Rhs, 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;
 > | address@hidden group
 > | address@hidden example
 > 
 > We should to unify this.  We still have some freedom on locations, and
 > we probably want to escape from macros, and use some new %directives
 > instead.

Sounds fine to me.  But I think I'd better put this off until your "we
probably want [something like X] ..." changes to "we will do X".


 > | ....  However, Bison currently
 > | +uses a simpler data structure that requires time proportional to the
 > | +length of the input times the maximum number of stacks required for any
 > | +prefix of the input.  Thus, really ambiguous or non-deterministic
 > | +grammars can require exponential time and space to process.   ...
 > 
 > Hm, I thought you were using one such structure.  I guess you're
 > saying the stacks are not maximally shared, right?

Correct.  Apparently, at least some other GLR implementors do the
same.  I figured that, at least for this initial implementation, it
was going to be hard enough getting things working without worrying
about additional trickiness that was not terribly important in
practice. I was also somewhat worried (perhaps unnecessarily) about
the interactions of this sharing and the calculation of semantic
values.  This was because I sort of had this idea that at some point,
I'd like to introduce semantic actions that are always executed
immediately upon reduction, even when in GLR mode.  They might be used
for particularly simple cases (for efficiency) or where semantic
actions somehow had to affect parsing or lexing.  

Besides, you sounded so disappointed at being deprived of the fun of
doing GLR from scratch, that I thought it would be nice to leave you
a project (:->).

 > | +  if (glr_parser)
 > | +    conflict_tos[state] = sp3 = XCALLOC (unsigned int, count);  
 > | +  else 
 > | +    conflict_tos[state] = NULL;
 > 
 > Hm, don't we want something more ``typed''?  These are state_number_t,
 > right?  Even if it's only typedef'd to unsigned int, reading
 > state_number_t makes it much easier to follow.

Well, yes, "we" do, but this is pervasive problem in this part of the
code, is it not?  Perhaps a general "typing sweep" is called for?

 > | +void
 > | +merger_output (FILE *out)
 > | +{
 > | +  int n;
 > | +  merger_list* p;
 > | +
...
 > | +}
 > 
 > Maybe we can move this out from bison, and have M4 do?

I guess I don't entirely understand.  This function is modeled on 
actions_output. 

I have incorporated your other comments, and will check in soon.

Paul