Re: TODO update

[Akim Demaille]

|  > I think we are still not understanding each other.  output is
|  > generated *before* the computation of actrow and the like.  It does
|  > *not* use the same computation of `default' as the ``real'' automaton
|  > does.
| 
| Ah, I see.  Well, fine: for whatever reason, the report (-v) output
| is, as far as I can see, almost OK.  Perhaps your concern is caused by:
| 
|  > I'm referring to the fact that, unless I'm mistaken, there is no such
|  > thing as a $default in GLR, so first of all, $default has nothing to
|  > do here.
| 
| On the contrary, $default IS still used in GLR parsers---just never
| for conflicted entries.  

Ah, this is the bit I was missing, thanks!

But then, I still don't understand the stuff below:


|  > | I'm not sure why you say so.  The one potentially confusing thing is
|  > | that the first $ rule (since there is no S/R conflict) is not
|  > | bracketed, even though it is, in fact, treated identically to the 
|  > | other $ rule (which is bracketed).   This is an artifact of bison's
|  > | reporting of the OTHER sense of 'default' reduction---i.e., the
|  > | reduction taken by default when there is a R/R conflict for the
|  > | ordinary LALR(1) parser.
|  > 
|  > I disagree on the reading.  What Bison wrote above is
|  > 
|  >         There are several possible actions on $: r1 and r2.
|  >         r2 is disabled.
|  >         There are several on +: s4, r1, r2.
|  >         r1 and r2 are disabled.
|  > 
|  > *That's* what ``means'' Bison. `[]' means `possible according to the
|  > grammar, but no executed at all because of conflicts', not `because of
|  > $default'.
| 
| Argh; this terminology is confusing.  When I said "the OTHER sense of
| 'default'" I meant exactly what you just wrote---the selection of the
| first of two conflicting rules in the case of R/R conflicts and the
| disabling of the rest---as opposed to "$default"---the rule that is
| executed when there is no entry in the action table for a given 
| State x Token pair.  In other words, bracketed entries don't really
| make sense for GLR parsing, just as you say next:
| 
|  > In the present case, it ought to be
|  > 
|  > state 5
|  > 
|  >     1 exp: exp . '+' exp  [$, '+']
|  >     1    | exp '+' exp .  [$, '+']
|  >     2    | exp . '+' exp  [$, '+']
|  >     2    | exp '+' exp .  [$, '+']
|  > 
|  >     '+'  shift, and go to state 4
|  > 
|  >     $         reduce using rule 1 (exp)
|  >     $         reduce using rule 2 (exp)
|  >     '+'       reduce using rule 1 (exp)
|  >     '+'       reduce using rule 2 (exp)
|  >     $default  reduce using rule 1 (exp)
| 
| Correct.
| 
|  > and I was, in addition, questioning the presence of this $default
|  > guy.  Should it be:
|  > 
|  > state 5
|  > 
|  >     1 exp: exp . '+' exp  [$, '+']
|  >     1    | exp '+' exp .  [$, '+']
|  >     2    | exp . '+' exp  [$, '+']
|  >     2    | exp '+' exp .  [$, '+']
|  > 
|  >     '+'  shift, and go to state 4
|  > 
|  >     $         reduce using rule 1 (exp)
|  >     $         reduce using rule 2 (exp)
|  >     '+'       reduce using rule 1 (exp)
|  >     '+'       reduce using rule 2 (exp)
|  > 
| 
| No.  Your first one is right.  $default reductions are still used by
| the GLR parser (when there is no conflict for a particular table entry).

I fail to see why $default exists here: the two valid lookaheads are $
and + (as denoted by [$, '+'].  So it seems to me that this state has
no default, and ought to trigger an error *now*, now after reduction.

----------------------------------------
%{
#include <stdio.h>
#include <stdlib.h>

const char *input;

int
yyerror (const char *msg)
{
  fprintf (stderr, "%s\n", msg);
  exit (1);
}

int
yylex (void)
{
  static int count = 0;
  return input[count++];
}

%}

%glr-parser
%debug

%%
exp: exp '+' exp
   | exp '+' exp
   | '0'
   ;
%%
int
main (int argc, const char *argv[])
{
  yydebug = !!getenv ("YYDEBUG");
  input = argv[1];
  return yyparse ();
}
----------------------------------------

/tmp % YYDEBUG=1 ./a.out 0+00                                    nostromo Err 1
Read token '0'
Shifted token '0'. Now in state #1
Reduced stack 0 by rule #2. Now in state 2.
Read token '+'
Shifted token '+'. Now in state #4
Read token '0'
Shifted token '0'. Now in state #1
Reduced stack 0 by rule #2. Now in state 5.
Read token '0'
Reduced stack 0 by rule #1. Now in state 2.
parse error

Hm, no, $default is here, indeed.  I'm not sure I understand why :(

It looks like I should think longer about it, thanks!