How to solve Bison optional else expression shift/reduce error?

Question

I'm trying to implement a toy language with grammar inspired by Scala. I used part of the Scala Syntax Specification:

Expr1 : ‘if’ ‘(’ Expr ‘)’ {nl} Expr [[semi] ‘else’ Expr]
      | ...

In this toy language, everything is an expression (if-else, for, while has a return value), and seperated by ; or \n.

Here's the parser.y:

%code top {
#include <cstdio>
}

%union {
    int n;
    Ast *ast;
}

%code requires {
class Ast;
int yylex(void);
void yyerror(const char *msg);
}

%token<n> NUM 
%token<n> PLUS '+'
%token<n> MINUS '-'
%token<n> TIMES '*'
%token<n> DIVIDE '/'
%token<n> SEMICOLON ';'
%token<n> NEWLINE '\n'
%token<n> IF "if"
%token<n> ELSE "else"
%token<n> LPAREN '('
%token<n> RPAREN ')'

%type<ast> prog expr primaryExpr optionalElse semi optionalSemi optionalNewlines newlines

%left PLUS MINUS
%left TIMES DIVIDE

%start prog

%%

prog : expr
     ;

expr : "if" '(' primaryExpr ')' optionalNewlines expr optionalElse { $$ = nullptr; }
     | primaryExpr
     ;

optionalElse : optionalSemi "else" expr { $$ = nullptr; }
             | %empty { $$ = nullptr; }
             ;

primaryExpr : NUM { $$ = nullptr; }
            | primaryExpr '+' NUM { $$ = nullptr; }
            | primaryExpr '-' NUM { $$ = nullptr; }
            | primaryExpr '*' NUM { $$ = nullptr; }
            | primaryExpr '/' NUM { $$ = nullptr; }
            ;

semi : ';' { $$ = nullptr; }
     | '\n' { $$ = nullptr; }
     ;

optionalSemi : semi { $$ = nullptr; }
             | %empty { $$ = nullptr; }
             ;

optionalNewlines : newlines { $$ = nullptr; }
                 | %empty { $$ = nullptr; }
                 ;

newlines : '\n' { $$ = nullptr; }
         | newlines '\n' { $$ = nullptr; }
         ;


%%

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

This is my grammar compiled with: bison --debug --verbose -Wcounterexamples -o grammar.tab.cpp --defines=grammar.tab.h grammar.y

It gives me output:

Terminals unused in grammar

    PLUS
    MINUS
    TIMES
    DIVIDE
    SEMICOLON
    NEWLINE
    LPAREN
    RPAREN


Rules useless in parser due to conflicts

   14 optionalSemi: %empty


State 21 conflicts: 2 shift/reduce, 1 reduce/reduce


Grammar

    0 $accept: prog $end

    1 prog: expr

    2 expr: "if" '(' primaryExpr ')' optionalNewlines expr optionalElse
    3     | primaryExpr

    4 optionalElse: optionalSemi "else" expr
    5             | %empty

    6 primaryExpr: NUM
    7            | primaryExpr '+' NUM
    8            | primaryExpr '-' NUM
    9            | primaryExpr '*' NUM
   10            | primaryExpr '/' NUM

   11 semi: ';'
   12     | '\n'

   13 optionalSemi: semi
   14             | %empty

   15 optionalNewlines: newlines
   16                 | %empty

   17 newlines: '\n'
   18         | newlines '\n'


Terminals, with rules where they appear

    $end (0) 0
    '\n' <n> (10) 12 17 18
    '(' <n> (40) 2
    ')' <n> (41) 2
    '*' <n> (42) 9
    '+' <n> (43) 7
    '-' <n> (45) 8
    '/' <n> (47) 10
    ';' <n> (59) 11
    error (256)
    NUM <n> (258) 6 7 8 9 10
    PLUS <n> (259)
    MINUS <n> (260)
    TIMES <n> (261)
    DIVIDE <n> (262)
    SEMICOLON <n> (263)
    NEWLINE <n> (264)
    "if" <n> (265) 2
    "else" <n> (266) 4
    LPAREN <n> (267)
    RPAREN <n> (268)


Nonterminals, with rules where they appear

    $accept (22)
        on left: 0
    prog <ast> (23)
        on left: 1
        on right: 0
    expr <ast> (24)
        on left: 2 3
        on right: 1 2 4
    optionalElse <ast> (25)
        on left: 4 5
        on right: 2
    primaryExpr <ast> (26)
        on left: 6 7 8 9 10
        on right: 2 3 7 8 9 10
    semi <ast> (27)
        on left: 11 12
        on right: 13
    optionalSemi <ast> (28)
        on left: 13 14
        on right: 4
    optionalNewlines <ast> (29)
        on left: 15 16
        on right: 2
    newlines <ast> (30)
        on left: 17 18
        on right: 15 18


