Trying to solve dangling else for a Mini-C grammar

Question

I have this grammar:

translation_unit 
    ::= external_declaration
    | translation_unit external_declaration

external_declaration 
    ::= function_definition
    | declaration

function_definition 
    ::= type_specifier declarator compound_statement
    | STATIC type_specifier declarator compound_statement

declaration 
    ::= type_specifier declarator ';'
    | EXTERN type_specifier declarator ';'

declaration_list_opt 
    ::= declaration_list
    | empty
    
declaration_list
    ::= declaration_list declaration
    | declaration

type_specifier 
    ::= INT
    | CHAR

declarator 
    ::= direct_declarator
    | ASTERISK declarator

direct_declarator 
    ::= ID
    | direct_declarator '(' parameter_type_list ')'
    | direct_declarator '(' ')'

parameter_type_list 
    ::= parameter_list ',' ELLIPSIS
    | parameter_list

parameter_list 
    ::= parameter_list ',' parameter_declaration
    | parameter_declaration

parameter_declaration 
    ::= type_specifier declarator

compound_statement 
    ::= '{' declaration_list_opt statement_list '}'
    | '{' declaration_list_opt '}'

expression_statement 
    ::= expression ';'

expression 
    ::= equality_expression

expression 
    ::= equality_expression '=' expression
    | equality_expression '+=' expression
    | equality_expression '-=' expression
    | equality_expression '*=' expression
    | equality_expression '/=' expression
    | equality_expression '%=' expression

equality_expression 
    ::= relational_expression

equality_expression 
    ::= equality_expression '==' relational_expression
    | equality_expression '!=' relational_expression

relational_expression 
    ::= additive_expression

relational_expression 
    ::= relational_expression '<'  additive_expression
    | relational_expression '>'  additive_expression
    | relational_expression '<=' additive_expression
    | relational_expression '>=' additive_expression

postfix_expression 
    ::= primary_expression
    | postfix_expression '(' argument_expression_list ')'
    | postfix_expression '(' ')'
    | postfix_expression '[' expression ']'


argument_expression_list 
    ::= argument_expression_list ',' expression
    | expression

unary_expression 
    ::= postfix_expression
    | '-' unary_expression
    | '+' unary_expression
    | '!' unary_expression
    | '*' unary_expression
    | '&' unary_expression

mult_expression 
    ::= unary_expression

mult_expression 
    ::= mult_expression '*' unary_expression
    | mult_expression '/' unary_expression
    | mult_expression '%' unary_expression

additive_expression 
    ::= mult_expression
    | additive_expression '+' mult_expression
    | additive_expression '-' mult_expression

primary_expression 
    ::= ID
    | INUMBER
    | FNUMBER
    | CHARACTER
    | string_literal
    | '(' expression ')'
    
string_literal 
    ::= string_literal STRING
    | STRING

statement 
    ::= compound_statement
    | expression_statement
    | selection_statement
    | iteration_statement
    | jump_statement

jump_statement 
    ::= RETURN ';'
    | RETURN expression ';'
    | BREAK ';'
    | CONTINUE ';'

iteration_statement 
    ::= WHILE '(' expression ')' statement
    | FOR '(' expression_statement expression_statement expression ')' statement

selection_statement 
    ::= IF '(' expression ')' statement
    | IF '(' expression ')' statement ELSE statement
    
statement_list 
    ::= statement_list statement
    | statement

When i implememented a parser using Sly it says that selection_statement has a shift reduce conflict.

I am trying to solve it without using precedence.

I tried using something like this:

@_("matched",
   "unmatched")
   def selection_statement(self, p):
      pass
    
@_("IF '(' expression ')' matched ELSE matched")
   def matched(self, p):
      pass

@_("IF '(' expression ')' matched",
   "IF '(' expression ')' unmatched",
   "IF '(' expression ')' matched ELSE unmatched")
   def unmatched(self, p):
      pass

But it has an infinite recursion on matched.

I tried adding other statements on matched to solve the recursion but it only generates more conflicts.

What should i use to elimiante the recursion?

Answer 1

I found the answer. I just had to modify my grammar to look like this:

statement 
    ::= matched
    | unmatched

matched 
    ::= if_matched
    | iteration_statement_matched
    | compound_statement
    | expression_statement
    | jump_statement

unmatched
    ::= if_unmatched
    | iteration_statement_unmatched

if_matched 
    ::= IF '(' expression ')' matched ELSE matched

if_unmatched 
    ::= IF '(' expression ')' statement
    | IF '(' expression ')' matched ELSE unmatched

iteration_statement_matched 
    ::= WHILE '(' expression ')' matched

iteration_statement_matched 
    ::= FOR '(' expression_statement expression_statement expression ')' matched

iteration_statement_unmatched 
    ::= WHILE '(' expression ')' unmatched

iteration_statement_unmatched 
    ::= FOR '(' expression_statement expression_statement expression ')' unmatched

I used this post as reference: Shift/reduce conflict in java cup - dangling else issue