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?

This is a canonical example of a shift / reduce conflict. For example, it is the one used [in the Bison manual](https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html) for discussing the issue. To implement the C semantics of binding the `else` to the innermost matching `if`, you resolve the conflict by shifting, which is Bison's default for all shift / reduce conflicts. I don't know how to tell Sly to do the same. — John Bollinger, Apr 03 '23 at 15:17
Isn't this really a Python question? The grammar may be C-like, but the coding is in Python and Sly. Also, isn't Sly retired? — Tom Karzes, Apr 03 '23 at 16:29
@TomKarzes: Sly is written (and used) in Python, but that probably doesn't apply to this situation. — Sean Duggan, Apr 03 '23 at 20:07
@JohnBollinger: Sly automatically shifts but it displays a warning. I am trying to remove the warning. — Juan_2054, Apr 03 '23 at 21:21
@Juan_2054: You need to make your grammar unambiguous then. How would you handle a nested if statement with a single else? — Sean Duggan, Apr 03 '23 at 22:01
The Sly documentation isn't bad. It contains [a section on dealing with ambiguities](https://sly.readthedocs.io/en/latest/sly.html#dealing-with-ambiguous-grammars). I'm inclined to guess that by declaring `ELSE` to have higher precedence than `IF`, you will satisfy Sly that it does not need to warn. — John Bollinger, Apr 04 '23 at 00:39
@SeanDuggan There are two types of code in the post: (1) Sly and (2) Python (embedded in the Sly code, but directly visible). There is no C code in the post. Hence, the language tags "Sly" and "Python" apply. — Tom Karzes, Apr 04 '23 at 01:02
@TomKarzes: It looks like they may be trying to implement C in Sly, but I'll yield that they don't say as much. — Sean Duggan, Apr 04 '23 at 03:12
@SeanDuggan The post title describes it as a "Mini-C grammar", so presumably it's meant to be a simplified subset of C. — Tom Karzes, Apr 04 '23 at 05:23

score 1 · Accepted Answer · answered Apr 04 '23 at 01:03

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

Glad you solved it! You will be able to accept your self-answer 48 hours after the question was asked (you can accept the answers of others within 10 minutes, I think). Any chance you can post the Sly code you wound up with, to help others in the future? — Sean Duggan, Apr 04 '23 at 15:27

Trying to solve dangling else for a Mini-C grammar

1 Answers1