Beaver parser generator shift-reduce conflicts connected to dangling else

204 Views Asked by At

I am feeding a (generated) grammar to Beaver parser generator. Multiple shift-reduce conflicts are caused by it seems like the dangling else problem in this rules:

Condition
    = IF LPAR Expression.expression RPAR Statement.trueStatement OptionalStatement_1.elem2  
    ;
OptionalStatement_1
    = ELSE StatementArray3.falseStatement   
    |   
    ;

I thought the dangling else will not be a problem, because the tool selects SHIFT by default, which is an accepted soluion to the dangling else problem AFAIK. However, there is some problem, as I have 16 other warnings, and I don't understand why:

grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (ELSE: SHIFT; goto 93) over (ELSE: REDUCE OptionalStatement_1 = ) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (LBR: SHIFT; goto 5) over (LBR: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (IF: SHIFT; goto 18) over (IF: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (RETURN: SHIFT; goto 95) over (RETURN: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (DO: SHIFT; goto 100) over (DO: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (READ: SHIFT; goto 107) over (READ: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (WRITE: SHIFT; goto 110) over (WRITE: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (SEMICOLON: SHIFT; goto 113) over (SEMICOLON: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (WHILE: SHIFT; goto 114) over (WHILE: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (LPAR: SHIFT; goto 63) over (LPAR: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (PLUSPLUS: SHIFT; goto 71) over (PLUSPLUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (PLUS: SHIFT; goto 73) over (PLUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (EXCL: SHIFT; goto 75) over (EXCL: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (MINUS: SHIFT; goto 77) over (MINUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (MINUSMINUS: SHIFT; goto 79) over (MINUSMINUS: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (VALUE: SHIFT; goto 81) over (VALUE: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.
grammar.grammar: Warning: Resolved Shift-Reduce conflict by selecting (IDENT: SHIFT; goto 82) over (IDENT: REDUCE OptionalStatement_1 = ELSE StatementArray3.falseStatement) using precedence.

The result is that in the StatementArray3 there's rubbish injected into the else branch (completely wrong type, a List instead of Optional, filled with gobbled up stuff from the following statements). Can someone explain me please what are all these shift-reduce conflicts caused by (except the obvious first one)? Mind, the grammar is generated from a class model, so very specific solutions to this problem are not the best, I would need to solve these kind of problems generally, or change the grammar.


The previous grammar (that I want to avoid) which was generated by another method yields this grammar:

Condition
    = IF LPAR Expression.expression RPAR Statement.trueStatement    
    | IF LPAR Expression.expression RPAR Statement.trueStatement ELSE Statement.falseStatement  
    ;

Which goes without conflicts during compilation, however for the following input:

{
  if(b == 21)
    c = 10;
  else
    c = 15;
}

the parser fails at runtime, just skipping the else and treating the second assignment as top-level:

4,4-4,7: Syntax Error: unexpected token "else"
4,4-4,7: Recovered: removed unexpected token "else"

The full problematic grammar (stripped of %import, %typeof and {: ... :}):

%terminals PERC, ASSIGNDIV, LT, RPAR, VALUE, DO, ASSIGN, PLUSPLUS, QUESTION, MINUS, WRITE, RETURN, LPAR, SEMICOLON, ASSIGNADD, ELSE, LBR, IF, COMMA, RBR, OR, SLASH, MINUSMINUS, COLON, EQ, GT, READ, ASSIGNMUL, STAR, IDENT, ASSIGNSUB, ASSIGNMOD, AND, GTE, WHILE, NEQ, EXCL, LTE, PLUS;

%left LPAR, RPAR;
%nonassoc PLUSPLUS, MINUSMINUS;
%left PREC_13_1, EXCL, PREC_13_2;
%left PERC, SLASH, STAR;
%left PLUS, MINUS;
%left LT, LTE, GT, GTE;
%left NEQ, EQ;
%left AND;
%left OR;
%left QUESTION, COLON;
%right ASSIGN, ASSIGNADD, ASSIGNMUL, ASSIGNDIV, ASSIGNSUB, ASSIGNMOD;


%goal Program;

Number
    = VALUE.value   
    ;

Program
    = FunctionArray1.functions Block.main   
    ;

UnaryOperation
    = PLUSPLUS Expression.expression    
    | PLUS Expression.expression @ PREC_13_1    
    | EXCL Expression.expression    
    | MINUS Expression.expression @ PREC_13_2   
    | MINUSMINUS Expression.expression  
    ;

Block
    = LBR StatementArray3.statements RBR    
    ;

BinaryOperation
    = Expression.expression1 NEQ Expression.expression2 
    | Expression.expression1 OR Expression.expression2  
    | Expression.expression1 PERC Expression.expression2    
    | Expression.expression1 EQ Expression.expression2  
    | Expression.expression1 PLUS Expression.expression2    
    | Expression.expression1 LT Expression.expression2  
    | Expression.expression1 MINUS Expression.expression2   
    | Expression.expression1 LTE Expression.expression2 
    | Expression.expression1 SLASH Expression.expression2   
    | Expression.expression1 GT Expression.expression2  
    | Expression.expression1 ASSIGN Expression.expression2  
    | Expression.expression1 STAR Expression.expression2    
    | AssignmentGeneric.val 
    | Expression.expression1 GTE Expression.expression2 
    | Expression.expression1 AND Expression.expression2 
    ;

Expression
    = LPAR Expression.val RPAR  
    | Expression.expression1 QUESTION Expression.expression2 COLON Expression.expression3   
    | UnaryOperation.val    
    | Number.val    
    | Variable.val  
    | FunctionCall.val  
    | BinaryOperation.val   
    ;

ParameterArray2
    = ParameterArray2.list COMMA Parameter.elem 
    |   
    | Parameter.elem    
    ;

Statement
    = Block.val 
    | Condition.val 
    | ReturnFunction.val    
    | ExpressionStatement.val   
    | DoWhile.val   
    | Read.val  
    | Write.val 
    | EmptyStatement.val    
    | WhileStatement.val    
    ;

Parameter
    = IDENT.ident   
    ;

Write
    = WRITE Expression.expression SEMICOLON 
    ;

OptionalStatement_1
    = ELSE StatementArray3.falseStatement   
    |   
    ;

FunctionArray1
    = FunctionArray1.list Function.elem 
    |   
    ;

WhileStatement
    = WHILE LPAR Expression.expression RPAR Statement.statement 
    ;

ExpressionArray4
    = ExpressionArray4.list COMMA Expression.elem   
    |   
    | Expression.elem   
    ;

ExpressionStatement
    = Expression.expression SEMICOLON   
    ;

Variable
    = IDENT.ident   
    ;

EmptyStatement
    = SEMICOLON 
    ;

Read
    = READ IDENT.ident SEMICOLON    
    ;

FunctionCall
    = IDENT.ident LPAR ExpressionArray4.expressions RPAR    
    ;

Condition
    = IF LPAR Expression.expression RPAR Statement.trueStatement OptionalStatement_1.elem2  
    ;

DoWhile
    = DO Statement.statement WHILE LPAR Expression.expression RPAR SEMICOLON    
    ;

Function
    = IDENT.ident LPAR ParameterArray2.parameters RPAR Block.body   
    ;

ReturnFunction
    = RETURN Expression.expression SEMICOLON    
    ;

StatementArray3
    = StatementArray3.list Statement.elem   
    |   
    ;

AssignmentGeneric
    = Expression.expression1 ASSIGNADD Expression.expression2   
    | Expression.expression1 ASSIGNMUL Expression.expression2   
    | Expression.expression1 ASSIGNDIV Expression.expression2   
    | Expression.expression1 ASSIGNSUB Expression.expression2   
    | Expression.expression1 ASSIGNMOD Expression.expression2   
    ;
1

There are 1 best solutions below

0
On

There is a problem in the grammar generation. It should have been

OptionalStatement_1
    = ELSE Statement.falseStatement   
    |   
    ;

not StatementArray3.falseStatement


after correctly generating the ELSE Statement.falseStatement alternative, only a single shift-reduce conflict arises and I can rely on the default SHIFT action.