Re: Grammar failing single lookahead

[Tim Van Holder]

Frans Englich wrote:
> The intent of the grammar is to enforce that declarations appear in a certain 
> order(FirstProlog, SecondProlog), that the declarations are optional, and 
> they take the form of "declare <statically known keyword>".
> 
> This is something that naturally leads to a shift/reduce conflict. As far as 
> I 
> know, this can be solved in two ways:
> 
> * Tokenize "declare foo" into one token, instead of two(the conflict goes 
> away).
> * Generate a GLR parser. The conflict stays, but the parser survives it.
> 
> For the user, I think the latter is a better alternative since it will yield 
> better error reporting(since the token granularity is higher).
> 
> But is it solvable in some other way? For instance, can the grammar be 
> rewritten in some way such that it can be parsed as LR(1)? I doubt it.

Try moving semantic checks like this out of the actual grammar
definition; often conflicts like this can be avoided by doing so.
Simply allow a sequence of any type of declaration, and do the
are-they-in-an-acceptable-order check on the AST. You could do this in
actions during the parse, or as part of a dedicated semantic check phase
on the full AST once it's constructed by yyparse().
You only need a GLR parser when it's not an error condition, i.e. if
DECLARE A should be parsed differently if it's after DECLARE B.

So instead of:

foo
: mul_declare_a mul_declare_b rest_of_program
;

mul_declare_a
:
| mul_declare_a declare_a
;

mul_declare_b
:
| mul_declare_b declare_b
;

declare_a
: DECLARE A rest_of_a_decl
;

declare_b
: DECLARE B rest_of_b_decl
;

You could simply have:

foo
: mul_declaration rest_of_program
  {
    // Alernative 1 - validate list in its entirety
    if (!validate_declaration_order($1))
      YYABORT;
  }
;

mul_declaration
:
| mul_declaration declaration
  {
    // Alternative 2 - check when adding to the list
    if ($1 != 0 && !validate_declaration_order($1->last_one, $2))
      YYABORT;
  }
;

declaration
: DECLARE A rest_of_a_decl
| DECLARE B rest_of_b_decl
;

(note about my rule naming: I use plus_ and mul_ prefixes to indicate
the equivalents of + and * regex operators)