Search code examples
bisonlr-grammarshift-reduce-conflictjison

How to solve this S/R conflict

Here's a simplification of my working EBNF grammar:

%token NEWLINE BLOCK_MARK A
%start file

file: block+ NEWLINE*;
block: BLOCK_MARK line;
line: A+;

Both \n and EOF spit out NEWLINE as a token (so that a single ending NEWLINE isn't required before EOF). It works with a stream like this:

BLOCK_MARK A A BLOCK_MARK A NEWLINE[actually EOF]

Now I want to have several line in a block, at least one being mandatory and the rest separated with NEWLINE. E.g.:

BLOCK_MARK A A NEWLINE A A BLOCK_MARK A A A EOF

I tried doing this:

file: block+ NEWLINE*;
block: BLOCK_MARK line moreline*;
line: A+;
moreline: NEWLINE line;

But Jison complains about a S/R conflict when lookahead is NEWLINE. I guess the state machine is confused deciding if the NEWLINE is part of a new block line or the final NEWLINE* in file (which is needed because the file can end with NEWLINE/EOF).

How can I fix this?

Solution

  • What you want is to make the newlines PART of the preceeding line, deferring a reduction of anything other than a line until after you see the newline. So you end up with:

    file: block+ ;
block: BLOCK_MARK line_nl+ line_nonl? | BLOCK_MARK line_nonl ;
line_nl: line NEWLINE ;
line_nonl: line ;
line: A+ ;

    Now the only problem with the above is that it doesn't allow for any blank lines (a blank line will be a syntax error). But that's the same as your original grammar.