State 0

    0 $accept: • prog $end

    NUM   shift, and go to state 1
    "if"  shift, and go to state 2

    prog         go to state 3
    expr         go to state 4
    primaryExpr  go to state 5


State 1

    6 primaryExpr: NUM •

    $default  reduce using rule 6 (primaryExpr)


State 2

    2 expr: "if" • '(' primaryExpr ')' optionalNewlines expr optionalElse

    '('  shift, and go to state 6


State 3

    0 $accept: prog • $end

    $end  shift, and go to state 7


State 4

    1 prog: expr •

    $default  reduce using rule 1 (prog)


State 5

    3 expr: primaryExpr •
    7 primaryExpr: primaryExpr • '+' NUM
    8            | primaryExpr • '-' NUM
    9            | primaryExpr • '*' NUM
   10            | primaryExpr • '/' NUM

    '+'  shift, and go to state 8
    '-'  shift, and go to state 9
    '*'  shift, and go to state 10
    '/'  shift, and go to state 11

    $default  reduce using rule 3 (expr)


State 6

    2 expr: "if" '(' • primaryExpr ')' optionalNewlines expr optionalElse

    NUM  shift, and go to state 1

    primaryExpr  go to state 12


State 7

    0 $accept: prog $end •

    $default  accept


State 8

    7 primaryExpr: primaryExpr '+' • NUM

    NUM  shift, and go to state 13


State 9

    8 primaryExpr: primaryExpr '-' • NUM

    NUM  shift, and go to state 14


State 10

    9 primaryExpr: primaryExpr '*' • NUM

    NUM  shift, and go to state 15


State 11

   10 primaryExpr: primaryExpr '/' • NUM

    NUM  shift, and go to state 16


State 12

    2 expr: "if" '(' primaryExpr • ')' optionalNewlines expr optionalElse
    7 primaryExpr: primaryExpr • '+' NUM
    8            | primaryExpr • '-' NUM
    9            | primaryExpr • '*' NUM
   10            | primaryExpr • '/' NUM

    '+'  shift, and go to state 8
    '-'  shift, and go to state 9
    '*'  shift, and go to state 10
    '/'  shift, and go to state 11
    ')'  shift, and go to state 17


State 13

    7 primaryExpr: primaryExpr '+' NUM •

    $default  reduce using rule 7 (primaryExpr)


State 14

    8 primaryExpr: primaryExpr '-' NUM •

    $default  reduce using rule 8 (primaryExpr)


State 15

    9 primaryExpr: primaryExpr '*' NUM •

    $default  reduce using rule 9 (primaryExpr)


State 16

   10 primaryExpr: primaryExpr '/' NUM •

    $default  reduce using rule 10 (primaryExpr)


State 17

    2 expr: "if" '(' primaryExpr ')' • optionalNewlines expr optionalElse

    '\n'  shift, and go to state 18

    $default  reduce using rule 16 (optionalNewlines)

    optionalNewlines  go to state 19
    newlines          go to state 20


State 18

   17 newlines: '\n' •

    $default  reduce using rule 17 (newlines)


State 19

    2 expr: "if" '(' primaryExpr ')' optionalNewlines • expr optionalElse

    NUM   shift, and go to state 1
    "if"  shift, and go to state 2

    expr         go to state 21
    primaryExpr  go to state 5


State 20

   15 optionalNewlines: newlines •
   18 newlines: newlines • '\n'

    '\n'  shift, and go to state 22

    $default  reduce using rule 15 (optionalNewlines)


State 21

    2 expr: "if" '(' primaryExpr ')' optionalNewlines expr • optionalElse

    ';'   shift, and go to state 23
    '\n'  shift, and go to state 24

    ';'       [reduce using rule 5 (optionalElse)]
    '\n'      [reduce using rule 5 (optionalElse)]
    "else"    reduce using rule 5 (optionalElse)
    "else"    [reduce using rule 14 (optionalSemi)]
    $default  reduce using rule 5 (optionalElse)

    optionalElse  go to state 25
    semi          go to state 26
    optionalSemi  go to state 27

    shift/reduce conflict on token ';':
        5 optionalElse: • %empty
       11 semi: • ';'
      Example: "if" '(' primaryExpr ')' optionalNewlines "if" '(' primaryExpr ')' optionalNewlines expr • ';' "else" expr
      Shift derivation
        expr
        ↳ "if" '(' primaryExpr ')' optionalNewlines expr                                                                        optionalElse
                                                    ↳ "if" '(' primaryExpr ')' optionalNewlines expr optionalElse               ↳ ε
                                                                                                     ↳ optionalSemi "else" expr
                                                                                                       ↳ semi
                                                                                                         ↳ • ';'
      Reduce derivation
        expr
        ↳ "if" '(' primaryExpr ')' optionalNewlines expr                                                          optionalElse
                                                    ↳ "if" '(' primaryExpr ')' optionalNewlines expr optionalElse ↳ optionalSemi "else" expr
                                                                                                     ↳ •            ↳ semi
                                                                                                                      ↳ ';'

    shift/reduce conflict on token '\n':
        5 optionalElse: • %empty
       12 semi: • '\n'
      Example: "if" '(' primaryExpr ')' optionalNewlines "if" '(' primaryExpr ')' optionalNewlines expr • '\n' "else" expr
      Shift derivation
        expr
        ↳ "if" '(' primaryExpr ')' optionalNewlines expr                                                                        optionalElse
                                                    ↳ "if" '(' primaryExpr ')' optionalNewlines expr optionalElse               ↳ ε
                                                                                                     ↳ optionalSemi "else" expr
                                                                                                       ↳ semi
                                                                                                         ↳ • '\n'
      Reduce derivation
        expr
        ↳ "if" '(' primaryExpr ')' optionalNewlines expr                                                          optionalElse
                                                    ↳ "if" '(' primaryExpr ')' optionalNewlines expr optionalElse ↳ optionalSemi "else" expr
                                                                                                     ↳ •            ↳ semi
                                                                                                                      ↳ '\n'

    reduce/reduce conflict on token "else":
        5 optionalElse: • %empty
       14 optionalSemi: • %empty
      Example: •
      First reduce derivation
        optionalElse
        ↳ •
      Second reduce derivation
        optionalSemi
        ↳ •



State 22

   18 newlines: newlines '\n' •

    $default  reduce using rule 18 (newlines)


State 23

   11 semi: ';' •

    $default  reduce using rule 11 (semi)


State 24

   12 semi: '\n' •

    $default  reduce using rule 12 (semi)


State 25

    2 expr: "if" '(' primaryExpr ')' optionalNewlines expr optionalElse •

    $default  reduce using rule 2 (expr)


State 26

   13 optionalSemi: semi •

    $default  reduce using rule 13 (optionalSemi)


State 27

    4 optionalElse: optionalSemi • "else" expr

    "else"  shift, and go to state 28


State 28

    4 optionalElse: optionalSemi "else" • expr

    NUM   shift, and go to state 1
    "if"  shift, and go to state 2

    expr         go to state 29
    primaryExpr  go to state 5


State 29

    4 optionalElse: optionalSemi "else" expr •

    $default  reduce using rule 4 (optionalElse)

How should I fix the State 21 conflicts: 2 shift/reduce, 1 reduce/reduce?

linrongbin · Answer 1 · 2020-08-24T08:41:38.480

For now I use a tricky way to fix this if-else shift/reduce error.

The idea is come from two answers:

https://stackoverflow.com/a/12734499/4438921 - use %prec to fix if-else shift/reduce error.
https://stackoverflow.com/a/63000285/4438921 - merge 2 tokens into single one to simplify bison grammar.

Firstly, add a token SEMICOLON_ELSE in flex token.l:

%option noyywrap
%option bison-bridge

%{
#include "parser.tab.hh"
%}

%%

[\n]+ { return NEWLINE; }
";"   { return SEMICOLON; }
"else"{ return ELSE; }
[\n]+[^ \t\v\f\r]*"else" { return SEMICOLON_ELSE; }
";"[^ \t\v\f\r]*"else"   { return SEMICOLON_ELSE; }

%%

Suppose there's no comment between ;/\n and else. Make them one single token.

You could use more complicated regex to allow comments between them.

Then in bison parser.y:

%token<n> SEMICOLON_ELSE "semicolon_else"
%token<n> ELSE "else"

%nonassoc "then"
%nonassoc "else"
%nonassoc "semicolon_else"

%%
expr : "if" '(' primaryExpr ')' optionalNewlines expr %prec "then" { $$ = nullptr; }
     | "if" '(' primaryExpr ')' optionalNewlines expr "semicolon_else" expr %prec "semicolon_else" { $$ = nullptr; }
     | "if" '(' primaryExpr ')' optionalNewlines expr "else" expr %prec "else" { $$ = nullptr; }
     | primaryExpr
     ;
%%

In this case, %prec will work for parser!!!

How to solve Bison optional else expression shift/reduce error?

1 Answers1